Redlock 安全嗎？
Martin Kleppmann（馬丁·克雷普曼），一位 distributed systems researcher(分散式系統研究者)，昨日發表了一篇針對 Redlock（http://redis.io/topics/distlock）的分析，你可以在這裡看到：http://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html
Redlock 是我設計用於 Redis 的 client side distributed locking algorithm(用戶端分散式鎖定演算法)，但該演算法是在用戶端協調一組具備特定能力的 data store(資料儲存庫)節點，以建立一個具備 auto release(自動釋放)能力的 multi-master fault tolerant(多主容錯)、且有望安全的 distributed lock(分散式鎖)。舉例來說，你也可以使用 MySQL 而非 Redis 來實作 Redlock。
該演算法的目標，是讓原本使用單一 Redis 執行個體、或是具備 failover(容錯移轉)的 master-slave(主從式)架構來實作 distributed lock 的人，轉向更可靠、更安全，同時具備極低複雜度與良好效能的方案。
自從我發表 Redlock 以來，已經有人用多種程式語言實作了它，並將其用於不同的用途。
馬丁·克雷普曼對該演算法的分析結論是 Redlock 並不安全。很高興馬丁·克雷普曼發表了這篇分析，我在原始的 Redlock 規格文件（http://redis.io/topics/distlock）中就曾請求外界進行分析。所以，謝謝馬丁·克雷普曼。不過，我並不認同這份分析。好處在於，分散式系統不像程式設計的其他領域，它是相當數學化、精確的，否則就不是；因此，一個演算法能否在特定假設下保證一組特定的屬性，是可以被驗證的，或者該演算法可能在某些假設下無法保證這些屬性。在這篇分析中，我將剖析馬丁·克雷普曼的分析，讓領域內的其他專家得以檢視這兩份文件（該分析與這篇反駁分析），最終我們或許能釐清 Redlock 是否可被視為安全的。
為什麼馬丁·克雷普曼認為 Redlock 不安全
分析中的論點主要有兩個：
- 具備 auto release 功能的 distributed lock（其互斥鎖定屬性僅在取得鎖定後的一段固定時間內有效）需要一種機制，以避免用戶端在過期時間後仍繼續使用鎖定、進而在存取共享資源時違反 mutual exclusion(互斥)的問題。馬丁·克雷普曼認為 Redlock 並沒有這樣的機制。
- 馬丁·克雷普曼認為，無論問題「1」如何，該演算法本質上就是不安全的，因為它對 system model(系統模型)所做的假設，在實務系統中是無法被保證的。
為了清楚起見，我將分別回應這兩個疑慮，先從第一點「1」開始。
distributed lock、auto release 與 token(權杖)
沒有 auto release 機制的 distributed lock，也就是鎖定擁有者將無限期持有鎖定的情況，基本上是毫無用處的。如果持有鎖定的用戶端當機，且無法在短時間內帶著完整狀態恢復，就會產生死結，使得 distributed lock 試圖保護的共享資源永遠無法被存取。這會造成在大多數情境下都無法接受的 liveness(活性)問題，因此，一個健全的 distributed lock 必須能夠自動釋放自己。
因此，實務上的鎖定會提供給用戶端一個最長存活時間。在過期時間之後，作為鎖定最主要屬性的 mutual exclusion 保證就消失了：另一個用戶端可能已經取得了該鎖定。如果兩個用戶端在不同時間取得了鎖定，但第一個用戶端因為 GC 暫停或其他排程問題而速度過慢，以至於與第二個已取得鎖定的用戶端同時在共享資源的脈絡下嘗試執行工作，會發生什麼事？
馬丁·克雷普曼認為，這個問題可以透過讓 distributed lock 伺服器在每次提供鎖定時附帶一個 token 來避免，在他的範例中，這個 token 僅是一個保證會持續遞增的數字。馬丁·克雷普曼使用 token 的理由是，如此一來，當兩個不同用戶端同時存取被鎖定的資源時，我們可以在資料庫寫入交易（假設該交易具體實現了用戶端所做的工作）中使用該 token：只有持有最大鎖定編號的用戶端才能寫入資料庫。
用馬丁·克雷普曼的話來說：
「修正這個問題的方法其實相當簡單：你需要在發往儲存服務的每個寫入請求中都包含一個 fencing token(圍欄權杖)。在這個脈絡下，fencing token 僅是一個數字（例如由鎖定服務遞增），每當用戶端取得鎖定時就會增加。」
… 節錄 …
「請注意，這需要儲存伺服器主動參與檢查權杖，並拒絕任何權杖出現回退的寫入。」
我認為這個論點有幾個問題：
- 多數情況下，當你需要一個能夠保證 mutual exclusivity(互斥性)的 distributed lock 系統時，一旦這個屬性被違反，你就已經失敗了。當我們對共享資源沒有其他控制手段時，distributed lock 正好非常有用。在他的分析中，馬丁·克雷普曼假設當鎖定的 mutual exclusivity 被違反時，你永遠都有其他方法可以避免競爭條件。我認為這種對具有強保證的 distributed lock 的推理方式非常奇怪，實在不清楚如果你可以用不同方式解決競爭，為何還需要使用具有強屬性的鎖定。不過，為了說明 Redlock 即使在這種非常人為的脈絡下也能良好運作，我仍會在下面繼續討論其他幾點。
- 如果你的 data store 永遠只能在你的 token 大於所有過去的 token 時才接受寫入，那麼它就是一個 linearizable store(線性一致性儲存)。如果你擁有 linearizable store，你大可為每次取得的 Redlock 產生一個遞增的 ID，如此一來，Redlock 就會等同於另一個在每次建立新鎖定時都提供遞增 token ID 的 distributed lock 系統。然而，下一個要點將說明為何這並非必要。
- 然而，「2」無論如何都不是一個明智的選擇：多數情況下，在共享資源上工作的結果並不是寫入 linearizable store，那麼該怎麼做？每個 Redlock 都會關聯一個大型的隨機 token（其產生方式讓碰撞可以被忽略。Redlock 規格在字面上假設為「20 bytes 來自 /dev/urandom」）。有了 unique token(唯一權杖)你能做什麼？舉例來說，你可以實作 Check and Set(條件式寫入)。在開始處理共享資源時，我們將其狀態設為「<token>」，然後僅在寫入時 token 仍相同才執行 read-modify-write(讀取-修改-寫入)。
- 請注意，在某些使用情境中，有人可能會說，擁有有序的 token 仍然是有用的。雖然很難想到具體的使用情境，但請注意，就馬丁·克雷普曼所提到的 GC 暫停而言，token 被取得的順序，並不一定遵守用戶端嘗試處理共享資源的順序，因此鎖定的順序未必與處理共享資源所產生的效應具有因果關係。
- 多數情況下，鎖定被用來存取以非交易方式更新的資源。有時我們會使用 distributed lock 來移動實體物件，舉例來說，或是與另一個外部 API 互動，諸如此類。
我想再次強調，奇怪之處在於，這一切都假設當 mutual exclusion 被違反時，你永遠必須有辦法處理競爭條件下產生的問題。實際上，如果你在競爭條件發生時已有這樣的系統來避免問題，你很可能根本不需要 distributed lock，或者至少不需要具有強保證的鎖定，而只需要一個弱鎖定，以便在大多數時候避免同時存取、進而提升效能。
然而，即使你碰巧認同馬丁·克雷普曼關於上述做法非常有用的看法，重點在於，每個鎖定對應的 unique identifier(唯一識別碼)可以用於相同的目的，但在不需要儲存層提供強保證方面要實用得多。
來談談 system model
上述批評基本上是所有不提供隨每個鎖定遞增計數器的、具備 auto release 的 distributed lock 所共通的，而非 Redlock 特有。然而，馬丁·克雷普曼的另一項批評是針對 Redlock 本身的。在此，馬丁·克雷普曼確實分析了該演算法，並得出它已損壞的結論。
Redlock 假設了一個 semi synchronous system model(半同步系統模型)，在其中不同的處理程序能夠以大致相同的「速度」來計算時間。不同處理程序之間完全不需要在絕對時間上有誤差範圍的限制。它們只需要做到，例如，能夠以最多 10% 的誤差來計算 5 秒鐘。也就是說，一個計算出實際的 4.5 秒，另一個計算出 5.5 秒，這樣就可以了。
馬丁·克雷普曼也指出 Redlock 需要有界的訊息最大延遲，這就我所知並不正確（我稍後會說明他的推理問題出在哪裡）。
那麼，讓我們從不同處理程序無法以相同速率計算時間的問題開始。
馬丁·克雷普曼認為，系統中的時鐘會因為兩個問題而隨機跳動：
- 系統管理員手動調整時鐘。
- ntpd 常駐程式因為收到更新而大幅改變時鐘。
上述兩個問題可以透過「1」不這麼做（否則即使是透過「echo foo > /my/raft/log.bin」來破壞 Raft 日誌也會是個問題），以及「2」使用不會直接跳動時間、而是將時間變更分散在較長時間區間內進行的 ntpd 來避免。
不過，我認為馬丁·克雷普曼關於 Redis 與 Redlock 實作應該切換至多數作業系統所提供的 monotonic time API(單調時間 API)以降低上述問題的看法是正確的。這個建議過去已被多次提出，雖然會在 Redis 內部增加一些複雜度，但卻是個好主意：我會在接下來的幾週內實作它。然而，雖然我們將會切換至 monotonic time API，因為這樣做有其優點，但在沒有會改變時鐘的軟體（時間伺服器）或人為（系統管理員）因素的作業系統中執行的處理程序，即使使用 gettimeofday()，也*能夠*以有界誤差來計算相對時間。
請注意，過去甚至曾有人嘗試透過使用 GPS 裝置來假設有界的絕對時間誤差（來實作分散式系統）。Redlock 並不需要那樣的條件，只需要不同處理程序能夠將 10 秒鐘計算為 9.5 或 11.2 秒（例如最多正負 2 秒的誤差）即可。
那麼，Redlock 安全還是不安全？這取決於上述情況。為了簡化並排除實作細節（對 POKE 情有獨鍾的系統管理員與時間伺服器），讓我們假設我們使用了單調遞增的時間 API。處理程序能否以固定的最大誤差百分比來計算相對時間？我認為答案是肯定的，而且回答這個問題，遠比回答：「處理程序能否在不損毀日誌的情況下寫入日誌」來得簡單。
網路延遲及其他
馬丁·克雷普曼認為 Redlock 不僅依賴於處理程序能夠以大致相同的時間來計算時間，他說：
「然而，Redlock 並非如此。它的安全性依賴於大量的時間假設：它假設所有 Redis 節點會在過期前以大致正確的時間長度持有鍵；假設網路延遲相較於過期時間是很小的；並假設處理程序暫停的時間遠短於過期時間。」
那麼，讓我們將上述主張拆成不同的部分：
- Redis 節點會以大致正確的時間長度持有鍵。
- 網路延遲相較於過期時間是很小的。
- 處理程序暫停的時間遠短於過期時間。
每當馬丁·克雷普曼說「系統時鐘跳動」時，我假設我們已透過不以會對演算法造成問題的方式擺弄系統時間，或為了簡化起見透過使用 monotonic time API 來涵蓋此情況。所以：
關於主張 1：這不是問題，我們已假設除非有任何實際的反對論點，否則我們能夠以大致相同的速度計算時間。
關於主張 2：情況有點複雜。馬丁·克雷普曼說：
「好吧，或許你認為時鐘跳動是不切實際的，因為你非常有信心已經正確設定 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 與 3。無論在網路或相關處理程序中發生什麼延遲，在取得多數節點的認可後，我們會*再次檢查*是否已超出時間。延遲只可能發生在步驟 3 之後，導致鎖定在實際上已過期的情況下仍被視為有效，也就是說，我們又回到了馬丁·克雷普曼所指出的第一個問題：用戶端在鎖定有效期過期前未能停止對共享資源的工作。讓我再次說明，這個問題與*所有具備 auto release 的 distributed lock 實作*共通，而作為解決方案的 token 既不切實際，且同樣可用於 Redlock。
請注意，無論在 1 與 3 之間發生什麼事，你大可加入任何想要的網路延遲，只要經過的時間過長，鎖定就永遠會被視為無效，因此 Redlock 看起來對處理程序之間具有無界延遲的訊息是完全免疫的。這正是它設計時的目標，而我看不出上述競爭條件是如何發生的。
然而，馬丁·克雷普曼的部落格文章也經過多位分散式系統專家的審閱，所以我不確定是我遺漏了什麼，還是 Redlock 的運作方式同時被許多人忽略了。我很樂意收到一些釐清。
上述內容也回應了關於「處理程序暫停」的疑慮編號 3。在取得鎖定的過程中發生的暫停，並不會影響演算法的正確性。然而，如同前文已涵蓋的，它們可能會像任何其他具備 auto release 的 distributed lock 一樣，影響用戶端在指定的鎖定存活時間內完成工作的能力。
關於網路延遲的題外話
只是快速補充一下。在具備 auto release 的 distributed lock 的伺服器端實作中，用戶端可能會請求取得鎖定，伺服器可能會允許用戶端這麼做，但處理程序可能會因 GC 暫停而停頓，或是網路可能很慢等等，因此用戶端可能會太晚才收到「好的，鎖定是你的了」的回應，此時鎖定已經過期。然而，你可以盡力避免你的處理程序長時間休眠，卻很難避免網路延遲，因此即使在使用其他實作具備過期時間的鎖定系統時，在取得鎖定前後檢查時間、看看還剩多少時間的做法，實際上也應該是常見的做法。
要不要 Fsync？
在某個段落，馬丁·克雷普曼談到 Redlock 使用延遲重啟節點。這同樣需要能夠或多或少等待一段指定時間的能力，如前文所述。實在無需再次重複同樣的論點。
然而，關於這點重要的是，這個步驟是可選的。你可以將每個 Redis 節點設定為在每次操作時都執行 fsync，如此一來，當用戶端收到回覆時，就知道鎖定已經持久化到磁碟上。這就是大多數其他提供強保證的系統的運作方式。Redlock 非常有趣的一點在於，你可以透過實作延遲重啟來完全選擇不涉及任何磁碟操作。這意味著僅用少數幾個 Redis 執行個體，就有可能每秒處理數十萬個鎖定，這是其他系統無法達成的。
GPS 裝置與本機電腦時鐘的比較
回到 system model，Redlock 的 system model 之所以實用，其中一個原因是你可以假設處理程序永遠不會與系統時鐘發生分割。請注意，這與使用 GPS 裝置的其他半同步模型不同，因為在那種情況下可能會發生兩個不明顯的分割：
- GPS 與 GPS 網路分割，導致它無法取得定位。
- 處理程序與 GPS 無法交換訊息，或是彼此交換的訊息出現延遲。
上述問題可能會導致 liveness 或安全性違規，具體取決於系統如何編排（只有在設計錯誤的情況下才會發生安全性問題，例如 GPS 非同步地更新系統時間，使得當 GPS 無法運作時，絕對時間誤差可能會超過最大界限）。
Redlock 的 system model 沒有這些複雜性，也不需要額外的硬體，只需要電腦的時鐘，甚至是一個非常便宜、帶有因晶體溫度及其他影響精度的因素而產生的所有明顯偏差的時鐘即可。
結論
我認為馬丁·克雷普曼關於 monotonic time API 的觀點是正確的，Redis 與 Redlock 的實作應該使用它來避免因系統時鐘被更動而產生的問題。然而，如上所述，我找不到分析中其他會影響 Redlock 安全性的論點，也認為他最終得出「當需要互斥保證時，人們不該使用 Redlock」的結論是有失公允的。
若能收到更多來自專家的回饋，並以 Jepsen 或類似工具來測試該演算法以累積更多數據，將會非常有幫助。
非常感謝幫我審閱這篇文章的朋友們。