摘要：集群實現分布式鎖上面的討論中我們有一個非常重要的假設是單點的。但是其實這已經超出了實現分布式鎖的范圍，單純用沒有命令來實現生成。這個問題用實現分布式鎖暫時無解。結論并不能實現嚴格意義上的分布式鎖。

關于Redis實現分布式鎖的問題，網絡上很多，但是很多人的討論基本就是把原來博主的貼過來，甚至很多面試官也是一知半解經不起推敲就來面候選人，最近結合我自己的學習和資料查閱，整理一下用Redis實現分布式鎖的方法，歡迎評論、交流、討論。

獲取鎖的過程很簡單，客戶端向Redis發送命令：

SET resource_name my_random_value NX PX 30000

my_random_value是由客戶端生成的一個隨機字符串，它要保證在足夠長的一段時間內在所有客戶端的所有獲取鎖的請求中都是唯一的。
NX表示只有當resource_name對應的key值不存在的時候才能SET成功。這保證了只有第一個請求的客戶端才能獲得鎖，而其它客戶端在鎖被釋放之前都無法獲得鎖。
PX 30000表示這個鎖有一個30秒的自動過期時間。

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

之前獲取鎖的時候生成的my_random_value 作為參數傳到Lua腳本里面，作為：ARGV[1],而 resource_name作為KEYS[1]。Lua腳本可以保證操作的原子性。

網絡上有文章說用如下命令獲取鎖:

SETNX resource_name my_random_value
EXPIRE resource_name 30

由于這兩個命令不是原子的。如果客戶端在執行完SETNX后crash了，那么就沒有機會執行EXPIRE了，導致它一直持有這個鎖，其他的客戶端就永遠獲取不到這個鎖了。

為什么my_random_value 要設置成隨機值?

保證了一個客戶端釋放的鎖是自己持有的那個鎖。如若不然，可能出現鎖不安全的情況。

客戶端1獲取鎖成功。
客戶端1在某個操作上阻塞了很長時間。
過期時間到了，鎖自動釋放了。
客戶端2獲取到了對應同一個資源的鎖。
客戶端1從阻塞中恢復過來，釋放掉了客戶端2持有的鎖。

用 SETNX獲取鎖

網上大量文章說用如下命令獲取鎖：

SETNX lock.foo 

原文在Redis對SETNX的官網說明，Redis官網文檔建議用Set命令來代替，主要原因是SETNX不支持超時時間的設置。

https://redis.io/commands/setnx

上面的討論中我們有一個非常重要的假設：Redis是單點的。如果Redis是集群模式，我們考慮如下場景:

客戶端1從Master獲取了鎖。
Master宕機了，存儲鎖的key還沒有來得及同步到Slave上。
Slave升級為Master。
客戶端2從新的Master獲取到了對應同一個資源的鎖。
客戶端1和客戶端2同時持有了同一個資源的鎖，鎖不再具有安全性。

就此問題，Redis作者antirez寫了RedLock算法來解決這種問題。

獲取當前時間。

按順序依次向N個Redis節點執行獲取鎖的操作。這個獲取操作跟前面基于單Redis節點的獲取鎖的過程相同，包含隨機字符串my_random_value，也包含過期時間(比如PX 30000，即鎖的有效時間)。為了保證在某個Redis節點不可用的時候算法能夠繼續運行，這個獲取鎖的操作還有一個超時時間(time out)，它要遠小于鎖的有效時間（幾十毫秒量級）。客戶端在向某個Redis節點獲取鎖失敗以后，應該立即嘗試下一個Redis節點。

計算整個獲取鎖的過程總共消耗了多長時間，計算方法是用當前時間減去第1步記錄的時間。如果客戶端從大多數Redis節點（>= N/2+1）成功獲取到了鎖，并且獲取鎖總共消耗的時間沒有超過鎖的有效時間(lock validity time)，那么這時客戶端才認為最終獲取鎖成功；否則，認為最終獲取鎖失敗。

