原文地址：https://redis.io/topics/distlock

在不同進(jìn)程必須以互斥的方式操作共享資源的環(huán)境中宜鸯，分布式鎖是一種非常有用的機(jī)制。

有很多代碼庫(kù)和博客描述了如何基于Redis實(shí)現(xiàn)DLM（Distributed Lock Manager）蠢箩，但是每個(gè)庫(kù)使用方式都不同，并且很多人使用了比復(fù)雜設(shè)計(jì)實(shí)現(xiàn)保證較低的簡(jiǎn)單方法肥荔。

本文旨在提供一種更權(quán)威的算法加酵，用于實(shí)現(xiàn)基于Redis的分布式鎖。我們提供的算法叫做RedLock姜盈，實(shí)現(xiàn)了一種比vanilla單例方式更安全的DLM低千。我們希望社區(qū)可以分析它并進(jìn)行反饋。

實(shí)現(xiàn)

在描述算法之前馏颂，下面有幾個(gè)可用的實(shí)現(xiàn)鏈接用于參考示血。

Redlock-rb?(Ruby).

Redlock-py?(Python)

Aioredlock?(Asyncio Python)

Redlock-php?(PHP)

PHPRedisMutex?(further PHP)

cheprasov/php-redis-lock?(PHP)

Redsync.go?(Go)

Redisson?(Java)

Redis::DistLock?(Perl)

Redlock-cpp?(C++)

Redlock-cs?(C#/.NET)

RedLock.net?(C#/.NET)

ScarletLock?(C# .NET)

node-redlock?(NodeJS)

安全與可用保證

我們用3個(gè)屬性對(duì)設(shè)計(jì)進(jìn)行建模，依我看來(lái)救拉，這些屬性有效使用分布式鎖的最小保證：

1. 安全性：互斥难审。在任一時(shí)刻，只有一個(gè)客戶端可以持有鎖亿絮。

2. 可用性 A：死鎖釋放告喊。即使鎖定資源的客戶端崩潰或者被分區(qū)麸拄，也可以獲取到鎖。

3. 可用性 B：容錯(cuò)黔姜。只要多數(shù)Redis節(jié)點(diǎn)啟動(dòng)拢切，客戶端就可以獲取和釋放鎖。

為什么基于故障轉(zhuǎn)移的實(shí)現(xiàn)還不夠

為了理解我們需要提升的內(nèi)容地淀，我們需要分析基于Redis的分布式鎖庫(kù)的現(xiàn)狀失球。

使用Redis鎖定資源的最簡(jiǎn)單的方式是在實(shí)例中創(chuàng)建一個(gè)Key。Key的創(chuàng)建通常會(huì)有一個(gè)存活時(shí)間帮毁，使用的是Redis的過(guò)期的特性，這樣可以保證鎖始終可以被釋放豺撑。當(dāng)客戶端需要釋放資源時(shí)烈疚，就刪除這個(gè)Key。

表面上看俏扩，這種方式很有效辑舷，但是有一個(gè)問(wèn)題：就是我們架構(gòu)中的單點(diǎn)故障西土。如果Redis主機(jī)故障會(huì)發(fā)生什么？好吧灯抛，我們?cè)黾右粋€(gè)Slave節(jié)點(diǎn)。如果Master不可用音瓷，我們就使用Slave節(jié)點(diǎn)对嚼。很遺憾這不可行。這樣做無(wú)法實(shí)現(xiàn)互斥的安全性绳慎，因?yàn)镽edis復(fù)制是異步的纵竖。

這個(gè)方案中有明顯的競(jìng)爭(zhēng)條件：

1. 客戶端A在Master中獲取鎖。

2. Key同步到Slave節(jié)點(diǎn)前杏愤，主機(jī)發(fā)生崩潰靡砌。

3. Slave被提升到Master。

4. 客戶端B獲取到客戶端A持有的鎖珊楼。違反安全性

如果發(fā)生故障時(shí)允許多個(gè)客戶端同時(shí)持有同一個(gè)鎖通殃，那么就可以使用基于復(fù)制的方案。否則厕宗，建議使用本文所描述的方案画舌。

基于單個(gè)實(shí)例的正確實(shí)現(xiàn)

在嘗試處理單例方案問(wèn)題之前，我們檢查下簡(jiǎn)單的場(chǎng)景中如何正確實(shí)現(xiàn)分布式鎖媳瞪，因?yàn)樵陔S時(shí)出現(xiàn)競(jìng)爭(zhēng)狀態(tài)的應(yīng)用中骗炉，這是一個(gè)可行的解決方案，而且對(duì)于我們將要描述的分布式算法這個(gè)是基礎(chǔ)蛇受。

