[[419431]]

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

TL; DR

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

分布式鎖三個屬性和兩大類

多線程編程通常使用 mutex 或信號量等方式進(jìn)行同步;在同一個操作系統(tǒng)下的多進(jìn)程也能通過共享內(nèi)存等方式同步;但在分布式系統(tǒng)多進(jìn)程之間的資源爭搶，例如下單搶購，就需要額外的分布式鎖。

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

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

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

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

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

總的來說，分布式鎖服務(wù)有三個必備的性質(zhì)：

• 互斥(Mutual Exclusion)，這是鎖最基本的功能，同一時刻只能有一個客戶端持有鎖;
• 避免死鎖(Dead lock free)，如果某個客戶端獲得鎖之后花了太長時間處理，或者客戶端發(fā)生了故障，鎖無法釋放會導(dǎo)致整個處理流程無法進(jìn)行下去，所以要避免死鎖。最常見的是通過設(shè)置一個 TTL(Time To Live，存活時間) 來避免死鎖。假設(shè)設(shè)置 TTL 為 3 秒，如果 3 秒過后鎖還沒有被釋放，系統(tǒng)也會自動釋放該鎖(TTL 的設(shè)置要非常小心!這個時長取決于你的業(yè)務(wù)邏輯)。可是這也存在一個問題，假如進(jìn)程1獲取了鎖，然后由于某些原因(下面會說到)沒有來得及更新 TTL;3秒后進(jìn)程2來獲取鎖，由于 TTL 已過，進(jìn)程2可以獲得鎖并開始處理，此時同時有兩個客戶端持有鎖，可能會產(chǎn)生意外行為。所以我們不能只有 TTL，還需要給鎖附加一個唯一 ID (或 fencing token)來標(biāo)識鎖。上述邏輯中，當(dāng)進(jìn)程 1 獲取到鎖后記為 LOCK_1;TTL 過后進(jìn)程 2 獲取到的鎖記為 LOCK_2。之后，我們可以在應(yīng)用層面或鎖服務(wù)層面檢查該 id，來阻斷舊的請求。
• 容錯(Fault tolerance)，為避免單點故障，鎖服務(wù)需要具有一定容錯性。大體有兩種容錯方式，一種是鎖服務(wù)本身是一個集群，能夠自動故障切換(ZooKeeper、etcd);另一種是客戶端向多個獨立的鎖服務(wù)發(fā)起請求，其中某個鎖服務(wù)故障時仍然可以從其他鎖服務(wù)讀取到鎖信息(Redlock)，代價是一個客戶端要獲取多把鎖，并且要求每臺機(jī)器的時鐘都是一樣的，否則 TTL 會不一致，可能有的機(jī)器會提前釋放鎖，有的機(jī)器會太晚釋放鎖，導(dǎo)致出現(xiàn)問題。

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

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

• 自旋類包括基于數(shù)據(jù)庫的實現(xiàn)和基于 Redis 的實現(xiàn)，這類實現(xiàn)需要客戶端不停反復(fù)請求鎖服務(wù)查看是否能夠獲取到鎖;
• 監(jiān)聽類主要包括基于 ZooKeeper 或 etcd 實現(xiàn)的分布式鎖，這類實現(xiàn)客戶端只需監(jiān)聽(watch) 某個 key，當(dāng)鎖可用時鎖服務(wù)會通知客戶端，無需客戶端不停請求鎖服務(wù)。

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

如此，我們在頭腦中已經(jīng)有了一個很好的框架，現(xiàn)在開始往思維導(dǎo)圖中填充知識。

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

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

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

為了避免死鎖，我們需要增加時間戳字段和自增 id 字段，同時在后臺啟動一個線程定時釋放和清理過期的鎖。

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

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

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

基于 Redis 的實現(xiàn)

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

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

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

set key value nx px 10000

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

1. 第一個為 key 作為鎖名;
2. 第二個為 value，一般傳入一個唯一 id，例如一個隨機(jī)數(shù)或者客戶端 mac 地址 + uuid;
3. 第三個為 NX，意思是 SET IF NOT EXIST，即只有 key 不存在時才進(jìn)行 set 操作;若 key 已經(jīng)存在(鎖已被占)，則不做任何操作;
4. 第四個為 PX，作用是給這個 key 加一個過期時間，具體時間長短由第五個參數(shù)決定;
5. 第五個為具體的過期時間，對應(yīng)第四個參數(shù) PX 是毫秒，EX 是秒;

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

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

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

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

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

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

