SOFAJRaft 選舉機制剖析 | SOFAJRaft 實現原理是什么

這篇文章主要講解了“SOFAJRaft 選舉機制剖析 | SOFAJRaft 實現原理是什么”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“SOFAJRaft 選舉機制剖析 | SOFAJRaft 實現原理是什么”吧！

前言

在 Raft 算法中，選舉是很重要的一部分，所謂選舉也就是在多個節點中選出一個 Leader 節點，由他來對外提供寫服務 （以及默認情況下的讀服務）。

在剖析源碼時，對選舉機制的理解經常會遇到兩極分化的情況，對于了解 Raft 算法基本原理的同學，閱讀源碼就是品味實現之巧妙的過程，而對初體驗的同學，卻會陷入丈二和尚的窘境，仿佛墜入云里霧里。

為了提升文章的可讀性，我還是希望花一部分篇幅講清楚選舉機制的基本原理，以便后面集中注意力于代碼實現。下面是一段圖文比喻，幫助理解的同時也讓整篇文章不至于過早陷入細節的討論。

問題1：選舉要解決什么

一個分布式集群可以看成是由多條戰船組成的一支艦隊，各船之間通過旗語來保持信息交流。這樣的一支艦隊中，各船既不會互相完全隔離，但也沒法像陸地上那樣保持非常密切的聯系，天氣、海況、船距、船只戰損情況導致船艦之間的聯系存在但不可靠。

艦隊作為一個統一的作戰集群，需要有統一的共識、步調一致的命令，這些都要依賴于旗艦指揮。各艦船要服從于旗艦發出的指令，當旗艦不能繼續工作后，需要有別的戰艦接替旗艦的角色。

cdn.nlark.com/yuque/0/2019/png/307286/1562208003160-14473ea8-f451-4c07-97f2-d79927b4f6f7.png">

圖1 - 所有船有責任隨時準備接替旗艦

如何在艦隊中，選出一艘得到大家認可的旗艦，這就是 SOFAJRaft 中選舉要解決的問題。

問題2：何時可以發起選舉

何時可以發起選舉？換句話說，觸發選舉的標準是什么？這個標準必須對所有戰艦一致，這樣就能夠在標準得到滿足時，所有艦船公平的參與競選。在 SOFAJRaft 中，觸發標準就是通信超時，當旗艦在規定的一段時間內沒有與 Follower 艦船進行通信時，Follower 就可以認為旗艦已經不能正常擔任旗艦的職責，則 Follower 可以去嘗試接替旗艦的角色。這段通信超時被稱為 Election Timeout （簡稱 ET）， Follower 接替旗艦的嘗試也就是發起選舉請求。

圖2 - ET 觸發其他船競選旗艦

問題3：何時真正發起選舉

在選舉中，只有當艦隊中超過一半的船都同意，發起選舉的船才能夠成為旗艦，否則就只能開始一輪新的選舉。所以如果 Follower 采取盡快發起選舉的策略，試圖盡早為艦隊選出可用的旗艦，就可能引發一個潛在的風險：可能多艘船幾乎同時發起選舉，結果其中任何一支船都沒能獲得超過半數選票，導致這一輪選舉無果，然后失敗的 Follower 們再一次幾乎同時發起選舉，又一次失敗，再選舉 again，再失敗 again ···

圖3 - 同時發起選舉，選票被瓜分

為避免這種情況，我們采用隨機的選舉觸發時間，當 Follower 發現旗艦失聯之后，會選擇等待一段隨機的時間 Random(0, ET) ，如果等待期間沒有選出旗艦，則 Follower 再發起選舉。

圖4 - 隨機等待時間

問題4：哪些候選者值得選票

SOFAJRaft 的選舉中包含了對兩個屬性的判斷：LogIndex 和 Term，這是整個選舉算法的核心部分，也是容易讓人產生困惑的地方，因此我們做一下解釋：

1. Term

我們會對艦隊中旗艦的歷史進行編號，比如艦隊的第1任旗艦、第2任旗艦，這個數字我們就用 Term 來表示。由于艦隊中同時最多只能有一艘艦船擔任旗艦，所以每一個 Term 只歸屬于一艘艦船，顯然 Term 是單調遞增的。

2. LogIndex

每任旗艦在職期間都會發布一些指令（稱其為“旗艦令”，類比“總統令”），這些旗艦令當然也是要編號歸檔的，這個編號我們用 Term 和 LogIndex 兩個維度來標識，表示“第 Term 任旗艦發布的第 LogIndex 號旗艦令”。不同于現實中的總統令，我們的旗艦令中的 LogIndex 是一直遞增的，不會因為旗艦的更迭而從頭開始計算。

圖5 - 總統令 Vs 旗艦令，LogIndex 稍有區別

所有的艦船都盡可能保存了過去從旗艦接收到的旗艦令，所以我們選舉的標準就是哪艘船保存了最完整的旗艦令，那他就最有資格接任旗艦。具體來說，參與投票的船 V 不會對下面兩種候選者 C 投票：一種是 lastTermC < lastTermV；另一種是 (lastTermV == lastTermC) && (lastLogIndexV > lastLogIndexC)。

