深入剖析共識性算法 Raft

作者：vivo 互聯網服務器團隊 -ZhangPeng

一、 Raft 簡介

1.1 Raft 簡介

Raft** 是一種爲了管理日誌複製的分佈式一致性算法。**Raft 出現之前，Paxos 一直是分佈式一致性算法的標準。Paxos 難以理解，更難以實現。Raft 的設計目標是簡化 Paxos，使得算法既容易理解，也容易實現。

Paxos 和 Raft 都是分佈式一致性算法，這個過程如同投票選舉領袖（Leader），參選者（Candidate）需要說服大多數投票者（Follower）投票給他，一旦選舉出領袖，就由領袖發號施令。Paxos 和 Raft 的區別在於選舉的具體過程不同。

Raft 可以解決分佈式 CAP 理論中的 CP，即 一致性（C：Consistency） 和 分區容忍性（P：Partition Tolerance），並不能解決 可用性（A：Availability） 的問題。

1.2 分佈一致性

分佈式一致性 (distributed consensus) 是分佈式系統中最基本的問題，用來保證一個分佈式系統的可靠性以及容錯能力。簡單來說，分佈式一致性是指多個服務器的保持狀態一致。

在分佈式系統中，可能出現各種意外（斷電、網絡擁塞、CPU / 內存耗盡等等），使得服務器宕機或無法訪問，最終導致無法和其他服務器保持狀態一致。爲了應對這種情況，就需要有一種一致性協議來進行容錯，使得分佈式系統中即使有部分服務器宕機或無法訪問，整體依然可以對外提供服務。

以容錯方式達成一致，自然不能要求所有服務器都達成一致狀態，只要超過半數以上的服務器達成一致就可以了。假設有 N 臺服務器， 大於等於 N / 2 + 1 臺服務器就算是半數以上了 。

1.3 複製狀態機

複製狀態機（Replicated State Machines） 是指一組服務器上的狀態機產生相同狀態的副本，並且在一些機器宕掉的情況下也可以繼續運行。一致性算法管理着來自客戶端指令的複製日誌。狀態機從日誌中處理相同順序的相同指令，所以產生的結果也是相同的。

圖片

複製狀態機通常都是基於複製日誌實現的，如上圖。每一個服務器存儲一個包含一系列指令的日誌，並且按照日誌的順序進行執行。每一個日誌都按照相同的順序包含相同的指令，所以每一個服務器都執行相同的指令序列。因爲每個狀態機都是確定的，每一次執行操作都產生相同的狀態和同樣的序列。

保證複製日誌相同就是一致性算法的工作了。在一臺服務器上，一致性模塊接收客戶端發送來的指令然後增加到自己的日誌中去。它和其他服務器上的一致性模塊進行通信來保證每一個服務器上的日誌最終都以相同的順序包含相同的請求，儘管有些服務器會宕機。一旦指令被正確的複製，每一個服務器的狀態機按照日誌順序處理他們，然後輸出結果被返回給客戶端。因此，服務器集羣看起來形成一個高可靠的狀態機。

實際系統中使用的一致性算法通常含有以下特性：

安全性保證（絕對不會返回一個錯誤的結果）：在非拜占庭錯誤情況下，包括網絡延遲、分區、丟包、冗餘和亂序等錯誤都可以保證正確。

**可用性：**集羣中只要有大多數的機器可運行並且能夠相互通信、和客戶端通信，就可以保證可用。因此，一個典型的包含 5 個節點的集羣可以容忍兩個節點的失敗。服務器被停止就認爲是失敗。他們當有穩定的存儲的時候可以從狀態中恢復回來並重新加入集羣。

**不依賴時序來保證一致性：**物理時鐘錯誤或者極端的消息延遲只有在最壞情況下才會導致可用性問題。

通常情況下，一條指令可以儘可能快的在集羣中大多數節點響應一輪遠程過程調用時完成。小部分比較慢的節點不會影響系統整體的性能。

1.4 RAFT 應用

通過 RAFT 提供的複製狀態機，可以解決分佈式系統的複製、修復、節點管理等問題。Raft 極大的簡化當前分佈式系統的設計與實現，讓開發者只關注於業務邏輯，將其抽象實現成對應的狀態機即可。基於這套框架，可以構建很多分佈式應用：

分佈式鎖服務，比如 Zookeeper

