前言
在分布式架構(gòu)中因?yàn)楣?jié)點(diǎn)之間存在共享資源的競(jìng)爭(zhēng)败去，所以在并發(fā)的情況下會(huì)帶來(lái)的數(shù)據(jù)不一致的問(wèn)題，而分布式鎖則成為了一種解決方案寂殉。分布式鎖的實(shí)現(xiàn)一般分為四種:
- 基于數(shù)據(jù)庫(kù)實(shí)現(xiàn)
- 基于Zookeeper實(shí)現(xiàn)
- 基于Etc實(shí)現(xiàn)
- 基于Redis實(shí)現(xiàn)
不同的實(shí)現(xiàn)各有優(yōu)劣怨酝，具體采用哪種還得結(jié)合項(xiàng)目實(shí)際情況。
下面的文章內(nèi)容是Redis作者提出的關(guān)于采用Redis實(shí)現(xiàn)分布式鎖RedLock的算法講解后德，受限于個(gè)人理解和翻譯水平，譯文與原文可能存在些許出入抄腔，請(qǐng)海納探遵！
閱讀原文(Distributed locks with Redis)始終是最好的選擇。
譯文內(nèi)容
在許多不同進(jìn)程必須相互獨(dú)占地操作共享的資源的環(huán)境中妓柜，分布式鎖是一種非常有用的藝術(shù)箱季。
有很多庫(kù)和博客講述了如何使用Redis實(shí)現(xiàn)DLM（分布式鎖管理器），但每個(gè)庫(kù)使用了不同的方式棍掐，與使用稍微復(fù)雜一點(diǎn)的設(shè)計(jì)實(shí)現(xiàn)相比藏雏，很多庫(kù)使用了一個(gè)更低保障的簡(jiǎn)單方式實(shí)現(xiàn)。
這篇文章嘗試提供一種更經(jīng)典的算法來(lái)使用Redis實(shí)現(xiàn)分布式鎖作煌。我們建議用來(lái)實(shí)現(xiàn)DLM的算法稱之為Redlock掘殴，我們相信它相比毫無(wú)特色的單例方案更加安全。我們希望社區(qū)能夠分析它粟誓，提供反饋奏寨，并且將其視為實(shí)現(xiàn)Redis分布式鎖或者更復(fù)雜或者可替代設(shè)計(jì)的一個(gè)起點(diǎn)。
實(shí)現(xiàn)
在講述Redlock算法前鹰服，這里有一些已經(jīng)可以使用的實(shí)現(xiàn)鏈接用于資料參考：
- Redlock-rb (Ruby) 同樣有一個(gè)Redlock-rb的fork添加了gem管理用于簡(jiǎn)單發(fā)布或者更多
- Redlock-py (Python)
- Aioredlock (Asyncio Python)
- Redlock-php (PHP)
- PHPRedisMutex (PHP)
- cheprasov/php-redis-lock (PHP)
- Redsync (Go)
- Redisson (Java)
- Redis::DistLock (Perl)
- Redlock-cpp (C++)
- Redlock-cs (C#/.NET)
- RedLock.net (C#/.NET)
- ScarletLock (C# .NET)
- Redlock4Net (C# .NET)
- node-redlock (NodeJS)
安全性和存活保障
我們將我們的設(shè)計(jì)模型化為三點(diǎn)性質(zhì)病瞳，這三點(diǎn)性質(zhì)從我們的視角看揽咕，是高效地使用分布式鎖的最低保障：
- 安全性：互斥鎖。在給定的任何時(shí)刻套菜，只有一個(gè)客戶端可以持有該鎖亲善。
- 存活性A：避免死鎖。最終總是可能獲取到鎖逗柴，即使持有鎖的客戶端crash了或者被分離了蛹头。
- 存活性B：容錯(cuò)性。只要Redis的大多數(shù)節(jié)點(diǎn)在運(yùn)行戏溺，客戶端就能夠獲得和釋放鎖渣蜗。
為什么基于故障轉(zhuǎn)移的實(shí)現(xiàn)是不夠的
為了理解我們想要改善的地方，讓我們分析一下當(dāng)前大多數(shù)基于Redis的分布式鎖的現(xiàn)狀旷祸。
使用Redis給一個(gè)資源上鎖的最簡(jiǎn)單的方法是在一個(gè)實(shí)例中創(chuàng)建一個(gè)key袍睡。通過(guò)Redis的expire功能，這個(gè)key通常伴隨著有效期被創(chuàng)建肋僧，所以最終它將會(huì)被釋放(在我們列表中的性質(zhì)2)斑胜。當(dāng)客戶端需要釋放資源的時(shí)候，直接刪除該key嫌吠。
從表面上看止潘，這運(yùn)行正常，但是有一個(gè)問(wèn)題：在我們的架構(gòu)中這是一個(gè)單點(diǎn)故障辫诅。如果主redis停機(jī)了會(huì)發(fā)生什么凭戴？讓我們添加一個(gè)從redis，當(dāng)主redis不可用的時(shí)候使用它炕矮，不幸的是這是不可用的么夫，這樣做我們不能實(shí)現(xiàn)互斥鎖的安全性，因?yàn)閞edis的復(fù)制是異步的肤视。
在這種模式下有一個(gè)明顯的競(jìng)爭(zhēng)條件：
- 客戶端A在主redis中獲得鎖
- 在key被傳送到從redis前档痪，主redis crash了
- 從redis晉升為主redis
- 客戶端B獲得相同資源的鎖，但是該鎖早已被客戶端A持有了邢滑。安全性問(wèn)題
多個(gè)客戶端可以同時(shí)持有鎖有時(shí)在特殊條件下是非常好的腐螟，比如故障期間。如果是這種情況困后，你可以使用基于復(fù)制的解決方案乐纸。否則我們建議實(shí)現(xiàn)我們?cè)谶@篇文檔里講述的方案。
單實(shí)例的正確實(shí)現(xiàn)
在試圖克服上面講述的單實(shí)例的局限性之前摇予，讓我們先檢查一下在這種簡(jiǎn)單情況下如何正確完成它汽绢，因?yàn)檫@對(duì)于可接受偶爾的競(jìng)爭(zhēng)條件的應(yīng)用來(lái)說(shuō)這實(shí)際上在是一個(gè)可實(shí)施的方案，也是因?yàn)閱螌?shí)例中的鎖是我們這里講述的分布式算法的基礎(chǔ)侧戴。
為了獲得鎖宁昭，需要做的如下：
SET resource_name my_random_value NX PX 30000
這個(gè)命令只有當(dāng)key不存在的時(shí)候才會(huì)設(shè)置（NX選項(xiàng)）跌宛，并且過(guò)期時(shí)間為30000毫秒（PX選項(xiàng)），設(shè)置key的值為"my_random_value"久窟，這個(gè)值在所有客戶端和所有的鎖請(qǐng)求中必須是唯一的。隨機(jī)的值是為了以一種安全的方式釋放鎖本缠，通過(guò)腳本告訴redis：只有當(dāng)key存在并且key存儲(chǔ)的值是所期望的值的時(shí)候才移除該key斥扛。這是由下面的Lua腳本實(shí)現(xiàn)的：
if redis.call("get",KEYS[1]) == ARGV[1] then
return redis.call("del",KEYS[1])
else
return 0
end
這對(duì)于為了避免移除其他客戶端創(chuàng)建的鎖是很重要的。例如一個(gè)客戶端可能獲得鎖丹锹，然后在某些操作中被阻塞了超過(guò)鎖的有效期時(shí)間（在該時(shí)間key將會(huì)過(guò)期）稀颁，并且在稍后移除鎖，而該鎖早已被其他客戶端獲得楣黍。僅僅使用DEL是不安全的匾灶，因?yàn)橐粋€(gè)客戶端也許會(huì)移除其他客戶端的鎖。通過(guò)上面的腳本替代租漂，每個(gè)鎖被一個(gè)隨機(jī)字符串所"簽名"阶女，所以鎖只有當(dāng)仍然是被設(shè)置自己的客戶端移除的時(shí)候才會(huì)被移除。
這樣的隨機(jī)字符串應(yīng)該是什么哩治？我假設(shè)它是20字節(jié)秃踩，來(lái)自/dev/urandom，但是對(duì)于你的任務(wù)來(lái)說(shuō)业筏，你可以找到讓它變得足夠唯一的更簡(jiǎn)單的方式憔杨，例如一個(gè)安全的選擇是用/dev/urandom作為RC4的種子，并且利用它生成一個(gè)偽隨機(jī)的stream蒜胖。一個(gè)更簡(jiǎn)單的方案是使用精確到微秒的unix時(shí)間戳與客戶端ID拼接消别，雖然這不夠安全，但是也許能勝任大多數(shù)環(huán)境中的任務(wù)台谢。我們用作key生命周期的時(shí)間寻狂，被稱之為鎖的有效期。它既是客戶端自動(dòng)釋放鎖的時(shí)間朋沮，也是在其他客戶端可以再次獲得鎖之前該客戶端用于執(zhí)行操作所需要的時(shí)間荆虱，從獲得鎖的時(shí)刻開(kāi)始，在給定的時(shí)間窗口內(nèi)朽们，沒(méi)有違背互斥鎖保障怀读。
所以現(xiàn)在我們有了一個(gè)獲得和釋放鎖的好方法。這個(gè)方法在一個(gè)由單個(gè)的骑脱、總是可用的實(shí)例組成的非分布式系統(tǒng)是安全的菜枷，讓我們將概念擴(kuò)展到一個(gè)沒(méi)有這種保障的分布式系統(tǒng)中去。
Redlock算法
在分布式版本的算法中叁丧，我們假設(shè)我們有N個(gè)主redis啤誊，所有這些節(jié)點(diǎn)都是獨(dú)立的岳瞭，所以我們不使用復(fù)制或者任何其他內(nèi)部的系統(tǒng)。我們已經(jīng)講述過(guò)在一個(gè)單實(shí)例系統(tǒng)中如何安全的獲得或者釋放鎖蚊锹，在單實(shí)例中瞳筏，我們認(rèn)為Redlock算法將會(huì)使用這個(gè)方法獲得和釋放鎖是理所當(dāng)然的。在我們的實(shí)例中我們將N設(shè)置為5牡昆，這是一個(gè)合理的值姚炕，所以為了保證所有redis以基本獨(dú)立的方式失敗，我們需要在不同的計(jì)算機(jī)或者虛擬機(jī)中運(yùn)行5個(gè)主redis丢烘。
為了獲得鎖柱宦，客戶端需要執(zhí)行下面的操作：
- 獲得當(dāng)前的時(shí)間，精確到毫秒播瞳。
- 在N個(gè)實(shí)例中相繼使用相同的key和不同的隨機(jī)值獲得鎖掸刊，在步驟2中，當(dāng)在每個(gè)實(shí)例中設(shè)置鎖的時(shí)候，客戶端使用比鎖自動(dòng)釋放時(shí)間少的超時(shí)時(shí)間來(lái)獲得鎖。例如标捺，如果鎖自動(dòng)釋放時(shí)間是10s，則超時(shí)時(shí)間可以設(shè)置為5-50毫秒之間苍柏，這防止了客戶端長(zhǎng)時(shí)間阻塞在與掛了的redis節(jié)點(diǎn)的交互中：如果一個(gè)實(shí)例不可用，我們應(yīng)該嘗試盡快與下一個(gè)實(shí)例交互姜贡。
- 客戶端通過(guò)當(dāng)前時(shí)間減去步驟1獲得的時(shí)間來(lái)評(píng)估為了獲得鎖耗費(fèi)來(lái)多少時(shí)間试吁，當(dāng)且只有當(dāng)客戶端可以從大多數(shù)實(shí)例（這里是至少3個(gè)）中獲得鎖，并且獲得鎖所需時(shí)間比鎖的有效期少時(shí)楼咳，才會(huì)被考慮獲得鎖熄捍。
- 如果獲得了鎖，它的有效期為初始有效時(shí)間減去如步驟3那樣計(jì)算出的獲得鎖所消耗的時(shí)間母怜。
- 如果因?yàn)橐恍┰颢@得鎖失斢嗟ⅰ（要么大多數(shù)實(shí)例少于N/2+1要么有效期為負(fù)），將會(huì)試圖解鎖所有的實(shí)例（即使實(shí)例被認(rèn)為不能上鎖）苹熏。
Redlock算法是異步的嗎碟贾？
Redlock算法基于這樣一個(gè)假設(shè)，即當(dāng)進(jìn)程之間沒(méi)有同步時(shí)鐘時(shí)轨域，每個(gè)進(jìn)程中的本地時(shí)間仍然以相同的速率流動(dòng)袱耽，與鎖的自動(dòng)釋放時(shí)間相比，誤差較小干发。這個(gè)假設(shè)與現(xiàn)實(shí)世界中的計(jì)算機(jī)非常相似：每臺(tái)計(jì)算機(jī)都有一個(gè)本地時(shí)鐘朱巨，我們通常可以依賴不同的計(jì)算機(jī)來(lái)獲得一個(gè)很小的時(shí)鐘漂移枉长。
在這一點(diǎn)上我們需要更精確的定義我們的互斥鎖規(guī)則：它保證只要客戶端持有鎖冀续，那么在鎖有效期（步驟3中獲得）減去一些時(shí)間（只有幾毫秒琼讽，為了補(bǔ)償進(jìn)程之間的時(shí)鐘飄移）內(nèi)客戶端將會(huì)結(jié)束它的工作。與需要限制時(shí)鐘飄移的相似系統(tǒng)的更多信息洪唐，這篇論文是一個(gè)有趣的參考：Leases: an efficient fault-tolerant mechanism for distributed file cache consistency.钻蹬。
失敗重試
當(dāng)一個(gè)客戶端無(wú)法獲得鎖的時(shí)候，為了取消在同一時(shí)刻針對(duì)相同資源嘗試獲得鎖的客戶端之間的同步凭需，該客戶端應(yīng)該在一個(gè)隨機(jī)延時(shí)后再一次嘗試獲得鎖（這可能會(huì)導(dǎo)致沒(méi)有贏家的大腦分裂局面）问欠。同樣，客戶端嘗試在大多數(shù)redis實(shí)例中獲得鎖越快功炮，出現(xiàn)分裂的窗口越薪η薄（重試的需要也越少）术唬，所以理想情況下薪伏，客戶端應(yīng)該多路復(fù)用地同時(shí)向N個(gè)實(shí)例發(fā)送SET命令。
值得強(qiáng)調(diào)的是粗仓，如果獲取大部分鎖失敗嫁怀，客戶端應(yīng)該盡可能快的釋放（部分）已經(jīng)獲得了的鎖，這很重要借浊。所以為了讓鎖能夠再次被獲得就沒(méi)有必要等待key過(guò)期（然而如果發(fā)生了網(wǎng)絡(luò)斷開(kāi)并且客戶端無(wú)法再與redis實(shí)例交互塘淑，在等待key過(guò)期時(shí)，有一個(gè)可用的懲罰需要支付）蚂斤。
釋放鎖
釋放鎖很簡(jiǎn)單存捺，只涉及在所有實(shí)例中釋放鎖，無(wú)論客戶端是否相信它能夠成功地鎖定給定實(shí)例曙蒸。
安全性討論
Redlock算法是安全的嗎捌治？我們嘗試在不同情況下會(huì)發(fā)生什么。
在開(kāi)始之前我們先假設(shè)客戶端能夠在大多數(shù)實(shí)例中獲得鎖纽窟。所有實(shí)例會(huì)包含一個(gè)有相同生命周期的key肖油。然而key是在不同的時(shí)間設(shè)置的，所以所有的key也會(huì)在不同的時(shí)間過(guò)期臂港。但是如果第一個(gè)key在T1時(shí)刻（我們?cè)谂c第一個(gè)服務(wù)器聯(lián)系前采樣的時(shí)刻）被設(shè)置為最壞的狀態(tài)森枪，最后一個(gè)key在T2時(shí)刻（我們從最后一個(gè)服務(wù)器獲得回復(fù)的時(shí)間）被設(shè)置為最壞的狀態(tài)，我們確定第一個(gè)過(guò)期的key將會(huì)存活至少最短有效期=TTL - (T2 - T1) - 時(shí)鐘飄移审孽。所有其他的key將會(huì)在稍后過(guò)期县袱，所以我們確定至少這次key將會(huì)被同時(shí)設(shè)置。
在大多數(shù)key被設(shè)置期間佑力，另一個(gè)客戶端將不能獲得鎖显拳，因?yàn)槿绻鸑/2+1個(gè)key已經(jīng)存在則N/2+1個(gè)SET NX操作不會(huì)成功。所以如果一個(gè)鎖被獲得了搓萧，在同一時(shí)刻該鎖不可能被再次獲得（違背互斥鎖性質(zhì)）杂数。
然而我們同樣要確保多個(gè)客戶端在同一時(shí)刻嘗試獲得鎖時(shí)不會(huì)成功宛畦。
如果一個(gè)客戶端使用接近或者大于鎖最大的有效期（我們用于SET的有效期）的時(shí)間鎖住了大多數(shù)實(shí)例，那么該鎖將會(huì)被認(rèn)為是非法的并且會(huì)解鎖所有的實(shí)例揍移，所以我們只需要考慮客戶端可以用少于有效期的時(shí)間鎖住大多數(shù)實(shí)例的情形次和，在這種情形下對(duì)于上面早已表達(dá)過(guò)的論點(diǎn)，在最短有效期內(nèi)應(yīng)該沒(méi)有客戶端能夠重復(fù)獲得鎖那伐。所以多個(gè)客戶端將能夠同時(shí)鎖住N/2+1個(gè)實(shí)例（用步驟2結(jié)尾的時(shí)間）踏施，只有當(dāng)鎖住大多數(shù)實(shí)例的時(shí)間大于TTL的時(shí)候，鎖才會(huì)無(wú)效罕邀。
你能提供一個(gè)正式的安全性證明畅形，指出現(xiàn)有的相似算法或者發(fā)現(xiàn)bug嗎？非常感激诉探！
存活討論
系統(tǒng)存活基于三個(gè)主要功能：
- 鎖自動(dòng)釋放（因?yàn)閗ey過(guò)期）：最終key可再次用于上鎖日熬。
- 事實(shí)上，客戶端通常會(huì)在沒(méi)有獲得鎖時(shí)肾胯，或者在獲得鎖后工作終止時(shí)竖席，合作地移除鎖，這使得我們不必等待key過(guò)期來(lái)重新獲得鎖敬肚。
- 事實(shí)上毕荐，當(dāng)客戶端需要重試鎖時(shí)，它等待的時(shí)間比獲取大多數(shù)鎖所需的時(shí)間要長(zhǎng)得多艳馒，以便在資源競(jìng)爭(zhēng)期間不太可能出現(xiàn)分裂大腦的情況憎亚。
然而，在網(wǎng)絡(luò)分區(qū)時(shí)我們支付一個(gè)與TTL時(shí)間對(duì)等的可用懲罰弄慰，所以如果有連續(xù)的分區(qū)第美，我們可以無(wú)限期的支付這個(gè)懲罰，這發(fā)生在每當(dāng)一個(gè)客戶端獲得鎖并且在可以移除鎖之前被分割開(kāi)的時(shí)候曹动。
基本上斋日，如果有無(wú)限連續(xù)的網(wǎng)絡(luò)分區(qū)，系統(tǒng)可能在很長(zhǎng)的時(shí)間內(nèi)不可用墓陈。
性能恶守、崩潰恢復(fù)和同步
就獲得和釋放鎖兩方面的延遲以及每秒獲得/釋放鎖操作次數(shù)，許多用戶使用redis作為鎖服務(wù)器需要高性能贡必。為了滿足這個(gè)需求兔港，用以降低與N個(gè)redis實(shí)例對(duì)話的延遲的策略無(wú)疑是多路復(fù)用（或者管道復(fù)用：讓socket進(jìn)入非阻塞模式，發(fā)送和讀取所有的命令仔拟，假設(shè)在客戶端和每個(gè)實(shí)例之間的RTT是相似的）衫樊。
然而如果我們想要達(dá)成一個(gè)崩潰-恢復(fù)的系統(tǒng)模式，仍然有另一個(gè)關(guān)于持久化的考慮。這里為了明白問(wèn)題科侈，我們假設(shè)我們沒(méi)有給redis配置持久化载佳，一個(gè)客戶端在5個(gè)實(shí)例中的3個(gè)獲得鎖，能夠獲得鎖的實(shí)例中有一個(gè)實(shí)例被重啟了臀栈，此時(shí)我們可以為同一資源鎖定3個(gè)實(shí)例蔫慧，另一個(gè)客戶端可以再次鎖定，這違反了鎖的獨(dú)占性的安全屬性权薯。
如果我們配置了AOF持久化姑躲，情況將會(huì)改善很多。比如我們可以通過(guò)發(fā)送SHUTDOWN更新一個(gè)和重啟它盟蚣。因?yàn)閞edis的過(guò)期機(jī)制是語(yǔ)義實(shí)現(xiàn)的黍析，所以當(dāng)服務(wù)器關(guān)閉的時(shí)候時(shí)間仍然在流逝，我們所有的請(qǐng)求都正常屎开。然而阐枣，只要徹底關(guān)閉，所有事情都是正常的牍戚。如果停電了怎么辦侮繁？如果redis被配置了默認(rèn)每秒同步數(shù)據(jù)到硬盤虑粥，重啟之后有可能我們的key會(huì)丟失如孝，理論上，如果我們想要保證面對(duì)任何實(shí)例重啟鎖都安全的情況娩贷，我們需要在持久化配置中設(shè)置fsync=always第晰。反過(guò)來(lái)這又會(huì)破壞傳統(tǒng)意義上用來(lái)以安全的方式實(shí)現(xiàn)分布式鎖的同級(jí)別CP系統(tǒng)的性能。然而彬祖，情況實(shí)際上比它們第一眼看起來(lái)更好茁瘦。基本上储笑，只要崩潰后重啟甜熔，算法繼續(xù)持有安全性，它不在參與任何當(dāng)前活動(dòng)的鎖突倍，所以當(dāng)實(shí)例重啟時(shí)腔稀，當(dāng)前所有活動(dòng)的鎖被正在請(qǐng)求鎖的實(shí)例獲得，而不是重新加入系統(tǒng)的實(shí)例羽历。
為了保證這一點(diǎn)焊虏，我們只需要讓一個(gè)崩潰時(shí)間、不可用時(shí)間（實(shí)例崩潰后存在的鎖的所有key所需的時(shí)間）比最大TTL還要長(zhǎng)的實(shí)例變成非法和自動(dòng)釋放的秕磷。
即使沒(méi)有任何類型的redis持久化可用诵闭，使用延遲重啟是基本可能實(shí)現(xiàn)安全性的，但是注意這有可能轉(zhuǎn)移成一個(gè)懲罰。比如疏尿，如果大多數(shù)實(shí)例崩潰了瘟芝，對(duì)于TTL來(lái)說(shuō)系統(tǒng)將會(huì)變成全局不可用的（這里的全局指期間不在有資源是可上鎖的）。
讓算法更可靠: 擴(kuò)展鎖
如果客戶端執(zhí)行的工作是由小步驟組成的褥琐，則可以默認(rèn)使用較小的鎖有效期模狭，并且擴(kuò)展實(shí)現(xiàn)鎖擴(kuò)展機(jī)制的算法。在計(jì)算執(zhí)行到一半當(dāng)鎖有效期快到的時(shí)候踩衩，基本上客戶端可以通過(guò)發(fā)送一個(gè)擴(kuò)展Lua腳本給所有的實(shí)例來(lái)擴(kuò)展鎖嚼鹉，該腳本用于擴(kuò)展key的TTL，而對(duì)應(yīng)的key必須仍然存在并且持有的隨機(jī)指仍然是上鎖時(shí)的值驱富。
客戶端應(yīng)該只在key有效期內(nèi)并且能夠在大多數(shù)實(shí)例中擴(kuò)展鎖的時(shí)候才認(rèn)為鎖是可以重新獲得的（基本上使用的算法與剛開(kāi)始獲取鎖的算法相似）锚赤。
然而這不能在技術(shù)上改變算法，所以重新獲得鎖的嘗試次數(shù)應(yīng)該限制最大值褐鸥，否則違背了存活性質(zhì)线脚。
想要幫忙？
如果你在分布式系統(tǒng)中使用了叫榕，擁有你的意見(jiàn)和分析將會(huì)是非常好的浑侥，用其他語(yǔ)言實(shí)現(xiàn)的參考文獻(xiàn)同樣棒極了。
提前感謝晰绎！
Redlock分析
- Martin Kleppmann在這里分析了Redlock寓落，我不同意該分析結(jié)果并且在這里發(fā)表了我對(duì)他的分析結(jié)果的回應(yīng)。
最后
譯文原址
Thanks!
