基于Raft協議的兩節點主備系統調度算法

胡琪，王曉懿，賀國平

（北京工業大學北京市物聯網軟件與系統工程技術研究中心，北京 100124）

0 引言

以城市軌道交通列車指揮調度系統為代表的工業系統，往往在指揮調度中心外的若干運營現場額外部署服務節點。為降低中心離線時運營現場因服務節點故障導致服務中斷的概率，需要在運營現場部署冗余服務節點并保證節點間的數據一致性，但產生的工程成本是不得回避的問題。以城市軌道交通列車指揮調度系統為例，一條線路上往往設置了若干個部署服務節點的集中站，如果在集中站部署3臺服務器，將比部署兩臺服務器多出50%的設備采購成本，如圖1所示。

Fig.1 Typical architecture of dispatch system圖1 指揮調度系統典型架構

此類工業系統往往因工程成本原因在運營現場部署兩個服務節點，并且對這兩個服務節點有著兼顧可用性與一致性的工程需求。但是，主流的分布式一致性協議受限于多數派的限制，要求分布式系統具有3個以上的服務節點才能兼顧可用性與數據一致性，不適用于此類工業系統。

因此，針對運營現場僅有的兩個服務節點在出現單節點故障時無法滿足多數派要求問題，本文基于Raft一致性協議提出一種調度算法，通過Ping請求與應答等機制使路由器能夠參與Leader選舉與數據同步過程，在兩節點分布式系統上基本達到三節點分布式系統運行效果。

1 相關研究

如圖2所示，為解決分布式系統對可用性與一致性的支持，業界提出了很多解決辦法與改進措施。

Fig.2 Brief history of distributed consistency protocols圖2 分布式一致性協議簡史

WARO協議（Write All Read One）提出發生數據更新時只有在所有的服務器節點上更新成功才認為更新成功，從而保證所有的節點上數據一致。WARO隨后被改進，分別提出了2PC協議和Quorum協議。2PC協議將數據同步過程分為Propose和Commit兩個階段，在分布式系統上保持了事務的ACID特性；Quorum算法通過限定讀寫操作最小參與的節點數為節點總數的半數加一，提高了分布式系統的可用性，能夠容忍小于節點總數半數的節點損壞。

通過融合Quorum的多數派設計與2PC的兩個階段，Lamport為業界提供了一個完善的分布式一致問題解決方案，但是工程界在嘗試實現Paxos時遇到了理論與應用之間的鴻溝。后續提出了Multi-Paxos、Fast-Paxos、Cheap-Paxos來嘗試將Paxos工程化。Ongaro等的 一致性協議受到Multi-Paxos影響，也基于多數派思想以及兩個階段數據提交思想，通過強化Leader節點的地位，保證日志的連續性等簡化設計，更加易于工程實現并證明實現的正確性。

Paxos與Raft作為主流的分布式一致性協議，被工程界廣泛采用。但是，隨著應用范圍越來越廣，這些主流協議仍需進一步改進以應對新出現的工程需求。

針對工程應用中對性能的更高要求，文獻［14］將確定性高的節點選為Leader節點，簡化Paxos協議的重確認過程，提高了性能與可用性；文獻［15］提出將普通日志復制替換為糾刪碼復制來降低存儲和網絡成本；文獻［16］中以多數派數據讀取的設計替換原有的從Leader節點讀取的設計，提高了讀性能；文獻［17］通過利用固定時段的歷史日志故障次數統計，實現最多經歷一次計時器時間完成Leader節點的確定；文獻［18］針對Raft中故障恢復節點需要多次網絡通信才能完成數據恢復的問題，提出了AELR算法，通過一次網絡通信獲取少量的數據即可完成數據恢復；文獻［19］在確保數據同步性的安全同時，通過提升數據同步的并發性來提高吞吐量。然而，此類研究主要聚焦于對性能的提升，均以節點數量滿足基礎運行要求為前提，沒有針對工程成本限制導致的節點數量不足、單節點故障時無法構成多數派的問題進行改進，此類研究可作為本算法后續性能提升的參考。