Redlock 容錯性依賴于一個時間戳的計算，這在分布式系統(tǒng)中并不受待見，于是有了一場著名的論戰(zhàn)。

Redlock 論戰(zhàn)

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

1. Redis 命令避免了死鎖但可能會不滿足互斥性，因為沒有自增 id 或 fencing token 來阻斷同時獲得鎖的兩個客戶端;
2. Redlock 基于時間戳的合理性值得懷疑，多臺服務(wù)器難以保證時間一致;

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

我們在避免死鎖時提到，需要另外用單調(diào)遞增 id (Martin 稱之為 fencing token，也叫序列號)來標(biāo)識每一個鎖。增加 id 后邏輯如下圖所示，最后的 Client 1 的寫請求因為 token 是舊的，會被存儲系統(tǒng)拒絕。

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

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

• 針對第一點，雖然 Redlock 提供不了自增 id 這樣的字段，但是由客戶端指定的字段 value 也可以實現(xiàn)唯一標(biāo)識，并通過 read-modify-write 原子操作來進(jìn)行檢查;
• 時鐘發(fā)送漂移肯定會影響 Redlock 安全性，可是通過恰當(dāng)?shù)倪\維，例如不要隨意人為修改時鐘、將一次大的 NTP 時鐘調(diào)整轉(zhuǎn)換成多次微小的調(diào)整等方式，使時鐘修改不超過某個范圍就不會對 Redlock 產(chǎn)生影響。

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

對于這兩個問題，我想談?wù)勎业睦斫狻?/p>

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

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

作為 fencing token 的一個實際參考，Hazelcast 的文章 "Distributed Locks are Dead; Long Live Distributed Locks!" 給出了一個 FencedLock 解決方案，并且通過了 Jepsen 測試。

第二個問題，時鐘漂移是否應(yīng)該引起注意呢?antirez 的觀點是時鐘確實會影響 Redlock，但可以通過合理運維避免。

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

事實上，時鐘問題并不罕見，例如：

• Nelson Minar 在1999年發(fā)表了論文，通過調(diào)查發(fā)現(xiàn)，NTP 服務(wù)器經(jīng)常提供不正確的時間;
• aphyr 的文章《The trouble with timestamps》也總結(jié)了時間戳在分布式系統(tǒng)中的麻煩;
• Google 在 Spanner 中投入大量精力來處理時間問題，并發(fā)明了 TrueTime 這一授時系統(tǒng);

閏秒也會導(dǎo)致時鐘漂移，不過閏秒確實非常罕見(即使是現(xiàn)在，閏秒依然會導(dǎo)致許多問題，以后我們會專門談?wù)?。

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

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

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

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

需要找出某個算法來解決此類問題，因此需要考慮所有 corner case;

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

其中一些問題其實是很常見的(例如：網(wǎng)絡(luò)分區(qū))。

基于 ZooKeeper 實現(xiàn)

除了 Redlock，還有哪些既能容錯又能避免死鎖的方式呢?

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

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

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

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

基于 ZooKeeper 實現(xiàn)的分布式鎖依賴以下兩個節(jié)點屬性：

• sequence：順序節(jié)點，ZooKeeper 會將一個10位帶有0填充的序列號附加到客戶端設(shè)置的 znode 路徑之后。例如 locknode/guid-lock- 會返回 locknode/guid-lock-0000000001;
• ephemeral：臨時節(jié)點，當(dāng)客戶端和 ZooKeeper 連接斷開時，臨時節(jié)點會被刪除，能夠避免死鎖。但這個斷開檢測依然有一定心跳延遲，所以仍然需要自增 id 來避免互斥性被破壞。

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

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

如上圖所示，每個客戶端只監(jiān)聽比自己小的 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 

釋放鎖非常簡單：客戶端直接刪除他們在步驟 1 創(chuàng)建的 znode 節(jié)點。

有幾點需要注意：

• 刪除一個 znode 只會導(dǎo)致一個客戶端被喚醒，因為每個節(jié)點正好被一個客戶端 watch 著，通過這種方式，可以避免驚群效應(yīng);
• 沒有輪詢或超時;
• 如果在調(diào)用 create() 時 ZooKeeper 創(chuàng)建鎖成功但沒有返回給客戶端就失敗了，客戶端收到錯誤響應(yīng)后，應(yīng)該先調(diào)用 getChildren() 并檢查該路徑是否包含 guid 來避免這一問題。

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

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

