Raft 算法原理及其在 CMQ 中的應用（上）
導語
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故障也可以在極短的時間內恢復，任何情況下系統都一直保持強一致性，為此犧牲了部分可用性(大多數節點故障時，概率極低)。不過，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算法只需要大多數節點成功即可，少量節點處理緩慢不會延緩整體系統運行。
原文鏈接：https://cloud.tencent.com/community/article/678192
【本文是51CTO專欄作者“騰訊云技術社區”的原創稿件，轉載請通過51CTO聯系原作者獲取授權】
