-----------------
更新：此演算法目前已收錄於 Redis 官方文件，請見 => http://redis.io/topics/distlock。本文保留為舊版內容，後續更新將直接反映於 Redis 文件中。
-----------------

許多人使用 Redis 來實作分散式鎖。許多人認為這是一個非常好的應用場景，Redis 很好地解決了原本難以解決的問題。也有人認為這是完全錯誤、不安全且不適合 Redis 的用法。

基本上，兩方都是對的。分散式鎖若要同時確保安全，又要求高可用性，讓 Redis 節點即使當機，客戶端仍能取得與釋放鎖，就並非易事。同時，一個快速的鎖管理器卻能解決大量在實務上原本難以處理的問題，而且有時候一個遠稱不上完美的解決方案，也勝過一個非常緩慢的方案。

我們能否同時擁有一個基於 Redis 且既快速又可靠的系統呢？這篇部落格文章就是對此領域的探索。我將嘗試描述一個使用 N 個 Redis 實例來實現分散式可靠鎖的簡單演算法提案，希望社群能協助分析與評論這個演算法，看看它是否是一個可行的候選方案。

# 我們真正想要的是什麼？

在談論分散式系統時，若不先闡明我們想要的安全性（safety）與活性（liveness）屬性，基本上是沒有意義的，因為只有當這兩項需求被明確定義後，才有可能檢驗設計是否正確，也才能讓他人分析並找出設計中的錯誤。我們將僅用三個屬性來為設計建模，我認為這是有效使用分散式鎖所需的最基本保證。

1) 安全性屬性：互斥（Mutual exclusion）。在任何給定時刻，只有一個客戶端能持有鎖。

2) 活性屬性 A：無死結（Deadlock free）。最終一定能夠取得鎖，即使鎖定資源的客戶端當機或發生網路分割亦然。

3) 活性屬性 B：容錯性（Fault tolerance）。只要多數 Redis 節點仍正常運作，客戶端就能夠取得與釋放鎖。

# 分散式鎖的簡易做法

為了理解我們想要改進什麼，讓我們先分析一下現狀。

使用 Redis 鎖定資源最簡單的方式，是在單一實例中建立一個鍵（key）。這個鍵通常會透過 Redis 的過期（expires）功能設定有限的存活時間（time to live），使它最終無論如何都會被釋放（符合我們清單中的第 2 點）。當客戶端需要釋放資源時，就刪除該鍵。

表面上這運作得很好，但有一個問題：這在我們的架構中是單點故障。如果 Redis 主節點當機會發生什麼事？
好吧，加一個從節點！在主節點無法使用時就改用它。但不幸的是這並不可行。這麼做我們就無法實現互斥的安全性保證，因為 Redis 的複寫是非同步的。

這種模型存在一個明顯的競爭條件（race condition）：

1) 客戶端 A 在主節點上取得鎖。

2) 主節點在將寫入該鍵的操作傳送給從節點之前就當機。

3) 從節點被提升為主節點。

4) 客戶端 B 對同一個資源取得鎖，而該資源其實已被 A 持有鎖。<- 違反安全性！

有時候，在特殊情況下，例如故障期間，多個客戶端同時持有鎖是完全可以接受的。
如果是這種情況，請就此打住，繼續享用你那基於複寫的解決方案。否則，請繼續閱讀，看看一個有望更安全的實作方式。

# 首先，在單一實例上正確地實作

在嘗試克服上述單一實例架構的限制之前，讓我們先看看在這種簡單情況下如何正確地實作，因為這在偶爾發生競爭條件仍可接受的應用中，本身就是一個可行的解決方案，而且在單一實例中加鎖也是本文所述分散式演算法的基礎。

要取得鎖，正確的做法如下：

SET resource_name my_random_value NX PX 30000

此命令只有在鍵不存在時才會設定該鍵（NX 選項），並設定 30000 毫秒的過期時間（PX 選項）。
該鍵的值被設為「my_random_value」。這個值在所有客戶端與所有加鎖請求之間必須是唯一的。

基本上，這個隨機值是用來以安全的方式釋放鎖，透過一個腳本告訴 Redis：只有在鍵存在且鍵中儲存的值恰好等於我預期的值時，才刪除該鍵。這可透過以下的 Lua 腳本達成：

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

