基于Raft協(xié)議的兩節(jié)點(diǎn)主備系統(tǒng)調(diào)度算法

胡琪，王曉懿，賀國平

（北京工業(yè)大學(xué)北京市物聯(lián)網(wǎng)軟件與系統(tǒng)工程技術(shù)研究中心，北京 100124）

0 引言

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

Fig.1 Typical architecture of dispatch system圖1 指揮調(diào)度系統(tǒng)典型架構(gòu)

此類工業(yè)系統(tǒng)往往因工程成本原因在運(yùn)營現(xiàn)場部署兩個(gè)服務(wù)節(jié)點(diǎn)，并且對這兩個(gè)服務(wù)節(jié)點(diǎn)有著兼顧可用性與一致性的工程需求。但是，主流的分布式一致性協(xié)議受限于多數(shù)派的限制，要求分布式系統(tǒng)具有3個(gè)以上的服務(wù)節(jié)點(diǎn)才能兼顧可用性與數(shù)據(jù)一致性，不適用于此類工業(yè)系統(tǒng)。

因此，針對運(yùn)營現(xiàn)場僅有的兩個(gè)服務(wù)節(jié)點(diǎn)在出現(xiàn)單節(jié)點(diǎn)故障時(shí)無法滿足多數(shù)派要求問題，本文基于Raft一致性協(xié)議提出一種調(diào)度算法，通過Ping請求與應(yīng)答等機(jī)制使路由器能夠參與Leader選舉與數(shù)據(jù)同步過程，在兩節(jié)點(diǎn)分布式系統(tǒng)上基本達(dá)到三節(jié)點(diǎn)分布式系統(tǒng)運(yùn)行效果。

1 相關(guān)研究

如圖2所示，為解決分布式系統(tǒng)對可用性與一致性的支持，業(yè)界提出了很多解決辦法與改進(jìn)措施。

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

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

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

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

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

針對工程應(yīng)用中對可用性的更高要求，文獻(xiàn)［20-21］通過在一些非必須的時(shí)刻縮減多數(shù)派設(shè)計(jì)的數(shù)量限制來提高Paxos的靈活性；MFTFS文件系統(tǒng)引入熱備群集和冷備群集，并通過Raft確定主機(jī)，實(shí)現(xiàn)主熱備集群發(fā)生單節(jié)點(diǎn)故障時(shí)由冷備集群中的節(jié)點(diǎn)加入熱備集群，繼續(xù)對外提供服務(wù)；文獻(xiàn)［23］則將Raft協(xié)議放在交換機(jī)上運(yùn)行，節(jié)約了服務(wù)節(jié)點(diǎn)開銷；文獻(xiàn)［24］在Proposer再次發(fā)出prepare請求前增加隨機(jī)長度的延遲，防止發(fā)生活鎖；文獻(xiàn)［25］在Raft協(xié)議基礎(chǔ)上根據(jù)工作負(fù)載的增減實(shí)現(xiàn)對分布式系統(tǒng)的自動(dòng)縮放。然而，F(xiàn)lexible Paxos因?yàn)榛赑axos設(shè)計(jì)，存在工程實(shí)現(xiàn)難的問題；MFTFS文件系統(tǒng)與Network-Assisted Raft均會(huì)導(dǎo)致工程成本增加；TB-Paxos與Geo-Raft在行為邏輯上提高了可用性，但仍以節(jié)點(diǎn)數(shù)量滿足基礎(chǔ)運(yùn)行要求為前提。

綜上，當(dāng)前大部分研究均無法完美解決本文提出的工程需求。為更有利于工程實(shí)現(xiàn)，本文以Raft一致性協(xié)議作為理論與設(shè)計(jì)基礎(chǔ)，并對其加以改進(jìn)，解決兩節(jié)點(diǎn)分布式系統(tǒng)兼顧可用性與數(shù)據(jù)一致性問題。

2 兩節(jié)點(diǎn)主備系統(tǒng)調(diào)度算法設(shè)計(jì)

2.1 對Raft一致性協(xié)議改造的難點(diǎn)

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

