[[419431]]

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

TL; DR

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

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

多線(xiàn)程編程通常使用 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，即在訪(fǎng)問(wèn)數(shù)據(jù)前先獲取鎖信息，再根據(jù)信息決定是否可以訪(fǎng)問(wèn);相對(duì)的是 mandatory lock，未授權(quán)訪(fǎng)問(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>

1. 很多(業(yè)務(wù))系統(tǒng)很難改造成使用共識(shí)算法，鎖服務(wù)更易于保持已存在的程序結(jié)構(gòu)和通信模式;
2. 基于鎖的接口更為程序員所熟悉。雖然可能只是表面熟悉 :)，但肯定好過(guò)使用一個(gè)共識(shí)庫(kù);
3. 鎖服務(wù)能減少客戶(hù)端系統(tǒng)運(yùn)行的服務(wù)器數(shù)目。一個(gè)共識(shí)算法需要 quorum 做決策，即我們常說(shuō)的超過(guò)半數(shù)節(jié)點(diǎn)可用，每個(gè)客戶(hù)端都構(gòu)建成 quorum 需要大量的服務(wù)器，而一套分布式鎖服務(wù)可以安全地服務(wù)多個(gè)客戶(hù)端。

因此，相比于客戶(hù)端實(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è)客戶(hù)端持有鎖;
• 避免死鎖(Dead lock free)，如果某個(gè)客戶(hù)端獲得鎖之后花了太長(zhǎng)時(shí)間處理，或者客戶(hù)端發(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è)客戶(hù)端持有鎖，可能會(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);另一種是客戶(hù)端向多個(gè)獨(dú)立的鎖服務(wù)發(fā)起請(qǐng)求，其中某個(gè)鎖服務(wù)故障時(shí)仍然可以從其他鎖服務(wù)讀取到鎖信息(Redlock)，代價(jià)是一個(gè)客戶(hù)端要獲取多把鎖，并且要求每臺(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ù)制也許就能滿(mǎn)足;如果你的系統(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)需要客戶(hù)端不停反復(fù)請(qǐng)求鎖服務(wù)查看是否能夠獲取到鎖;
• 監(jiān)聽(tīng)類(lèi)主要包括基于 ZooKeeper 或 etcd 實(shí)現(xiàn)的分布式鎖，這類(lèi)實(shí)現(xiàn)客戶(hù)端只需監(jiān)聽(tīng)(watch) 某個(gè) key，當(dāng)鎖可用時(shí)鎖服務(wù)會(huì)通知客戶(hù)端，無(wú)需客戶(hù)端不停請(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è)線(xiàn)程定時(shí)釋放和清理過(guò)期的鎖。

可見(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ù)分別是：

1. 第一個(gè)為 key 作為鎖名;
2. 第二個(gè)為 value，一般傳入一個(gè)唯一 id，例如一個(gè)隨機(jī)數(shù)或者客戶(hù)端 mac 地址 + uuid;
3. 第三個(gè)為 NX，意思是 SET IF NOT EXIST，即只有 key 不存在時(shí)才進(jìn)行 set 操作;若 key 已經(jīng)存在(鎖已被占)，則不做任何操作;
4. 第四個(gè)為 PX，作用是給這個(gè) key 加一個(gè)過(guò)期時(shí)間，具體時(shí)間長(zhǎng)短由第五個(gè)參數(shù)決定;
5. 第五個(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 獲取鎖的大致步驟如下：

1. 依次對(duì)多個(gè) Redis 實(shí)例進(jìn)行加鎖(一般是3個(gè)或5個(gè))，加鎖命令使用單實(shí)例 Redis 的加鎖命令;
2. 為了避免在某個(gè)節(jié)點(diǎn)長(zhǎng)時(shí)間獲取不到鎖而阻塞，每次獲取鎖操作也有一個(gè)超時(shí)時(shí)間，遠(yuǎn)小于 TTL，超過(guò)超時(shí)時(shí)間則認(rèn)為失敗，繼續(xù)向下一個(gè)節(jié)點(diǎn)獲取鎖;
3. 計(jì)算整個(gè)獲取多把鎖的總消耗時(shí)間，只有在超過(guò)半數(shù)節(jié)點(diǎn)都成功獲取鎖，并且總消耗時(shí)間小于 TTL，則認(rèn)為成功持有鎖;
4. 成功獲取鎖后，要重新計(jì)算 TTL = TTL - 總消耗時(shí)間;
5. 如果獲取鎖失敗，要向所有 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)：

1. Redis 命令避免了死鎖但可能會(huì)不滿(mǎn)足互斥性，因?yàn)闆](méi)有自增 id 或 fencing token 來(lái)阻斷同時(shí)獲得鎖的兩個(gè)客戶(hù)端;
2. Redlock 基于時(shí)間戳的合理性值得懷疑，多臺(tái)服務(wù)器難以保證時(shí)間一致;

第一點(diǎn)如下圖所示，Client 1 獲取鎖后發(fā)生了 STW GC(或缺頁(yè)等問(wèn)題)，TTL 過(guò)期后 Client 2 獲取了鎖，此時(shí)兩個(gè)客戶(hù)端持有鎖，違反了互斥性。后續(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 這樣的字段，但是由客戶(hù)端指定的字段 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ù)?。

通過(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í)算法，我們不再讓客戶(hù)端依次上多個(gè)鎖，而是讓鎖服務(wù)器通過(guò)共識(shí)算法復(fù)制到多數(shù)派節(jié)點(diǎn)，然后再回復(fù)客戶(hù)端。由于共識(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)附加到客戶(hù)端設(shè)置的 znode 路徑之后。例如 locknode/guid-lock- 會(huì)返回 locknode/guid-lock-0000000001;
• ephemeral：臨時(shí)節(jié)點(diǎn)，當(dāng)客戶(hù)端和 ZooKeeper 連接斷開(kāi)時(shí)，臨時(shí)節(jié)點(diǎn)會(huì)被刪除，能夠避免死鎖。但這個(gè)斷開(kāi)檢測(cè)依然有一定心跳延遲，所以仍然需要自增 id 來(lái)避免互斥性被破壞。

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

