“分布式鎖”這個(gè)問(wèn)題快被說(shuō)爛了，奈何筆者實(shí)在沒(méi)有找到一個(gè)滿意的答案，故記錄自己尋找答案、總結(jié)的過(guò)程。分布式鎖的設(shè)計(jì)涉及了許多分布式系統(tǒng)相關(guān)的問(wèn)題，許多地方值得推敲，非常有意思。

太長(zhǎng)不看？沒(méi)關(guān)系，我已經(jīng)做好了思維導(dǎo)圖，點(diǎn)個(gè)分享再收藏，支持一下，也方便以后查閱。

分布式鎖三個(gè)屬性和兩大類(lèi)

多線程編程通常使用 mutex 或信號(hào)量等方式進(jìn)行同步；在同一個(gè)操作系統(tǒng)下的多進(jìn)程也能通過(guò)共享內(nèi)存等方式同步；但在分布式系統(tǒng)多進(jìn)程之間的資源爭(zhēng)搶?zhuān)缦聠螕屬?gòu)，就需要額外的分布式鎖。

分布式鎖大多都是 Advisory lock，即在訪問(wèn)數(shù)據(jù)前先獲取鎖信息，再根據(jù)信息決定是否可以訪問(wèn)；相對(duì)的是 mandatory lock，未授權(quán)訪問(wèn)鎖定的數(shù)據(jù)時(shí)會(huì)產(chǎn)生異常。

分布式鎖屬于分布式互斥問(wèn)題（distributed mutual exclusion），實(shí)際上 Lamport 在那篇經(jīng)典論文 “Time， clocks， and the ordering of events in a distributed system” 中早就證明了使用狀態(tài)機(jī)能夠去中心化解決多進(jìn)程互斥問(wèn)題，而共識(shí)算法就能實(shí)現(xiàn)這樣的狀態(tài)機(jī)。但大多時(shí)候我們還是會(huì)使用一個(gè)分布式鎖而不是構(gòu)建一個(gè)共識(shí)庫(kù)，主要因?yàn)椋?/p>

很多（業(yè)務(wù)）系統(tǒng)很難改造成使用共識(shí)算法，鎖服務(wù)更易于保持已存在的程序結(jié)構(gòu)和通信模式；

基于鎖的接口更為程序員所熟悉。雖然可能只是表面熟悉 ：），但肯定好過(guò)使用一個(gè)共識(shí)庫(kù)；

鎖服務(wù)能減少客戶端系統(tǒng)運(yùn)行的服務(wù)器數(shù)目。一個(gè)共識(shí)算法需要 quorum 做決策，即我們常說(shuō)的超過(guò)半數(shù)節(jié)點(diǎn)可用，每個(gè)客戶端都構(gòu)建成 quorum 需要大量的服務(wù)器，而一套分布式鎖服務(wù)可以安全地服務(wù)多個(gè)客戶端。

因此，相比于客戶端實(shí)現(xiàn)一個(gè)共識(shí)庫(kù)，使用分布式鎖服務(wù)耦合更松、更易用、也更節(jié)省資源。

提起分布式鎖，大家可能馬上會(huì)想到各種實(shí)現(xiàn)方式，以及一場(chǎng)關(guān)于基于 Redis 實(shí)現(xiàn)的分布式鎖是否安全的論戰(zhàn)，這些文章可能很多地方都能搜到。但在開(kāi)始討論這些東西之前，我們首先要思考，一個(gè)分布式鎖到底需要具備哪些性質(zhì)？

總的來(lái)說(shuō)，分布式鎖服務(wù)有三個(gè)必備的性質(zhì)：

互斥（Mutual Exclusion），這是鎖最基本的功能，同一時(shí)刻只能有一個(gè)客戶端持有鎖；

避免死鎖（Dead lock free），如果某個(gè)客戶端獲得鎖之后花了太長(zhǎng)時(shí)間處理，或者客戶端發(fā)生了故障，鎖無(wú)法釋放會(huì)導(dǎo)致整個(gè)處理流程無(wú)法進(jìn)行下去，所以要避免死鎖。最常見(jiàn)的是通過(guò)設(shè)置一個(gè) TTL（Time To Live，存活時(shí)間） 來(lái)避免死鎖。假設(shè)設(shè)置 TTL 為 3 秒，如果 3 秒過(guò)后鎖還沒(méi)有被釋放，系統(tǒng)也會(huì)自動(dòng)釋放該鎖（TTL 的設(shè)置要非常小心！這個(gè)時(shí)長(zhǎng)取決于你的業(yè)務(wù)邏輯）。可是這也存在一個(gè)問(wèn)題，假如進(jìn)程1獲取了鎖，然后由于某些原因（下面會(huì)說(shuō)到）沒(méi)有來(lái)得及更新 TTL；3秒后進(jìn)程2來(lái)獲取鎖，由于 TTL 已過(guò)，進(jìn)程2可以獲得鎖并開(kāi)始處理，此時(shí)同時(shí)有兩個(gè)客戶端持有鎖，可能會(huì)產(chǎn)生意外行為。所以我們不能只有 TTL，還需要給鎖附加一個(gè)唯一 ID （或 fencing token）來(lái)標(biāo)識(shí)鎖。上述邏輯中，當(dāng)進(jìn)程 1 獲取到鎖后記為 LOCK_1；TTL 過(guò)后進(jìn)程 2 獲取到的鎖記為 LOCK_2。之后，我們可以在應(yīng)用層面或鎖服務(wù)層面檢查該 id，來(lái)阻斷舊的請(qǐng)求。