分佈式存儲系統，比如分佈式消息隊列、分佈式塊系統、分佈式文件系統、分佈式表格系統等，比如大名鼎鼎的 Redis 就是基於 Raft 實現分佈式一致性

高可靠元信息管理，比如各類 Master 模塊的 HA

二、 Raft 基礎

Raft 將一致性問題分解成了三個子問題：**選舉 Leader、****日誌複製、**安全性。

在後續章節，會詳細講解這個子問題。現在，先了解一下 Raft 的一些核心概念。

2.1 服務器角色

在 Raft 中，任何時刻，每個服務器都處於這三個角色之一 ：

Leader - 領導者，通常一個系統中是一主（Leader）多從（Follower）。Leader 負責處理所有的客戶端請求。

Follower - 跟隨者，不會發送任何請求，只是簡單的** 響應來自 Leader 或者 Candidate 的請求**。

Candidate - 參選者，選舉新 Leader 時的臨時角色。

圖片

圖示說明：

• Follower 只響應來自其他服務器的請求。在一定時限內，如果 Follower 接收不到消息，就會轉變成 Candidate，併發起選舉。

• Candidate 向 Follower 發起投票請求，如果獲得集羣中半數以上的選票，就會轉變爲 Leader。

• 在一個 Term 內，Leader 始終保持不變，直到下線了。Leader 需要週期性向所有 Follower 發送心跳消息，以阻止 Follower 轉變爲 Candidate。

2.2 任期

圖片

Raft 把時間分割成任意長度的 任期（Term），任期用連續的整數標記。每一段任期從一次選舉開始。Raft 保證了在一個給定的任期內，最多隻有一個領導者。

如果選舉成功，Leader 會管理整個集羣直到任期結束。

如果選舉失敗，那麼這個任期就會因爲沒有 Leader 而結束。

不同服務器節點觀察到的任期轉換狀態可能不一樣：

服務器節點可能觀察到多次的任期轉換。

服務器節點也可能觀察不到任何一次任期轉換。

任期在 Raft 算法中充當邏輯時鐘的作用，使得服務器節點可以查明一些過期的信息（比如過期的 Leader）。每個服務器節點都會存儲一個當前任期號，這一編號在整個時期內單調的增長。當服務器之間通信的時候會交換當前任期號。

如果一個服務器的當前任期號比其他人小，那麼他會更新自己的編號到較大的編號值。

如果一個 Candidate 或者 Leader 發現自己的任期號過期了，那麼他會立即恢復成跟隨者狀態。

如果一個節點接收到一個包含過期的任期號的請求，那麼他會直接拒絕這個請求。

數據可視化的應用場景越來越廣泛，數據可以呈現爲更多豐富的可視化形式，使用戶能夠更加輕易、便捷的獲取並理解數據傳達的信息。

2.3 RPC

Raft 算法中服務器節點之間的通信使用 遠程過程調用（RPC）。基本的一致性算法只需要兩種 RPC：

RequestVote RPC - 請求投票 RPC，由 Candidate 在選舉期間發起。

AppendEntries RPC - 附加條目 RPC，由 Leader 發起，用來複制日誌和提供一種心跳機制。

三、選舉 Leader

3.1 選舉規則

**Raft 使用一種心跳機制來觸發 Leader 選舉。**Leader 需要週期性的向所有 Follower 發送心跳消息，以此維持自己的權威並阻止新 Leader 的產生。

每個 Follower 都設置了一個隨機的競選超時時間，一般爲 150ms ~ 300ms，如果在競選超時時間內沒有收到 Leader 的心跳消息，就會認爲當前 Term 沒有可用的 Leader，併發起選舉來選出新的 Leader。開始一次選舉過程，Follower 先要增加自己的當前 Term 號，並轉換爲 Candidate。

Candidate 會並行的向集羣中的所有服務器節點發送投票請求（RequestVote RPC），它會保持當前狀態直到以下三件事情之一發生：

自己成爲 Leader

其他的服務器成爲 Leader

沒有任何服務器成爲 Leader

3.1.1 自己成爲 Leader

當一個 Candidate 從整個集羣半數以上的服務器節點獲得了針對同一個 Term 的選票，那麼它就贏得了這次選舉併成爲 Leader。每個服務器最多會對一個 Term 投出一張選票，按照先來先服務（FIFO）的原則。要求半數以上選票的規則確保了最多隻會有一個 Candidate 贏得此次選舉。

