摘要：Raft算法是一種分布式共識(shí)算法，用于解決分布式系統(tǒng)中的一致性問題。

本文分享自華為云社區(qū)《共識(shí)算法之Raft算法模擬數(shù)》，作者： TiAmoZhang 。

01、Leader選舉

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

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

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

■ 圖2 請(qǐng)求投票

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

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

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

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

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

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

■ 圖3 Leader晉升示意

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

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

02、日志復(fù)制

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

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

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

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

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

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

• 第一個(gè)參數(shù)為committedIndex，即Leader最后提交的日志索引。
• 第二個(gè)參數(shù)為L(zhǎng)eader所處的日志索引，即Add日志項(xiàng)的索引。
• 第三個(gè)參數(shù)為事務(wù)操作指令，即客戶端的指令。

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

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

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

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

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

03、日志對(duì)齊

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

■ 表1 日志對(duì)齊

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

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

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

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

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

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

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

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

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

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

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

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

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

?

點(diǎn)擊關(guān)注，第一時(shí)間了解華為云新鮮技術(shù)~文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-517952.html

到了這里，關(guān)于詳解共識(shí)算法的Raft算法模擬數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！