在不同進(jìn)程需要互斥地訪問共享資源時(shí)，分布式鎖是一種非常有用的技術(shù)手段。 有很多三方庫和文章描述如何用Redis實(shí)現(xiàn)一個(gè)分布式鎖管理器，但是這些庫實(shí)現(xiàn)的方式差別很大，而且很多簡單的實(shí)現(xiàn)其實(shí)只需采用稍微增加一點(diǎn)復(fù)雜的設(shè)計(jì)就可以獲得更好的可靠性。?這篇文章的目的就是嘗試提出一種官方權(quán)威的用Redis實(shí)現(xiàn)分布式鎖管理器的算法，我們把這個(gè)算法稱為RedLock。

實(shí)現(xiàn)

在描述具體的算法之前，下面是已經(jīng)實(shí)現(xiàn)了的項(xiàng)目可以作為參考：Redlock-rb(Ruby實(shí)現(xiàn))。還有一個(gè)Redlock-rb的分支，添加了一些特性使得實(shí)現(xiàn)分布式鎖更簡單

Redlock-py(Python 實(shí)現(xiàn)).

Redlock-php(PHP 實(shí)現(xiàn)).

PHPRedisMutex(PHP 更完整的實(shí)現(xiàn))

Redsync.go(Go 實(shí)現(xiàn)).

Redisson(Java 實(shí)現(xiàn)).

Redis::DistLock(Perl 實(shí)現(xiàn)).

Redlock-cpp(C++ 實(shí)現(xiàn)).

Redlock-cs(C#/.NET 實(shí)現(xiàn)).

node-redlock(NodeJS 實(shí)現(xiàn)). Includes support for lock extension.

安全和可靠性保證

在描述我們的設(shè)計(jì)之前，我們想先提出三個(gè)屬性，這三個(gè)屬性在我們看來，是實(shí)現(xiàn)高效分布式鎖的基礎(chǔ)。

一致性：互斥，不管任何時(shí)候，只有一個(gè)客戶端能持有同一個(gè)鎖。

分區(qū)可容忍性：不會(huì)死鎖，最終一定會(huì)得到鎖，就算一個(gè)持有鎖的客戶端宕掉或者發(fā)生網(wǎng)絡(luò)分區(qū)。

可用性：只要大多數(shù)Redis節(jié)點(diǎn)正常工作，客戶端應(yīng)該都能獲取和釋放鎖。

為什么基于故障切換的方案不夠好

為了理解我們想要提高的到底是什么，我們先看下當(dāng)前大多數(shù)基于Redis的分布式鎖三方庫的現(xiàn)狀。?用Redis來實(shí)現(xiàn)分布式鎖最簡單的方式就是在實(shí)例里創(chuàng)建一個(gè)鍵值，創(chuàng)建出來的鍵值一般都是有一個(gè)超時(shí)時(shí)間的（這個(gè)是Redis自帶的超時(shí)特性），所以每個(gè)鎖最終都會(huì)釋放（參見前文屬性2）。而當(dāng)一個(gè)客戶端想要釋放鎖時(shí)，它只需要?jiǎng)h除這個(gè)鍵值即可。 表面來看，這個(gè)方法似乎很管用，但是這里存在一個(gè)問題：在我們的系統(tǒng)架構(gòu)里存在一個(gè)單點(diǎn)故障，如果Redis的master節(jié)點(diǎn)宕機(jī)了怎么辦呢？有人可能會(huì)說：加一個(gè)slave節(jié)點(diǎn)！在master宕機(jī)時(shí)用slave就行了！但是其實(shí)這個(gè)方案明顯是不可行的，因?yàn)檫@種方案無法保證第1個(gè)安全互斥屬性，因?yàn)镽edis的復(fù)制是異步的。 總的來說，這個(gè)方案里有一個(gè)明顯的競爭條件（race condition），舉例來說：

客戶端A在master節(jié)點(diǎn)拿到了鎖。

master節(jié)點(diǎn)在把A創(chuàng)建的key寫入slave之前宕機(jī)了。

