條分縷析 Raft 算法

本文整理自 Ongaro 在 Youtube 上的視頻。

目標

Raft 的目標（或者說是分佈式共識算法的目標）是：保證 log 完全相同地複製到多臺服務器上。

只要每臺服務器的日誌相同，那麼，在不同服務器上的狀態機以相同順序從日誌中執行相同的命令，將會產生相同的結果。

共識算法的工作就是管理這些日誌。

系統模型

我們假設：

Raft 是基於 Leader 的共識算法，故主要考慮：

優點：只有一個 Leader，簡單。

難點：Leader 發生改變時，可能會使系統處於不一致的狀態，因此，下一任 Leader 必須進行清理；

我們將從 6 個部分解釋 Raft：

  1. Leader 選舉；

  2. 正常運行：日誌複製（最簡單的部分）；

  3. Leader 變更時的安全性和一致性（最棘手、最關鍵的部分）；

  4. 處理舊 Leader：舊的 Leader 並沒有真的下線怎麼辦？

  5. 客戶端交互：實現線性化語義 (linearizable semantics)；

  6. 配置變更：如何在集羣中增加或刪除節點；

開始之前

開始之前需要了解 Raft 的一些術語。

服務器狀態

服務器在任意時間只能處於以下三種狀態之一：

系統正常運行時，只有一個 Leader，其餘都是 Followers.

狀態轉換圖：

任期

時間被劃分成一個個的任期 (Term)，每個任期都由一個數字來表示任期號，任期號單調遞增並且永遠不會重複。

一個正常的任期至少有一個 Leader，通常分爲兩部分：

有些任期可能沒有選出 Leader（如圖 Term 3），這時候會立即進入下一個任期，再次嘗試選出一個 Leader。

每個節點維護一個 currentTerm 變量，表示系統中當前任期。currentTerm 必須持久化存儲，以便在服務器宕機重啓時將其恢復。

任期非常重要！任期能夠幫助 Raft 識別過期的信息。
例如：如果 currentTerm = 2 的節點與 currentTerm = 3 的節點通信，我們可以知道第一個節點上的信息是過時的。

我們只使用最新任期的信息。後面我們會遇到各種情況，去檢測和消除不是最新任期的信息。

兩個 RPC

Raft 中服務器之間所有類型的通信通過兩個 RPC 調用：

  1. Leader 選舉

啓動

選舉

當一個節點開始競選：

  1. 獲得超過半數的選票：成爲 Leader，並向其它節點發送 AppendEntries 心跳；

  2. 收到來自 Leader 的 RPC：轉爲 Follower；

  3. 其它兩種情況都沒發生，沒人能夠獲勝 (electionTimeout 已過)：增加 currentTerm，開始新一輪選舉；

流程圖如下：

選舉安全性

選舉過程需要保證兩個特性：安全性 (safety) 和活性 (liveness)。

安全性 (safety)：一個任期內只會有一個 Leader 被選舉出來。需要保證：

活性 (liveness)：確保最終能選出一個 Leader。

問題是：原則上我們可以無限重複分割選票，假如選舉同一時間開始，同一時間超時，同一時間再次選舉，如此循環。

解決辦法很簡單：

  1. 日誌複製

日誌結構

每個節點存儲自己的日誌副本 (log[])，每條日誌記錄包含：

日誌必須持久化存儲。 一個節點必須先將記錄安全寫到磁盤，才能向系統中其他節點返回響應。

如果一條日誌記錄被存儲在超過半數的節點上，我們認爲該記錄已提交 (committed)——這是 Raft 非常重要的特性！如果一條記錄已提交，意味着狀態機可以安全地執行該記錄。

在上圖中，第 1-7 條記錄被提交，第 8 條尚未提交。

提醒：多數派複製了日誌即已提交，這個定義並不精確，我們會在後面稍作修改。

正常運行

日誌一致性

Raft 嘗試在集羣中保持日誌較高的一致性。

Raft 日誌的 index 和 term 唯一標示一條日誌記錄。（這非常重要！！！）

  1. 如果兩個節點的日誌在相同的索引位置上的任期號相同，則認爲他們具有一樣的命令；從頭到這個索引位置之間的日誌完全相同；

  2. 如果給定的記錄已提交，那麼所有前面的記錄也已提交。

AppendEntries 一致性檢查