稍作解釋，第一種情況說明候選者 C 最后一次通信過的旗艦已經不是最新的旗艦了，至少比 V 更滯后，所以它所知道的旗艦令也不可能比 V 更完整。第二種情況說明，雖然 C 和 V 都與同一個旗艦有過通信，但是候選者 C 從旗艦處獲得的旗艦令不如 V 完整 (lastLogIndexV > lastLogIndexC)，所以 V 不會投票給它。

圖6 - Follower 船 b 拒絕了船 c 而投票給船 a，船 a 旗艦令有一個空白框表示“第 Term 任旗艦”沒有發布過任何旗艦令

問題5：如何避免不夠格的候選者“搗亂”

如上一小節所說，SOFAJRaft 將 LogIndex 和 Term 作為選舉的評選標準，所以當一艘船發起選舉之前，會自增 Term 然后填到選舉請求里發給其他船只 （可能是一段很復雜的旗語），表示自己競選“第 Term + 1 任”旗艦。

這里要先說明一個機制，它被用來保證各船只的 Term 同步遞增：當參與投票的 Follower 船收到這個投票請求后，如果發現自己的 Term 比投票請求里的小，就會自覺更新自己的 Term 向候選者看齊，這樣能夠很方便的將 Term 遞增的信息同步到整個艦隊中。

圖7 - Follower 船根據投票請求更新自己的 Term

但是這種機制也帶來一個麻煩，如果一艘船因為自己的原因沒有看到旗艦發出的旗語，他就會自以為是的試圖競選成為新的旗艦，雖然不斷發起選舉且一直未能當選（因為旗艦和其他船都正常通信），但是它卻通過自己的投票請求實際抬升了全局的 Term，這在 SOFAJRaft 算法中會迫使旗艦 stepdown （從旗艦的位置上退下來）。

圖8 - 自以為是的搗亂者，迫使旗艦 stepdown

所以我們需要一種機制阻止這種“搗亂”，這就是預投票 (pre-vote) 環節。候選者在發起投票之前，先發起預投票，如果沒有得到半數以上節點的反饋，則候選者就會識趣的放棄參選，也就不會抬升全局的 Term。

圖9 - Pre-vote 預投票

選舉剖析

在上面的比喻中，我們可以看到整個選舉操作的主線任務就是：

1. Candidate 被 ET 觸發

2. Candidate 開始嘗試發起 pre-vote 預投票

3. Follower 判斷是否認可該 pre-vote request

4. Candidate 根據 pre-vote response 來決定是否發起 RequestVoteRequest

5. Follower 判斷是否認可該 RequestVoteRequest

6. Candidate 根據 response 來判斷自己是否當選

這個過程可用下圖表示：

圖10 - 一次成功的選舉

在代碼層面，主要是由四個方法來處理這個流程：

com.alipay.sofa.jraft.core.NodeImpl#preVote //預投票
com.alipay.sofa.jraft.core.NodeImpl#electSelf //投票
com.alipay.sofa.jraft.core.NodeImpl#handlePreVoteRequest //處理預投票請求
com.alipay.sofa.jraft.core.NodeImpl#handleRequestVoteRequest //處理投票請求

代碼邏輯比較直觀，所以我們用流程圖來簡述各個方法中的處理。

預投票和投票

圖11 - 預投票 Vs 投票

圖中可見，預投票請求 preVote 和投票請求 electSelf 的流程基本類似，只是有幾個細節不太一樣：

1. preVote 是由超時觸發；

2. preVote 在組裝 Request 的時候將 term 賦值為 currTerm + 1，而 electSelf 是先將 term ++；

3. preVote 成功后，進入 electSelf，electSelf 成功后 become Leader。

處理請求

處理預投票和投票請求的邏輯也比較類似，同樣用圖來表示。

圖12 - 處理預投票請求

圖13 - 處理投票請求

圖中可見，處理兩種請求的流程也基本類似，只是處理投票請求的時候，會有 stepdown 機制，強制使 Leader 從其 Leader 的身份退到 Follower。在具體的實現中，Leader 會通過租約的機制來避免一些沒有必要的 stepdown，關于租約機制，可以參見之前的系列文章《SOFAJRaft 線性一致讀實現剖析 | SOFAJRaft 實現原理》。

總結

我們在本文中采用了類比的方式來剖析源碼，主要是為了讓讀者能更容易的理解如何在分布式環境中達成共識，其實這也是整個 SOFAJRaft 要實現的目標。

行文至此，作者感覺已經把選舉說清楚了，如果還有沒提到的地方，或者一些流程中的分支任務，歡迎從源碼中進一步尋找答案。最后貼出上面提到的四個方法的源碼。

圖14 - preVote 預投票

圖15 - electSelf 投票

圖16 - handlePreVoteRequest 處理預投票

圖17 - handleRequestVoteRequest 處理投票

感謝各位的閱讀，以上就是“SOFAJRaft 選舉機制剖析 | SOFAJRaft 實現原理是什么”的內容了，經過本文的學習后，相信大家對SOFAJRaft 選舉機制剖析 | SOFAJRaft 實現原理是什么這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！