針對工程應用中對可用性的更高要求，文獻［20-21］通過在一些非必須的時刻縮減多數派設計的數量限制來提高Paxos的靈活性；MFTFS文件系統引入熱備群集和冷備群集，并通過Raft確定主機，實現主熱備集群發生單節點故障時由冷備集群中的節點加入熱備集群，繼續對外提供服務；文獻［23］則將Raft協議放在交換機上運行，節約了服務節點開銷；文獻［24］在Proposer再次發出prepare請求前增加隨機長度的延遲，防止發生活鎖；文獻［25］在Raft協議基礎上根據工作負載的增減實現對分布式系統的自動縮放。然而，Flexible Paxos因為基于Paxos設計，存在工程實現難的問題；MFTFS文件系統與Network-Assisted Raft均會導致工程成本增加；TB-Paxos與Geo-Raft在行為邏輯上提高了可用性，但仍以節點數量滿足基礎運行要求為前提。

綜上，當前大部分研究均無法完美解決本文提出的工程需求。為更有利于工程實現，本文以Raft一致性協議作為理論與設計基礎，并對其加以改進，解決兩節點分布式系統兼顧可用性與數據一致性問題。

2 兩節點主備系統調度算法設計

2.1 對Raft一致性協議改造的難點

為防止分網等故障造成“腦裂”和數據沖突問題，多數派設計貫穿了Raft一致性協議的兩個核心工作過程：Leader選舉與數據同步。在一個基于原生Raft的兩節點分布式系統中，由于節點總數為2，大于節點總數半數的最小數值也為2，因此整個系統的任何操作都需要所有節點參與，這也意味著當Leader節點故障離線時，存活的另一Follower節點因Leader選舉得票不足無法成為新的Leader節點；當Follower節點故障離線，仍然存活的Leader節點也會因為數據沒有同步給另一節點而無法完成數據提交。

但是，任何嘗試對多數派設計的修改都將造成正確性問題，例如一個顯而易見的方法就是在一個節點發現與另外一個節點失去聯系之后會降低多數派標準，使得節點在不能構成多數派的情況下也能完成Leader選舉和數據同步。但一旦發生分網故障，整個系統將會出現兩個Leader節點，導致兩個節點之間產生數據狀態差異。

2.2 讓路由器成為分布式系統中的節點

通過降低多數派設計的節點數量來解決多數派限制的方案不可行，則通過增加節點來滿足多數派的限制成為唯一方向。

若這個節點是一個工程中成本很低或必不可缺的硬件設備，當這個設備成為分布式系統中的節點之后，不會導致成本超出預期，能夠滿足工程成本需求。

若在Leader選舉以及數據同步過程中該設備能夠提供關鍵的輔助信息，那么就能在不打破任何Raft協議基礎理論的情況下，讓兩臺服務器及該硬件設備實現三節點分布式系統運行效果。

路由器支持TCP、UDP、ICMP等網絡通信協議，具有提供關鍵輔助信息的潛力，本算法選定路由器這一必不可少且不會額外增加任何工程成本的設備作為分布式系統邏輯上的第3個節點。

2.3 基礎設計

受限于實際設備情況，工程中往往無法讓路由器運行Raft一致性協議，因此需要對路由器進行抽象設計，利用路由器上運行的若干網絡協議來獲取一些關鍵的輔助信息。

Raft一致性協議通過網絡傳輸的內容十分簡單，在Leader選舉和數據同步功能中分別用到Append Entries請求、RequestVote請求以及它們對應的應答。考慮到路由器節點無法主動發出這兩種請求，本算法將路由器節點抽象地視為一個永遠不會嘗試成為Leader的Follower節點，因此它無需對外發出任何請求，只需要對請求進行應答。

但是接收這兩種請求并應答的路由器也面臨無法執行問題。為此，本算法選擇將IMCP協議中的Ping請求抽象為Raft協議的兩種請求內容，將路由器的Ping應答抽象為對兩種請求的執行成功應答。對于Leader選舉過程，Ping應答就相當于Leader選舉投贊成票；對于數據同步過程，Ping應答就相當于數據同步成功應答。

但是，Raft協議設計的兩個應答消息攜帶了一些額外的重要數據，這些數據肯定無法從Ping請求與應答中獲取，需要在現有Raft協議的Leader選舉與數據同步設計基礎上增加一些設計來彌補這些關鍵數據的缺失。

2.4 對Leader選舉過程的設計

受Raft一致性協議規定，當一個Follower節點收到RequestVote請求時，需要檢查請求內容來確定是否發出肯定的投票應答：①請求發出者的數據狀態是否陳舊；②請求發出者的Term是否陳舊；③是否投出了該Term下唯一的贊成票。