slave變成了master節(jié)點(diǎn)?

B也得到了和A還持有的相同的鎖（因?yàn)樵瓉淼膕lave里還沒有A持有鎖的信息）

當(dāng)然，在某些特殊場景下，前面提到的這個(gè)方案則完全沒有問題，比如在宕機(jī)期間，多個(gè)客戶端允許同時(shí)都持有鎖，如果你可以容忍這個(gè)問題的話，那用這個(gè)基于復(fù)制的方案就完全沒有問題，否則的話我們還是建議你采用這篇文章里接下來要描述的方案。

采用單實(shí)例的正確實(shí)現(xiàn)

在講述如何用其他方案突破單實(shí)例方案的限制之前，讓我們先看下是否有什么辦法可以修復(fù)這個(gè)簡單場景的問題，因?yàn)檫@個(gè)方案其實(shí)如果可以忍受競爭條件的話是有望可行的，而且單實(shí)例來實(shí)現(xiàn)分布式鎖是我們后面要講的算法的基礎(chǔ)。?要獲得鎖，要用下面這個(gè)命令： SET resource_name my_random_value NX PX 30000?這個(gè)命令的作用是在只有這個(gè)key不存在的時(shí)候才會(huì)設(shè)置這個(gè)key的值（NX選項(xiàng)的作用），超時(shí)時(shí)間設(shè)為30000毫秒（PX選項(xiàng)的作用）?這個(gè)key的值設(shè)為“my_random_value”。這個(gè)值必須在所有獲取鎖請求的客戶端里保持唯一。 基本上這個(gè)隨機(jī)值就是用來保證能安全地釋放鎖，我們可以用下面這個(gè)Lua腳本來告訴Redis：刪除這個(gè)key當(dāng)且僅當(dāng)這個(gè)key存在而且值是我期望的那個(gè)值。

ifredis.call("get",KEYS[1]) == ARGV[1] then

????????returnredis.call("del",KEYS[1])

????else

????????return0

????end

這個(gè)很重要，因?yàn)檫@可以避免誤刪其他客戶端得到的鎖，舉個(gè)例子，一個(gè)客戶端拿到了鎖，被某個(gè)操作阻塞了很長時(shí)間，過了超時(shí)時(shí)間后自動(dòng)釋放了這個(gè)鎖，然后這個(gè)客戶端之后又嘗試刪除這個(gè)其實(shí)已經(jīng)被其他客戶端拿到的鎖。所以單純的用DEL指令有可能造成一個(gè)客戶端刪除了其他客戶端的鎖，用上面這個(gè)腳本可以保證每個(gè)客戶單都用一個(gè)隨機(jī)字符串’簽名’了，這樣每個(gè)鎖就只能被獲得鎖的客戶端刪除了。

這個(gè)隨機(jī)字符串應(yīng)該用什么生成呢？我假設(shè)這是從/dev/urandom生成的20字節(jié)大小的字符串，但是其實(shí)你可以有效率更高的方案來保證這個(gè)字符串足夠唯一。比如你可以用RC4加密算法來從/dev/urandom生成一個(gè)偽隨機(jī)流。還有更簡單的方案，比如用毫秒的unix時(shí)間戳加上客戶端id，這個(gè)也許不夠安全，但是也許在大多數(shù)環(huán)境下已經(jīng)夠用了。

key值的超時(shí)時(shí)間，也叫做”鎖有效時(shí)間”。這個(gè)是鎖的自動(dòng)釋放時(shí)間，也是一個(gè)客戶端在其他客戶端能搶占鎖之前可以執(zhí)行任務(wù)的時(shí)間，這個(gè)時(shí)間從獲取鎖的時(shí)間點(diǎn)開始計(jì)算。 所以現(xiàn)在我們有很好的獲取和釋放鎖的方式，在一個(gè)非分布式的、單點(diǎn)的、保證永不宕機(jī)的環(huán)境下這個(gè)方式?jīng)]有任何問題，接下來我們看看無法保證這些條件的分布式環(huán)境下我們該怎么做。