容錯(cuò)（Fault tolerance），為避免單點(diǎn)故障，鎖服務(wù)需要具有一定容錯(cuò)性。大體有兩種容錯(cuò)方式，一種是鎖服務(wù)本身是一個(gè)集群，能夠自動(dòng)故障切換（ZooKeeper、etcd）；另一種是客戶端向多個(gè)獨(dú)立的鎖服務(wù)發(fā)起請(qǐng)求，其中某個(gè)鎖服務(wù)故障時(shí)仍然可以從其他鎖服務(wù)讀取到鎖信息（Redlock），代價(jià)是一個(gè)客戶端要獲取多把鎖，并且要求每臺(tái)機(jī)器的時(shí)鐘都是一樣的，否則 TTL 會(huì)不一致，可能有的機(jī)器會(huì)提前釋放鎖，有的機(jī)器會(huì)太晚釋放鎖，導(dǎo)致出現(xiàn)問(wèn)題。

值得注意的是，容錯(cuò)會(huì)以性能為代價(jià)，容錯(cuò)性取決于你的系統(tǒng)級(jí)別，如果你的系統(tǒng)可以承擔(dān)分布式鎖存在誤差，那么單節(jié)點(diǎn)或者簡(jiǎn)單的主從復(fù)制也許就能滿足；如果你的系統(tǒng)非常嚴(yán)格，例如金融系統(tǒng)或航天系統(tǒng)，那么就要考慮每個(gè) corner case——本文更傾向于討論后者。

我們會(huì)拿著這三個(gè)屬性逐一分析各種分布式鎖的實(shí)現(xiàn)。在此之前，先把分布式鎖分為兩大類(lèi)：自旋類(lèi)和監(jiān)聽(tīng)類(lèi)。

自旋類(lèi)包括基于數(shù)據(jù)庫(kù)的實(shí)現(xiàn)和基于 Redis 的實(shí)現(xiàn)，這類(lèi)實(shí)現(xiàn)需要客戶端不停反復(fù)請(qǐng)求鎖服務(wù)查看是否能夠獲取到鎖；

監(jiān)聽(tīng)類(lèi)主要包括基于 ZooKeeper 或 etcd 實(shí)現(xiàn)的分布式鎖，這類(lèi)實(shí)現(xiàn)客戶端只需監(jiān)聽(tīng)（watch） 某個(gè) key，當(dāng)鎖可用時(shí)鎖服務(wù)會(huì)通知客戶端，無(wú)需客戶端不停請(qǐng)求鎖服務(wù)。

因此，本文默認(rèn)讀者大概了解 Redis、ZooKeeper 和 etcd 是什么。

如此，我們?cè)陬^腦中已經(jīng)有了一個(gè)很好的框架，現(xiàn)在開(kāi)始往思維導(dǎo)圖中填充知識(shí)。

基于數(shù)據(jù)庫(kù)的實(shí)現(xiàn)

最簡(jiǎn)單的，我們想到通過(guò)某個(gè)獨(dú)立的數(shù)據(jù)庫(kù)（或文件），當(dāng)獲取到數(shù)據(jù)時(shí)，往數(shù)據(jù)庫(kù)中插入一條數(shù)據(jù)。之后的進(jìn)程想要獲取數(shù)據(jù)，會(huì)先檢查數(shù)據(jù)庫(kù)是否存在記錄，就能夠知道是否有別的進(jìn)程持有鎖，這便實(shí)現(xiàn)了分布式鎖的互斥性。

數(shù)據(jù)庫(kù)可以通過(guò)主從同步復(fù)制來(lái)實(shí)現(xiàn)容錯(cuò)，雖然主從復(fù)制切換時(shí)不會(huì)非常輕松，可能需要管理員參與。

