Raft 演算法原理及其在 CMQ 中的應用（上）

02-10

歡迎大家前往騰訊雲技術社區，獲取更多騰訊海量技術實踐乾貨哦~

作者：陳雲，騰訊雲中間件團隊的一員

導語

Raft演算法是一種分散式一致性演算法。與paxos相比，它更易理解和工程化。我們完整實現了該演算法並將其應用在自研的高可靠消息中間件CMQ中，同時沉澱出對外通用的Raft演算法庫。本文主要介紹Raft演算法的原理、工程化時遇到的問題與解決方案、以及改進性能的措施。

一、背景介紹

分散式系統是指一組獨立的計算機，通過網路協同工作的系統，客戶看來就如同單台機器在工作。隨著互聯網時代數據規模的爆髮式增長，傳統的單機系統在性能和可用性上已經無法勝任，分散式系統具有擴展性強，可用性高，廉價高效等優點，得以廣泛應用。

但與單機系統相比，分散式系統在實現上要複雜很多。CAP理論是分散式系統的理論基石，它提出在以下3個要素中：

Consistency（強一致性）：任何客戶端都可以讀取到其他客戶端最近的更新。

Availability（可用性）：系統一直處於可服務狀態。

Partition-tolenrance（分區可容忍性）：單機故障或網路分區，系統仍然可以保證強一致性和可用性。

一個分散式系統最多只能滿足其中2個要素。對於分散式系統而言，P顯然是必不可少的，那麼只能在AP和CP之間權衡。AP系統犧牲強一致性，這在某些業務場景下（如金融類）是不可接受的，CP系統可以滿足這類需求，問題的關鍵在於會犧牲多少可用性。傳統的主備強同步模式雖然可以保證一致性，但一旦機器故障或網路分區系統將變得不可用。paxos和raft等一致性演算法的提出，彌補了這一缺陷。它們在保證CP的前提下，只要求大多數節點可以正常互聯，系統便可以一直處於可用狀態，可用性上顯著提高。paxos的理論性偏強，開發者需要自己處理很多細節，這也是它有很多變種的原因，相對而言raft更易理解和工程化，一經提出便廣受歡迎。

在我們關注的消息中間件領域，金融支付類業務往往對數據的強一致性和高可靠性有嚴格要求。強一致性：A給B轉賬100元，系統返回A轉賬成功。此後B查詢餘額時應該能顯示收到100元，如果發現並未收到或隔一段時間後才收到，那這樣的系統非強一致性；高可靠性：一個請求如果返回客戶成功，那麼需要保證請求結果不丟失。

在對主流的消息中間件進行調研後，發現它們在應對這種場景時都存在一定的不足：

RabbitMQ：一個請求需要在所有節點上處理2次才能保證一致性，性能不高。

Kafka：kafka主要應用在日誌、大數據等方向，少量丟失數據業務可以忍受，但不適合要求數據高可靠性的系統。

RocketMQ：未採用一致性演算法，如果配置成非同步模式可能丟失數據，同步模式下節點故障或網路分區都會影響可用性。

SQS：只提供最終一致性，不保證強一致性。

鑒於以上分析，我們設計開發了基於Raft的強一致高可靠消息中間件CMQ。接下來會詳細介紹raft演算法原理細節、如何應用在CMQ中在保證消息可靠不丟失以及實現過程中我們在性能方面所作的優化。

二、Raft演算法核心原理

2.1 概述

raft演算法是Diego Ongaro博士在論文《In Search of an Understandable Consensus Algorithm》,2014 USENIX中首次提出，演算法主要包括選舉和日誌同步兩部分:

第一階段選舉：

從集群中選出一個合適的節點作為Leader。

第二階段日誌同步：

選舉出的Leader接收客戶端請求，將其轉為raft日誌。
Leader將日誌同步到其他節點，當大多數節點寫入成功後，日誌變為Committed，一經Committed日誌便不會再被篡改。
Leader故障時，切換到第一階段，重新選舉。

以下是貫穿raft演算法的重要術語：

Term： 節點當前所處的周期，可以看作一個文明所處的時代。

votedFor： 當前Term的投票信息，每個節點在給定的Term上只能投票一次。

Entry： raft日誌中的基本單元，包含index、term和user_data。其中index在日誌文件中順序分配，term為創建該entry的leader term，user_data 業務數據。

State : 節點角色（Leader、Candidate、Follower之一）。

CommitIndex：已提交到的日誌Index。

State Machine：狀態機。業務模塊，與Raft交互。

ApplyIndex：已應用到的日誌Index。

ElectionTime：選舉超時時間。

