🥇使用Redis進行分散式鎖定

嘿哈布爾！

今天我們提請您注意一篇關於使用Redis實現分散式鎖定的複雜文章的翻譯，並邀請您談論Redis作為主題的前景。《Redlock 演算法分析》一書的作者 Martin Kleppmann高負載應用”，給定這裡.

分散式鎖定是一種非常有用的原語，在許多環境中使用，在這些環境中，不同的程序必須以互斥的方式處理共享資源。

有許多函式庫和貼文描述如何使用 Redis 實作 DLM（分散式鎖定管理器），但每個函式庫都採用不同的方法，與稍微複雜的設計可實現的保證相比，它們提供的保證相當弱。

在本文中，我們將嘗試描述一個條件規範演算法，示範如何使用 Redis 實現分散式鎖定。我們將討論一種稱為 雷德洛克，它實作了分散式鎖定管理器，在我們看來，該演算法比通常的單一實例方法更安全。我們希望社群能夠對其進行分析、提供回饋，並將其用作更複雜或替代專案的起點。

實施

在繼續描述演算法之前，我們提供了幾個現成實現的連結。它們可以作為參考。

Redlock-rb （Ruby 的實作）。還有叉 Redlock-rb，它添加了一個包（gem）以方便分發，但不僅僅是為了這個。
Redlock-py （Python 實作）。
空氣鎖（Asyncio Python 的實作）。
Redlock-php （PHP 的實作）。
PHPRedis互斥體（PHP 的另一個實作）
cheprasov/php-redis-lock （PHP 鎖庫）
紅同步（Go 的實現）。
雷迪森（Java 的實作）。
Redis::DistLock （Perl 的實現）。
Redlock-cpp （C++ 的實作）。
Redlock-cs （C#/.NET 的實作）。
紅鎖網（C#/.NET 的實作）。支援異步和鎖擴展。
猩紅鎖（具有可配置資料儲存的 C# .NET 實作）
紅鎖網（C# .NET 的實作）
節點紅鎖（NodeJS 的實作）。包括對擴展鎖的支援。

安全性和可用性保證

我們將僅使用三個屬性來對我們的設計進行建模，我們認為這三個屬性提供了有效使用分散式鎖定所需的最低保證。

安全屬性：互斥。在任何給定時間，只有一個客戶端可以持有鎖。
可用性屬性A：無死鎖。即使鎖定資源的用戶端發生故障或位於不同的磁碟區上，最終也總是有可能獲得鎖。
可用性屬性B：容錯性。只要大多數 Redis 節點正在運行，客戶端就能夠取得和釋放鎖定。

為什麼在這種情況下基於故障復原的實現還不夠
為了了解我們要改進的地方，讓我們分析一下大多數基於 Redis 的分散式鎖定庫的現狀。

使用 Redis 鎖定資源的最簡單方法是在實例中建立金鑰。通常，建立的金鑰具有有限的生命週期，這是使用 Redis 中提供的過期功能來實現的，因此該金鑰遲早會被釋放（我們清單中的屬性 2）。當客戶端需要釋放資源時，它會刪除該金鑰。

乍一看，這個解決方案運作得很好，但有一個問題：我們的架構會產生單點故障。如果主機 Redis 實例發生故障會發生什麼事？那我們就加入一個奴隸吧！如果演示者不在，我們將使用它。不幸的是，這個選項不可行。這樣做的話，我們將無法正確實現保證安全性所需的互斥屬性，因為Redis中的複製是異步的。

顯然，在這樣的模型中會出現競爭條件：

客戶端 A 取得主伺服器上的鎖。
在密鑰條目傳輸到從屬設備之前主設備發生故障。
追隨者晉升為領導者。
客戶端 B 取得 A 已鎖定的相同資源的鎖定。 違反安全！

有時，在特殊情況下，例如故障，許多客戶可以同時持有鎖，這是完全正常的。在這種情況下，可以應用基於複製的解決方案。否則，我們建議使用本文中所述的解決方案。

單一實例正確實現