ZooKeeper 的另一個缺點是需要另外維護(hù)一套 ZooKeeper 服務(wù)(已有則忽略)。

etcd

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

我們來看下 etcd 是如何解決分布式鎖“三大問題”的：

• 互斥：etcd 支持事務(wù)，通過事務(wù)創(chuàng)建 key 和檢查 key 是否存在，可以保證互斥性;
• 容錯：etcd 基于 Raft 共識算法，寫 key 成功至少需要超過半數(shù)節(jié)點確認(rèn)，這就保證了容錯性;
• 死鎖：etcd 支持租約(Lease)機(jī)制，可以對 key 設(shè)置租約存活時間(TTL)，到期后該 key 將失效刪除，避免死鎖;etc 也支持租約續(xù)期，如果客戶端還未處理完可以繼續(xù)續(xù)約;同時 etcd 也有自增 id，在下文介紹。

為了幫助開發(fā)者快速實現(xiàn)分布式鎖，etcd 給出了 clientv3 包，其中分布式鎖在 concurrency 包中。按照官方文檔給出的案例1，首先創(chuàng)建一個新的會話(session)并指定租約的 TTL，然后實例化一個 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ù)的源代碼很容易找到，由于篇幅我就不放出來了，但源代碼中可以看到的一些其他機(jī)制包括：

• Revision 機(jī)制。一個全局序列號，跟 ZooKeeper 的序列號類似，可以用來避免 watch 驚群;
• Prefix 機(jī)制。即上述代碼中 etcd 會創(chuàng)建一個前綴為 /my-lock/ 的 key(/my-lock/ + LeaseID)，分布式鎖由該前綴下 revision 最小(最早創(chuàng)建)的 key 獲得;
• Watch 機(jī)制。跟 ZooKeeper 一樣，客戶端會監(jiān)聽 revision 比自己小的 key，當(dāng)比自己小的 key 釋放鎖后，嘗試去獲得鎖。

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

選擇 etcd 的原因可能有：

• 生產(chǎn)環(huán)境中已經(jīng)大規(guī)模部署了 etcd 集群;
• etcd 在保證強(qiáng)一致性的同時真的夠快，性能介于 Redis 和 ZooKeeper 之間;
• 許多語言都有 etcd 的客戶端庫，很容易使用;

Chubby

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

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

• 粗粒度(Coarse-grained)。相對于細(xì)粒度(Fine-grained)，粗粒度鎖會持續(xù)幾小時或幾天;
• 可用性、可靠性;
• 可以存儲一些元數(shù)據(jù);
• 大量廉價機(jī)器部署;

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

[[419432]]

為了容錯，一個 Chubby 集群包含 5 個節(jié)點，組成一個 Chubby cell。這 5 個節(jié)點只有一個是 master 其余都是 replicas，只有 Master 能夠處理請求和讀寫文件，其它副本節(jié)點通過 Paxos 算法復(fù)制 Master 的行為來容錯。

Chubby 還支持：

• Sequencer：鎖的序列號(更好的避免死鎖和 watch);
• Session：客戶端會話，包括租約時間;
• KeepAlive：在租約快要過期時可以發(fā)送 KeepAlive 續(xù)約;
• Cache：鎖服務(wù)支持大量的客戶端，為了減少讀請求支持客戶端無感知的緩存;

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

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

根據(jù)數(shù)據(jù)庫(持久化存儲)中的數(shù)據(jù)恢復(fù)出 session 和鎖相關(guān)信息，并將 session 租約延長到一個可能的最大期限;

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

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

整個過程如圖所示。其中綠色都是安全時期，橙色部分是危險時期，Chubby 集群切換到新的 Master。

Chubby 我不想太過深入，我想大家沒有再造一個 Chubby 的動力了。

結(jié)語

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

想要深入分布式鎖問題的同學(xué)，我推薦好好看一遍 Lamport 的 "Time, clocks, and the ordering of events in a distributed system"，當(dāng)然我的新書里也有對該論文的剖析，下半年會跟大家見面。

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

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 實現(xiàn)分布式鎖官方文檔, https://zookeeper.apache.org/doc/r3.7.0/recipes.html#sc_recipes_Locks

11. etcd 實現(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.