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

很多人用 Redis 來實作分散式鎖。不少人認為這是很棒的使用情境，Redis 非常適合用來解決一個原本很難解的問題。也有人認為這根本是錯誤、不安全、不該這樣使用 Redis。

基本上，兩方都對。分散式鎖如果要做得安全並不容易，同時我們又要求高可用性，讓 Redis 節點就算掛掉，客戶端仍然能夠取得與釋放鎖。另一方面，一個快速的鎖管理器可以解決大量在實務上難以處理的問題，有時候一個遠稱不上完美的解法，也勝過一個非常緩慢的解法。

我們能不能同時擁有基於 Redis、又快又可靠的系統？這篇文章就是對這個領域的探索。我將嘗試描述一個簡單的演算法提案，利用 N 個 Redis 執行個體來實現分散式且可靠的鎖，希望社群能幫忙分析與評論這個演算法，看看它是否是一個可行的候選方案。

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

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

1) 安全性屬性：互斥。在任何時刻，只有一位客戶端能夠持有鎖。

2) 活性屬性 A：無死結。最終一定有辦法取得鎖，即使持有資源的客戶端當掉或發生網路分割。

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

# 分散式鎖，天真的做法

要了解我們想改進什麼，先來看看現況。

用 Redis 鎖定資源最簡單的方法，就是在某個執行個體中建立一個 key。這個 key 通常會設定存活時間，利用 Redis 的 expire 功能，讓它最終無論如何都會被釋放（對應我們清單中的屬性 2）。當客戶端需要釋放資源時，就把這個 key 刪掉。

表面上看起來運作良好，但有個問題：這在我們的架構中是單點故障。如果 Redis 主節點掛了會怎樣？
好吧，那就加一個備援！主節點不可用時就改用備援。不幸的是這行不通。這麼做就無法實現我們所要求的互斥安全性，因為 Redis 的複寫是非同步的。

這個模型存在明顯的競爭條件：

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

2) 主節點在把寫入 key 的操作傳送給備援節點之前就當掉了。

3) 備援節點被提升為主節點。

4) 客戶端 B 對同一個 A 已經持有鎖的資源取得鎖。 <- 違反安全性！

有時候，在特殊情況下，例如故障期間，多個客戶端同時持有鎖是完全可以接受的。
如果是這樣，就別再往下看了，盡情享用你的基於複寫的解法吧。否則，請繼續看下去，看看一個 hopefully 更安全的實作方式。

# 首先，在單一執行個體上把它做對

在嘗試克服上述單一執行個體架構的限制之前，先來看看在這個簡單情境下如何正確地實作，因為這在容許偶爾發生競爭條件的應用中其實是可行的方案，而且單一執行個體的上鎖正是本文所述分散式演算法的基礎。

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

SET resource_name my_random_value NX PX 30000

這個指令只有在 key 尚未存在時才會設定（NX 選項），並設定 30000 毫秒的過期時間（PX 選項）。
key 的值設為「my_random_value」。這個值必須在所有客戶端與所有上鎖請求之間保持唯一。

基本上，這個隨機值是用來安全地釋放鎖，透過一個腳本告訴 Redis：只有當 key 存在且儲存的值正好是我預期的值時，才刪除它。這可以透過以下的 Lua 腳本達成：

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

這很重要，目的是避免刪除了由另一個客戶端建立的鎖。舉例來說，客戶端可能取得鎖後，因執行某個操作而被卡住超過鎖的有效時間（也就是 key 過期的時間），之後再去刪除鎖時，該鎖其實已經被其他客戶端取得。
只用 DEL 並不安全，因為客戶端可能會刪掉別人的鎖。透過上面的腳本，每個鎖都用一個隨機字串「簽名」，因此只有當鎖仍是當初嘗試刪除的客戶端所設定的那一把時，才會被刪除。

這個隨機字串應該是什麼？我假設是從 /dev/urandom 取出的 20 個位元組，但你也可以找到更省成本、但對你的任務來說已足夠唯一的方法。
例如，一個安全的選擇是用 /dev/urandom 來播種 RC4，再產生偽隨機串流。
更簡單的作法是使用 Unix 時間（微秒級解析度）加上客戶端 ID 的組合，雖然沒那麼安全，但在大多數環境下應該也夠用。

