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

1)??RPC中的RTerm大于自身當(dāng)前Term，更新自身Term = RTerm、votedFor = null，轉(zhuǎn)為Follower。

2)??RPC中的RTerm小于自身當(dāng)前Term，拒絕請求，響應(yīng)包中攜帶自身的Term。

2.2?選舉算法

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

選舉流程如下：

1. ? ?節(jié)點初始狀態(tài)均為Follower，F(xiàn)ollower只被動接收請求，如果ElectionTime到期時仍未收到Leader的AppendEntry RPC，F(xiàn)ollower認(rèn)為當(dāng)前沒有Leader，轉(zhuǎn)為Candidate。
2. ? ?Candidate在集群中廣播RequestVote RPC，嘗試競選Leader，其他節(jié)點收到后首先判斷是否同意本次選舉，并將結(jié)果返回給Candidate。如果Candidate收到大多數(shù)節(jié)點的同意響應(yīng)，轉(zhuǎn)為Leader。
3. ? ?Leader接收客戶端請求，將其轉(zhuǎn)為Entry追加到日志文件，同時通過AppendEntry RPC同步日志Entry給其他節(jié)點。

選舉超時值：

在選舉時可能會出現(xiàn)兩個節(jié)點的選舉定時器同時到期并發(fā)起選舉，各自得到一半選票導(dǎo)致選舉失敗，選舉失敗意味著系統(tǒng)沒有Leader，不可服務(wù)。如果選舉定時器是定值，很可能兩者再次同時到期。為了降低沖突的概率，選舉超時值采用隨機值的方式。此外，選舉超時值如果過大會導(dǎo)致Leader故障會很久才會再次選舉。選舉超時值通常取300ms~600ms之間的隨機值。

2.3日志同步

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

日志同步具體流程：

1）Leader上為每個節(jié)點維護NextIndex、MatchIndex，NextIndex表示待發(fā)往該節(jié)點的Entry index，MatchIndex表示該節(jié)點已匹配的Entry index，同時每個節(jié)點維護CommitIndex表示當(dāng)前已提交的Entry index。轉(zhuǎn)為Leader后會將所有節(jié)點的NextIndex置為自己最后一條日志index+1，MatchIndex全置0，同時將自身CommitIndex置0。

2）Leader節(jié)點不斷將user_data轉(zhuǎn)為Entry追加到日志文件末尾，Entry包含index、term和user_data，其中index在日志文件中從1開始順序分配，term為Leader當(dāng)前的term。

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

4）當(dāng)Follower返回成功時，更新對應(yīng)節(jié)點的NextIndex和MatchIndex，繼續(xù)發(fā)送后續(xù)的Entry。如果MatchIndex更新后，大多數(shù)節(jié)點的MatchIndex已大于CommitIndex，則更新CommitIndex。Follower返回失敗時回退NextIndex繼續(xù)發(fā)送，直到Follower返回成功。

5）Leader每次AppendEntry RPC中會攜帶當(dāng)前最新的LeaderCommitIndex，F(xiàn)ollower寫入成功時會將自身CommitIndex更新為Min(LastLogIndex,LeaderCommitIndex)。

同步過程中每次日志的寫入均需刷盤以保證宕機時數(shù)據(jù)不丟失。

日志沖突：

在日志同步的過程中，可能會出現(xiàn)節(jié)點之間日志不一致的問題。例如Follower寫日志過慢、Leader切換導(dǎo)致舊Leader上未提交的臟數(shù)據(jù)等場景下都會發(fā)生。在Raft算法中，日志沖突時以Leader的日志為準(zhǔn)，F(xiàn)ollower刪除不匹配部分。

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

2.4集群管理

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

添加節(jié)點：

如下圖所示，集群中包含A B C，A為Leader，現(xiàn)在添加節(jié)點D。

1）??清空D節(jié)點上的所有數(shù)據(jù)，避免有臟數(shù)據(jù)。

2）??Leader將存量的日志通過AppendEntry RPC同步到D，使D的數(shù)據(jù)跟上其他節(jié)點。

3）??待D的日志追上后，Leader A創(chuàng)建一條Config Entry，其中集群信息包含ABCD。