為了避免死鎖，我們需要增加時(shí)間戳字段和自增 id 字段，同時(shí)在后臺(tái)啟動(dòng)一個(gè)線程定時(shí)釋放和清理過(guò)期的鎖。

字段作用

id自增 id，唯一標(biāo)識(shí)鎖

key鎖名稱(chēng)

value自定義字段

ttl存活時(shí)間，定時(shí)清理，避免死鎖

可見(jiàn)基于數(shù)據(jù)庫(kù)的實(shí)現(xiàn)較為繁瑣，要自己維護(hù)鎖的 TTL；除非使用分布式數(shù)據(jù)庫(kù)，否則主從復(fù)制的故障切換并不輕松。

除了麻煩之外，如果經(jīng)常用數(shù)據(jù)庫(kù)你也知道，在高并發(fā)常見(jiàn)下數(shù)據(jù)庫(kù)讀寫(xiě)是非常緩慢的，會(huì)導(dǎo)致我們的系統(tǒng)性能存在瓶頸。如果采用多個(gè)獨(dú)立數(shù)據(jù)庫(kù)進(jìn)行容錯(cuò)，那性能就更差了。

于是，為了分布式鎖的性能，開(kāi)始轉(zhuǎn)向基于 Redis 或者 memcache 等內(nèi)存存儲(chǔ)系統(tǒng)來(lái)實(shí)現(xiàn)分布式鎖。

基于 Redis 的實(shí)現(xiàn)

分布式鎖最多的恐怕就是基于 Redis 的實(shí)現(xiàn)。首先我們從單節(jié)點(diǎn) Redis 開(kāi)始。

基于單節(jié)點(diǎn) Redis 的分布式鎖

總的來(lái)說(shuō)就是一條命令實(shí)現(xiàn)寫(xiě) key + 設(shè)置過(guò)期時(shí)間，否則原子性無(wú)法保證可能出現(xiàn)死鎖。于是就有了以下命令：

set key value nx px 10000

set 命令后的 5 個(gè)參數(shù)分別是：

第一個(gè)為 key 作為鎖名；

第二個(gè)為 value，一般傳入一個(gè)唯一 id，例如一個(gè)隨機(jī)數(shù)或者客戶端 mac 地址 + uuid；

第三個(gè)為 NX，意思是 SET IF NOT EXIST，即只有 key 不存在時(shí)才進(jìn)行 set 操作；若 key 已經(jīng)存在（鎖已被占），則不做任何操作；

第四個(gè)為 PX，作用是給這個(gè) key 加一個(gè)過(guò)期時(shí)間，具體時(shí)間長(zhǎng)短由第五個(gè)參數(shù)決定；

第五個(gè)為具體的過(guò)期時(shí)間，對(duì)應(yīng)第四個(gè)參數(shù) PX 是毫秒，EX 是秒；

這個(gè)方案在互斥性和避免死鎖上性能良好，且非常輕量。但單節(jié)點(diǎn)的 Redis 存在單點(diǎn)故障。注意，Redis 主從復(fù)制是異步的，所以加入從節(jié)點(diǎn)會(huì)增加破壞互斥性的風(fēng)險(xiǎn)。為了實(shí)現(xiàn)容錯(cuò)性，就有了基于多節(jié)點(diǎn) Redis 的分布式鎖，即 Redlock。

基于多節(jié)點(diǎn) Redis 的分布式鎖

Redlock 用到多個(gè)獨(dú)立的 Redis 節(jié)點(diǎn)，其思想簡(jiǎn)而言之，是在多個(gè) Redis 實(shí)際都獲取鎖，其中一個(gè)宕機(jī)了，只要還有超過(guò)半數(shù)節(jié)點(diǎn)可用，就可以繼續(xù)提供鎖服務(wù)。

如圖所示，Redlock 獲取鎖的大致步驟如下，：

依次對(duì)多個(gè) Redis 實(shí)例進(jìn)行加鎖（一般是3個(gè)或5個(gè)），加鎖命令使用單實(shí)例 Redis 的加鎖命令；

為了避免在某個(gè)節(jié)點(diǎn)長(zhǎng)時(shí)間獲取不到鎖而阻塞，每次獲取鎖操作也有一個(gè)超時(shí)時(shí)間，遠(yuǎn)小于 TTL，超過(guò)超時(shí)時(shí)間則認(rèn)為失敗，繼續(xù)向下一個(gè)節(jié)點(diǎn)獲取鎖；

計(jì)算整個(gè)獲取多把鎖的總消耗時(shí)間，只有在超過(guò)半數(shù)節(jié)點(diǎn)都成功獲取鎖，并且總消耗時(shí)間小于 TTL，則認(rèn)為成功持有鎖；

成功獲取鎖后，要重新計(jì)算 TTL = TTL - 總消耗時(shí)間；