這對於避免刪除由其他客戶端建立的鎖非常重要。例如，某個客戶端可能取得鎖，在某個操作中被阻塞的時間超過了鎖的有效時間（即鍵過期的時間），之後又去刪除鎖，而該鎖其實已被其他客戶端取得。
僅使用 DEL 是不安全的，因為客戶端可能會刪除另一個客戶端的鎖。相反地，使用上述腳本後，每個鎖都會用一個隨機字串「簽署」，因此只有當鎖仍然是當初嘗試刪除它的客戶端所設定的那一把時，才會被移除。

這個隨機字串應該是什麼？我假設它是來自 /dev/urandom 的 20 個位元組，但你也可以找到更省成本的方式來為你的任務產生足夠唯一的字串。
例如，一個安全的選擇是以 /dev/urandom 作為種子來初始化 RC4，再從中產生擬隨機串流。
更簡單的方案是使用具微秒精度的 Unix 時間戳記，再串接上客戶端 ID，雖然安全性沒那麼高，但在大多數環境中應該已足夠應付需求。

我們用來作為鍵存活時間的時間，被稱為「鎖有效時間」。它既是自動釋放時間，也是客戶端在另一個客戶端可能再次取得鎖之前，必須完成所需操作的時間，而這並不會在技術上違反互斥保證，因為互斥保證僅限於從取得鎖的那一刻起算的特定時間窗口內。

所以現在我們已經有了取得與釋放鎖的良好方法。以由單一、永遠可用的實例所組成的非分散式系統而言，這個系統是安全的。接下來讓我們將此概念擴展到沒有此類保證的分散式系統中。

# 分散式版本

在演算法的分散式版本中，我們假設有 N 個 Redis 主節點。這些節點完全獨立，因此我們不使用複寫或任何其他隱含的協調系統。我們已經描述過如何在單一實例中安全地取得與釋放鎖。我們假定演算法將使用此方法在單一實例中取得與釋放鎖。在我們的範例中，我們設定 N=5，這是一個合理的值，因此我們需要在不同的電腦或虛擬機器上運行 5 個 Redis 主節點，以確保它們會以大多數獨立的方式失效。

為了取得鎖，客戶端執行以下操作：

步驟 1）取得當前的毫秒級時間。

步驟 2）依序嘗試在全部 N 個實例中取得鎖，在所有實例中使用相同的鍵名與隨機值。

在步驟 2 中，當在每個實例中設定鎖時，客戶端會使用一個相較於總鎖自動釋放時間而言很小的逾時時間來嘗試取得。
例如，若自動釋放時間為 10 秒，逾時時間可以落在約 5 至 50 毫秒的範圍內。
這可防止客戶端在嘗試與當機的 Redis 節點通訊時被長時間阻塞：若某個實例無法使用，我們應盡快嘗試與下一個實例通訊。

步驟 3）客戶端透過將當前時間減去在步驟 1 中取得的時間戳記，來計算取得鎖所經過的時間。
若且唯若客戶端能夠在多數實例（至少 3 個）中取得鎖，且取得鎖所經過的總時間小於鎖的有效時間，該鎖才被視為取得成功。

步驟 4）若鎖已取得，其有效時間則被視為初始有效時間減去在步驟 3 中計算出的經過時間。

步驟 5）若客戶端因故未能取得鎖（無論是無法鎖定 N/2+1 個實例，或有效時間為負值），它將嘗試解鎖所有實例（即使是它認為未能成功加鎖的實例）。

# 是同步還是非同步？

基本上，此演算法是部分同步的：它依賴於一個假設，即雖然行程之間沒有同步的時鐘，但每個行程中的本地時間仍以大致相同的速率推進，其誤差相較於鎖的自動釋放時間而言很小。這個假設非常貼近真實世界的電腦：每台電腦都有本地時鐘，而我們通常可以依賴不同電腦之間的時鐘漂移（drift）很小。

此外，我們需要更精確地定義互斥規則：只有當持有鎖的客戶端在鎖的有效時間（即在步驟 3 中取得的時間）內完成其工作，再減去一些時間（為了補償行程間時鐘漂移的數毫秒）時，互斥性才有保證。

# 重試

