歡迎光臨
每天分享高質量文章

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

已同步到看一看
赞(0)

分享創造快樂