我們作為 key 存活時間所使用的時間，被稱為「鎖有效時間」。它既是自動釋放時間，也是客戶端在另一個客戶端能夠再次取得鎖之前，必須完成所需操作的時間；這並未在技術上違反互斥保證，因為互斥只在從取得鎖的當下起算的一段時間窗口內有效。

所以現在我們已經有取得與釋放鎖的好方法。以單一、始終可用的非分散式系統來看，這個系統是安全的。接下來把這個概念延伸到我們沒有這種保證的分散式系統中。

# 分散式版本

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

要取得鎖，客戶端會執行以下操作：

步驟 1) 取得當前的時間，單位為毫秒。

步驟 2) 依序嘗試在所有 N 個執行個體中取得鎖，在所有執行個體中使用相同的 key 名稱與隨機值。

在步驟 2 中，當在每個執行個體設定鎖時，客戶端使用的逾時時間相對於總的鎖自動釋放時間來說要短得多。
例如，如果自動釋放時間是 10 秒，逾時可以設在約 5-50 毫秒的範圍。
這可以避免客戶端在嘗試與已當掉的 Redis 節點溝通時被長時間卡住：如果某個執行個體不可用，我們應該盡快嘗試下一個執行個體。

步驟 3) 客戶端計算取得鎖所經過的時間，方法是將當前時間減去步驟 1 取得的時間戳。
若且唯若客戶端能夠在多數執行個體中取得鎖（至少 3 個），且取得鎖的總耗時小於鎖的有效時間，才視為成功取得鎖。

步驟 4) 如果成功取得鎖，其有效時間被視為初始有效時間減去步驟 3 所計算的耗時。

步驟 5) 如果客戶端因某些原因未能取得鎖（無論是無法鎖定 N/2+1 個執行個體，或有效時間為負），它將嘗試解鎖所有執行個體（即使是它認為未能成功上鎖的執行個體）。

# 是否同步？

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

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

# 重試

當客戶端無法取得鎖時，應該在一個隨機延遲後重試，以避免多個客戶端同時嘗試取得同一資源的鎖而產生不同步的情況（這可能導致沒有人能勝出的腦裂狀態）。另外，客戶端越快在多數 Redis 執行個體上嘗試取得鎖，發生腦裂的窗口就越小（也就越不需要重試），所以理想上客戶端應該使用多工同時對 N 個執行個體發送 SET 指令。

值得強調的是，對於未能取得多數鎖的客戶端，盡快釋放（部分）已取得的鎖非常重要，這樣就不需要等到 key 過期才能再次取得鎖（不過如果發生網路分割且客戶端已無法與 Redis 執行個體通訊，就得付出可用性的代價，等待過期）。

# 釋放鎖

釋放鎖很簡單，只需在所有執行個體上釋放鎖，無論客戶端認為自己是否成功鎖定了某個特定執行個體。

# 安全性論證

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

首先，假設某個客戶端能夠在多數執行個體中取得鎖。所有執行個體都會包含一個具有相同存活時間的 key。然而，這些 key 是在不同時間設定的，所以也會在不同時間過期。不過，如果第一個 key 最晚在時間 T1 被設定（我們在聯繫第一台伺服器之前取樣的時間），而最後一個 key 最晚在時間 T2 被設定（我們收到最後一台伺服器回覆的時間），我們可以確定這組 key 中最早過期的那個，至少會存在 MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT 的時間。其他 key 會更晚才過期，所以我們可以確定這些 key 至少會同時存在這麼長的時間。

在多數 key 同時存在的這段期間，另一個客戶端將無法取得鎖，因為如果已有 N/2+1 個 key 存在，就不可能有 N/2+1 個 SET NX 操作成功。因此，如果鎖已被取得，就不可能同時再次取得它（違反互斥性）。

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

如果某個客戶端以接近或超過鎖的最大有效時間（基本上就是我們用於 SET 的 TTL）才鎖定多數執行個體，它會認為鎖是無效的並解鎖這些執行個體，所以我們只需考慮客戶端能在小於有效時間內鎖定多數執行個體的情況。在這種情況下，根據前面已闡述的論點，在 MIN_VALIDITY 這段時間內，沒有任何客戶端應該能夠重新取得鎖。因此，多個客戶端能夠同時鎖定 N/2+1 個執行個體（此處的「同時」指的是步驟 2 結束的時間點），只有當鎖定多數所需的時間大於 TTL，使得鎖變為無效時才可能發生。

