萬字長文說透分佈式鎖

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

TL; DR

太長不看？沒關係，我已經做好了思維導圖，點個分享再收藏，支持一下，也方便以後查閱。

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

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

分佈式鎖大多都是 Advisory lock，即在訪問數據前先獲取鎖信息，再根據信息決定是否可以訪問；相對的是 mandatory lock，未授權訪問鎖定的數據時會產生異常。

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

  1. 很多 (業務) 系統很難改造成使用共識算法，鎖服務更易於保持已存在的程序結構和通信模式；

  2. 基於鎖的接口更爲程序員所熟悉。雖然可能只是表面熟悉 :)，但肯定好過使用一個共識庫；

  3. 鎖服務能減少客戶端系統運行的服務器數目。一個共識算法需要 quorum 做決策，即我們常說的超過半數節點可用，每個客戶端都構建成 quorum 需要大量的服務器，而一套分佈式鎖服務可以安全地服務多個客戶端。

因此，相比於客戶端實現一個共識庫，使用分佈式鎖服務耦合更松、更易用、也更節省資源。

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

總的來說，分佈式鎖服務有三個必備的性質：

值得注意的是，容錯會以性能爲代價，容錯性取決於你的系統級別，如果你的系統可以承擔分佈式鎖存在誤差，那麼單節點或者簡單的主從複製也許就能滿足；如果你的系統非常嚴格，例如金融系統或航天系統，那麼就要考慮每個 corner case——本文更傾向於討論後者。

我們會拿着這三個屬性逐一分析各種分佈式鎖的實現。在此之前，先把分佈式鎖分爲兩大類：自旋類和監聽類。

因此，本文默認讀者大概瞭解 Redis、ZooKeeper 和 etcd 是什麼。

如此，我們在頭腦中已經有了一個很好的框架，現在開始往思維導圖中填充知識。

基於數據庫的實現

最簡單的，我們想到通過某個獨立的數據庫（或文件），當獲取到數據時，往數據庫中插入一條數據。之後的進程想要獲取數據，會先檢查數據庫是否存在記錄，就能夠知道是否有別的進程持有鎖，這便實現了分佈式鎖的互斥性。

數據庫可以通過主從同步複製來實現容錯，雖然主從複製切換時不會非常輕鬆，可能需要管理員參與。

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

fz3vOa

可見基於數據庫的實現較爲繁瑣，要自己維護鎖的 TTL；除非使用分佈式數據庫，否則主從複製的故障切換並不輕鬆。

除了麻煩之外，如果經常用數據庫你也知道，在高併發常見下數據庫讀寫是非常緩慢的，會導致我們的系統性能存在瓶頸。如果採用多個獨立數據庫進行容錯，那性能就更差了。

於是，爲了分佈式鎖的性能，開始轉向基於 Redis 或者 memcache 等內存存儲系統來實現分佈式鎖。

基於 Redis 的實現

分佈式鎖最多的恐怕就是基於 Redis 的實現。首先我們從單節點 Redis 開始。

基於單節點 Redis 的分佈式鎖

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

set key value nx px 10000

set 命令後的 5 個參數分別是：

  1. 第一個爲 key 作爲鎖名；

  2. 第二個爲 value，一般傳入一個唯一 id，例如一個隨機數或者客戶端 mac 地址 + uuid；

  3. 第三個爲 NX，意思是 SET IF NOT EXIST，即只有 key 不存在時才進行 set 操作；若 key 已經存在 (鎖已被佔)，則不做任何操作；

  4. 第四個爲 PX，作用是給這個 key 加一個過期時間，具體時間長短由第五個參數決定；

  5. 第五個爲具體的過期時間，對應第四個參數 PX 是毫秒，EX 是秒；

這個方案在互斥性和避免死鎖上性能良好，且非常輕量。但單節點的 Redis 存在單點故障。注意，Redis 主從複製是異步的，所以加入從節點會增加破壞互斥性的風險。爲了實現容錯性，就有了基於多節點 Redis 的分佈式鎖，即 Redlock。

