Redis分布式鎖
[TOC]
在許多環(huán)境中晦嵌，分布式鎖是一種非常有用的原語，其中不同的進(jìn)程必須以互斥的方式與共享資源一起運(yùn)行泥耀。
有許多庫和博客文章描述了如何使用Redis實(shí)現(xiàn)DLM（分布式鎖管理器）碎浇，但是每個庫都使用不同的方法力惯，并且許多庫使用簡單的方法，它們與稍微復(fù)雜的方法相比死讹，也可以實(shí)現(xiàn)低保證的設(shè)計瞒滴。
此頁面試圖提供一種更規(guī)范的算法來使用Redis實(shí)現(xiàn)分布式鎖。 我們提出了一種稱為Redlock的算法赞警，它實(shí)現(xiàn)了一種我們認(rèn)為比vanilla單實(shí)例方法更安全的DLM妓忍。 我們希望社區(qū)將對其進(jìn)行分析，提供反饋愧旦，并將其作為實(shí)現(xiàn)更復(fù)雜或替代設(shè)計的起點(diǎn)世剖。
安全和活力保證
我們將僅使用三個屬性對我們的設(shè)計進(jìn)行建模，從我們的角度來看笤虫，這些屬性是有效使用分布式鎖所需的最低保證搁廓。
- 安全屬性：相互排斥引颈。 在任何給定時刻，只有一個客戶端可以持有鎖境蜕。
- 活力屬性A：無死鎖蝙场。即使鎖定資源的客戶端崩潰或被分區(qū)， 也始終可以獲取鎖粱年。
- 活力屬性B：容錯售滤。 只要大多數(shù)Redis節(jié)點(diǎn)啟動，客戶端就能夠獲取和釋放鎖台诗。
為什么基于故障轉(zhuǎn)移的實(shí)現(xiàn)還不夠完箩？
為了理解我們想要改進(jìn)的內(nèi)容，讓我們分析大多數(shù)基于Redis的分布式鎖庫的現(xiàn)狀拉队。
使用Redis鎖定資源的最簡單方法是在實(shí)例中創(chuàng)建key弊知。 key通常使用Redis過期功能在有限的生存時間內(nèi)存活，因此最終它將被釋放（我們列表中的屬性2）粱快。 當(dāng)客戶端需要釋放資源時秩彤，它會刪除key。
表面上看事哭，這很有效漫雷，但存在一個問題：那就是我們架構(gòu)中的單點(diǎn)故障。 如果Redis master出現(xiàn)故障會怎樣鳍咱？ 好吧降盹，讓我們添加一個slave！ 如果master服務(wù)器不可用谤辜，就是用這個slave蓄坏。 遺憾的是，這并不可行丑念。 因?yàn)檫@樣做剑辫，我們無法實(shí)現(xiàn)互斥的安全屬性，因?yàn)镽edis復(fù)制是異步的渠欺。
這個模型有明顯的競爭條件：
- 客戶端A獲取master服務(wù)器中的鎖妹蔽。
- 在寫入key之前，master崩潰并發(fā)送到slave挠将。
- Slave被提升為master胳岂。
- 客戶端B獲取與A已經(jīng)擁有鎖的相同資源的鎖。 安全違例舔稀！
有時在特殊情況下乳丰，例如在故障期間，多個客戶端可以同時持有鎖内贮，這是完全正常的产园。 如果是這種情況汞斧，您可以使用基于復(fù)制的解決方案。 否則什燕，我們建議實(shí)施本文檔中描述的解決方案粘勒。
單個實(shí)例的正確實(shí)現(xiàn)
在嘗試克服上述單實(shí)例設(shè)置的限制之前，讓我們在這個簡單的情況下檢查如何正確地執(zhí)行它屎即，因?yàn)檫@實(shí)際上是一個可行的解決方案庙睡，在不時可以接受競爭條件的應(yīng)用程序中，并且因?yàn)殒i定到單個實(shí)例是我們描述的分布式算法的基礎(chǔ)技俐。
要獲得鎖乘陪，可以采用以下方法：
SET resource_name my_random_value NX PX 30000
該命令僅在key尚不存在時才設(shè)置成功（NX選項），到期時間為30000毫秒（PX選項）雕擂。 值設(shè)置為“my_random_value”啡邑。 此值必須在所有客戶端和所有鎖定請求中都是唯一的。如果值設(shè)置成功井赌，則表明獲取到鎖（設(shè)置成功返回1）谤逼，否者視為獲取鎖不成功（返回0）。
使用隨機(jī)值是為了以安全的方式釋放鎖族展，使用一個腳本告訴Redis：只有當(dāng)key存在并且key中存儲的值正是我期望的那個時才刪除密鑰。 該Lua腳本為：
if redis.call("get",KEYS[1]) == ARGV[1] then
return redis.call("del",KEYS[1])
else
return 0
end
這一點(diǎn)很重要拔鹰，以避免刪除由另一個客戶端創(chuàng)建的鎖仪缸。 例如，某個客戶端獲取了鎖列肢，在執(zhí)行某些操作時花費(fèi)的時間長于鎖的有效時間（key的有效時間）恰画，稍后移除已經(jīng)由某個其他客戶端獲取的鎖。 僅使用DEL是不安全的瓷马，因?yàn)樵摽蛻舳丝赡軙h除另一個客戶端持有的鎖拴还。 使用上面的腳本而不是每個鎖都使用隨機(jī)字符串“簽名”，因此只有在客戶端嘗試刪除鎖時欧聘，鎖才會被刪除片林。
這個隨機(jī)字符串應(yīng)該是什么？ 我假設(shè)它是來自/dev/urandom的20個字節(jié)怀骤，但是你可以找到更好的方法來唯一標(biāo)識你要執(zhí)行的任務(wù)费封。 例如，安全選擇是使用/dev/urandom對RC4進(jìn)行種子處理蒋伦，并從中生成偽隨機(jī)流弓摘。 一個更簡單的解決方案是使用unix時間和微秒分辨率的組合，將其與客戶端ID連接起來痕届，它不是那么安全韧献，但可能在大多數(shù)環(huán)境中都可以完成任務(wù)末患。
我們用作key存活的時間被稱為“鎖有效時間”。 它既是自動釋放鎖的時間锤窑，也是客戶端為了執(zhí)行操作所需的時間璧针，而另一個客戶端可能能夠再次獲取鎖，而不會在技術(shù)上違反互斥保證果复，這僅限于從獲得鎖定的那一刻起的時間的給定窗口陈莽。
所以現(xiàn)在我們有了獲得和釋放鎖的好方法。 系統(tǒng)推理由單個始終可用的實(shí)例組成的非分布式系統(tǒng)是安全的虽抄。 讓我們將概念擴(kuò)展到我們沒有這種保證的分布式系統(tǒng)走搁。
Redlock算法
在算法的分布式版本中，我們假設(shè)我們有N個Redis主機(jī)迈窟。 這些節(jié)點(diǎn)完全獨(dú)立私植，因此我們不使用復(fù)制或任何其他隱式方式協(xié)調(diào)系統(tǒng)。 我們已經(jīng)描述了如何在單個實(shí)例中安全地獲取和釋放鎖车酣。 我們理所當(dāng)然地認(rèn)為算法將使用此方法在單個實(shí)例中獲取和釋放鎖曲稼。 在我們的示例中，我們設(shè)置N = 5湖员，這是一個合理的值贫悄，因此我們需要在不同的計算機(jī)或虛擬機(jī)上運(yùn)行5個Redis主服務(wù)器，以確保它們以大多數(shù)獨(dú)立的方式失敗娘摔。
為了獲取鎖窄坦，客戶端執(zhí)行以下操作：
- 它以毫秒為單位獲取當(dāng)前時間。
- 它嘗試按順序獲取所有N個實(shí)例中的鎖凳寺，在所有實(shí)例中使用相同的鍵名和隨機(jī)值鸭津。 在步驟2期間，當(dāng)在每個實(shí)例中set鎖時肠缨，客戶端需要設(shè)置超時時間逆趋，該超時時間小于鎖的自動釋放時間，也就是鎖的過期時間晒奕。 例如闻书，如果自動釋放時間是10秒，則超時可以在~5-50毫秒范圍內(nèi)脑慧。 這可以防止客戶端試圖與Redis節(jié)點(diǎn)進(jìn)行通信時長時間保持阻塞惠窄，如果該實(shí)例不可用，我們應(yīng)該嘗試盡快與下一個實(shí)例通信漾橙。
- 客戶端通過從當(dāng)前時間中減去在步驟1中獲得的時間戳來計算獲取鎖所需的時間杆融。當(dāng)且僅當(dāng)客戶端能夠在大多數(shù)實(shí)例中獲取鎖定時（至少3個） 并且獲取鎖定所經(jīng)過的總時間小于鎖定有效時間，認(rèn)為鎖被獲取霜运。
- 如果獲得了鎖脾歇，則其有效時間被認(rèn)為是初始有效時間減去經(jīng)過的時間蒋腮，如步驟3中計算的那樣。
- 如果客戶端由于某種原因（無法鎖定N / 2 + 1實(shí)例或有效時間為負(fù)）未能獲取鎖定藕各，它將嘗試解鎖所有實(shí)例池摧。
算法是異步的嗎？
算法依賴于這樣的假設(shè)激况，即雖然進(jìn)程中沒有同步時鐘作彤，但每個進(jìn)程中的本地時間仍然大致以相同的速率流動，這種時鐘誤差與鎖的自動釋放時間相比較小乌逐。 這個假設(shè)與現(xiàn)實(shí)世界的計算機(jī)非常相似：每臺計算機(jī)都有一個本地時鐘竭讳，我們通常可以依靠不同的計算機(jī)來獲得較小的時鐘漂移浙踢。
此時我們需要更好地指定我們的互斥規(guī)則：只要持有鎖的客戶端將在鎖定有效時間內(nèi)（如步驟3中獲得）終止其工作绢慢，減去一些時間（僅幾毫秒），它就能補(bǔ)償進(jìn)程之間的時鐘漂移洛波。
重試失敗
當(dāng)客戶端無法獲取鎖時胰舆，它應(yīng)該在隨機(jī)延遲后再次嘗試獲取鎖，這樣做是為了和多個同時嘗試獲取鎖的客戶端同步（這可能會導(dǎo)致大腦裂情況發(fā)生蹬挤，從而使得任何一個示例都無法獲取到鎖）缚窿。此外，客戶端嘗試在大多數(shù)Redis實(shí)例中獲取鎖的速度越快焰扳，腦裂條件的窗口越芯肓恪（需要重試），因此理想情況下客戶端應(yīng)嘗試將SET命令發(fā)送到N個實(shí)例同時使用多路復(fù)用蓝翰。
值得強(qiáng)調(diào)的是光绕，對于未能獲得大多數(shù)鎖定的客戶來說女嘲，盡快釋放（部分）獲取的鎖定是多么重要畜份，這樣就不需要等待key到期以便再次獲取鎖（但是，如果發(fā)生網(wǎng)絡(luò)分區(qū)且客戶端無法再與Redis實(shí)例通信欣尼，則在等待key到期時需要支付可用性懲罰爆雹。
釋放鎖
釋放鎖是很簡單的，只需在所有實(shí)例中釋放鎖愕鼓，無論客戶端是否認(rèn)為它能夠成功鎖定給定實(shí)例钙态。
安全論據(jù)
算法安全嗎？ 我們可以嘗試了解不同場景中會發(fā)生什么菇晃。
首先讓我們假設(shè)客戶端能夠在大多數(shù)情況下獲取鎖册倒。所有實(shí)例都將包含一個生存時間相同的key。 但是磺送，key設(shè)置在不同的時間驻子，因此key也將在不同的時間到期灿意。 但是如果第一個key在時間T1設(shè)置為最差（我們在聯(lián)系第一個服務(wù)器之前采樣的時間），并且最后一個key在時間T2設(shè)置為最差（我們從最后一個服務(wù)器獲得回復(fù)的時間）崇呵，我們確定在集合中到期的第一個key將至少存在于MIN_VALIDITY = TTL-（T2-T1）-CLOCK_DRIFT缤剧。 所有其他key將在稍后到期，因此我們確信key將至少同時設(shè)置為此時間域慷。
在設(shè)置大多數(shù)密鑰期間荒辕，另一個客戶端將無法獲取鎖定，因?yàn)槿绻汛嬖?code>N/2+1個key犹褒，則N/2+1 SET NX操作不能成功抵窒。 因此，如果獲得鎖化漆，則無法同時重新獲取鎖定（違反互斥屬性）估脆。
但是，我們還希望確保同時嘗試獲取鎖的多個客戶端不能同時成功座云。
如果客戶端使用的時間接近或大于鎖定最大有效時間（我們基本上用于SET的TTL）鎖定大多數(shù)實(shí)例疙赠，則會認(rèn)為鎖定無效并將解鎖實(shí)例，因此我們只需要考慮 客戶端能夠在小于有效時間的時間內(nèi)鎖定大多數(shù)實(shí)例的情況朦拖。 在這種情況下圃阳，對于上面已經(jīng)表達(dá)的參數(shù)，對于MIN_VALIDITY璧帝，沒有客戶端應(yīng)該能夠重新獲取鎖捍岳。 因此，只有當(dāng)鎖定多數(shù)的時間大于TTL時間時睬隶，多個客戶端才能同時鎖定N / 2 + 1實(shí)例（“時間”是步驟2的結(jié)束）锣夹，從而使鎖無效。
活躍的論點(diǎn)
系統(tǒng)活躍度基于三個主要特征：
- 鎖的自動釋放（因?yàn)閗ey到期）：最終可以再次鎖定key苏潜。
- 通常银萍，當(dāng)沒有獲得鎖定時，或者當(dāng)獲取鎖定并且工作終止時恤左，客戶通常會合作移除鎖定贴唇，這使得我們可能不必等待key到期以重新獲取鎖。
- 事實(shí)上飞袋，當(dāng)客戶端需要重試鎖定時戳气，它等待的時間比獲取大多數(shù)鎖定所需的時間要大得多，以便在資源爭用期間不可能出現(xiàn)腦裂狀況巧鸭。
但是瓶您，我們在網(wǎng)絡(luò)分區(qū)上支付的可用性罰款等于TTL時間，因此如果有連續(xù)分區(qū)，我們可以無限期地支付此罰款呀袱。 每次客戶端獲取鎖定并在能夠刪除鎖定之前進(jìn)行分區(qū)時芯肤，都會發(fā)生這種情況。
基本上压鉴，如果存在無限的連續(xù)網(wǎng)絡(luò)分區(qū)崖咨，則系統(tǒng)可能在無限長的時間內(nèi)不可用。
性能油吭，崩潰恢復(fù)和fsync
使用Redis作為鎖服務(wù)器的許多用戶在獲取和釋放鎖的延遲以及每秒可執(zhí)行的獲取/釋放操作的數(shù)量方面需要高性能击蹲。 為了滿足這一要求，與N個Redis服務(wù)器通信以減少延遲的策略肯定是多路復(fù)用（或者是簡單多路復(fù)用婉宰，即將套接字置于非阻塞模式歌豺，發(fā)送所有命令，并讀取所有命令以后心包，假設(shè)客戶端和每個實(shí)例之間的RTT相似）类咧。
但是，如果我們想要定位崩潰恢復(fù)系統(tǒng)模型蟹腾，還有另一個關(guān)于持久性的考慮因素痕惋。
基本上要看到這里的問題，讓我們假設(shè)我們根本沒有持久性配置Redis娃殖。 客戶端在5個實(shí)例中的3個中獲取鎖定值戳。 重新啟動客戶端能夠獲取鎖的實(shí)例之一，此時還有3個實(shí)例可以鎖定同一資源炉爆，而另一個客戶端可以再次鎖定它堕虹，違反了鎖獨(dú)占的安全屬性。
如果我們啟用AOF持久性芬首，事情會有所改善赴捞。例如，我們可以通過發(fā)送SHUTDOWN并重新啟動它來升級服務(wù)器郁稍。因?yàn)镽edis過期是在語義上實(shí)現(xiàn)的赦政，所以當(dāng)服務(wù)器關(guān)閉時，實(shí)際上時間仍然過去艺晴，我們所有的要求都很好昼钻。但是一切都很好掸屡，只要它是一個干凈的關(guān)閉封寞。停電怎么樣？如果默認(rèn)情況下將Redis配置為每秒在磁盤上進(jìn)行fsync仅财，則重新啟動后可能會丟失密鑰狈究。理論上，如果我們想要在任何類型的實(shí)例重啟時保證鎖定安全性盏求，我們需要在持久性設(shè)置中始終啟用fsync =抖锥。反過來亿眠，這將完全毀掉傳統(tǒng)上用于以安全方式實(shí)現(xiàn)分布式鎖的CP系統(tǒng)的性能。
然而磅废，事情比第一眼看起來更好纳像。基本上拯勉，只要實(shí)例在崩潰后重新啟動時竟趾，它就會保留算法安全性，它不再參與任何當(dāng)前活動的鎖宫峦，因此當(dāng)實(shí)例重新啟動時岔帽，當(dāng)前活動鎖的集合都是通過鎖定除了實(shí)例之外的實(shí)例獲得的。這是重新加入系統(tǒng)导绷。
為了保證這一點(diǎn)犀勒，我們只需要在崩潰后創(chuàng)建一個實(shí)例，至少比我們使用的最大TTL少一點(diǎn)妥曲，也就是說贾费，實(shí)例崩潰時存在的所有鎖所需的時間，到 變?yōu)闊o效并自動釋放檐盟。
使用延遲重啟基本上可以實(shí)現(xiàn)安全性铸本，即使沒有任何可用的Redis持久性，但請注意遵堵，這可能轉(zhuǎn)化為可用性懲罰箱玷。 例如，如果大多數(shù)實(shí)例崩潰陌宿，系統(tǒng)將變?yōu)槿植豢捎糜赥TL（這里全局意味著在此期間根本沒有資源可鎖定）锡足。
使算法更可靠：擴(kuò)展鎖
如果客戶端執(zhí)行的工作由小步驟組成，則默認(rèn)情況下可以使用較小的鎖定有效時間壳坪，并擴(kuò)展實(shí)現(xiàn)鎖定擴(kuò)展機(jī)制的算法舶得。 基本上客戶端，如果在鎖定有效性接近低值的情況下處于計算中間爽蝴，則可以通過向所有擴(kuò)展密鑰的TTL的實(shí)例發(fā)送Lua腳本來擴(kuò)展鎖定（如果密鑰存在且其值仍然是 獲取鎖定時客戶端分配的隨機(jī)值沐批。
如果能夠?qū)㈡i擴(kuò)展到大多數(shù)實(shí)例，并且在有效時間內(nèi)（基本上使用的算法與獲取鎖時使用的算法非常相似）蝎亚，客戶端應(yīng)該只考慮重新獲取的鎖九孩。
但是，這在技術(shù)上不會更改算法发框，因此應(yīng)限制鎖定重新獲取嘗試的最大次數(shù)躺彬，否則會違反其中一個活動屬性。
