前言

---

持續創作，加速成長！這是我參與「掘金日新計劃 · 10 月更文挑戰」的第4天，點選檢視活動詳情

正式介紹 Raft 協議之前，我們先來舉個職場產研團隊的一個例子。

方式一：

在一個技術團隊內假設角色都是 均等的，會導致什麼情況呢？產品提出一個需求，就可以隨便去找團隊中的任意一個人去發起需求。如果這個人因為請假走了，但是他沒有把需求及時同步給團隊其他人，因此會導致該需求存在很大的延遲。

方式二：

在技術團隊中選舉一個 Leader角色，產品提出的需求必須優先提給 Leader，找 Leader 先溝通。Leader 自己消化完後，在將需求傳達給團隊其他成員。如果 Leader 請假了，會指定某一個人充當 Leader 角色負責接收產品需求，並將需求同步給其他成員。

上述很簡單的案例，可以對應理解分散式系統中的資料一致性演算法。

分散式系統資料一致性演算法一般都應用在中介軟體專案中，平時你寫的業務程式碼，一般根本不會接觸到的。

SpringCloud 家族中集成了大名鼎鼎的註冊中心 Eureka 就使用的上面的 方式一 的思路來完成節點之間資料同步的，稱為 Peer To Peer 叢集架構。

Eureka 當中的每個節點的地位都是均等的，每個節點都可以接收寫入請求，每個節點接收請求之後，進行請求打包處理，非同步化延遲一點時間，將資料同步給 Eureka 叢集當中的其他節點。任何一臺節點宕機之後，理論上應該是不影響叢集執行的，都可以從其他節點獲取登錄檔資訊。

另外的一些開源專案，比如 Etcd、Consul，Zookeeper，還有未來會流行的國產技術阿里開源的 Nacos 專案，其中的 CP 模式也是基於 Raft 協議 來實現分散式一致性演算法的。當然 Zookeeper 在 Raft 協議基礎上做了一些改良，使用的 ZAB 分散式一致性協議來實現的。

在 Raft 協議出現之前，廣泛使用的一致性演算法是 Paxos。Paxos 演算法解決的是如何保障單一客戶端操作的一致性，完成每個操作都需要至少兩輪的訊息交換。和 Paxos 演算法不同，Raft 裡有 Leader 的概念，Raft 在處理任何客戶端操作之前必須要選舉出來一個 leader 角色，選舉一個 Leader 經過至少一輪的訊息交換，但是選舉了 Leader 之後，處理每個客戶端的操作只需要一輪訊息交換。

詳解 Raft 協議

---

接下來，圍繞如下幾點展開：

1）Leader選舉流程

2）節點心跳檢測

3）選主超時操作

4）日誌複製流程

5）日誌條目結構

6）Leader崩潰恢復操作

---

1）Leader選舉流程

如果系統中只有唯一一個節點，讀寫操作都由這一個節點來負責，不會存在資料不一致的問題。

但是，對於分散式系統會存在至少兩個節點，需要有一個角色來充唯一的節點，我們把這個唯一節點叫做 Leader 節點，其他節點叫做 Follower 節點， leader 選舉過程中才會有的狀態叫做 Candidate 節點。

為了便於理解和說明，假設叢集中有三個節點：節點A、節點B、節點C。

叢集啟動後，初始節點狀態都是 Follower 狀態。最開始各個節點啟動之後，此時叢集內還沒有 Leader。

如果每次各節點都投票給自己，Leader 會始終無法選出來，這樣僵持下去肯定是不行的。所以出現了 electionTimeout 的概念，稱為 選舉超時時間 每個節點都會有 electionTimeout。

一旦發現一輪投票沒有結果，叢集中各節點自身設定一個 electionTimeout，時間範圍在 150ms ~ 300ms 之間的一個隨機值。

當節點 A 的 electionTimeout 時間到了，會將節點 A 狀態變為 Candidate 狀態，節點 A 甦醒過來，很Happy，終於可以參與競選了，立馬給自己投了一票 。然後向叢集中其他兩個節點發起選舉投票（Http協議或者RPC協議請求都可以）。