基於多節點 Redis 的分佈式鎖

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

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

  1. 依次對多個 Redis 實例進行加鎖 (一般是 3 個或 5 個)，加鎖命令使用單實例 Redis 的加鎖命令；

  2. 爲了避免在某個節點長時間獲取不到鎖而阻塞，每次獲取鎖操作也有一個超時時間，遠小於 TTL，超過超時時間則認爲失敗，繼續向下一個節點獲取鎖；

  3. 計算整個獲取多把鎖的總消耗時間，只有在超過半數節點都成功獲取鎖，並且總消耗時間小於 TTL，則認爲成功持有鎖；

  4. 成功獲取鎖後，要重新計算 TTL = TTL - 總消耗時間；

  5. 如果獲取鎖失敗，要向所有 redis 實例發送釋放鎖的命令。

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

Redlock 容錯性依賴於一個時間戳的計算，這在分佈式系統中並不受待見，於是有了一場著名的論戰。

Redlock 論戰

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

  1. Redis 命令避免了死鎖但可能會不滿足互斥性，因爲沒有自增 id 或 fencing token 來阻斷同時獲得鎖的兩個客戶端；

  2. Redlock 基於時間戳的合理性值得懷疑，多臺服務器難以保證時間一致；

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

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

第二點 Martin 認爲，Redlock 的時間戳計算方式不可靠，每臺服務器的走時並不絕對準確，例如 NTP 進行同步時系統會發生時鐘漂移，即當前服務器的時間戳突然變大或變小，這都會影響 Redlock 的計算。

Martin 的這篇文章引起了大家對分佈式鎖廣泛討論。Redis 作者 antirez 也不甘示弱，發表文章《Is Redlock safe?》進行反駁，迴應了上述兩個問題，我總結了 antirez 的論點：

  1. 針對第一點，雖然 Redlock 提供不了自增 id 這樣的字段，但是由客戶端指定的字段 value 也可以實現唯一標識，並通過 read-modify-write 原子操作來進行檢查；

  2. 時鐘發送漂移肯定會影響 Redlock 安全性，可是通過恰當的運維，例如不要隨意人爲修改時鐘、將一次大的 NTP 時鐘調整轉換成多次微小的調整等方式，使時鐘修改不超過某個範圍就不會對 Redlock 產生影響。

非常推薦閱讀爭論的兩篇文章，但篇幅所限我只提取了觀點。關於爭論的詳細內容張鐵蕾老師的文章《基於 Redis 的分佈式鎖到底安全嗎（下）？》也有着比較完整的中文回顧。

對於這兩個問題，我想談談我的理解。

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

我認爲 fencing token 是一個更好的解決方案，一個單調自增的 id 更符合我們的直覺，同時也更好進行 debug。

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

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

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

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

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

Martin Kleppmann 沒有回覆任何 Hacker News 的評論，他覺得自己想要表達的都已經說完了，他不想參與爭論，他認爲實際上一個分佈式系統到底該怎麼做取決於你如何管理你的系統。

本文想表達的也是這樣的觀點，軟件工程沒有銀彈，這些 trade-off 取決於你係統的重要級別，你怎麼管理你的分佈式系統。

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

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

  2. 分佈式系統中會有成千上萬的機器，那麼不大可能發生的事情會變得極有可能；

  3. 其中一些問題其實是很常見的（例如：網絡分區）。

基於 ZooKeeper 實現

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

容錯性當然離不開我們的老朋友共識算法，我們不再讓客戶端依次上多個鎖，而是讓鎖服務器通過共識算法複製到多數派節點，然後再回復客戶端。由於共識算法本身不依賴系統時間戳而是邏輯時鐘（Raft 的任期或 Paxos 的 epoch），故不存在時鐘漂移問題。

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

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

ZooKeeper 是一個分佈式協調服務，參見：《ZooKeeper 設計原理》。

基於 ZooKeeper 實現的分佈式鎖依賴以下兩個節點屬性：

ZooKeeper 官方文檔有提供現成的分佈式鎖實現方法：

  1. 首先調用 create()，鎖路徑例如 locknode/guid-lock-，並設置 sequence 和 ephemeral 標誌。guid 是客戶端的唯一標識，如果 create() 創建失敗可以通過 guid 來進行檢查，下面會提到；

  2. 調用 getChildren() 獲取子節點列表，不要設置 watch 標誌（很重要，可以避免 Herd Effect，即驚羣效應）；

  3. 檢查 2 中的子節點列表，如果步驟 1 中創建成功並且返回的序列號後綴是最小的，則客戶端持有該分佈式鎖，到此結束；

  4. 如果發現序列不是最小的，則從子節點列表中選擇比當前序列號小一位的節點記爲 p，客戶端調用 exist(p, watch=true)，即監聽 p，當 p 被刪除時收到通知（該節點只有比自己小一位的節點釋放時才能獲得鎖）；

  5. 如果 exist() 返回 null，即前一個分佈式鎖被釋放了，轉到步驟 2；否則需要一直等待步驟 4 中 watch 的通知。