顯然，路由器無法完成這3項檢查中的任何一個。因此，只能通過在發出RequestVote請求的節點上增加一些設計來解決這一問題。

由于無法滿足③中的檢查內容，在網絡連接正常情況下，任何時刻服務節點向路由器節點發出投票請求，路由器節點都會回復贊成票，這將造成同一個Term內路由器節點發出多次贊成票，導致分布式系統出現多個Leader節點。然而，路由器在收到Ping請求之后進行應答是路由器的固有行為，并不會因為本算法將Ping應答視作贊成的應答而發生任何改變。

因此，本算法基于分時復用思想設計了全局時鐘機制，將物理時間拆分為與選舉超時時間上限相同的片段，節點只能在所屬時間片段的開始時刻向路由器節點發出投票請求，并且在時間片段和當前Term的選舉超時結束前收到應答才算得票。其中一個節點所屬時間片段序號為奇數，另外一個所屬時間片段序號為偶數，因此不存在同一個時間片段內同時有兩個服務器節點向路由器節點發出投票請求的情況，進而保證了同一Term內路由器不會多次投出贊成票。

實際工程中不能忽略網絡可能存在的丟包問題，例如有可能出現兩個節點間所有的消息包均在發送過程中丟失，但是Ping的消息包卻成功接收的情況，此時全局時鐘無法阻止多個Leader的出現。為此，本算法增加了對指定IP地址搶占的設計。當一個節點嘗試由Candidate狀態變為Leader狀態時，除了收到路由器的Ping應答，還需要成功執行IP搶占，否則無法轉變狀態至Leader節點，由此保證分布式系統一定不會在同一Term內出現兩個Leader。IP搶占功能可以借用一些網絡協議實現，如基于ARP協議的IP漂移，或基于DHCP的IP分配與續約等。

Fig.3 State transition圖3 狀態轉換

情況①與情況②中的檢查內容屬于對發出請求節點狀態的檢查，路由器同樣會因為對Ping請求進行應答的固有特性而無法完成兩項檢查內容的處理。因此，本算法將該檢查轉移到發出請求節點的內部進行。如圖3所示，本算法在節點上增加了Ping應答是否有效的狀態設計，該狀態設計包含available（可用狀態）、unavailable（不可用狀態）兩個狀態。處于unavailable狀態時，來自路由器的Ping應答將被判定為失效，available狀態反之，兩個狀態之間的轉換遵循以下原則：

（1）節點啟動，路由器投票狀態將處于unavailable狀態。

（2）節點與路由器通信失敗時將處于unavailable狀態。

（3）陳舊的節點數據將處于unavilable狀態。

（4）嘗試搶占指定IP地址失敗時將處于unavailable狀態。

（5）當節點處于unavailable狀態時，若收到來自其他節點的消息并且所存儲的數據為一樣新或者更新的情況時，則將狀態轉變為available。基于上述規則，服務節點與路由器節點交互的行為能夠與服務節點間交互的行為保持一致。

對于情況①中的檢查內容：請求攜帶的數據是否從陳舊的判斷，本算法利用兩個服務器節點間的消息交換使每個節點能知道另一節點的數據情況，進而比較和判斷本節點數據是否為陳舊。

以一個節點視角來看，它不能在剛啟動或者因為網絡問題失去與分布式系統聯系的情況下確保數據是最新的，因而規則（1）-規則（3）共同保證了數據可能陳舊的節點不會因為接收到路由器節點的投票而成為Leader，規則（4）避免了丟包等網絡故障造成的分布式系統中出現多個Leader節點，規則（5）則用于確定一個節點何時具備成為Leader的潛力。

對于情況②中的檢查內容：Term的相關判斷和處理，本算法在服務器節點間采用原生的Raft機制，Raft協議已經對它的安全性進行了證明；與路由器節點交互時，本算法取消情況②中對Term的檢查。一個節點需要與另外一個節點進行信息交換才有可能進入available狀態從而通過Ping應答成為Leader節點。而在進行信息交換時，Raft協議提供了節點間Term同步的措施，保證了節點間的Term一定是同步且最新的。

2.5 對數據同步過程的設計

本算法能夠保證數據陳舊的節點一定不會成為Leader節點，而Raft協議規定，只有Leader節點才能發起數據同步，因此路由器節點即便不對數據同步的請求進行檢查，在兩節點分布式系統中也不會存在正確性問題。

