分散式系統研究者 Martin Kleppmann 昨天發表了一篇針對 Redlock（http://redis.io/topics/distlock）的分析，你可以在這裡找到原文：http://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html

Redlock 是我為了搭配 Redis 使用而設計的客戶端分散式鎖定演算法，不過這個演算法是在客戶端協調一組具備特定能力的資料儲存節點，藉此建立一個具備多主架構、容錯能力，且希望是安全的、擁有自動釋放能力的分散式鎖。你也可以用 MySQL 而不是 Redis 來實作 Redlock，舉例來說。

這個演算法的目標，是讓那些原本只用單一 Redis 執行個體、或是採用主從備援架構來實作分散式鎖的人，能夠轉向一個更可靠、更安全，同時又具備極低複雜度與良好效能的方案。

自從我發表 Redlock 以來，許多人已用多種語言實作了它，並將它用於不同的用途。

Martin 對這個演算法的分析結論是 Redlock 並不安全。Martin 發表這篇分析是件好事，我在最初的 Redlock 規格文件（http://redis.io/topics/distlock）中就曾邀請大家進行分析。所以，謝謝 Martin。不過我並不同意這份分析。好處在於，分散式系統不像程式設計的其他領域，它是相當數學化、精確的，或者說，它要嘛是精確的，要嘛就不是，因此一個演算法能否在特定假設下保證某組性質，是可以被明確檢驗的。在這篇文章中，我將剖析 Martin 的分析，讓領域內的其他專家可以對照這兩份文件（分析與反分析），最終釐清 Redlock 是否能被視為安全的。

為什麼 Martin 認為 Redlock 不安全

分析中的論點主要有兩個：

1. 具備自動釋放功能的分散式鎖（也就是互斥性僅在取得鎖後的一段固定時間內有效）需要有一種機制，來避免客戶端在過期後仍繼續使用鎖，進而在存取共享資源時破壞互斥性。Martin 認為 Redlock 並沒有這樣的機制。
2. Martin 認為，無論問題「1」如何，該演算法本身在本質上就是不安全的，因為它對系統模型做了在實務系統中無法被保證的假設。

為了清楚起見，我會分別回應這兩個疑慮，先從第一點「1」開始。

分散式鎖、自動釋放與權杖

一個沒有自動釋放機制、讓持有鎖的客戶端可以無限期持有鎖的分散式鎖，基本上是沒有用處的。如果持有鎖的客戶端當機，且無法在短時間內帶著完整狀態恢復，就會產生死結，使得分散式鎖原本要保護的共享資源永遠無法被存取。這會造成在多數情境下都無法接受的活性（liveness）問題，因此一個合理的分散式鎖必須能夠自動釋放。

因此實務上的鎖會提供給客戶端一個最長存活時間。過期之後，作為鎖最主要性質的互斥保證就消失了：另一個客戶端可能已經取得了鎖。如果兩個客戶端在不同時間取得鎖，但第一個客戶端因為 GC 暫停或其他排程問題而速度過慢，以至於在第二個已取得鎖的客戶端同時，還在共享資源的脈絡下嘗試執行工作，會發生什麼事？

Martin 認為這個問題可以透過讓分散式鎖伺服器在每次授與鎖時提供一個權杖（token）來避免，在他的例子中，這個權杖只是一個保證會持續遞增的數字。Martin 使用權杖的理由是，這樣當兩個不同的客戶端同時存取被上鎖的資源時，我們可以在資料庫的寫入交易中（假設該交易具體實現了客戶端所做的工作）利用這個權杖：只有持有最大鎖編號的客戶端才能寫入資料庫。

用 Martin 的話來說：

「這個問題的修正其實相當簡單：你需要在每次對儲存服務的寫入請求中都附上一個 fencing token。在這個脈絡下，fencing token 只是一個每當客戶端取得鎖時就會遞增的數字（例如由鎖服務來遞增）。」

… 節略 …

「請注意，這需要儲存伺服器主動參與檢查權杖，並拒絕任何權杖回退的寫入。」

我認為這個論點有幾個問題：