Redlock算法

在分布式版本的算法里我們假設(shè)我們有N個(gè)Redis master節(jié)點(diǎn)，這些節(jié)點(diǎn)都是完全獨(dú)立的，我們不用任何復(fù)制或者其他隱含的分布式協(xié)調(diào)算法。我們已經(jīng)描述了如何在單節(jié)點(diǎn)環(huán)境下安全地獲取和釋放鎖。因此我們理所當(dāng)然地應(yīng)當(dāng)用這個(gè)方法在每個(gè)單節(jié)點(diǎn)里來獲取和釋放鎖。在我們的例子里面我們把N設(shè)成5，這個(gè)數(shù)字是一個(gè)相對比較合理的數(shù)值，因此我們需要在不同的計(jì)算機(jī)或者虛擬機(jī)上運(yùn)行5個(gè)master節(jié)點(diǎn)來保證他們大多數(shù)情況下都不會(huì)同時(shí)宕機(jī)。一個(gè)客戶端需要做如下操作來獲取鎖：

獲取當(dāng)前時(shí)間（單位是毫秒）。

輪流用相同的key和隨機(jī)值在N個(gè)節(jié)點(diǎn)上請求鎖，在這一步里，客戶端在每個(gè)master上請求鎖時(shí)，會(huì)有一個(gè)和總的鎖釋放時(shí)間相比小的多的超時(shí)時(shí)間。比如如果鎖自動(dòng)釋放時(shí)間是10秒鐘，那每個(gè)節(jié)點(diǎn)鎖請求的超時(shí)時(shí)間可能是5-50毫秒的范圍，這個(gè)可以防止一個(gè)客戶端在某個(gè)宕掉的master節(jié)點(diǎn)上阻塞過長時(shí)間，如果一個(gè)master節(jié)點(diǎn)不可用了，我們應(yīng)該盡快嘗試下一個(gè)master節(jié)點(diǎn)。

客戶端計(jì)算第二步中獲取鎖所花的時(shí)間，只有當(dāng)客戶端在大多數(shù)master節(jié)點(diǎn)上成功獲取了鎖（在這里是3個(gè)），而且總共消耗的時(shí)間不超過鎖釋放時(shí)間，這個(gè)鎖就認(rèn)為是獲取成功了。

如果鎖獲取成功了，那現(xiàn)在鎖自動(dòng)釋放時(shí)間就是最初的鎖釋放時(shí)間減去之前獲取鎖所消耗的時(shí)間。

如果鎖獲取失敗了，不管是因?yàn)楂@取成功的鎖不超過一半（N/2+1)還是因?yàn)榭傁臅r(shí)間超過了鎖釋放時(shí)間，客戶端都會(huì)到每個(gè)master節(jié)點(diǎn)上釋放鎖，即便是那些他認(rèn)為沒有獲取成功的鎖。

這個(gè)算法是否是異步的？

這個(gè)算法是基于一個(gè)假設(shè)：雖然不存在可以跨進(jìn)程的同步時(shí)鐘，但是不同進(jìn)程時(shí)間都是以差不多相同的速度前進(jìn)，這個(gè)假設(shè)不一定完全準(zhǔn)確，但是和自動(dòng)釋放鎖的時(shí)間長度相比不同進(jìn)程時(shí)間前進(jìn)速度差異基本是可以忽略不計(jì)的。這個(gè)假設(shè)就好比真實(shí)世界里的計(jì)算機(jī)：每個(gè)計(jì)算機(jī)都有本地時(shí)鐘，但是我們可以說大部分情況下不同計(jì)算機(jī)之間的時(shí)間差是很小的。 現(xiàn)在我們需要更細(xì)化我們的鎖互斥規(guī)則，只有當(dāng)客戶端能在T時(shí)間內(nèi)完成所做的工作才能保證鎖是有效的（詳見算法的第3步），T的計(jì)算規(guī)則是鎖失效時(shí)間T1減去一個(gè)用來補(bǔ)償不同進(jìn)程間時(shí)鐘差異的delta值（一般只有幾毫秒而已） 如果想了解更多基于有限時(shí)鐘差異的類似系統(tǒng)，可以參考這篇有趣的文章：《Leases: an efficient fault-tolerant mechanism for distributed file cache consistency.》