一旦 Candidate 贏得選舉，就立即成爲 Leader。然後它會向其他的服務器發送心跳消息來建立自己的權威並且阻止新的領導人的產生。

3.1.2 其他的服務器成爲 Leader

等待投票期間，Candidate 可能會從其他的服務器接收到聲明它是 Leader  的 AppendEntries RPC。

如果這個 Leader 的 Term 號（包含在此次的 RPC 中）不小於 Candidate 當前的 Term，那麼 Candidate 會承認 Leader 合法並回到 Follower 狀態。

如果此次 RPC 中的 Term 號比自己小，那麼 Candidate 就會拒絕這個消息並繼續保持 Candidate 狀態。

3.1.3 沒有任何服務器成爲 Leader

如果有多個 Follower 同時成爲 Candidate，那麼選票可能會被瓜分以至於沒有 Candidate 可以贏得半數以上的投票。當這種情況發生的時候，每一個 Candidate 都會競選超時，然後通過增加當前 Term 號來開始一輪新的選舉。然而，沒有其他機制的話，選票可能會被無限的重複瓜分。

Raft 算法使用隨機選舉超時時間的方法來確保很少會發生選票瓜分的情況，就算髮生也能很快的解決。爲了阻止選票起初就被瓜分，競選超時時間是一個隨機的時間，在一個固定的區間（例如 150-300 毫秒）隨機選擇，這樣可以把選舉都分散開。

以至於在大多數情況下，只有一個服務器會超時，然後它贏得選舉，成爲 Leader，並在其他服務器超時之前發送心跳包。

同樣的機制也被用在選票瓜分的情況下：每一個 Candidate 在開始一次選舉的時候會重置一個隨機的選舉超時時間，然後在超時時間內等待投票的結果；這樣減少了在新的選舉中另外的選票瓜分的可能性。

理解了上面的選舉規則後，我們通過動圖來加深認識。

3.2 單 Candidate 選舉

1. 下圖表示一個分佈式系統的最初階段，此時只有 Follower，沒有 Leader。Follower A 等待一個隨機的選舉超時時間之後，沒收到 Leader 發來的心跳消息。因此，將 Term 由 0 增加爲 1，轉換爲 Candidate，進入選舉狀態。

圖片

2. 此時，A 向所有其他節點發送投票請求。

圖片

3. 其它節點會對投票請求進行回覆，如果超過半數以上的節點投票了，那麼該 Candidate 就會立即變成 Term 爲 1 的 Leader。

圖片

4. Leader 會週期性地發送心跳消息給所有 Follower，Follower 接收到心跳包，會重新開始計時。

圖片

3.3 多 Candidate 選舉

1. 1 如果有多個 Follower 成爲 Candidate，並且所獲得票數相同，那麼就需要重新開始投票。例如下圖中 Candidate B 和 Candidate D 都發起 Term 爲 4 的選舉，且都獲得兩票，因此需要重新開始投票。

圖片

2) 當重新開始投票時，由於每個節點設置的隨機競選超時時間不同，因此能下一次再次出現多個 Candidate 並獲得同樣票數的概率很低。

圖片

四、日誌複製

4.1 日誌格式

**日誌由含日誌索引（log index）**的日誌條目（log entry）組成。每個日誌條目包含它被創建時的 Term 號（下圖中方框中的數字），和一個複製狀態機需要執行的指令。如果一個日誌條目被複制到半數以上的服務器上，就被認爲可以提交（Commit）了。

日誌條目中的 Term 號被用來檢查是否出現不一致的情況。

日誌條目中的日誌索引（一個整數值）用來表明它在日誌中的位置。

圖片

Raft 日誌同步保證如下兩點；圖示說明：

如果不同日誌中的兩個日誌條目有着相同的日誌索引和 Term，則它們所存儲的命令是相同的。

這個特性基於這條原則：Leader 最多在一個 Term 內、在指定的一個日誌索引上創建一條日誌條目，同時日誌條目在日誌中的位置也從來不會改變。

如果不同日誌中的兩個日誌條目有着相同的日誌索引和 Term，則它們之前的所有條目都是完全一樣的。

這個特性由 AppendEntries RPC 的一個簡單的一致性檢查所保證。在發送 AppendEntries RPC 時，Leader 會把新日誌條目之前的日誌條目的日誌索引和 Term 號一起發送。如果 Follower 在它的日誌中找不到包含相同日誌索引和 Term 號的日誌條目，它就會拒絕接收新的日誌條目。

