SOFAJRaft 優先級選舉剖析 | SOFAJRaft 特性解析

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

默認文件1588729141756.png

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

本文作者胡宗棠，SOFAJRaft Committer，來自中國移動。本文主要介紹 SOFAJRaft 在 Leader 選舉過程中的重要優化方案—一種半確定性的優先級選舉機制，將會先簡單地介紹下原 Raft 算法中隨機超時選舉機制的大致內容，如果讀者對這塊內容理解得不夠深入，建議可以先閱讀下《SOFAJRaft 選舉機制剖析 | SOFAJRaft 實現原理》。閱讀完這篇文章後，再來看本篇的內容會對半確定性的優先級選舉機制有更為深刻的理解。

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

一、Raft 算法中選舉機制的概念與特點

Raft 算法是一種“共識性”算法，這裡所謂的“共識性”主要體現在讓多個參與者針對某一件事達成完全一致：一件事一個結論，同時對已達成一致的結論，是不可推翻的。基於這個根本特徵，就決定了 Raft 算法具有以下幾個主要特點：

Strong leader：Raft 集群中最多只能有一個 Leader，日誌只能從 Leader 複製到 Follower 上；
Leader election：Raft 算法採用隨機超時時間觸發選舉來避免選票被瓜分的情況，保證選舉的順利完成。這是主要為了保證在任何的時間段內，Raft 集群最多隻能存在一個 Leader 角色的節點；
Membership changes：通過兩階段的方式應對集群內成員的加入或者退出情況，在此期間並不影響集群對外的服務；

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

這裡先介紹一個任期的概念—Term，其用來將一個連續的時間軸在邏輯上切割成一個個區間，它的含義類似於“美國第 26 屆總統”這個表述中的“26”。同時，該 Term ID 的值是按照時間軸單調遞增的，它構成了 Raft Leader 選舉的必要屬性。

每一個 Term 期間集群要做的第一件事情就是選舉 Leader。起初所有的 Server 都是 Follower 角色，如果 Follower 經過一段時間( election timeout )的等待卻依然沒有收到其他 Server 發來的消息時，Follower 就可以認為集群中沒有可用的 Leader，遂開始準備發起選舉。為了讓 Raft 集群中的所有節點儘可能的客觀公平公正，採用了隨機超時時間觸發選舉，來避免若干個節點在同一時刻嘗試選舉而導致選票被瓜分的情況，保證選舉的順利完成。SOFAJRaft 的做法是，在 Node 觸發選舉的定時任務— electionTimer 中的設置每次定時執行的時間點：時間區間 [electionTimeoutMs，electionTimeoutMs + maxElectionDelayMs) 中的任何時間點。

在發起選舉的時候 Server 會從 Follower 角色轉變成 Candidate，然後開始嘗試競選 Term + 1 屆的 Leader，此時他會向其他的 Server 發送投票請求，當收到集群內多數機器同意其當選的應答之後，Candidate 成功當選 Leader。但是如下兩種情況會讓 Candidate 退回 (step down) 到 Follower，放棄競選本屆 Leader：

如果在 Candidate 等待 Servers 的投票結果期間收到了其他擁有更高 Term 的 Server 發來的投票請求；
如果在 Candidate 等待 Servers 的投票結果期間收到了其他擁有更高 Term 的 Server 發來的心跳；

同時，當一個 Leader 發現有 Term 更高的 Leader 時也會退回到 Follower 狀態。當選舉 Leader 選舉成功後，整個 Raft 集群就可以正常地向外提供讀寫服務了，如上圖所示，集群由一個 Leader 和兩個 Follower 組成，Leader 負責處理 Client 發起的讀寫請求，同時還要跟 Follower 保持心跳和將日誌 Log 複製給 Follower。

01 Raft_Random_TimeOut_Election_Launch.png

但 Raft 算法的“隨機超時時間選舉機制”存在如下問題和限制：