Raft 通過 AppendEntries RPC 來檢測這兩個屬性。

  1. Leader 更替

當新的 Leader 上任後，日誌可能不會非常乾淨，因爲前一任領導可能在完成日誌複製之前就宕機了。Raft 對此的處理方式是：無需採取任何特殊處理。

當新 Leader 上任後，他不會立即進行任何清理操作，他將會在正常運行期間進行清理。

原因是當一個新的 Leader 上任時，往往意味着有機器故障了，那些機器可能宕機或網絡不通，所以沒有辦法立即清理他們的日誌。在機器恢復運行之前，我們必須保證系統正常運行。

大前提是 Raft 假設了 Leader 的日誌始終是對的。 所以 Leader 要做的是，隨着時間推移，讓所有 Follower 的日誌最終都與其匹配。

但與此同時，Leader 也可能在完成這項工作之前故障，日誌會在一段時間內堆積起來，從而造成看起來相當混亂的情況，如下所示：

因爲我們已經知道 index 和 term 是日誌記錄的唯一標識符，這裏不再顯示日誌包含的命令，下同。

如圖，這種情況可能出現在 S4 和 S5 是任期 2、3、4 的 Leader，但不知何故，他們沒有複製自己的日誌記錄就崩潰了，系統分區了一段時間，S1、S2、S3 輪流成爲了任期 5、6、7 的 Leader，但無法與 S4、S5 通信以進行日誌清理——所以我們看到的日誌非常混亂。

唯一重要的是，索引 1-3 之間的記錄是已提交的 (已存在多數派節點)，因此我們必須確保留下它們。

其它日誌都是未提交的，我們還沒有將這些命令傳遞給狀態機，也沒有客戶端會收到這些執行的結果，所以不管是保留還是丟棄它們都無關緊要。

安全性

一旦狀態機執行了一條日誌裏的命令，必須確保其它狀態機在同樣索引的位置不會執行不同的命令。

Raft 安全性 (Safety)：如果某條日誌記錄在某個任期號已提交，那麼這條記錄必然出現在更大任期號的未來 Leader 的日誌中。

這保證了安全性要求：

這決定我們要修改選舉程序：

延遲提交，選出最佳 Leader

問題來了：我們如何確保選出了一個很好地保存了所有已提交日誌的 Leader ？

這有點棘手，舉個例子：假設我們要在下面的集羣中選出一個新 Leader，但此時第三臺服務器不可用。

這種情況下，僅看前兩個節點的日誌我們無法確認是否達成多數派，故無法確認第五條日誌是否已提交。

那怎麼辦呢？

通過比較日誌，在選舉期間，選擇最有可能包含所有已提交的日誌：

舉個例子

Case 1: Leader 決定提交日誌

任期 2 的 Leader S1 的 index = 4 日誌剛剛被複制到 S3，並且 Leader 可以看到 index = 4 已複製到超過半數的服務器，那麼該日誌可以提交，並且安全地應用到狀態機。

現在，這條記錄是安全的，下一任期的 Leader 必須包含此記錄，因此 S4 和 S5 都不可能從其它節點那裏獲得選票：S5 任期太舊，S4 日誌太短。

只有前三臺中的一臺可以成爲新的 Leader——S1 當然可以，S2、S3 也可以通過獲取 S4 和 S5 的選票成爲 Leader。

Case 2: Leader 試圖提交之前任期的日誌

如圖所示的情況，在任期 2 時記錄僅寫在 S1 和 S2 兩個節點上，由於某種原因，任期 3 的 Leader S5 並不知道這些記錄，S5 創建了自己的三條記錄然後宕機了，然後任期 4 的 Leader S1 被選出，S1 試圖與其它服務器的日誌進行匹配。因此它複製了任期 2 的日誌到 S3。

此時 index=3 的記錄時是不安全的。

因爲 S1 可能在此時宕機，然後 S5 可能從 S2、S3、S4 獲得選票成爲任期 5 的 Leader。一旦 S5 成爲新 Leader，它將覆蓋 index=3-5 的日誌，S1-S3 的這些記錄都將消失。

我們還要需要一條新的規則，來處理這種情況。

新的 Commit 規則

新的選舉不足以保證日誌安全，我們還需要繼續修改 commit 規則。

Leader 要提交一條日誌：

