簡單易懂的 Raft 分散式共識演算法講義

語言: CN / TW / HK
時間 2021-12-05 09:33:32
主題:

本文整理自 Ongaro 在 Youtube 上的影片，http://www.youtube.com/watch?v=vYp4LYbnnW8。

目標

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

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

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

系統模型

我們假設：

  • 伺服器可能會宕機、會停止執行過段時間再恢復，但是 非拜占庭的 （即它的行為是非惡意的，不會篡改資料等）；

  • 網路通訊會中斷，訊息可能會丟失、延遲或亂序；可能會網路分割槽；

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

  • Leader 正常執行

  • Leader 故障，必須選出新的 Leader

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

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

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

  1. Leader 選舉；

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

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

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

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

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

開始之前

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

伺服器狀態

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

  • Leader：處理所有客戶端請求、日誌複製。同一時刻最多隻能有一個可行的 Leader；

  • Follower：完全被動的（不傳送 RPC，只響應收到的 RPC）——大多數伺服器在大多數情況下處於此狀態；

  • Candidate：用來選舉新的 Leader，處於 Leader 和 Follower 之間的暫時狀態；

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

狀態轉換圖：

任期

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

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

  • 任期開始時的選舉過程；

  • 正常執行的部分；

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

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

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

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

兩個 RPC

Raft 中伺服器之間所有型別的通訊通過兩個 RPC 呼叫：

  • RequestVote ：用於選舉；

  • AppendEntries ：用於複製 log 和傳送心跳；

1. Leader 選舉

啟動

  • 節點啟動時，都是 Follower 狀態；

  • Follower 被動地接受 Leader 或 Candidate 的 RPC；

  • 所以，如果 Leader 想要保持權威，必須向叢集中的其它節點發送心跳包（空的 AppendEntries RPC ）；

  • 等待選舉超時( electionTimeout ，一般在 100~500ms)後，Follower 沒有收到任何 RPC：

    • Follower 認為叢集中沒有 Leader

    • 開始新的一輪選舉

選舉

當一個節點開始競選：

  • 增加自己的 currentTerm

  • 轉為 Candidate 狀態， 其目標是獲取超過半數節點的選票，讓自己成為 Leader

  • 先給自己投一票

  • 並行地向叢集中其它節點發送 RequestVote RPC 索要選票，如果沒有收到指定節點的響應，它會反覆嘗試，直到發生以下三種情況之一：

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

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

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

流程圖如下：

選舉安全性

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

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

  • 每個節點在同一任期內只能投一次票，它將投給第一個滿足條件的投票請求，然後拒絕其它 Candidate 的請求。這需要持久化儲存投票資訊 votedFor ，以便宕機重啟後恢復，否則重啟後  votedFor 丟失會導致投給別的節點；

  • 只有獲得超過半數節點的選票才能成為 Leader，也就是說，兩個不同的 Candidate 無法在同一任期內都獲得超過半數的票；

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

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

解決辦法很簡單：

  • 節點隨機選擇超時時間，通常在 [T, 2T] 之間（T = electionTimeout ）

  • 這樣，節點不太可能再同時開始競選，先競選的節點有足夠的時間來索要其他節點的選票

  • T >> broadcast time(T 遠大於廣播時間)時效果更佳

2. 日誌複製

日誌結構

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

  • 索引：該記錄在日誌中的位置

  • 任期號：該記錄首次被建立時的任期號

  • 命令

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

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

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

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

正常執行

  • 客戶端向 Leader 傳送命令，希望該命令被所有狀態機執行；

  • Leader 先將該命令追加到自己的日誌中；

  • Leader 並行地向其它節點發送 AppendEntries RPC ，等待響應；

  • 收到超過半數節點的響應，則認為新的日誌記錄是被提交的：

    • Leader 將命令傳給自己的狀態機，然後向客戶端返回響應

    • 此外，一旦 Leader 知道一條記錄被提交了，將在後續的 AppendEntries RPC 中通知已經提交記錄的 Followers

    • Follower 將已提交的命令傳給自己的狀態機

  • 如果 Follower 宕機/超時：Leader 將反覆嘗試傳送 RPC；

  • 效能優化：Leader 不必等待每個 Follower 做出響應，只需要超過半數的成功響應（確保日誌記錄已經儲存在超過半數的節點上）——一個很慢的節點不會使系統變慢，因為 Leader 不必等他；

日誌一致性

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

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

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

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

AppendEntries 一致性檢查

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

  • 對於每個 AppendEntries RPC 包含新日誌記錄 之前那條記錄的 索引( prevLogIndex )和任期( prevLogTerm )；

  • Follower 檢查自己的 index 和 term 是否與 prevLogIndex 和  prevLogTerm 匹配，匹配則接收該記錄；否則拒絕；

