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

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

實(shí)現(xiàn)

在說具體算法之前，下面有一些具體的實(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)).

安全和活躍性保證

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Redlock 算法

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

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

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

算法是異步的?

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

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

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

失敗時重試

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

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

釋放鎖

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

安全參數(shù)

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

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

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

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

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

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

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

然而，在網(wǎng)絡(luò)割裂的情況下，我們得付出等同于"TTL"時間的可用性代價，如果網(wǎng)絡(luò)持續(xù)割裂，我們就得無限的付出這個代價。這發(fā)生于當(dāng)客戶端獲取了一個鎖，而在刪除鎖之前網(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實(shí)例的往返時間是相似的）。

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

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

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

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

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

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

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

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

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

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