如果獲取鎖失敗，要向所有 redis 實(shí)例發(fā)送釋放鎖的命令。

釋放鎖操作就是向所有實(shí)例都發(fā)送刪除 key 命令。

Redlock 容錯(cuò)性依賴(lài)于一個(gè)時(shí)間戳的計(jì)算，這在分布式系統(tǒng)中并不受待見(jiàn)，于是有了一場(chǎng)著名的論戰(zhàn)。

Redlock 論戰(zhàn)

DDIA 的作者 Martin Kleppmann 大佬發(fā)表了著名的文章《How to do distributed locking》，表示 Redlock 并不可靠，該文章主要闡述了兩個(gè)觀點(diǎn)：

Redis 命令避免了死鎖但可能會(huì)不滿足互斥性，因?yàn)闆](méi)有自增 id 或 fencing token 來(lái)阻斷同時(shí)獲得鎖的兩個(gè)客戶端；

Redlock 基于時(shí)間戳的合理性值得懷疑，多臺(tái)服務(wù)器難以保證時(shí)間一致；

第一點(diǎn)如下圖所示，Client 1 獲取鎖后發(fā)生了 STW GC（或缺頁(yè)等問(wèn)題），TTL 過(guò)期后 Client 2 獲取了鎖，此時(shí)兩個(gè)客戶端持有鎖，違反了互斥性。后續(xù)寫(xiě)操作自然就可能存在問(wèn)題。

我們?cè)诒苊馑梨i時(shí)提到，需要另外用單調(diào)遞增 id （Martin 稱(chēng)之為 fencing token，也叫序列號(hào)）來(lái)標(biāo)識(shí)每一個(gè)鎖。增加 id 后邏輯如下圖所示，最后的 Client 1 的寫(xiě)請(qǐng)求因?yàn)?token 是舊的，會(huì)被存儲(chǔ)系統(tǒng)拒絕。

第二點(diǎn) Martin 認(rèn)為，Redlock 的時(shí)間戳計(jì)算方式不可靠，每臺(tái)服務(wù)器的走時(shí)并不絕對(duì)準(zhǔn)確，例如 NTP 進(jìn)行同步時(shí)系統(tǒng)會(huì)發(fā)生時(shí)鐘漂移，即當(dāng)前服務(wù)器的時(shí)間戳突然變大或變小，這都會(huì)影響 Redlock 的計(jì)算。

Martin 的這篇文章引起了大家對(duì)分布式鎖廣泛討論。Redis 作者 antirez 也不甘示弱，發(fā)表文章《Is Redlock safe？》進(jìn)行反駁，回應(yīng)了上述兩個(gè)問(wèn)題，我總結(jié)了 antirez 的論點(diǎn)：

針對(duì)第一點(diǎn)，雖然 Redlock 提供不了自增 id 這樣的字段，但是由客戶端指定的字段 value 也可以實(shí)現(xiàn)唯一標(biāo)識(shí)，并通過(guò) read-modify-write 原子操作來(lái)進(jìn)行檢查；

時(shí)鐘發(fā)送漂移肯定會(huì)影響 Redlock 安全性，可是通過(guò)恰當(dāng)?shù)倪\(yùn)維，例如不要隨意人為修改時(shí)鐘、將一次大的 NTP 時(shí)鐘調(diào)整轉(zhuǎn)換成多次微小的調(diào)整等方式，使時(shí)鐘修改不超過(guò)某個(gè)范圍就不會(huì)對(duì) Redlock 產(chǎn)生影響。

非常推薦閱讀爭(zhēng)論的兩篇文章，但篇幅所限我只提取了觀點(diǎn)。關(guān)于爭(zhēng)論的詳細(xì)內(nèi)容張鐵蕾老師的文章《基于Redis的分布式鎖到底安全嗎（下）？》也有著比較完整的中文回顧。

對(duì)于這兩個(gè)問(wèn)題，我想談?wù)勎业睦斫狻?/p>

對(duì)于第一個(gè)問(wèn)題，文章開(kāi)頭“三大屬性”我們就分析過(guò)，增加 TTL 來(lái)避免死鎖就會(huì)對(duì)互斥性產(chǎn)生影響，無(wú)論基于 Redis 還是基于 Zookeeper 實(shí)現(xiàn)都會(huì)存在該問(wèn)題。antirez 觀點(diǎn)是 Redlock 也可以用 value 作為唯一標(biāo)識(shí)來(lái)阻斷操作，這確實(shí)沒(méi)問(wèn)題，我也挑不出毛病。但我們可以思考下，實(shí)際編程中讀者您覺(jué)得使用一個(gè)自增 id 進(jìn)行判斷容易還是使用 read-modify-write 操作更容易呢？（實(shí)際上，一開(kāi)始我都不怎么理解什么是 read-modify-write 操作）