但是，任何嘗試對多數(shù)派設(shè)計(jì)的修改都將造成正確性問題，例如一個(gè)顯而易見的方法就是在一個(gè)節(jié)點(diǎn)發(fā)現(xiàn)與另外一個(gè)節(jié)點(diǎn)失去聯(lián)系之后會(huì)降低多數(shù)派標(biāo)準(zhǔn)，使得節(jié)點(diǎn)在不能構(gòu)成多數(shù)派的情況下也能完成Leader選舉和數(shù)據(jù)同步。但一旦發(fā)生分網(wǎng)故障，整個(gè)系統(tǒng)將會(huì)出現(xiàn)兩個(gè)Leader節(jié)點(diǎn)，導(dǎo)致兩個(gè)節(jié)點(diǎn)之間產(chǎn)生數(shù)據(jù)狀態(tài)差異。

2.2 讓路由器成為分布式系統(tǒng)中的節(jié)點(diǎn)

通過降低多數(shù)派設(shè)計(jì)的節(jié)點(diǎn)數(shù)量來解決多數(shù)派限制的方案不可行，則通過增加節(jié)點(diǎn)來滿足多數(shù)派的限制成為唯一方向。

若這個(gè)節(jié)點(diǎn)是一個(gè)工程中成本很低或必不可缺的硬件設(shè)備，當(dāng)這個(gè)設(shè)備成為分布式系統(tǒng)中的節(jié)點(diǎn)之后，不會(huì)導(dǎo)致成本超出預(yù)期，能夠滿足工程成本需求。

若在Leader選舉以及數(shù)據(jù)同步過程中該設(shè)備能夠提供關(guān)鍵的輔助信息，那么就能在不打破任何Raft協(xié)議基礎(chǔ)理論的情況下，讓兩臺(tái)服務(wù)器及該硬件設(shè)備實(shí)現(xiàn)三節(jié)點(diǎn)分布式系統(tǒng)運(yùn)行效果。

路由器支持TCP、UDP、ICMP等網(wǎng)絡(luò)通信協(xié)議，具有提供關(guān)鍵輔助信息的潛力，本算法選定路由器這一必不可少且不會(huì)額外增加任何工程成本的設(shè)備作為分布式系統(tǒng)邏輯上的第3個(gè)節(jié)點(diǎn)。

2.3 基礎(chǔ)設(shè)計(jì)

受限于實(shí)際設(shè)備情況，工程中往往無法讓路由器運(yùn)行Raft一致性協(xié)議，因此需要對路由器進(jìn)行抽象設(shè)計(jì)，利用路由器上運(yùn)行的若干網(wǎng)絡(luò)協(xié)議來獲取一些關(guān)鍵的輔助信息。

Raft一致性協(xié)議通過網(wǎng)絡(luò)傳輸?shù)膬?nèi)容十分簡單，在Leader選舉和數(shù)據(jù)同步功能中分別用到Append Entries請求、RequestVote請求以及它們對應(yīng)的應(yīng)答?？紤]到路由器節(jié)點(diǎn)無法主動(dòng)發(fā)出這兩種請求，本算法將路由器節(jié)點(diǎn)抽象地視為一個(gè)永遠(yuǎn)不會(huì)嘗試成為Leader的Follower節(jié)點(diǎn)，因此它無需對外發(fā)出任何請求，只需要對請求進(jìn)行應(yīng)答。

但是接收這兩種請求并應(yīng)答的路由器也面臨無法執(zhí)行問題。為此，本算法選擇將IMCP協(xié)議中的Ping請求抽象為Raft協(xié)議的兩種請求內(nèi)容，將路由器的Ping應(yīng)答抽象為對兩種請求的執(zhí)行成功應(yīng)答。對于Leader選舉過程，Ping應(yīng)答就相當(dāng)于Leader選舉投贊成票；對于數(shù)據(jù)同步過程，Ping應(yīng)答就相當(dāng)于數(shù)據(jù)同步成功應(yīng)答。

