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

SOFAStack （Scalable Open Financial Architecture Stack）是螞蟻金服自主研發的金融級分散式架構，包含了構建金融級雲原生架構所需的各個元件，是在金融場景裡錘煉出來的最佳實踐。

本文為《剖析 | SOFAJRaft 實現原理》第四篇，本篇作者力鯤，來自螞蟻金服《剖析 | SOFAJRaft 實現原理》系列由 SOFA 團隊和原始碼愛好者們出品，專案代號：，目前領取已經完成，感謝大家的參與。

SOFAJRaft 是一個基於 Raft 一致性演演算法的生產級高效能 Java 實現，支援 MULTI-RAFT-GROUP，適用於高負載低延遲的場景。

SOFAJRaft ：

https://github.com/sofastack/sofa-jraft

前言 

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

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

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

 

問題1：選舉要解決什麼 

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

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

圖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 – 一次成功的選舉

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

1.  

   com.alipay.sofa.jraft.core.NodeImpl#preVote //預投票

2. com.alipay.sofa.jraft.core.NodeImpl#electSelf //投票

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

4. 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 處理投票