說明：本文節(jié)選自清華大學(xué)出版社出版的《深入理解分布式共識算法》，略有修改。

粉絲福利，京東5折購買鏈接：https://item.jd.com/13677957.html，2023年4月5日前有效。點擊原文立即參與

全文導(dǎo)讀

Raft是一個強Leader的算法，我們可以根據(jù)Leader的狀態(tài)來劃分Raft的執(zhí)行階段。本文從以下三個方面行文。

• Leader選舉，集群中沒有Leader，該階段將選舉出日志最完整的成員晉升為Leader

• 日志復(fù)制，集群正常運行，在該階段處理事務(wù)請求

• 日志對齊，使得集群中所有成員的數(shù)據(jù)保持一致

存在A、B、C三個成員組成的Raft集群，剛啟動時，每個成員都處于Follower狀態(tài)，其中，成員A心跳超時為110ms，成員B心跳超時為150ms，成員C心跳超時為130ms，其他相關(guān)信息如圖1所示。

圖1 Raft模擬初始狀態(tài)

由于集群中不存在Leader，A、B、C三個成員都不會收到來自Leader的心跳信息。其中，成員A的超時最短，最先進入選舉狀態(tài)，修改自己的狀態(tài)為Candidate，并增加自己的任期編號為1，發(fā)起請求投票消息，如圖2所示。

圖2 請求投票

成員A通過RequestVote廣播自己的選票給成員B、C，選票描述了成員A所擁有的數(shù)據(jù)，其包含成員A所處的term及最新的日志索引。成員B、C根據(jù)投票規(guī)則處理RequestVote消息。

• term大的成員拒絕投票給term小的成員。

• 日志索引大的成員拒絕投票給日志索引小的成員。

• 一個term內(nèi)只投出一張選票，采用先來先獲得投票的原則。

很明顯，成員B、C的term小于成員A的term，也不存在比成員A日志索引更大的日志索引，并且term為1的選票還沒有投給其他成員，因此成員B、C將term為1的選票投給成員A并更新自己的term為1。

成員A獲得包括自己在內(nèi)的3張選票，贏得大多數(shù)選票，成員A晉升為Leader，并向其他成員發(fā)送心跳信息，維護自己的領(lǐng)導(dǎo)地位，如圖3所示。

圖3 Leader晉升示意

如果成員A在等待投票超過約定的時間內(nèi)沒有收到多數(shù)派的選票，則會重置自己的超時，并結(jié)束本次選舉進程。接著會有其他成員在等待心跳超時后發(fā)起Leader選舉，在當前案例中，發(fā)起Leader選舉的順序為A→C→B。

可能因為網(wǎng)絡(luò)問題，使集群中的所有成員又發(fā)起了一輪選舉，但是都沒有獲得多數(shù)派的選票，因此會隨機產(chǎn)生新的超時，開始下一個循環(huán)的選舉。

日志復(fù)制

在之前的文章中提過，日志復(fù)制是一個一階段協(xié)商的過程，其中，日志項的提交操作由下一輪協(xié)商或者心跳消息來代替完成。因此處理事務(wù)請求，Raft只需要發(fā)送一輪AppendEntries消息即可。

AppendEntries消息除了會包含需要復(fù)制日志項的相關(guān)信息外，通常會攜帶Leader的committedIndex參數(shù)，標示著最后一個已提交的日志索引。每個Follower的本地都維護了committedIndex，F(xiàn)ollower可以對比Leader的committedIndex來推進自己的提交操作。

接著如圖3所示的示例，一個三個成員組成的集群，成員A為Leader，成員B和C為Follower，并且在集群中未提交任何日志項。Leader收到客戶端發(fā)送的Add請求后，Leader和Follower依次執(zhí)行以下步驟，如圖4所示。

圖4 日志復(fù)制-復(fù)制

（1）Leader將其封裝成日志項追加到本地的日志中，日志索引為1。

（2）Leader通過AppendEntries(0, <1, Add>)消息時將日志項廣播給所有的Follower。其中：

• 第一個參數(shù)為committedIndex，即Leader最后提交的日志索引。

• 第二個參數(shù)為Leader所處的日志索引，即Add日志項的索引。