1. 在大多數需要能保證互斥性的分散式鎖系統的場合，一旦這個性質被破壞，你就已經出問題了。分散式鎖之所以非常有用，正是因為我們對共享資源沒有其他控制手段。在他的分析中，Martin 假設當鎖的互斥性被破壞時，你總是有另一種方式可以避免競爭條件。我認為這種對具有強保證的分散式鎖的思考方式很奇怪——如果你可以用別的方式解決競爭，那你根本不需要強保證的鎖。儘管如此，為了完整說明 Redlock 在這個非常人為的情境下也能良好運作，我還是會繼續討論下面的幾點。
2. 如果你的資料儲存能夠做到只有當權杖大於所有過去的權杖時才接受寫入，那它就是一個線性一致（linearizable）的儲存。如果你擁有線性一致的儲存，你大可為每次取得的 Redlock 產生一個遞增 ID，這會讓 Redlock 等同於另一個每次授與新鎖時都提供遞增權杖 ID 的分散式鎖系統。不過在下一點我會說明其實不需要這麼做。
3. 然而，「2」無論如何都不是一個合理的選擇：大多數時候對共享資源進行操作的結果，並不是寫入到一個線性一致的儲存中，那該怎麼辦？每個 Redlock 都會關聯一個很大的隨機權杖（其產生方式讓碰撞可以被忽略。Redlock 規格書中原文假設是「來自 /dev/urandom 的 20 個位元組」）。有了唯一權杖要怎麼用？例如你可以實作 Check and Set。在開始操作共享資源時，我們先將其狀態設為「`<token>`」，然後只有在寫入時權杖仍然相同，才執行讀取-修改-寫入操作。
4. 值得注意的是，在某些使用情境下，有人可能會說有序的權杖無論如何還是有用的。雖然很難想到具體的使用情境，但請注意，就如同 Martin 提到的 GC 暫停，取得權杖的順序未必會對應到客戶端實際嘗試操作共享資源的順序，因此鎖的順序未必與對共享資源操作的效應有因果關係。
5. 大多數時候，鎖是用來存取以非交易方式更新的資源。有時候我們使用分散式鎖是為了移動實體物件，舉例來說。或是與另一個外部 API 互動等等。

我想再次強調，這整件事奇怪的地方在於，它假設你在互斥性被破壞時永遠都必須有辦法處理競爭條件。實際上，如果你已經有這樣一套能在競爭時避免問題的系統，你很可能根本不需要分散式鎖，至少不需要具有強保證的鎖，而只需要一個弱鎖來在大多數時候避免並行存取、基於效能考量就夠了。

然而，即使你碰巧認同 Martin 認為上述機制非常有用的看法，重點在於，每個鎖的唯一識別碼也能達到同樣的目的，而且在不需要對儲存提供強保證的前提下要實用得多。

來談談系統模型

上述的批評基本上適用於所有具備自動釋放、但未在每次授與鎖時提供單調遞增計數器的分散式鎖，而不只是針對 Redlock。然而 Martin 的另一個批評則是針對 Redlock 本身。在那裡 Martin 真正分析了這個演算法，並得出它是有缺陷的結論。

Redlock 假設的是一個半同步（semi-synchronous）的系統模型，在其中不同的行程可以用大致相同的「速度」來計時。不同的行程之間完全不需要在絕對時間上有誤差範圍的保證。它們只需要做到，例如，能以最多 10% 的誤差來計算 5 秒鐘。所以一個實際上算了 4.5 秒，另一個算了 5.5 秒，這樣就可以了。

Martin 也指出 Redlock 需要有界的訊息最大延遲，就我所知這是不正確的（稍後我會解釋他的推理出了什麼問題）。

那麼就先從不同行程無法以相同速率計時的問題開始談起。

Martin 說系統時鐘會因為兩個問題而隨機跳動：

1. 系統管理員手動修改時鐘。
2. ntpd 常駐程式因為收到更新而大幅調整時鐘。

