分布式鎖是一個在很多環境中非常有用的原語，它是不同進程互斥操作共享資源的唯一方法。有很多的開發庫和博客描述如何使用Redis實現DLM（Distributed Lock Manager），但是每個開發庫使用不同的方式，而且相比更復雜的設計與實現，很多庫使用一些簡單低可靠的方式來實現。

這篇文章嘗試提供更標準的算法來使用Redis實現分布式鎖。我們提出一種算法，叫做Relock，它實現了我們認為比vanilla單一實例方式更安全的DLM（分布式鎖管理）。我們希望社區分析它并提供反饋，以做為更加復雜或替代設計的一個實現。

實現

在說具體算法之前，下面有一些具體的實現可供參考.

   Redlock-rb (Ruby實現).

    Redlock-php (PHP 實現).

    Redsync.go (Go 實現).

    Redisson (Java 實現).

安全和活躍性保證

從有效分布式鎖的最小保證粒度來說，我們的模型里面只用了3個屬性，具體如下：

1. 屬性安全: 互斥行.在任何時候，只有一個客戶端可以獲得鎖.

2. 活躍屬性A: 死鎖自由. 即使一個客戶端已經擁用了已損壞或已被分割資源的鎖，但它也有可能請求其他的鎖.

3. 活躍屬性B:容錯. 只要大部分Redis節點可用, 客戶端就可以獲得和釋放鎖.

為何基于容錯的實現還不夠

要理解我們所做的改進，就要先分析下當前基于Redis的分布式鎖的做法。

使用Redis鎖住資源的最簡單的方法是創建一對key-value值。利用Redis的超時機制，key被創建為有一定的生存期，因此它最終會被釋放。而當客戶端想要釋放時，直接刪除key就行了。

一般來說這工作得很好，但有個問題: 這是系統的一個單點。如果Redis主節點掛了呢？當然，我們可以加個子節點，主節點出問題時可以切換過來。不過很可惜，這種方案不可行，因為Redis的主-從復制是異步的，我們無法用其實現互斥的安全特性。

這明顯是該模型的一種競態條件：

    客戶端A在主節點獲得了一個鎖。

    主節點掛了，而到從節點的寫同步還沒完成。

    從節點被提升為主節點。

    客戶端B獲得和A相同的鎖。注意，鎖安全性被破壞了！

有時候，在某些情況下這反而工作得很好，例如在出錯時，多個客戶端可以獲得同一個鎖。如果這正好是你想要的，那就可以使用主-從復制的方案。否則，我們建議使用這篇文章中描述的方法。

單實例的正確實現方案

在嘗試解決上文描述的單實例方案的缺陷之前，先讓我們確保針對這種簡單的情況，怎么做才是無誤的，因為這種方案對某些程序而言也是可以接受的，而且這也是我們即將描述的分布式方案的基礎。

為了獲取鎖，方法是這樣的：
 

這條指令將設置key的值，僅當其不存在時生效(NX選項), 且設置其生存期為30000毫秒(PX選項)。和key關聯的value值是"my_random_value"。這個值在所有客戶端和所有加鎖請求中是必須是唯一的。

使用隨機值主要是為了能夠安全地釋放鎖，這要同時結合這么個處理邏輯：刪除key值當且僅當其已存在并且其value值是我們所期待的。看看以下lua代碼：
 

這么做很重要，可以避免誤刪其他客戶端創建的鎖。例如某個客戶端獲得了一個鎖，但它的處理時長超過了鎖的有效時長，之后它刪除了這個鎖，而此時這個鎖可能又被其他客戶端給獲得了。僅僅做刪除是不夠安全的，很可能會把其他客戶端的鎖給刪了。結合上面的代碼，每個鎖都有個唯一的隨機值，因此僅當這個值依舊是客戶端所設置的值時，才會去刪除它。

那么應該怎樣生成這個隨機值呢？我們使用的是從/dev/urandom讀取的20個字節，但你也可以找個更簡單的方法，只要能滿足任務就行。例如，可以使用/dev/urandom初始化RC4算法，然后用其產生隨機數流。更簡單的方法是組合unix時間戳和客戶端ID, 這并不安全，但對很多環境而言也夠用了。

我們所說的key的時間，是指”鎖的有效時長“. 它代表兩種情況，一種是指鎖的自動釋放時長，另一種是指在另一個客戶端獲取鎖之前某個客戶端占用這個鎖的時長，這被限制在從鎖獲取后開始的一段時間窗口內。

現在我們已經有好的辦法獲取和釋放鎖了。在單實例非分布式系統中，只要保證節點沒掛掉，這個方法就是安全的。那么讓我們把這個概念擴展到分布式的系統中吧，那里可沒有這種保證。