但是，Raft協(xié)議設(shè)計(jì)的兩個(gè)應(yīng)答消息攜帶了一些額外的重要數(shù)據(jù)，這些數(shù)據(jù)肯定無法從Ping請求與應(yīng)答中獲取，需要在現(xiàn)有Raft協(xié)議的Leader選舉與數(shù)據(jù)同步設(shè)計(jì)基礎(chǔ)上增加一些設(shè)計(jì)來彌補(bǔ)這些關(guān)鍵數(shù)據(jù)的缺失。

2.4 對Leader選舉過程的設(shè)計(jì)

受Raft一致性協(xié)議規(guī)定，當(dāng)一個(gè)Follower節(jié)點(diǎn)收到RequestVote請求時(shí)，需要檢查請求內(nèi)容來確定是否發(fā)出肯定的投票應(yīng)答：①請求發(fā)出者的數(shù)據(jù)狀態(tài)是否陳舊；②請求發(fā)出者的Term是否陳舊；③是否投出了該Term下唯一的贊成票。

顯然，路由器無法完成這3項(xiàng)檢查中的任何一個(gè)。因此，只能通過在發(fā)出RequestVote請求的節(jié)點(diǎn)上增加一些設(shè)計(jì)來解決這一問題。

由于無法滿足③中的檢查內(nèi)容，在網(wǎng)絡(luò)連接正常情況下，任何時(shí)刻服務(wù)節(jié)點(diǎn)向路由器節(jié)點(diǎn)發(fā)出投票請求，路由器節(jié)點(diǎn)都會(huì)回復(fù)贊成票，這將造成同一個(gè)Term內(nèi)路由器節(jié)點(diǎn)發(fā)出多次贊成票，導(dǎo)致分布式系統(tǒng)出現(xiàn)多個(gè)Leader節(jié)點(diǎn)。然而，路由器在收到Ping請求之后進(jìn)行應(yīng)答是路由器的固有行為，并不會(huì)因?yàn)楸舅惴▽ing應(yīng)答視作贊成的應(yīng)答而發(fā)生任何改變。

因此，本算法基于分時(shí)復(fù)用思想設(shè)計(jì)了全局時(shí)鐘機(jī)制，將物理時(shí)間拆分為與選舉超時(shí)時(shí)間上限相同的片段，節(jié)點(diǎn)只能在所屬時(shí)間片段的開始時(shí)刻向路由器節(jié)點(diǎn)發(fā)出投票請求，并且在時(shí)間片段和當(dāng)前Term的選舉超時(shí)結(jié)束前收到應(yīng)答才算得票。其中一個(gè)節(jié)點(diǎn)所屬時(shí)間片段序號(hào)為奇數(shù)，另外一個(gè)所屬時(shí)間片段序號(hào)為偶數(shù)，因此不存在同一個(gè)時(shí)間片段內(nèi)同時(shí)有兩個(gè)服務(wù)器節(jié)點(diǎn)向路由器節(jié)點(diǎn)發(fā)出投票請求的情況，進(jìn)而保證了同一Term內(nèi)路由器不會(huì)多次投出贊成票。

實(shí)際工程中不能忽略網(wǎng)絡(luò)可能存在的丟包問題，例如有可能出現(xiàn)兩個(gè)節(jié)點(diǎn)間所有的消息包均在發(fā)送過程中丟失，但是Ping的消息包卻成功接收的情況，此時(shí)全局時(shí)鐘無法阻止多個(gè)Leader的出現(xiàn)。為此，本算法增加了對指定IP地址搶占的設(shè)計(jì)。當(dāng)一個(gè)節(jié)點(diǎn)嘗試由Candidate狀態(tài)變?yōu)長eader狀態(tài)時(shí)，除了收到路由器的Ping應(yīng)答，還需要成功執(zhí)行IP搶占，否則無法轉(zhuǎn)變狀態(tài)至Leader節(jié)點(diǎn)，由此保證分布式系統(tǒng)一定不會(huì)在同一Term內(nèi)出現(xiàn)兩個(gè)Leader。IP搶占功能可以借用一些網(wǎng)絡(luò)協(xié)議實(shí)現(xiàn)，如基于ARP協(xié)議的IP漂移，或基于DHCP的IP分配與續(xù)約等。

