分布式鎖是一個(gè)在很多環(huán)境中非常有用的原語(yǔ)，它是不同進(jìn)程互斥操作共享資源的唯一方法。有很多的開(kāi)發(fā)庫(kù)和博客描述如何使用Redis實(shí)現(xiàn)DLM（Distributed Lock Manager），但是每個(gè)開(kāi)發(fā)庫(kù)使用不同的方式，而且相比更復(fù)雜的設(shè)計(jì)與實(shí)現(xiàn)，很多庫(kù)使用一些簡(jiǎn)單低可靠的方式來(lái)實(shí)現(xiàn)。

這篇文章嘗試提供更標(biāo)準(zhǔn)的算法來(lái)使用Redis實(shí)現(xiàn)分布式鎖。我們提出一種算法，叫做Relock，它實(shí)現(xiàn)了我們認(rèn)為比vanilla單一實(shí)例方式更安全的DLM（分布式鎖管理）。我們希望社區(qū)分析它并提供反饋，以做為更加復(fù)雜或替代設(shè)計(jì)的一個(gè)實(shí)現(xiàn)。

實(shí)現(xiàn)

在說(shuō)具體算法之前，下面有一些具體的實(shí)現(xiàn)可供參考.

•    Redlock-rb (Ruby實(shí)現(xiàn)).
•     Redlock-php (PHP 實(shí)現(xiàn)).
•     Redsync.go (Go 實(shí)現(xiàn)).
•     Redisson (Java 實(shí)現(xiàn)).

安全和活躍性保證

從有效分布式鎖的最小保證粒度來(lái)說(shuō)，我們的模型里面只用了3個(gè)屬性，具體如下：

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

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

3. 活躍屬性B:容錯(cuò). 只要大部分Redis節(jié)點(diǎn)可用, 客戶端就可以獲得和釋放鎖.

為何基于容錯(cuò)的實(shí)現(xiàn)還不夠

要理解我們所做的改進(jìn)，就要先分析下當(dāng)前基于Redis的分布式鎖的做法。

使用Redis鎖住資源的最簡(jiǎn)單的方法是創(chuàng)建一對(duì)key-value值。利用Redis的超時(shí)機(jī)制，key被創(chuàng)建為有一定的生存期，因此它最終會(huì)被釋放。而當(dāng)客戶端想要釋放時(shí)，直接刪除key就行了。

一般來(lái)說(shuō)這工作得很好，但有個(gè)問(wèn)題: 這是系統(tǒng)的一個(gè)單點(diǎn)。如果Redis主節(jié)點(diǎn)掛了呢？當(dāng)然，我們可以加個(gè)子節(jié)點(diǎn)，主節(jié)點(diǎn)出問(wèn)題時(shí)可以切換過(guò)來(lái)。不過(guò)很可惜，這種方案不可行，因?yàn)镽edis的主-從復(fù)制是異步的，我們無(wú)法用其實(shí)現(xiàn)互斥的安全特性。

這明顯是該模型的一種競(jìng)態(tài)條件：

•     客戶端A在主節(jié)點(diǎn)獲得了一個(gè)鎖。
•     主節(jié)點(diǎn)掛了，而到從節(jié)點(diǎn)的寫(xiě)同步還沒(méi)完成。
•     從節(jié)點(diǎn)被提升為主節(jié)點(diǎn)。
•     客戶端B獲得和A相同的鎖。注意，鎖安全性被破壞了！

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

單實(shí)例的正確實(shí)現(xiàn)方案

在嘗試解決上文描述的單實(shí)例方案的缺陷之前，先讓我們確保針對(duì)這種簡(jiǎn)單的情況，怎么做才是無(wú)誤的，因?yàn)檫@種方案對(duì)某些程序而言也是可以接受的，而且這也是我們即將描述的分布式方案的基礎(chǔ)。

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

這條指令將設(shè)置key的值，僅當(dāng)其不存在時(shí)生效(NX選項(xiàng)), 且設(shè)置其生存期為30000毫秒(PX選項(xiàng))。和key關(guān)聯(lián)的value值是"my_random_value"。這個(gè)值在所有客戶端和所有加鎖請(qǐng)求中是必須是唯一的。

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