節點之間通過RPC通信來完成選舉和日誌同步，發送方在發送RPC時會攜帶自身的Term，接收方在處理RPC時有以下兩條通用規則：

RPC中的RTerm大於自身當前Term，更新自身Term = RTerm、votedFor = null，轉為Follower。
RPC中的RTerm小於自身當前Term，拒絕請求，響應包中攜帶自身的Term。

2.2 選舉

Raft演算法屬於強Leader模式，只有Leader可以處理客戶端的請求，Leader通過心跳維持自身地位，除非Leader故障或網路異常，否則Leader保持不變。選舉階段的目的就是為了從集群中選出合適的Leader節點。

選舉流程：

1.節點初始狀態均為Follower，Follower只被動接收請求，如果ElectionTime到期時仍未收到Leader的AppendEntry RPC，Follower認為當前沒有Leader，轉為Candidate。

2.Candidate在集群中廣播RequestVote RPC，嘗試競選Leader，其他節點收到後首先判斷是否同意本次選舉，並將結果返回給Candidate。如果Candidate收到大多數節點的同意響應，轉為Leader。

3.Leader接收客戶端請求，將其轉為Entry追加到日誌文件，同時通過AppendEntry RPC同步日誌Entry給其他節點。

下面通過一個案例詳細說明選舉流程。

1）初始狀態：3個節點組成的集群，初始均為Follower狀態，圖中方格部分代表節點的raft日誌。