我認(rèn)為 fencing token 是一個(gè)更好的解決方案，一個(gè)單調(diào)自增的 id 更符合我們的直覺(jué)，同時(shí)也更好進(jìn)行 debug。

作為 fencing token 的一個(gè)實(shí)際參考，Hazelcast 的文章 “Distributed Locks are Dead; Long Live Distributed Locks！” 給出了一個(gè) FencedLock 解決方案，并且通過(guò)了 Jepsen 測(cè)試。

第二個(gè)問(wèn)題，時(shí)鐘漂移是否應(yīng)該引起注意呢？antirez 的觀點(diǎn)是時(shí)鐘確實(shí)會(huì)影響 Redlock，但可以通過(guò)合理運(yùn)維避免。

Julia Evans（也是很出名的技術(shù)博主）也寫(xiě)了一篇后續(xù)文章 “TIL： clock skew exists”，來(lái)討論時(shí)鐘漂移的問(wèn)題是否真的值得引起注意。最終得出的結(jié)論是：有界的時(shí)鐘漂移不是一個(gè)安全的假設(shè)。

事實(shí)上，時(shí)鐘問(wèn)題并不罕見(jiàn)，例如：

Nelson Minar 在1999年發(fā)表了論文，通過(guò)調(diào)查發(fā)現(xiàn)，NTP 服務(wù)器經(jīng)常提供不正確的時(shí)間；

aphyr 的文章《The trouble with timestamps》也總結(jié)了時(shí)間戳在分布式系統(tǒng)中的麻煩；

Google 在 Spanner 中投入大量精力來(lái)處理時(shí)間問(wèn)題，并發(fā)明了 TrueTime 這一授時(shí)系統(tǒng)；

閏秒也會(huì)導(dǎo)致時(shí)鐘漂移，不過(guò)閏秒確實(shí)非常罕見(jiàn)（即使是現(xiàn)在，閏秒依然會(huì)導(dǎo)致許多問(wèn)題，以后我們會(huì)專(zhuān)門(mén)談?wù)劊?/p>

通過(guò)上述例子，時(shí)鐘問(wèn)題是真實(shí)存在的，如果你的系統(tǒng)對(duì)分布式鎖的安全性要求嚴(yán)格，不想造成任何系統(tǒng)和金錢(qián)上的損失，那么你應(yīng)該考慮所有的邊緣情況。

Martin Kleppmann 沒(méi)有回復(fù)任何 Hacker News 的評(píng)論，他覺(jué)得自己想要表達(dá)的都已經(jīng)說(shuō)完了，他不想?yún)⑴c爭(zhēng)論，他認(rèn)為實(shí)際上一個(gè)分布式系統(tǒng)到底該怎么做取決于你如何管理你的系統(tǒng)。

本文想表達(dá)的也是這樣的觀點(diǎn)，軟件工程沒(méi)有銀彈，這些 trade-off 取決于你系統(tǒng)的重要級(jí)別，你怎么管理你的分布式系統(tǒng)。

只不過(guò)分布式系統(tǒng)研究人員通常會(huì)非常關(guān)注那些看似非常不可能在你的電腦上發(fā)生的事情（例如：時(shí)鐘偏移），原因是：

需要找出某個(gè)算法來(lái)解決此類(lèi)問(wèn)題，因此需要考慮所有 corner case；

分布式系統(tǒng)中會(huì)有成千上萬(wàn)的機(jī)器，那么不大可能發(fā)生的事情會(huì)變得極有可能；

其中一些問(wèn)題其實(shí)是很常見(jiàn)的（例如：網(wǎng)絡(luò)分區(qū)）。

基于 ZooKeeper 實(shí)現(xiàn)

除了 Redlock，還有哪些既能容錯(cuò)又能避免死鎖的方式呢？

容錯(cuò)性當(dāng)然離不開(kāi)我們的老朋友共識(shí)算法，我們不再讓客戶端依次上多個(gè)鎖，而是讓鎖服務(wù)器通過(guò)共識(shí)算法復(fù)制到多數(shù)派節(jié)點(diǎn)，然后再回復(fù)客戶端。由于共識(shí)算法本身不依賴(lài)系統(tǒng)時(shí)間戳而是邏輯時(shí)鐘（Raft 的任期或 Paxos 的 epoch），故不存在時(shí)鐘漂移問(wèn)題。

其次，死鎖避免問(wèn)題依然需要 TTL 和自增 id 等手段，我們通過(guò)鎖服務(wù)給每次加鎖請(qǐng)求標(biāo)識(shí)上單調(diào)遞增 id。