4）??Leader A將Config Entry同步給B C D，F(xiàn)ollower收到后應(yīng)用，之后所有節(jié)點的集群信息都變?yōu)锳BCD，添加完成。

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

刪除節(jié)點：

如下圖所示，集群中原來包含A B C D，A為Leader，現(xiàn)在剔除節(jié)點D。

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

2)?A將日志通過AppendEntry RPC同步給節(jié)點B C。

3)?A B C在應(yīng)用該日志后集群信息變?yōu)锳BC，A不再發(fā)送AppendEntry給D，D從集群中移除。

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

5)?將D的數(shù)據(jù)清空并下線。

2.5?快照管理

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

1）?在應(yīng)用完Entry 5?后，將當(dāng)前State Matchine的數(shù)據(jù)連同Entry信息寫入快照文件。

2）?如果節(jié)點重啟，首先從快照文件中恢復(fù)State Matchine，等價于應(yīng)用了截止到Entry 5為止的所有Entry，但效率明顯提高。

3）?將ApplyIndex置為5，之后從Entry 6繼續(xù)應(yīng)用日志，數(shù)據(jù)和重啟前一致。

2.6異常場景及處理

Raft具有很強的容錯性，只要大多數(shù)節(jié)點正?；ヂ?lián)，即可保證系統(tǒng)的一致性和可用性，下面是一些常見的異常情況，以及他們的影響及處理：

可以看到異常情況對系統(tǒng)的影響很小，即使是Leader故障也可以在極短的時間內(nèi)恢復(fù)，任何情況下系統(tǒng)都一直保持強一致性，為此犧牲了部分可用性（大多數(shù)節(jié)點故障時，概率極低）。不過，Leader故障時新的Leader可能會包含舊Leader未提交或已提交但尚未通知客戶端的日志。由于算法規(guī)定成為Leader后不允許刪除日志，所以這部分日志會被新Leader同步并提交，但由于連接信息丟失，客戶端無法得知該情況。當(dāng)發(fā)起重試后會出現(xiàn)重復(fù)數(shù)據(jù)，需要有冪等性保證。此外，raft的核心算法都是圍繞Leader展開，網(wǎng)絡(luò)分區(qū)時可能出現(xiàn)偽Leader問題，也需要特殊考慮。

三?Raft在CMQ中的應(yīng)用和性能優(yōu)化

3.1 Raft算法在CMQ中的應(yīng)用

我們用State Matchine統(tǒng)一表示業(yè)務(wù)模塊，其通過ApplyIndex維護已應(yīng)用的日志index。以下為Raft與狀態(tài)機交互的流程：

1）客戶端請求發(fā)往Leader節(jié)點。

2）Leader節(jié)點的Raft模塊將請求轉(zhuǎn)為Entry并同步到Followers。

3）大多數(shù)節(jié)點寫入成功后Raft模塊更新CommitIndex。

4）各節(jié)點的State Machine順序讀取ApplyIndex+1到CimmitIndex之間的Entry，取出其中的user_data并應(yīng)用，完成后更新ApplyIndex。

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

6）如此循環(huán)。

下面介紹CMQ詳細(xì)的生產(chǎn)消費流程：

生產(chǎn)流程：

1）生產(chǎn)者將生產(chǎn)消息的請求發(fā)往Leader的Raft模塊。

2）Raft模塊完成Entry的創(chuàng)建和同步。

3）大多數(shù)節(jié)點上持久化并返回成功后Entry標(biāo)記為Committed。

4）所有節(jié)點的State Machine應(yīng)用該日志，取出實際的生產(chǎn)請求，將消息內(nèi)容寫入磁盤，更新ApplyIndex。該步驟不需要刷盤。

5）Leader回復(fù)客戶端Confirm，通知生產(chǎn)成功。

6）如果此后機器重啟，通過raft日志恢復(fù)生產(chǎn)消息，保證了已Confirm的消息不丟失。

消費流程：

1）消費者從Leader節(jié)點拉取消息。

2）Leader收到后從磁盤加載未刪除的消息投遞給客戶端。

3）客戶端處理完成后Ack消息，通知服務(wù)器刪除消息。

4）Ack請求經(jīng)Raft同步后標(biāo)記為Committed。