如果最終獲取鎖成功了，那么這個鎖的有效時間應該重新計算，它等于最初的鎖的有效時間減去第3步計算出來的獲取鎖消耗的時間。

如果最終獲取鎖失敗了（可能由于獲取到鎖的Redis節點個數少于N/2+1，或者整個獲取鎖的過程消耗的時間超過了鎖的最初有效時間），那么客戶端應該立即向所有Redis節點發起釋放鎖的操作（即前面介紹的單機Redis Lua腳本釋放鎖的方法）。

客戶端向所有Redis節點發起釋放鎖的操作，不管這些節點當時在獲取鎖的時候成功與否。

如果有節點發生崩潰重啟

假設一共有5個Redis節點：A, B, C, D, E。設想發生了如下的事件序列：

客戶端1成功鎖住了A, B, C，獲取鎖成功（但D和E沒有鎖住）。
節點C崩潰重啟了，但客戶端1在C上加的鎖沒有持久化下來，丟失了。
節點C重啟后，客戶端2鎖住了C, D, E，獲取鎖成功。
客戶端1和客戶端2同時獲得了鎖。

為了應對這一問題，antirez又提出了延遲重啟(delayed restarts)的概念。也就是說，一個節點崩潰后，先不立即重啟它，而是等待一段時間再重啟，這段時間應該大于鎖的有效時間(lock validity time)。這樣的話，這個節點在重啟前所參與的鎖都會過期，它在重啟后就不會對現有的鎖造成影響。

如果客戶端長期阻塞導致鎖過期

解釋一下這個時序圖，客戶端1在獲得鎖之后發生了很長時間的GC pause，在此期間，它獲得的鎖過期了，而客戶端2獲得了鎖。當客戶端1從GC pause中恢復過來的時候，它不知道自己持有的鎖已經過期了，它依然向共享資源（上圖中是一個存儲服務）發起了寫數據請求，而這時鎖實際上被客戶端2持有，因此兩個客戶端的寫請求就有可能沖突（鎖的互斥作用失效了）。

如何解決這個問題呢?引入了fencing token的概念：

客戶端1先獲取到的鎖，因此有一個較小的fencing token，等于33，而客戶端2后獲取到的鎖，有一個較大的fencing token，等于34。客戶端1從GC pause中恢復過來之后，依然是向存儲服務發送訪問請求，但是帶了fencing token = 33。存儲服務發現它之前已經處理過34的請求，所以會拒絕掉這次33的請求。這樣就避免了沖突。

但是其實這已經超出了Redis實現分布式鎖的范圍，單純用Redis沒有命令來實現生成Token。

時鐘跳躍問題

假設有5個Redis節點A, B, C, D, E。

客戶端1從Redis節點A, B, C成功獲取了鎖（多數節點）。由于網絡問題，與D和E通信失敗。
節點C上的時鐘發生了向前跳躍，導致它上面維護的鎖快速過期。
客戶端2從Redis節點C, D, E成功獲取了同一個資源的鎖（多數節點）。
客戶端1和客戶端2現在都認為自己持有了鎖。
這個問題用Redis實現分布式鎖暫時無解。而生產環境這種情況是存在的。

結論
Redis并不能實現嚴格意義上的分布式鎖。但是這并不意味著上面討論的方案一無是處。如果你的應用場景為了效率(efficiency)，協調各個客戶端避免做重復的工作，即使鎖失效了，只是可能把某些操作多做一遍而已，不會產生其它的不良后果。但是如果你的應用場景是為了正確性(correctness)，那么用Redis實現分布式鎖并不合適，會存在各種各樣的問題，且解決起來就很復雜，為了正確性，需要使用zab、raft共識算法，或者使用帶有事務的數據庫來實現嚴格意義上的分布式鎖。

參考資料
Distributed locks with Redis
基于Redis的分布式鎖到底安全嗎（上）？ - 鐵蕾的個人博客
https://martin.kleppmann.com/...

技術文章匯總

【Leetcode】101. 對稱二叉樹

【Leetcode】100. 相同的樹

【Leetcode】98. 驗證二叉搜索樹