轉(zhuǎn)自：http://ifeve.com/redis-lock/
英文原文：https://github.com/antirez/redis-doc/blob/master/topics/distlock.md
用Redis構(gòu)建分布式鎖
在不同進程需要互斥地訪問共享資源時丑瞧，分布式鎖是一種非常有用的技術(shù)手段至会。 有很多三方庫和文章描述如何用Redis實現(xiàn)一個分布式鎖管理器，但是這些庫實現(xiàn)的方式差別很大恳啥，而且很多簡單的實現(xiàn)其實只需采用稍微增加一點復雜的設計就可以獲得更好的可靠性喷面。 這篇文章的目的就是嘗試提出一種官方權(quán)威的用Redis實現(xiàn)分布式鎖管理器的算法星瘾，我們把這個算法稱為RedLock，我們相信這個算法會比一般的普通方法更加安全可靠惧辈。我們也希望社區(qū)能一起分析這個算法琳状，提供一些反饋，然后我們以此為基礎盒齿，來設計出更加復雜可靠的算法念逞，或者更好的新算法。
實現(xiàn)
在描述具體的算法之前边翁，下面是已經(jīng)實現(xiàn)了的項目可以作為參考：
- Redlock-rb (Ruby實現(xiàn))翎承。還有一個Redlock-rb的分支，添加了一些特性使得實現(xiàn)分布式鎖更簡單
- Redlock-py (Python 實現(xiàn)).
- Redlock-php (PHP 實現(xiàn)).
- PHPRedisMutex (PHP 更完整的實現(xiàn))
- Redsync.go (Go 實現(xiàn)).
- Redisson (Java 實現(xiàn)).
- Redis::DistLock (Perl 實現(xiàn)).
- Redlock-cpp (C++ 實現(xiàn)).
- Redlock-cs (C#/.NET 實現(xiàn)).
- node-redlock (NodeJS 實現(xiàn)). Includes support for lock extension.
安全和可靠性保證
在描述我們的設計之前符匾，我們想先提出三個屬性叨咖，這三個屬性在我們看來，是實現(xiàn)高效分布式鎖的基礎啊胶。
- 安全屬性：互斥甸各，不管任何時候，只有一個客戶端能持有同一個鎖焰坪。
- 效率屬性A：不會死鎖趣倾，最終一定會得到鎖，就算一個持有鎖的客戶端宕掉或者發(fā)生網(wǎng)絡分區(qū)琳彩。
- 效率屬性B：容錯誊酌，只要大多數(shù)Redis節(jié)點正常工作，客戶端應該都能獲取和釋放鎖露乏。
為什么基于故障切換的方案不夠好
為了理解我們想要提高的到底是什么碧浊，我們先看下當前大多數(shù)基于Redis的分布式鎖三方庫的現(xiàn)狀。 用Redis來實現(xiàn)分布式鎖最簡單的方式就是在實例里創(chuàng)建一個鍵值瘟仿，創(chuàng)建出來的鍵值一般都是有一個超時時間的（這個是Redis自帶的超時特性）箱锐，所以每個鎖最終都會釋放（參見前文屬性2）。而當一個客戶端想要釋放鎖時劳较，它只需要刪除這個鍵值即可驹止。 表面來看浩聋，這個方法似乎很管用，但是這里存在一個問題：在我們的系統(tǒng)架構(gòu)里存在一個單點故障臊恋，如果Redis的master節(jié)點宕機了怎么辦呢衣洁？有人可能會說：加一個slave節(jié)點！在master宕機時用slave就行了抖仅！但是其實這個方案明顯是不可行的坊夫，因為這種方案無法保證第1個安全互斥屬性，因為Redis的復制是異步的撤卢。 總的來說环凿，這個方案里有一個明顯的競爭條件（race condition），舉例來說：
- 客戶端A在master節(jié)點拿到了鎖放吩。
- master節(jié)點在把A創(chuàng)建的key寫入slave之前宕機了智听。
- slave變成了master節(jié)點 4.B也得到了和A還持有的相同的鎖（因為原來的slave里還沒有A持有鎖的信息）
當然，在某些特殊場景下渡紫，前面提到的這個方案則完全沒有問題到推，比如在宕機期間，多個客戶端允許同時都持有鎖腻惠，如果你可以容忍這個問題的話环肘，那用這個基于復制的方案就完全沒有問題欲虚，否則的話我們還是建議你采用這篇文章里接下來要描述的方案集灌。
采用單實例的正確實現(xiàn)
在講述如何用其他方案突破單實例方案的限制之前，讓我們先看下是否有什么辦法可以修復這個簡單場景的問題复哆，因為這個方案其實如果可以忍受競爭條件的話是有望可行的欣喧，而且單實例來實現(xiàn)分布式鎖是我們后面要講的算法的基礎。 要獲得鎖梯找，要用下面這個命令： 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
這個很重要久免，因為這可以避免誤刪其他客戶端得到的鎖浅辙，舉個例子，一個客戶端拿到了鎖阎姥，被某個操作阻塞了很長時間记舆，過了超時時間后自動釋放了這個鎖，然后這個客戶端之后又嘗試刪除這個其實已經(jīng)被其他客戶端拿到的鎖呼巴。所以單純的用DEL指令有可能造成一個客戶端刪除了其他客戶端的鎖泽腮，用上面這個腳本可以保證每個客戶單都用一個隨機字符串’簽名’了御蒲，這樣每個鎖就只能被獲得鎖的客戶端刪除了。
這個隨機字符串應該用什么生成呢诊赊？我假設這是從/dev/urandom生成的20字節(jié)大小的字符串厚满，但是其實你可以有效率更高的方案來保證這個字符串足夠唯一。比如你可以用RC4加密算法來從/dev/urandom生成一個偽隨機流碧磅。還有更簡單的方案痰滋，比如用毫秒的unix時間戳加上客戶端id，這個也許不夠安全续崖，但是也許在大多數(shù)環(huán)境下已經(jīng)夠用了敲街。
key值的超時時間，也叫做”鎖有效時間”严望。這個是鎖的自動釋放時間多艇，也是一個客戶端在其他客戶端能搶占鎖之前可以執(zhí)行任務的時間，這個時間從獲取鎖的時間點開始計算像吻。 所以現(xiàn)在我們有很好的獲取和釋放鎖的方式峻黍，在一個非分布式的、單點的拨匆、保證永不宕機的環(huán)境下這個方式?jīng)]有任何問題姆涩，接下來我們看看無法保證這些條件的分布式環(huán)境下我們該怎么做。
Redlock算法
在分布式版本的算法里我們假設我們有N個Redis master節(jié)點惭每，這些節(jié)點都是完全獨立的骨饿，我們不用任何復制或者其他隱含的分布式協(xié)調(diào)算法。我們已經(jīng)描述了如何在單節(jié)點環(huán)境下安全地獲取和釋放鎖台腥。因此我們理所當然地應當用這個方法在每個單節(jié)點里來獲取和釋放鎖宏赘。在我們的例子里面我們把N設成5，這個數(shù)字是一個相對比較合理的數(shù)值黎侈，因此我們需要在不同的計算機或者虛擬機上運行5個master節(jié)點來保證他們大多數(shù)情況下都不會同時宕機察署。一個客戶端需要做如下操作來獲取鎖：
1.獲取當前時間（單位是毫秒）。
2.輪流用相同的key和隨機值在N個節(jié)點上請求鎖峻汉，在這一步里贴汪，客戶端在每個master上請求鎖時，會有一個和總的鎖釋放時間相比小的多的超時時間休吠。比如如果鎖自動釋放時間是10秒鐘扳埂，那每個節(jié)點鎖請求的超時時間可能是5-50毫秒的范圍，這個可以防止一個客戶端在某個宕掉的master節(jié)點上阻塞過長時間蛛碌，如果一個master節(jié)點不可用了聂喇，我們應該盡快嘗試下一個master節(jié)點。
3.客戶端計算第二步中獲取鎖所花的時間，只有當客戶端在大多數(shù)master節(jié)點上成功獲取了鎖（在這里是3個）希太，而且總共消耗的時間不超過鎖釋放時間克饶，這個鎖就認為是獲取成功了。
4.如果鎖獲取成功了誊辉，那現(xiàn)在鎖自動釋放時間就是最初的鎖釋放時間減去之前獲取鎖所消耗的時間矾湃。
5.如果鎖獲取失敗了，不管是因為獲取成功的鎖不超過一半（N/2+1)還是因為總消耗時間超過了鎖釋放時間堕澄，客戶端都會到每個master節(jié)點上釋放鎖邀跃，即便是那些他認為沒有獲取成功的鎖。
這個算法是否是異步的蛙紫？
這個算法是基于一個假設：雖然不存在可以跨進程的同步時鐘拍屑，但是不同進程時間都是以差不多相同的速度前進，這個假設不一定完全準確坑傅，但是和自動釋放鎖的時間長度相比不同進程時間前進速度差異基本是可以忽略不計的僵驰。這個假設就好比真實世界里的計算機：每個計算機都有本地時鐘，但是我們可以說大部分情況下不同計算機之間的時間差是很小的唁毒。 現(xiàn)在我們需要更細化我們的鎖互斥規(guī)則蒜茴，只有當客戶端能在T時間內(nèi)完成所做的工作才能保證鎖是有效的（詳見算法的第3步），T的計算規(guī)則是鎖失效時間T1減去一個用來補償不同進程間時鐘差異的delta值（一般只有幾毫秒而已） 如果想了解更多基于有限時鐘差異的類似系統(tǒng)浆西，可以參考這篇有趣的文章：《Leases: an efficient fault-tolerant mechanism for distributed file cache consistency.》
失敗的重試
當一個客戶端獲取鎖失敗時粉私，這個客戶端應該在一個隨機延時后進行重試，之所以采用隨機延時是為了避免不同客戶端同時重試導致誰都無法拿到鎖的情況出現(xiàn)近零。同樣的道理客戶端越快嘗試在大多數(shù)Redis節(jié)點獲取鎖诺核，出現(xiàn)多個客戶端同時競爭鎖和重試的時間窗口越小，可能性就越低秒赤，所以最完美的情況下猪瞬，客戶端應該用多路傳輸?shù)姆绞酵瑫r向所有Redis節(jié)點發(fā)送SET命令憎瘸。 這里非常有必要強調(diào)一下客戶端如果沒有在多數(shù)節(jié)點獲取到鎖入篮，一定要盡快在獲取鎖成功的節(jié)點上釋放鎖，這樣就沒必要等到key超時后才能重新獲取這個鎖（但是如果網(wǎng)絡分區(qū)的情況發(fā)生而且客戶端無法連接到Redis節(jié)點時幌甘，會損失等待key超時這段時間的系統(tǒng)可用性）
釋放鎖
釋放鎖比較簡單潮售，因為只需要在所有節(jié)點都釋放鎖就行，不管之前有沒有在該節(jié)點獲取鎖成功锅风。
安全性的論證
這個算法到底是不是安全的呢酥诽？我們可以觀察不同場景下的情況來理解這個算法為什么是安全的。 開始之前皱埠，讓我們假設客戶端可以在大多數(shù)節(jié)點都獲取到鎖肮帐，這樣所有的節(jié)點都會包含一個有相同存活時間的key。但是需要注意的是，這個key是在不同時間點設置的训枢，所以這些key也會在不同的時間超時托修，但是我們假設最壞情況下第一個key是在T1時間設置的（客戶端連接到第一個服務器時的時間），最后一個key是在T2時間設置的（客戶端收到最后一個服務器返回結(jié)果的時間）恒界，從T2時間開始睦刃，我們可以確認最早超時的key至少也會存在的時間為MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT，TTL是鎖超時時間十酣、（T2-T1）是最晚獲取到的鎖的耗時涩拙，CLOCK_DRIFT是不同進程間時鐘差異，這個是用來補償前面的(T2-T1）耸采。其他的key都會在這個時間點之后才會超時兴泥，所以我們可以確定這些key在這個時間點之前至少都是同時存在的。
在大多數(shù)節(jié)點的key都set了的時間段內(nèi)虾宇，其他客戶端無法搶占這個鎖郁轻，因為在N/2+1個客戶端的key已經(jīng)存在的情況下不可能再在N/2+1個客戶端上獲取鎖成功，所以如果一個鎖獲取成功了文留，就不可能同時重新獲取這個鎖成功（不然就違反了分布式鎖互斥原則）好唯，然后我們也要確保多個客戶端同時嘗試獲取鎖時不會都同時成功。 如果一個客戶端獲取大多數(shù)節(jié)點鎖的耗時接近甚至超過鎖的最大有效時間時（就是我們?yōu)镾ET操作設置的TTL值）燥翅，那么系統(tǒng)會認為這個鎖是無效的同時會釋放這些節(jié)點上的鎖骑篙，所以我們僅僅需要考慮獲取大多數(shù)節(jié)點鎖的耗時小于有效時間的情況。在這種情況下森书，根據(jù)我們前面的證明靶端，在MIN_VALIDITY時間內(nèi)，沒有客戶端能重新獲取鎖成功凛膏，所以多個客戶端都能同時成功獲取鎖的結(jié)果杨名，只會發(fā)生在多數(shù)節(jié)點獲取鎖的時間都大大超過TTL時間的情況下，實際上這種情況下這些鎖都會失效 猖毫。 我們非常期待和歡迎有人能提供這個算法安全性的公式化證明台谍，或者發(fā)現(xiàn)任何bug。
性能論證
這個系統(tǒng)的性能主要基于以下三個主要特征：
1.鎖自動釋放的特征（超時后會自動釋放）吁断，一定時間后某個鎖都能被再次獲取趁蕊。
2.客戶端通常會在不再需要鎖或者任務執(zhí)行完成之后主動釋放鎖，這樣我們就不用等到超時時間會再去獲取這個鎖仔役。
3.當一個客戶端需要重試獲取鎖時掷伙，這個客戶端會等待一段時間，等待的時間相對來說會比我們重新獲取大多數(shù)鎖的時間要長一些又兵，這樣可以降低不同客戶端競爭鎖資源時發(fā)生死鎖的概率任柜。
然而，我們在網(wǎng)絡分區(qū)時要損失TTL的可用性時間，所以如果網(wǎng)絡分區(qū)持續(xù)發(fā)生宙地，這個不可用會一直持續(xù)升熊。這種情況在每次一個客戶端獲取到了鎖并在釋放鎖之前被網(wǎng)絡分區(qū)了時都會出現(xiàn)。
基本來說绸栅，如果持續(xù)的網(wǎng)絡分區(qū)發(fā)生的話级野，系統(tǒng)也會在持續(xù)不可用。
性能粹胯、故障恢復和fsync
很多使用Redis做鎖服務器的用戶在獲取鎖和釋放鎖時不止要求低延時蓖柔，同時要求高吞吐量，也即單位時間內(nèi)可以獲取和釋放的鎖數(shù)量风纠。為了達到這個要求况鸣，一定會使用多路傳輸來和N個服務器進行通信以降低延時（或者也可以用假多路傳輸，也就是把socket設置成非阻塞模式竹观，發(fā)送所有命令镐捧，然后再去讀取返回的命令，假設說客戶端和不同Redis服務節(jié)點的網(wǎng)絡往返延時相差不大的話）臭增。
然后如果我們想讓系統(tǒng)可以自動故障恢復的話懂酱，我們還需要考慮一下信息持久化的問題。
為了更好的描述問題誊抛，我們先假設我們Redis都是配置成非持久化的列牺，某個客戶端拿到了總共5個節(jié)點中的3個鎖，這三個已經(jīng)獲取到鎖的節(jié)點中隨后重啟了拗窃，這樣一來我們又有3個節(jié)點可以獲取鎖了（重啟的那個加上另外兩個）瞎领，這樣一來其他客戶端又可以獲得這個鎖了，這樣就違反了我們之前說的鎖互斥原則了随夸。
如果我們啟用AOF持久化功能九默，情況會好很多。舉例來說宾毒，我們可以發(fā)送SHUTDOWN命令來升級一個Redis服務器然后重啟之驼修，因為Redis超時時效是語義層面實現(xiàn)的，所以在服務器關掉期間時超時時間還是算在內(nèi)的伍俘，我們所有要求還是滿足了的邪锌。然后這個是基于我們做的是一次正常的shutdown，但是如果是斷電這種意外停機呢癌瘾？如果Redis是默認地配置成每秒在磁盤上執(zhí)行一次fsync同步文件到磁盤操作，那就可能在一次重啟后我們鎖的key就丟失了饵溅。理論上如果我們想要在所有服務重啟的情況下都確保鎖的安全性妨退，我們需要在持久化設置里設置成永遠執(zhí)行fsync操作，但是這個反過來又會造成性能遠不如其他同級別的傳統(tǒng)用來實現(xiàn)分布式鎖的系統(tǒng)咬荷。 然后問題其實并不像我們第一眼看起來那么糟糕，基本上只要一個服務節(jié)點在宕機重啟后不去參與現(xiàn)在所有仍在使用的鎖幸乒，這樣正在使用的鎖集合在這個服務節(jié)點重啟時，算法的安全性就可以維持罕扎，因為這樣就可以保證正在使用的鎖都被所有沒重啟的節(jié)點持有聚唐。 為了滿足這個條件，我們只要讓一個宕機重啟后的實例腔召，至少在我們使用的最大TTL時間內(nèi)處于不可用狀態(tài)杆查，超過這個時間之后臀蛛，所有在這期間活躍的鎖都會自動釋放掉亲桦。 使用延時重啟的策略基本上可以在不適用任何Redis持久化特性情況下保證安全性浊仆，然后要注意這個也必然會影響到系統(tǒng)的可用性客峭。舉個例子，如果系統(tǒng)里大多數(shù)節(jié)點都宕機了抡柿，那在TTL時間內(nèi)整個系統(tǒng)都處于全局不可用狀態(tài)（全局不可用的意思就是在獲取不到任何鎖）桃笙。
擴展鎖來使得算法更可靠
如果客戶端做的工作都是由一些小的步驟組成，那么就有可能使用更小的默認鎖有效時間沙绝，而且擴展這個算法來實現(xiàn)一個鎖擴展機制搏明∩撩剩基本上星著，客戶端如果在執(zhí)行計算期間發(fā)現(xiàn)鎖快要超時了粗悯，客戶端可以給所有服務實例發(fā)送一個Lua腳本讓服務端延長鎖的時間，只要這個鎖的key還存在而且值還等于客戶端獲取時的那個值样傍。 客戶端應當只有在失效時間內(nèi)無法延長鎖時再去重新獲取鎖（基本上這個和獲取鎖的算法是差不多的） 然而這個并不會對從本質(zhì)上改變這個算法，所以最大的重新獲取鎖數(shù)量應該被設置成合理的大小衫哥，不然性能必然會受到影響。
想提供幫助撤逢？
如果你很了解分布式系統(tǒng)的話膛锭，我們非常歡迎你提供一些意見和分析。當然如果能引用其他語言的實現(xiàn)話就更棒了初狰。 謝謝！
