1.term 和 logIndex

Raft 算法設(shè)計(jì)了 term 和 logIndex 兩個(gè)屬性，分別用于表示 Leader 節(jié)點(diǎn)的任期，以及集群運(yùn)行期間接收到的指令對(duì)應(yīng)的日志條目的 ID，這兩個(gè)屬性都是單調(diào)遞增的。

Raft 算法要求節(jié)點(diǎn)在給參選節(jié)點(diǎn)投票時(shí)必須保證參選節(jié)點(diǎn)滿足以下兩個(gè)條件之一：

• 參選節(jié)點(diǎn)的 term 值大于投票節(jié)點(diǎn)，否則拒絕為其投票。
• 如果參選節(jié)點(diǎn)與投票節(jié)點(diǎn)的 term 值相同，則需要保證參選節(jié)點(diǎn)的 logIndex 值不小于投票節(jié)點(diǎn)。

這兩個(gè)條件的目的都在于保證當(dāng)前參選節(jié)點(diǎn)本地的日志數(shù)據(jù)不能比投票節(jié)點(diǎn)要陳舊。

2.為什么需要預(yù)選舉步驟？

JRaft 在設(shè)計(jì)層面將選舉的過(guò)程拆分為預(yù)選舉和正式選舉兩個(gè)過(guò)程，之所以這樣設(shè)計(jì)是為了避免無(wú)效的選舉進(jìn)程遞增 term 值，進(jìn)而造成浪費(fèi)，同時(shí)也會(huì)導(dǎo)致正常運(yùn)行的 Leader 節(jié)點(diǎn)執(zhí)行角色降級(jí)。

• 正常情況：Raft 算法要求當(dāng)節(jié)點(diǎn)接收到 term 值更大的請(qǐng)求時(shí)需要遞增本地的 term 值，以此實(shí)現(xiàn)集群中 term 值的同步。對(duì)于 Leader 節(jié)點(diǎn)而言，當(dāng)收到 term 值更大的請(qǐng)求時(shí)，該節(jié)點(diǎn)會(huì)認(rèn)為集群中有新的 Leader 節(jié)點(diǎn)生成，于是需要執(zhí)行角色降級(jí)。這一機(jī)制能夠保證在出現(xiàn)網(wǎng)絡(luò)分區(qū)等問(wèn)題時(shí)，在網(wǎng)絡(luò)恢復(fù)時(shí)能夠促使 term 值較小的 Leader 節(jié)點(diǎn)退位為 Follower 節(jié)點(diǎn)，從而實(shí)現(xiàn)讓集群達(dá)到一個(gè)新的平穩(wěn)狀態(tài)。
• 無(wú)效選舉情況：如果集群中某個(gè) Follower 節(jié)點(diǎn)因?yàn)槟承┰蛭茨芙邮盏?Leader 節(jié)點(diǎn)的主權(quán)宣示指令，就會(huì)一直嘗試發(fā)動(dòng)新一輪的選舉革命，進(jìn)而遞增 term 值，導(dǎo)致 Leader 節(jié)點(diǎn)執(zhí)行角色降級(jí)，最終影響整個(gè)集群的正常運(yùn)行。
• 預(yù)選機(jī)制：當(dāng)一個(gè) Follower 節(jié)點(diǎn)嘗試發(fā)起一輪新的選舉革命時(shí)，該節(jié)點(diǎn)不會(huì)立即遞增 term 值，而是嘗試將 term 值加 1 去試探性的征集選票，只有當(dāng)集群中過(guò)半數(shù)的節(jié)點(diǎn)同意投票的前提下才會(huì)進(jìn)入正式投票的環(huán)節(jié)，這樣對(duì)于無(wú)效選舉而言一般只會(huì)停留在預(yù)選舉階段，不會(huì)對(duì)集群的正常運(yùn)行造成影響。

3.預(yù)選舉

