微信公衆号：小梁程式設計彙
關注可了解更多幹貨。因未開通留言，問題或建議，請私信留言;
内容目錄
1.前言2.你為何要用分布式鎖？3.用鎖保護資源4.使用fencing讓鎖安全5.用時間解決共識6.基于時間假設的Redlock不可靠7.Redlock的同步假設8. 結論9. References
1.前言
再往下看之前，我們先來了解下什麼是RedLock算法。
Redlock算法是Redis作者antirez提出的一種分布式鎖的實作方式，算法思想如下：在Redis的分布式環境中，可以假設有N個Redis master。這些節點完全互相獨立，不存在主從複制或者其他叢集協調機制。我們在N個執行個體上使用與單機Redis相同的方法擷取和釋放鎖。現在我們假設有5個Redis master節點(官方文檔裡将N設定成5，實際大等于3就滿足要求)并在在5台伺服器上面運作這5個執行個體，這樣保證他們不會同時都宕掉。為了取到鎖，Redis用戶端會執行以下操作:
- 擷取目前Unix時間，以毫秒為機關。
- 使用同一個key和具有唯一值的value，依次嘗試從這5個執行個體中擷取鎖。當向Redis請求擷取鎖時，用戶端應該設定一個網絡連接配接和響應逾時時間，這個逾時時間應該小于鎖的失效時間。例如你的鎖自動失效時間為10秒，則逾時時間應該在5-50毫秒之間。這樣可以避免伺服器端Redis已經挂掉的情況下，用戶端還在死死地等待響應結果。如果伺服器端沒有在規定時間内響應，用戶端應該盡快嘗試去另外一個Redis執行個體請求擷取鎖。
- 用戶端使用目前時間減去開始擷取鎖時間（步驟1記錄的時間）就得到擷取鎖使用的時間。當且僅當從大多數（N/2+1，這裡是3個節點）的Redis節點都取到鎖，并且使用的時間小于鎖失效時間時，鎖才算擷取成功。
- 如果取到了鎖，key的真正有效時間等于有效時間減去擷取鎖所使用的時間（步驟3計算的結果）。
- 如果因為某些原因，擷取鎖失敗（沒有在至少N/2+1個Redis執行個體取到鎖或者取鎖時間已經超過了有效時間），用戶端應該在所有的Redis執行個體上進行解鎖（即便某些Redis執行個體根本就沒有加鎖成功，防止某些節點擷取到鎖但是用戶端沒有得到響應而導緻接下來的一段時間不能被重新擷取鎖）。
關于對分布式鎖算法RedLock，DDIA的作者Martin Kleppmann[1]發表了一篇很牛的文章。本文在此基礎上翻譯和融入個人了解，下面正式開始。
Redis 網站上釋出了一種名為Redlock[2]的算法。該算法聲稱在Redis之上實作了容錯分布式鎖（或者更确切地說，租約[3]），身為分布式系統研究人員的我對此保持質疑，并寫下了自己的思考。
由于Redlock 已經有 10 多個獨立的實作，并且不知道誰已經在依賴這個算法，我認為是時候公開分享自己的筆記了。我不會深入探讨 Redis 的其他方面，因為Redis在其他地方已經受到批評[4]。
先說我非常喜歡 Redis，并且我過去在生産中成功使用過它。我認為它非常适合伺服器之間共享一些瞬态、近似、快速變化的資料的情況，并且如果你偶爾由于某種原因丢失這些資料也沒什麼大不了的。例如，一個很好的用例是維護每個 IP 位址的請求計數器（為了限制通路速率）和每個使用者 ID 它使用的不同 IP 位址集（用于濫用檢測）。
然而，Redis 已經逐漸進入資料管理領域，那裡需要有更強的一緻性和持久性——這讓我擔心，因為這不是 Redis 的設計目标。但分布式鎖是這些領域之一。讓我們更詳細地研究一下。
2.你為何要用分布式鎖？
加鎖的目的是確定多個節點在嘗試執行相同工作時，隻有一個節點實際執行此操作（至少一次隻有一個）。這項工作可能是将一些資料寫入共享存儲系統、執行一些計算、調用一些外部 API 等。總而言之，你需要在分布式應用程式中使用鎖的原因可能有兩個：為了效率或正确性。怎麼區分這兩種原因呢？你可以問自己如果擷取鎖失敗會發生什麼：
- 效率：擷取鎖可以避免不必要地做兩次相同的工作（例如一些昂貴的計算）。如果加鎖失敗并且兩個節點最終完成相同的工作，可能會導緻成本略有增加（比如你最終向 AWS 支付的費用比其他情況多 5 美分）或帶來輕微的不便（例如，使用者最終兩次收到相同的電子郵件通知）。
- 正确性：使用鎖可以防止并發程序互相幹擾并破壞系統狀态。如果加鎖失敗導緻兩個節點同時處理同一條資料，後果可能是檔案損壞、資料丢失、永久性不一緻，或者發生給患者服用的藥物劑量錯誤或其他一些更嚴重的問題。
以上兩者都是需要使用鎖的原因，但你需要非常清楚自己正在處理兩者中的哪一個。
如果你僅出于效率目的使用鎖，則沒有必要承擔 Redlock 的成本和複雜性，運作 5 個 Redis 伺服器并檢查大多數以獲得你的鎖。你最好隻使用單個 Redis 執行個體，也許可以異步複制到副本執行個體，以防主執行個體崩潰。
假如你使用單個Redis執行個體，在你的Redis節點突然斷電，或者出現其他問題時，你的鎖也會出現一些問題。但如果你出于效率優化的目而使用鎖，并且Redis節點崩潰不會經常發生，那其實也沒什麼大不了。這種“沒什麼大不了”的場景正是 Redis的用武之地。至少，如果你隻依賴單個 Redis 執行個體，那麼管理系統的每個人都清楚這把鎖是近似的，并且僅用于非關鍵路徑和用途。
另一方面，具有 5 個副本和多數投票的 Redlock 算法乍一看似乎适用于對鎖的正确性有嚴格要求的情況。但往往事與願違，對于本文的其餘部分，我們将假設你使用分布式鎖是為了保證正确性，那麼如果兩個不同的節點同時認為它們持有相同的鎖，這将是一個嚴重的錯誤。
3.用鎖保護資源
讓我們暫時先把 Redlock 的細節放在一邊，然後讨論一下分布式鎖的一般的使用方式（獨立于所使用的特定鎖算法）。重要的是要記住，分布式系統中的鎖不像多線程應用程式中的互斥鎖。這是一個更複雜的設計，因為不同節點和網絡都可能以各種方式自主失敗。
例如，假設你有一個應用程式，其中用戶端需要更新共享存儲（例如 HDFS 或 S3）中的檔案。用戶端首先擷取鎖，然後讀取檔案并進行一些更改，接着将修改後的檔案回寫，最後釋放鎖。該鎖可防止兩個用戶端同時執行此讀取->修改->寫入同一個檔案，這會導緻更新丢失。代碼可能如下：
1// THIS CODE IS BROKEN
2function writeData(filename, data) {
3 var lock = lockService.acquireLock(filename);
4 if (!lock) {
5 throw 'Failed to acquire lock';
6 }
7
8 try {
9 var file = storage.readFile(filename);
10 var updated = updateContents(file, data);
11 storage.writeFile(filename, updated);
12 } finally {
13 lock.release();
14 }
15} 不幸的是，即使你有完美的鎖服務，上面的代碼也會被破壞。下圖顯示了資料如何被損壞：
在這個例子中，擷取鎖的用戶端在持有鎖後暫停了很長一段時間——例如因為垃圾收集器（GC）的啟動。鎖有一個逾時（即它是一個租約），這是個很好的設計（否則崩潰的用戶端最終可能會永遠持有鎖并且永遠不會釋放它）。但是，如果 GC 暫停持續時間超過租用到期時間，并且用戶端沒有意識到自己持有的鎖已經過期，它可能會繼續進行一些不安全的更改。
這個錯誤就曾經發生過：HBase 曾經有這個問題[5]。通常情況下，GC 暫停時間很短，但“stop-the-world”的GC暫停有時會持續幾分鐘 ——當然足以讓租約到期。即使是所謂的“并發”垃圾收集器，如 HotSpot JVM 的 CMS，也不能完全與應用程式代碼并行運作——因為它們有時也需要"stop-the-world"。
你無法通過在寫回存儲之前插入對鎖定到期的檢查來解決此問題。請記住，GC 可以在任何時間暫停正在運作的線程，包括你最不願意發生的時間點（在最後一次檢查和寫入操作之間）。
雖然你自己使用的程式設計語言可能沒有長時間的 GC，但你的程序還是可能會因許多其他原因而暫停。比如也許你的程序試圖讀取尚未加載到記憶體中的位址，它會導緻缺頁錯誤并暫停，直到從磁盤加載該頁面。也許你的磁盤使用的是 EBS，是以在讀取一個變量時可能不知不覺中變成了 Amazon 擁塞網絡上的同步網絡請求。也許還有許多其他程序在争奪 CPU，而你在排程程式樹中遇到了一個黑色節點[6]。也許有人不小心向程序發送了 SIGSTOP等，這些都會導緻程序暫停。
如果你仍然不相信程序會暫停，那麼請考慮檔案寫入請求在到達存儲伺服器之前可能會因為網絡堵塞而延遲。以太網和 IP 等資料包網絡可能會使資料包出現任意延遲，它們确實如此：在 GitHub 的一個著名事件中，資料包在網絡中延遲了大約 90 秒。這意味着一個應用程序可能會發送一個寫請求，當租約已經到期時，它可能會在一分鐘後才到達存儲伺服器。
即使在管理良好的網絡中，這種事情也可能發生。你根本無法對時間做出任何假設，是以無論你使用哪種鎖服務，上面的代碼都是不安全的。
RedLock算法的價值在于它引入了多數派思想(paxos分布式一緻性算法)，來解決單點故障對資料安全性和服務可用性的影響。但它嚴重依賴系統時鐘和合适的租約時間設定也注定它不可能用于對強正确性有要求的場景。
4.使用fencing讓鎖安全
修複上面的問題其實非常簡單：對存儲服務的每個寫請求中都帶一個防護令牌。在這種情況下，防護令牌隻需要是一個數字，每次用戶端擷取鎖時它都會遞增（例如，由鎖服務遞增）。如下圖所示：
用戶端1獲得租約和值為33的令牌，但随後進入長時間暫停，租約到期。用戶端 2 擷取租約，得到值為34 的令牌（數字總是遞增），然後将内容和值為34的令牌都寫入到存儲服務。稍後，用戶端1恢複正常後，将寫入請求：内容和值為33的令牌 發送到存儲服務。但是，存儲伺服器記住它已經處理了具有更高數值令牌号 (34) 的寫入，是以它拒絕帶有令牌 33 的請求。
請注意，這需要存儲伺服器采取主動角色檢查令牌，并拒絕較小值令牌的任何寫操作。但這并不是特别難，一旦你知道了訣竅。并且如果鎖服務生成嚴格單調遞增的令牌，這使得鎖是安全的。例如，如果你使用 ZooKeeper 作為鎖定服務，你可以使用 zxid 或 znode 版本号作為防護令牌，并且你處于良好狀态。
然而，這将我們引向了 Redlock 的第一個大問題：它沒有任何用于生成單調遞增的令牌的工具。該算法不能保證每次用戶端擷取鎖時都會拿到遞增的數字。這意味着即使算法在其他方面是完美的，使用它也不安全，因為在一個用戶端程序暫停或有資料包延遲的情況下，你無法防止其他用戶端此時去競争那把鎖。
對我來說，如何更改 Redlock 算法以開始生成防護令牌并不明顯。它使用的唯一随機值不提供所需的單調性。僅僅在一個 Redis 節點上保留一個計數器是不夠的，因為該節點可能會挂掉。在多個節點上保留計數器意味着它們的資料會出現不同步或同步不及時。你可能需要一個共識算法來生成fencing tokens。（如果隻是增加一個計數器是簡單的）
5.用時間解決共識
在想使用鎖保證正确性的情況下不應該使用Redlock，因為Redlock無法生成 fencing 令牌。但還有一些更進一步的問題值得讨論。
在學術文獻中，這種算法最實用的系統模型是帶有不可靠故障檢測器的異步模型[7]。簡單來說，這意味着算法不對時間做任何假設：程序可能會暫停任意長度的時間，資料包可能會在網絡中任意延遲，時鐘可能會任意錯誤——盡管如此，算法都會做正确的事物。鑒于我們上面讨論的内容，這些都是非常合理的假設。
Redlock算法使用時鐘的唯一目的是産生逾時，以避免在節點關閉時永遠等待。但是逾時不一定準确：僅僅因為請求逾時，并不意味着另一個節點已關閉 – 也可能是網絡中存在很大延遲，或者你的本地時鐘是錯的。當用作故障檢測器時，逾時隻是猜測出了問題。（如果可以的話，分布式算法将完全沒有時鐘，但這樣就不可能達成共識[8]，擷取鎖就像一個比較和設定操作，需要達成共識[9]。）
請注意，Redis 使用gettimeofday[10]，而不是單調時鐘[11]，以确定密鑰的到期時間[12]。gettimeofday 的手冊頁明确指出[13]它傳回的時間會受到系統時間不連續跳躍的影響——也就是說，它可能會突然向前跳躍幾分鐘，甚至時間跳躍（例如，如果時鐘被NTP步進[14]，因為它與 NTP 伺服器差别太大，或者如果時鐘由管理者手動調整）。是以，如果系統時鐘正在做一些奇怪的事情，很容易發生 Redis 中某個鍵的到期比預期快得多或慢得多的情況。
對于異步模型中的算法，這不是一個大問題：這些算法通常會在不基于時間做出假設[15]的前提下保證它們的安全屬性始終不變。隻有活性屬性取決于逾時或其他一些故障檢測器。通俗地說，這意味着即使計時在系統中到處都是（程序暫停，網絡延遲，時鐘向前和向後跳躍），導緻算法的性能可能會下降，但算法永遠不會做出錯誤的決定。
然而，Redlock不是這樣的。它的安全性取決于很多時間假設：
- 它假設所有 Redis 節點在過期前都持有合适的時間長度
- 網絡延遲比過期時間短得多
- 程序暫停時間比過期時間短得多
6.基于時間假設的Redlock不可靠
讓我們看一些例子來證明 Redlock 對時間假設的依賴。假設系統有五個 Redis 節點（A、B、C、D 、 E）和兩個用戶端（1 和 2）。如果其中一個 Redis 節點上的時鐘向前跳躍會發生什麼？
- 用戶端 1 擷取節點 A、B、C 上的鎖。由于網絡問題，無法通路 D 和 E。
- 節點 C 上的時鐘向前跳躍，導緻鎖到期。
- 用戶端 2 擷取節點 C、D、E 上的鎖。由于網絡問題，無法通路 A 和 B。
- 用戶端 1 和 2 現在都相信他們持有鎖。
如果 C 在将鎖定持久化到磁盤之前崩潰并立即重新啟動，則可能會發生類似的問題。出于這個原因，Redlock 文檔建議至少将崩潰節點的重新開機延遲[16]到鎖的最長存活時間。但是這種重新啟動延遲再次依賴于合理準确的時間測量，但在發生時鐘跳躍時也會導緻失敗。
可能你認為發生時鐘跳躍不現實，因為你對正确配置 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 現在都相信他們持有鎖。
請注意，即使 Redis 是用 C 編寫的，是以沒有 GC，但這對我們沒有幫助：任何用戶端可能遇到GC暫停的系統都有這個問題。你隻能通過在用戶端 2 擷取鎖後阻止用戶端 1 在鎖下執行任何操作來確定安全，例如使用上面的防護方法。
較長的網絡延遲會産生與程序暫停相同的效果。這可能取決于你的 TCP 使用者逾時——如果你使逾時明顯短于 Redis TTL，則可能會忽略延遲的網絡資料包，但我們必須詳細檢視 TCP 實作才能确定。此外，随着逾時，我們再次回到時間測量的準确性！
7.Redlock的同步假設
這些例子表明，Redlock 隻有在你假設一個同步系統模型時才能正确工作——也就是說，一個系統具有以下屬性：
- 有邊界時間的網絡延遲（必須保證資料包總是在某個最大延遲時刻内到達）
- 有邊界時間的程序暫停（必須保證程序最長暫停時間小于設定的逾時時間，即：hard real-time constraints[17]，通常你隻能在汽車安全氣囊系統中才能找到）
- 有限的時鐘誤差（難以避免從壞的NTP伺服器[18]擷取時間）
請注意，同步模型并不意味着時鐘是完全同步的時鐘：這意味着你假設網絡延遲、暫停和時鐘漂移有一個已知的、固定的上限[19]。Redlock 算法假設延遲、暫停和漂移相對于鎖的逾時時間來說都很小；但如果時序問題變得與逾時時間一樣大，算法就會失敗。
在運作良好的資料中心環境中，大部分時間都會滿足時序假設——這被稱為部分同步系統 。但這還不夠，因為一旦這些時間假設被打破，Redlock 可能會違反其安全屬性，例如在另一個用戶端到期之前向一個用戶端授予租約。如果你依賴你的鎖來保證正确性，“大部分時間”是不夠的——因為你需要它一直在正确運作。
有大量證據表明，假設大多數系統環境符合同步系統模型是種危險行為。我不斷提醒自己 GitHub 的事故--90 秒資料包延遲[20] (90-second packet delay)。是以Redlock 不太可能在Jepsen[21]測試中幸存下來。
如果你想保證系統的正确性和強一直性，那你要利用好Raft、Viewstamped Replication、Zab 和 Paxos 這些為部分同步系統模型（或帶有故障檢測器的異步模型）設計的共識算法。共識算法必須放棄所有關于時序的假設。雖然假設網絡、程序、時鐘比實際情況更可靠是很誘人的，但在混亂複雜的分布式系統中，你必須非常小心你的假設條件。
8. 結論
我認為 Redlock 算法是一個糟糕的選擇：對于效率優化來說實作太複雜、成本昂貴的，對于想保證正确性的場景來說它又不夠安全。
特别是，該算法對時序和系統時鐘做出了危險的假設（基本上假設同步系統具有有限的網絡延遲和有限的操作執行時間），如果不滿足這些假設，則會違反安全屬性。此外，它缺乏用于生成隔離令牌的設施（保護系統免受網絡長時間延遲或暫停程序的影響）。
如果使用鎖是出于效率優化的目的且可以容忍一定程度的不正确性，我建議堅持使用簡單的 Redis單節點鎖定算法[22]（條件設定如果不存在以獲得鎖， atomic delete-if-value-matches 以釋放鎖），并在你的代碼中非常清楚地記錄鎖隻是近似值，有時可能會失敗。不要費心設定五個 Redis 節點的叢集。
另一方面，如果你需要鎖定以確定正确性，請不要使用 Redlock。相反，請使用适當的共識系統，例如 ZooKeeper，可能通過實作鎖定的 Curator recipes[23]之一。（至少，使用具有合理事務保證的資料庫[24]。）并且請在鎖定下的所有資源通路中強制使用防護令牌。
正如我在開頭所說的，如果正确使用Redis，它是一個很好的工具。以上都不會降低 Redis 對其預期用途的實用性。 Salvatore[25]多年來一直緻力于該項目，其成功當之無愧。但是每個工具都有局限性，了解它們并相應地進行計劃很重要。
9.References
[1]原文：https://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html
[2] RedLock算法及實作：https://redis.io/topics/distlock
[3]租約論文：https://www.semanticscholar.org/paper/Leases%3A-an-efficient-fault-tolerant-mechanism-for-Gray-Cheriton/8965057405c1de742346eba16f20eaca2612f576?p2df
[4] https://aphyr.com/tags/Redis
[5]https://www.slideshare.net/enissoz/hbase-and-hdfs-understanding-filesystem-usage
[6] http://43.128.13.41/?p=188
[7] http://courses.csail.mit.edu/6.852/08/papers/CT96-JACM.pdf
[8] https://www.cs.princeton.edu/courses/archive/fall07/cos518/papers/flp.pdf
[9] https://cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf
[10]https://github.com/redis/redis/blob/edd4d555df57dc84265fdfb4ef59a4678832f6da/src/server.c#L390-L404
[11] https://linux.die.net/man/2/clock_gettime
[12]https://github.com/redis/redis/blob/f0b168e8944af41c4161249040f01ece227cfc0c/src/db.c#L933-L959
[13] https://linux.die.net/man/2/gettimeofday
[14] https://www.eecis.udel.edu/~mills/ntp/html/clock.html
[15] http://www.net.t-labs.tu-berlin.de/~petr/ADC-07/papers/DLS88.pdf
[16] https://redis.io/topics/distlock#performance-crash-recovery-and-fsync
[17]https://stackoverflow.com/questions/17308956/differences-between-hard-real-time-soft-real-time-and-firm-real-time
[18] http://xenia.media.mit.edu/~nelson/research/ntp-survey99/
[19] http://www.net.t-labs.tu-berlin.de/~petr/ADC-07/papers/DLS88.pdf
[20] https://github.com/blog/1364-downtime-last-saturday
[21] https://aphyr.com/tags/jepsen
[22] https://redis.io/commands/set