在嘗試克服上述單一實例配置的缺點之前，讓我們了解如何正確處理這個簡單的情況，因為該解決方案實際上在不時可以接受競爭條件的應用程式中有效，並且還因為阻塞單一實例用作此處描述的分散式演算法中使用的基礎。

若要取得鎖，請執行下列操作：

SET resource_name my_random_value NX PX 30000

只有當金鑰尚不存在時，此指令才會安裝金鑰（NX 選項），有效期為 30000 毫秒（PX 選項）。鍵設定為“myrandomvalue」該值在所有客戶端和所有鎖定請求中必須是唯一的。
基本上，使用一個隨機值來安全地釋放鎖，並透過一個腳本告訴 Redis：僅在密鑰存在且儲存在其中的值正是預期的情況下才刪除該密鑰。這是使用以下 Lua 腳本實現的：

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

這對於防止另一個客戶端持有的鎖被刪除非常重要。例如，客戶端可能會取得一個鎖，然後在某個比第一個鎖持續時間更長的操作中被鎖定（以便金鑰有時間過期），然後刪除其他某個客戶端放置的鎖。
使用簡單的 DEL 是不安全的，因為客戶端可以刪除另一個客戶端持有的鎖。相反，當使用上面的腳本時，每個鎖都用隨機字串“簽名”，因此只有先前放置它的客戶端才能刪除它。

這個隨機字串應該是什麼？我猜它應該是來自 /dev/urandom 的 20 個字節，但是您可以找到更便宜的方法來使字串足夠獨特，以滿足您的目的。例如，可以使用 /dev/urandom 為 RC4 播種，然後從中產生偽隨機流。一個更簡單的解決方案涉及以微秒解析度表示的 Unix 時間加上客戶端 ID 的組合；它並不那麼安全，但在大多數情況下它可能可以勝任任務。

我們用來衡量密鑰生命週期的時間稱為「鎖生命週期」。該值既是自動釋放鎖之前的時間量，也是客戶端在另一個客戶端可以輪流鎖定該資源之前必須完成操作的時間量，而實際上不會違反互斥保證。此保證僅限於一定的時間範圍，該時間範圍從購買鎖的那一刻開始。

所以我們討論了一個獲取和釋放鎖的好方法。該系統（如果我們談論的是由單一且始終可用的實例組成的非分散式系統）是安全的。讓我們將這個概念擴展到分散式系統，但我們沒有這樣的保證。

Redlock演算法

這個演算法的分散式版本假設我們有 N 個 Redis 主節點。這些節點彼此完全獨立，因此我們不使用複製或任何其他隱式協調系統。我們已經介紹瞭如何安全地獲取和釋放單一實例上的鎖。我們理所當然地認為演算法在處理單一實例時將完全使用此方法。在我們的範例中，我們將 N 設為 5，這是一個合理的值。因此，我們需要在不同的電腦或虛擬機器上使用 5 個 Redis 主節點，以確保它們在很大程度上彼此獨立運作。

為了取得鎖，客戶端執行以下操作：

取得當前時間（以毫秒為單位）。
順序嘗試取得所有 N 個實例的鎖，在所有情況下使用相同的金鑰名稱和隨機值。在第 2 階段，當客戶端在每個執行個體的基礎上設定鎖定時，用戶端會使用比自動釋放鎖定的時間足夠短的延遲來取得鎖定。例如，如果阻塞持續時間為 10 秒，則延遲可能在 ~5-50 毫秒的範圍內。這消除了客戶端在嘗試到達失敗的 Redis 節點時可能會長時間保持阻塞的情況：如果實例不可用，那麼我們會盡快嘗試連接到另一個實例。
為了獲得鎖定，客戶端運算已經過了多少時間；為此，它從實際時間值中減去在步驟 1 中獲得的時間戳。當且僅當客戶端能夠獲得大多數實例（至少 3 個）的鎖定時，以及它所花費的總時間獲取鎖，小於鎖持續時間，則認為已經取得鎖。
如果已取得鎖，則鎖定持續時間為原始鎖定持續時間減去步驟3中計算出的經過時間。
如果客戶端因某種原因未能獲得鎖（或無法鎖定 N/2+1 個實例，或鎖定持續時間為負），那麼它將嘗試解鎖所有實例（甚至是那些它認為無法鎖定的實例）堵塞）。