失敗的重試

當(dāng)一個(gè)客戶端獲取鎖失敗時(shí)，這個(gè)客戶端應(yīng)該在一個(gè)隨機(jī)延時(shí)后進(jìn)行重試，之所以采用隨機(jī)延時(shí)是為了避免不同客戶端同時(shí)重試導(dǎo)致誰都無法拿到鎖的情況出現(xiàn)。同樣的道理客戶端越快嘗試在大多數(shù)Redis節(jié)點(diǎn)獲取鎖，出現(xiàn)多個(gè)客戶端同時(shí)競爭鎖和重試的時(shí)間窗口越小，可能性就越低，所以最完美的情況下，客戶端應(yīng)該用多路傳輸?shù)姆绞酵瑫r(shí)向所有Redis節(jié)點(diǎn)發(fā)送SET命令。 這里非常有必要強(qiáng)調(diào)一下客戶端如果沒有在多數(shù)節(jié)點(diǎn)獲取到鎖，一定要盡快在獲取鎖成功的節(jié)點(diǎn)上釋放鎖，這樣就沒必要等到key超時(shí)后才能重新獲取這個(gè)鎖（但是如果網(wǎng)絡(luò)分區(qū)的情況發(fā)生而且客戶端無法連接到Redis節(jié)點(diǎn)時(shí)，會(huì)損失等待key超時(shí)這段時(shí)間的系統(tǒng)可用性）

釋放鎖

釋放鎖比較簡單，因?yàn)橹恍枰谒泄?jié)點(diǎn)都釋放鎖就行，不管之前有沒有在該節(jié)點(diǎn)獲取鎖成功。

安全性的論證

這個(gè)算法到底是不是安全的呢？我們可以觀察不同場景下的情況來理解這個(gè)算法為什么是安全的。 開始之前，讓我們假設(shè)客戶端可以在大多數(shù)節(jié)點(diǎn)都獲取到鎖，這樣所有的節(jié)點(diǎn)都會(huì)包含一個(gè)有相同存活時(shí)間的key。但是需要注意的是，這個(gè)key是在不同時(shí)間點(diǎn)設(shè)置的，所以這些key也會(huì)在不同的時(shí)間超時(shí)，但是我們假設(shè)最壞情況下第一個(gè)key是在T1時(shí)間設(shè)置的（客戶端連接到第一個(gè)服務(wù)器時(shí)的時(shí)間），最后一個(gè)key是在T2時(shí)間設(shè)置的（客戶端收到最后一個(gè)服務(wù)器返回結(jié)果的時(shí)間），從T2時(shí)間開始，我們可以確認(rèn)最早超時(shí)的key至少也會(huì)存在的時(shí)間為MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT，TTL是鎖超時(shí)時(shí)間、（T2-T1）是最晚獲取到的鎖的耗時(shí)，CLOCK_DRIFT是不同進(jìn)程間時(shí)鐘差異，這個(gè)是用來補(bǔ)償前面的(T2-T1）。其他的key都會(huì)在這個(gè)時(shí)間點(diǎn)之后才會(huì)超時(shí)，所以我們可以確定這些key在這個(gè)時(shí)間點(diǎn)之前至少都是同時(shí)存在的。

在大多數(shù)節(jié)點(diǎn)的key都set了的時(shí)間段內(nèi)，其他客戶端無法搶占這個(gè)鎖，因?yàn)樵贜/2+1個(gè)客戶端的key已經(jīng)存在的情況下不可能再在N/2+1個(gè)客戶端上獲取鎖成功，所以如果一個(gè)鎖獲取成功了，就不可能同時(shí)重新獲取這個(gè)鎖成功（不然就違反了分布式鎖互斥原則），然后我們也要確保多個(gè)客戶端同時(shí)嘗試獲取鎖時(shí)不會(huì)都同時(shí)成功。?如果一個(gè)客戶端獲取大多數(shù)節(jié)點(diǎn)鎖的耗時(shí)接近甚至超過鎖的最大有效時(shí)間時(shí)（就是我們?yōu)镾ET操作設(shè)置的TTL值），那么系統(tǒng)會(huì)認(rèn)為這個(gè)鎖是無效的同時(shí)會(huì)釋放這些節(jié)點(diǎn)上的鎖，所以我們僅僅需要考慮獲取大多數(shù)節(jié)點(diǎn)鎖的耗時(shí)小于有效時(shí)間的情況。在這種情況下，根據(jù)我們前面的證明，在MIN_VALIDITY時(shí)間內(nèi)，沒有客戶端能重新獲取鎖成功，所以多個(gè)客戶端都能同時(shí)成功獲取鎖的結(jié)果，只會(huì)發(fā)生在多數(shù)節(jié)點(diǎn)獲取鎖的時(shí)間都大大超過TTL時(shí)間的情況下，實(shí)際上這種情況下這些鎖都會(huì)失效 。