節點B、C可以認為處於 Follower 狀態，如何進行選舉投票呢？

這裡就出現了 term 的概念，每個節點都會有個 term，term 表示任期，跟美國總統競選裡的任期類似。term 是一個全域性且連續遞增的整數，每完成一次選舉，term會遞增 +1。

Follower 狀態的節點此時收到 Candidate 選舉請求，發現叢集中就只有一個 Candidate 狀態的節點 A，所以直接投票給 Candidate 節點。

這裡就出現了 voteFor 的概念，每個節點都會有voteFor，voteFor 表示投票的資料。

節點 A 收到投票反饋之後，引出了另外的判斷條件：必須是叢集中過半節點都投票給自己，也包括自己。

算式：n / 2 + 1

舉個：

叢集中有三個節點，3 / 2 + 1 = 2 必須有 2 個節點投票成功。

叢集中有五個節點，5 / 2 + 1 = 3 必須有 3 個節點投票成功。

最終 Candidate 狀態的節點 A 很榮幸晉升為 Leader。

2）節點心跳檢測

我們看到上述的狀態流轉圖，當重新選舉 Leader 時，各節點自身的狀態會在 Candidate、Follower、Leader 之間不斷的變換。

所以，被選舉的節點 A 成為了 Leader ，為了保持它的『統治』地位，要不斷的向其他節點發送心跳，告訴他們「我還活著，我還活著... 」。

其他節點 B、C 收到心跳請求後，會返回響應，發現原來 Leader 還在，不需要發起選舉，同時要重置選舉超時時間 electionTimeout。

如果作為 Leader 的節點 A 因為意外，比如網路問題無法正常傳送心跳給其他節點。

此時，節點 B 的 electionTimeout 超時時間到了，變成了 Candidate 狀態，term + 1，voteFor 投票給自己，併發送投票請求給節點 A、C。

之前還是 Leader 的節點 A 收到了節點 B 發來的投票請求，發現 term 任期不是最大的了，更新自身的 term 值為節點 B 的 term，從 Leader 狀態切換為 Follower 狀態，並重置 electionTimeout。

3）選主超時操作

如果恰巧有兩個節點同時都發起了投票，但都沒有獲得多數節點的選票，此時就得打加時賽了，直到獲得多數選票的節點成為 Leader。

如下圖所示：

假設叢集中有4個節點，A、B、C、D。出現了兩個節點處於 Candidate 狀態。

第一輪選舉狀態如下：

``` 節點A[Candidate] <----- 節點 C 選舉節點A

節點B[Candidate] <----- 節點 D 選舉節點B ```

第一輪選舉之後，節點 A 和節點 B 還是處於 Candidate 狀態，都不滿足叢集過半數投票成功的條件，選舉 Leader 失敗。

下一輪就要看 Candidate 狀態的節點誰的 electionTimeout 先到，誰就先發起新一輪選舉操作。只要發起選舉，term 任期就要遞增的。

如果節點 B 的 electionTimeout 先到，先發起選舉操作，那麼叢集中按照條件必須是有 3 個節點投票成功之後最終成為 Leader。

為了避免出現上述這種平局的情況，所以一般叢集中節點部署個數都是奇數： 2n + 1

4）日誌複製流程

當 Leader 選出來之後，Client 客戶端發起的寫請求都會由 Leader 節點來處理。

即使其他的 Follower 節點收到了 Client 客戶端的請求，也會將請求轉交給 Leader 來處理。

Leader 接收到 Client 的請求之後，會優先將資料寫入到自身節點的 log 日誌檔案中。

被寫入到日誌檔案裡的日誌條目，被稱為 append entries 。

Leader 將傳送 append entries 訊息給其他節點，這裡並不是每次都將相同的日誌條目，都發送給其他節點，而是根據節點的不同對應的訊息也是不同的。因為叢集中節點之間資料可能會有不一致的情況。