這么做很重要，可以避免誤刪其他客戶端創(chuàng)建的鎖。例如某個(gè)客戶端獲得了一個(gè)鎖，但它的處理時(shí)長(zhǎng)超過(guò)了鎖的有效時(shí)長(zhǎng)，之后它刪除了這個(gè)鎖，而此時(shí)這個(gè)鎖可能又被其他客戶端給獲得了。僅僅做刪除是不夠安全的，很可能會(huì)把其他客戶端的鎖給刪了。結(jié)合上面的代碼，每個(gè)鎖都有個(gè)唯一的隨機(jī)值，因此僅當(dāng)這個(gè)值依舊是客戶端所設(shè)置的值時(shí)，才會(huì)去刪除它。

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

我們所說(shuō)的key的時(shí)間，是指”鎖的有效時(shí)長(zhǎng)“. 它代表兩種情況，一種是指鎖的自動(dòng)釋放時(shí)長(zhǎng)，另一種是指在另一個(gè)客戶端獲取鎖之前某個(gè)客戶端占用這個(gè)鎖的時(shí)長(zhǎng)，這被限制在從鎖獲取后開(kāi)始的一段時(shí)間窗口內(nèi)。

現(xiàn)在我們已經(jīng)有好的辦法獲取和釋放鎖了。在單實(shí)例非分布式系統(tǒng)中，只要保證節(jié)點(diǎn)沒(méi)掛掉，這個(gè)方法就是安全的。那么讓我們把這個(gè)概念擴(kuò)展到分布式的系統(tǒng)中吧，那里可沒(méi)有這種保證。

Redlock 算法

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

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

•     獲取當(dāng)前時(shí)間，以毫秒為單位。
•     以串行的方式嘗試從所有的N個(gè)實(shí)例中獲取鎖，使用的是相同的key值和相同的隨機(jī)value值。在從每個(gè)實(shí)例獲取鎖時(shí)，客戶端會(huì)設(shè)置一個(gè)連接超時(shí)，其時(shí)長(zhǎng)相比鎖的自動(dòng)釋放時(shí)間要短得多。例如，若鎖的自動(dòng)釋放時(shí)間是10秒，那么連接超時(shí)大概設(shè)在5到50毫秒之間。這可以避免當(dāng)Redis節(jié)點(diǎn)掛掉時(shí)，會(huì)長(zhǎng)時(shí)間堵住客戶端：如果某個(gè)節(jié)點(diǎn)沒(méi)及時(shí)響應(yīng)，就應(yīng)該盡快轉(zhuǎn)到下個(gè)節(jié)點(diǎn)。
•     客戶端計(jì)算獲取所有鎖耗費(fèi)的時(shí)長(zhǎng)，方法是使用當(dāng)前時(shí)間減去步驟1中的時(shí)間戳。當(dāng)且僅當(dāng)客戶端能從多數(shù)節(jié)點(diǎn)（至少3個(gè)）中獲得鎖，并且耗費(fèi)的時(shí)長(zhǎng)小于鎖的有效期時(shí)，可認(rèn)為鎖已經(jīng)獲得了。
•     如果鎖獲得了，它的最終有效時(shí)長(zhǎng)將重新計(jì)算為其原時(shí)長(zhǎng)減去步驟3中獲取鎖耗費(fèi)的時(shí)長(zhǎng)。
•     如果鎖獲取失敗了（要么是沒(méi)有鎖住N/2+1個(gè)節(jié)點(diǎn)，要么是鎖的最終有效時(shí)長(zhǎng)為負(fù)數(shù)），客戶端會(huì)對(duì)所有實(shí)例進(jìn)行解鎖操作（即使對(duì)那些沒(méi)有加鎖成功的實(shí)例也一樣）。

算法是異步的?

