分布式鎖是一個在很多環(huán)境中非常有用的原語，它是不同進程互斥操作共享資源的唯一方法。有很多的開發(fā)庫和博客描述如何使用Redis實現(xiàn)DLM（Distributed Lock Manager），但是每個開發(fā)庫使用不同的方式，而且相比更復(fù)雜的設(shè)計與實現(xiàn)，很多庫使用一些簡單低可靠的方式來實現(xiàn)。
這篇文章嘗試提供更標準的算法來使用Redis實現(xiàn)分布式鎖。我們提出一種算法，叫做Relock，它實現(xiàn)了我們認為比vanilla單一實例方式更安全的DLM（分布式鎖管理）。我們希望社區(qū)分析它并提供反饋，以做為更加復(fù)雜或替代設(shè)計的一個實現(xiàn)。
實現(xiàn)
在說具體算法之前，下面有一些具體的實現(xiàn)可供參考.
安全和活躍性保證
從有效分布式鎖的最小保證粒度來說，我們的模型里面只用了3個屬性，具體如下：
1. 屬性安全: 互斥行.在任何時候，只有一個客戶端可以獲得鎖.
2. 活躍屬性A: 死鎖自由. 即使一個客戶端已經(jīng)擁用了已損壞或已被分割資源的鎖，但它也有可能請求其他的鎖.
3. 活躍屬性B:容錯. 只要大部分Redis節(jié)點可用, 客戶端就可以獲得和釋放鎖.
為何基于容錯的實現(xiàn)還不夠
要理解我們所做的改進，就要先分析下當前基于Redis的分布式鎖的做法。
使用Redis鎖住資源的最簡單的方法是創(chuàng)建一對key-value值。利用Redis的超時機制，key被創(chuàng)建為有一定的生存期，因此它最終會被釋放。而當客戶端想要釋放時，直接刪除key就行了。
一般來說這工作得很好，但有個問題: 這是系統(tǒng)的一個單點。如果Redis主節(jié)點掛了呢？當然，我們可以加個子節(jié)點，主節(jié)點出問題時可以切換過來。不過很可惜，這種方案不可行，因為Redis的主-從復(fù)制是異步的，我們無法用其實現(xiàn)互斥的安全特性。
這明顯是該模型的一種競態(tài)條件：
有時候，在某些情況下這反而工作得很好，例如在出錯時，多個客戶端可以獲得同一個鎖。如果這正好是你想要的，那就可以使用主-從復(fù)制的方案。否則，我們建議使用這篇文章中描述的方法。
單實例的正確實現(xiàn)方案
在嘗試解決上文描述的單實例方案的缺陷之前，先讓我們確保針對這種簡單的情況，怎么做才是無誤的，因為這種方案對某些程序而言也是可以接受的，而且這也是我們即將描述的分布式方案的基礎(chǔ)。
為了獲取鎖，方法是這樣的：
這條指令將設(shè)置key的值，僅當其不存在時生效(NX選項), 且設(shè)置其生存期為30000毫秒(PX選項)。和key關(guān)聯(lián)的value值是"my_random_value"。這個值在所有客戶端和所有加鎖請求中是必須是唯一的。
使用隨機值主要是為了能夠安全地釋放鎖，這要同時結(jié)合這么個處理邏輯：刪除key值當且僅當其已存在并且其value值是我們所期待的?？纯匆韵耹ua代碼：
這么做很重要，可以避免誤刪其他客戶端創(chuàng)建的鎖。例如某個客戶端獲得了一個鎖，但它的處理時長超過了鎖的有效時長，之后它刪除了這個鎖，而此時這個鎖可能又被其他客戶端給獲得了。僅僅做刪除是不夠安全的，很可能會把其他客戶端的鎖給刪了。結(jié)合上面的代碼，每個鎖都有個唯一的隨機值，因此僅當這個值依舊是客戶端所設(shè)置的值時，才會去刪除它。
那么應(yīng)該怎樣生成這個隨機值呢？我們使用的是從/dev/urandom讀取的20個字節(jié)，但你也可以找個更簡單的方法，只要能滿足任務(wù)就行。例如，可以使用/dev/urandom初始化RC4算法，然后用其產(chǎn)生隨機數(shù)流。更簡單的方法是組合unix時間戳和客戶端ID, 這并不安全，但對很多環(huán)境而言也夠用了。
我們所說的key的時間，是指”鎖的有效時長“. 它代表兩種情況，一種是指鎖的自動釋放時長，另一種是指在另一個客戶端獲取鎖之前某個客戶端占用這個鎖的時長，這被限制在從鎖獲取后開始的一段時間窗口內(nèi)。
現(xiàn)在我們已經(jīng)有好的辦法獲取和釋放鎖了。在單實例非分布式系統(tǒng)中，只要保證節(jié)點沒掛掉，這個方法就是安全的。那么讓我們把這個概念擴展到分布式的系統(tǒng)中吧，那里可沒有這種保證。
Redlock 算法
在此算法的分布式版本中，我們假設(shè)有N個Redis主節(jié)點。這些節(jié)點是相互獨立的，因此我們不使用復(fù)制或其他隱式同步機制。我們已經(jīng)描述過在單實例情況下如何安全地獲取鎖。我們也指出此算法將使用這種方法從單實例獲取和釋放鎖。在以下示例中，我們設(shè)置N=5（這是個比較適中的值），這樣我們需要在不同物理機或虛擬機上運行5個Redis主節(jié)點，以確保它們的出錯是盡可能獨立的。
為了獲取鎖，客戶端執(zhí)行以下操作：
算法是異步的?
算法依賴于這樣一個假定，它在處理的時候不是（基于）同步時鐘的，每個處理中仍然使用的是本地的時間，它只是大致地以同樣地速率運行，這樣它就會有一個小的錯誤，與之相比會有一個小的自動開合的時鐘時間。這個假設(shè)很像真正世界的電腦：每一臺電腦有一個本地時鐘，通常我們使用不同的電腦會有一個很小的時鐘差。
基于這個觀點，我們需要更好地指明我們共同的互斥法則：這是保證客戶端能長時間保持狀態(tài)鎖定，其將會終止它們在有效時間內(nèi)的工作（在步驟3中獲得），減去一些時間（在處理時時間差時減去了一些毫秒用來補償）。
想要了解關(guān)于系統(tǒng)需要一個范圍的時間差的內(nèi)容可以獲取更多的信息，這篇論文是很好的參考： Leases: an efficient fault-tolerant mechanism for distributed file cache consistency.
失敗時重試
當客戶端無法獲取鎖時，它應(yīng)該在一個隨機延遲后重試，從而避免多個客戶端同時試圖獲取鎖，相對應(yīng)同一的同時請求（這可能會導(dǎo)致崩潰，沒人會勝出）。同樣的，客戶端在大多數(shù)場合下嘗試獲取鎖的速度越快，崩潰的窗口就越少（重試的需要也越少），所以實際情況下客戶端應(yīng)嘗試采用復(fù)用方式發(fā)送SET命令到多個實例。
強調(diào)客戶在獲取主鎖失敗是值得的，釋放（或部分）以盡快獲得鎖，這樣沒有必要為獲取鎖鎖而去等待鍵到期（但是如果網(wǎng)絡(luò)分區(qū)發(fā)生變化時客戶端不能與Redis通信的情況下，需要顯性提示和等待超時）。
釋放鎖
釋放鎖是簡單的，只需要釋放所有實例的鎖即可，盡管客戶端認為有能力成功鎖住一個給出的實例。
安全參數(shù)
要問一個算法是安全的么？那么可以嘗試著去理解在不同的情景下發(fā)生了什么。我們以假設(shè)客戶端在大多數(shù)情況下都能獲得鎖來開始，所有的實例都包含相同生存周期的鍵。由于鍵是在不同的時間設(shè)定的，所以鍵也將在不同的時間超時。然而，如果第一個節(jié)點最遲在t1時刻建立（即樣品接觸的第一服務(wù)器之前），上一個鍵最遲在T2時刻建立（從上一個服務(wù)器獲得回復(fù)的時間）?？梢源_定的是第一個鍵在超時之前將生存至少MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT。所有其他的鑰匙將到期后，鑰匙將至少在這一次同時設(shè)置。
在過半的鍵被設(shè)置這段時間里，另一個客戶端無法獲得鎖，如果N/2+1個鍵已經(jīng)存在，N/2+1 SET NX操作將不能成功。所以一個鎖被獲取，同一時刻被重復(fù)獲取是不可能的（違反互斥性）。
然而我們還想讓多個客戶端在獲取鎖的時候不能同時成功。
如果一個客戶端鎖定大部分實例的時間超過了鎖的最大有效時間（TTL基本設(shè)定） ，它將考慮鎖無效了，并解鎖。所以我們僅考慮在有效時間內(nèi)大部分實例獲得鎖的情況。這種情況已經(jīng)在上文中討論過， 對于MIN_VALIDITY沒有客戶端會重新獲取鎖。所以只有當鎖大多數(shù)實例的時間超過TTL時間時，多客戶端才能同時鎖住N/2+1個實例（在步驟2的“時間”即將結(jié)束時），讓鎖失效。
你是否能提供一個形式化的證明，指出現(xiàn)存的足夠相似的算法，或找出些bug? 那我們將感激不盡。
存活性證明
系統(tǒng)的存活性基于以下三個主要特性：
然而，在網(wǎng)絡(luò)割裂的情況下，我們得付出等同于"TTL"時間的可用性代價，如果網(wǎng)絡(luò)持續(xù)割裂，我們就得無限的付出這個代價。這發(fā)生于當客戶端獲取了一個鎖，而在刪除鎖之前網(wǎng)絡(luò)斷開了。
基本上，如果網(wǎng)絡(luò)無限期地持續(xù)割裂，那系統(tǒng)將無限期地不可用。
性能、故障恢復(fù)和文件同步
許多用戶使用Redis作為一個需要高性能的加鎖服務(wù)器，可以根據(jù)延遲動態(tài)的獲取和釋放鎖，每秒可以成功執(zhí)行大量的獲取/釋放鎖操作。為了滿足這些需求，一種多路復(fù)用策略是協(xié)同N臺 Redis服務(wù)器減少延遲（或者叫做窮人的互助，也就是說，將端口置為non-blocking模式，發(fā)送所有的命令，延遲讀出所有的命令，假定客戶端和每個Redis實例的往返時間是相似的）。
然而，如果我們旨在實現(xiàn)一種故障系統(tǒng)的恢復(fù)模式，這里有另一種與持久性相關(guān)的思路。
考慮這個基本問題，假定我們完全沒有配置Redis的持久性。一個客戶端需要鎖定5個實例中的3個。其中一個允許客戶端獲取的鎖重新啟動，雖然我們可以再次為一些資源鎖定3個實例，但其它的客戶端同樣可以鎖定它，違反了排他鎖安全性。
如果我們啟用AOF持久性，情況就會得到相當?shù)母纳?。例如我們可以通過發(fā)送 SHUTDOWN升級一個服務(wù)器并且重啟它。因為Redis的期限是通過語義設(shè)置的，所以服務(wù)器關(guān)閉的情況下虛擬時間仍然會流逝，我們所有的需求都得到了滿足。不管怎樣所有事務(wù)都會正常運轉(zhuǎn)只要服務(wù)器完全關(guān)閉。如果電源中斷會怎樣？如果Redis進行了相關(guān)配置，默認情況下每秒文件都會同步寫入磁盤，很有可能在重啟后我們的數(shù)據(jù)會丟失。理論上，如果我們想在任何一種實例重啟后保證鎖的安全性，我們需要確保在持久性配置中設(shè)置fsync=always。這將會在同等級別的CP系統(tǒng)上損失性能，傳統(tǒng)上這種方式用來更安全的分配鎖。
不管怎樣事情比我們初次瞥見他們看起來好些?；旧纤惴ǖ陌踩缘玫奖Ａ簦退闶钱斠粋€實例在故障后重啟，它也將不再參與任何當前活躍的鎖的分配。因此當實例重啟時，當前所有活動鎖的設(shè)置將從鎖定的實例中獲取除它重新加入系統(tǒng)。
為了保證這一點，我們只需要做一個實例，在超過最大TTL后，崩潰，不可用，那么就需要時間去獲取所有存在著的鎖的鑰匙，當實例崩潰時，其就會變得無效，會被自動釋放。
使用延時重啟可以基本上實現(xiàn)安全，甚至不需要利用任何Redis的持久化特性，但是這存在著另外的副作用。舉例來說，如果大量的實例崩潰，系統(tǒng)變得全局不可用，那么TTL（這里的全局意味著根本就沒有資源可用，在這個時間內(nèi)所有的資源都會被鎖定）。
讓算法更可靠: 擴展鎖
如果客戶工作的執(zhí)行是由小步驟組成，那么它就可以在默認時間里默認使用更小的鎖，并擴展了算法去實現(xiàn)的一個鎖的擴展機制。當鎖的有效性接近于一個低值，那么通常是客戶端在運算中處于居中位置。當鎖被取得時，可能擴展的鎖通過發(fā)送一個Lua腳本到所有的實例，這個實例是擴展TTL的鑰匙，如果鑰匙存在，那么它的值就是客戶端復(fù)制的隨機值。
客戶端應(yīng)該僅考慮鎖的重新取得，如果它可以被擴展，鎖就會在有效時間內(nèi)進入大量實例（基本的算法使用非常類似于獲取鎖的使用）。
雖然這不是從技術(shù)上去改變算法，但是無論如何嘗試獲取鎖的最大次數(shù)是需要限制的，否則的話會違反活躍性中的一個屬性。