Fig.3 State transition圖3 狀態(tài)轉(zhuǎn)換

情況①與情況②中的檢查內(nèi)容屬于對發(fā)出請求節(jié)點(diǎn)狀態(tài)的檢查，路由器同樣會(huì)因?yàn)閷ing請求進(jìn)行應(yīng)答的固有特性而無法完成兩項(xiàng)檢查內(nèi)容的處理。因此，本算法將該檢查轉(zhuǎn)移到發(fā)出請求節(jié)點(diǎn)的內(nèi)部進(jìn)行。如圖3所示，本算法在節(jié)點(diǎn)上增加了Ping應(yīng)答是否有效的狀態(tài)設(shè)計(jì)，該狀態(tài)設(shè)計(jì)包含available（可用狀態(tài)）、unavailable（不可用狀態(tài)）兩個(gè)狀態(tài)。處于unavailable狀態(tài)時(shí)，來自路由器的Ping應(yīng)答將被判定為失效，available狀態(tài)反之，兩個(gè)狀態(tài)之間的轉(zhuǎn)換遵循以下原則：

（1）節(jié)點(diǎn)啟動(dòng)，路由器投票狀態(tài)將處于unavailable狀態(tài)。

（2）節(jié)點(diǎn)與路由器通信失敗時(shí)將處于unavailable狀態(tài)。

（3）陳舊的節(jié)點(diǎn)數(shù)據(jù)將處于unavilable狀態(tài)。

（4）嘗試搶占指定IP地址失敗時(shí)將處于unavailable狀態(tài)。

（5）當(dāng)節(jié)點(diǎn)處于unavailable狀態(tài)時(shí)，若收到來自其他節(jié)點(diǎn)的消息并且所存儲(chǔ)的數(shù)據(jù)為一樣新或者更新的情況時(shí)，則將狀態(tài)轉(zhuǎn)變?yōu)閍vailable?；谏鲜鲆?guī)則，服務(wù)節(jié)點(diǎn)與路由器節(jié)點(diǎn)交互的行為能夠與服務(wù)節(jié)點(diǎn)間交互的行為保持一致。

對于情況①中的檢查內(nèi)容：請求攜帶的數(shù)據(jù)是否從陳舊的判斷，本算法利用兩個(gè)服務(wù)器節(jié)點(diǎn)間的消息交換使每個(gè)節(jié)點(diǎn)能知道另一節(jié)點(diǎn)的數(shù)據(jù)情況，進(jìn)而比較和判斷本節(jié)點(diǎn)數(shù)據(jù)是否為陳舊。

以一個(gè)節(jié)點(diǎn)視角來看，它不能在剛啟動(dòng)或者因?yàn)榫W(wǎng)絡(luò)問題失去與分布式系統(tǒng)聯(lián)系的情況下確保數(shù)據(jù)是最新的，因而規(guī)則（1）-規(guī)則（3）共同保證了數(shù)據(jù)可能陳舊的節(jié)點(diǎn)不會(huì)因?yàn)榻邮盏铰酚善鞴?jié)點(diǎn)的投票而成為Leader，規(guī)則（4）避免了丟包等網(wǎng)絡(luò)故障造成的分布式系統(tǒng)中出現(xiàn)多個(gè)Leader節(jié)點(diǎn)，規(guī)則（5）則用于確定一個(gè)節(jié)點(diǎn)何時(shí)具備成為Leader的潛力。

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

2.5 對數(shù)據(jù)同步過程的設(shè)計(jì)

本算法能夠保證數(shù)據(jù)陳舊的節(jié)點(diǎn)一定不會(huì)成為Leader節(jié)點(diǎn)，而Raft協(xié)議規(guī)定，只有Leader節(jié)點(diǎn)才能發(fā)起數(shù)據(jù)同步，因此路由器節(jié)點(diǎn)即便不對數(shù)據(jù)同步的請求進(jìn)行檢查，在兩節(jié)點(diǎn)分布式系統(tǒng)中也不會(huì)存在正確性問題。

