Redis分散式鎖之Redlock演算法，那些你可能不知道的秘密！
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
2
function
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/20
16/02/08/how-to-do-distributed-locking。html
［2］ RedLock演算法及實現：
https：//
redis。io/topics/distloc
k
［3］租約論文：
https：//www。
semanticscholar。org/pap
er/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/course
s/archive/fall07/cos518/papers/flp。pdf
［9］
https：//
cs。brown。edu/~mph/Herli
hy91/p124-herlihy。pdf
［10］
https：//
github。com/redis/redis/
blob/edd4d555df57dc84265fdfb4ef59a4678832f6da/src/server。c#L390-L404
［11］
https：//
linux。die。net/man/2/clo
ck_gettime
［12］
https：//
github。com/redis/redis/
blob/f0b168e8944af41c4161249040f01ece227cfc0c/src/db。c#L933-L959
［13］
https：//
linux。die。net/man/2/get
timeofday
［14］
https：//www。
eecis。udel。edu/~mills/n
tp/html/clock。html
［15］
http：//www。
net。t-labs。tu-berlin。de
/~petr/ADC-07/papers/DLS88。pdf
［16］
https：//
redis。io/topics/distloc
k#performance-crash-recovery-and-fsync
［17］
https：//
stackoverflow。com/quest
ions/17308956/differences-between-hard-real-time-soft-real-time-and-firm-real-time
［18］
http：//
xenia。media。mit。edu/~ne
lson/research/ntp-survey99/
［19］
http：//www。
net。t-labs。tu-berlin。de
/~petr/ADC-07/papers/DLS88。pdf
［20］
https：//
github。com/blog/1364-do
wntime-last-saturday
［21］
https：//
aphyr。com/tags/jepsen
［22］
https：//
redis。io/commands/set
［23］
https：//
curator。apache。org/cura
tor-recipes/index。html
［24］
https：//www。
postgresql。org/
［25］
http：//
antirez。com/latest/0
