449
《Redis官方文檔》用Redis構建分布式鎖
用Redis構建分布式鎖
在不同進程需要互斥地訪問共享資源時，分布式鎖是一種非常有用的技術手段。 有很多三方庫和文章描述如何用Redis實現一個分布式鎖管理器，但是這些庫實現的方式差別很大，而且很多簡單的實現其實隻需采用稍微增加一點複雜的設計就可以獲得更好的可靠性。 這篇文章的目的就是嚐試提出一種官方權威的用Redis實現分布式鎖管理器的算法，我們把這個算法稱為RedLock，我們相信這個算法會比一般的普通方法更加安全可靠。我們也希望社區能一起分析這個算法，提供一些反饋，然後我們以此為基礎，來設計出更加複雜可靠的算法，或者更好的新算法。
實現
在描述具體的算法之前，下麵是已經實現了的項目可以作為參考： Redlock-rb (Ruby實現)。還有一個Redlock-rb的分支，添加了一些特性使得實現分布式鎖更簡單
- Redlock-py (Python 實現).
- Redlock-php (PHP 實現).
- PHPRedisMutex (PHP 更完整的實現)
- Redsync.go (Go 實現).
- Redisson (Java 實現).
- Redis::DistLock (Perl 實現).
- Redlock-cpp (C++ 實現).
- Redlock-cs (C#/.NET 實現).
- node-redlock (NodeJS 實現). Includes support for lock extension.
安全和可靠性保證
在描述我們的設計之前，我們想先提出三個屬性，這三個屬性在我們看來，是實現高效分布式鎖的基礎。
- 安全屬性：互斥，不管任何時候，隻有一個客戶端能持有同一個鎖。
- 效率屬性A：不會死鎖，最終一定會得到鎖，就算一個持有鎖的客戶端宕掉或者發生網絡分區。
- 效率屬性B：容錯，隻要大多數Redis節點正常工作，客戶端應該都能獲取和釋放鎖。
為什麼基於故障切換的方案不夠好
為了理解我們想要提高的到底是什麼，我們先看下當前大多數基於Redis的分布式鎖三方庫的現狀。 用Redis來實現分布式鎖最簡單的方式就是在實例裏創建一個鍵值，創建出來的鍵值一般都是有一個超時時間的（這個是Redis自帶的超時特性），所以每個鎖最終都會釋放（參見前文屬性2）。而當一個客戶端想要釋放鎖時，它隻需要刪除這個鍵值即可。 表麵來看，這個方法似乎很管用，但是這裏存在一個問題：在我們的係統架構裏存在一個單點故障，如果Redis的master節點宕機了怎麼辦呢？有人可能會說：加一個slave節點！在master宕機時用slave就行了！但是其實這個方案明顯是不可行的，因為這種方案無法保證第1個安全互斥屬性，因為Redis的複製是異步的。 總的來說，這個方案裏有一個明顯的競爭條件（race condition），舉例來說：
- 客戶端A在master節點拿到了鎖。
- master節點在把A創建的key寫入slave之前宕機了。
- slave變成了master節點 4.B也得到了和A還持有的相同的鎖（因為原來的slave裏還沒有A持有鎖的信息）
當然，在某些特殊場景下，前麵提到的這個方案則完全沒有問題，比如在宕機期間，多個客戶端允許同時都持有鎖，如果你可以容忍這個問題的話，那用這個基於複製的方案就完全沒有問題，否則的話我們還是建議你采用這篇文章裏接下來要描述的方案。
采用單實例的正確實現
在講述如何用其他方案突破單實例方案的限製之前，讓我們先看下是否有什麼辦法可以修複這個簡單場景的問題，因為這個方案其實如果可以忍受競爭條件的話是有望可行的，而且單實例來實現分布式鎖是我們後麵要講的算法的基礎。 要獲得鎖，要用下麵這個命令： SET resource_name my_random_value NX PX 30000 這個命令的作用是在隻有這個key不存在的時候才會設置這個key的值（NX選項的作用），超時時間設為30000毫秒（PX選項的作用） 這個key的值設為“my_random_value”。這個值必須在所有獲取鎖請求的客戶端裏保持唯一。 基本上這個隨機值就是用來保證能安全地釋放鎖，我們可以用下麵這個Lua腳本來告訴Redis：刪除這個key當且僅當這個key存在而且值是我期望的那個值。
if redis.call("get",KEYS[1]) == ARGV[1] then
return redis.call("del",KEYS[1])
else
return 0
end
這個很重要，因為這可以避免誤刪其他客戶端得到的鎖，舉個例子，一個客戶端拿到了鎖，被某個操作阻塞了很長時間，過了超時時間後自動釋放了這個鎖，然後這個客戶端之後又嚐試刪除這個其實已經被其他客戶端拿到的鎖。所以單純的用DEL指令有可能造成一個客戶端刪除了其他客戶端的鎖，用上麵這個腳本可以保證每個客戶單都用一個隨機字符串’簽名’了，這樣每個鎖就隻能被獲得鎖的客戶端刪除了。
這個隨機字符串應該用什麼生成呢？我假設這是從/dev/urandom生成的20字節大小的字符串，但是其實你可以有效率更高的方案來保證這個字符串足夠唯一。比如你可以用RC4加密算法來從/dev/urandom生成一個偽隨機流。還有更簡單的方案，比如用毫秒的unix時間戳加上客戶端id，這個也許不夠安全，但是也許在大多數環境下已經夠用了。
key值的超時時間，也叫做”鎖有效時間”。這個是鎖的自動釋放時間，也是一個客戶端在其他客戶端能搶占鎖之前可以執行任務的時間，這個時間從獲取鎖的時間點開始計算。 所以現在我們有很好的獲取和釋放鎖的方式，在一個非分布式的、單點的、保證永不宕機的環境下這個方式沒有任何問題，接下來我們看看無法保證這些條件的分布式環境下我們該怎麼做。
Redlock算法
在分布式版本的算法裏我們假設我們有N個Redis master節點，這些節點都是完全獨立的，我們不用任何複製或者其他隱含的分布式協調算法。我們已經描述了如何在單節點環境下安全地獲取和釋放鎖。因此我們理所當然地應當用這個方法在每個單節點裏來獲取和釋放鎖。在我們的例子裏麵我們把N設成5，這個數字是一個相對比較合理的數值，因此我們需要在不同的計算機或者虛擬機上運行5個master節點來保證他們大多數情況下都不會同時宕機。一個客戶端需要做如下操作來獲取鎖：
1.獲取當前時間（單位是毫秒）。
2.輪流用相同的key和隨機值在N個節點上請求鎖，在這一步裏，客戶端在每個master上請求鎖時，會有一個和總的鎖釋放時間相比小的多的超時時間。比如如果鎖自動釋放時間是10秒鍾，那每個節點鎖請求的超時時間可能是5-50毫秒的範圍，這個可以防止一個客戶端在某個宕掉的master節點上阻塞過長時間，如果一個master節點不可用了，我們應該盡快嚐試下一個master節點。
3.客戶端計算第二步中獲取鎖所花的時間，隻有當客戶端在大多數master節點上成功獲取了鎖（在這裏是3個），而且總共消耗的時間不超過鎖釋放時間，這個鎖就認為是獲取成功了。
4.如果鎖獲取成功了，那現在鎖自動釋放時間就是最初的鎖釋放時間減去之前獲取鎖所消耗的時間。
5.如果鎖獲取失敗了，不管是因為獲取成功的鎖不超過一半（N/2+1)還是因為總消耗時間超過了鎖釋放時間，客戶端都會到每個master節點上釋放鎖，即便是那些他認為沒有獲取成功的鎖。
這個算法是否是異步的？
這個算法是基於一個假設：雖然不存在可以跨進程的同步時鍾，但是不同進程時間都是以差不多相同的速度前進，這個假設不一定完全準確，但是和自動釋放鎖的時間長度相比不同進程時間前進速度差異基本是可以忽略不計的。這個假設就好比真實世界裏的計算機：每個計算機都有本地時鍾，但是我們可以說大部分情況下不同計算機之間的時間差是很小的。 現在我們需要更細化我們的鎖互斥規則，隻有當客戶端能在T時間內完成所做的工作才能保證鎖是有效的（詳見算法的第3步），T的計算規則是鎖失效時間T1減去一個用來補償不同進程間時鍾差異的delta值（一般隻有幾毫秒而已） 如果想了解更多基於有限時鍾差異的類似係統，可以參考這篇有趣的文章：《Leases: an efficient fault-tolerant mechanism for distributed file cache consistency.》
失敗的重試
當一個客戶端獲取鎖失敗時，這個客戶端應該在一個隨機延時後進行重試，之所以采用隨機延時是為了避免不同客戶端同時重試導致誰都無法拿到鎖的情況出現。同樣的道理客戶端越快嚐試在大多數Redis節點獲取鎖，出現多個客戶端同時競爭鎖和重試的時間窗口越小，可能性就越低，所以最完美的情況下，客戶端應該用多路傳輸的方式同時向所有Redis節點發送SET命令。 這裏非常有必要強調一下客戶端如果沒有在多數節點獲取到鎖，一定要盡快在獲取鎖成功的節點上釋放鎖，這樣就沒必要等到key超時後才能重新獲取這個鎖（但是如果網絡分區的情況發生而且客戶端無法連接到Redis節點時，會損失等待key超時這段時間的係統可用性）
釋放鎖
釋放鎖比較簡單，因為隻需要在所有節點都釋放鎖就行，不管之前有沒有在該節點獲取鎖成功。
安全性的論證
這個算法到底是不是安全的呢？我們可以觀察不同場景下的情況來理解這個算法為什麼是安全的。 開始之前，讓我們假設客戶端可以在大多數節點都獲取到鎖，這樣所有的節點都會包含一個有相同存活時間的key。但是需要注意的是，這個key是在不同時間點設置的，所以這些key也會在不同的時間超時，但是我們假設最壞情況下第一個key是在T1時間設置的（客戶端連接到第一個服務器時的時間），最後一個key是在T2時間設置的（客戶端收到最後一個服務器返回結果的時間），從T2時間開始，我們可以確認最早超時的key至少也會存在的時間為MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT，TTL是鎖超時時間、（T2-T1）是最晚獲取到的鎖的耗時，CLOCK_DRIFT是不同進程間時鍾差異，這個是用來補償前麵的(T2-T1）。其他的key都會在這個時間點之後才會超時，所以我們可以確定這些key在這個時間點之前至少都是同時存在的。
在大多數節點的key都set了的時間段內，其他客戶端無法搶占這個鎖，因為在N/2+1個客戶端的key已經存在的情況下不可能再在N/2+1個客戶端上獲取鎖成功，所以如果一個鎖獲取成功了，就不可能同時重新獲取這個鎖成功（不然就違反了分布式鎖互斥原則），然後我們也要確保多個客戶端同時嚐試獲取鎖時不會都同時成功。 如果一個客戶端獲取大多數節點鎖的耗時接近甚至超過鎖的最大有效時間時（就是我們為SET操作設置的TTL值），那麼係統會認為這個鎖是無效的同時會釋放這些節點上的鎖，所以我們僅僅需要考慮獲取大多數節點鎖的耗時小於有效時間的情況。在這種情況下，根據我們前麵的證明，在MIN_VALIDITY時間內，沒有客戶端能重新獲取鎖成功，所以多個客戶端都能同時成功獲取鎖的結果，隻會發生在多數節點獲取鎖的時間都大大超過TTL時間的情況下，實際上這種情況下這些鎖都會失效 。 我們非常期待和歡迎有人能提供這個算法安全性的公式化證明，或者發現任何bug。
性能論證
這個係統的性能主要基於以下三個主要特征：
1.鎖自動釋放的特征（超時後會自動釋放），一定時間後某個鎖都能被再次獲取。
2.客戶端通常會在不再需要鎖或者任務執行完成之後主動釋放鎖，這樣我們就不用等到超時時間會再去獲取這個鎖。
3.當一個客戶端需要重試獲取鎖時，這個客戶端會等待一段時間，等待的時間相對來說會比我們重新獲取大多數鎖的時間要長一些，這樣可以降低不同客戶端競爭鎖資源時發生死鎖的概率。
然而，我們在網絡分區時要損失TTL的可用性時間，所以如果網絡分區持續發生，這個不可用會一直持續。這種情況在每次一個客戶端獲取到了鎖並在釋放鎖之前被網絡分區了時都會出現。
基本來說，如果持續的網絡分區發生的話，係統也會在持續不可用。
性能、故障恢複和fsync
很多使用Redis做鎖服務器的用戶在獲取鎖和釋放鎖時不止要求低延時，同時要求高吞吐量，也即單位時間內可以獲取和釋放的鎖數量。為了達到這個要求，一定會使用多路傳輸來和N個服務器進行通信以降低延時（或者也可以用假多路傳輸，也就是把socket設置成非阻塞模式，發送所有命令，然後再去讀取返回的命令，假設說客戶端和不同Redis服務節點的網絡往返延時相差不大的話）。
然後如果我們想讓係統可以自動故障恢複的話，我們還需要考慮一下信息持久化的問題。
為了更好的描述問題，我們先假設我們Redis都是配置成非持久化的，某個客戶端拿到了總共5個節點中的3個鎖，這三個已經獲取到鎖的節點中隨後重啟了，這樣一來我們又有3個節點可以獲取鎖了（重啟的那個加上另外兩個），這樣一來其他客戶端又可以獲得這個鎖了，這樣就違反了我們之前說的鎖互斥原則了。
如果我們啟用AOF持久化功能，情況會好很多。舉例來說，我們可以發送SHUTDOWN命令來升級一個Redis服務器然後重啟之，因為Redis超時時效是語義層麵實現的，所以在服務器關掉期間時超時時間還是算在內的，我們所有要求還是滿足了的。然後這個是基於我們做的是一次正常的shutdown，但是如果是斷電這種意外停機呢？如果Redis是默認地配置成每秒在磁盤上執行一次fsync同步文件到磁盤操作，那就可能在一次重啟後我們鎖的key就丟失了。理論上如果我們想要在所有服務重啟的情況下都確保鎖的安全性，我們需要在持久化設置裏設置成永遠執行fsync操作，但是這個反過來又會造成性能遠不如其他同級別的傳統用來實現分布式鎖的係統。 然後問題其實並不像我們第一眼看起來那麼糟糕，基本上隻要一個服務節點在宕機重啟後不去參與現在所有仍在使用的鎖，這樣正在使用的鎖集合在這個服務節點重啟時，算法的安全性就可以維持，因為這樣就可以保證正在使用的鎖都被所有沒重啟的節點持有。 為了滿足這個條件，我們隻要讓一個宕機重啟後的實例，至少在我們使用的最大TTL時間內處於不可用狀態，超過這個時間之後，所有在這期間活躍的鎖都會自動釋放掉。 使用延時重啟的策略基本上可以在不適用任何Redis持久化特性情況下保證安全性，然後要注意這個也必然會影響到係統的可用性。舉個例子，如果係統裏大多數節點都宕機了，那在TTL時間內整個係統都處於全局不可用狀態（全局不可用的意思就是在獲取不到任何鎖）。
擴展鎖來使得算法更可靠
如果客戶端做的工作都是由一些小的步驟組成，那麼就有可能使用更小的默認鎖有效時間，而且擴展這個算法來實現一個鎖擴展機製。基本上，客戶端如果在執行計算期間發現鎖快要超時了，客戶端可以給所有服務實例發送一個Lua腳本讓服務端延長鎖的時間，隻要這個鎖的key還存在而且值還等於客戶端獲取時的那個值。 客戶端應當隻有在失效時間內無法延長鎖時再去重新獲取鎖（基本上這個和獲取鎖的算法是差不多的） 然而這個並不會對從本質上改變這個算法，所以最大的重新獲取鎖數量應該被設置成合理的大小，不然性能必然會受到影響。
想提供幫助？
如果你很了解分布式係統的話，我們非常歡迎你提供一些意見和分析。當然如果能引用其他語言的實現話就更棒了。 謝謝！
最後更新：2017-05-22 09:31:59