一文理解 Raft 分佈式一致性算法

一、Raf 算法背景

在學術理論界，分佈式一致性算法的代表還是 Paxos。但是少數理解的人覺得很簡單，尚未理解的覺得很難，大多數人還是一知半解。Paxos 的可理解性和工程落地性的門檻很高。斯坦福學者也花了很多時間理解 Paxos，於是他們又研究出 Raft。

二、Raft 算法基本原理

共識算法就是保證一個集羣的多臺機器協同工作，在遇到請求時，數據能夠保持一致。即使遇到機器宕機，整個系統仍然能夠對外保持服務的可用性。

Raft 將共識問題分解三個子問題：

• Leader election 領導選舉：有且僅有一個 leader 節點，如果 leader 宕機，通過選舉機制選出新的 leader；

• Log replication 日誌複製：leader 從客戶端接收數據更新 / 刪除請求，然後日誌複製到 follower 節點，從而保證集羣數據的一致性；

• Safety 安全性：通過安全性原則來處理一些特殊 case，保證 Raft 算法的完備性；

所以，Raft 算法核心流程可以歸納爲：

• 首先選出 leader，leader 節點負責接收外部的數據更新 / 刪除請求；

• 然後日誌複製到其他 follower 節點，同時通過安全性的準則來保證整個日誌複製的一致性；

• 如果遇到 leader 故障，followers 會重新發起選舉出新的 leader；

這裏先介紹一下日誌同步的概念：服務器接收客戶的數據更新 / 刪除請求，這些請求會落地爲命令日誌。只要輸入狀態機的日誌命令相同，狀態機的執行結果就相同。所以 Raft 的核心就是 leader 發出日誌同步請求，follower 接收並同步日誌，最終保證整個集羣的日誌一致性。

1. Leader Election 領導選舉

集羣中每個節點只能處於 Leader、Follower 和 Candidate 三種狀態的一種:

（1）follower 從節點：

• 節點默認是 follower；

• 如果剛剛開始或和 leader 通信超時，follower 會發起選舉，變成 candidate，然後去競選 leader；

• 如果收到其他 candidate 的競選投票請求，按照先來先得 & 每個任期只能投票一次的投票原則投票;

（2）candidate 候選者：

• follower 發起選舉後就變爲 candidate，會向其他節點拉選票。candidate 的票會投給自己，所以不會向其他節點投票；

• 如果獲得超過半數的投票，candidate 變成 leader，然後馬上和其他節點通信，表明自己的 leader 的地位；

• 如果選舉超時，重新發起選舉；

• 如果遇到更高任期 Term 的 leader 的通信請求，轉化爲 follower；

（3）leader 主節點：

• 成爲 leader 節點後，此時可以接受客戶端的數據請求，負責日誌同步；

• 如果遇到更高任期 Term 的 candidate 的通信請求，這說明 candidate 正在競選 leader，此時之前任期的 leader 轉化爲 follower，且完成投票；

• 如果遇到更高任期 Term 的 leader 的通信請求，這說明已經選舉成功新的 leader，此時之前任期的 leader 轉化爲 follower；

具體的節點狀態轉換參考下圖：

Raft 算法把時間軸劃分爲不同任期 Term。每個任期 Term 都有自己的編號 TermId，該編號全局唯一且單調遞增。如下圖，每個任務的開始都 Leader Election 領導選舉。如果選舉成功，則進入維持任務 Term 階段，此時 leader 負責接收客戶端請求並，負責複製日誌。Leader 和所有 follower 都保持通信，如果 follower 發現通信超時，TermId 遞增併發起新的選舉。如果選舉成功，則進入新的任期。如果選舉失敗，TermId 遞增，然後重新發起選舉直到成功。

舉個例子，參考下圖，Term N 選舉成功，Term N+1 和 Term N+2 選舉失敗，Term N+3 重新選舉成功。

具體的說，Leader 在任期內會週期性向其他 follower 節點發送心跳來維持地位。follower 如果發現心跳超時，就認爲 leader 節點宕機或不存在。隨機等待一定時間後，follower 會發起選舉，變成 candidate，然後去競選 leader。選舉結果有三種情況：