3. 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；

  • 稍微修改 committed 的定義（ 即前面提到的要稍作修改 ）：前面說多數派儲存即是已提交的，但在某些時候，我們必須延遲提交日誌記錄，直到我們知道這條記錄是安全的， 所謂安全的，就是我們認為後續 Leader 也會有這條日誌 。

延遲提交，選出最佳 Leader

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

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

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

那怎麼辦呢？

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

  • Candidate 在 RequestVote RPCs 中包含日誌資訊（最後一條記錄的 index 和 term，記為  lastIndex 和  lastTerm ）；

  • 收到此投票請求的伺服器 V 將比較誰的日誌更完整： 

    (lastTermV > lastTermC) ||
(lastTermV == lastTermC) && (lastIndexV > lastIndexC)
    將拒絕投票；（即：V 的任期比 C 的任期新，或任期相同但 V 的日誌比 C 的日誌更完整）；

  • 無論誰贏得選舉，可以確保 Leader 和超過半數投票給它的節點中擁有最完整的日誌—— 最完整的意思就是 index 和 term 這對唯一標識是最大的 。

舉個例子

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 要提交一條日誌：

  • 日誌必須儲存在超過半數的節點上；

  • Leader 必須看到：超過半數的節點上還必須儲存著至少一條自己任期內的日誌；

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

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

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

日誌不一致

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

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

  • 缺失的記錄(Missing Entries)；

  • 多出來的記錄(Extraneous Entries)；

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

修復 Follower 日誌

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

  • 刪除 Extraneous Entries；

  • 補齊 Missing Entries；

Leader 為每個 Follower 儲存 nextIndex ：

  • 下一個要傳送給 Follower 的日誌索引；

  • 初始化為：1 + Leader 最後一條日誌的索引；

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

對於 a：

  • 一開始 nextIndex = 11，帶上日誌 index = 10 & term = 6，檢查失敗；

  • nextIndex = 10，帶上日誌 index = 9 & term = 6，檢查失敗；

  • 如此反覆，直到 nextIndex = 5，帶上日誌 index = 4 & term = 4，該日誌現在匹配，會在 a 中補齊 Leader 的日誌。如此往下補齊。

對於 b：

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

4. 處理舊 Leader

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

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

  • 每個 RPC 都包含傳送方的任期；

  • 如果傳送方的任期太老，無論哪個過程，RPC 都會被拒絕，傳送方轉變到 Follower 並更新其任期；

  • 如果接收方的任期太老，接收方將轉為 Follower，更新它的任期，然後正常的處理 RPC；

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

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

5. 客戶端協議

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

  • 如果客戶端不知道 Leader 是誰，它會和任意一臺伺服器通訊；

  • 如果通訊的節點不是 Leader，它會告訴客戶端 Leader 是誰；

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

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

  • 客戶端重新發出命令到其他伺服器上，最終重定向到新的 Leader

  • 用新的 Leader 重試請求，直到命令被執行

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

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

  • Leader 將唯一 id 寫到日誌記錄中

  • 在 Leader 接受命令之前，先檢查其日誌中是否已經具有該 id

  • 如果 id 在日誌中，說明是重複的請求，則忽略新的命令，返回舊命令的響應

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

6. 配置變更

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

系統配置是指：

  • 每臺伺服器的 id 和地址

  • 系統配置資訊是非常重要的，它決定了多數派的組成

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

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

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

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

共同一致(Joint Consensus)

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

第一階段：

  • Leader 收到 的配置變更請求後，先寫入一條  的日誌，配置變更立即生效，然後將日誌通過  AppendEntries RPC 複製到 Follower 中，收到該     的節點立即應用該配置作為當前節點的配置；

  •   日誌複製到多數派節點上時，     的日誌已提交；

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

第二階段：

  •   日誌已提交後，立即寫入一條     的日誌，並將該日誌通過  AppendEntries RPC 複製到 Follower 中，收到     的節點立即應用該配置作為當前節點的配置；

  •   日誌複製到多數派節點上時，     的日誌已提交；在     日誌提交以後，後續的配置都基於     了；

Joint Consensus 還有一些細節：

  • 變更過程中，來自新舊配置的節點都有可能成為 Leader；

  • 如果當前 Leader 不在   配置裡面，一旦     提交，它必須下臺(step down)。

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

- END -

掃碼關注公眾號「網管叨bi叨」

給網管個星標，第一時間吸我的知識 :point_up_2:

網管為大家整理了一本超實用的《Go 開發參考書》收集了70多條開發實踐。去公眾號回覆【gocookbook】即刻領取！

覺得有用就點個在看   :point_down::point_down::point_down:

「」