2）發起選舉：節點1選舉定時器先到期，轉為Candidate，Term自增，更新voteFor=1(投票給自己），接著廣播RequestVote RPC給集群中其他節點，RequestVote RPC會攜帶節點的日誌信息。

3）響應選舉：節點2和3收到RequestVote RPC後，根據RPC規則，更新term和voteFor(term:6 , voteFor:null )；然後判斷是否同意本次選舉，如果已投票給別人，則拒絕本次選舉（這裡voteFor：null 未投票），如果RequestVote RPC中的日誌沒有自身全，也拒絕，否則同意（這裡節點1的日誌比2、3都更全）；最後通過voteReply RPC響應投票結果。

4）選舉完成：由於節點2和3都同意本次選舉，所以節點1在收到任何一個的voteReply RPC便轉為Leader（大多數同意即可）。

選舉超時值：

在選舉時可能會出現兩個節點的選舉定時器同時到期並發起選舉，各自得到一半選票導致選舉失敗，選舉失敗意味著系統沒有Leader，不可服務。如果選舉定時器是定值，很可能兩者再次同時到期。為了降低衝突的概率，選舉超時值採用隨機值的方式。此外，選舉超時值如果過大會導致Leader故障會很久才會再次選舉。選舉超時值通常取300ms~600ms之間的隨機值。

2.3日誌同步

選舉階段完成後，Leader節點開始接收客戶端請求，將請求封裝成Entry追加到raft日誌文件末尾，之後同步Entry到其他Follower節點。當大多數節點寫入成功後，該Entry被標記為committed，raft演算法保證了committed的Entry一定不會再被修改。

日誌同步具體流程：

1）Leader上為每個節點維護NextIndex、MatchIndex，NextIndex表示待發往該節點的Entry index，MatchIndex表示該節點已匹配的Entry index，同時每個節點維護CommitIndex表示當前已提交的Entry index。轉為Leader後會將所有節點的NextIndex置為自己最後一條日誌index+1，MatchIndex全置0，同時將自身CommitIndex置0。

2）Leader節點不斷將user_data轉為Entry追加到日誌文件末尾，Entry包含index、term和user_data，其中index在日誌文件中從1開始順序分配，term為Leader當前的term。

3）Leader通過AppendEntry RPC將Entry同步到Followers，Follower收到後校驗該Entry之前的日誌是否已匹配。如匹配則直接寫入Entry，返回成功；否則刪除不匹配的日誌，返回失敗。校驗是通過在AppendEntry RPC中攜帶待寫入Entry的前一條entry信息完成。

4）當Follower返回成功時，更新對應節點的NextIndex和MatchIndex，繼續發送後續的Entry。如果MatchIndex更新後，大多數節點的MatchIndex已大於CommitIndex，則更新CommitIndex。Follower返回失敗時回退NextIndex繼續發送，直到Follower返回成功。

5）Leader每次AppendEntry RPC中會攜帶當前最新的LeaderCommitIndex，Follower寫入成功時會將自身CommitIndex更新為Min(LastLogIndex,LeaderCommitIndex)。

同步過程中每次日誌的寫入均需刷盤以保證宕機時數據不丟失。

下面通過一個例子介紹日誌同步基本流程：

1）初始狀態所有節點的Term=2，CommitIndex=2，接著Leader收到一條y←9的請求，轉為Entry寫入日誌的末尾，Entry的index =3 term =1。

2）Leader通過AppendEntry RPC同步該Entry給2個Follower，RPC中包含前一條Entry信息（index=2 term =1），Follower收到後首先校驗前一條Entry是否與自身匹配（這裡匹配成功），之後寫入該Entry，返回Leader成功。

3）Leader在收到Follower的回包後，更新相應節點的NextIndex和MatchIndex，這時大多數節點MatchIndex已經大於CommitIndex，所以Leader更新CommitIndex=3。

4）Leader繼續發送AppendEntry到Follower，此時由於沒有新Entry，所以RPC中entry信息為空，LeaderCommitIndex為3。Follower收到後更新CommitIndex=3 (Min（3,3）)。

日誌衝突：

在日誌同步的過程中，可能會出現節點之間日誌不一致的問題。例如Follower寫日誌過慢、Leader切換導致舊Leader上未提交的臟數據等場景下都會發生。在Raft演算法中，日誌衝突時以Leader的日誌為準，Follower刪除不匹配部分。

如下圖所示，Follower節點與Leader節點的日誌都存在不一致問題，其中(a)、(b)節點日誌不全，(c)、(d)、(e)、(f)有衝突日誌。Leader首先從index=11(最後一條Entry index +1)開始發送AppendEntry RPC,Follower均返回不匹配，Leader收到後不斷回退。(a)、(b)在找到第一條匹配的日誌後正常同步，(c)、(d)、(e)、(f)在這個過程中會逐步刪除不一致的日誌，最終所有節點的日誌都與Leader一致。成為Leader節點後不會修改和刪除已存在的日誌，只會追加新的日誌。

2.4 演算法證明

Raft演算法的2個核心屬性：

1）已提交的日誌不會再修改；(可靠性)

2）所有節點上的數據一致。（一致性）

具體證明如下：

1）Leader Completeness：給定Term上提交的日誌一定存在於後續更高Term的 Leader上。（日誌不丟失）

選舉出的Leader一定包含當前已提交所有日誌：已提交的日誌存在於大多數節點上，而同意選舉的前提是候選者的日誌必須夠全或更新。一個不包含已提交日誌的節點必然不會得到大多數節點的選票(這些節點上都有已提交的日誌，不滿足日誌足夠全的前提)，也就無法成為Leader。
Leader節點不修改和刪除已存在日誌(演算法的約束)。

綜上所述，選舉和日誌同步時都不會破壞已提交的日誌，得證。

2）State Machine Safety：所有節點的數據最終一致。

根據Leader Completeness可知已提交的日誌不會再修改，業務的狀態機依次取出Entry中的user_data應用，最終所有節點的數據一致。

2.5集群管理

Raft演算法中充分考慮了工程化中集群管理問題，支持動態的添加節點到集群，剔除故障節點等。下面詳細描述添加和刪除節點流程。

添加節點

如下圖所示，集群中包含A B C，A為Leader，現在添加節點D。

1）清空D節點上的所有數據，避免有臟數據。

2）Leader將存量的日誌通過AppendEntry RPC同步到D，使D的數據跟上其他節點。

3）待D的日誌追上後，Leader A創建一條Config Entry，其中集群信息包含ABCD。

4）Leader A將Config Entry同步給B C D，Follower收到後應用，之後所有節點的集群信息都變為ABCD，添加完成。

註：在步驟2過程中,Leader仍在不斷接收客戶請求生成Entry，所以只要D與A日誌相差不大即認為D已追上。

刪除節點

如下圖所示，集群中原來包含A B C D，A為Leader，現在剔除節點D。

1) Leader A創建一條Config Entry，其中集群信息為ABC。

2) A將日誌通過AppendEntry RPC同步給節點B C。

3) A B C在應用該日誌後集群信息變為ABC，A不再發送AppendEntry給D，D從集群中移除。

4) 此時D的集群信息依舊為ABCD，在選舉超時到期後，發起選舉，為了防止D的干擾，引入額外機制：所有節點在正常接收Leader的AppendEntry時，拒絕其他節點發來的選舉請求。

5) 將D的數據清空並下線。

2.5 Raft應用

我們用State Matchine統一表示業務模塊，其通過ApplyIndex維護已應用到的日誌index。以下為Raft與狀態機交互的流程：

1）客戶端請求發往Leader節點。

2）Leader節點的Raft模塊將請求轉為Entry並同步到Followers。