當(dāng)啟動(dòng)一個(gè) JRaft 節(jié)點(diǎn)時(shí)，如果初始化集群節(jié)點(diǎn)配置不為空，則節(jié)點(diǎn)會(huì)調(diào)用 NodeImpl#stepDown 方法執(zhí)行角色降級(jí)操作。所謂角色降級(jí)實(shí)際上是一個(gè)寬泛的說(shuō)法，因?yàn)?NodeImpl#stepDown 方法會(huì)在多種場(chǎng)景下被調(diào)用。而這里調(diào)用該方法的背景是一個(gè) FOLLOWER 節(jié)點(diǎn)剛剛啟動(dòng)的時(shí)候，所以除了初始化一些本地狀態(tài)之外，整個(gè)角色降級(jí)過(guò)程重點(diǎn)做的一件事就是啟動(dòng)預(yù)選舉計(jì)時(shí)器 electionTimer。

NodeImpl#init
-> NodeImpl#stepDown
-> this.electionTimer.restart()
-> RepeatedTimer#restart
-> RepeatedTimer#schedule
-> RepeatedTimer#run
-> 回調(diào) onTrigger()

在NodeImpl#init中看electionTimer的onTrigger()實(shí)現(xiàn)：

        this.electionTimer = new RepeatedTimer(name, this.options.getElectionTimeoutMs(),
            TIMER_FACTORY.getElectionTimer(this.options.isSharedElectionTimer(), name)) {

            @Override
            protected void onTrigger() {
                handleElectionTimeout();
            }

            @Override
            protected int adjustTimeout(final int timeoutMs) {
                return randomTimeout(timeoutMs);
            }
        };

核心是NodeImpl#handleElectionTimeout，默認(rèn)隨機(jī)區(qū)間為 1~2s。

NodeImpl#handleElectionTimeout