• 第三個參數(shù)為事務(wù)操作指令，即客戶端的指令。

（3）Follower收到消息，將日志項追加到本地的日志中。

此時，成員A、B、C都擁有日志項Add且都已在索引為1上完成了持久化。Follower在處理完AppendEntries消息后需要回復(fù)ACK消息給Leader，代表接受該日志項。Leader收到多數(shù)派的ACK消息后，可以在本地提交該日志項并執(zhí)行狀態(tài)轉(zhuǎn)移，之后將執(zhí)行結(jié)果返回給客戶端，如圖5所示。

圖5 日志復(fù)制-回復(fù)

在當前場景中，成員A提交了索引為1的日志項，成員B、C僅僅擁有索引為1的日志項的所有信息但并未提交。成員B、C需要等待下一次AppendEntries消息，根據(jù)其committedIndex推進索引為1的日志項的提交操作。以心跳的AppendEntries消息為例，該AppendEntries消息僅攜帶了committedIndex，此時Leader已經(jīng)提交了索引為1的日志項，因此committedIndex為1。Follower則可以提交索引為1及其之前的所有日志項，如圖6所示。

圖6 日志復(fù)制-心跳

日志對齊

我們使用> 表示一個日志項，如表1所示為Follower E的日志索引3和Follower D的日志索引4，與當前Leader處理不一致的情況。出現(xiàn)這種情況可能是Follower E和Follower D曾經(jīng)當選過Leader，并且在自己的term上提出了日志索引為3和4的日志項后立即宕機造成的。

表1 日志對齊

Log Index

1

2

3

4

5

6

Leader A

<1, 1>

<1, 2>

<2, 3>

<3, 4>

<3, 5>

<3, 6>

Follower B

<1, 1>

<1, 2>

<2, 3>

<3, 4>

<3, 5>

Follower C

<1, 1>

<1, 2>

<2, 3>

<3, 4>

<3, 5>

Follower D

<1, 1>

<1, 2>

<2, 3>

<2, 4>

Follower E

<1, 1>

<1, 2>

<1, 3>

要使Follower E和Follower D與Leader數(shù)據(jù)保持一致，大致步驟分為兩步：尋找nextIndex，復(fù)制nextIndex及其之后的日志項。在Raft中，這個步驟均可由AppendEntries消息來完成。這里以Follower E成員為例，交互細節(jié)如下：

（1）Leader為Follower E初始化nextIndex，nextIndex=lastLogIndex+1，即nextIndex=6+1=7。

（2）Leader通過AppendEntries發(fā)送探測消息，攜帶preLogIndex（nextIndex-1）及preLogTerm，其中，preLogIndex=6，preLogTerm=3。

（3）Follower收到探測消息，對比索引為6的日志項，返回失敗的響應(yīng)給Leader并攜帶lastLogIndex=3。

（4）Leader收到失敗的響應(yīng)，更新nextIndex=lastLogIndexmsg+1，即nextIndex=4。

（5）Leader發(fā)送下一輪的探測消息，其中，preLogIndex=3，preLogTerm=2。

（6）Follower收到探測消息，對比索引為3的日志項，返回失敗的響應(yīng)給Leader并攜帶lastLogIndex=3。

（7）Leader收到失敗的響應(yīng)，此時lastLogIndexmsg+1 ≤ nextIndex，則nextIndex單調(diào)遞減為3。

（8）Leader發(fā)送下一輪的探測消息，其中，preLogIndex=2，preLogTerm=1。

（9）Follower收到探測消息，對比索引為2的日志項，返回探測成功的響應(yīng)給Leader。

（10）Leader在成功探測到nextIndex之后，通過AppendEntries消息從nextIndex開始發(fā)送索引為3的日志項給Follower。

（11）Follower將以Leader的數(shù)據(jù)為準，覆蓋本地的日志項并返回處理成功的響應(yīng)給Leader。

（12）Leader收到成功響應(yīng)后，單調(diào)遞增nextIndex，繼續(xù)發(fā)送下一個日志項。直到nextIndex等于Leader的lastLogIndex，意味著該Follower擁有Leader所有的數(shù)據(jù)，本次日志對齊即完成。