其他 Follower 節點收到 Leader 的訊息後，將資料新增到本地，然後返回給 Leader 響應，確認訊息已收到。

Leader 節點收到其他節點確認訊息且過半數，先 Commit 提交記錄，返回 Client 客戶端響應。

然後，Leader 節點再次向其他 Follower 節點發送 Commit 提交資料通知。

其他 Follower 節點收到通知後，Commit 提交自身的日誌條目資料，返回 Leader 更新結束的通知。

日誌條目提交保證兩點：

容錯：

在數量少於 Raft 伺服器節點總數一半的 Follower 失敗的情況下 ，Raft 叢集仍然可以正常處理來自客戶端的請求。

確保重疊：

一旦 Leader 響應了一個客戶端的請求，即使出現了 Raft 叢集中少數伺服器的失敗，也會有一個伺服器包含所有以前提交的日誌條目。

5）日誌條目結構

每個節點都會有兩個索引，日誌條目最終提交完成，提交的索引值稱為 commitIndex ，另外一個是目前最後一行索引值，稱為lastApplied

Leader 節點除了儲存上面提到的 commitIndex 和 lastApplied之外，還需要儲存其他 Follower 節點的資料情況。

一個是 nextIndex 記錄的是 Leader 裡有，Follower 節點沒有的資料索引，即需要傳送 append entries 的資料索引。

另外一個是 matchIndex ，記錄的是 Leader 節點已知，已經複製給他 Follower 節點日誌的最高索引值。

當資料變更時， Leader 向其他節點發送不同的 append entries 訊息資料。

如果重新選舉了 Leader，新的 Leader 並不知道原來 Leader 的 nextIndex 和 matchIndex 兩個資料，會將自身節點的 nextIndex 重置為 commitIndex，matchIndex 則全部重置為 0。

6）選主後日志同步

當叢集中的 Leader 接收到 Client 請求，發現部分節點因為網路問題無法正常通訊，所以日誌不能複製給多數節點，日誌無法正常提交。

如下圖所示：

其他 Follower 節點無法正常收到 Leader 心跳檢測請求，會發生重新選主操作。

當新的 Leader1 產生，原來的 Leader2 叢集恢復之後，發現自己不是選票最多的節點，即 term 不是最大的，節點狀態切換到 Follower，回滾未提交的日誌。

新的 Leader1 重新將同步日誌重新同步給其他 Follower 節點。

如下圖所示 ：

總結

---

經過對 Raft 協議的詳細分析，我們能夠總結到，其實 Raft 協議就是 2PC (兩階段提交) + 叢集過半節點寫機制 結合實現的。

1、每個節點都有 electionTimeout 選舉超時時間，用於當 Follower 節點無法收到心跳時，到期發起選舉 Leader 的操作。

2、Leader 節點選舉時，最終選出來的 Leader 的 term 任期一定是最大的。

3、Leader 節點給其他 Follower 節點發送 append enties 日誌條目時，針對不同的節點發送不同的日誌訊息。

4、Leader 接收客戶端的寫入請求，此時處於 uncommitted 狀態，Leader 將 uncommitted 訊息傳送給其他 Follower 節點，作為第一階段。

5、其他 Follower 節點收到 uncommitted 請求之後，返回確認 ack 響應給 Leader，如果 Leader 收到了過半數 Follower 節點的 ack 響應，則將請求標記為 committed，同時傳送 committed 請求傳送給其他 Follower 節點，讓其他節點對訊息進行 committed。作為第二階段 + 過半數機制。

另外剛剛文中提到阿里開源的 Nacos 註冊中心，其內部自己實現了一套簡化版的 Raft 協議。看了 Nacos 官方的 Roadmap 能夠了解到，規劃在 nacos 1.7.0 GA 中會替換掉現在的 Raft 協議實現，有可能會採用螞蟻金服開源的SOFA-JRaft，SOFA-JRaft 基於 Raft 一致性演算法的生產級高效能 Java 實現，支援 MULTI-RAFT-GROUP，適用於高負載低延遲的場景。

關注我，後續更多幹貨奉上！