要獲得鎖句葵，可以采用下面的方式：

SET resource_name my_random_value NX PX 30000

只有Key不存在時(shí)（NX 選項(xiàng)），這條命令才會(huì)設(shè)置Key，并且30000毫秒到期（PX 選項(xiàng)）乍丈。Key設(shè)置為“myrandomvalue”剂碴。這個(gè)值必須要在所有的客戶端以及加鎖的請(qǐng)求中保證唯一。使用隨機(jī)值本質(zhì)上是為了以安全的方式釋放鎖轻专，通過(guò)腳本告訴Redis：只有Key存在并且Key對(duì)應(yīng)的Value是期望值忆矛，才能移除Key。這是通過(guò)以下Lua腳本完成的：

if redis.call("get",KEYS[1]) == ARGV[1] then

? ? return redis.call("del",KEYS[1]);

else?

? ? return 0;

end

避免移除其他客戶端的鎖是很重要的请垛。例如客戶端A獲取到鎖以后催训，鎖失效后才執(zhí)行完成，當(dāng)客戶端釋放鎖時(shí)鎖已經(jīng)被其他的客戶端獲取宗收。因此客戶端只用DEL命令是不安全的漫拭，也許會(huì)移除其他客戶端的鎖。相反混稽，使用上述的腳本采驻，每把鎖都有一個(gè)隨機(jī)的“簽名”，因此匈勋，只有設(shè)置鎖的客戶端嘗試刪除時(shí)礼旅，這把鎖才能被刪除。

隨機(jī)字符串應(yīng)該是什么呢洽洁？我采取的是 /dev/urandom 生成的20個(gè)字節(jié)痘系，但是你可以找到一種成本更低的方式，確保它在你的任務(wù)中是唯一的诡挂。例如一個(gè)安全的選擇是利用RC4算法從/dev/urandom生成一個(gè)偽隨機(jī)流碎浇。還有一種簡(jiǎn)單的方案是使用unix時(shí)間戳加上客戶端ID，雖然不夠安全璃俗，但是在大多數(shù)環(huán)境中可能足夠了奴璃。

我們用作Key存活的時(shí)間，也叫做“鎖可用時(shí)間”城豁。它既是鎖自動(dòng)釋放時(shí)間苟穆，也是其他客戶端搶占鎖之前客戶端用來(lái)執(zhí)行任務(wù)的時(shí)間，在技術(shù)上不違反互斥的原則唱星，他保證了在獲取鎖以后限定的時(shí)間內(nèi)保持互斥雳旅。

現(xiàn)在我們有了一個(gè)獲取釋放鎖的好的方法。由單一间聊、持續(xù)可用的實(shí)例組成的非分布式系統(tǒng)是安全的攒盈。讓我們將這一概念擴(kuò)展到分布式系統(tǒng)，分布式系統(tǒng)沒(méi)有這么多保證哎榴。

Redlock算法

在這個(gè)算法的分布式版本中型豁，我們假設(shè)有N個(gè)Redis節(jié)點(diǎn)僵蛛。這些節(jié)點(diǎn)總是相互獨(dú)立的，因此我們不需要同步或者其他的隱式協(xié)調(diào)系統(tǒng)迎变。我們描述了在單節(jié)點(diǎn)環(huán)境中如何安全的獲取與釋放鎖充尉。我們理所當(dāng)然的認(rèn)為這個(gè)算法在每個(gè)節(jié)點(diǎn)中使用相同的方式獲取和釋放鎖。在例子中我們set N=5衣形，這是一個(gè)比較合適的值驼侠，因此我們需要在不同的主機(jī)或者虛擬機(jī)上運(yùn)行5個(gè)Redis主節(jié)點(diǎn)，確保他們故障能夠相互隔離谆吴。

為了獲取鎖倒源，客戶端需要執(zhí)行下面的操作：

1. 以毫秒為單位獲取當(dāng)前時(shí)間。

