52
基於Redis的分布式鎖真的安全嗎？（上）
網上有關Redis分布式鎖的文章可謂多如牛毛了，不信的話你可以拿關鍵詞“Redis 分布式鎖”隨便到哪個搜索引擎上去搜索一下就知道了。這些文章的思路大體相近，給出的實現算法也看似合乎邏輯，但當我們著手去實現它們的時候，卻發現如果你越是仔細推敲，疑慮也就越來越多。
實際上，大概在一年以前，關於Redis分布式鎖的安全性問題，在分布式係統專家Martin Kleppmann和Redis的作者antirez之間就發生過一場爭論。由於對這個問題一直以來比較關注，所以我前些日子仔細閱讀了與這場爭論相關的資料。
這場爭論的大概過程是這樣的：
為了規範各家對基於Redis的分布式鎖的實現，Redis的作者提出了一個更安全的實現，叫做Redlock。有一天，Martin Kleppmann寫了一篇blog，分析了Redlock在安全性上存在的一些問題。然後Redis的作者立即寫了一篇blog來反駁Martin的分析。但Martin表示仍然堅持原來的觀點。隨後，這個問題在Twitter和Hacker News上引發了激烈的討論，很多分布式係統的專家都參與其中。
對於那些對分布式係統感興趣的人來說，這個事件非常值得關注。不管你是剛接觸分布式係統的新手，還是有著多年分布式開發經驗的老手，讀完這些分析和評論之後，大概都會有所收獲。要知道，親手實現過Redis Cluster這樣一個複雜係統的antirez，足以算得上分布式領域的一名專家了。但對於由分布式鎖引發的一係列問題的分析中，不同的專家卻能得出迥異的結論，從中我們可以窺見分布式係統相關的問題具有何等的複雜性。實際上，在分布式係統的設計中經常發生的事情是：許多想法初看起來毫無破綻，而一旦詳加考量，卻發現不是那麼天衣無縫。
下麵，我們就從頭至尾把這場爭論過程中各方的觀點進行一下回顧和分析。在這個過程中，我們把影響分布式鎖的安全性的那些技術細節展開進行討論，這將是一件很有意思的事情。這也是一個比較長的故事。當然，其中也免不了包含一些小“八卦”。
Redlock算法
就像本文開頭所講的，借助Redis來實現一個分布式鎖(Distributed Lock)的做法，已經有很多人嚐試過。人們構建這樣的分布式鎖的目的，是為了對一些共享資源進行互斥訪問。
但是，這些實現雖然思路大體相近，但實現細節上各不相同，它們能提供的安全性和可用性也不盡相同。所以，Redis的作者antirez給出了一個更好的實現，稱為Redlock，算是Redis官方對於實現分布式鎖的指導規範。Redlock的算法描述就放在Redis的官網上：
https://redis.io/topics/distlock
在Redlock之前，很多人對於分布式鎖的實現都是基於單個Redis節點的。而Redlock是基於多個Redis節點（都是Master）的一種實現。為了能理解Redlock，我們首先需要把簡單的基於單Redis節點的算法描述清楚，因為它是Redlock的基礎。
基於單Redis節點的分布式鎖
首先，Redis客戶端為了獲取鎖，向Redis節點發送如下命令：
SET resource_name my_random_value NX PX 30000
上麵的命令如果執行成功，則客戶端成功獲取到了鎖，接下來就可以訪問共享資源了；而如果上麵的命令執行失敗，則說明獲取鎖失敗。
注意，在上麵的SET命令中：
-
my_random_value是由客戶端生成的一個隨機字符串，它要保證在足夠長的一段時間內在所有客戶端的所有獲取鎖的請求中都是唯一的。
-
NX表示隻有當resource_name對應的key值不存在的時候才能SET成功。這保證了隻有第一個請求的客戶端才能獲得鎖，而其它客戶端在鎖被釋放之前都無法獲得鎖。
-
PX 30000表示這個鎖有一個30秒的自動過期時間。當然，這裏30秒隻是一個例子，客戶端可以選擇合適的過期時間。
最後，當客戶端完成了對共享資源的操作之後，執行下麵的Redis Lua腳本來釋放鎖：
if redis.call("get",KEYS[1]) == ARGV[1] then
return redis.call("del",KEYS[1])
else
return 0
end
這段Lua腳本在執行的時候要把前麵的my_random_value作為ARGV[1]的值傳進去，把resource_name作為KEYS[1]的值傳進去。
至此，基於單Redis節點的分布式鎖的算法就描述完了。這裏麵有好幾個問題需要重點分析一下。
首先第一個問題，這個鎖必須要設置一個過期時間。否則的話，當一個客戶端獲取鎖成功之後，假如它崩潰了，或者由於發生了網絡分割（network partition）導致它再也無法和Redis節點通信了，那麼它就會一直持有這個鎖，而其它客戶端永遠無法獲得鎖了。antirez在後麵的分析中也特別強調了這一點，而且把這個過期時間稱為鎖的有效時間(lock validity time)。獲得鎖的客戶端必須在這個時間之內完成對共享資源的訪問。
第二個問題，第一步獲取鎖的操作，網上不少文章把它實現成了兩個Redis命令：
SETNX resource_name my_random_value
EXPIRE resource_name 30
雖然這兩個命令和前麵算法描述中的一個SET命令執行效果相同，但卻不是原子的。如果客戶端在執行完SETNX後崩潰了，那麼就沒有機會執行EXPIRE了，導致它一直持有這個鎖。
第三個問題，也是antirez指出的，設置一個隨機字符串my_random_value是很有必要的，它保證了一個客戶端釋放的鎖必須是自己持有的那個鎖。假如獲取鎖時SET的不是一個隨機字符串，而是一個固定值，那麼可能會發生下麵的執行序列：
-
客戶端1獲取鎖成功。
-
客戶端1在某個操作上阻塞了很長時間。
-
過期時間到了，鎖自動釋放了。
-
客戶端2獲取到了對應同一個資源的鎖。
-
客戶端1從阻塞中恢複過來，釋放掉了客戶端2持有的鎖。
之後，客戶端2在訪問共享資源的時候，就沒有鎖為它提供保護了。
第四個問題，釋放鎖的操作必須使用Lua腳本來實現。釋放鎖其實包含三步操作：'GET'、判斷和'DEL'，用Lua腳本來實現能保證這三步的原子性。否則，如果把這三步操作放到客戶端邏輯中去執行的話，就有可能發生與前麵第三個問題類似的執行序列：
-
客戶端1獲取鎖成功。
-
客戶端1訪問共享資源。
-
客戶端1為了釋放鎖，先執行'GET'操作獲取隨機字符串的值。
-
客戶端1判斷隨機字符串的值，與預期的值相等。
-
客戶端1由於某個原因阻塞住了很長時間。
-
過期時間到了，鎖自動釋放了。
-
客戶端2獲取到了對應同一個資源的鎖。
-
客戶端1從阻塞中恢複過來，執行DEL操縱，釋放掉了客戶端2持有的鎖。
實際上，在上述第三個問題和第四個問題的分析中，如果不是客戶端阻塞住了，而是出現了大的網絡延遲，也有可能導致類似的執行序列發生。
前麵的四個問題，隻要實現分布式鎖的時候加以注意，就都能夠被正確處理。但除此之外，antirez還指出了一個問題，是由failover引起的，卻是基於單Redis節點的分布式鎖無法解決的。正是這個問題催生了Redlock的出現。
這個問題是這樣的。假如Redis節點宕機了，那麼所有客戶端就都無法獲得鎖了，服務變得不可用。為了提高可用性，我們可以給這個Redis節點掛一個Slave，當Master節點不可用的時候，係統自動切到Slave上（failover）。但由於Redis的主從複製（replication）是異步的，這可能導致在failover過程中喪失鎖的安全性。考慮下麵的執行序列：
-
客戶端1從Master獲取了鎖。
-
Master宕機了，存儲鎖的key還沒有來得及同步到Slave上。
-
Slave升級為Master。
-
客戶端2從新的Master獲取到了對應同一個資源的鎖。
於是，客戶端1和客戶端2同時持有了同一個資源的鎖。鎖的安全性被打破。針對這個問題，antirez設計了Redlock算法，我們接下來會討論。
【其它疑問】
前麵這個算法中出現的鎖的有效時間(lock validity time)，設置成多少合適呢？如果設置太短的話，鎖就有可能在客戶端完成對於共享資源的訪問之前過期，從而失去保護；如果設置太長的話，一旦某個持有鎖的客戶端釋放鎖失敗，那麼就會導致所有其它客戶端都無法獲取鎖，從而長時間內無法正常工作。看來真是個兩難的問題。
而且，在前麵對於隨機字符串my_random_value的分析中，antirez也在文章中承認的確應該考慮客戶端長期阻塞導致鎖過期的情況。如果真的發生了這種情況，那麼共享資源是不是已經失去了保護呢？antirez重新設計的Redlock是否能解決這些問題呢？
分布式鎖Redlock
由於前麵介紹的基於單Redis節點的分布式鎖在failover的時候會產生解決不了的安全性問題，因此antirez提出了新的分布式鎖的算法Redlock，它基於N個完全獨立的Redis節點（通常情況下N可以設置成5）。
運行Redlock算法的客戶端依次執行下麵各個步驟，來完成獲取鎖的操作：
-
獲取當前時間（毫秒數）。
-
按順序依次向N個Redis節點執行獲取鎖的操作。這個獲取操作跟前麵基於單Redis節點的獲取鎖的過程相同，包含隨機字符串my_random_value，也包含過期時間(比如PX 30000，即鎖的有效時間)。為了保證在某個Redis節點不可用的時候算法能夠繼續運行，這個獲取鎖的操作還有一個超時時間(time out)，它要遠小於鎖的有效時間（幾十毫秒量級）。客戶端在向某個Redis節點獲取鎖失敗以後，應該立即嚐試下一個Redis節點。這裏的失敗，應該包含任何類型的失敗，比如該Redis節點不可用，或者該Redis節點上的鎖已經被其它客戶端持有（注：Redlock原文中這裏隻提到了Redis節點不可用的情況，但也應該包含其它的失敗情況）。
-
計算整個獲取鎖的過程總共消耗了多長時間，計算方法是用當前時間減去第1步記錄的時間。如果客戶端從大多數Redis節點（>= N/2+1）成功獲取到了鎖，並且獲取鎖總共消耗的時間沒有超過鎖的有效時間(lock validity time)，那麼這時客戶端才認為最終獲取鎖成功；否則，認為最終獲取鎖失敗。
-
如果最終獲取鎖成功了，那麼這個鎖的有效時間應該重新計算，它等於最初的鎖的有效時間減去第3步計算出來的獲取鎖消耗的時間。
-
如果最終獲取鎖失敗了（可能由於獲取到鎖的Redis節點個數少於N/2+1，或者整個獲取鎖的過程消耗的時間超過了鎖的最初有效時間），那麼客戶端應該立即向所有Redis節點發起釋放鎖的操作（即前麵介紹的Redis Lua腳本）。
當然，上麵描述的隻是獲取鎖的過程，而釋放鎖的過程比較簡單：客戶端向所有Redis節點發起釋放鎖的操作，不管這些節點當時在獲取鎖的時候成功與否。
由於N個Redis節點中的大多數能正常工作就能保證Redlock正常工作，因此理論上它的可用性更高。我們前麵討論的單Redis節點的分布式鎖在failover的時候鎖失效的問題，在Redlock中不存在了，但如果有節點發生崩潰重啟，還是會對鎖的安全性有影響的。具體的影響程度跟Redis對數據的持久化程度有關。
假設一共有5個Redis節點：A, B, C, D, E。設想發生了如下的事件序列：
-
客戶端1成功鎖住了A, B, C，獲取鎖成功（但D和E沒有鎖住）。
-
節點C崩潰重啟了，但客戶端1在C上加的鎖沒有持久化下來，丟失了。
-
節點C重啟後，客戶端2鎖住了C, D, E，獲取鎖成功。
這樣，客戶端1和客戶端2同時獲得了鎖（針對同一資源）。
在默認情況下，Redis的AOF持久化方式是每秒寫一次磁盤（即執行fsync），因此最壞情況下可能丟失1秒的數據。為了盡可能不丟數據，Redis允許設置成每次修改數據都進行fsync，但這會降低性能。當然，即使執行了fsync也仍然有可能丟失數據（這取決於係統而不是Redis的實現）。所以，上麵分析的由於節點重啟引發的鎖失效問題，總是有可能出現的。為了應對這一問題，antirez又提出了延遲重啟(delayed restarts)的概念。也就是說，一個節點崩潰後，先不立即重啟它，而是等待一段時間再重啟，這段時間應該大於鎖的有效時間(lock validity time)。這樣的話，這個節點在重啟前所參與的鎖都會過期，它在重啟後就不會對現有的鎖造成影響。
關於Redlock還有一點細節值得拿出來分析一下：
在最後釋放鎖的時候，antirez在算法描述中特別強調，客戶端應該向所有Redis節點發起釋放鎖的操作。也就是說，即使當時向某個節點獲取鎖沒有成功，在釋放鎖的時候也不應該漏掉這個節點。
這是為什麼呢？設想這樣一種情況，客戶端發給某個Redis節點的獲取鎖的請求成功到達了該Redis節點，這個節點也成功執行了SET操作，但是它返回給客戶端的響應包卻丟失了。這在客戶端看來，獲取鎖的請求由於超時而失敗了，但在Redis這邊看來，加鎖已經成功了。因此，釋放鎖的時候，客戶端也應該對當時獲取鎖失敗的那些Redis節點同樣發起請求。實際上，這種情況在異步通信模型中是有可能發生的：客戶端向服務器通信是正常的，但反方向卻是有問題的。
【其它疑問】
前麵在討論單Redis節點的分布式鎖的時候，最後我們提出了一個疑問，如果客戶端長期阻塞導致鎖過期，那麼它接下來訪問共享資源就不安全了（沒有了鎖的保護）。這個問題在Redlock中是否有所改善呢？顯然，這樣的問題在Redlock中是依然存在的。
另外，在算法第4步成功獲取了鎖之後，如果由於獲取鎖的過程消耗了較長時間，重新計算出來的剩餘的鎖有效時間很短了，那麼我們還來得及去完成共享資源訪問嗎？如果我們認為太短，是不是應該立即進行鎖的釋放操作？那到底多短才算呢？又是一個選擇難題。
Martin的分析
Martin Kleppmann在2016-02-08這一天發表了一篇blog，名字叫"How to do distributed locking"，地址如下：
https://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html
Martin在這篇文章中談及了分布式係統的很多基礎性的問題（特別是分布式計算的異步模型），對分布式係統的從業者來說非常值得一讀。這篇文章大體可以分為兩大部分：
-
前半部分，與Redlock無關。Martin指出，即使我們擁有一個完美實現的分布式鎖（帶自動過期功能），在沒有共享資源參與進來提供某種fencing機製的前提下，我們仍然不可能獲得足夠的安全性。
-
後半部分，是對Redlock本身的批評。Martin指出，由於Redlock本質上是建立在一個同步模型之上，對係統的記時假設(timing assumption)有很強的要求，因此本身的安全性是不夠的。
首先我們討論一下前半部分的關鍵點。Martin給出了下麵這樣一份時序圖：
在上麵的時序圖中，假設鎖服務本身是沒有問題的，它總是能保證任一時刻最多隻有一個客戶端獲得鎖。上圖中出現的lease這個詞可以暫且認為就等同於一個帶有自動過期功能的鎖。客戶端1在獲得鎖之後發生了很長時間的GC pause，在此期間，它獲得的鎖過期了，而客戶端2獲得了鎖。當客戶端1從GC pause中恢複過來的時候，它不知道自己持有的鎖已經過期了，它依然向共享資源（上圖中是一個存儲服務）發起了寫數據請求，而這時鎖實際上被客戶端2持有，因此兩個客戶端的寫請求就有可能衝突（鎖的互斥作用失效了）。
初看上去，有人可能會說，既然客戶端1從GC pause中恢複過來以後不知道自己持有的鎖已經過期了，那麼它可以在訪問共享資源之前先判斷一下鎖是否過期。但仔細想想，這絲毫也沒有幫助。因為GC pause可能發生在任意時刻，也許恰好在判斷完之後。
也有人會說，如果客戶端使用沒有GC的語言來實現，是不是就沒有這個問題呢？Martin指出，係統環境太複雜，仍然有很多原因導致進程的pause，比如虛存造成的缺頁故障(page fault)，再比如CPU資源的競爭。即使不考慮進程pause的情況，網絡延遲也仍然會造成類似的結果。
總結起來就是說，即使鎖服務本身是沒有問題的，而僅僅是客戶端有長時間的pause或網絡延遲，仍然會造成兩個客戶端同時訪問共享資源的衝突情況發生。而這種情況其實就是我們在前麵已經提出來的“客戶端長期阻塞導致鎖過期”的那個疑問。
那怎麼解決這個問題呢？Martin給出了一種方法，稱為fencing token。fencing token是一個單調遞增的數字，當客戶端成功獲取鎖的時候它隨同鎖一起返回給客戶端。而客戶端訪問共享資源的時候帶著這個fencing token，這樣提供共享資源的服務就能根據它進行檢查，拒絕掉延遲到來的訪問請求（避免了衝突）。如下圖：
在上圖中，客戶端1先獲取到的鎖，因此有一個較小的fencing token，等於33，而客戶端2後獲取到的鎖，有一個較大的fencing token，等於34。客戶端1從GC pause中恢複過來之後，依然是向存儲服務發送訪問請求，但是帶了fencing token = 33。存儲服務發現它之前已經處理過34的請求，所以會拒絕掉這次33的請求。這樣就避免了衝突。
現在我們再討論一下Martin的文章的後半部分。
Martin在文中構造了一些事件序列，能夠讓Redlock失效（兩個客戶端同時持有鎖）。為了說明Redlock對係統記時(timing)的過分依賴，他首先給出了下麵的一個例子（還是假設有5個Redis節點A, B, C, D, E）：
-
客戶端1從Redis節點A, B, C成功獲取了鎖（多數節點）。由於網絡問題，與D和E通信失敗。
-
節點C上的時鍾發生了向前跳躍，導致它上麵維護的鎖快速過期。
-
客戶端2從Redis節點C, D, E成功獲取了同一個資源的鎖（多數節點）。
-
客戶端1和客戶端2現在都認為自己持有了鎖。
上麵這種情況之所以有可能發生，本質上是因為Redlock的安全性(safety property)對係統的時鍾有比較強的依賴，一旦係統的時鍾變得不準確，算法的安全性也就保證不了了。Martin在這裏其實是要指出分布式算法研究中的一些基礎性問題，或者說一些常識問題，即好的分布式算法應該基於異步模型(asynchronous model)，算法的安全性不應該依賴於任何記時假設(timing assumption)。在異步模型中：進程可能pause任意長的時間，消息可能在網絡中延遲任意長的時間，甚至丟失，係統時鍾也可能以任意方式出錯。一個好的分布式算法，這些因素不應該影響它的安全性(safety property)，隻可能影響到它的活性(liveness property)，也就是說，即使在非常極端的情況下（比如係統時鍾嚴重錯誤），算法頂多是不能在有限的時間內給出結果而已，而不應該給出錯誤的結果。這樣的算法在現實中是存在的，像比較著名的Paxos，或Raft。但顯然按這個標準的話，Redlock的安全性級別是達不到的。
隨後，Martin覺得前麵這個時鍾跳躍的例子還不夠，又給出了一個由客戶端GC pause引發Redlock失效的例子。如下：
-
客戶端1向Redis節點A, B, C, D, E發起鎖請求。
-
各個Redis節點已經把請求結果返回給了客戶端1，但客戶端1在收到請求結果之前進入了長時間的GC pause。
-
在所有的Redis節點上，鎖過期了。
-
客戶端2在A, B, C, D, E上獲取到了鎖。
-
客戶端1從GC pause從恢複，收到了前麵第2步來自各個Redis節點的請求結果。客戶端1認為自己成功獲取到了鎖。
-
客戶端1和客戶端2現在都認為自己持有了鎖。
Martin給出的這個例子其實有點小問題。在Redlock算法中，客戶端在完成向各個Redis節點的獲取鎖的請求之後，會計算這個過程消耗的時間，然後檢查是不是超過了鎖的有效時間(lock validity time)。也就是上麵的例子中第5步，客戶端1從GC pause中恢複過來以後，它會通過這個檢查發現鎖已經過期了，不會再認為自己成功獲取到鎖了。隨後antirez在他的反駁文章中就指出來了這個問題，但Martin認為這個細節對Redlock整體的安全性沒有本質的影響。
拋開這個細節，我們可以分析一下Martin舉這個例子的意圖在哪。初看起來，這個例子跟文章前半部分分析通用的分布式鎖時給出的GC pause的時序圖是基本一樣的，隻不過那裏的GC pause發生在客戶端1獲得了鎖之後，而這裏的GC pause發生在客戶端1獲得鎖之前。但兩個例子的側重點不太一樣。Martin構造這裏的這個例子，是為了強調在一個分布式的異步環境下，長時間的GC pause或消息延遲（上麵這個例子中，把GC pause換成Redis節點和客戶端1之間的消息延遲，邏輯不變），會讓客戶端獲得一個已經過期的鎖。從客戶端1的角度看，Redlock的安全性被打破了，因為客戶端1收到鎖的時候，這個鎖已經失效了，而Redlock同時還把這個鎖分配給了客戶端2。
換句話說，Redis服務器在把鎖分發給客戶端的途中，鎖就過期了，但又沒有有效的機製讓客戶端明確知道這個問題。而在之前的那個例子中，客戶端1收到鎖的時候鎖還是有效的，鎖服務本身的安全性可以認為沒有被打破，後麵雖然也出了問題，但問題是出在客戶端1和共享資源服務器之間的交互上。
在Martin的這篇文章中，還有一個很有見地的觀點，就是對鎖的用途的區分。他把鎖的用途分為兩種：
-
為了效率(efficiency)，協調各個客戶端避免做重複的工作。即使鎖偶爾失效了，隻是可能把某些操作多做一遍而已，不會產生其它的不良後果。比如重複發送了一封同樣的email。
-
為了正確性(correctness)。在任何情況下都不允許鎖失效的情況發生，因為一旦發生，就可能意味著數據不一致(inconsistency)，數據丟失，文件損壞，或者其它嚴重的問題。
最後，Martin得出了如下的結論：
-
如果是為了效率(efficiency)而使用分布式鎖，允許鎖的偶爾失效，那麼使用單Redis節點的鎖方案就足夠了，簡單而且效率高。Redlock則是個過重的實現(heavyweight)。
-
如果是為了正確性(correctness)在很嚴肅的場合使用分布式鎖，那麼不要使用Redlock。它不是建立在異步模型上的一個足夠強的算法，它對於係統模型的假設中包含很多危險的成分(對於timing)。而且，它沒有一個機製能夠提供fencing token。那應該使用什麼技術呢？Martin認為，應該考慮類似Zookeeper的方案，或者支持事務的數據庫。
Martin對Redlock算法的形容是：
neither fish nor fowl （非驢非馬）
【其它疑問】
-
Martin提出的fencing token的方案，需要對提供共享資源的服務進行修改，這在現實中可行嗎？
-
根據Martin的說法，看起來，如果資源服務器實現了fencing token，它在分布式鎖失效的情況下也仍然能保持資源的互斥訪問。這是不是意味著分布式鎖根本沒有存在的意義了？
-
資源服務器需要檢查fencing token的大小，如果提供資源訪問的服務也是包含多個節點的（分布式的），那麼這裏怎麼檢查才能保證fencing token在多個節點上是遞增的呢？
-
Martin對於fencing token的舉例中，兩個fencing token到達資源服務器的順序顛倒了（小的fencing token後到了），這時資源服務器檢查出了這一問題。如果客戶端1和客戶端2都發生了GC pause，兩個fencing token都延遲了，它們幾乎同時達到了資源服務器，但保持了順序，那麼資源服務器是不是就檢查不出問題了？這時對於資源的訪問是不是就發生衝突了？
-
分布式鎖+fencing的方案是絕對正確的嗎？能證明嗎？
-
原文發布時間為：2017-03-10
本文來自雲棲社區合作夥伴DBAplus
最後更新：2017-05-16 10:31:40