（1）獲取超過半數投票，贏得選舉：

• 當 Candidate 獲得超過半數的投票時，代表自己贏得了選舉，且轉化爲 leader。此時，它會馬上向其他節點發送請求，從而確認自己的 leader 地位，從而阻止新一輪的選舉；

• 投票原則**：當多個 Candidate 競選 Leader 時**

• ‍一個任期內，follower 只會投票一次票，且投票先來先得；

• Candidate 存儲的日誌至少要和 follower 一樣新（安全性準則），否則拒絕投票；

‍

（2）投票未超過半數，選舉失敗：

• 當 Candidate 沒有獲得超過半數的投票時，說明多個 Candidate 競爭投票導致過於分散，或者出現了丟包現象。此時，認爲當期任期選舉失敗，任期 TermId+1，然後發起新一輪選舉；

• 上述機制可能出現多個 Candidate 競爭投票，導致每個 Candidate 一直得不到超過半數的票，最終導致無限選舉投票循環；

• 投票分散問題解決：Raft 會給每個 Candidate 在固定時間內隨機確認一個超時時間（一般爲 150-300ms）。這麼做可以儘量避免新的一次選舉出現多個 Candidate 競爭投票的現象；

（3）收到其他 Leader 通信請求：

• 如果 Candidate 收到其他聲稱自己是 Leader 的請求的時候，通過任期 TermId 來判斷是否處理；

• 如果請求的任期 TermId 不小於 Candidate 當前任期 TermId，那麼 Candidate 會承認該 Leader 的合法地位並轉化爲 Follower；

• 否則，拒絕這次請求，並繼續保持 Candidate；

簡單地說，Leader Election 領導選舉通過若干的投票原則，保證一次選舉有且僅可能最多選出一個 leader，從而解決了腦裂問題。

2. Log Replication 日誌複製

選舉 leader 成功後，整個集羣就可以正常對外提供服務了。Leader 接收所有客戶端請求，然後轉化爲 log 複製命令，發送通知其他節點完成日誌複製請求。每個日誌複製請求包括狀態機命令 & 任期號，同時還有前一個日誌的任期號和日誌索引。狀態機命令表示客戶端請求的數據操作指令，任期號表示 leader 的當前任期。

follower 收到日誌複製請求的處理流程：

（1）follower 會使用前一個日誌的任期號和日誌索引來對比自己的數據：

• 如果相同，接收復制請求，回覆 ok；

• 否則回拒絕複製當前日誌，回覆 error；

（2）leader 收到拒絕複製的回覆後，繼續發送節點日誌複製請求，不過這次會帶上更前面的一個日誌任期號和索引；

（3）如此循環往復，直到找到一個共同的任期號 & 日誌索引。此時 follower 從這個索引值開始複製，最終和 leader 節點日誌保持一致；

（4）日誌複製過程中，Leader 會無限重試直到成功。如果超過半數的節點複製日誌成功，就可以任務當前數據請求達成了共識，即日誌可以 commite 提交了；

綜上，Log Replication 日誌複製有兩個特點：

（1）如果在不同日誌中的兩個條目有着相同索引和任期號，則所存儲的命令是相同的，這點是由 leader 來保證的；

（2）如果在不同日誌中的兩個條目有着相同索引和任期號，則它們之間所有條目完全一樣，這點是由日誌複製的規則來保證的；

舉個例子，最上面表示日誌索引，這個是保證唯一性。每個方塊代表指定任期內的數據操作，目前來看，LogIndex 1-4 的日誌已經完成同步，LogIndex 5 的正在同步，LogIndex6 還未開始同步。Raft 日誌提交的過程有點類似兩階段原子提交協議 2PC，不過和 2PC 的最大區別是，Raft 要求超過一般節點同意即可 commited，2PC 要求所有節點同意才能 commited。

日誌不一致問題：在正常情況下，leader 和 follower 的日誌複製能夠保證整個集羣的一致性，但是遇到 leader 崩潰的時候，leader 和 follower 日誌可能出現了不一致的狀態，此時 follower 相比 leader 缺少部分日誌。