上述兩個問題可以透過「1」不要這麼做（否則就連用「echo foo > /my/raft/log.bin」去覆寫 Raft 日誌也會是個問題），以及「2」使用不會直接跳動時間、而是將時間變化分散在一段較長時間內逐步調整的 ntpd 來避免。

不過我認為 Martin 有一點是對的：Redis 與 Redlock 的實作應該改用多數作業系統提供的單調時間（monotonic time）API，以降低上述問題帶來的影響。這在過去就曾被多次提議，雖然會為 Redis 增加一點複雜度，但這是個好主意：我會在接下來的幾週內實作它。然而，儘管我們將會改用單調時間 API，因為這樣做有好處，但在一個沒有會竄改時鐘的軟體（時間伺服器）或人為（系統管理員）因素的作業系統中，行程即使使用 gettimeofday()，也*能夠*以有界的誤差來計算相對時間。

請注意，過去也曾有人嘗試即使假設有界的絕對時間誤差（透過使用 GPS 設備）來實作分散式系統。Redlock 並不需要那樣的東西，它只需要不同的行程能夠把 10 秒鐘算成 9.5 或 11.2 秒（在例子中最多正負 2 秒），就足夠了。

那麼 Redlock 到底安不安全？這取決於上述條件。為了簡化、排除實作細節（像是熱愛 POKE 時鐘的系統管理員與時間伺服器），讓我們假設我們使用單調遞增的時間 API。一個行程能否以固定的最大誤差百分比來計算相對時間？我認為答案是響亮的「可以」，而且回答這個問題，遠比回答：「行程能否在不毀損日誌的情況下寫入日誌」來得簡單。

網路延遲及其他

Martin 說 Redlock 不僅僅依賴於行程能以大致相同的速度計時，他說：

「然而，Redlock 並非如此。它的安全性依賴於大量的時間假設：它假設所有 Redis 節點在過期前都能以大致正確的時間長度持有鍵；網路延遲相對於過期時間是很小的；而且行程暫停的時間遠短於過期時間。」

所以讓我們把上述的主張拆成不同部分來看：

1. Redis 節點以大致正確的時間長度持有鍵。
2. 網路延遲相對於過期時間是很小的。
3. 行程暫停的時間遠短於過期時間。

Martin 每次提到「系統時鐘跳動」時，我都假設我們已經透過不去胡亂撥動系統時間來涵蓋這個問題，或為了簡化起見，透過使用單調時間 API 來處理。所以：

關於主張 1：這不是問題，我們已經假設我們能以大致相同的速度計時，除非有任何實際的論點可以反駁這一點。

關於主張 2：情況有點複雜。Martin 說：

「好吧，或許你認為時鐘跳動是不切實際的，因為你非常有信心已經正確設定 NTP，讓它只會平滑地調整時鐘。」（對，這點我們有共識 ;-) 他接著說……）

「在這種情況下，讓我們來看一個行程暫停如何導致演算法失敗的例子：客戶端 1 向節點 A、B、C、D、E 請求鎖定。當回應還在傳送給客戶端 1 的途中，客戶端 1 進入了 stop-the-world GC。所有 Redis 節點上的鎖都過期了。客戶端 2 在節點 A、B、C、D、E 上取得了鎖。客戶端 1 結束 GC，並收到來自 Redis 節點、顯示它已成功取得鎖的回應（這些回應在行程暫停期間一直被留在客戶端 1 的核心網路緩衝區中）。現在客戶端 1 和客戶端 2 都認為自己持有鎖。」

如果你閱讀我已經好幾個月沒動過的 Redlock 規格書，你會看到取得鎖的步驟是：

1. 取得目前時間。
2. … 執行取得鎖所需的所有步驟 …
3. 再次取得目前時間。
4. 檢查我們是否已經超時，或是否已夠快地取得鎖。
5. 利用你的鎖進行工作。

請注意步驟 1 和 3。無論在網路或相關行程中發生什麼延遲，在取得多數節點的同意後，我們會*再次檢查*是否已經超時。延遲只可能發生在步驟 3 之後，導致鎖被視為有效但實際上已經過期，也就是說，我們又回到了 Martin 所指出的、客戶端在鎖的有效期限過後仍未能在共享資源上停止工作的第一個問題。容我再次說明，這個問題是*所有分散式鎖實作*共通的，而權杖作為解法既不切實際，也同樣可以在 Redlock 上使用。