本算法在Raft協議數據同步功能基礎上增加了數據同步模式轉換機制。當Leader節點能夠與Follower節點正常通信時，Leader節點將數據同步的標準提高，收到來自路由器和另外一個Follower節點的數據同步成功的應答后才能將數據提交。

當無法與另外一個Follower節點通信時，將數據同步的標準降低，只要收到來自路由器的數據同步應答即可進行數據提交。判定能否與Follower節點正常通信的標準是，在兩個選舉超時周期內是否收到了來自Follower節點的數據同步應答，以防止新一任的Leader節點產生之前前一任的Leader提交新的數據。通過該設計，避免了路由器Ping應答速度過快，Leader節點與Follower節點產生較大的數據差距問題。

同時，為了提高算法的可用性，還調整了數據新舊程度判別標準。原生Raft通過最新一條log記錄的Index和Term進行判別，本算法將其降低至已提交的log記錄的Index進行判別：Index一樣新或者更新即為節點的數據狀態是最新或者更新的。通過該設計，可在一定程度上避免了大量請求情況下時，Follower節點按照Raft一致性協議的判別標準長期處于數據陳舊狀態而無法成為新任的Leader。

當然，本文提出的算法還需要對原生Raft的兩對請求與應答消息包進行擴容，增加已提交的log記錄的Index信息，以便兩個節點能夠在消息交換時獲知另一節點的數據狀態。

3 實驗驗證

實驗以基于本算法的兩節點分布式系統作為實驗組，以基于Raft協議的兩節點、三節點分布式系統作為對照組，驗證本算法Leader選舉正確性、數據同步正確性、性能及可用性。

（1）在驗證Leader選舉正確性時，實驗以300次客戶端請求為工作周期，每個節點在工作周期內隨機出現節點停止運行、節點恢復運行、網絡斷開、網絡恢復以及網絡丟包的故障情況，以此模擬實際運行過程各種復雜故障情景。實驗組與對照組的消息丟包率為30%，斷網、停機故障出現和恢復的時間周期為10s內的隨機數。通過監測是否出現了多個Leader節點故障，從而證明Leader選舉正確性。同時通過統計出現多Leader節點的時長，量化Leader選舉問題的嚴重性。實驗組與對照組都進行10次實驗，并將最終獲取到的實驗數據求取平均值。

（2）在驗證數據同步正確性時，將復用驗證Leader選舉正確性的實驗設計，由客戶端向整個分布式系統發送300個內容為連續數字序號的請求，通過檢查每個節點的數據同步結果是否出現了數據不一致問題來證明數據同步的正確性。通過統計問題序號出現的個數，量化數據同步問題的嚴重性。實驗組與對照組同樣進行10次實驗，并將最終獲取到的實驗數據求取平均值。

（3）測試系統運行核心性能包括：Leader選舉的性能測試、數據同步的性能測試。在測試Leader選舉性能時，實驗以完成100次主機更迭的耗時作為量化評價標準。為測試數據的準確性，本實驗僅將每次前一任Leader節點停機到新一任的Leader出現這段時間列入統計。在測試數據同步性能時，實驗以連續完成300次數據同步的耗時作為量化評價標準，記錄客戶端發出第1個請求到收到第300個請求的應答時間間隔。

（4）在對可用性進行考察時，由于故障情況無法窮舉，本實驗將測試驗證一些典型故障下的可用性表現，每個典型故障下進行5次重復的定性實驗。首先將故障情況大致分類為節點停機及恢復、網絡故障及恢復。

其中，節點停機及恢復包含：僅有一個節點停機、僅有一個節點停機且從停機中恢復、僅有兩個節點停機、僅有兩個節點停機且依次從停機中恢復。

網絡故障包含：僅有一個節點發生斷網、僅有一個節點發生斷網并從斷網故障中恢復、僅有兩個節點發生斷網、僅有兩個節點發生斷網且依次從斷網中恢復。

實驗結果以分數的形式來量化在某一故障下分布式系統的可用性。統計方式為：

能對外提供服務的情況數量/總情況數量×100

例如：基于本算法的兩節點分布式系統，在遭遇其中一個節點發生故障停機時包含3種情況：①Follower節點停機；②Leader節點停機且Follower節點數據與Leader節點一樣新；③Leader節點停機且Follower節點數據陳舊。其中，當遭遇Leader節點停機且Follower節點數據陳舊時，基于本算法的兩節點分布式系統為了保證數據一致性，將停止對外提供服務。因此，可用性得分為：2/3×100=66.6。