通過(guò)以上兩種方法，我們可以得到一個(gè)更可靠的分布式鎖。代價(jià)是，我們需要一個(gè)實(shí)現(xiàn)共識(shí)算法的第三方組件。下文主要介紹三個(gè)此類(lèi)實(shí)現(xiàn)：ZooKeeper、etcd 和 Chubby。

ZooKeeper 是一個(gè)分布式協(xié)調(diào)服務(wù)，參見(jiàn)：《ZooKeeper 設(shè)計(jì)原理》。

基于 ZooKeeper 實(shí)現(xiàn)的分布式鎖依賴(lài)以下兩個(gè)節(jié)點(diǎn)屬性：

sequence：順序節(jié)點(diǎn)，ZooKeeper 會(huì)將一個(gè)10位帶有0填充的序列號(hào)附加到客戶端設(shè)置的 znode 路徑之后。例如 locknode/guid-lock- 會(huì)返回 locknode/guid-lock-0000000001；

ephemeral：臨時(shí)節(jié)點(diǎn)，當(dāng)客戶端和 ZooKeeper 連接斷開(kāi)時(shí)，臨時(shí)節(jié)點(diǎn)會(huì)被刪除，能夠避免死鎖。但這個(gè)斷開(kāi)檢測(cè)依然有一定心跳延遲，所以仍然需要自增 id 來(lái)避免互斥性被破壞。

ZooKeeper 官方文檔有提供現(xiàn)成的分布式鎖實(shí)現(xiàn)方法：

首先調(diào)用 create（），鎖路徑例如 locknode/guid-lock-，并設(shè)置 sequence 和 ephemeral 標(biāo)志。guid 是客戶端的唯一標(biāo)識(shí)，如果 create（） 創(chuàng)建失敗可以通過(guò) guid 來(lái)進(jìn)行檢查，下面會(huì)提到；

調(diào)用 getChildren（） 獲取子節(jié)點(diǎn)列表，不要設(shè)置 watch 標(biāo)志（很重要，可以避免 Herd Effect，即驚群效應(yīng)）；

檢查 2 中的子節(jié)點(diǎn)列表，如果步驟 1 中創(chuàng)建成功并且返回的序列號(hào)后綴是最小的，則客戶端持有該分布式鎖，到此結(jié)束；

如果發(fā)現(xiàn)序列不是最小的，則從子節(jié)點(diǎn)列表中選擇比當(dāng)前序列號(hào)小一位的節(jié)點(diǎn)記為 p，客戶端調(diào)用 exist（p， watch=true），即監(jiān)聽(tīng) p，當(dāng) p 被刪除時(shí)收到通知（該節(jié)點(diǎn)只有比自己小一位的節(jié)點(diǎn)釋放時(shí)才能獲得鎖）；

如果 exist（） 返回 null，即前一個(gè)分布式鎖被釋放了，轉(zhuǎn)到步驟 2；否則需要一直等待步驟 4 中 watch 的通知。

每個(gè)客戶端只監(jiān)聽(tīng)比自己小的 znode，可以避免驚群效應(yīng)。

獲取鎖的偽代碼如下：

n = create（l + “/guid-lock-”， EPHEMERAL|SEQUENTIAL）

C = getChildren（l， false）

if n is lowest znode in C， exit

p = znode in C ordered just before n

goto 2

釋放鎖非常簡(jiǎn)單：客戶端直接刪除他們?cè)诓襟E 1 創(chuàng)建的 znode 節(jié)點(diǎn)。

有幾點(diǎn)需要注意：

刪除一個(gè) znode 只會(huì)導(dǎo)致一個(gè)客戶端被喚醒，因?yàn)槊總€(gè)節(jié)點(diǎn)正好被一個(gè)客戶端 watch 著，通過(guò)這種方式，可以避免驚群效應(yīng)；

沒(méi)有輪詢或超時(shí)；

如果在調(diào)用 create（） 時(shí) ZooKeeper 創(chuàng)建鎖成功但沒(méi)有返回給客戶端就失敗了，客戶端收到錯(cuò)誤響應(yīng)后，應(yīng)該先調(diào)用 getChildren（） 并檢查該路徑是否包含 guid 來(lái)避免這一問(wèn)題。

當(dāng)然，雖然 ZooKeeper 的實(shí)現(xiàn)看起來(lái)更為可靠，但根據(jù)你實(shí)現(xiàn)鎖的方式，可能還是會(huì)有大量的鎖邏輯調(diào)試、鎖爭(zhēng)搶等問(wèn)題。

基于 ZooKeeper 的分布式鎖性能介于基于 Mysql 和基于 Redis 的實(shí)現(xiàn)之間，性能上當(dāng)然不如單節(jié)點(diǎn) Redis。