你能提供正式的安全性證明，或是找出錯誤嗎？非常歡迎。

# 活性論證

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

1) 鎖的自動釋放（因為 key 會過期）：最終 key 又會變得可被鎖定。

2) 客戶端通常會合作，在未取得鎖或已完成工作後移除鎖，使得我們很可能不需要等到 key 過期就能重新取得鎖。

3) 當客戶端需要重試鎖時，它會等待一段時間，該時間相對於取得多數鎖所需的時間來說要長得多，以便在資源競爭期間，以機率方式讓腦裂狀況變得不太可能發生。

然而，至少存在一種情境，在非常特殊的網路分割／重新合併模式不斷重複發生時，可能會違反系統的可用性。
例如，當 N=5 時，兩個客戶端 A 與 B 可能同時嘗試鎖定同一資源，沒有人能取得多數鎖，但如果把 A 與 B 的鎖加總，卻可能鎖定了多數節點（例如客戶端 A 鎖了 2 個執行個體，客戶端 B 鎖了 1 個執行個體）。
接著，客戶端在還來不及解鎖已鎖定的執行個體前就被分割隔離。這會讓該資源在一段約等於自動釋放時間的期間內無法被鎖定。接著當 key 過期後，兩個客戶端 A 與 B 再次加入分割，反覆重現相同的模式，如此無限循環。

換個角度看上面的問題，就是在網路分割時，我們付出了等於「TTL」時間的可用性代價，所以如果持續發生分割，這個代價就會無限期地付出。

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

# 效能、當機復原與 fsync

許多將 Redis 作為鎖伺服器使用的使用者，需要在取得與釋放鎖的延遲，以及每秒可執行的取得／釋放操作數量上都有高效能。為了滿足這個需求，與 N 台 Redis 伺服器溝通以降低延遲的策略，絕對是多工（或是陽春版的多工，也就是把 socket 設為非阻塞模式，送出所有指令，之後再一次讀取所有回覆，假設客戶端與每個執行個體之間的 RTT 差不多）。

然而，如果我們想針對當機復原的系統模型，還有另一個關於持久化的考量。

基本上，要看出這裡的問題，假設我們將 Redis 設定為完全不做持久化。某個客戶端在 5 個執行個體中的 3 個上取得鎖。其中一個客戶端成功取得鎖的執行個體重新啟動，此時又再次有 3 個執行個體可以對同一資源上鎖，另一個客戶端就能再次鎖定它，違反了鎖的互斥安全性。

如果啟用 AOF 持久化，情況會好很多。例如，我們可以透過發送 SHUTDOWN 並重新啟動伺服器來升級伺服器。由於 Redis 的過期在語意上被實作為即使伺服器關閉時，時間仍虛擬地持續流逝，因此我們的所有需求都沒問題。
然而，一切正常的前提是乾淨的關機。那如果是斷電呢？如果 Redis 如預設設定為每秒 fsync 一次磁碟，重啟後我們的 key 可能就不見了。長話短說，如果我們想在任何形式的執行個體重啟面前保證鎖的安全性，就需要在持久化設定中啟用 fsync=always。這反過來又會把效能徹底拖垮到與傳統上用來安全實作分散式鎖的 CP 系統同等的水準。

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

# 參考實作

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

# 想要幫忙嗎？

如果你對分散式系統有研究，很希望能聽到你的意見／分析。
其他語言的參考實作也很棒。

先在此致謝！

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

1) 如 Steven Benjamin 在下方留言中所指出的，如果重啟執行個體後，我們能讓它在一段足夠長的時間內保持不可用，直到所有使用該執行個體的鎖都過期，我們就不需要 fsync。事實上，我們根本不需要任何持久化，就能在純記憶體的設定下提供安全性保證。

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

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

3) Hacker News 使用者 mjb 指出，「skew」一詞用來描述不同時鐘各自遞增本地時間的速率差異並不正確，我真正想說的是「Drift」。我將把「skew」替換為「drift」以使用正確的術語。

感謝非常實用的回饋。