下一個任期 Term，Raft 集群中誰會成為 Leader 角色是不確定的，集群中的其他節點成為 Leader 角色的隨機性較強，無法預估。試想這樣的一個場景：假設部署 Raft 集群的服務器採用不同性能規格，業務用戶總是期望 Leader 角色節點總是在性能最強的服務器上，這樣能夠為客戶端提供較好的讀寫能力，而上面這種“隨機超時時間選舉機制”將不能滿足需求；
如上圖所示，由於會存在選票被瓜分的場景，集群中的各個 Candidate 角色節點將在下一個週期內重新發起選舉。而在這個極短的時間內，由於集群中不存在 Leader 角色所以是無法正常向客戶端提供讀寫能力，因此業務用戶需要通過其他方式來避免短時間的不可用造成的影響；

二、SOFAJRaft 基於優先級的半確定性選舉機制

2.1 SOFAJRaft 基於優先級選舉機制的原理

為了解決原本 Raft 算法“隨機超時時間選舉機制”帶來的問題，增加選舉的確定性，作者貢獻了一種“基於優先級的半確定性選舉機制”。主要的算法思想是：通過配置參數的方式預先定義 Raft 集群中各個節點的 priority 選舉優先級的值，每個 Raft 節點進程在啟動運行後是能夠知道集群中所有節點的 priority 的值（包括它自身的、本地會維護 priority 變量）。

對每個 Raft 節點的配置如下（下面以其中一個節點的配置舉例），其中 PeerId 的字符串值的具體形式為：{ip}:{port}:{index}:{priority}；

sofajraft_config

在 Raft 節點進程初始化階段，通過對所有節點 priority 值求最大值來設置至節點自身維護的 targetPriority 本地全局變量裡。在上面這個例子中，節點的 targetPriority 本地全局變量值就被設置為 160，而自身的 priority 值為 100。

02 Raft_Semi_Priority_Leader_Election_Phase1

在每個 Raft 節點通過隨機超時機制觸發 PreVote 預選舉階段之前，會通過先比較自身的 priority 值和 targetPriority 值來決定是否參加本輪的 Leader 選舉投票。所以，一組 Raft 節點組成的集群在剛啟動運行的階段，priority 值最大的節點（上面例子中 160 的那個節點）必然會優先被選擇成為這個集群中 Leader 角色的節點向外提供讀和寫的服務。

2.2 SOFAJRaft 優先級選舉在故障情況下的重選舉機制

在大部分正常的業務場景中，Raft 集群中的 Leader 角色節點是可以通過上面 2.1 節中介紹的方法來預先確定的。但在實際的生產環境中，一切未知情況都有可能發生，如果 Raft 集群中的 Leader 節點發生故障宕機，那麼基於上述內容的優先選舉是否就會出現問題了？

可以想到，priority 值最大的節點宕機後，如果其他各個節點維護的本地全局變量 targetPriority 值如果不發生改變，因為節點自身的 priority 值是小於前者的，那其他 Raft 節點不就永遠都無法來參與競選 Leader 角色，沒有 Leader 節點整個 Raft 集群也就無法向外提供讀寫服務了，這將是設計中的重大缺陷問題！！！

為了解決上述 Raft 集群在發生故障轉移時，其他節點無法參與競選新 Leader 角色的問題。作者在設計時，引入了 “decayTargetPriority()” 目標優先級衰減降級函數，如果在上一輪由隨機超時時間觸發的選舉週期內沒有投票選出 Leader 角色，那麼 Raft 集群中其他各個節點會對本地全局變量 targetPriority 的值按照每次減少 20% 進行衰減，直至衰減值優先級的最小值“1”。目標優先級衰減降級函數的源碼如下：

decayTargetPriority

當其他節點在對自身維護的本地全局變量 targetPriority 進行衰減後，如果節點自身的 priority 值大於等於 targetPriority 值，則該節點能夠參與到由隨機超時時間觸發的下一輪 Leader 選舉流程中。在一般的情況下，次優先級值的節點能夠搶佔到下一輪 Leader 選舉的機會。

03 SOFAJRaft_decayTargetPriority_when_brokedown_3