ZooKeeper 的另一個(gè)缺點(diǎn)是需要另外維護(hù)一套 ZooKeeper 服務(wù)（已有則忽略）。

etcd

Etcd 是著名的分布式 key-value 存儲(chǔ)結(jié)構(gòu)，因在 Kubernetes 中使用而聞名。etcd 同樣可以用來(lái)實(shí)現(xiàn)分布式鎖，官方也很貼心的提供了 clientv3 包給開(kāi)發(fā)者快速實(shí)現(xiàn)分布式鎖。

我們來(lái)看下 etcd 是如何解決分布式鎖“三大問(wèn)題”的：

互斥：etcd 支持事務(wù)，通過(guò)事務(wù)創(chuàng)建 key 和檢查 key 是否存在，可以保證互斥性；

容錯(cuò)：etcd 基于 Raft 共識(shí)算法，寫(xiě) key 成功至少需要超過(guò)半數(shù)節(jié)點(diǎn)確認(rèn)，這就保證了容錯(cuò)性；

死鎖：etcd 支持租約（Lease）機(jī)制，可以對(duì) key 設(shè)置租約存活時(shí)間（TTL），到期后該 key 將失效刪除，避免死鎖；etc 也支持租約續(xù)期，如果客戶端還未處理完可以繼續(xù)續(xù)約；同時(shí) etcd 也有自增 id，在下文介紹。

為了幫助開(kāi)發(fā)者快速實(shí)現(xiàn)分布式鎖，etcd 給出了 clientv3 包，其中分布式鎖在 concurrency 包中。按照官方文檔給出的案例1，首先創(chuàng)建一個(gè)新的會(huì)話（session）并指定租約的 TTL，然后實(shí)例化一個(gè) NewMutex（） 之后就可以調(diào)用 Lock（） 和 Unlock（） 進(jìn)行搶鎖和釋放鎖。代碼如下：

cli， err ：= clientv3.New（clientv3.Config{Endpoints： endpoints}）

if err ！= nil {

log.Fatal（err）

}

defer cli.Close（）

s， err ：= concurrency.NewSession（cli， concurrency.WithTTL（10））

if err ！= nil {

log.Fatal（err）

}

defer s.Close（）

m ：= concurrency.NewMutex（s， “/my-lock/”）

if err ：= m.Lock（context.TODO（））; err ！= nil {

log.Fatal（err）

}

fmt.Println（“acquired lock for s”）

if err ：= m.Unlock（context.TODO（））; err ！= nil {

log.Fatal（err）

}

fmt.Println（“released lock for s”）

其中 Lock（） 函數(shù)的源代碼很容易找到，由于篇幅我就不放出來(lái)了，但源代碼中可以看到的一些其他機(jī)制包括：

Revision 機(jī)制。一個(gè)全局序列號(hào)，跟 ZooKeeper 的序列號(hào)類(lèi)似，可以用來(lái)避免 watch 驚群；

Prefix 機(jī)制。即上述代碼中 etcd 會(huì)創(chuàng)建一個(gè)前綴為 /my-lock/ 的 key（/my-lock/ + LeaseID），分布式鎖由該前綴下 revision 最小（最早創(chuàng)建）的 key 獲得；

Watch 機(jī)制。跟 ZooKeeper 一樣，客戶端會(huì)監(jiān)聽(tīng) revision 比自己小的 key，當(dāng)比自己小的 key 釋放鎖后，嘗試去獲得鎖。

本質(zhì)上 etcd 和 ZooKeeper 對(duì)分布式鎖的實(shí)現(xiàn)是類(lèi)似的。

選擇 etcd 的原因可能有：

生產(chǎn)環(huán)境中已經(jīng)大規(guī)模部署了 etcd 集群；

etcd 在保證強(qiáng)一致性的同時(shí)真的夠快，性能介于 Redis 和 ZooKeeper 之間；

許多語(yǔ)言都有 etcd 的客戶端庫(kù)，很容易使用；

Chubby

最后簡(jiǎn)要談一下 Chubby。由于 Chubby 沒(méi)有開(kāi)源，沒(méi)法直接使用，細(xì)節(jié)也難以得知，很少會(huì)有造一個(gè) Chubby 的需求（雖然我老東家真的用 C++ 造了一個(gè)）。因此，Chubby 部分只是 Paper 讀后感，不感興趣的讀者可以跳過(guò)。

Chubby 是 Google 研發(fā)的松耦合分布式鎖服務(wù)，此外 GFS 和 BigTable 使用 Chubby 來(lái)存儲(chǔ)一些元數(shù)據(jù)。Chubby 有以下幾大特點(diǎn)：