當客戶端無法取得鎖時，應在隨機延遲後重試，以便讓多個同時嘗試對同一資源取得鎖的客戶端去同步化（否則可能導致沒有人獲勝的腦裂（split brain）狀況）。此外，客戶端越快在多數 Redis 實例中嘗試取得鎖，發生腦裂狀況的窗口就越小（也就越不需要重試），因此理想上客戶端應嘗試使用多工（multiplexing）同時對 N 個實例發送 SET 命令。

值得強調的是，對於未能取得多數鎖的客戶端而言，盡快釋放（部分）已取得的鎖非常重要，這樣就不需要等待鍵過期才能再次取得鎖（然而，若發生網路分割且客戶端已無法再與 Redis 實例通訊，就必須付出可用性的代價，等待過期）。

# 釋放鎖

釋放鎖很簡單，只需在所有實例中釋放鎖，無論客戶端是否認為自己已成功鎖定該特定實例。

# 安全性論證

這個系統安全嗎？我們可以試著理解在不同情境下會發生什麼。

首先，假設客戶端能夠在多數實例中取得鎖。所有實例都將包含一個具有相同存活時間的鍵。然而，該鍵是在不同時間點設定的，因此這些鍵也會在不同時間過期。不過，若第一個鍵最晚在時間 T1 被設定（即我們在聯繫第一台伺服器前取樣的時間），而最後一個鍵最晚在時間 T2 被設定（即我們收到最後一台伺服器回應的時間），我們可以確定集合中最早過期的鍵至少會存在 MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT 的時間。所有其他鍵會更晚才過期，因此我們可以確定這些鍵至少會同時存在這段時間。

在多數鍵被設定的這段期間，另一個客戶端將無法取得鎖，因為若已有 N/2+1 個鍵存在，N/2+1 個 SET NX 操作不可能同時成功。因此，若某把鎖已被取得，就不可能在同一時間被重新取得（違反互斥屬性）。

然而，我們也想確保多個同時嘗試取得鎖的客戶端不會同時成功。

若某個客戶端使用接近或大於鎖最大有效時間（基本上就是我們用於 SET 的 TTL）的時間來鎖定多數實例，它會認為該鎖無效並將解鎖這些實例，因此我們只需考慮客戶端能夠在小於有效時間內鎖定多數實例的情況。在此情況下，根據上述論證，在 MIN_VALIDITY 期間內，沒有任何客戶端應能重新取得鎖。因此，多個客戶端能夠同時鎖定 N/2+1 個實例（此處的「同時」指的是步驟 2 結束時的時間），只有當鎖定多數實例所需的時間大於 TTL 時間，導致鎖變為無效時才有可能。

你能提供形式化的安全性證明，或找出其中的錯誤嗎？若能提供，將非常感激。

# 活性論證

系統的活性基於三個主要特性：

1) 鎖的自動釋放（因為鍵會過期）：最終鍵會再次變為可鎖定狀態。

2) 客戶端通常會協作清除鎖，無論是在未取得鎖時，或是在已取得鎖且工作完成時，使得我們很可能不需要等待鍵過期就能重新取得鎖。

3) 當客戶端需要重試鎖時，它會等待一段時間，該時間相較於取得多數鎖所需的時間而言相對較長，以便在機率上讓資源競爭期間發生腦裂狀況的可能性降低。

然而，至少存在一種情境，即一種非常特殊的網路分割／重連模式若無限重複，可能會破壞系統的可用性。
例如，當 N=5 時，兩個客戶端 A 與 B 可能同時嘗試鎖定同一資源，沒有人能取得多數鎖，但若將 A 與 B 的鎖加總起來，卻可能鎖定了多數節點（例如客戶端 A 鎖定了 2 個實例，客戶端 B 僅鎖定了 1 個實例）。
接著客戶端在能夠解鎖已鎖定的實例之前就被分割隔離。這將導致該資源在一段約等於自動釋放時間的期間內無法被鎖定。接著當鍵過期時，兩個客戶端 A 與 B 再次加入分割並重複相同的模式，如此無限循環下去。

從另一個角度來看上述問題，我們在網路分割時付出了等於「TTL」時間的可用性代價，因此若持續發生分割，我們就可能無限期地付出此一代價。

我找不到一個簡單的方法來保證活性（但老實說也沒有非常努力地嘗試），不過最糟的情況似乎很難被觸發。
基本上，這意味著使用此演算法，我們只能提供對第 2 項屬性的一個近似保證。