2. 嘗試在所有的N個(gè)實(shí)例中順序的獲取鎖纪铺，在所有實(shí)例中使用相同的Key和Value相速。步驟2中，在每個(gè)實(shí)例中設(shè)置鎖時(shí)鲜锚，為了獲取到鎖，客戶端需要設(shè)置一個(gè)小于鎖自動(dòng)釋放時(shí)間的超時(shí)時(shí)間苫拍。例如如果鎖自動(dòng)釋放時(shí)間是10s芜繁，那么超時(shí)時(shí)間可以設(shè)置成5～50毫秒。避免客戶端長(zhǎng)時(shí)間嘗試與宕掉的Redis的節(jié)點(diǎn)通信造成阻塞：如果一個(gè)實(shí)例不可用绒极，我們應(yīng)該盡快嘗試和下一個(gè)實(shí)例通信骏令。

3. 客戶機(jī)獲取鎖花費(fèi)的時(shí)間，是用當(dāng)前時(shí)間減去步驟1獲取的時(shí)間戳垄提。如果客戶端能夠在多數(shù)實(shí)例（至少3個(gè)）中獲取到鎖榔袋，獲取鎖的總時(shí)間少于鎖的有效時(shí)間，就可以認(rèn)為鎖被成功獲取

4. 如果鎖被獲取到铡俐，就可以認(rèn)為鎖的實(shí)際有效時(shí)間就是初始的有效時(shí)間減去步驟3計(jì)算的時(shí)間凰兑。

5. 如果客戶端因?yàn)槟承┰颢@取鎖失敗（不能在N/2+1個(gè)實(shí)例中獲取鎖或者有效時(shí)間是負(fù)數(shù)）审丘，那么將會(huì)嘗試在所有實(shí)例中解鎖（包括沒(méi)有成功加鎖的實(shí)例）

算法是異步的嗎吏够？

該算法基于這樣一個(gè)假設(shè)，雖然沒(méi)有跨進(jìn)程的同步時(shí)鐘滩报，但每個(gè)進(jìn)程的本地時(shí)鐘會(huì)以近似相同的速率流動(dòng)锅知，誤差小于鎖自動(dòng)釋放的時(shí)間。這一假定與現(xiàn)實(shí)世界的計(jì)算機(jī)類似：每個(gè)計(jì)算機(jī)有本地時(shí)鐘脓钾，我們通常信任不同的計(jì)算機(jī)之間時(shí)間差是很小的售睹。

現(xiàn)在，我們需要細(xì)化互斥規(guī)則：只要獲取到鎖的客戶端能夠在時(shí)間T內(nèi)完成它的工作可训，就能夠保證互斥昌妹，時(shí)間T的計(jì)算規(guī)則是有效時(shí)間（詳見(jiàn)步驟3）減去一些時(shí)間（一般只有幾毫秒捶枢，為了補(bǔ)償不同進(jìn)程之間的時(shí)間差）

想要了解更多關(guān)于時(shí)間差的類似系統(tǒng)，可以參考這篇有趣的文章：《Leases: an efficient fault-tolerant mechanism for distributed file cache consistency》

失敗重試

當(dāng)客戶端不能獲取到鎖時(shí)捺宗，應(yīng)該在隨機(jī)延時(shí)后再次嘗試柱蟀，隨機(jī)延時(shí)是為了避免多個(gè)客戶端同步的在同一時(shí)間獲取同一個(gè)資源的鎖（否則會(huì)出現(xiàn)沒(méi)有客戶端能獲取到鎖的腦裂狀態(tài)）⊙晾鳎客戶端在多數(shù)Redis實(shí)例中獲取鎖的速度越快长已，需要重試的時(shí)間窗口就越小。因此理想狀態(tài)下昼牛，客戶端應(yīng)該在采用多路復(fù)用的模式同時(shí)向N個(gè)實(shí)例中發(fā)送Set命令

有必要強(qiáng)調(diào)一下术瓮，如果客戶端獲取多數(shù)鎖失敗，應(yīng)盡快的釋放已經(jīng)獲得的鎖贰健，這樣沒(méi)必要等到Key超時(shí)后再獲取鎖（然而出現(xiàn)網(wǎng)絡(luò)分區(qū)和客戶端無(wú)法連接Redis實(shí)例的情況胞四，將失去等待鎖過(guò)期這段時(shí)間的可用性）

鎖釋放

鎖釋放很簡(jiǎn)單，無(wú)論客戶端是否成功的獲取到鎖伶椿，只需要在所有節(jié)點(diǎn)釋放鎖就行辜伟。

安全性論證