算法依賴于這樣一個(gè)假定，它在處理的時(shí)候不是（基于）同步時(shí)鐘的，每個(gè)處理中仍然使用的是本地的時(shí)間，它只是大致地以同樣地速率運(yùn)行，這樣它就會(huì)有一個(gè)小的錯(cuò)誤，與之相比會(huì)有一個(gè)小的自動(dòng)開(kāi)合的時(shí)鐘時(shí)間。這個(gè)假設(shè)很像真正世界的電腦：每一臺(tái)電腦有一個(gè)本地時(shí)鐘，通常我們使用不同的電腦會(huì)有一個(gè)很小的時(shí)鐘差。

基于這個(gè)觀點(diǎn)，我們需要更好地指明我們共同的互斥法則：這是保證客戶端能長(zhǎng)時(shí)間保持狀態(tài)鎖定，其將會(huì)終止它們?cè)谟行r(shí)間內(nèi)的工作（在步驟3中獲得），減去一些時(shí)間（在處理時(shí)時(shí)間差時(shí)減去了一些毫秒用來(lái)補(bǔ)償）。

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

失敗時(shí)重試

當(dāng)客戶端無(wú)法獲取鎖時(shí)，它應(yīng)該在一個(gè)隨機(jī)延遲后重試，從而避免多個(gè)客戶端同時(shí)試圖獲取鎖，相對(duì)應(yīng)同一的同時(shí)請(qǐng)求（這可能會(huì)導(dǎo)致崩潰，沒(méi)人會(huì)勝出）。同樣的，客戶端在大多數(shù)場(chǎng)合下嘗試獲取鎖的速度越快，崩潰的窗口就越少（重試的需要也越少），所以實(shí)際情況下客戶端應(yīng)嘗試采用復(fù)用方式發(fā)送SET命令到多個(gè)實(shí)例。

強(qiáng)調(diào)客戶在獲取主鎖失敗是值得的，釋放（或部分）以盡快獲得鎖，這樣沒(méi)有必要為獲取鎖鎖而去等待鍵到期（但是如果網(wǎng)絡(luò)分區(qū)發(fā)生變化時(shí)客戶端不能與Redis通信的情況下，需要顯性提示和等待超時(shí)）。

釋放鎖

釋放鎖是簡(jiǎn)單的，只需要釋放所有實(shí)例的鎖即可，盡管客戶端認(rèn)為有能力成功鎖住一個(gè)給出的實(shí)例。

安全參數(shù)

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

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

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

如果一個(gè)客戶端鎖定大部分實(shí)例的時(shí)間超過(guò)了鎖的最大有效時(shí)間（TTL基本設(shè)定） ，它將考慮鎖無(wú)效了，并解鎖。所以我們僅考慮在有效時(shí)間內(nèi)大部分實(shí)例獲得鎖的情況。這種情況已經(jīng)在上文中討論過(guò)， 對(duì)于MIN_VALIDITY沒(méi)有客戶端會(huì)重新獲取鎖。所以只有當(dāng)鎖大多數(shù)實(shí)例的時(shí)間超過(guò)TTL時(shí)間時(shí)，多客戶端才能同時(shí)鎖住N/2+1個(gè)實(shí)例（在步驟2的“時(shí)間”即將結(jié)束時(shí)），讓鎖失效。

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

系統(tǒng)的存活性基于以下三個(gè)主要特性：

1.     鎖的自動(dòng)釋放（key會(huì)到期）: 最終所有的key將可以被重新鎖?。?/li>
2.     一般來(lái)說(shuō)，客戶端如果沒(méi)有成功獲得鎖，或者獲得了鎖并且完成了工作，都會(huì)及時(shí)釋放鎖，使得我們無(wú)需等待key自動(dòng)釋放以重新獲得。
3.     當(dāng)客戶端重新獲取鎖之前，它會(huì)等待一段時(shí)間，這段時(shí)間比獲取鎖本身要長(zhǎng)得多，這是為了盡量降低資源競(jìng)爭(zhēng)引起的腦裂條件的概率。

然而，在網(wǎng)絡(luò)割裂的情況下，我們得付出等同于"TTL"時(shí)間的可用性代價(jià)，如果網(wǎng)絡(luò)持續(xù)割裂，我們就得無(wú)限的付出這個(gè)代價(jià)。這發(fā)生于當(dāng)客戶端獲取了一個(gè)鎖，而在刪除鎖之前網(wǎng)絡(luò)斷開(kāi)了。