# 效能、當機復原與 fsync

許多將 Redis 用作鎖伺服器的使用者，需要在取得與釋放鎖的延遲，以及每秒可執行的取得／釋放操作數量方面具備高效能。為了滿足此需求，與 N 台 Redis 伺服器通訊以降低延遲的策略，絕對是多工（或簡易的多工，也就是將通訊端設為非阻塞模式，發送所有命令後再一次讀取所有回應，假設客戶端與每個實例之間的 RTT 相似）。

然而，若我們想針對當機復原（crash-recovery）系統模型，還有另一個關於持久化的考量。

基本上，要看出此處的問題，讓我們假設我們完全未設定 Redis 持久化。某個客戶端在 5 個實例中的 3 個上取得鎖。其中一個成功取得鎖的實例重新啟動，此時我們又再次有 3 個實例可以對同一資源加鎖，而另一個客戶端就能再次鎖定它，違反了鎖互斥的安全性屬性。

若我們啟用 AOF 持久化，情況會好得多。例如，我們可以透過發送 SHUTDOWN 並重新啟動伺服器來升級伺服器。由於 Redis 的過期在語意上是以虛擬方式實作的，即使伺服器關閉，時間仍會繼續流逝，因此我們所有的需求都能被滿足。
然而，一切正常的前提是乾淨地關機。那若是斷電呢？若 Redis 如預設般設定為每秒 fsync 一次，則在重新啟動後我們的鍵可能會遺失。長話短說，若我們想在任何類型的實例重啟面前保證鎖的安全性，就需要在持久化設定中啟用 fsync=always。這反過來又會將效能完全拉低到與傳統上用於以安全方式實現分散式鎖的 CP 系統相同的等級。

好消息是，由於在我們的演算法中，我們並不會在達到多數伺服器後就停止嘗試取得鎖，實際發生安全性違規的機率很小，因為大多數時候鎖會同時在全部 5 台伺服器上被持有，因此即使其中一台在沒有鍵的情況下重啟，實際發生安全性違規的可能性在實務上很低（但並非不可能）。長話短說，這是使用者的選擇，也是一個很大的權衡。鑑於競爭條件的機率很小，若在當機復原事件後，極小機率下多個客戶端同時取得鎖是可接受的，那麼每次操作都 fsync 就能夠（且應該）避免。

# 參考實作

我用 Ruby 寫了一個簡單的參考實作，其基於 redis-rb，請見：http://github.com/antirez/redlock-rb

# 需要幫忙嗎？

若你熟悉分散式系統，能提供你的意見／分析將會非常有幫助。
此外，其他語言的參考實作也會很有價值。

先在此致謝！

編輯：我在這篇部落格文章的留言以及透過 Hacker News 收到的回饋值得納入本文。

1) 如 Steven Benjamin（史蒂文·班傑明）在下方留言中所指出的，若在重新啟動實例後，我們能讓它在一段足夠所有使用該實例的鎖都過期的時間內保持不可用，我們就不需要 fsync。實際上我們完全不需要任何持久化，因此僅透過純記憶體的設定就能提供安全性保證。

一個範例：先前我們描述了一個競爭條件範例，即在 5 台伺服器中的 3 台上取得鎖，而其中一台已取得鎖的伺服器在空的狀態下重新啟動：另一個客戶端可能會透過鎖定該伺服器以及另外兩台先前未被鎖定的伺服器來取得同一把鎖。然而，若重新啟動的伺服器在一段足夠所有透過它取得的鎖都過期的時間內不接受查詢，我們就能保證此競爭不再可能發生。

2) Hacker News 使用者 eurleif 指出，若客戶端發現完成操作需要的時間太長，可以重新取得鎖作為一種策略。這可以透過僅擴展現有鎖來完成，發送一個腳本來延長鍵中儲存的值的過期時間，前提是該值符合預期。若沒有新的分割發生，且我們嘗試在鍵過期前足夠提前地去延長鎖，就能保證鎖會被延長。

3) Hacker News 使用者 mjb 指出，用語「skew」並不正確，不應被用來描述不同時鐘各自推進本地時間的速率差異，而我實際上談論的是「drift」。我將把「skew」一詞替換為「drift」以使用正確的術語。

感謝非常有用的回饋。