如上圖所示，每個客戶端只監聽比自己小的 znode，可以避免驚羣效應。

獲取鎖的僞代碼如下：

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 創建的 znode 節點。

有幾點需要注意：

當然，雖然 ZooKeeper 的實現看起來更爲可靠，但根據你實現鎖的方式，可能還是會有大量的鎖邏輯調試、鎖爭搶等問題。

基於 ZooKeeper 的分佈式鎖性能介於基於 Mysql 和基於 Redis 的實現之間，性能上當然不如單節點 Redis。

ZooKeeper 的另一個缺點是需要另外維護一套 ZooKeeper 服務（已有則忽略）。

etcd

Etcd 是著名的分佈式 key-value 存儲結構，因在 Kubernetes 中使用而聞名。etcd 同樣可以用來實現分佈式鎖，官方也很貼心的提供了 clientv3 包給開發者快速實現分佈式鎖。

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

爲了幫助開發者快速實現分佈式鎖，etcd 給出了 clientv3 包，其中分佈式鎖在 concurrency 包中。按照官方文檔給出的案例 1，首先創建一個新的會話 (session) 並指定租約的 TTL，然後實例化一個 NewMutex() 之後就可以調用 Lock() 和 Unlock() 進行搶鎖和釋放鎖。代碼如下：

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() 函數的源代碼很容易找到，由於篇幅我就不放出來了，但源代碼中可以看到的一些其他機制包括：

本質上 etcd 和 ZooKeeper 對分佈式鎖的實現是類似的。

選擇 etcd 的原因可能有：

Chubby

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

Chubby 是 Google 研發的松耦合分佈式鎖服務，此外 GFS 和 BigTable 使用 Chubby 來存儲一些元數據。Chubby 有以下幾大特點：

Chubby 依賴於 Paxos 共識算法來實現容錯，數據以 UNIX 文件系統方式進行組織 (稱爲 Node)，同樣有 Ephemeral 類型的臨時節點，斷開連接後會被刪除；支持監聽某個 Node——總而言之，我們可以從 ZooKeeper 上看到許多 Chubby 的影子，ZooKeeper 和 Chubby 解決的問題是比較類似的，因此很多人認爲 ZooKeeper 是 Chubby 的開源實現，不過兩者的具體架構還是略有不同。

爲了容錯，一個 Chubby 集羣包含 5 個節點，組成一個 Chubby cell。這 5 個節點只有一個是 master 其餘都是 replicas，只有 Master 能夠處理請求和讀寫文件，其它副本節點通過 Paxos 算法複製 Master 的行爲來容錯。

Chubby 還支持：

比較有意思的是 Chubby 的故障恢復。當 Master 發生故障，其內存的 session 和鎖信息會丟失，session 中最重要的租約信息，Paxos 算法會選舉出新的 Master，然後：

  1. 選擇新的 epoch，可以理解爲 Raft 中的任期，小於 epoch 的客戶端請求會被拒絕，保證了 Master 不會響應舊 Master 的請求；

  2. 根據數據庫 (持久化存儲) 中的數據恢復出 session 和鎖相關信息，並將 session 租約延長到一個可能的最大期限；

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

  4. 從新請求中發現老 Master 創建的 Handle 時，新 Master 也需要重建，一段時間後 (一般是一分鐘)，刪除沒有 Handle 的臨時節點。

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

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

結語

寫這篇文章的時候內心是忐忑的，爲了 ego 和不被大家罵我儘量不犯錯，但錯誤實在難免，並且隨着時間推移可能兩三年後一些解決方案並不適用。這篇文章實在花了我許多時間和精力。

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

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

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

  11. etcd 實現分佈式鎖官方案例，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.

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/35aCS_5GqLyzZS3VobL6fg

猜你喜歡