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

語言: CN / TW / HK

本文整理自 Ongaro 在 Youtube 上的影片,https://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: