前言

Raft 也是一個 一致性算法，和 Paxos 目標相同。但它還有另一個名字 - 易于理解的一致性算法。Paxos 和 Raft 都是為了實現 一致性 產生的。這個過程如同選舉一樣，參選者 需要說服 大多數選民 (服務器) 投票給他，一旦選定后就跟隨其操作。Paxos 和 Raft 的區(qū)別在于選舉的 具體過程 不同。

正文

小試牛刀

在進入正題前，給大家分享一個《數學發(fā)散思維》中的一個故事，站在不同思維角度上，了解對一個問題理解的差異性。

問題: 甲乙兩人輪流在一張圓桌上平放黑白圍棋子，每次放一子，棋子不許重疊，誰先沒有地方放就輸。請問怎樣放才能贏？

這個問題有兩層意思，第一，有沒有一種放法保證必贏？第二，如果有怎么證明？

image

上圖回答了這個問題，那就是先行者必勝，這里使用了三種不同的思維方式來闡述:

1. 假如桌子只有一個圍棋子那么大。

2. 假如桌子無限大，先行者先占住圓心。由于圓是對稱圖形，所以只要對手還能找到位置放，你總能在對稱的另一面找到位置放。

3. 一個圓中可畫單數個直徑相等且互切的小圓。

三種不同的思維方式在可理解性難度上逐漸加深。

1. 第一種是 極簡化思維，但數學上是 不嚴謹 的。

2. 第二種是 極限思維，和第一種結合起來就是 數學歸納法，在數學上是 嚴謹 的。

3. 第三種是 形象思維，使用了 幾何學概念，但對于沒有幾何學基礎知識的人就很難理解了。

什么是Raft協議

Raft 協議將 Server 進程分成三類，分別是 Leader，Candidate，Follower。一個 Server 進程在某一時刻，只能是其中 一種類型，但這不是固定的。不同的時刻，它可能擁有不同的類型，一個 Server 進程的類型是如何改變的，后面會有解釋。

在一個由 Raft 協議組織的集群中有三類角色：

• Leader（領袖）
• Follower（群眾）
• Candidate（候選人）

就像一個民主社會，領袖由民眾投票選出。剛開始沒有 領袖，所有集群中的 參與者 都是 群眾，那么首先開啟一輪大選。在大選期間 所有群眾 都能參與競選，這時所有群眾的角色就變成了 候選人，民主投票選出領袖后就開始了這屆領袖的任期，然后選舉結束，所有除 領袖 的 候選人 又變回 群眾角色 服從領袖領導。

這里提到一個概念 「任期」，用術語 Term 表達。關于 Raft 協議的核心概念和術語就這么多，而且和現實民主制度非常匹配，所以很容易理解。

三類角色的變遷圖如下，結合后面的選舉過程來看很容易理解。

image

Leader選舉過程

在極簡的思維下，一個最小的 Raft 民主集群需要 三個參與者（如下圖：A、B、C），這樣才可能投出多數票。

初始狀態(tài) ABC 都是 Follower，然后發(fā)起選舉這時有 三種 可能的情形發(fā)生。下圖中前二種都能選出 Leader，第三種則表明 本輪投票無效（Split Votes）。對于第三種，每方都投給了自己，結果沒有任何一方獲得多數票。之后 每個參與方 隨機休息一陣（Election Timeout）重新發(fā)起投票直到一方獲得多數票。這里的關鍵就是隨機 timeout，最先從 timeout 中恢復發(fā)起投票的一方，向還在 timeout 中的另外兩方 請求投票，這時它就只能投給自己，導致很快達成一致。

image

選出 Leader 后，Leader 通過 定期 向所有 Follower 發(fā)送 心跳信息 維持其統治。若 Follower 一段時間未收到 Leader 的 心跳，則認為 Leader 可能已經掛了，然后再次發(fā)起 選舉 過程。

Leader對一致性的影響

Raft 協議 強依賴 Leader 節(jié)點的 可用性，以確保集群 數據的一致性。數據的流向 只能從 Leader 節(jié)點向 Follower 節(jié)點轉移。具體過程如下：

image

1. 當 Client 向集群 Leader 節(jié)點 提交數據 后，Leader 節(jié)點 接收到的數據 處于 未提交狀態(tài)（Uncommitted）。

2. 接著 Leader 節(jié)點會 并發(fā)地 向所有 Follower 節(jié)點 復制數據 并 等待接收響應。

3. 集群中至少 超過半數 的節(jié)點 已接收 到數據后， Leader 再向 Client 確認數據 已接收。