算法是否是安全的？我們可以試著思考在不同的場(chǎng)景下會(huì)發(fā)生什么脊另。

開(kāi)始之前导狡，我們假設(shè)客戶端可以在多數(shù)實(shí)例中獲取到鎖。所有的實(shí)例都包含一個(gè)有相同存活時(shí)間的Key偎痛。然而Key是在不同的時(shí)間設(shè)置的旱捧，因此這些key也會(huì)在不同的時(shí)間失效。我們假設(shè)最壞情況下踩麦，第一個(gè)Key設(shè)置的時(shí)間是T1（連接到第一個(gè)服務(wù)的時(shí)間）枚赡，最后一個(gè)Key設(shè)置時(shí)間是T2（最后一個(gè)服務(wù)應(yīng)答的時(shí)間），我們確定第一個(gè)設(shè)置了失效時(shí)間的Key至少存活的時(shí)間為MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT 谓谦，TTL是鎖超時(shí)時(shí)間贫橙，(T2-T1)是獲取鎖的耗時(shí)，CLOCK_DRIFT不同進(jìn)程的時(shí)間差茁计。其他Key會(huì)在這個(gè)時(shí)間之后失效料皇，因此我們可以確定，所有的Key在這個(gè)時(shí)間點(diǎn)之前是同時(shí)存在的星压。

在多數(shù)Key被設(shè)置的時(shí)間內(nèi)践剂，其他客戶端無(wú)法獲取到鎖，在N/2+1個(gè)Key存在的情況下娜膘，N/2+1個(gè) SET NX 命令是不會(huì)成功的逊脯。因此一個(gè)鎖被獲取，就不能同時(shí)重新獲取這個(gè)鎖（違反了互斥原則）

當(dāng)然我們需要保證多個(gè)客戶端同時(shí)獲取鎖時(shí)不會(huì)同時(shí)成功竣贪。

如果一個(gè)客戶端鎖定多數(shù)實(shí)例消耗的時(shí)間接近或者超過(guò)鎖最大的有效時(shí)間（為SET使用的TTL）军洼，那么系統(tǒng)會(huì)認(rèn)為鎖失效同時(shí)解鎖這些實(shí)例巩螃，因此我們只需要考慮客戶端在小于鎖有效時(shí)間的范圍內(nèi)鎖定多個(gè)實(shí)例的場(chǎng)景。這種情況我們已經(jīng)在上文進(jìn)行論證匕争，在MIN_VALIDITY時(shí)間范圍內(nèi)避乏，沒(méi)有客戶端能夠重新獲取鎖。因此只有當(dāng)多數(shù)節(jié)點(diǎn)獲取鎖的時(shí)間遠(yuǎn)遠(yuǎn)大于TTL時(shí)甘桑，多個(gè)客戶端才能同時(shí)鎖定N/2+1個(gè)實(shí)例拍皮。

可靠性論證

系統(tǒng)可靠性是基于三個(gè)主要的特性：

1. 鎖自動(dòng)釋放（因?yàn)镵ey失效）：最終被鎖定的Key可以再次使用

2. 客戶端通常在鎖獲取失敗或者工作完成后主動(dòng)釋放鎖，我們不需要等待鎖過(guò)期在重新獲得鎖

3. 當(dāng)客戶端重試獲取鎖時(shí)跑杭，客戶端等待時(shí)間遠(yuǎn)遠(yuǎn)大于獲取多數(shù)鎖的時(shí)間铆帽，為了降低資源競(jìng)爭(zhēng)期間腦裂的概率

然而我們?cè)诰W(wǎng)絡(luò)分區(qū)時(shí)需要損失TTL時(shí)間的可用性，如果有持續(xù)的分區(qū)問(wèn)題德谅，那么就會(huì)持續(xù)不可用爹橱。這種情況會(huì)在每次客戶端獲取鎖之后釋放鎖之前被分區(qū)時(shí)發(fā)生。

基本上窄做，如果有持續(xù)的網(wǎng)絡(luò)分區(qū)愧驱，系統(tǒng)在這段時(shí)間內(nèi)就會(huì)持續(xù)不可用。

性能椭盏、故障恢復(fù)和fsync