基本上，如果網(wǎng)絡(luò)無(wú)限期地持續(xù)割裂，那系統(tǒng)將無(wú)限期地不可用。

性能、故障恢復(fù)和文件同步

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

然而，如果我們旨在實(shí)現(xiàn)一種故障系統(tǒng)的恢復(fù)模式，這里有另一種與持久性相關(guān)的思路。

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

如果我們啟用AOF持久性，情況就會(huì)得到相當(dāng)?shù)母纳?。例如我們可以通過(guò)發(fā)送 SHUTDOWN升級(jí)一個(gè)服務(wù)器并且重啟它。因?yàn)镽edis的期限是通過(guò)語(yǔ)義設(shè)置的，所以服務(wù)器關(guān)閉的情況下虛擬時(shí)間仍然會(huì)流逝，我們所有的需求都得到了滿足。不管怎樣所有事務(wù)都會(huì)正常運(yùn)轉(zhuǎn)只要服務(wù)器完全關(guān)閉。如果電源中斷會(huì)怎樣？如果Redis進(jìn)行了相關(guān)配置，默認(rèn)情況下每秒文件都會(huì)同步寫(xiě)入磁盤(pán)，很有可能在重啟后我們的數(shù)據(jù)會(huì)丟失。理論上，如果我們想在任何一種實(shí)例重啟后保證鎖的安全性，我們需要確保在持久性配置中設(shè)置fsync=always。這將會(huì)在同等級(jí)別的CP系統(tǒng)上損失性能，傳統(tǒng)上這種方式用來(lái)更安全的分配鎖。

不管怎樣事情比我們初次瞥見(jiàn)他們看起來(lái)好些?；旧纤惴ǖ陌踩缘玫奖Ａ?，就算是當(dāng)一個(gè)實(shí)例在故障后重啟，它也將不再參與任何當(dāng)前活躍的鎖的分配。因此當(dāng)實(shí)例重啟時(shí)，當(dāng)前所有活動(dòng)鎖的設(shè)置將從鎖定的實(shí)例中獲取除它重新加入系統(tǒng)。

為了保證這一點(diǎn)，我們只需要做一個(gè)實(shí)例，在超過(guò)最大TTL后，崩潰，不可用，那么就需要時(shí)間去獲取所有存在著的鎖的鑰匙，當(dāng)實(shí)例崩潰時(shí)，其就會(huì)變得無(wú)效，會(huì)被自動(dòng)釋放。

使用延時(shí)重啟可以基本上實(shí)現(xiàn)安全，甚至不需要利用任何Redis的持久化特性，但是這存在著另外的副作用。舉例來(lái)說(shuō)，如果大量的實(shí)例崩潰，系統(tǒng)變得全局不可用，那么TTL（這里的全局意味著根本就沒(méi)有資源可用，在這個(gè)時(shí)間內(nèi)所有的資源都會(huì)被鎖定）。

讓算法更可靠: 擴(kuò)展鎖

如果客戶工作的執(zhí)行是由小步驟組成，那么它就可以在默認(rèn)時(shí)間里默認(rèn)使用更小的鎖，并擴(kuò)展了算法去實(shí)現(xiàn)的一個(gè)鎖的擴(kuò)展機(jī)制。當(dāng)鎖的有效性接近于一個(gè)低值，那么通常是客戶端在運(yùn)算中處于居中位置。當(dāng)鎖被取得時(shí)，可能擴(kuò)展的鎖通過(guò)發(fā)送一個(gè)Lua腳本到所有的實(shí)例，這個(gè)實(shí)例是擴(kuò)展TTL的鑰匙，如果鑰匙存在，那么它的值就是客戶端復(fù)制的隨機(jī)值。

客戶端應(yīng)該僅考慮鎖的重新取得，如果它可以被擴(kuò)展，鎖就會(huì)在有效時(shí)間內(nèi)進(jìn)入大量實(shí)例（基本的算法使用非常類似于獲取鎖的使用）。 

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