粗粒度（Coarse-grained）。相對(duì)于細(xì)粒度（Fine-grained），粗粒度鎖會(huì)持續(xù)幾小時(shí)或幾天；

可用性、可靠性；

可以存儲(chǔ)一些元數(shù)據(jù)；

大量廉價(jià)機(jī)器部署；

Chubby 依賴(lài)于 Paxos 共識(shí)算法來(lái)實(shí)現(xiàn)容錯(cuò)，數(shù)據(jù)以 UNIX 文件系統(tǒng)方式進(jìn)行組織（稱(chēng)為 Node），同樣有 Ephemeral 類(lèi)型的臨時(shí)節(jié)點(diǎn)，斷開(kāi)連接后會(huì)被刪除；支持監(jiān)聽(tīng)某個(gè) Node——總而言之，我們可以從 ZooKeeper 上看到許多 Chubby 的影子，ZooKeeper 和 Chubby 解決的問(wèn)題是比較類(lèi)似的，因此很多人認(rèn)為 ZooKeeper 是 Chubby 的開(kāi)源實(shí)現(xiàn)，不過(guò)兩者的具體架構(gòu)還是略有不同。

為了容錯(cuò)，一個(gè) Chubby 集群包含 5 個(gè)節(jié)點(diǎn)，組成一個(gè) Chubby cell。這 5 個(gè)節(jié)點(diǎn)只有一個(gè)是 master 其余都是 replicas，只有 Master 能夠處理請(qǐng)求和讀寫(xiě)文件，其它副本節(jié)點(diǎn)通過(guò) Paxos 算法復(fù)制 Master 的行為來(lái)容錯(cuò)。

Chubby 還支持：

Sequencer：鎖的序列號(hào)（更好的避免死鎖和 watch）；

Session：客戶端會(huì)話，包括租約時(shí)間；

KeepAlive：在租約快要過(guò)期時(shí)可以發(fā)送 KeepAlive 續(xù)約；

Cache：鎖服務(wù)支持大量的客戶端，為了減少讀請(qǐng)求支持客戶端無(wú)感知的緩存；

比較有意思的是 Chubby 的故障恢復(fù)。當(dāng) Master 發(fā)生故障，其內(nèi)存的 session 和鎖信息會(huì)丟失，session 中最重要的租約信息，Paxos 算法會(huì)選舉出新的 Master，然后：

選擇新的 epoch，可以理解為 Raft 中的任期，小于 epoch 的客戶端請(qǐng)求會(huì)被拒絕，保證了 Master 不會(huì)響應(yīng)舊 Master 的請(qǐng)求；

根據(jù)數(shù)據(jù)庫(kù)（持久化存儲(chǔ)）中的數(shù)據(jù)恢復(fù)出 session 和鎖相關(guān)信息，并將 session 租約延長(zhǎng)到一個(gè)可能的最大期限；

只接受 KeepAlive 請(qǐng)求；下圖步驟 4 中第一個(gè) KeepAlive 請(qǐng)求會(huì)由于epoch錯(cuò)誤而被 Maser 拒絕，但客戶端也因此獲得了最新的 epoch；步驟 6 中第二個(gè) KeepAlive 成功，由于上一步延長(zhǎng)的租約夠長(zhǎng)，步驟 7 的響應(yīng)會(huì)延長(zhǎng)客戶端本地的租約時(shí)間；接著恢復(fù)正常的通信。

從新請(qǐng)求中發(fā)現(xiàn)老 Master 創(chuàng)建的 Handle 時(shí)，新 Master 也需要重建，一段時(shí)間后（一般是一分鐘），刪除沒(méi)有 Handle 的臨時(shí)節(jié)點(diǎn)。

整個(gè)過(guò)程如圖所示。其中綠色都是安全時(shí)期，橙色部分是危險(xiǎn)時(shí)期，Chubby 集群切換到新的 Master。

Chubby 我不想太過(guò)深入，我想大家沒(méi)有再造一個(gè) Chubby 的動(dòng)力了。

結(jié)語(yǔ)

寫(xiě)這篇文章的時(shí)候內(nèi)心是忐忑的，為了 ego 和不被大家罵我盡量不犯錯(cuò)，但錯(cuò)誤實(shí)在難免，并且隨著時(shí)間推移可能兩三年后一些解決方案并不適用。這篇文章實(shí)在花了我許多時(shí)間和精力。

想要深入分布式鎖問(wèn)題的同學(xué)，我推薦好好看一遍 Lamport 的 “Time， clocks， and the ordering of events in a distributed system”。

最后，本文如有不妥之處，希望讀者能夠留言指出，我會(huì)積極改正。

責(zé)任編輯：haq