1. 首先調(diào)用 create()，鎖路徑例如 locknode/guid-lock-，并設(shè)置 sequence 和 ephemeral 標(biāo)志。guid 是客戶(hù)端的唯一標(biāo)識(shí)，如果 create() 創(chuàng)建失敗可以通過(guò) guid 來(lái)進(jìn)行檢查，下面會(huì)提到;
2. 調(diào)用 getChildren() 獲取子節(jié)點(diǎn)列表，不要設(shè)置 watch 標(biāo)志(很重要，可以避免 Herd Effect，即驚群效應(yīng));
3. 檢查 2 中的子節(jié)點(diǎn)列表，如果步驟 1 中創(chuàng)建成功并且返回的序列號(hào)后綴是最小的，則客戶(hù)端持有該分布式鎖，到此結(jié)束;
4. 如果發(fā)現(xiàn)序列不是最小的，則從子節(jié)點(diǎn)列表中選擇比當(dāng)前序列號(hào)小一位的節(jié)點(diǎn)記為 p，客戶(hù)端調(diào)用 exist(p, watch=true)，即監(jiān)聽(tīng) p，當(dāng) p 被刪除時(shí)收到通知(該節(jié)點(diǎn)只有比自己小一位的節(jié)點(diǎn)釋放時(shí)才能獲得鎖);
5. 如果 exist() 返回 null，即前一個(gè)分布式鎖被釋放了，轉(zhuǎn)到步驟 2;否則需要一直等待步驟 4 中 watch 的通知。

如上圖所示，每個(gè)客戶(hù)端只監(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)單：客戶(hù)端直接刪除他們?cè)诓襟E 1 創(chuàng)建的 znode 節(jié)點(diǎn)。

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

• 刪除一個(gè) znode 只會(huì)導(dǎo)致一個(gè)客戶(hù)端被喚醒，因?yàn)槊總€(gè)節(jié)點(diǎn)正好被一個(gè)客戶(hù)端 watch 著，通過(guò)這種方式，可以避免驚群效應(yīng);
• 沒(méi)有輪詢(xún)或超時(shí);
• 如果在調(diào)用 create() 時(shí) ZooKeeper 創(chuàng)建鎖成功但沒(méi)有返回給客戶(hù)端就失敗了，客戶(hù)端收到錯(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ù)期，如果客戶(hù)端還未處理完可以繼續(xù)續(xù)約;同時(shí) etcd 也有自增 id，在下文介紹。

為了幫助開(kāi)發(fā)者快速實(shí)現(xiàn)分布式鎖，etcd 給出了 clientv3 包，其中分布式鎖在 concurrency 包中。按照官方文檔給出的案例1，首先創(chuàng)建一個(gè)新的會(huì)話(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 一樣，客戶(hù)端會(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 的客戶(hù)端庫(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)還是略有不同。

[[419432]]

為了容錯(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：客戶(hù)端會(huì)話(huà)，包括租約時(shí)間;
• KeepAlive：在租約快要過(guò)期時(shí)可以發(fā)送 KeepAlive 續(xù)約;
• Cache：鎖服務(wù)支持大量的客戶(hù)端，為了減少讀請(qǐng)求支持客戶(hù)端無(wú)感知的緩存;

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

選擇新的 epoch，可以理解為 Raft 中的任期，小于 epoch 的客戶(hù)端請(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 拒絕，但客戶(hù)端也因此獲得了最新的 epoch;步驟 6 中第二個(gè) KeepAlive 成功，由于上一步延長(zhǎng)的租約夠長(zhǎng)，步驟 7 的響應(yīng)會(huì)延長(zhǎng)客戶(hù)端本地的租約時(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"，當(dāng)然我的新書(shū)里也有對(duì)該論文的剖析，下半年會(huì)跟大家見(jiàn)面。

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

Reference

1. Lamport, Leslie. "Time, clocks, and the ordering of events in a distributed system." Concurrency: the Works of Leslie Lamport. 2019. 179-196.

2. How to do distributed locking, https://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html

3. Is Redlock safe?, http://antirez.com/news/101

4. Distributed Locks are Dead; Long Live Distributed Locks! https://hazelcast.com/blog/long-live-distributed-locks/

5. TIL: clock skew exists,http://jvns.ca/blog/2016/02/09/til-clock-skew-exists/

6. A Survey of the NTP Network, http://alumni.media.mit.edu/~nelson/research/ntp-survey99/

7. The trouble with timestamps, https://aphyr.com/posts/299-the-trouble-with-timestamps

8. Corbett, James C., et al. "Spanner: Google’s globally distributed database." ACM Transactions on Computer Systems (TOCS) 31.3 (2013): 1-22.

9. Hunt, Patrick, et al. "ZooKeeper: Wait-free Coordination for Internet-scale Systems." USENIX annual technical conference. Vol. 8. No. 9. 2010.

10. ZooKeeper 實(shí)現(xiàn)分布式鎖官方文檔, https://zookeeper.apache.org/doc/r3.7.0/recipes.html#sc_recipes_Locks

11. etcd 實(shí)現(xiàn)分布式鎖官方案例，https://github.com/etcd-io/etcd/blob/main/tests/integration/clientv3/concurrency/mutex_test.go

12. Burrows, Mike. "The Chubby lock service for loosely-coupled distributed systems." Proceedings of the 7th symposium on Operating systems design and implementation. 2006.