3）大多數節點寫入成功後Raft模塊更新CommitIndex。

4）各節點的State Machine順序讀取ApplyIndex+1到CimmitIndex之間的Entry，取出其中的user_data並應用，完成後更新ApplyIndex。

5）Leader 上的State Machine通知客戶端操作成功。

6）如此循環。

2.6 快照管理

在節點重啟時，由於無法得知State Matchine當前ApplyIndex(除非每次應用完日誌都持久化ApplyIndex，還要保證是原子操作，代價較大)，所以必須清空State Matchine的數據，將ApplyIndex置為0,，從頭開始應用日誌，代價太大，可以通過定期創建快照的方式解決該問題。如下圖所示：

1）在應用完Entry 5 後，將當前State Matchine的數據連同Entry信息寫入快照文件。

2）如果節點重啟，首先從快照文件中恢復State Matchine，等價於應用了截止到Entry 5為止的所有Entry，但效率明顯提高。

3）將ApplyIndex置為5，之後從Entry 6繼續應用日誌，數據和重啟前一致。

快照的優點：

降低重啟耗時：通過snapshot +　raft log恢復，無需從第一條Entry開始。
節省空間：快照做完後即可刪除快照點之前的Raft日誌。

2.7異常場景及處理

Raft具有很強的容錯性，只要大多數節點正常互聯，即可保證系統的一致性和可用性，下面是一些常見的異常情況，以及他們的影響及處理：

異常場景影響及處理Leader故障短暫不可服務，自動選舉，客戶端須重試Follower或Candidate故障無影響網路分區大多數互聯時自動選舉，偽Leader節點重啟快照+raft日誌自動恢復大多數節點故障不可用（保證強一致性）選舉衝突暫時不可服務（隨機選舉時間保證極少出現該場景）

可以看到異常情況對系統的影響很小，即使是Leader故障也可以在極短的時間內恢復，任何情況下系統都一直保持強一致性，為此犧牲了部分可用性（大多數節點故障時，概率極低）。不過，Leader故障時新的Leader可能會包含舊Leader未提交或已提交但尚未通知客戶端的日誌，由於演算法規定成為Leader後不允許刪除日誌，所以這部分日誌會被新Leader同步並提交，但由於連接信息丟失，客戶端無法得知該情況，當發起重試後會出現重複數據，需要有冪等性保證。此外，raft的核心演算法都是圍繞Leader展開，網路分區時可能出現偽Leader問題，也需要特殊考慮。

以下是網路分區時產生偽Leader 的過程：

上述情況下，Leader與2個Follower網路異常，而2個Follower之間通信正常，由於收不到Leader的心跳，其中一個Follower發起選舉並成為Leader，原Leader成為偽Leader，接下來我們分析該場景下是否會影響系統的一致性：

寫一致性：發往新Leader的寫請求可以被提交，而發往偽Leader的請求無法得到提交，只有一個Leader在正常處理寫請求，所以不影響寫一致性。

讀一致性：如果讀請求不經過Raft同步，那麼當客戶端的寫請求被發往新Leader並執行成功後，讀請求發往了偽Leader並得到結果，就會造成數據不一致。有兩種方案可以解決該問題：

讀請求也經過Raft同步，這樣就不會有不一致的問題，但會增加系統負載。
讀請求收到後，Leader節點等待大多數節點再次響應心跳RPC，接著返回結果。

因為大多數節點響應心跳，說明當前一定沒有另一個Leader存在（大多數節點還與當前Leader維持租約，新Leader需要得到大多數投票）。

2.8 小結

Raft演算法具備強一致、高可靠、高可用等優點，具體體現在：

強一致性：雖然所有節點的數據並非實時一致，但Raft演算法保證Leader節點的數據最全，同時所有請求都由Leader處理，所以在客戶端角度看是強一致性的。
高可靠性：Raft演算法保證了Committed的日誌不會被修改，State Matchine只應用Committed的日誌，所以當客戶端收到請求成功即代表數據不再改變。Committed日誌在大多數節點上冗餘存儲，少於一半的磁碟故障數據不會丟失。
高可用性：從Raft演算法原理可以看出，選舉和日誌同步都只需要大多數的節點正常互聯即可，所以少量節點故障或網路異常不會影響系統的可用性。即使Leader故障，在選舉超時到期後，集群自發選舉新Leader，無需人工干預，不可用時間極小。但Leader故障時存在重複數據問題，需要業務去重或冪等性保證。
高性能：與必須將數據寫到所有節點才能返回客戶端成功的演算法相比，Raft演算法只需要大多數節點成功即可，少量節點處理緩慢不會延緩整體系統運行。