5）各節(jié)點狀態(tài)機應(yīng)用該日志，將消息對應(yīng)的bit置位，將其設(shè)置為已刪除并更新ApplyIndex。

6）通知客戶端刪除成功。

7）如果機器重啟，通過Raft日志恢復(fù)Ack請求，保證了已刪除的消息不會再投遞。

快照管理：

快照管理與業(yè)務(wù)緊密相關(guān)，不同系統(tǒng)快照制作的成本差異很大，CMQ中快照的內(nèi)容十分輕量，一次快照的耗時在毫秒級，平均5min創(chuàng)建一次，各節(jié)點獨立完成。實現(xiàn)上內(nèi)存中維護了一份動態(tài)的快照，制作快照時首先拷貝出動態(tài)快照的副本，之后處理流繼續(xù)更新動態(tài)快照，用拷貝出的副本創(chuàng)建快照文件，不影響實際的處理流?？煺站唧w內(nèi)容包括：

1）term：快照對應(yīng)Entry的term?（參照算法）

2）index：快照對應(yīng)Entry的?index?（參照算法）

3）node_info：Entry時的集群配置信息。

4）topic info：每個隊列一項。CMQ中同一隊列生產(chǎn)的消息順序?qū)懭?，分片存儲，因此只需記錄最后一個分片的狀態(tài)（分片文件名，文件偏移量）。

5）queue info：每個隊列一項。CMQ中采用bitmap記錄消息的刪除情況，在內(nèi)存中維護，在制作快照時dump到快照文件。

3.2 Raft算法性能優(yōu)化

Raft算法的性能瓶頸主要有兩方面：

1）每次日志寫入后都需要刷盤才能返回成功，而刷盤是一個比較耗時的操作。

2）由于算法限制，所有的請求都由Leader處理，不能做到所有節(jié)點皆可提供服務(wù)。

針對以上兩個問題，我們做了以下優(yōu)化：

Batch Processing：在請求量較大時，并不是每一條日志寫入都刷盤，還是累積一定量的日志后集中刷盤，從而減少刷盤次數(shù)。對應(yīng)的，在同步到Follower時也采用批量同步的方式，F(xiàn)ollower接收后將日志批量寫盤。

Multi-Raft：?進程中同時運行多個raft實例，機器之間組建多raft?組，客戶端請求路由到不同的group上，從而實現(xiàn)多主讀寫，提高并發(fā)性能。通過將leader分布在不同機器上，提高了系統(tǒng)的整體利用率。

Async-rpc：?在日志同步過程中采用同步rpc方式，在一端處理時另一端只能等待，性能較差。我們采用異步的方式使得leader端發(fā)送和Follower端處理并發(fā)進行。發(fā)送過程中l(wèi)eader端維持一個發(fā)送窗口，當(dāng)待確認(rèn)的rpc數(shù)達(dá)到上限停止發(fā)送，窗口值上限：

在與同屬于高可靠(多副本同步刷盤)的Rabbitmq性能對比中，相同壓測場景下CMQ速度可以達(dá)到RabbitMQ的四倍左右。

以下為在E5-2620*2/8G*8/2T*12/SSD-80G*1/10GE*2?配置機型測試1KB消息大小時性能數(shù)據(jù)：

測試中CMQ采用單Raft組方式以保證測試公平性。監(jiān)控顯示CPU、內(nèi)存和網(wǎng)卡均未達(dá)到瓶頸，系統(tǒng)瓶頸在磁盤IO，iostat顯示w_await遠(yuǎn)大于svctm。主要原因在于刷盤耗時，造成寫操作排隊等待。

實際生產(chǎn)環(huán)境CMQ中我們將raft組和磁盤進行綁定，實現(xiàn)raft組之間磁盤的隔離，一方面保證了磁盤的順序讀寫，另一方面充分利用機器的cpu?、內(nèi)存、網(wǎng)卡等資源。

四?總結(jié)

Raft算法具備強一致、高可靠、高可用等優(yōu)點，?消息中間件通常分為高可靠版本和高性能版本兩種。騰訊云CMQ是一款金融級的高可靠分布式消息中間件，通過raft保證了消息的可靠不丟失。同時在性能和可用性方面相比競品都有顯著提高。

songjy