爲了解決數據不一致性，Raft 算法規定 follower 強制複製 leader 節日的日誌，即 follower 不一致日誌都會被 leader 的日誌覆蓋，最終 follower 和 leader 保持一致。簡單的說，從前向後尋找 follower 和 leader 第一個公共 LogIndex 的位置，然後從這個位置開始，follower 強制複製 leader 的日誌。但是這麼多還有其他的安全性問題，所以需要引入 Safety 安全性規則。

3. Safety 安全性

當前的 Leader election 領導選舉和 Log replication 日誌複製並不能保證 Raft 算法的安全性，在一些特殊情況下，可能導致數據不一致，所以需要引入下面安全性規則。

（1）Election Safety 選舉安全性：避免腦裂問題

選舉安全性要求一個任期 Term 內只能有一個 leader，即不能出現腦裂現象，否者 raft 的日誌複製原則很可能出現數據覆蓋丟失的問題。Raft 算法通過規定若干投票原則來解決這個問題：

• 一個任期內，follower 只會投票一次票，且先來先得；

• Candidate 存儲的日誌至少要和 follower 一樣新；

• 只有獲得超過半數投票纔有機會成爲 leader；

（2）Leader Append-Only 日誌只能由 leader 添加修改

Raft 算法規定，所有的數據請求都要交給 leader 節點處理，要求：

• leader 只能日誌追加日誌，不能覆蓋日誌；

• 只有 leader 的日誌項才能被提交，follower 不能接收寫請求和提交日誌；

• 只有已經提交的日誌項，才能被應用到狀態機中；

• 選舉時限制新 leader 日誌包含所有已提交日誌項；

（3）Log Matching 日誌匹配特性

這點主要是爲了保證日誌的唯一性，要求：

• 如果在不同日誌中的兩個條目有着相同索引和任期號，則所存儲的命令是相同的；

• 如果在不同日誌中的兩個條目有着相同索引和任期號，則它們之間所有條目完全一樣；

（4）Leader Completeness 選舉完備性：leader 必須具備最新提交日誌

Raft 規定：只有擁有最新提交日誌的 follower 節點纔有資格成爲 leader 節點。具體做法：candidate 競選投票時會攜帶最新提交日誌，follower 會用自己的日誌和 candidate 做比較。

• 如果 follower 的更新，那麼拒絕這次投票；

• 否則根據前面的投票規則處理。這樣就可以保證只有最新提交節點成爲 leader；

因爲日誌提交需要超過半數的節點同意，所以針對日誌同步落後的 follower（還未同步完全部日誌，導致落後於其他節點）在競選 leader 的時候，肯定拿不到超過半數的票，也只有那些完成同步的纔有可能獲取超過半數的票成爲 leader。

日誌更新判斷方式是比較日誌項的 term 和 index：

• 如果 TermId 不同，選擇 TermId 最大的；

• 如果 TermId 相同，選擇 Index 最大的；

下面舉個例子來解釋爲什麼需要這個原則，如下圖，假如集羣中 follower4 在 LogIndex3 故障宕機，經過一段時間間，任期 Term3 的 leader 接收並提交了很多日誌（LogIndex1-5 已經提交，LogIndex6 正在複製中）。然後 follower4 恢復正常，在沒有和 leader 完成同步日誌的情況下，如果 leader 突然宕機，此時開始領導選舉。再假設在 Term4 follower4 當選 leader。根據日誌複製的規則，其他 follower 強制複製 leader 的日誌，那麼已經提交卻沒完成同步的日誌將會被強制覆蓋掉，這回導致已提交日誌被覆蓋。

（5）State Machine Safety 狀態機安全性：確保當前任期日誌提交

考慮到當前的日誌複製規則：

• 當前 follower 節點強制複製 leader 節點；

• 假如以前 Term 日誌複製超過半數節點，在面對當前任期日誌的節點比較中，很明顯當前任期節點更新，有資格成爲 leader；