該演算法是異步的嗎？

演算法基於這樣的假設：雖然沒有所有進程都可以工作的同步時鐘，但每個進程中的本地時間仍然以大致相同的速度流動，並且與鎖定之後的總時間相比，誤差很小。自動釋放。這種假設與普通計算機的典型情況非常相似：每台計算機都有一個本地時鐘，我們通常可以認為不同計算機之間的時間差異很小。

此時，我們必須更加仔細地制定我們的互斥規則：只有持有鎖的客戶端在鎖有效期間（這個值在步驟3中獲得）退出，再減去一些時間（總共幾個毫秒來補償進程之間的時間差）。

以下有趣的文章詳細介紹了這類需要協調時間間隔的系統：租約：分散式檔案快取一致性的高效能容錯機制.

失敗重試

當客戶端取得鎖定失敗時，必須在隨機延遲後重試；這樣做是為了使多個客戶端同時嘗試獲取相同資源上的鎖去同步（這可能導致沒有贏家的「裂腦」情況）。此外，用戶端嘗試取得大多數 Redis 實例上的鎖的速度越快，發生裂腦情況的視窗就越窄（並且重試的需要就越少）。因此，理想情況下，客戶端應嘗試使用多路復用同時向 N 個實例發送 SET 命令。

這裡值得強調的是，對於未能獲取大部分鎖的客戶端來說，釋放（部分）獲取的鎖是多麼重要，這樣他們就不必等待密鑰過期才能再次獲取資源上的鎖（儘管如果發生網絡碎片，並且客戶端與Redis 執行個體失去聯繫，那麼您必須在等待金鑰過期時付出可用性損失）。

釋放鎖

釋放鎖定是一個簡單的操作，只需要解鎖所有實例，無論客戶端是否已成功鎖定特定實例。

安全考慮

演算法安全嗎？讓我們試著想像一下不同場景下會發生什麼事。

首先，我們假設客戶端能夠獲得大多數實例的鎖定。每個實例都將包含一個具有相同生命週期的金鑰。但是，每個密鑰都是在不同的時間安裝的，因此它們將在不同的時間過期。但是，如果第一個金鑰的安裝時間不低於 T1（我們在聯繫第一台伺服器之前選擇的時間），且最後一個金鑰的安裝時間不低於 T2（收到回應的時間）來自最後一個伺服器），那麼我們有信心集合中第一個過期的密鑰至少會存活 MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT。所有其他密鑰將在稍後過期，因此我們可以確定所有密鑰至少在這段時間同時有效。

在大多數金鑰保持有效的時間內，另一個用戶端將無法取得鎖，因為如果 N/2+1 個金鑰已存在，則 N/2+1 SET NX 操作無法成功。因此，一旦取得了鎖，就不可能在同一時刻再次取得它（這會違反互斥性質）。
但是，我們希望確保多個客戶端嘗試同時取得鎖不能同時成功。

如果客戶端鎖定大多數實例的時間大約或超過最大鎖定持續時間，它將認為鎖定無效並解鎖實例。因此，我們只需要考慮客戶端在小於到期日的時間內阻止了大多數實例的情況。在此情況下，針對上述論證，期間 MIN_VALIDITY 任何客戶端都不能重新取得鎖。因此，只有當鎖定多數實例的時間大於 TTL 時間時，多個客戶端才能同時鎖定 N/2+1 個實例（在第 2 階段結束時結束），導致鎖定無效。

您能否提供正式的安全證明，指出現有的類似演算法，或發現上述演算法中的錯誤？

輔助功能注意事項

系統可用性取決於三個主要特徵：