如圖，回到上面的 Case 2: 當 index = 3 & term = 2 被複制到 S3 時，它還不能提交該記錄，必須等到 term = 4 的記錄存儲在超過半數的節點上，此時 index = 3 和 index = 4 可以認爲是已提交。

此時 S5 無法贏得選舉了，它無法從 S1-S3 獲得選票。

結合新的選舉規則和 commit 規則，我們可以保證 Raft 的安全性。

日誌不一致

Leader 變更可能導致日誌的不一致，這裏展示一種可能的情況。

可以從圖中看出，Raft 集羣中通常有兩種不一致的日誌：

我們要做的就是清理這兩種日誌。

修復 Follower 日誌

新的 Leader 必須使 Follower 的日誌與自己的日誌保持一致，通過：

Leader 爲每個 Follower 保存 nextIndex：

Leader 通過 nextIndex 來修復日誌。當 AppendEntries RPC 一致性檢查失敗，遞減 nextIndex 並重試。如下圖所示：

對於 a：

對於 b：
會一直檢查到 nextIndex = 4 才匹配。值得注意的是，對於 b 這種情況，當 Follower 覆蓋不一致的日誌時，它將刪除所有後續的日誌記錄（任何無關緊要的記錄之後的記錄也都是無關緊要的）。如下圖所示：

  1. 處理舊 Leader

實際上，老的 Leader 可能不會馬上消失，例如：網絡分區將 Leader 與集羣的其餘部分分隔，其餘部分選舉出了一個新的 Leader。問題在於，如果老的 Leader 重新連接，也不知道新的 Leader 已經被選出來，它會嘗試作爲 Leader 繼續提交日誌。此時如果有客戶端向老 Leader 發送請求，老的 Leader 會嘗試存儲該命令並向其它節點複製日誌——我們必須阻止這種情況發生。

任期就是用來發現過時的 Leader(和 Candidates)：

由於新 Leader 的選舉會更新超過半數服務器的任期，舊的 Leader 不能提交新的日誌，因爲它會聯繫至少一臺多數派集羣的節點，然後發現自己任期太老，會轉爲 Follower 繼續工作。

這裏不打算繼續討論別的極端情況。

  1. 客戶端協議

客戶端只將命令發送到 Leader：

Leader 直到將命令記錄、提交和執行到狀態機之前，不會做出響應。

這裏的問題是如果 Leader 宕機會導致請求超時：

這留下了一個命令可能被執行兩次的風險——Leader 可能在執行命令之後但響應客戶端之前宕機，此時客戶端再去尋找下一個 Leader，同一個命令就會被執行兩次——這是不可接受的！

解決辦法是：客戶端發送給 Leader 的每個命令都帶上一個唯一 id

每個命令只會被執行一次，這就是所謂的線性化的關鍵要素。

  1. 配置變更

隨着時間推移，會有機器故障需要我們去替換它，或者修改節點數量，需要有一些機制來變更系統配置，並且是安全、自動的方式，無需停止系統。

系統配置是指：

首先要意識到，我們不能直接從舊配置切換到新配置，這可能會導致矛盾的多數派。

如圖，系統以三臺服務器的配置運行着，此時我們要添加兩臺服務器。如果我們直接修改配置，他們可能無法完全在同一時間做到配置切換，這會導致 S1 和 S2 形成舊集羣的多數派，而同一時間 S3-S5 已經切換到新配置，這會產生兩個集羣。

這說明我們必須使用一個兩階段 (two-phase) 協議。

如果有人告訴你，他可以在分佈式系統中一個階段就做出決策，你應該非常認真地詢問他，因爲他要麼錯了，要麼發現了世界上所有人都不知道的東西。

共同一致 (Joint Consensus)

Raft 通過共同一致 (Joint Consensus) 來完成兩階段協議，即：新、舊兩種配置上都獲得多數派選票。

第一階段：

  日誌已提交保證了後續任何 Leader 一定有  日誌，Leader 選舉過程必須獲得舊配置中的多數派和新配置中的多數派同時投票。

第二階段：

Joint Consensus 還有一些細節：

如圖所示，舊 Leader 不再是新配置的成員之後，還有可能繼續服務一小段時間；即舊 Leader 可能在  配置下繼續當 Leader（雖然實質上並不是 Leader），直到  的日誌複製到多數派上而 committed；

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/lUbVBVzvNVxhgbcHQBbkkQ

猜你喜歡