本算法在Raft協(xié)議數(shù)據(jù)同步功能基礎(chǔ)上增加了數(shù)據(jù)同步模式轉(zhuǎn)換機(jī)制。當(dāng)Leader節(jié)點(diǎn)能夠與Follower節(jié)點(diǎn)正常通信時(shí)，Leader節(jié)點(diǎn)將數(shù)據(jù)同步的標(biāo)準(zhǔn)提高，收到來自路由器和另外一個(gè)Follower節(jié)點(diǎn)的數(shù)據(jù)同步成功的應(yīng)答后才能將數(shù)據(jù)提交。

當(dāng)無法與另外一個(gè)Follower節(jié)點(diǎn)通信時(shí)，將數(shù)據(jù)同步的標(biāo)準(zhǔn)降低，只要收到來自路由器的數(shù)據(jù)同步應(yīng)答即可進(jìn)行數(shù)據(jù)提交。判定能否與Follower節(jié)點(diǎn)正常通信的標(biāo)準(zhǔn)是，在兩個(gè)選舉超時(shí)周期內(nèi)是否收到了來自Follower節(jié)點(diǎn)的數(shù)據(jù)同步應(yīng)答，以防止新一任的Leader節(jié)點(diǎn)產(chǎn)生之前前一任的Leader提交新的數(shù)據(jù)。通過該設(shè)計(jì)，避免了路由器Ping應(yīng)答速度過快，Leader節(jié)點(diǎn)與Follower節(jié)點(diǎn)產(chǎn)生較大的數(shù)據(jù)差距問題。

同時(shí)，為了提高算法的可用性，還調(diào)整了數(shù)據(jù)新舊程度判別標(biāo)準(zhǔn)。原生Raft通過最新一條log記錄的Index和Term進(jìn)行判別，本算法將其降低至已提交的log記錄的Index進(jìn)行判別：Index一樣新或者更新即為節(jié)點(diǎn)的數(shù)據(jù)狀態(tài)是最新或者更新的。通過該設(shè)計(jì)，可在一定程度上避免了大量請求情況下時(shí)，F(xiàn)ollower節(jié)點(diǎn)按照Raft一致性協(xié)議的判別標(biāo)準(zhǔn)長期處于數(shù)據(jù)陳舊狀態(tài)而無法成為新任的Leader。

當(dāng)然，本文提出的算法還需要對原生Raft的兩對請求與應(yīng)答消息包進(jìn)行擴(kuò)容，增加已提交的log記錄的Index信息，以便兩個(gè)節(jié)點(diǎn)能夠在消息交換時(shí)獲知另一節(jié)點(diǎn)的數(shù)據(jù)狀態(tài)。

3 實(shí)驗(yàn)驗(yàn)證

實(shí)驗(yàn)以基于本算法的兩節(jié)點(diǎn)分布式系統(tǒng)作為實(shí)驗(yàn)組，以基于Raft協(xié)議的兩節(jié)點(diǎn)、三節(jié)點(diǎn)分布式系統(tǒng)作為對照組，驗(yàn)證本算法Leader選舉正確性、數(shù)據(jù)同步正確性、性能及可用性。

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

（2）在驗(yàn)證數(shù)據(jù)同步正確性時(shí)，將復(fù)用驗(yàn)證Leader選舉正確性的實(shí)驗(yàn)設(shè)計(jì)，由客戶端向整個(gè)分布式系統(tǒng)發(fā)送300個(gè)內(nèi)容為連續(xù)數(shù)字序號(hào)的請求，通過檢查每個(gè)節(jié)點(diǎn)的數(shù)據(jù)同步結(jié)果是否出現(xiàn)了數(shù)據(jù)不一致問題來證明數(shù)據(jù)同步的正確性。通過統(tǒng)計(jì)問題序號(hào)出現(xiàn)的個(gè)數(shù)，量化數(shù)據(jù)同步問題的嚴(yán)重性。實(shí)驗(yàn)組與對照組同樣進(jìn)行10次實(shí)驗(yàn)，并將最終獲取到的實(shí)驗(yàn)數(shù)據(jù)求取平均值。