性能論證

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

鎖自動(dòng)釋放的特征（超時(shí)后會(huì)自動(dòng)釋放），一定時(shí)間后某個(gè)鎖都能被再次獲取。

客戶端通常會(huì)在不再需要鎖或者任務(wù)執(zhí)行完成之后主動(dòng)釋放鎖，這樣我們就不用等到超時(shí)時(shí)間會(huì)再去獲取這個(gè)鎖。

當(dāng)一個(gè)客戶端需要重試獲取鎖時(shí)，這個(gè)客戶端會(huì)等待一段時(shí)間，等待的時(shí)間相對來說會(huì)比我們重新獲取大多數(shù)鎖的時(shí)間要長一些，這樣可以降低不同客戶端競爭鎖資源時(shí)發(fā)生死鎖的概率。

然而，我們在網(wǎng)絡(luò)分區(qū)時(shí)要損失TTL的可用性時(shí)間，所以如果網(wǎng)絡(luò)分區(qū)持續(xù)發(fā)生，這個(gè)不可用會(huì)一直持續(xù)。這種情況在每次一個(gè)客戶端獲取到了鎖并在釋放鎖之前被網(wǎng)絡(luò)分區(qū)了時(shí)都會(huì)出現(xiàn)。

基本來說，如果持續(xù)的網(wǎng)絡(luò)分區(qū)發(fā)生的話，系統(tǒng)也會(huì)在持續(xù)不可用。

性能、故障恢復(fù)和fsync

很多使用Redis做鎖服務(wù)器的用戶在獲取鎖和釋放鎖時(shí)不止要求低延時(shí)，同時(shí)要求高吞吐量，也即單位時(shí)間內(nèi)可以獲取和釋放的鎖數(shù)量。為了達(dá)到這個(gè)要求，一定會(huì)使用多路傳輸來和N個(gè)服務(wù)器進(jìn)行通信以降低延時(shí)（或者也可以用假多路傳輸，也就是把socket設(shè)置成非阻塞模式，發(fā)送所有命令，然后再去讀取返回的命令，假設(shè)說客戶端和不同Redis服務(wù)節(jié)點(diǎn)的網(wǎng)絡(luò)往返延時(shí)相差不大的話）。

然后如果我們想讓系統(tǒng)可以自動(dòng)故障恢復(fù)的話，我們還需要考慮一下信息持久化的問題。

為了更好的描述問題，我們先假設(shè)我們Redis都是配置成非持久化的，某個(gè)客戶端拿到了總共5個(gè)節(jié)點(diǎn)中的3個(gè)鎖，這三個(gè)已經(jīng)獲取到鎖的節(jié)點(diǎn)中隨后重啟了，這樣一來我們又有3個(gè)節(jié)點(diǎn)可以獲取鎖了（重啟的那個(gè)加上另外兩個(gè)），這樣一來其他客戶端又可以獲得這個(gè)鎖了，這樣就違反了我們之前說的鎖互斥原則了。