很多使用Redis作為鎖服務(wù)的用戶冯键，不僅要求獲取釋放鎖的低延時(shí)，也要求高吞吐量庸汗，即每秒鐘獲取釋放鎖的數(shù)量。為了滿足這個(gè)要求手报，采用多路復(fù)用的策略與N個(gè)Redis服務(wù)通信以降低延時(shí)（或者使用可憐人的多路復(fù)用蚯舱，即socket設(shè)置成非阻塞模式，發(fā)送所有命令掩蛤，然后讀所有的命令枉昏，假設(shè)客戶端和多個(gè)實(shí)例之間的RTT是相近的）

然而如果我們想要系統(tǒng)故障自動(dòng)回復(fù)，還需要考慮持久化揍鸟。我們看下這個(gè)問(wèn)題兄裂，假設(shè)我們配置Redis不持久化⊙粼澹客戶端在3個(gè)實(shí)例中獲取鎖晰奖，然后一個(gè)加鎖的實(shí)例重啟，這時(shí)相同的資源有3個(gè)實(shí)例可以獲取到鎖腥泥，另一個(gè)客戶端就可以再次對(duì)這個(gè)資源加鎖匾南，違反了鎖互斥的安全原則。

如果我們使用AOF持久化蛔外，情況會(huì)好一些蛆楞。例如我們可以通過(guò)SHUTDOWN和重啟升級(jí)一個(gè)服務(wù)溯乒。因?yàn)镽edis失效是語(yǔ)義層面的實(shí)現(xiàn)，當(dāng)服務(wù)關(guān)閉時(shí)時(shí)間實(shí)際上仍然在流逝豹爹，我們的需求都能滿足裆悄。只要是正常關(guān)閉，一切都很好臂聋。斷電會(huì)怎么樣呢光稼？如果Redis是默認(rèn)配置，每秒執(zhí)行一次fsync逻住，重啟后我們的key就有可能丟失钟哥。理論上， 如果我們要保證任何實(shí)例重啟的情況下鎖的安全性瞎访，我們需要在持久化設(shè)置中啟用 fsync=always腻贰。反過(guò)來(lái)說(shuō)，相比與其他同級(jí)別的實(shí)現(xiàn)安全的分布式鎖的CP系統(tǒng)扒秸，會(huì)損失性能播演。

然而事情會(huì)比第一眼看起來(lái)的那樣要好，只要實(shí)例崩潰后重啟伴奥，不再參與到當(dāng)前激活的鎖写烤，算法的安全性就能保證。因?yàn)閷?shí)例重啟時(shí)拾徙，當(dāng)前激活的鎖可以被其他實(shí)例獲取洲炊。

為了滿足這一條件，我們需要讓一個(gè)實(shí)例在崩潰后尼啡，不可用的時(shí)間至少要比我們?cè)O(shè)置的TTL多一點(diǎn)暂衡，也就是說(shuō)，要大于實(shí)例崩潰時(shí)所有存在的鎖失效或者自動(dòng)釋放所需要的時(shí)間崖瞭。

延遲重啟基本可以保證安全性狂巢，即使沒(méi)有任務(wù)可用的Redis持久化。然而书聚，需要注意的是這也意味著可用性的損失唧领。嫁入多數(shù)實(shí)例崩潰，TTL時(shí)間內(nèi)系統(tǒng)全局不可用（全局意味著在這個(gè)時(shí)間內(nèi)沒(méi)有資源能夠被鎖定）

使算法更可靠：擴(kuò)展鎖

如果客戶端的工作是由小步驟組成的雌续，那么鎖有效時(shí)間可以使用更小的默認(rèn)值斩个，擴(kuò)展算法以實(shí)現(xiàn)鎖的延長(zhǎng)機(jī)制。當(dāng)鎖即將失效時(shí)西雀，如果客戶端處于計(jì)算中萨驶，那么可以通過(guò)向所有實(shí)例發(fā)送延長(zhǎng)TTL的Lua腳本來(lái)延長(zhǎng)鎖，這個(gè)Key必須存在并且和獲取鎖時(shí)客戶端分配的隨機(jī)值一致艇肴。如果可以在多數(shù)實(shí)例中擴(kuò)展鎖并且是在有效期內(nèi)腔呜，那么客戶端只需要考慮鎖的重新獲取叁温。

然而這不是在技術(shù)上改變算法，因此鎖重新獲取的最大次數(shù)應(yīng)該被限制核畴，否則性能會(huì)受到影響膝但。

RedLock分析

Martin Kleppmann 對(duì)RedLock的分析How to do distributed locking

我不同意這篇評(píng)測(cè)并且上傳了我的回復(fù)?Is RedLock Safe?