（3）測試系統(tǒng)運(yùn)行核心性能包括：Leader選舉的性能測試、數(shù)據(jù)同步的性能測試。在測試Leader選舉性能時(shí)，實(shí)驗(yàn)以完成100次主機(jī)更迭的耗時(shí)作為量化評價(jià)標(biāo)準(zhǔn)。為測試數(shù)據(jù)的準(zhǔn)確性，本實(shí)驗(yàn)僅將每次前一任Leader節(jié)點(diǎn)停機(jī)到新一任的Leader出現(xiàn)這段時(shí)間列入統(tǒng)計(jì)。在測試數(shù)據(jù)同步性能時(shí)，實(shí)驗(yàn)以連續(xù)完成300次數(shù)據(jù)同步的耗時(shí)作為量化評價(jià)標(biāo)準(zhǔn)，記錄客戶端發(fā)出第1個(gè)請求到收到第300個(gè)請求的應(yīng)答時(shí)間間隔。

（4）在對可用性進(jìn)行考察時(shí)，由于故障情況無法窮舉，本實(shí)驗(yàn)將測試驗(yàn)證一些典型故障下的可用性表現(xiàn)，每個(gè)典型故障下進(jìn)行5次重復(fù)的定性實(shí)驗(yàn)。首先將故障情況大致分類為節(jié)點(diǎn)停機(jī)及恢復(fù)、網(wǎng)絡(luò)故障及恢復(fù)。

其中，節(jié)點(diǎn)停機(jī)及恢復(fù)包含：僅有一個(gè)節(jié)點(diǎn)停機(jī)、僅有一個(gè)節(jié)點(diǎn)停機(jī)且從停機(jī)中恢復(fù)、僅有兩個(gè)節(jié)點(diǎn)停機(jī)、僅有兩個(gè)節(jié)點(diǎn)停機(jī)且依次從停機(jī)中恢復(fù)。

網(wǎng)絡(luò)故障包含：僅有一個(gè)節(jié)點(diǎn)發(fā)生斷網(wǎng)、僅有一個(gè)節(jié)點(diǎn)發(fā)生斷網(wǎng)并從斷網(wǎng)故障中恢復(fù)、僅有兩個(gè)節(jié)點(diǎn)發(fā)生斷網(wǎng)、僅有兩個(gè)節(jié)點(diǎn)發(fā)生斷網(wǎng)且依次從斷網(wǎng)中恢復(fù)。

實(shí)驗(yàn)結(jié)果以分?jǐn)?shù)的形式來量化在某一故障下分布式系統(tǒng)的可用性。統(tǒng)計(jì)方式為：

能對外提供服務(wù)的情況數(shù)量/總情況數(shù)量×100

例如：基于本算法的兩節(jié)點(diǎn)分布式系統(tǒng)，在遭遇其中一個(gè)節(jié)點(diǎn)發(fā)生故障停機(jī)時(shí)包含3種情況：①Follower節(jié)點(diǎn)停機(jī)；②Leader節(jié)點(diǎn)停機(jī)且Follower節(jié)點(diǎn)數(shù)據(jù)與Leader節(jié)點(diǎn)一樣新；③Leader節(jié)點(diǎn)停機(jī)且Follower節(jié)點(diǎn)數(shù)據(jù)陳舊。其中，當(dāng)遭遇Leader節(jié)點(diǎn)停機(jī)且Follower節(jié)點(diǎn)數(shù)據(jù)陳舊時(shí)，基于本算法的兩節(jié)點(diǎn)分布式系統(tǒng)為了保證數(shù)據(jù)一致性，將停止對外提供服務(wù)。因此，可用性得分為：2/3×100=66.6。

4 實(shí)驗(yàn)結(jié)果分析