4 實驗結果分析

在完成驗證Leader選舉正確性的實驗之后得到如圖4所示的結果。

Fig.4 Thelength of time in each state of distributed systems圖4 分布式系統處于各個狀態下的時長

圖4統計了在不同設計下分布式系統存在隨機故障情況時完成300次數據同步的工作總時長以及處于各種狀態下的時長。測試結果中，基于本算法與基于Raft協議的三節點分布式系統均出現兩個Leader節點情況，但是通過對邏輯狀態以及系統故障情況的分析，該情況符合設計預期。這兩個Leader節點中有一個處于陳舊的Term狀態且無法完成數據提交。當丟包或者斷網故障恢復后，Term陳舊的Leader節點會自我修復進入Follower狀態，整個分布式系統的Leader選舉正確性不會受到任何影響。

通過統計數據同步情況得到圖5中的統計數據。無論是Raft一致性協議還是本算法，數據同步的結果均沒有發生序號缺失、覆蓋、重復、前后顛倒等情況。因此，它們的數據不一致個數均為0。

Fig.5 Number of data synchronization and number of data inconsistencies圖5 數據同步數量與數據不一致次數

由圖6可見，統計了完成100次Leader選舉的總耗時，用于檢驗本算法中Leader選舉性能。由于基于Raft協議的兩節點分布式系統無法支持僅剩一個節點正常運行情況下選舉出新的Leader節點，因此設其Leader選舉耗時為無限大。基于本算法的兩節點分布式系統的Leader選舉性能比基于Raft的三節點分布式系統稍差，但未達到數量級以上的差距，不會對工程使用造成影響，其主要原因是本算法增加了全局時鐘以及IP搶占設計，造成一定的延遲。

圖7統計了連續完成300次數據同步的總耗時，用于檢驗本算法中數據同步性能。基于本算法的兩節點分布式系統比基于Raft協議的兩節點分布式系統在數據同步性能上稍有差距。因為在常規的數據同步工作流程中，本算法需要得到來自Follower節點以及路由器節點的數據同步應答才能完成數據提交。而基于Raft協議的兩節點分布式系統中，數據同步給另一個節點之后就能夠完成數據提交。此外，由于基于Raft協議的三節點分布式系統需要最終將數據同步給另外兩個節點，因此造成時間損耗較大。但總體而言，本算法在數據同步性能方面與Raft協議接近。

Fig.6 Timeto complete100 times Leader elections圖6 完成100次Leader選舉的耗時

Fig.7 Time to complete 300 times data synchronizations圖7 完成300次數據同步的耗時

圖8分別記錄了基于本算法的兩節點分布式系統、基于Raft協議的三節點和兩節點分布式系統在各種典型故障情況下可用性測試結果。

本算法的可用性接近于Raft協議。在一些嚴重的故障下，例如分布式系統中有兩個節點同時出現停機、斷網故障時，它們均停止對外提供服務。

當分布式系統中一個節點出現故障，基于Raft協議的兩節點分布式系統將無法繼續提供服務，而基于本算法的兩節點分布式系統與基于Raft協議的三節點分布式系統依然能夠對外提供服務，只不過本算法為了保護數據一致性，在一些僅剩單個節點存活的情況下也將停止對外提供服務。

Fig.8 Availability test results of distributed system圖8 分布式系統可用性測試結果

5 結語

本文基于Raft一致性協議，提出能夠在兩個節點分布式主備系統中運行的調度算法，在不增加工程成本的情況下具備以下實際工程應用特征：①兼顧可用性與一致性；②保證Leader選舉與數據同步的正確性；③性能與Raft一致性協議接近；④可用性方面與Raft一致性協議沒有明顯差距。

但是，本算法在性能、可用性以及對路由器過度依賴方面仍有進一步提升空間。隨著路由器設備的可拓展性逐漸增強，后續可考慮將Raft協議簡化，讓路由器節點運行Raft協議并記錄少量的關鍵信息，構建由多個路由器與服務節點組成的異構分布式系統。在不顯著增加成本的情況下具備與3個以上節點的分布式系統同樣優秀的性能與可用性，同時避免因單個路由器故障造成的服務中斷。