• 1）如果當(dāng)前節(jié)點(diǎn)不是 FOLLOWER 角色，則放棄預(yù)選舉；
• 2）否則，如果當(dāng)前節(jié)點(diǎn)與 Leader 節(jié)點(diǎn)之間的租約仍然有效，則放棄預(yù)選舉；（Follower 節(jié)點(diǎn)會(huì)在本地記錄最近一次收到來(lái)自 Leader 節(jié)點(diǎn)的 RPC 請(qǐng)求時(shí)間戳，如果該時(shí)間戳距離當(dāng)前時(shí)間小于選舉超時(shí)時(shí)間，則說(shuō)明當(dāng)前節(jié)點(diǎn)與 Leader 節(jié)點(diǎn)之間的租約仍然有效，無(wú)需繼續(xù)發(fā)起預(yù)選舉。）
• 3）否則，清空本地記錄的 Leader 節(jié)點(diǎn) ID，回調(diào) FSMCaller#onStopFollowing 方法；（方法 NodeImpl#resetLeaderId 會(huì)清空本地記錄的 Leader 節(jié)點(diǎn) ID，如果當(dāng)前節(jié)點(diǎn)不是 Leader 角色，并且正在追隨某個(gè) Leader 節(jié)點(diǎn)，則該方法會(huì)回調(diào) FSMCaller#onStopFollowing 方法將停止追隨的事件透?jìng)鹘o狀態(tài)機(jī)。業(yè)務(wù)可以通過(guò)覆蓋實(shí)現(xiàn) StateMachine#onStopFollowing 方法捕獲這一事件。）
• 4）基于節(jié)點(diǎn)優(yōu)先級(jí)判斷是否允許發(fā)起預(yù)選舉，如果允許則發(fā)起預(yù)選舉進(jìn)程。
  ?4-1）校驗(yàn)當(dāng)前節(jié)點(diǎn)是否正在安裝快照，如果是則放棄預(yù)選舉；
  ?4-2）校驗(yàn)當(dāng)前節(jié)點(diǎn)是否位于節(jié)點(diǎn)配置列表中，如果不是則說(shuō)明當(dāng)前節(jié)點(diǎn)不是一個(gè)有效節(jié)點(diǎn)，放棄預(yù)選舉；
  ?4-3）從本地磁盤獲取最新的 LogId，包含 logIndex 和 term 值；LogManagerImpl#getLastLogId。
  ??如果設(shè)置 isFlush = true 則會(huì)往該隊(duì)列提交一個(gè) LAST_LOG_ID 類型事件，并阻塞等待該事件處理完成。方法 StableClosureEventHandler#onEvent 中實(shí)現(xiàn)了對(duì) Disruptor 中消息的處理邏輯，并定義了一個(gè) AppendBatcher 類型的屬性用于緩存收集到的 LogEntry 數(shù)據(jù)。在響應(yīng) LAST_LOG_ID 事件之前，StableClosureEventHandler 會(huì)調(diào)用 AppendBatcher#flush 方法將收集到的 LogEntry 數(shù)據(jù)刷盤。
  ??RocksDBLogStorage 設(shè)置了兩個(gè) column family，即 conf family 和 data family，其中后者復(fù)用了 RocksDB 提供的默認(rèn) column family。由上述實(shí)現(xiàn)可以看到，JRaft 針對(duì)配置類型的 LogEntry 會(huì)同時(shí)寫入這兩個(gè) family 中，而其它類型的 LogEntry 僅會(huì)寫入到 data family 中。
  ?4-4）初始化預(yù)選舉選票 Ballot 實(shí)例；
  ?4-5）遍歷向除自己以外的所有連通節(jié)點(diǎn)發(fā)送 RequestVote RPC 請(qǐng)求，以征集選票，同時(shí)給自己投上一票；RaftServerService#handlePreVoteRequest：
  ??A）如果當(dāng)前節(jié)點(diǎn)處于非活躍狀態(tài)，則響應(yīng)錯(cuò)誤；
  ??B）否則，解析候選節(jié)點(diǎn)的節(jié)點(diǎn) ID，如果解析出錯(cuò)，則響應(yīng)錯(cuò)誤；
  ??C）否則，如果當(dāng)前節(jié)點(diǎn)與對(duì)應(yīng) Leader 節(jié)點(diǎn)之間的租約仍然有效，則拒絕投票；
  ??D）否則，如果候選節(jié)點(diǎn)的 term 值相較于當(dāng)前節(jié)點(diǎn)小，則拒絕投票；如果當(dāng)前節(jié)點(diǎn)正好是 Leader 節(jié)點(diǎn)，還需要檢查候選節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)之間的復(fù)制關(guān)系（如果當(dāng)前節(jié)點(diǎn)是 Leader 節(jié)點(diǎn)，但是仍然有節(jié)點(diǎn)發(fā)起預(yù)選舉進(jìn)程，則說(shuō)明當(dāng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間的復(fù)制關(guān)系存在問(wèn)題，需要重新建立復(fù)制關(guān)系，并啟動(dòng)對(duì)應(yīng)的復(fù)制器 Replicator。）；
  ??E）否則，獲取本地最新的 logIndex 和對(duì)應(yīng)的 term 值，如果候選節(jié)點(diǎn)的 term 和 logIndex 值更新，則同意投票，否則拒絕投票。
  DefaultRaftClientService#preVote：
  ??A）AbstractClientService#invokeWithDone
  ??B）NodeImpl.OnPreVoteRpcDone#run
  ??C）NodeImpl#handlePreVoteResponse
  ???C-1）校驗(yàn)當(dāng)前節(jié)點(diǎn)是否仍然是 FOLLOWER 角色，如果不是則忽略響應(yīng)，可能已經(jīng)預(yù)選舉成功了；
  ???C-2）否則，校驗(yàn)當(dāng)前節(jié)點(diǎn)的 term 值是否發(fā)生變化，如果是則忽略響應(yīng)；
  ???C-3）否則，如果目標(biāo)節(jié)點(diǎn)的 term 值較當(dāng)前節(jié)點(diǎn)更大，則忽略響應(yīng)，并執(zhí)行 stepdown；
  ???C-4）否則，如果目標(biāo)節(jié)點(diǎn)拒絕投票，則忽略響應(yīng)；
  ???C-5）否則，如果目標(biāo)節(jié)點(diǎn)同意投票，則更新得票數(shù)，并檢查是否預(yù)選舉成功，如果是則進(jìn)入正式投票環(huán)節(jié)。（在處理預(yù)選舉響應(yīng)時(shí)會(huì)讓每個(gè)目標(biāo)節(jié)點(diǎn)的響應(yīng)在同意投票的前提下都會(huì)回調(diào)觸發(fā)一次 Ballot#grant 操作以更新得票數(shù)，并調(diào)用 Ballot#isGranted 方法檢查得票數(shù)是否過(guò)半，如果是則進(jìn)入正式投票的環(huán)節(jié)。）
  ?4-6）如果票數(shù)過(guò)半，則執(zhí)行 NodeImpl#electSelf 操作進(jìn)入正式投票環(huán)節(jié)。

預(yù)選舉的特點(diǎn)：

• 預(yù)選舉階段的 RequestVote 請(qǐng)求會(huì)設(shè)置 preVote = true，以標(biāo)識(shí)自己是一個(gè)預(yù)選舉請(qǐng)求，用來(lái)與正式投票階段的 RequestVote 請(qǐng)求請(qǐng)求相區(qū)別。
• 為了避免 term 值無(wú)謂的遞增，預(yù)選舉階段不會(huì)真正遞增 term 值，而只是將 term 加 1 進(jìn)行試探性的發(fā)起投票。

4.正式選舉

觸發(fā)正式選舉進(jìn)程，除了發(fā)生在預(yù)選舉成功之后之外，主要還包括另外兩個(gè)場(chǎng)景：

• 在只有一個(gè)節(jié)點(diǎn)的情況下，此時(shí)該節(jié)點(diǎn)一定能夠競(jìng)選成功，所以沒有進(jìn)行預(yù)選舉的必要。
• 正式選舉階段超時(shí)，此時(shí)需要再次發(fā)起一輪新的正式選舉進(jìn)程，這也是正式選舉計(jì)時(shí)器 voteTimer 的職責(zé)。

NodeImpl#electSelf

• 1）校驗(yàn)當(dāng)前節(jié)點(diǎn)是否是合法節(jié)點(diǎn)，即屬于集群節(jié)點(diǎn)配置集合中的一員，如果不是則放棄參選；
• 2）如果當(dāng)前節(jié)點(diǎn)是 FOLLOWER 角色，說(shuō)明是剛剛從預(yù)選舉階段過(guò)渡而來(lái)，需要停止預(yù)選舉計(jì)時(shí)器 electionTimer，避免期間再次發(fā)起新的預(yù)選舉進(jìn)程；
• 3）重置本地記錄的 leader 節(jié)點(diǎn)的 ID；
• 4）切換節(jié)點(diǎn)為 CANDIDATE 角色、遞增 term 值，以及更新 votedId 為當(dāng)前節(jié)點(diǎn) ID；
• 5）啟動(dòng)正式選舉計(jì)時(shí)器 voteTimer，用于當(dāng)正式選舉超時(shí)時(shí)，再次發(fā)起一輪新的正式選舉進(jìn)程；
• 6）初始化正式選票 Ballot 實(shí)例；
• 7）獲取本地最新的 logIndex 和對(duì)應(yīng)的 term 值；
• 8）遍歷向除自己以外的所有連通節(jié)點(diǎn)發(fā)送 RequestVote RPC 請(qǐng)求，以征集選票，同時(shí)給自己投上一票；
  NodeImpl#handleRequestVoteRequest（各節(jié)點(diǎn)處理）
  ?A）如果當(dāng)前節(jié)點(diǎn)處于非活躍狀態(tài)，則響應(yīng)錯(cuò)誤；
  ?B）否則，解析候選節(jié)點(diǎn)的節(jié)點(diǎn) ID，如果解析出錯(cuò)則響應(yīng)錯(cuò)誤；
  ?C）否則，如果候選節(jié)點(diǎn)的 term 值小于當(dāng)前節(jié)點(diǎn)，則拒絕投票；
  ?D）否則，如果候選節(jié)點(diǎn)的 term 值大于當(dāng)前節(jié)點(diǎn)，則需要執(zhí)行 stepdown（此時(shí)處理 RequestVote RPC 請(qǐng)求的節(jié)點(diǎn)角色仍然是 FOLLOWER，所以除了重置本地狀態(tài)和再次啟動(dòng)預(yù)選舉計(jì)時(shí)器之外，一個(gè)重要的工作就是更新當(dāng)前節(jié)點(diǎn)的 term 值，以保證與當(dāng)前集群已知的最大 term 值看齊）；
  ?E）如果候選節(jié)點(diǎn)的 term 值更新，或者 term 值相同但是對(duì)應(yīng)的 logIndex 不小于當(dāng)前節(jié)點(diǎn)，且當(dāng)前節(jié)點(diǎn)未投票給其它節(jié)點(diǎn)，則同意投票，同時(shí)更新本地元數(shù)據(jù)信息；
  ?F）否則，拒絕投票。
  DefaultRaftClientService#requestVote
  ?A）AbstractClientService#invokeWithDone
  ?B）OnRequestVoteRpcDone#run
  ?C）NodeImpl#handleRequestVoteResponse
  ???C-1）校驗(yàn)當(dāng)前節(jié)點(diǎn)是不是 CANDIDATE 角色，如果不是則可能已經(jīng)競(jìng)選成功，或者被打回成了 FOLLOWER 角色，忽略響應(yīng)；
  ???C-2）否則，校驗(yàn)等待響應(yīng)期間節(jié)點(diǎn)的 term 值是否發(fā)生變化，如果是則忽略響應(yīng)；
  ???C-3）否則，如果目標(biāo)節(jié)點(diǎn)的 term 值相較于當(dāng)前節(jié)點(diǎn)更大，則需要忽略響應(yīng)，并執(zhí)行 stepdown（當(dāng)前節(jié)點(diǎn)角色為 CANDIDATE，所以執(zhí)行 stepdown 會(huì)讓當(dāng)前節(jié)點(diǎn)停止正式選舉計(jì)時(shí)器，并切換角色為 FOLLOWER，并再次啟動(dòng)預(yù)選舉計(jì)時(shí)器。此外，還會(huì)更新當(dāng)前節(jié)點(diǎn)的 term 值，以保證與當(dāng)前集群已知的最大 term 值看齊）；
  ???C-4）否則，如果目標(biāo)節(jié)點(diǎn)同意投票，則更新選票計(jì)數(shù)，否則忽略響應(yīng)；
  ???C-5）如果票數(shù)過(guò)半，則執(zhí)行 NodeImpl#becomeLeader 方法成為 LEADER 角色。
• 9）更新本地元數(shù)據(jù)信息，即 term 值和 votedId 值；
• 10）如果票數(shù)過(guò)半，則執(zhí)行 NodeImpl#becomeLeader 操作以切換角色為 LEADER，即競(jìng)選成功。
  NodeImpl#becomeLeader
  ?A）校驗(yàn)當(dāng)前節(jié)點(diǎn)角色是否為 CANDIDATE，LEADER 角色的前置角色必須是 CANDIDATE；
  ?B）停止正式選舉計(jì)時(shí)器 voteTimer；
  ?C）切換節(jié)點(diǎn)角色為 LEADER；
  ?D）建立到除自己以外的所有節(jié)點(diǎn)之間的復(fù)制關(guān)系，包括 Follower 和 Learner；
  ?E）重置選票箱 BallotBox；
  ?F）將當(dāng)前集群的節(jié)點(diǎn)配置信息記錄到日志中（方法 ConfigurationCtx#flush 會(huì)將當(dāng)前集群的節(jié)點(diǎn)配置信息作為當(dāng)前節(jié)點(diǎn)成為 LEADER 角色之后的第一條日志同步給集群中的 Follower 節(jié)點(diǎn)。Leader 節(jié)點(diǎn)在將日志數(shù)據(jù)同步出去之前會(huì)設(shè)置一個(gè) ConfigurationChangeDone 回調(diào)，并在日志數(shù)據(jù)被 committed 之后觸發(fā)執(zhí)行 ConfigurationChangeDone#run 方法。）；
  ConfigurationChangeDone#run
  -> 嘗試讓集群節(jié)點(diǎn)配置趨于穩(wěn)定。在 Leader 選舉場(chǎng)景下，集群節(jié)點(diǎn)配置上下文 ConfigurationCtx 的 stage 分為 STAGE_STABLE 和 STAGE_JOINT 兩類，前者表示集群配置已經(jīng)趨于穩(wěn)定，而后者則表示集群目前存在新老配置過(guò)渡的情況。
  -> 回調(diào)StateMachine#onLeaderStart
  ?G）啟動(dòng) stepdown 計(jì)時(shí)器 stepDownTimer。

在節(jié)點(diǎn)成為 LEADER 角色之后會(huì)將集群配置信息作為第一條日志進(jìn)行提交，還有另外一個(gè)考慮。當(dāng)一個(gè)節(jié)點(diǎn)剛剛競(jìng)選成為 LEADER 角色時(shí)，此時(shí)該節(jié)點(diǎn)本地的 committedIndex 值并不一定是當(dāng)前整個(gè)系統(tǒng)范圍內(nèi)最新的 committedIndex 值，這會(huì)影響線性一致性讀結(jié)果的準(zhǔn)確性，而通過(guò)提交日志操作則能夠保證新的 Leader 節(jié)點(diǎn)的 committedIndex 被更新為集群范圍內(nèi)的最新值。

5.Leader 讓權(quán)

Leader 節(jié)點(diǎn)需要定期檢查自己的權(quán)威是否持續(xù)有效，即集群中過(guò)半數(shù)的 Follower 節(jié)點(diǎn)都能響應(yīng)自己的心跳請(qǐng)求，如果不是則需要讓權(quán)。這一過(guò)程由 stepdown 計(jì)時(shí)器 stepDownTimer 負(fù)責(zé)，由前面 NodeImpl#becomeLeader 方法的實(shí)現(xiàn)也可以看到在節(jié)點(diǎn)成為 LEADER 角色之后會(huì)啟動(dòng) stepdown 計(jì)時(shí)器。

NodeImpl#handleStepDownTimeout
-> NodeImpl#checkDeadNodes如果集群中認(rèn)同當(dāng)前 Leader 節(jié)點(diǎn)的 Follower 節(jié)點(diǎn)數(shù)過(guò)半，則無(wú)需讓權(quán)；集群中認(rèn)同當(dāng)前 Leader 節(jié)點(diǎn)的 Follower 節(jié)點(diǎn)數(shù)小于一半，執(zhí)行讓權(quán)操作
-> NodeImpl#checkDeadNodes0 會(huì)檢查目標(biāo) Follower 節(jié)點(diǎn)與當(dāng)前 Leader 節(jié)點(diǎn)最近一次的 RPC 請(qǐng)求時(shí)間戳，以此決定對(duì)應(yīng)的租約是否仍然有效
-> NodeImpl#stepDown 節(jié)點(diǎn)以 LEADER 角色調(diào)用該方法，除了將角色切換成 FOLLOWER、初始化本地狀態(tài)，以及啟動(dòng)預(yù)選舉計(jì)時(shí)器 electionTimer 之外，在此之前還會(huì)執(zhí)行如下一段邏輯：停止 stepdown 計(jì)時(shí)器、清空選票箱、向狀態(tài)機(jī)調(diào)度器發(fā)布 LEADER_STOP 事件。LEADER_STOP 狀態(tài)機(jī)事件會(huì)觸發(fā) FSMCaller 回調(diào)應(yīng)用程序?qū)崿F(xiàn)的 StateMachine#onLeaderStop 方法。

參考

• SOFA-JRaft 源碼解析：主節(jié)點(diǎn)選舉機(jī)制