自動釋放鎖（當金鑰過期時）：金鑰最終將再次可用於鎖定。
事實上，當所需的鎖尚未取得或已取得且作業已完成時，客戶端通常會透過刪除鎖定來互相幫助；因此我們很可能不必等待密鑰過期來重新取得鎖。
事實上，當客戶端需要重試獲取鎖時，它等待的時間比獲取大多數鎖所需的時間要長。這降低了爭奪資源時出現腦裂情況的可能性。

但是，可用性懲罰等於網段的 TTL，因此如果存在連續的網段，則懲罰可能是無限期的。每當客戶端取得鎖，然後在釋放鎖之前轉移到另一個段時，就會發生這種情況。

原則上，給定無限連續的網路段，系統可以在無限長的時間內保持不可用狀態。

效能、故障轉移和 fsync

許多人使用Redis是因為他們需要較高的鎖定伺服器效能，包括獲取和釋放鎖定所需的延遲以及每秒可以完成的獲取/釋放次數。為了滿足這個需求，有一個策略是與N個Redis伺服器進行通訊以減少延遲。這是一種多路復用策略（或“窮人的多路復用”，其中套接字置於非阻塞模式，發送所有命令，並稍後讀取命令，假設客戶端和每個實例之間的往返時間相似）。

然而，如果我們努力創建一個能夠可靠地從故障中恢復的模型，我們還必須考慮與長期資料儲存相關的考慮。

基本上，為了澄清這個問題，我們假設我們配置的 Redis 根本沒有長期資料儲存。客戶端成功封鎖了 3 個實例中的 5 個。客戶端設法阻止的實例之一重新啟動，此時同一資源又出現了 3 個實例，我們可以阻止這些實例，而另一個客戶端又可以阻止重新啟動的實例，這違反了安全屬性假定鎖的排他性。

如果啟用資料提前（AOF），情況會略有改善。例如，您可以透過發送 SHUTDOWN 命令並重新啟動伺服器來升級伺服器。由於 Redis 中的過期操作在語義上是透過這樣的方式實現的：即使伺服器關閉，時間也會繼續流動，因此我們的所有要求都很好。只要保證正常關機，這是正常的。停電時該怎麼辦？如果 Redis 預設配置為每秒在磁碟上進行 fsync 同步，那麼重新啟動後我們可能會找不到金鑰。理論上，如果我們想確保實例重新啟動過程中的鎖定安全，我們應該啟用 fsync=always 在長期資料儲存的設定中。這將完全降低效能，降低到傳統上用於安全實現分散式鎖的 CP 系統的水平。

但情況比乍看之下要好。原則上，演算法的安全性得以保留，因為當實例在故障後重新啟動時，它不再參與當前活動的任何鎖定。

為了確保這一點，我們只需要確保在發生故障後，實例在略超過我們使用的最大 TTL 的時間內保持不可用狀態。這樣，我們將等到到期日並自動釋放故障時處於活動狀態的所有金鑰。

使用延遲重啟，即使在 Redis 中沒有任何長期持久性的情況下，原則上也可以實現安全性。但請注意，這可能會因違反可訪問性而被處以罰款。例如，如果大多數實例發生故障，系統將在 TTL 內變得全域不可用（並且在此期間不能阻止任何資源）。

我們提高了演算法的可用性：我們擴展了阻塞

如果用戶端執行的工作由小步驟組成，則可以減少預設鎖定持續時間並實現擴展鎖定的機制。原則上，如果客戶端正忙於計算，並且鎖定過期值過低，您可以向所有實例發送一個Lua 腳本，延長密鑰的TTL，前提是密鑰仍然存在，並且其值仍然是鎖定時獲得的隨機值。已取得鎖。

只有當客戶端在有效期內成功鎖定了大多數執行個體時，才應考慮重新取得鎖定。

確實，從技術上講，該演算法不會改變，因此必須限制重複嘗試獲取鎖的最大次數，否則將違反可訪問性屬性。

來源： www.habr.com

使用 Redis 進行分散式鎖定

添加評論取消回复

使用 Redis 進行分散式鎖定

添加評論 取消回复

添加評論取消回复