Redis分布式鎖

參考連結

1. 概述

分布式鎖在很多場景中是非常有用的原語，不同的程序必須以獨占資源的方式實作資源共享就是一個典型的例子。

這個頁面試圖提供一個使用Redis實作分布式鎖的規範算法。我們提出一種算法，叫Redlock,我們認為這種實作比普通的單執行個體實作更安全,我們希望redis社群能幫助分析一下這種實作方法，并給我們提供回報。

2. 實作細節

在我們開始描述算法之前，我們已經有一些可供參考的實作庫.

詳細實作連結

Redlock-rb (Ruby 版). There is also a fork of Redlock-rb that adds a gem for easy distribution and perhaps more.

Redlock-py (Python 版).

Aioredlock (Asyncio Python 版).

Redlock-php (PHP 版).

redlock-php packagist

PHPRedisMutex (further PHP 版)

cheprasov/php-redis-lock (PHP library for locks)

Redsync.go (Go 版).

Redisson (Java 版).

Redis-DistLock (Perl 版).

Redlock-cpp (C++ 版).

Redlock-cs (C#/.NET 版).

RedLock.net (C#/.NET 版). Includes async and lock extension support.

ScarletLock (C# .NET 版 with configurable datastore)

node-redlock (NodeJS 版). Includes support for lock extension.

3. 安全和活性失效保障

按照我們的思路和設計方案，算法隻需具備3個特性就可以實作一個最低保障的分布式鎖。

安全屬性（Safety property） : 獨享（互相排斥）。在任意一個時刻，隻有一個用戶端持有鎖。
活性A(Liveness property A) : 無死鎖。即便持有鎖的用戶端崩潰（crashed)或者網絡被分裂（gets partitioned)，鎖仍然可以被擷取。
活性B(Liveness property B) : 容錯。隻要大部分Redis節點都活着，用戶端就可以擷取和釋放鎖.

3.1 為什麼基于故障轉移的實作還不夠

為了更好的了解我們想要改進的方面，我們先分析一下目前大多數基于Redis的分布式鎖現狀和實作方法.

實作Redis分布式鎖的最簡單的方法就是在Redis中建立一個key，這個key有一個失效時間（TTL)，以保證鎖最終會被自動釋放掉（這個對應特性2）。當用戶端釋放資源(解鎖）的時候，會删除掉這個key。

從表面上看，似乎效果還不錯，但是這裡有一個問題：這個架構中存在一個嚴重的單點失敗問題。如果Redis挂了怎麼辦？

你可能會說，可以通過增加一個slave節點解決這個問題。但這通常是行不通的。這樣做，我們不能實作資源的獨享,因為Redis的主從同步通常是異步的。

3.2 在這種場景（主從結構）中存在明顯的競态

用戶端A從master擷取到鎖
在master将鎖同步到slave之前，master宕掉了。
slave節點被晉級為master節點
用戶端B取得了同一個資源被用戶端A已經擷取到的另外一個鎖。安全失效！

有時候程式就是這麼巧，比如說正好一個節點挂掉的時候，多個用戶端同時取到了鎖。如果你可以接受這種小機率錯誤，那用這個基于複制的方案就完全沒有問題。否則的話，我們建議你實作下面描述的解決方案。

4. 單Redis執行個體實作分布式鎖的正确方法

在嘗試克服上述單執行個體設定的限制之前，讓我們先讨論一下在這種簡單情況下實作分布式鎖的正确做法，實際上這是一種可行的方案，盡管存在競态，結果仍然是可接受的，另外，這裡讨論的單執行個體加鎖方法也是分布式加鎖算法的基礎。

擷取鎖使用指令:

SET resource_name my_random_value NX PX 30000

這個指令僅在不存在

key

的時候才能被執行成功（

NX選項

），并且這個

key

有一個30秒的自動失效時間（

PX屬性

）。這個key的值是

“my_random_value”

(一個随機值），這個值在所有的用戶端必須是唯一的，所有同一

key

的擷取者（競争者）這個值都不能一樣。

value

的值必須是随機數主要是為了更安全的釋放鎖，釋放鎖的時候使用腳本告訴Redis:隻有key存在并且存儲的值和我指定的值一樣才能告訴我删除成功。可以通過以下Lua腳本實作：

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

使用這種方式釋放鎖可以避免删除别的用戶端擷取成功的鎖。舉個例子：用戶端A取得資源鎖，但是緊接着被一個其他操作阻塞了，當用戶端A運作完畢其他操作後要釋放鎖時，原來的鎖早已逾時并且被Redis自動釋放，并且在這期間資源鎖又被用戶端B再次擷取到。如果僅使用DEL指令将key删除，那麼這種情況就會把用戶端B的鎖給删除掉。使用Lua腳本就不會存在這種情況，因為腳本僅會删除value等于用戶端A的value的key（value相當于用戶端的一個簽名）。

這個随機字元串應該怎麼設定？我認為它應該是從/dev/urandom産生的一個20位元組随機數，但是我想你可以找到比這種方法代價更小的方法，隻要這個數在你的任務中是唯一的就行。例如一種安全可行的方法是使用/dev/urandom作為RC4的種子和源産生一個僞随機流;一種更簡單的方法是把以毫秒為機關的unix時間和用戶端ID拼接起來，理論上不是完全安全，但是在多數情況下可以滿足需求.

key的失效時間

，被稱作

“鎖定有效期”

。它不僅是key自動失效時間，而且還是一個用戶端持有鎖多長時間後可以被另外一個用戶端重新獲得。

截至到目前，我們已經有較好的方法擷取鎖和釋放鎖。基于Redis單執行個體，假設這個單執行個體總是可用，這種方法已經足夠安全。現在讓我們擴充一下，假設Redis沒有總是可用的保障。

5. Redlock算法

在Redis的分布式環境中，我們假設有N個Redis master。這些節點完全互相獨立，不存在主從複制或者其他叢集協調機制。之前我們已經描述了在Redis單執行個體下怎麼安全地擷取和釋放鎖。我們確定将在每（N)個執行個體上使用此方法擷取和釋放鎖。在這個樣例中，我們假設有5個Redis master節點，這是一個比較合理的設定，是以我們需要在5台機器上面或者5台虛拟機上面運作這些執行個體，這樣保證他們不會同時都宕掉。

為了取到鎖，用戶端應該執行以下操作:

擷取目前Unix時間，以毫秒為機關。
依次嘗試從N個執行個體，使用相同的key和随機值擷取鎖。在步驟2，當向Redis設定鎖時,用戶端應該設定一個網絡連接配接和響應逾時時間，這個逾時時間應該小于鎖的失效時間。例如你的鎖自動失效時間為10秒，則逾時時間應該在5-50毫秒之間。這樣可以避免伺服器端Redis已經挂掉的情況下，用戶端還在死死地等待響應結果。如果伺服器端沒有在規定時間内響應，用戶端應該盡快嘗試另外一個Redis執行個體。
用戶端使用目前時間減去開始擷取鎖時間（步驟1記錄的時間）就得到擷取鎖使用的時間。當且僅當從大多數（這裡是3個節點）的Redis節點都取到鎖，并且使用的時間小于鎖失效時間時，鎖才算擷取成功。
如果取到了鎖，key的真正有效時間等于有效時間減去擷取鎖所使用的時間（步驟3計算的結果）。
如果因為某些原因，擷取鎖失敗（沒有在至少N/2+1個Redis執行個體取到鎖或者取鎖時間已經超過了有效時間），用戶端應該在所有的Redis執行個體上進行解鎖（即便某些Redis執行個體根本就沒有加鎖成功）。

這個算法是異步的麼?

算法基于這樣一個假設：雖然多個程序之間沒有時鐘同步，但每個程序都以相同的時鐘頻率前進，時間差相對于失效時間來說幾乎可以忽略不計。這種假設和我們的真實世界非常接近：每個計算機都有一個本地時鐘，我們可以容忍多個計算機之間有較小的時鐘漂移。

從這點來說，我們必須再次強調我們的互相排斥規則：隻有在鎖的有效時間（在步驟3計算的結果）範圍内用戶端能夠做完它的工作，鎖的安全性才能得到保證（鎖的實際有效時間通常要比設定的短，因為計算機之間有時鐘漂移的現象）。.

想要了解更多關于需要時鐘漂移間隙的相似系統, 這裡有一個非常有趣的參考: Leases: an efficient fault-tolerant mechanism for distributed file cache consistency.

5.1 失敗時重試

當用戶端無法取到鎖時，應該在一個随機延遲後重試,防止多個用戶端在同時搶奪同一資源的鎖（這樣會導緻腦裂，沒有人會取到鎖）。同樣，用戶端取得大部分Redis執行個體鎖所花費的時間越短，腦裂出現的機率就會越低（必要的重試），是以，理想情況一下，用戶端應該同時（并發地）向所有Redis發送SET指令。

需要強調，當用戶端從大多數Redis執行個體擷取鎖失敗時，應該盡快地釋放（部分）已經成功取到的鎖，這樣其他的用戶端就不必非得等到鎖過完“有效時間”才能取到（然而，如果已經存在網絡分裂，用戶端已經無法和Redis執行個體通信，此時就隻能等待key的自動釋放了，等于被懲罰了）。

5.2 釋放鎖

釋放鎖比較簡單，向所有的Redis執行個體發送釋放鎖指令即可，不用關心之前有沒有從Redis執行個體成功擷取到鎖.

5.3 安全争議

這個算法安全麼？我們可以從不同的場景讨論一下。

讓我們假設用戶端從大多數Redis執行個體取到了鎖。所有的執行個體都包含同樣的key，并且key的有效時間也一樣。然而，key肯定是在不同的時間被設定上的，是以key的失效時間也不是精确的相同。我們假設第一個設定的key時間是 T1 (開始向第一個server發送指令前時間），最後一個設定的key時間是 T2 (得到最後一台server的答複後的時間），我們可以确認，第一個server的key至少會存活 MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT 。所有其他的key的存活時間，都會比這個key時間晚，是以可以肯定，所有key的失效時間至少是 MIN_VALIDITY 。
當大部分執行個體的key被設定後，其他的用戶端将不能再取到鎖，因為至少N/2+1個執行個體已經存在key。是以，如果一個鎖被（用戶端）擷取後，用戶端自己也不能再次申請到鎖(違反互相排斥屬性）。
然而我們也想確定，當多個用戶端同時搶奪一個鎖時不能兩個都成功。
如果用戶端在擷取到大多數redis執行個體鎖，使用的時間接近或者已經大于失效時間，用戶端将認為鎖是失效的鎖，并且将釋放掉已經擷取到的鎖，是以我們隻需要在有效時間範圍内擷取到大部分鎖這種情況。在上面已經讨論過有争議的地方，在 MIN_VALIDITY 時間内，将沒有用戶端再次取得鎖。是以隻有一種情況，多個用戶端會在相同時間取得N/2+1執行個體的鎖，那就是取得鎖的時間大于失效時間（TTL time)，這樣取到的鎖也是無效的.

如果你能提供關于現有的類似算法的一個正式證明（指出正确性），或者是發現這個算法的bug？我們将非常感激.

5.4 活性争議

系統的活性安全基于三個主要特性:

鎖的自動釋放（因為key失效了）：最終鎖可以再次被使用.
用戶端通常會将沒有擷取到的鎖删除，或者鎖被取到後，使用完後，用戶端會主動（提前）釋放鎖，而不是等到鎖失效另外的用戶端才能取到鎖。.
當用戶端重試擷取鎖時，需要等待一段時間，這個時間必須大于從大多數Redis執行個體成功擷取鎖使用的時間，以最大限度地避免腦裂。.

然而，當網絡出現問題時系統在失效時間(TTL)内就無法服務，這種情況下我們的程式就會為此付出代價。如果網絡持續的有問題，可能就會出現死循環了。這種情況發生在當用戶端剛取到一個鎖還沒有來得及釋放鎖就被網絡隔離.

如果網絡一直沒有恢複，這個算法會導緻系統不可用.

5.5 性能，崩潰恢複和Redis同步

很多使用者把Redis當做分布式鎖伺服器，使用擷取鎖和釋放鎖的響應時間，每秒鐘可用執行多少次 acquire / release 操作作為性能名額。為了達到這一要求，增加Redis執行個體當然可用降低響應延遲（沒有錢買硬體的”窮人”,也可以在網絡方面做優化，使用非阻塞模型，一次發送所有的指令，然後異步的讀取響應結果，假設用戶端和redis伺服器之間的RTT都差不多。

然而，如果我們想使用可以從備份中恢複的redis模式，有另外一種持久化情況你需要考慮，

我們考慮這樣一種場景，假設我們的redis沒用使用備份。一個用戶端擷取到了3個執行個體的鎖。此時，其中一個已經被用戶端取到鎖的redis執行個體被重新開機，在這個時間點，就可能出現3個節點沒有設定鎖，此時如果有另外一個用戶端來設定鎖，鎖就可能被再次擷取到，這樣鎖的互相排斥的特性就被破壞掉了。

如果我們啟用了AOF持久化，情況會好很多。我們可用使用

SHUTDOWN

指令關閉然後再次重新開機。因為Redis到期是語義上實作的，是以當伺服器關閉時，實際上還是經過了時間，所有（保持鎖）需要的條件都沒有受到影響. 沒有受到影響的前提是redis優雅的關閉。停電了怎麼辦？如果redis是每秒執行一次fsync，那麼很有可能在redis重新開機之後，key已經丢棄。理論上，如果我們想在Redis重新開機地任何情況下都保證鎖的安全，我們必須開啟fsync=always的配置。這反過來将完全破壞與傳統上用于以安全的方式實作分布式鎖的同一級别的CP系統的性能.

然而情況總比一開始想象的好一些。當一個redis節點重新開機後，隻要它不參與到任意目前活動的鎖，沒有被當做“目前存活”節點被用戶端重新擷取到,算法的安全性仍然是有保障的。

為了達到這種效果，我們隻需要将新的redis執行個體，在一個TTL時間内，對用戶端不可用即可，在這個時間内，所有用戶端鎖将被失效或者自動釋放.

使用延遲重新開機可以在不采用持久化政策的情況下達到同樣的安全，然而這樣做有時會讓系統轉化為徹底不可用。比如大部分的redis執行個體都崩潰了，系統在TTL時間内任何鎖都将無法加鎖成功。

Redis分布式鎖