4. 一旦向 Client 發(fā)出數據接收 Ack 響應后，表明此時 數據狀態(tài) 進入 已提交（Committed），Leader 節(jié)點再向 Follower 節(jié)點發(fā)通知告知該 數據狀態(tài)已提交。

在這個過程中，主節(jié)點 可能在 任意階段 掛掉，看下 Raft 協議如何針對不同階段保障 數據一致性 的。

1. 情形1

數據到達 Leader 節(jié)點前，這個階段 Leader 掛掉不影響一致性，不用多說。

image

2. 情形2

數據到達 Leader 節(jié)點，但未復制到 Follower 節(jié)點。

這個階段 Leader 掛掉，數據屬于 未提交狀態(tài)，Client 不會收到 Ack 會認為 超時失敗 可安全發(fā)起 重試。

image

Follower 節(jié)點上沒有該數據，重新選主 后 Client 重試 重新提交 可成功。原來的 Leader 節(jié)點 恢復 后作為 Follower 加入集群，重新從 當前任期 的新 Leader 處 同步數據，強制保持和 Leader 數據一致。

3. 情形3

數據到達 Leader 節(jié)點，成功復制到 Follower 所有節(jié)點，但 Follower 還未向 Leader 響應接收。

這個階段 Leader 掛掉，雖然數據在 Follower 節(jié)點處于 未提交狀態(tài)（Uncommitted），但是 保持一致 的。重新選出 Leader 后可完成 數據提交。

image

此時 Client 由于不知到底提交成功沒有，可重試提交。針對這種情況 Raft 要求 RPC 請求實現 冪等性，也就是要實現 內部去重機制。

4. 情形4

數據到達 Leader 節(jié)點，成功復制到 Follower 的部分節(jié)點，但這部分 Follower 節(jié)點還未向 Leader 響應接收。

這個階段 Leader 掛掉，數據在 Follower 節(jié)點處于 未提交狀態(tài)（Uncommitted）且 不一致。

image

Raft 協議要求投票只能投給擁有 最新數據 的節(jié)點。所以擁有最新數據的節(jié)點會被選為 Leader，然后再 強制同步數據 到其他 Follower，保證 數據不會丟失并 最終一致。

5. 情形5

數據到達 Leader 節(jié)點，成功復制到 Follower 所有或多數節(jié)點，數據在 Leader 處于已提交狀態(tài)，但在 Follower 處于未提交狀態(tài)。

這個階段 Leader 掛掉，重新選出 新的 Leader 后的處理流程和階段 3 一樣。

image

6. 情形6

數據到達 Leader 節(jié)點，成功復制到 Follower 所有或多數節(jié)點，數據在所有節(jié)點都處于已提交狀態(tài)，但還未響應 Client。

這個階段 Leader 掛掉，集群內部數據其實已經是 一致的，Client 重復重試基于冪等策略對 一致性無影響。

image

7. 情形7

網絡分區(qū)導致的腦裂情況，出現雙 Leader 的現象。

網絡分區(qū) 將原先的 Leader 節(jié)點和 Follower 節(jié)點分隔開，Follower 收不到 Leader 的 心跳 將 重新 發(fā)起選舉產生新的 Leader，這時就產生了 雙Leader 現象。

image

原先的 Leader 獨自在一個區(qū)，向它提交數據不可能復制到多數節(jié)點所以永遠提交不成功。向新的 Leader 提交數據可以提交成功。

網絡恢復 后，舊的 Leader 發(fā)現集群中有 更新任期（Term）的新 Leader ，則 自動降級 為 Follower 并從新 Leader 處 同步數據 達成集群 數據一致。

驗證結果

綜上窮舉分析了 最小集群（3 節(jié)點）面臨的所有情況，可以看出 Raft 協議都能很好的應對 一致性問題，并且很容易理解。

小結

Paxos 算法是 Leslie Lamport 在 1990 年就公開發(fā)表在了自己的網站上，想想我們是什么時候才聽說的？什么時候才有一個可用的實現？而 Raft 算法是 2013 年發(fā)表的，大家在參考 Raft開源實現庫，可以看到有很多基于不同語言的 開源實現庫，這就是 可理解性 的重要性。

歡迎關注技術公眾號： 零壹技術棧

零壹技術棧

本帳號將持續(xù)分享后端技術干貨，包括虛擬機基礎，多線程編程，高性能框架，異步、緩存和消息中間件，分布式和微服務，架構學習和進階等學習資料和文章。