網上有關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為了釋放鎖，先執行'get'操作擷取随機字元串的值。
用戶端1判斷随機字元串的值，與預期的值相等。
用戶端1由于某個原因阻塞住了很長時間。
用戶端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認為自己成功擷取到了鎖。
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