4.2 日誌複製流程

圖片

Leader 負責處理所有客戶端的請求。

Leader 把請求作爲日誌條目加入到它的日誌中，然後並行的向其他服務器發送 AppendEntries RPC 請求，要求 Follower 複製日誌條目。

Follower 複製成功後，返回確認消息。

當這個日誌條目被半數以上的服務器複製後，Leader 提交這個日誌條目到它的複製狀態機，並向客戶端返回執行結果。

注意：如果 Follower 崩潰或者運行緩慢，再或者網絡丟包，Leader 會不斷的重複嘗試發送 AppendEntries RPC 請求 （儘管已經回覆了客戶端），直到所有的跟隨者都最終複製了所有的日誌條目。

下面，通過一組動圖來加深認識：

1. 來自客戶端的修改都會被傳入 Leader。注意該修改還未被提交，只是寫入日誌中。

圖片

2)Leader 會把修改複製到所有 Follower。

圖片

3)Leader 會等待大多數的 Follower 也進行了修改，然後纔將修改提交。

圖片

4. 此時 Leader 會通知的所有 Follower 讓它們也提交修改，此時所有節點的值達成一致。

圖片

4.3 日誌一致性

一般情況下，Leader 和 Followers 的日誌保持一致，因此日誌條目一致性檢查通常不會失敗。然而，Leader 崩潰可能會導致日誌不一致：舊的 Leader 可能沒有完全複製完日誌中的所有條目。

4.3.1 Leader 和 Follower 日誌不一致的可能

Leader 和 Follower 可能存在多種日誌不一致的可能。

圖片

圖示說明：上圖闡述了 Leader 和 Follower 可能存在多種日誌不一致的可能，每一個方框表示一個日誌條目，裏面的數字表示任期號 。

當一個 Leader 成功當選時，Follower 可能出現以下情況（a-f）：

存在未更新日誌條目，如（a、b）。

存在未提交日誌條目，如（c、d）。

或兩種情況都存在，如（e、f）。

例如，場景 f 可能會這樣發生，某服務器在 Term2 的時候是 Leader，已附加了一些日誌條目到自己的日誌中，但在提交之前就崩潰了；很快這個機器就被重啓了，在 Term3 重新被選爲 Leader，並且又增加了一些日誌條目到自己的日誌中；在 Term 2 和 Term 3 的日誌被提交之前，這個服務器又宕機了，並且在接下來的幾個任期裏一直處於宕機狀態。

4.3.2 Leader 和 Follower 日誌一致的保證

Leader 通過強制 Followers 複製它的日誌來處理日誌的不一致，Followers 上的不一致的日誌會被 Leader 的日誌覆蓋。

Leader 爲了使 Followers 的日誌同自己的一致，Leader 需要找到 Followers 同它的日誌一致的地方，然後覆蓋 Followers 在該位置之後的條目。

Leader 會從後往前試，每次日誌條目失敗後嘗試前一個日誌條目，直到成功找到每個 Follower 的日誌一致位點，然後向後逐條覆蓋 Followers 在該位置之後的條目。

五、安全性

前面描述了 Raft 算法是如何選舉 Leader 和複製日誌的。

Raft 還增加了一些限制來完善 Raft 算法，以保證安全性：保證了任意 Leader 對於給定的 Term，都擁有了之前 Term 的所有被提交的日誌條目。

5.1 選舉限制

擁有最新的已提交的日誌條目的 Follower 纔有資格成爲 Leader。

Raft 使用投票的方式來阻止一個 Candidate 贏得選舉除非這個 Candidate 包含了所有已經提交的日誌條目。Candidate 爲了贏得選舉必須聯繫集羣中的大部分節點，這意味着每一個已經提交的日誌條目在這些服務器節點中肯定存在於至少一個節點上。如果 Candidate 的日誌至少和大多數的服務器節點一樣新（這個新的定義會在下面討論），那麼他一定持有了所有已經提交的日誌條目。

RequestVote RPC 實現了這樣的限制：RequestVote RPC 中包含了 Candidate 的日誌信息， Follower 會拒絕掉那些日誌沒有自己新的投票請求。

5.1.1 場如何判斷哪個日誌條目比較新？