請注意，無論在 1 和 3 之間發生什麼事，你可以加入任意的網路延遲，只要經過的時間過長，鎖就永遠會被視為無效，因此 Redlock 對於行程之間具有無界延遲的訊息看起來是完全免疫的。這正是它設計時的目標，而我看不出上述的競爭條件如何可能發生。

然而 Martin 的部落格文章也經過多位分散式系統專家的審閱，所以我不確定是我遺漏了什麼，還是 Redlock 的運作方式同時被許多人忽略了。我很樂意收到對此的進一步釐清。

上述內容也回應了關於「行程暫停」的第三點疑慮。在取得鎖的過程中發生的暫停，並不會影響演算法的正確性。然而，如同前面已涵蓋的，它們確實可能影響客戶端在指定的鎖存活時間內完成工作的能力，這與任何其他具備自動釋放功能的分散式鎖的情況相同。

關於網路延遲的題外話

只是快速補充一下。在具備自動釋放功能的分散式鎖的伺服器端實作中，客戶端可能會請求取得鎖，伺服器也可能允許客戶端這麼做，但行程可能會陷入 GC 暫停，或網路可能很慢等等，因此客戶端可能會太晚才收到「OK，鎖是你的了」的回應，此時鎖其實已經過期。然而，你可以做很多事來避免行程長時間休眠，卻很難避免網路延遲，所以在取得鎖之前與之後檢查時間、看看還剩下多少時間的步驟，其實即使在使用其他實作帶有過期時間的鎖的系統時，也應該是常見的做法。

要不要 Fsync？

Martin 在某個段落談到 Redlock 使用延遲重啟節點的做法。這同樣需要能夠或多或少等待一段指定時間的能力，如同上面所涵蓋的。實在沒有必要再重複同樣的論點。

然而，關於這點重要的是，這個步驟是可選的。你可以將每個 Redis 節點設定為在每次操作時都執行 fsync，這樣當客戶端收到回覆時，就知道鎖已經被持久化到磁碟上。這就是大多數提供強保證的其他系統的運作方式。而 Redlock 非常有趣的地方在於，你可以透過實作延遲重啟來完全選擇不涉及磁碟。這意味著用少數幾個 Redis 執行個體就有可能每秒處理數十萬個鎖，這是用其他系統無法達成的。

GPS 設備與本機電腦時鐘的比較

回到系統模型，讓 Redlock 系統模型得以實用的原因之一，是你可以假設行程永遠不會與系統時鐘發生分割。請注意，這與其他使用 GPS 設備的半同步模型不同，因為在那種情況下可能會發生兩種不太明顯的分割：

1. GPS 與 GPS 網路發生分割，因此無法取得定位。
2. 行程與 GPS 之間無法交換訊息，或交換的訊息有延遲。

上述問題可能會導致活性或安全性違規，取決於系統如何協調（安全性問題只有在設計有誤時才會發生，例如 GPS 以非同步方式更新系統時間，以至於當 GPS 無法運作時，絕對時間誤差可能會超過最大上限）。

Redlock 的系統模型沒有這些複雜性，也不需要額外的硬體，只需要電腦的時鐘，即使是非常廉價、帶有因晶體溫度及其他影響精度的因素所造成的明顯偏差的時鐘也行。

結論

我認為 Martin 關於單調時間 API 的觀點是正確的，Redis 與 Redlock 的實作應該使用它來避免因系統時鐘被更動而產生的問題。然而，如上所述，我無法找出分析中其他會影響 Redlock 安全性的要點，也不認為他最後提出「當需要互斥保證時，人們不應該使用 Redlock」的結論是有道理的。

若能收到更多來自專家的回饋，並使用 Jepsen 或類似工具來測試這個演算法以累積更多數據，那會是很好的事。

非常感謝協助我審閱這篇文章的朋友們。