如果我們啟用AOF持久化功能，情況會(huì)好很多。舉例來說，我們可以發(fā)送SHUTDOWN命令來升級(jí)一個(gè)Redis服務(wù)器然后重啟之，因?yàn)镽edis超時(shí)時(shí)效是語義層面實(shí)現(xiàn)的，所以在服務(wù)器關(guān)掉期間時(shí)超時(shí)時(shí)間還是算在內(nèi)的，我們所有要求還是滿足了的。然后這個(gè)是基于我們做的是一次正常的shutdown，但是如果是斷電這種意外停機(jī)呢？如果Redis是默認(rèn)地配置成每秒在磁盤上執(zhí)行一次fsync同步文件到磁盤操作，那就可能在一次重啟后我們鎖的key就丟失了。理論上如果我們想要在所有服務(wù)重啟的情況下都確保鎖的安全性，我們需要在持久化設(shè)置里設(shè)置成永遠(yuǎn)執(zhí)行fsync操作，但是這個(gè)反過來又會(huì)造成性能遠(yuǎn)不如其他同級(jí)別的傳統(tǒng)用來實(shí)現(xiàn)分布式鎖的系統(tǒng)。 然后問題其實(shí)并不像我們第一眼看起來那么糟糕，基本上只要一個(gè)服務(wù)節(jié)點(diǎn)在宕機(jī)重啟后不去參與現(xiàn)在所有仍在使用的鎖，這樣正在使用的鎖集合在這個(gè)服務(wù)節(jié)點(diǎn)重啟時(shí)，算法的安全性就可以維持，因?yàn)檫@樣就可以保證正在使用的鎖都被所有沒重啟的節(jié)點(diǎn)持有。 為了滿足這個(gè)條件，我們只要讓一個(gè)宕機(jī)重啟后的實(shí)例，至少在我們使用的最大TTL時(shí)間內(nèi)處于不可用狀態(tài)，超過這個(gè)時(shí)間之后，所有在這期間活躍的鎖都會(huì)自動(dòng)釋放掉。 使用延時(shí)重啟的策略基本上可以在不適用任何Redis持久化特性情況下保證安全性，然后要注意這個(gè)也必然會(huì)影響到系統(tǒng)的可用性。舉個(gè)例子，如果系統(tǒng)里大多數(shù)節(jié)點(diǎn)都宕機(jī)了，那在TTL時(shí)間內(nèi)整個(gè)系統(tǒng)都處于全局不可用狀態(tài)（全局不可用的意思就是在獲取不到任何鎖）。

擴(kuò)展鎖來使得算法更可靠

如果客戶端做的工作都是由一些小的步驟組成，那么就有可能使用更小的默認(rèn)鎖有效時(shí)間，而且擴(kuò)展這個(gè)算法來實(shí)現(xiàn)一個(gè)鎖擴(kuò)展機(jī)制?；旧希蛻舳巳绻趫?zhí)行計(jì)算期間發(fā)現(xiàn)鎖快要超時(shí)了，客戶端可以給所有服務(wù)實(shí)例發(fā)送一個(gè)Lua腳本讓服務(wù)端延長鎖的時(shí)間，只要這個(gè)鎖的key還存在而且值還等于客戶端獲取時(shí)的那個(gè)值。 客戶端應(yīng)當(dāng)只有在失效時(shí)間內(nèi)無法延長鎖時(shí)再去重新獲取鎖（基本上這個(gè)和獲取鎖的算法是差不多的） 然而這個(gè)并不會(huì)對從本質(zhì)上改變這個(gè)算法，所以最大的重新獲取鎖數(shù)量應(yīng)該被設(shè)置成合理的大小，不然性能必然會(huì)受到影響。

轉(zhuǎn)自：https://www.cnblogs.com/ironPhoenix/p/6048467.html