譯自Redis官方文檔

在多線程共享臨界資源的場景下，分布式鎖是一種非常重要的組件。
許多庫使用不同的方式使用redis實現(xiàn)一個分布式鎖管理。
其中有一部分簡單的實現(xiàn)方式可靠性不足，可以通過一些簡單的修改提高其可靠性。
這篇文章介紹了一種指導(dǎo)性的redis分布式鎖算法RedLock，RedLock比起單實例的實現(xiàn)方式更加安全。

在介紹RedLock算法之前，我們列出了一些已經(jīng)實現(xiàn)了分布式鎖的類庫供大家參考。

Redlock-rb (Ruby 實現(xiàn)).
Redlock-py (Python 實現(xiàn))
Redlock-php (PHP 實現(xiàn))
PHPRedisMutex (further PHP 實現(xiàn))??
Redsync.go (Go 實現(xiàn))
Redisson (Java 實現(xiàn))
Redis::DistLock (Perl 實現(xiàn))
Redlock-cpp (C++ 實現(xiàn))
Redlock-cs (C#/.NET 實現(xiàn))
RedLock.net (C#/.NET 實現(xiàn)
ScarletLock (C# .NET 實現(xiàn))
node-redlock (NodeJS 實現(xiàn))

分布式鎖應(yīng)該具有的特性(Safety & Liveness)

我們將從三個特性的角度出發(fā)來設(shè)計RedLock模型：

1. 安全性(Safety):在任意時刻，只有一個客戶端可以獲得鎖(排他性)。
2. 避免死鎖：客戶端最終一定可以獲得鎖，即使鎖住某個資源的客戶端在釋放鎖之前崩潰或者網(wǎng)絡(luò)不可達(dá)。
3. 容錯性：只要Redsi集群中的大部分節(jié)點存活，client就可以進(jìn)行加鎖解鎖操作。

故障切換(failover)實現(xiàn)方式的局限性

通過Redis為某個資源加鎖的最簡單方式就是在一個Redis實例中使用過期特性(expire)創(chuàng)建一個key, 如果獲得鎖的客戶端沒有釋放鎖，那么在一定時間內(nèi)這個Key將會自動刪除，避免死鎖。
這種做法在表面上看起來可行，但分布式鎖作為架構(gòu)中的一個組件,為了避免Redis宕機(jī)引起鎖服務(wù)不可用, 我們需要為Redis實例(master)增加熱備(slave)，如果master不可用則將slave提升為master。
這種主從的配置方式存在一定的安全風(fēng)險，由于Redis的主從復(fù)制是異步進(jìn)行的， 可能會發(fā)生多個客戶端同時持有一個鎖的現(xiàn)象。

此類場景是非常典型的競態(tài)模型：

1. Client A 獲得在master節(jié)點獲得了鎖
2. 在master將key備份到slave節(jié)點之前，master宕機(jī)
3. slave 被提升為master
4. Client B 在新的master節(jié)點處獲得了鎖，Client A也持有這個鎖。

如何正確實現(xiàn)單實例的鎖

在單redis實例中實現(xiàn)鎖是分布式鎖的基礎(chǔ)，在解決前文提到的單實例的不足之前，我們先了解如何在單點中正確的實現(xiàn)鎖。
如果你的應(yīng)用可以容忍偶爾發(fā)生競態(tài)問題，那么單實例鎖就足夠了。

我們通過以下命令對資源加鎖
SET resource_name my_random_value NX PX 30000
SET NX 命令只會在Key不存在的時給key賦值，PX 命令通知redis保存這個key 30000ms。
my_random_value必須是全局唯一的值。這個隨機(jī)數(shù)在釋放鎖時保證釋放鎖操作的安全性。

通過下面的腳本為申請成功的鎖解鎖:
if redis.call("get",KEYS[1]) == ARGV[1] then return redis.call("del",KEYS[1]) else return 0 end

如果key對應(yīng)的Value一致，則刪除這個key。

通過這個方式釋放鎖是為了避免client釋放了其他client申請的鎖。
例如:

1. Client A 獲得了一個鎖，
2. 當(dāng)嘗試釋放鎖的請求發(fā)送給Redis時被阻塞，沒有及時到達(dá)Redis。
3. 鎖定時間超時，Redis認(rèn)為鎖的租約到期，釋放了這個鎖。
4. client B 重新申請到了這個鎖
5. client A的解鎖請求到達(dá),將Client B鎖定的key解鎖
6. Client C 也獲得了鎖
7. Client B client C 同時持有鎖。

通過執(zhí)行上面腳本的方式釋放鎖，Client的解鎖操作只會解鎖自己曾經(jīng)加鎖的資源。
官方推薦通從 /dev/urandom/中取20個byte作為隨機(jī)數(shù)或者采用更加簡單的方式， 例如使用RC4加密算法在/dev/urandom中得到一個種子(Seed)，然后生成一個偽隨機(jī)流。
也可以用更簡單的使用時間戳+客戶端編號的方式生成隨機(jī)數(shù)，
這種方式的安全性較差一些，但是對于絕大多數(shù)的場景來說也已經(jīng)足夠安全了。

PX 操作后面的參數(shù)代表的是這key的存活時間，稱作鎖過期時間。

1. 當(dāng)資源被鎖定超過這個時間，鎖將自動釋放。
2. 獲得鎖的客戶端如果沒有在這個時間窗口內(nèi)完成操作,就可能會有其他客戶端獲得鎖，引起爭用問題。

通過上面的兩個操作，我們可以完成獲得鎖和釋放鎖操作。如果這個系統(tǒng)不宕機(jī)，那么單點的鎖服務(wù)已經(jīng)足夠安全,接下來我們開始把場景擴(kuò)展到分布式系統(tǒng)。

RedLock算法介紹

下面例子中的分布式環(huán)境包含N個Redis Master節(jié)點，這些節(jié)點相互獨立，無需備份。這些節(jié)點盡可能相互隔離的部署在不同的物理機(jī)或虛擬機(jī)上(故障隔離)。
節(jié)點數(shù)量暫定為5個(在需要投票的集群中,5個節(jié)點的配置是比較合理的最小配置方式)。獲得鎖和釋放鎖的方式仍然采用之前介紹的方法。

一個Client想要獲得一個鎖需要以下幾個操作：

1. 得到本地時間
2. Client使用相同的key和隨機(jī)數(shù),按照順序在每個Master實例中嘗試獲得鎖。在獲得鎖的過程中，為每一個鎖操作設(shè)置一個快速失敗時間(如果想要獲得一個10秒的鎖， 那么每一個鎖操作的失敗時間設(shè)為5-50ms)。
   這樣可以避免客戶端與一個已經(jīng)故障的Master通信占用太長時間，通過快速失敗的方式盡快的與集群中的其他節(jié)點完成鎖操作。
3. 客戶端計算出與master獲得鎖操作過程中消耗的時間，當(dāng)且僅當(dāng)Client獲得鎖消耗的時間小于鎖的存活時間，并且在一半以上的master節(jié)點中獲得鎖。才認(rèn)為client成功的獲得了鎖。
4. 如果已經(jīng)獲得了鎖，Client執(zhí)行任務(wù)的時間窗口是鎖的存活時間減去獲得鎖消耗的時間。
5. 如果Client獲得鎖的數(shù)量不足一半以上，或獲得鎖的時間超時，那么認(rèn)為獲得鎖失敗?？蛻舳诵枰獓L試在所有的master節(jié)點中釋放鎖， 即使在第二步中沒有成功獲得該Master節(jié)點中的鎖，仍要進(jìn)行釋放操作。

RedLock能保證鎖同步嗎？

這個算法成立的一個條件是：即使集群中沒有同步時鐘，各個進(jìn)程的時間流逝速度也要大體一致，并且誤差與鎖存活時間相比是比較小的。實際應(yīng)用中的計算機(jī)也能滿足這個條件：各個計算機(jī)中間有幾毫秒的時鐘漂移(clock drift)。

失敗重試機(jī)制

如果一個Client無法獲得鎖，它將在一個隨機(jī)延時后開始重試。使用隨機(jī)延時的目的是為了與其他申請同一個鎖的Client錯開申請時間，減少腦裂(split brain)發(fā)生的可能性。

三個Client同時嘗試獲得鎖，分別獲得了2,2,1個實例中的鎖，三個鎖請求全部失敗。

一個client在全部Redis實例中完成的申請時間越短，發(fā)生腦裂的時間窗口越小。所以比較理想的做法是同時向N個Redis實例發(fā)出異步的SET請求。
當(dāng)Client沒有在大多數(shù)Master中獲得鎖時，立即釋放已經(jīng)取得的鎖時非常必要的。(PS.當(dāng)極端情況發(fā)生時，比如獲得了部分鎖以后，client發(fā)生網(wǎng)絡(luò)故障，無法再釋放鎖資源。
那么其他client重新獲得鎖的時間將是鎖的過期時間)。
無論Client認(rèn)為在指定的Master中有沒有獲得鎖，都需要執(zhí)行釋放鎖操作。

RedLock算法安全性分析

我們將從不同的場景分析RedLock算法是否足夠安全。首先我們假設(shè)一個client在大多數(shù)的Redis實例中取得了鎖,
那么:

1. 每個實例中的鎖的剩余存活時間相等為TTL。
2. 每個鎖請求到達(dá)各個Redis實例中的時間有差異。
3. 第一個鎖成功請求最先在T1后返回，最后返回的請求在T2后返回。(T1,T2都小于最大失敗時間)
4. 并且每個實例之間存在時鐘漂移CLOCK_DRIFT(Time Drift)。

于是，最先被SET的鎖將在TTL-(T2-T1)-CLOCK_DIRFT后自動過期，其他的鎖將在之后陸續(xù)過期。
所以可以得到結(jié)論：所有的key這段時間內(nèi)是同時被鎖住的。
在這段時間內(nèi)，一半以上的Redis實例中這個key都處在被鎖定狀態(tài)，其他的客戶端無法獲得這個鎖。

鎖的可用性分析(Liveness)

分布式鎖系統(tǒng)的可用性主要依靠以下三種機(jī)制

1. 鎖的自動釋放(key expire)，最終鎖將被釋放并且被再次申請。
2. 客戶端在未申請到鎖以及申請到鎖并完成任務(wù)后都將進(jìn)行釋放鎖的操作，所以大部分情況下都不需要等待到鎖的自動釋放期限，其他client即可重新申請到鎖。
3. 假設(shè)一個Client在大多數(shù)Redis實例中申請鎖請求所成功花費的時間為Tac。那么如果某個Client第一次沒有申請到鎖，需要重試之前，必須等待一段時間T。T需要遠(yuǎn)大于Tac。 因為多個Client同時請求鎖資源，他們有可能都無法獲得一半以上的鎖，導(dǎo)致腦裂雙方均失敗。設(shè)置較久的重試時間是為了減少腦裂產(chǎn)生的概率。

如果一直持續(xù)的發(fā)生網(wǎng)絡(luò)故障，那么沒有客戶端可以申請到鎖。分布式鎖系統(tǒng)也將無法提供服務(wù)直到網(wǎng)絡(luò)故障恢復(fù)為止。

性能，故障恢復(fù)與文件同步

用戶使用redis作為鎖服務(wù)的主要優(yōu)勢是性能。其性能的指標(biāo)有兩個

1. 加鎖和解鎖的延遲
2. 每秒可以進(jìn)行多少加鎖和解鎖操作

所以，在客戶端與N個Redis節(jié)點通信時，必須使用多路發(fā)送的方式(multiplex)，減少通信延時。

為了實現(xiàn)故障恢復(fù)還需要考慮數(shù)據(jù)持久化的問題。

我們還是從某個特定的場景分析：
<code>
Redis實例的配置不進(jìn)行任何持久化,集群中5個實例 M1,M2,M3,M4,M5
client A獲得了M1,M2,M3實例的鎖。
此時M1宕機(jī)并重啟。
由于沒有進(jìn)行持久化，M1重啟后不存在任何KEY
client B獲得M4,M5和重啟后的M1中的鎖。
此時client A 和Client B 同時獲得鎖
</code>

如果使用AOF的方式進(jìn)行持久化，情況會稍好一些。例如我們可以向某個實例發(fā)送shutdown和restart命令。即使節(jié)點被關(guān)閉，EX設(shè)置的時間仍在計算，鎖的排他性仍能保證。

但當(dāng)Redis發(fā)生電源瞬斷的情況又會遇到有新的問題出現(xiàn)。如果Redis配置中的進(jìn)行磁盤持久化的時間是每分鐘進(jìn)行，那么會有部分key在重新啟動后丟失。
如果為了避免key的丟失，將持久化的設(shè)置改為Always,那么性能將大幅度下降。

另一種解決方案是在這臺實例重新啟動后，令其在一定時間內(nèi)不參與任何加鎖。在間隔了一整個鎖生命周期后，重新參與到鎖服務(wù)中。這樣可以保證所有在這臺實例宕機(jī)期間內(nèi)的key都已經(jīng)過期或被釋放。

延時重啟機(jī)制能夠保證Redis即使不使用任何持久化策略，仍能保證鎖的可靠性。但是這種策略可能會犧牲掉一部分可用性。
例如集群中超過半數(shù)的實例都宕機(jī)了，那么整個分布式鎖系統(tǒng)需要等待一整個鎖有效期的時間才能重新提供鎖服務(wù)。

使鎖算法更加可靠：鎖續(xù)約

如果Client進(jìn)行的工作耗時較短，那么可以默認(rèn)使用一個較小的鎖有效期，然后實現(xiàn)一個鎖續(xù)約機(jī)制。

當(dāng)一個Client在工作計算到一半時發(fā)現(xiàn)鎖的剩余有效期不足。可以向Redis實例發(fā)送續(xù)約鎖的Lua腳本。如果Client在一定的期限內(nèi)(耗間與申請鎖的耗時接近)成功的續(xù)約了半數(shù)以上的實例，那么續(xù)約鎖成功。

為了提高系統(tǒng)的可用性，每個Client申請鎖續(xù)約的次數(shù)需要有一個最大限制，避免其不斷續(xù)約造成該key長時間不可用。