如上面時序圖所示，當 Raft 集群出現 Leader 角色的 Node1 節點宕機異常情況時，由於 Node2 和 Node3 無法與之同步心跳信息，這兩個節點會通過隨機超時時間觸發新 Leader 的選舉流程。

在假設在 t2（>t1）時刻，Node3 搶先觸發了 Leader 選舉流程，因為其自身的 priority 值（40）小於本地全局 targetPriority 變量值（100），所以無法發起向 Raft 集群中其他存活的節點發起 PreVote 預投票請求。

同理，在 t3（>t2）時刻，Node2 也同 Node3 一樣無法發起 PreVote 預投票請求。但當到了 t4（>t3）時刻，由於在上一個選舉週期內 Raft 集群中沒有產生 Leader 角色節點，所以會將其本地全局變量 targetPriority 值進行 20% 的衰減（如上圖中“set T3 = 80”），經過衰減後由於 Node3 的 priority 值仍然是小於衰減後的 targetPriority 變量值（80），所以還是無法發起投票請求。

同理，在 t5（>t4）時刻，Node2 在經過衰減後其 targetPriority 值（80）等於自身的 priority 值（80），因而可以向 Raft 集群中其他節點發起 PreVote 預投票請求，得到 Node3 的響應後，Raft 集群就產生了新的 Leader 角色節點 — Node2。

由於 Node 觸發選舉的定時任務 — electionTimer，每次隨機超時觸發的執行時間點不確定，在如上圖所示的實際應用場景中，Node2 或 Node3 都有可能會搶先執行目標優先級衰減降級的流程，所以如果 Node2 和 Node3 自身的 priority 值設置的比較接近，比如 Node3 和 Node2 的 priority 值分別設置為 50 和 40，那麼在某一些時刻，優先級小的 Node2 也有可能會成為 Raft 集群中的 Leader。因此，在實際的生產環境使用中，建議將 Raft 集群中各個節點的優先級定義成區分度較高的數值。

三、SOFAJRaft 優先級選舉機制的實踐示例

在 SOFAJRaft 的 GitHub上有比較詳細的 example 示例，鏈接：
https://github.com/sofastack/sofa-jraft/tree/master/jraft-example/src/main/java/com/alipay/sofa/jraft/example/priorityelection

其中的啟動代碼如下：

PriorityElectionBootstrap

感興趣的用戶可以在本地編輯環境，比如 Idea 或者 Eclipse 的運行命令行中將上面的 demo 程序中所需要的參數設置完，即可體驗優先級選舉的實際效，其中與優先級選舉相關的配置參數在 NodeOptions 類中。

JRaft_Priority_Election_NodeOptions

如上圖所示，其中：

electionPriority：Node 節點本身的 priority 值。如果設置為 0，則表示該節點不參與 Raft 集群 Leader 角色的選舉流程，它永遠不會成為 Leader 角色；如果設置為 -1，則表示該節點不支持優先級選舉功能，它還是執行原本 Raft 隨機超時時間選舉流程；
decayPriorityGap：優先級衰減的間隔值，如果用戶認為 Node 節點本身的 priority 值衰減過慢，可以適當地增加該配置參數，這樣可以使得 priority 值較小的節點不需要花費太多時間即可完成衰減；

四、 SOFAJRaft 優先級選舉機制的源碼解析

handleElectionTimeout

如上圖所示，在 SOFAJRaft 隨機超時時間觸發的定時任務— JRaft-ElectionTimer-X，所執行的 handleElectionTimeout() 方法中，在 preVote 預投票前通過對當前 Node 的優先級變量 priority 值與本地全局變量 targetPriority 值進行判斷和比較，來決定當前 Node 節點是否參與 Raft 集群本輪 Leader 角色的選舉流程。

allowLaunchElection

allowLaunchElection() 方法中定義了當前 Node 節點判斷 priority 值與本地全局變量 targetPriority 值的邏輯。同時，如果在上一輪選舉週期內沒有選舉出 Leader 角色的節點，那麼執行目標優先級衰減降級方法，並設置相關的變量值。