在完成驗(yàn)證Leader選舉正確性的實(shí)驗(yàn)之后得到如圖4所示的結(jié)果。

Fig.4 Thelength of time in each state of distributed systems圖4 分布式系統(tǒng)處于各個(gè)狀態(tài)下的時(shí)長

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

通過統(tǒng)計(jì)數(shù)據(jù)同步情況得到圖5中的統(tǒng)計(jì)數(shù)據(jù)。無論是Raft一致性協(xié)議還是本算法，數(shù)據(jù)同步的結(jié)果均沒有發(fā)生序號(hào)缺失、覆蓋、重復(fù)、前后顛倒等情況。因此，它們的數(shù)據(jù)不一致個(gè)數(shù)均為0。

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

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

圖7統(tǒng)計(jì)了連續(xù)完成300次數(shù)據(jù)同步的總耗時(shí)，用于檢驗(yàn)本算法中數(shù)據(jù)同步性能?；诒舅惴ǖ膬晒?jié)點(diǎn)分布式系統(tǒng)比基于Raft協(xié)議的兩節(jié)點(diǎn)分布式系統(tǒng)在數(shù)據(jù)同步性能上稍有差距。因?yàn)樵诔Ｒ?guī)的數(shù)據(jù)同步工作流程中，本算法需要得到來自Follower節(jié)點(diǎn)以及路由器節(jié)點(diǎn)的數(shù)據(jù)同步應(yīng)答才能完成數(shù)據(jù)提交。而基于Raft協(xié)議的兩節(jié)點(diǎn)分布式系統(tǒng)中，數(shù)據(jù)同步給另一個(gè)節(jié)點(diǎn)之后就能夠完成數(shù)據(jù)提交。此外，由于基于Raft協(xié)議的三節(jié)點(diǎn)分布式系統(tǒng)需要最終將數(shù)據(jù)同步給另外兩個(gè)節(jié)點(diǎn)，因此造成時(shí)間損耗較大。但總體而言，本算法在數(shù)據(jù)同步性能方面與Raft協(xié)議接近。

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

Fig.7 Time to complete 300 times data synchronizations圖7 完成300次數(shù)據(jù)同步的耗時(shí)

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

本算法的可用性接近于Raft協(xié)議。在一些嚴(yán)重的故障下，例如分布式系統(tǒng)中有兩個(gè)節(jié)點(diǎn)同時(shí)出現(xiàn)停機(jī)、斷網(wǎng)故障時(shí)，它們均停止對外提供服務(wù)。

當(dāng)分布式系統(tǒng)中一個(gè)節(jié)點(diǎn)出現(xiàn)故障，基于Raft協(xié)議的兩節(jié)點(diǎn)分布式系統(tǒng)將無法繼續(xù)提供服務(wù)，而基于本算法的兩節(jié)點(diǎn)分布式系統(tǒng)與基于Raft協(xié)議的三節(jié)點(diǎn)分布式系統(tǒng)依然能夠?qū)ν馓峁┓?wù)，只不過本算法為了保護(hù)數(shù)據(jù)一致性，在一些僅剩單個(gè)節(jié)點(diǎn)存活的情況下也將停止對外提供服務(wù)。

Fig.8 Availability test results of distributed system圖8 分布式系統(tǒng)可用性測試結(jié)果

5 結(jié)語

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

但是，本算法在性能、可用性以及對路由器過度依賴方面仍有進(jìn)一步提升空間。隨著路由器設(shè)備的可拓展性逐漸增強(qiáng)，后續(xù)可考慮將Raft協(xié)議簡化，讓路由器節(jié)點(diǎn)運(yùn)行Raft協(xié)議并記錄少量的關(guān)鍵信息，構(gòu)建由多個(gè)路由器與服務(wù)節(jié)點(diǎn)組成的異構(gòu)分布式系統(tǒng)。在不顯著增加成本的情況下具備與3個(gè)以上節(jié)點(diǎn)的分布式系統(tǒng)同樣優(yōu)秀的性能與可用性，同時(shí)避免因單個(gè)路由器故障造成的服務(wù)中斷。