Redlock 算法

在此算法的分布式版本中，我們假設有N個Redis主節點。這些節點是相互獨立的，因此我們不使用復制或其他隱式同步機制。我們已經描述過在單實例情況下如何安全地獲取鎖。我們也指出此算法將使用這種方法從單實例獲取和釋放鎖。在以下示例中，我們設置N=5（這是個比較適中的值），這樣我們需要在不同物理機或虛擬機上運行5個Redis主節點，以確保它們的出錯是盡可能獨立的。

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

•     獲取當前時間，以毫秒為單位。

•     以串行的方式嘗試從所有的N個實例中獲取鎖，使用的是相同的key值和相同的隨機value值。在從每個實例獲取鎖時，客戶端會設置一個連接超時，其時長相比鎖的自動釋放時間要短得多。例如，若鎖的自動釋放時間是10秒，那么連接超時大概設在5到50毫秒之間。這可以避免當Redis節點掛掉時，會長時間堵住客戶端：如果某個節點沒及時響應，就應該盡快轉到下個節點。

•     客戶端計算獲取所有鎖耗費的時長，方法是使用當前時間減去步驟1中的時間戳。當且僅當客戶端能從多數節點（至少3個）中獲得鎖，并且耗費的時長小于鎖的有效期時，可認為鎖已經獲得了。

•     如果鎖獲得了，它的最終有效時長將重新計算為其原時長減去步驟3中獲取鎖耗費的時長。

•     如果鎖獲取失敗了（要么是沒有鎖住N/2+1個節點，要么是鎖的最終有效時長為負數），客戶端會對所有實例進行解鎖操作（即使對那些沒有加鎖成功的實例也一樣）。

算法是異步的?

算法依賴于這樣一個假定，它在處理的時候不是（基于）同步時鐘的，每個處理中仍然使用的是本地的時間，它只是大致地以同樣地速率運行，這樣它就會有一個小的錯誤，與之相比會有一個小的自動開合的時鐘時間。這個假設很像真正世界的電腦：每一臺電腦有一個本地時鐘，通常我們使用不同的電腦會有一個很小的時鐘差。

基于這個觀點，我們需要更好地指明我們共同的互斥法則：這是保證客戶端能長時間保持狀態鎖定，其將會終止它們在有效時間內的工作（在步驟3中獲得），減去一些時間（在處理時時間差時減去了一些毫秒用來補償）。

想要了解關于系統需要一個范圍的時間差的內容可以獲取更多的信息，這篇論文是很好的參考： Leases: an efficient fault-tolerant mechanism for distributed file cache consistency.

失敗時重試

當客戶端無法獲取鎖時，它應該在一個隨機延遲后重試，從而避免多個客戶端同時試圖獲取鎖，相對應同一的同時請求（這可能會導致崩潰，沒人會勝出）。同樣的，客戶端在大多數場合下嘗試獲取鎖的速度越快，崩潰的窗口就越少（重試的需要也越少），所以實際情況下客戶端應嘗試采用復用方式發送SET命令到多個實例。

強調客戶在獲取主鎖失敗是值得的，釋放（或部分）以盡快獲得鎖，這樣沒有必要為獲取鎖鎖而去等待鍵到期（但是如果網絡分區發生變化時客戶端不能與Redis通信的情況下，需要顯性提示和等待超時）。

釋放鎖

釋放鎖是簡單的，只需要釋放所有實例的鎖即可，盡管客戶端認為有能力成功鎖住一個給出的實例。

安全參數

要問一個算法是安全的么？那么可以嘗試著去理解在不同的情景下發生了什么。我們以假設客戶端在大多數情況下都能獲得鎖來開始，所有的實例都包含相同生存周期的鍵。由于鍵是在不同的時間設定的，所以鍵也將在不同的時間超時。然而，如果第一個節點最遲在t1時刻建立（即樣品接觸的第一服務器之前），上一個鍵最遲在T2時刻建立（從上一個服務器獲得回復的時間）。可以確定的是第一個鍵在超時之前將生存至少MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT。所有其他的鑰匙將到期后，鑰匙將至少在這一次同時設置。

在過半的鍵被設置這段時間里，另一個客戶端無法獲得鎖，如果N/2+1個鍵已經存在，N/2+1 SET NX操作將不能成功。所以一個鎖被獲取，同一時刻被重復獲取是不可能的（違反互斥性）。

然而我們還想讓多個客戶端在獲取鎖的時候不能同時成功。