上述兩條就可能出現已有任期日誌被覆蓋的情況，這意味着已複製超過半數的以前任期日誌被強制覆蓋了，和前面提到的日誌安全性矛盾。

所以，Raft 對日誌提交有額外安全機制：leader 只能提交當前任期 Term 的日誌，舊任期 Term（以前的數據）只能通過當前任期 Term 的數據提交來間接完成提交。簡單的說，日誌提交有兩個條件需要滿足：

• 當前任期；

• 複製結點超過半數；

下面舉個例子來解釋爲什麼需要這個原則，如下圖：

• 任期 Term2：

• follower1 是 leader，此時 LogIndex3 已經複製到 follower2，且正在給 follower3 複製，此時 follower 突然宕機；

• 任期 Term3：

• leader 選舉。follower5 發起投票，可以得到自己、follower3、follower4 的票（3/5），最終成爲 leader；

• 在任期 Term3 內，提交接收客戶請求並提交 LogIndex3-5，但是暫時未複製到其他節點，然後宕機；

• 任期 Term4：

• leader 選舉，follower1 發起選舉，可以得到自己、follower2、follower3、follower4 的票（4/5），最終成爲 leader；

• 此時 follower1 將 LogIndex3 複製到 follower3，此時 LogIndex3 複製超過半數，接着在本地提交了 LogIndex4，然後宕機；

• 任期 Term4：

• leader 選舉：follower5 發起選舉，可以得到自己、follower2、follower3、follower4 的票（4/5），最終成爲 leader；

• 此時其他節點需要強制複製 follower5 的日誌，那麼 follower1、follower2、follower3 的日誌被強制覆蓋掉。即雖然 LogIndex3 被複制到了超過半數節點，但也有可能被覆蓋掉；

如何解決這個問題呢？Raft 在日誌項提交上增加了限制：只有當前任期且複製超過半數的日誌纔可以提交。即只有 LogIndex4 提交後，LogIndex3 纔會被提交。

三、Paxos VS Raft

這個世界上只有一種一致性算法，那就是 Paxos。

Basic Paxos 算法沒有 leader proposer 角色，是一個純粹的去中心化的分佈式算法，但是它存在若干不足（只能單值共識 & 活鎖 & 網絡開銷大）。所以纔有了以 leader proposer 爲核心的 Multi Paxos 算法（由一個去中心化的算法變爲 leader-based 的算法）。Raft 算法相當於 Multi Paxos 的進一步優化，主要通過增加兩個限制：

（1）日誌添加次序性：

• Raft 要求日誌必須要串行連續添加的；

• Multi Paxos 可以併發添加日誌，沒有順序性要求，所以日誌可能存在空洞現象；

（2）選主限制：

• Raft 要求只有擁有最新日誌的節點纔有資格當選 leader，因爲日誌是串行連續添加的，所以 Raft 能夠根據日誌確認最新節點；

• 在 Multi Paxos 算法中由於日誌是併發添加的，所以無法確認最新日誌的節點，所以 Multi Paxos 可以選擇任意節點作爲了 leader proposer 節點，成爲 leader 節點後需要把其他日誌補全；

下面是我個人的理解：

• 作爲分佈式算法，Raft 的規則限制很多，但是每個規則都簡單易懂，最重要的是 leader-based 的，整個程序是一個串行的流程，這使得更加容易理解和實現；

• 作爲對比，Multi Paxos 的限制就很少了，每個節點都可以成爲 leader，併發添加日誌，這使得理解和落地就沒那麼簡單；

• 不同業務場景下有着不同的述求，所以一致性算法選擇 Multi Paxos 還是 Raft 看各自需求。

四、總結

學習總結分佈式一致性算法 Paxos 和 Raft 對我們理解、設計、實現、部署、測試分佈式系統都大有益處，希望本文能與大家共同商榷。

作者簡介

張輝，騰訊後臺開發工程師，主要負責騰訊霧計算平臺 PCDN SDK 相關的業務，畢業於南京大學計算機系。

推薦關注「數據分析與開發」，提升數據技能

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