另外，還有一個問題需要注意，在 NodeImpl 中的 stepDown() 方法會調用stopAllAndFindTheNextCandidate() 方法去暫停所有日誌複製的 Replicator 線程，同時找到下一個具有最完備日誌的節點作為最後可能接任下一任 Leader 角色的 Candicate 候選人。所以引入優先級選舉的概念後，除了需要比較日誌的 log_index 值大小以外，如果兩個節點的 log_index 值是相等的，那麼還需要再判斷 priority 值。具體的代碼如下所示：

04 SOFAJRaft_findTheNextCandidate

五、SOFAJRaft 優先級選舉機制的 Jepsen 測試

Jepsen 能在特定故障下驗證系統是否滿足一致性，一方面它提供了故障注入的手段，能模擬各種各樣的故障，比如網絡分區，進程崩潰、CPU 超載等。另一方面，它提供了各種校驗模型，比如 Set、Lock、Queue 等來檢測各種分佈式系統在故障下是否仍然滿足所預期的一致性。所以，通過 Jepsen 測試，能發現分佈式系統在極端故障下的隱藏錯誤，從而提高分佈式系統的容錯能力。

對於分佈式系統而言，一般會使用如下幾種類型的故障進行注入：

（1）partition-random-node 和 partition-random-halves 故障是模擬常見的對稱網絡分區；
（2）kill-random-processes 和 crash-random-nodes 故障是模擬進程崩潰，節點崩潰的情況；
（3）hammer-time 故障是模擬一些慢節點的情況，比如發生 Full GC、OOM 等；
（4）bridge 和 partition-majorities-ring 模擬比較極端的非對稱網絡分區；

分佈式系統故障注入

為驗證 SOFAJRaft 優先級選舉機制的可靠性，我們選擇對上面(1)、(2)、(4)種類型的故障進行注入測試。以圖表的形式可以更好分析 SOFAJRaft 集群在測試過程中的表現情況。下圖展示的是，在模擬注入對稱網絡分區故障情況下，客戶端對 SOFAJRaft 集群每一次操作的時延如下圖所示：

其中藍色框表示數據添加成功，紅色框表示數據添加失敗，黃色框表示不確定是否數據添加成功，灰色部分表示故障注入的時間段。可以看出一些故障注入時間段造成了集群短暫的不可用，一些故障時間段則沒有，這是合理的。由於是隨機網絡分區，所以只有當前 Leader 角色節點被隔離到少數節點區域才會造成集群重新選舉，但即使造成集群重新選舉，在較短時間內， SOFAJRaft 集群也會恢復可用性。此外，可以看到由於 SOFAJRaft 對對稱網絡分區有較好的容錯設計，每次故障恢復後，集群不會發生重新選舉。

下圖展示了 SOFAJRaft 在測試過程中時延百分位點圖。

可以看到除了在一些故障引入後造成集群重新選舉的時間段，時延升高，在其他的時間段， SOFAJRaft 集群表現穩定。 SOFAJRaft 在隨機對稱網絡分區故障注入下，表現穩定，符合預期。除了隨機對稱網絡分區， SOFAJRaft 在其他幾種故障注入下也均通過了 Set 測試的一致性驗證，證明了 SOFAJRaft 對網絡分區，進程、節點崩潰等故障的容錯能力和良好的可靠性。

六、總結

本文從原來 Raft 算法中隨機超時選舉機制帶來的不確定性問題出發，圍繞優先級選舉機制的概念、特點和原理，並結合作者提出的 SOFAJRaft 優先級選舉機制的設計和實現細節，詳細闡述了其基本流程和半確定性，介紹了 SOFAJRaft 優先級選舉的實踐應用，並剖析了源碼中的實現細節。

之前 SOFA 團隊與社區同學共建完結了《剖析 | SOFAJRaft 實現原理》系列，對 SOFAJRaft 的相關實現原理進行源碼解析。現在開啟《SOFAJRaft 特性解析》系列，本文為該系列的第一篇，後續也會持續展開對於 SOFAJRaft 特性的文章分享，也歡迎更多感興趣的技術同學加入～