如果一個客戶端鎖定大部分實例的時間超過了鎖的最大有效時間（TTL基本設定） ，它將考慮鎖無效了，并解鎖。所以我們僅考慮在有效時間內大部分實例獲得鎖的情況。這種情況已經在上文中討論過， 對于MIN_VALIDITY沒有客戶端會重新獲取鎖。所以只有當鎖大多數實例的時間超過TTL時間時，多客戶端才能同時鎖住N/2+1個實例（在步驟2的“時間”即將結束時），讓鎖失效。

你是否能提供一個形式化的證明，指出現存的足夠相似的算法，或找出些bug? 那我們將感激不盡。
存活性證明

系統的存活性基于以下三個主要特性：

1.     鎖的自動釋放（key會到期）: 最終所有的key將可以被重新鎖住；

2.     一般來說，客戶端如果沒有成功獲得鎖，或者獲得了鎖并且完成了工作，都會及時釋放鎖，使得我們無需等待key自動釋放以重新獲得。

3.     當客戶端重新獲取鎖之前，它會等待一段時間，這段時間比獲取鎖本身要長得多，這是為了盡量降低資源競爭引起的腦裂條件的概率。

然而，在網絡割裂的情況下，我們得付出等同于"TTL"時間的可用性代價，如果網絡持續割裂，我們就得無限的付出這個代價。這發生于當客戶端獲取了一個鎖，而在刪除鎖之前網絡斷開了。

基本上，如果網絡無限期地持續割裂，那系統將無限期地不可用。

性能、故障恢復和文件同步

許多用戶使用Redis作為一個需要高性能的加鎖服務器，可以根據延遲動態的獲取和釋放鎖，每秒可以成功執行大量的獲取/釋放鎖操作。為了滿足這些需求，一種多路復用策略是協同N臺 Redis服務器減少延遲（或者叫做窮人的互助，也就是說，將端口置為non-blocking模式，發送所有的命令，延遲讀出所有的命令，假定客戶端和每個Redis實例的往返時間是相似的）。

然而，如果我們旨在實現一種故障系統的恢復模式，這里有另一種與持久性相關的思路。

考慮這個基本問題，假定我們完全沒有配置Redis的持久性。一個客戶端需要鎖定5個實例中的3個。其中一個允許客戶端獲取的鎖重新啟動，雖然我們可以再次為一些資源鎖定3個實例，但其它的客戶端同樣可以鎖定它，違反了排他鎖安全性。

如果我們啟用AOF持久性，情況就會得到相當的改善。例如我們可以通過發送 SHUTDOWN升級一個服務器并且重啟它。因為Redis的期限是通過語義設置的，所以服務器關閉的情況下虛擬時間仍然會流逝，我們所有的需求都得到了滿足。不管怎樣所有事務都會正常運轉只要服務器完全關閉。如果電源中斷會怎樣？如果Redis進行了相關配置，默認情況下每秒文件都會同步寫入磁盤，很有可能在重啟后我們的數據會丟失。理論上，如果我們想在任何一種實例重啟后保證鎖的安全性，我們需要確保在持久性配置中設置fsync=always。這將會在同等級別的CP系統上損失性能，傳統上這種方式用來更安全的分配鎖。

不管怎樣事情比我們初次瞥見他們看起來好些。基本上算法的安全性得到保留，就算是當一個實例在故障后重啟，它也將不再參與任何當前活躍的鎖的分配。因此當實例重啟時，當前所有活動鎖的設置將從鎖定的實例中獲取除它重新加入系統。

為了保證這一點，我們只需要做一個實例，在超過最大TTL后，崩潰，不可用，那么就需要時間去獲取所有存在著的鎖的鑰匙，當實例崩潰時，其就會變得無效，會被自動釋放。

使用延時重啟可以基本上實現安全，甚至不需要利用任何Redis的持久化特性，但是這存在著另外的副作用。舉例來說，如果大量的實例崩潰，系統變得全局不可用，那么TTL（這里的全局意味著根本就沒有資源可用，在這個時間內所有的資源都會被鎖定）。

讓算法更可靠: 擴展鎖

如果客戶工作的執行是由小步驟組成，那么它就可以在默認時間里默認使用更小的鎖，并擴展了算法去實現的一個鎖的擴展機制。當鎖的有效性接近于一個低值，那么通常是客戶端在運算中處于居中位置。當鎖被取得時，可能擴展的鎖通過發送一個Lua腳本到所有的實例，這個實例是擴展TTL的鑰匙，如果鑰匙存在，那么它的值就是客戶端復制的隨機值。

客戶端應該僅考慮鎖的重新取得，如果它可以被擴展，鎖就會在有效時間內進入大量實例（基本的算法使用非常類似于獲取鎖的使用）。 

雖然這不是從技術上去改變算法，但是無論如何嘗試獲取鎖的最大次數是需要限制的，否則的話會違反活躍性中的一個屬性。