Raft 通過比較兩份日誌中最後一條日誌條目的日誌索引和 Term 來判斷哪個日誌比較新。

先判斷 Term，哪個數值大即代表哪個日誌比較新。

如果 Term 相同，再比較 日誌索引，哪個數值大即代表哪個日誌比較新。

5.1.2 提交舊任期的日誌條目

一個當前 Term 的日誌條目被複制到了半數以上的服務器上，Leader 就認爲它是可以被提交的。如果這個 Leader 在提交日誌條目前就下線了，後續的 Leader 可能會覆蓋掉這個日誌條目。

圖片

**圖示說明：**上圖解釋了爲什麼 Leader 無法對舊 Term 的日誌條目進行提交。

• 階段 (a) ，S1 是 Leader，且 S1 寫入日誌條目爲 (Term 2，日誌索引 2），只有 S2 複製了這個日誌條目。

• 階段 (b)，S1 下線，S5 被選舉爲 Term3 的 Leader。S5 寫入日誌條目爲 (Term 3，日誌索引 2）。

• 階段 (c)，S5 下線，S1 重新上線，並被選舉爲 Term4 的 Leader。此時，Term 2 的那條日誌條目已經被複制到了集羣中的大多數節點上，但是還沒有被提交。

• 階段 (d)，S1 再次下線，S5 重新上線，並被重新選舉爲 Term3 的 Leader。然後 S5 覆蓋了日誌索引 2 處的日誌。

• 階段 (e)，如果階段 (d) 還未發生，即 S1 再次下線之前，S1 把自己主導的日誌條目複製到了大多數節點上，那麼在後續 Term 裏面這些新日誌條目就會被提交。這樣在同一時刻就同時保證了，之前的所有舊日誌條目就會被提交。

Raft 永遠不會通過計算副本數目的方式去提交一個之前 Term 內的日誌條目。只有 Leader 當前 Term 裏的日誌條目通過計算副本數目可以被提交；一旦當前 Term 的日誌條目以這種方式被提交，那麼由於日誌匹配特性，之前的日誌條目也都會被間接的提交。

當 Leader 複製之前任期裏的日誌時，Raft 會爲所有日誌保留原始的 Term，這在提交規則上產生了額外的複雜性。在其他的一致性算法中，如果一個新的領導人要重新複製之前的任期裏的日誌時，它必須使用當前新的任期號。

Raft 使用的方法更加容易辨別出日誌，因爲它可以隨着時間和日誌的變化對日誌維護着同一個任期編號。另外，和其他的算法相比，Raft 中的新領導人只需要發送更少日誌條目（其他算法中必須在他們被提交之前發送更多的冗餘日誌條目來爲他們重新編號）。

六、日誌壓縮

在實際的系統中，不能讓日誌無限膨脹，否則系統重啓時需要花很長的時間進行恢復，從而影響可用性。Raft 採用對整個系統進行快照來解決，快照之前的日誌都可以丟棄。

每個副本獨立的對自己的系統狀態生成快照，並且只能對已經提交的日誌條目生成快照。快照包含以下內容：

日誌元數據。最後一條已提交的日誌條目的日誌索引和 Term。這兩個值在快照之後的第一條日誌條目的 AppendEntries RPC 的完整性檢查的時候會被用上。

系統當前狀態。

當 Leader 要發送某個日誌條目，落後太多的 Follower 的日誌條目會被丟棄，Leader 會將快照發給 Follower。或者新上線一臺機器時，也會發送快照給它。

圖片

生成快照的頻率要適中，頻率過高會消耗大量 I/O 帶寬；頻率過低，一旦需要執行恢復操作，會丟失大量數據，影響可用性。推薦當日志達到某個固定的大小時生成快照。

生成一次快照可能耗時過長，影響正常日誌同步。可以通過使用 copy-on-write 技術避免快照過程影響正常日誌同步。

**說明：**本文僅闡述 Raft 算法的核心內容，不包括算法論證、評估等

七、參考資料

1.Raft 一致性算法論文原文

2.Raft 一致性算法論文譯文

3.Raft 作者講解視頻

4.Raft 作者講解視頻對應的 PPT

5. 分佈式系統的 Raft 算法

6.Raft 算法詳解

7.Raft: Understandable Distributed 

Consensus

8.sofa-jraft - 螞蟻金服的 Raft 算法實現庫（Java 版）

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