馬博韜，倪 宏，朱小勇

(1.中國科學(xué)院聲學(xué)研究所國家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心,北京 100190; 2.中國科學(xué)院大學(xué),北京 100049)

0 引 言

作為一種易于理解的一致性協(xié)議，Raft算法于2013年由斯坦福大學(xué)的Diego Ongaro等在其論文《In Search of an Understandable Consensus Algorithm》[1]中首次提出。文中表示，由于現(xiàn)有的Paxos一致性協(xié)議實(shí)現(xiàn)機(jī)制復(fù)雜，原理晦澀[2]，需要設(shè)計(jì)一個(gè)足夠詳細(xì)并且易于實(shí)現(xiàn)的類似Paxos協(xié)議，以方便開發(fā)人員能在短期內(nèi)實(shí)現(xiàn)一套可用系統(tǒng)。

基于Raft一致性算法在設(shè)計(jì)之初便以易于實(shí)現(xiàn)、原理清晰等特點(diǎn)作為設(shè)計(jì)原則，短短幾年時(shí)間便已被廣泛應(yīng)用于各類分布式環(huán)境中。同時(shí)，作為Paxos協(xié)議的簡化版本，Raft算法犧牲了部分性能[3]，對于不同場景中的實(shí)際應(yīng)用，可根據(jù)場景特殊性對該算法作出某些方面的具體改進(jìn)。當(dāng)分布式系統(tǒng)中的管理節(jié)點(diǎn)因故障無法處理集群服務(wù)時(shí)，需要進(jìn)行管理節(jié)點(diǎn)的重新選舉，以恢復(fù)系統(tǒng)運(yùn)作。

在類似于邊緣計(jì)算的場景中，由于終端設(shè)備的不穩(wěn)定性，設(shè)備故障率相比于云端服務(wù)器故障率大幅提高，管理節(jié)點(diǎn)因故障發(fā)生重新選舉的可能性也將因此增加[4]。當(dāng)邊緣計(jì)算業(yè)務(wù)需要長時(shí)間工作時(shí)，不可避免會(huì)在工作周期內(nèi)因設(shè)備故障發(fā)生多次管理節(jié)點(diǎn)選舉。

Raft算法在設(shè)計(jì)選舉機(jī)制時(shí)，選擇在每個(gè)節(jié)點(diǎn)上設(shè)置隨機(jī)起始時(shí)間，以盡可能避免出現(xiàn)多個(gè)節(jié)點(diǎn)同時(shí)發(fā)起廣播競選。然而，由于競選信息在分布式環(huán)境傳輸過程中存在通信開銷，在此過程中可能存在其余從屬節(jié)點(diǎn)發(fā)起競選。此時(shí)若采用Raft一致性算法進(jìn)行選舉操作，將可能出現(xiàn)因備選節(jié)點(diǎn)選票瓜分而導(dǎo)致的多次超時(shí)選舉，影響分布式系統(tǒng)的可用性。優(yōu)化Raft一致性算法的選舉過程，意義在于減少選舉過程平均時(shí)間，降低出現(xiàn)選票瓜分導(dǎo)致超時(shí)選舉的可能性，避免出現(xiàn)多次超時(shí)選舉的極端情況，從而增加分布式系統(tǒng)的可用性。

本文設(shè)計(jì)的LC-Raft(Log_Calculation-Raft)一致性算法在原Raft算法基礎(chǔ)上，改進(jìn)原有選舉機(jī)制，在分布式系統(tǒng)中參與選舉所有節(jié)點(diǎn)之間的網(wǎng)絡(luò)通信無故障情況下，能夠?qū)崿F(xiàn)在最長一次超時(shí)時(shí)間內(nèi)選舉出新的管理節(jié)點(diǎn)，且管理節(jié)點(diǎn)具有更強(qiáng)的穩(wěn)定性。本文通過在選舉過程中增加基于歷史日志計(jì)算值的數(shù)值指標(biāo)，評價(jià)各個(gè)節(jié)點(diǎn)的穩(wěn)定性程度，以獲得具有更佳穩(wěn)定性的新管理節(jié)點(diǎn)(Leader)；同時(shí)，基于歷史日志計(jì)算值，修改選舉過程整體流程，避免出現(xiàn)多個(gè)Candidate節(jié)點(diǎn)瓜分選票，實(shí)現(xiàn)在一次計(jì)時(shí)器時(shí)間內(nèi)選舉出新的管理節(jié)點(diǎn)，增加系統(tǒng)可用性。在實(shí)驗(yàn)驗(yàn)證環(huán)節(jié)，通過Docker容器引擎方案，實(shí)現(xiàn)在一臺(tái)服務(wù)器上快速模擬出各種節(jié)點(diǎn)規(guī)模的實(shí)驗(yàn)環(huán)境。在此基礎(chǔ)上，通過多次實(shí)驗(yàn)驗(yàn)證各種節(jié)點(diǎn)規(guī)模的選舉過程，根據(jù)統(tǒng)計(jì)值驗(yàn)證分析LC-Raft一致性算法與原Raft一致性算法在選舉階段的耗時(shí)指標(biāo)。

1 改進(jìn)的LC-Raft一致性算法

1.1 適用條件

作為一種能在一次超時(shí)時(shí)間內(nèi)完成選舉的改良方案，LC-Raft一致性方案需要保證分布式系統(tǒng)中各節(jié)點(diǎn)網(wǎng)絡(luò)通信無故障。當(dāng)出現(xiàn)網(wǎng)絡(luò)分區(qū)(Network Partition)的情況時(shí)，小概率存在多個(gè)備選節(jié)點(diǎn)處于不同分區(qū)中的極端情況。在此情況下，此方案并不能實(shí)現(xiàn)分布式的可用性[5]。

1.2 節(jié)點(diǎn)狀態(tài)分析

與Raft一致性算法類似，LC-Raft一致性算法將節(jié)點(diǎn)狀態(tài)區(qū)分為3種狀態(tài)，分別為管理節(jié)點(diǎn)(Leader)、從屬節(jié)點(diǎn)(Follower)以及備選節(jié)點(diǎn)(Candidate)[6]。在分布式系統(tǒng)正常工作時(shí)，僅存在一個(gè)管理節(jié)點(diǎn)以及多個(gè)從屬節(jié)點(diǎn)，不存在備選節(jié)點(diǎn)，客戶端通過與管理節(jié)點(diǎn)通信進(jìn)行相應(yīng)的冪等操作。每個(gè)節(jié)點(diǎn)設(shè)置有固定的計(jì)時(shí)器時(shí)間，用于區(qū)分每個(gè)節(jié)點(diǎn)是否超時(shí)，當(dāng)從屬節(jié)點(diǎn)超過計(jì)時(shí)器時(shí)間未接收到來自管理節(jié)點(diǎn)的心跳信息時(shí)，則該從屬節(jié)點(diǎn)認(rèn)定管理節(jié)點(diǎn)出現(xiàn)故障，將宣布成為備選節(jié)點(diǎn)，通過增加任期，向其余節(jié)點(diǎn)廣播競選信息RequestVote RPC，從而得到其余節(jié)點(diǎn)的回復(fù)信息，當(dāng)在計(jì)時(shí)器時(shí)間內(nèi)接收到半數(shù)以上節(jié)點(diǎn)同意競選請求的回復(fù)時(shí)，備選節(jié)點(diǎn)將修改節(jié)點(diǎn)狀態(tài)為管理節(jié)點(diǎn)，成功競選。

與Raft算法不同之處在于，備選節(jié)點(diǎn)在超過計(jì)時(shí)器時(shí)間后，不再繼續(xù)保留備選節(jié)點(diǎn)狀態(tài)，轉(zhuǎn)而修改為管理節(jié)點(diǎn)狀態(tài)，具體原因?qū)⒃谙挛恼f明。與此同時(shí)，備選節(jié)點(diǎn)發(fā)現(xiàn)存在任期更大的節(jié)點(diǎn)時(shí)，將會(huì)放棄競選，恢復(fù)為從屬節(jié)點(diǎn)，并更新任期值為對方任期值。并且，當(dāng)管理節(jié)點(diǎn)發(fā)現(xiàn)存在更大任期值的節(jié)點(diǎn)時(shí)，將會(huì)放棄管理節(jié)點(diǎn)狀態(tài)，修改任期，變更為從屬節(jié)點(diǎn)。發(fā)生此狀態(tài)的原因一般存在2種：一種為管理節(jié)點(diǎn)長時(shí)間網(wǎng)絡(luò)故障，未與其余工作節(jié)點(diǎn)發(fā)生有效通信，其余節(jié)點(diǎn)因此已通過重新選舉重新構(gòu)建新的分布式系統(tǒng)，此時(shí)管理節(jié)點(diǎn)排除網(wǎng)絡(luò)故障，重新加入該分布式環(huán)境，因此需要重新變更為從屬節(jié)點(diǎn)；另一種情況為管理節(jié)點(diǎn)發(fā)送的心跳信息過大，并且心跳信息與超時(shí)時(shí)間比例不合理，從屬節(jié)點(diǎn)在未完全處理心跳信息時(shí)便已達(dá)到超時(shí)時(shí)間，發(fā)起管理節(jié)點(diǎn)競選。為了避免上述情況，應(yīng)合理預(yù)設(shè)心跳時(shí)間間隔與計(jì)時(shí)器時(shí)間之間的比例關(guān)系，一般而言，應(yīng)滿足心跳時(shí)間<<計(jì)時(shí)器時(shí)間[7]。圖1為LC-Raft算法狀態(tài)轉(zhuǎn)移圖。

圖1 LC-Raft算法狀態(tài)轉(zhuǎn)移圖

1.3 記錄節(jié)點(diǎn)物理時(shí)間日志

在Raft算法的設(shè)計(jì)機(jī)制中，并不考慮物理時(shí)間日志在競選管理節(jié)點(diǎn)的選舉階段及狀態(tài)機(jī)修改階段中的應(yīng)用，而是采用任期及索引作為邏輯時(shí)間加以判斷，這是由于各節(jié)點(diǎn)物理時(shí)間并不能達(dá)成完全一致[8]。在使用Raft一致性協(xié)議的分布式系統(tǒng)中，已達(dá)成一致性的日志項(xiàng)將由管理節(jié)點(diǎn)分發(fā)至每個(gè)從屬節(jié)點(diǎn)，并保存在日志列表中。日志項(xiàng)對應(yīng)的任期值不能進(jìn)行刪減，只能增加對應(yīng)同一任期值更大索引號的日志項(xiàng)或者更大任期值的日志項(xiàng)。因此，日志列表中保存的各日志項(xiàng)表示該節(jié)點(diǎn)在分布式環(huán)境中運(yùn)行期間的各類操作，由客戶端通過各任期內(nèi)管理節(jié)點(diǎn)將已達(dá)成共識(shí)的日志項(xiàng)通過AppendEntries RPC消息傳遞給各個(gè)從屬節(jié)點(diǎn)[8]，從而實(shí)現(xiàn)分布式系統(tǒng)中各個(gè)節(jié)點(diǎn)的最終一致性。

然而，上述日志列表中的日志項(xiàng)只包含有各日志的邏輯時(shí)間戳與狀態(tài)機(jī)對應(yīng)狀態(tài)值，并不能體現(xiàn)每個(gè)節(jié)點(diǎn)的穩(wěn)定性程度。對于穩(wěn)定性較差的節(jié)點(diǎn)，日志項(xiàng)參數(shù)并不會(huì)告知其余節(jié)點(diǎn)其經(jīng)歷的正常工作時(shí)間與異常響應(yīng)次數(shù)，在該節(jié)點(diǎn)故障排除后，通過與管理節(jié)點(diǎn)的心跳信息多次交互后，仍然能表現(xiàn)出與正常節(jié)點(diǎn)相同的日志列表與狀態(tài)機(jī)狀態(tài)。Raft算法中，在節(jié)點(diǎn)進(jìn)行管理節(jié)點(diǎn)選舉時(shí)，具有相同任期的不同備選節(jié)點(diǎn)根據(jù)其余節(jié)點(diǎn)的贊成投票次數(shù)來決定最后的管理節(jié)點(diǎn)，不僅可能出現(xiàn)因選票瓜分而導(dǎo)致的超時(shí)選舉，同時(shí)也可能出現(xiàn)選舉出的新管理節(jié)點(diǎn)在穩(wěn)定性程度上不能勝任工作的情況[9]。

因此，在原有選舉機(jī)制上，可以考慮加入基于節(jié)點(diǎn)歷史日志判斷穩(wěn)定性的方案，進(jìn)行備選節(jié)點(diǎn)的二次判決。一方面可以避免多個(gè)備選節(jié)點(diǎn)瓜分選票導(dǎo)致選舉超時(shí)，另一方面也可排除所有穩(wěn)定性較差的備選節(jié)點(diǎn)，增強(qiáng)分布式系統(tǒng)的魯棒性。

1.4 歷史日志計(jì)算值

本節(jié)在原有Raft一致性算法的選舉機(jī)制上，增加每個(gè)節(jié)點(diǎn)在固定物理時(shí)間范圍的異常日志統(tǒng)計(jì)，通過事件ID統(tǒng)計(jì)在此時(shí)段內(nèi)的典型異常響應(yīng)次數(shù)，以及節(jié)點(diǎn)正常工作時(shí)間等參數(shù)，作為選舉管理節(jié)點(diǎn)的附加評價(jià)指標(biāo)。從設(shè)計(jì)目的出發(fā)，主要存在2個(gè)考量因素：

1)避免出現(xiàn)管理節(jié)點(diǎn)選舉階段多個(gè)備選節(jié)點(diǎn)瓜分選票，造成超時(shí)選舉。

2)確保新選舉出的管理節(jié)點(diǎn)是所有備選節(jié)點(diǎn)中穩(wěn)定性最好的節(jié)點(diǎn)設(shè)備，減少新的分布式系統(tǒng)管理節(jié)點(diǎn)發(fā)生故障概率。

對于在分布式系統(tǒng)中穩(wěn)定運(yùn)行時(shí)間更長的節(jié)點(diǎn)，傾向于認(rèn)為該節(jié)點(diǎn)狀態(tài)更加穩(wěn)定，出現(xiàn)故障或下線的概率更低。尤其在本文需要考慮的邊緣計(jì)算場景，各終端設(shè)備的穩(wěn)定性遠(yuǎn)不如云端服務(wù)器，在節(jié)點(diǎn)可用閑置資源量相差不大的情況下，管理節(jié)點(diǎn)的穩(wěn)定性往往需要作為選舉階段的重要參考指標(biāo)。

在實(shí)施方案中，本節(jié)對位于分布式系統(tǒng)中的各個(gè)節(jié)點(diǎn)定時(shí)設(shè)置統(tǒng)一物理時(shí)間戳，用于計(jì)算最近2次物理時(shí)間戳之間的固定物理時(shí)間。對于每個(gè)節(jié)點(diǎn)在該時(shí)段內(nèi)日志的異常響應(yīng)事件ID進(jìn)行次數(shù)統(tǒng)計(jì)，在此基礎(chǔ)上，2次異常事件ID之間的正常運(yùn)行時(shí)間同樣也納入評價(jià)指標(biāo)。異常事件ID以黑名單方式存儲(chǔ)，對應(yīng)的所有異常事件都有相應(yīng)的恢復(fù)事件ID號，根據(jù)具體實(shí)驗(yàn)需求，添加需要加入的具體事件ID號。從屬節(jié)點(diǎn)在超時(shí)時(shí)間內(nèi)仍未接收到來自管理節(jié)點(diǎn)的心跳信息時(shí)，會(huì)將上述固定時(shí)段內(nèi)統(tǒng)計(jì)的日志信息按照公式(1)計(jì)算，并保存為歷史日志計(jì)算值。

(1)

其中，T表示2次物理時(shí)間戳之間的固定時(shí)間，M表示統(tǒng)計(jì)的異常事件總次數(shù)，K表示節(jié)點(diǎn)在該歷史時(shí)段內(nèi)的正常工作次數(shù)，ti表示節(jié)點(diǎn)每次正常工作的時(shí)間。計(jì)算所得值Log_Calculate作為評價(jià)節(jié)點(diǎn)穩(wěn)定性的數(shù)值指標(biāo)，介于[0,M]之間，數(shù)值越小，表示該節(jié)點(diǎn)在此時(shí)段內(nèi)的穩(wěn)定性越好，以無符號浮點(diǎn)數(shù)格式保存。

在從屬節(jié)點(diǎn)修改為備選節(jié)點(diǎn)后，需要將競選信息RequestVote RPC通過廣播發(fā)送至其余所有節(jié)點(diǎn)，上述計(jì)算的歷史日志計(jì)算值也將包含在其中，新的RequestVote RPC如表1所示。

表1 LC-Raft競選信息參數(shù)表

舉例說明，當(dāng)競選管理節(jié)點(diǎn)的選舉階段存在2個(gè)備選節(jié)點(diǎn)時(shí)，對于上述方案設(shè)置2次物理時(shí)間戳之間的固定時(shí)間為24 h，即8.64×107ms，節(jié)點(diǎn)A在此時(shí)間內(nèi)存在異常響應(yīng)28次，正常運(yùn)行時(shí)間為7.59×107ms；節(jié)點(diǎn)B存在異常響應(yīng)19次，正常運(yùn)行時(shí)間為5.41×107ms。根據(jù)公式(1)計(jì)算可知，Log_CalculateA≈3.40, Log_CalculateB≈7.10，節(jié)點(diǎn)A的歷史日志計(jì)算值小于節(jié)點(diǎn)B，由此判斷節(jié)點(diǎn)A穩(wěn)定性更優(yōu)于節(jié)點(diǎn)B。

1.5 選票瓜分解決方案

在原Raft算法中，每個(gè)從屬節(jié)點(diǎn)在回復(fù)心跳信息之后，會(huì)重置計(jì)時(shí)器時(shí)間，并隨機(jī)增加一段隨機(jī)時(shí)間，以避免多個(gè)從屬節(jié)點(diǎn)在未收到心跳信息時(shí)而達(dá)到超時(shí)時(shí)間[10]。當(dāng)?shù)谝粋€(gè)從屬節(jié)點(diǎn)在超時(shí)時(shí)間未收到心跳信息時(shí)，將修改節(jié)點(diǎn)狀態(tài)為備選節(jié)點(diǎn)，增加任期，并廣播競選信息RequestVote RPC。然而，由于節(jié)點(diǎn)之間存在通信開銷，存在一定概率使得另外的從屬節(jié)點(diǎn)在未收到上述競選信息時(shí)也達(dá)到超時(shí)時(shí)間[11]。當(dāng)上述情況出現(xiàn)時(shí)，每個(gè)備選節(jié)點(diǎn)臨近的從屬節(jié)點(diǎn)將會(huì)優(yōu)先接收到來自此備選節(jié)點(diǎn)的競選信息，從而在分布式系統(tǒng)中形成多個(gè)選票分區(qū)。Raft一致性算法規(guī)定，從屬節(jié)點(diǎn)只有收到超過半數(shù)以上節(jié)點(diǎn)的同意競選回復(fù)后才能成為新的管理節(jié)點(diǎn)，如果多個(gè)選票分區(qū)中所有分區(qū)均無法達(dá)到半數(shù)以上選票，則此次管理節(jié)點(diǎn)選舉失敗，所有節(jié)點(diǎn)將等待至超時(shí)時(shí)間后重新競選。

上述方案在極端情況下將出現(xiàn)多次超時(shí)選舉，盡管出現(xiàn)概率較小，但在終端資源池中，由于設(shè)備的不穩(wěn)定性，頻繁的重新選舉過程仍然需要從實(shí)現(xiàn)機(jī)制上避免上述情況發(fā)生[12]。在本節(jié)提出的方案中，分布式系統(tǒng)中的各個(gè)節(jié)點(diǎn)仍然設(shè)置有固定的計(jì)時(shí)器時(shí)間，當(dāng)超過該時(shí)間從屬節(jié)點(diǎn)未收到來自管理節(jié)點(diǎn)心跳信息時(shí)，節(jié)點(diǎn)將修改節(jié)點(diǎn)狀態(tài)為備選節(jié)點(diǎn)，任期增加，重置計(jì)時(shí)器時(shí)間，隨即增加一段起始時(shí)間，并廣播競選信息。與Raft算法可能出現(xiàn)的選票瓜分情況相似，本節(jié)方案中仍然有可能出現(xiàn)多個(gè)備選節(jié)點(diǎn)。不同之處在于，備選節(jié)點(diǎn)在接收到其余備選節(jié)點(diǎn)的競選信息時(shí)，將額外對比競選信息RequestVote RPC中以無符號浮點(diǎn)數(shù)保存的歷史日志計(jì)算值，根據(jù)值的大小，判定2個(gè)備選節(jié)點(diǎn)在分布式系統(tǒng)中的穩(wěn)定性程度。對于更加穩(wěn)定的備選節(jié)點(diǎn)，保留節(jié)點(diǎn)狀態(tài)，并繼續(xù)等待其余節(jié)點(diǎn)的回復(fù)信息；否則備選節(jié)點(diǎn)將修改自身狀態(tài)為從屬節(jié)點(diǎn)，放棄所有選票，重置計(jì)時(shí)器時(shí)間。在上述方案中，多個(gè)備選節(jié)點(diǎn)在對比來自系統(tǒng)其余備選節(jié)點(diǎn)的競選信息后，將只保留唯一一個(gè)備選節(jié)點(diǎn)，剩余的備選節(jié)點(diǎn)當(dāng)有超過半數(shù)從屬節(jié)點(diǎn)回復(fù)同意競選時(shí)，則成功競選為管理節(jié)點(diǎn)。當(dāng)剩余的備選節(jié)點(diǎn)未接收到半數(shù)設(shè)備的同意回復(fù)時(shí)，將繼續(xù)保留節(jié)點(diǎn)狀態(tài)直至達(dá)到超時(shí)時(shí)間，當(dāng)達(dá)到超時(shí)時(shí)間時(shí)，由于此時(shí)系統(tǒng)只存在唯一的備選節(jié)點(diǎn)，該節(jié)點(diǎn)將宣布成功競選為管理節(jié)點(diǎn)。

1.6 LC-Raft算法選舉管理節(jié)點(diǎn)流程

該算法在選舉管理節(jié)點(diǎn)階段的具體工作流程如圖2所示，各從屬節(jié)點(diǎn)通過日志項(xiàng)信息進(jìn)行日志列表的共識(shí)確認(rèn)及狀態(tài)機(jī)執(zhí)行，該日志項(xiàng)由管理節(jié)點(diǎn)每次發(fā)送的心跳信息AppendEntries RPC負(fù)責(zé)維護(hù)[13]。同時(shí)，心跳信息作為從屬節(jié)點(diǎn)判斷管理節(jié)點(diǎn)是否正常工作的判斷依據(jù)，當(dāng)超過計(jì)時(shí)器預(yù)先設(shè)置的計(jì)時(shí)器時(shí)間而未收到心跳信息，則從屬節(jié)點(diǎn)認(rèn)為管理節(jié)點(diǎn)出現(xiàn)故障，將修改自身狀態(tài)為備選節(jié)點(diǎn)，計(jì)算最近2次物理時(shí)間戳之間的歷史日志計(jì)算值，并增加任期號，廣播競選信息RequestVote RPC[14]。在廣播信息中LC-Raft一致性算法額外增加了以無符號浮點(diǎn)數(shù)格式保存的歷史日志計(jì)算值，該數(shù)值綜合計(jì)算了節(jié)點(diǎn)近期固定時(shí)段內(nèi)發(fā)生異常響應(yīng)次數(shù)以及正常運(yùn)行總時(shí)長。

圖2 LC-Raft一致性算法選舉過程工作流程圖

當(dāng)備選節(jié)點(diǎn)接收到其余從屬節(jié)點(diǎn)的回復(fù)信息時(shí)，需要對比兩者任期值，當(dāng)任期值小于對方時(shí)，備選節(jié)點(diǎn)將修改自身任期為對方任期，并清空投票，放棄競選，重置計(jì)時(shí)器時(shí)間，將節(jié)點(diǎn)狀態(tài)恢復(fù)為從屬節(jié)點(diǎn)；否則，當(dāng)回復(fù)信息為同意競選時(shí)，該備選節(jié)點(diǎn)會(huì)增加投票數(shù)，當(dāng)備選節(jié)點(diǎn)投票數(shù)超過半數(shù)節(jié)點(diǎn)數(shù)量時(shí)，則此次競選結(jié)束[15]，該備選節(jié)點(diǎn)成功成為管理節(jié)點(diǎn)，廣播心跳信息，表示此分布式系統(tǒng)結(jié)束重新選舉，并恢復(fù)工作[16]。如果備選節(jié)點(diǎn)接收到來自其余備選節(jié)點(diǎn)的廣播競選信息，將通過比對附加在競選信息中的Log_Calculate數(shù)值，以判斷2個(gè)節(jié)點(diǎn)的穩(wěn)定性程度，當(dāng)該備選節(jié)點(diǎn)穩(wěn)定性大于對方備選節(jié)點(diǎn)時(shí)，則保留備選節(jié)點(diǎn)狀態(tài)，反之將節(jié)點(diǎn)狀態(tài)修改為從屬節(jié)點(diǎn)，并清空投票數(shù)，同意對方節(jié)點(diǎn)競選。

經(jīng)過上述步驟，分布式環(huán)境將保留唯一的備選節(jié)點(diǎn)，若仍未在計(jì)時(shí)器時(shí)間內(nèi)收到半數(shù)以上選票，該備選節(jié)點(diǎn)達(dá)到超時(shí)時(shí)間后，將宣布成功競選為管理節(jié)點(diǎn)，并廣播心跳信息告知其余所有節(jié)點(diǎn)恢復(fù)正常工作狀態(tài)。

2 實(shí)驗(yàn)與分析

本章針對改進(jìn)的LC-Raft算法的選舉管理節(jié)點(diǎn)部分核心設(shè)計(jì)模塊加以實(shí)驗(yàn)論證。在實(shí)際運(yùn)行環(huán)境中，節(jié)點(diǎn)通信采用RPC方式實(shí)現(xiàn)，實(shí)驗(yàn)中繼續(xù)沿用原Raft算法中的Golang Channel方式實(shí)現(xiàn)RPC通信[17]。LC-Raft算法在遷移至運(yùn)行環(huán)境時(shí)，對外提供與原Raft算法一致的接口，運(yùn)行環(huán)境中其余模塊無需發(fā)生改變。

實(shí)驗(yàn)擬在不同節(jié)點(diǎn)規(guī)模的分布式系統(tǒng)中模擬因管理節(jié)點(diǎn)故障而進(jìn)行重新選舉的過程，分布式環(huán)境中節(jié)點(diǎn)規(guī)模從5個(gè)節(jié)點(diǎn)到80個(gè)節(jié)點(diǎn)遞增。在每個(gè)規(guī)模的選舉過程中，模擬出所有節(jié)點(diǎn)任期值不完全相同的場景，以增加實(shí)驗(yàn)的復(fù)雜性，從而更加貼合實(shí)際應(yīng)用環(huán)境。同時(shí)，為了避免實(shí)驗(yàn)偶然性，在每個(gè)節(jié)點(diǎn)規(guī)模中，改進(jìn)的LC-Raft算法與原Raft算法均重復(fù)對比實(shí)驗(yàn)500次，取統(tǒng)計(jì)值作為評價(jià)指標(biāo)，以增加實(shí)驗(yàn)可信度。

2.1 測試方案分析

為了驗(yàn)證上文提出的LC-Raft算法在重新競選管理節(jié)點(diǎn)部分的性能指標(biāo)，作以下方案設(shè)定：

1)以不同規(guī)模的物理節(jié)點(diǎn)作為測試節(jié)點(diǎn)進(jìn)行部署。為了驗(yàn)證該算法在不同節(jié)點(diǎn)規(guī)模的分布式環(huán)境中與原Raft算法的性能差異，可以采用對不同規(guī)模下各個(gè)節(jié)點(diǎn)設(shè)備的測試環(huán)境配置及統(tǒng)一調(diào)度的方案。然而，當(dāng)測試規(guī)模增大時(shí)，需要購買或租用大量的物理設(shè)備作為測試節(jié)點(diǎn)，并對每臺(tái)設(shè)備進(jìn)行測試環(huán)境配置，從操作復(fù)雜性角度及經(jīng)濟(jì)成本控制角度出發(fā)，此方案僅能在小規(guī)模分布式系統(tǒng)中進(jìn)行實(shí)驗(yàn)測試，具有一定的局限性[18]。

2)使用虛擬機(jī)模擬測試節(jié)點(diǎn)在少量服務(wù)器上進(jìn)行部署。此方案在一臺(tái)或多臺(tái)服務(wù)器上的硬件層面上實(shí)現(xiàn)虛擬化，通過在宿主機(jī)操作系統(tǒng)中運(yùn)行虛擬機(jī)操作系統(tǒng)，實(shí)現(xiàn)資源的隔離性，從而模擬出多個(gè)可用于驗(yàn)證算法性能的測試節(jié)點(diǎn)[19]。此方案相比于第1種方案而言，操作復(fù)雜性得到一定程度的降低，同時(shí)僅需少量設(shè)備即可實(shí)現(xiàn)。與此同時(shí)，虛擬機(jī)操作系統(tǒng)需要額外的CPU及內(nèi)存消耗，占用資源較大，無法大規(guī)模運(yùn)行在單臺(tái)服務(wù)器上[20]。此外，為了避免測試實(shí)驗(yàn)的偶然性，對于同一規(guī)模的性能測試需要重復(fù)多次后取統(tǒng)計(jì)值加以分析，虛擬機(jī)模擬的測試節(jié)點(diǎn)部署速度較慢，10 s左右的啟動(dòng)速度也成為限制該方案進(jìn)一步優(yōu)化的瓶頸所在。

3)使用容器技術(shù)模擬測試節(jié)點(diǎn)在單臺(tái)服務(wù)器上進(jìn)行部署。相比于虛擬機(jī)方案，基于Linux容器虛擬技術(shù)(Linux Container)的Docker輕量級虛擬化技術(shù)更加靈活輕便[21]。Docker容器能夠與宿主機(jī)共享操作系統(tǒng)，通過命名空間實(shí)現(xiàn)資源之間的隔離，構(gòu)造出多個(gè)類似“沙箱”的小規(guī)模環(huán)境，在運(yùn)行時(shí)幾乎無額外的性能損失，從而模擬出多個(gè)相互獨(dú)立的測試節(jié)點(diǎn)[22]。在此基礎(chǔ)上，該方案中單臺(tái)服務(wù)器具有以腳本方式秒級增刪數(shù)十臺(tái)容器的優(yōu)勢，在同一節(jié)點(diǎn)規(guī)模下，可以快速分析驗(yàn)證LC-Raft算法與Raft算法多次測試的統(tǒng)計(jì)值。

綜合上述方案分析，本節(jié)選用容器技術(shù)模擬LC-Raft算法與Raft算法在不同測試規(guī)模下的測試節(jié)點(diǎn)，實(shí)驗(yàn)中所有節(jié)點(diǎn)均以容器方式實(shí)現(xiàn)。為了簡化描述，下述節(jié)點(diǎn)與容器表述均為一致。具體實(shí)驗(yàn)參數(shù)列表如表2所示。

表2 實(shí)驗(yàn)環(huán)境配置參數(shù)

在單臺(tái)服務(wù)器中，通過Shell腳本指令及基礎(chǔ)鏡像，可以實(shí)現(xiàn)測試節(jié)點(diǎn)實(shí)驗(yàn)配置環(huán)境的批量部署。由于Docker自帶的Docker Swarm容器編排工具中使用源生的Raft算法作為分布式一致性工具[23]，且改進(jìn)的LC-Raft算法具有與原Raft算法一致的對外接口，實(shí)驗(yàn)中，通過修改Docker Swarm分別調(diào)用上述2個(gè)不同算法，實(shí)現(xiàn)LC-Raft算法與Raft算法在多個(gè)節(jié)點(diǎn)規(guī)模下的管理節(jié)點(diǎn)競選性能對比。

在基礎(chǔ)數(shù)值配置上，2種算法均設(shè)定管理節(jié)點(diǎn)的心跳時(shí)間為30 ms，初始所有節(jié)點(diǎn)任期值均設(shè)置為1，并且計(jì)時(shí)器時(shí)間為300 ms，從屬節(jié)點(diǎn)在超過該時(shí)間未接收到來自管理節(jié)點(diǎn)的心跳信息則認(rèn)定超時(shí)。經(jīng)過測試分析，備選節(jié)點(diǎn)在實(shí)驗(yàn)分布式環(huán)境中，發(fā)布競選信息RequestVote RPC到接收到從屬節(jié)點(diǎn)的回復(fù)信息，時(shí)間大致在18 ms～27 ms之間。

在服務(wù)器上部署的各個(gè)容器，穩(wěn)定性依賴于此服務(wù)器設(shè)備，在一定程度上并不能體現(xiàn)智能終端設(shè)備的不穩(wěn)定性。為了模擬出類似于終端設(shè)備的不穩(wěn)定程度，實(shí)驗(yàn)在每個(gè)容器初始化時(shí)通過腳本方式設(shè)置了不同的開關(guān)頻率。為了簡化實(shí)驗(yàn)流程，對于異常事件統(tǒng)計(jì)部分，只考慮由于容器關(guān)閉、重啟所導(dǎo)致的不穩(wěn)定性，并未模擬網(wǎng)絡(luò)故障、讀寫IO故障等情況。同時(shí)，為了保證實(shí)驗(yàn)的可操作性，在一定程度縮減了正常運(yùn)行時(shí)間、異常時(shí)間、統(tǒng)計(jì)周期的時(shí)間尺度，采用隨機(jī)時(shí)間腳本方式加以修改。其中設(shè)置每次運(yùn)行時(shí)間介于5 min～10 min之間，斷開時(shí)間介于10 s～20 s之間。例如，容器A第1次正常運(yùn)行時(shí)間為7.5 min，斷開后間隔12 s恢復(fù)運(yùn)行；第2次運(yùn)行時(shí)間8 min，在斷開后間隔10 s再一次正常運(yùn)行。相鄰物理時(shí)間戳之間設(shè)置為1 h的固定時(shí)段，統(tǒng)計(jì)最近時(shí)段內(nèi)每個(gè)容器的斷開次數(shù)以及運(yùn)行總時(shí)長，以此計(jì)算每個(gè)容器的Log_Calculate值。重復(fù)開關(guān)容器方式的目的在于對各容器設(shè)定不同的異常響應(yīng)次數(shù)及正常運(yùn)行時(shí)間，上述操作所計(jì)算出的對應(yīng)Log_Calculate值將作為后續(xù)各容器在選舉過程中的二次評價(jià)指標(biāo)。在計(jì)算結(jié)束后，不再對各容器進(jìn)行重復(fù)開關(guān)，使得各容器在選舉過程中正常運(yùn)行，避免因容器的頻繁上下線影響實(shí)驗(yàn)結(jié)果的有效性。

由于實(shí)驗(yàn)中需要設(shè)定所有節(jié)點(diǎn)任期不完全相同，以模擬出實(shí)際應(yīng)用場景中選舉階段的復(fù)雜性，本實(shí)驗(yàn)選用下述方案實(shí)現(xiàn)，具體由Shell腳本負(fù)責(zé)執(zhí)行操作：在由N個(gè)容器模擬的分布式環(huán)境中，在已初始化部署實(shí)現(xiàn)容器集群后，斷開管理節(jié)點(diǎn)與其余節(jié)點(diǎn)之間的網(wǎng)絡(luò)連接；同時(shí)對于其余從屬節(jié)點(diǎn)，斷開介于[0,N/2-1)之間隨機(jī)個(gè)數(shù)的容器網(wǎng)絡(luò)。在上述操作之后，仍保留網(wǎng)絡(luò)連接的剩余容器將進(jìn)行新一輪的管理節(jié)點(diǎn)競選，當(dāng)競選完成時(shí)，新的容器集群中所有容器節(jié)點(diǎn)任期均比斷開網(wǎng)絡(luò)連接的容器節(jié)點(diǎn)至少+1，從而確保N個(gè)容器節(jié)點(diǎn)任期不完全相同。在完成上述步驟后，斷開新的管理節(jié)點(diǎn)網(wǎng)絡(luò)，并重新恢復(fù)原來斷開網(wǎng)絡(luò)的所有容器網(wǎng)絡(luò)，從而模擬出不同任期的不同容器節(jié)點(diǎn)在管理節(jié)點(diǎn)故障時(shí)進(jìn)行的競選過程。該過程的操作流程如圖3所示。

圖3 固定節(jié)點(diǎn)情況下管理節(jié)點(diǎn)選舉耗時(shí)計(jì)算流程圖

根據(jù)上述方案，通過計(jì)算第i次結(jié)束時(shí)間減去第i次開始時(shí)間的值，可以得到在固定節(jié)點(diǎn)數(shù)情況下第i次選舉總耗時(shí)。根據(jù)算法機(jī)制分析，該數(shù)值取決于3個(gè)因素變量：節(jié)點(diǎn)超時(shí)時(shí)間t1、節(jié)點(diǎn)接收到心跳信息后的預(yù)設(shè)隨機(jī)時(shí)間值t2、節(jié)點(diǎn)從宣布競選到成功競選管理節(jié)點(diǎn)的耗時(shí)t3。關(guān)于t2部分的取值，本實(shí)驗(yàn)選擇t2為介于[0,100] ms之間的隨機(jī)數(shù)。

選舉總耗時(shí)T計(jì)算公式如公式(2)所示。其中，t1-t2為第1階段的計(jì)時(shí)，此時(shí)從屬節(jié)點(diǎn)在發(fā)出對上一條心跳信息回復(fù)之后，等待到超時(shí)時(shí)間仍未收到來自管理節(jié)點(diǎn)的心跳信息；t3為第2階段計(jì)時(shí)，此時(shí)從屬節(jié)點(diǎn)已達(dá)到超時(shí)時(shí)間，將節(jié)點(diǎn)狀態(tài)修改為備選節(jié)點(diǎn)，并廣播RequestVote RPC信息，直到宣布競選完成，成為新的管理節(jié)點(diǎn)。

T=t1-t2+t3

(2)

在對比實(shí)驗(yàn)中，選擇Raft作為對比算法，進(jìn)行選舉過程的時(shí)間指標(biāo)統(tǒng)計(jì)。由于本文提出的LC-Raft算法，主要針對原有Raft算法在選舉階段可能出現(xiàn)的超時(shí)情況加以改進(jìn)，在其余邏輯時(shí)間戳等方面未作變動(dòng)，并不會(huì)影響算法在集群正常運(yùn)行時(shí)心跳信息中的日志一致性，也不會(huì)影響后續(xù)狀態(tài)機(jī)讀寫性能。因此，本文考慮只在選舉過程的各個(gè)性能指標(biāo)上做出實(shí)驗(yàn)對比及數(shù)據(jù)分析。

實(shí)驗(yàn)中將按照上述耗時(shí)計(jì)算流程圖計(jì)算每次不同任期節(jié)點(diǎn)競選管理節(jié)點(diǎn)的用時(shí)開銷，并根據(jù)預(yù)設(shè)的循環(huán)次數(shù)重復(fù)多次，記錄下各個(gè)節(jié)點(diǎn)數(shù)情況下基于LC-Raft一致性算法或Raft一致性算法選舉耗時(shí)的統(tǒng)計(jì)值。由于實(shí)驗(yàn)?zāi)康闹饕谟隍?yàn)證改進(jìn)的LC-Raft算法在競選管理節(jié)點(diǎn)時(shí)是否能夠有效避免因選票瓜分導(dǎo)致的多次超時(shí)選舉，因此在每個(gè)固定節(jié)點(diǎn)數(shù)統(tǒng)計(jì)值分析中主要需要考慮以下3個(gè)參數(shù)：選舉最長耗時(shí)、選舉平均耗時(shí)、標(biāo)準(zhǔn)差。

其中，統(tǒng)計(jì)選舉最長耗時(shí)意義在于判斷2種算法應(yīng)對選票瓜分時(shí)最差將經(jīng)歷幾次超時(shí)選舉。由于t1為固定數(shù)值，t2為介于[0,t1]之間的隨機(jī)數(shù)值，對于統(tǒng)計(jì)值結(jié)果影響并不大，因此，LC-Raft算法與Raft算法在選舉耗時(shí)的性能對比上主要取決于節(jié)點(diǎn)從宣布競選到成功競選管理節(jié)點(diǎn)的耗時(shí)t3。t3數(shù)值的大小，具體反映了選舉是否經(jīng)歷了選票瓜分帶來的超時(shí)選舉。鑒于上述分析，選舉最長耗時(shí)可以反映出在固定節(jié)點(diǎn)次數(shù)情況下，2種算法應(yīng)對選票瓜分情況的能力。

2.2 實(shí)驗(yàn)數(shù)據(jù)分析

對于上述實(shí)驗(yàn)方案，對應(yīng)的統(tǒng)計(jì)結(jié)果如圖4～圖6所示，分別對應(yīng)為選舉最長耗時(shí)對比圖、選舉平均耗時(shí)對比圖及標(biāo)準(zhǔn)差值對比圖。

圖4 選舉最長耗時(shí)對比圖

圖5 選舉平均耗時(shí)對比圖

圖6 算法標(biāo)準(zhǔn)差值對比折線圖

由圖4可知，在最差情況下，Raft算法對應(yīng)的最長選舉總時(shí)長在大致情況下與分布式環(huán)境節(jié)點(diǎn)數(shù)量呈現(xiàn)正相關(guān)關(guān)系。盡管各個(gè)節(jié)點(diǎn)存在隨機(jī)的起始時(shí)間及統(tǒng)一的超時(shí)時(shí)間上限，在一定程度上能避免不同節(jié)點(diǎn)同時(shí)因達(dá)到超時(shí)時(shí)間而發(fā)起競選廣播，但由于備選節(jié)點(diǎn)在選舉階段廣播RequestVote RPC過程存在通信開銷，在最先發(fā)起競選的備選節(jié)點(diǎn)廣播信息未到達(dá)從屬節(jié)點(diǎn)時(shí)，其余從屬節(jié)點(diǎn)存在一定概率已達(dá)到超時(shí)時(shí)間，并再次發(fā)起廣播競選。當(dāng)對應(yīng)節(jié)點(diǎn)數(shù)增加時(shí)，統(tǒng)計(jì)結(jié)果中最長選舉總時(shí)長整體表現(xiàn)為增長趨勢，情況惡化程度增加。其中，當(dāng)節(jié)點(diǎn)數(shù)介于5～55之間時(shí)，由統(tǒng)計(jì)結(jié)果可知，最長選舉耗時(shí)在500次循環(huán)實(shí)驗(yàn)中最多經(jīng)歷了5次超時(shí)選舉，最少對應(yīng)2次超時(shí)選舉。當(dāng)節(jié)點(diǎn)數(shù)介于56～80時(shí)，最多經(jīng)歷6次超時(shí)選舉，最少經(jīng)歷4次超時(shí)選舉。

上述結(jié)果表明，原Raft一致性算法在競選管理節(jié)點(diǎn)機(jī)制上并不能完全避免超時(shí)選舉，存在一定概率會(huì)因?yàn)槎啻纬瑫r(shí)造成分布式環(huán)境選舉過程緩慢，改進(jìn)后的LC-Raft一致性算法在選舉階段能夠避免出現(xiàn)因選票瓜分導(dǎo)致的多次超時(shí)選舉，有效實(shí)現(xiàn)在最多一次超時(shí)時(shí)間內(nèi)完成分布式系統(tǒng)的恢復(fù)，重新選舉出新的管理節(jié)點(diǎn)。

在統(tǒng)計(jì)各個(gè)節(jié)點(diǎn)規(guī)模分布式環(huán)境下，選用2種一致性算法進(jìn)行選舉的平均耗時(shí)狀態(tài)如圖5所示?？梢姰?dāng)節(jié)點(diǎn)數(shù)量增加時(shí)，采用Raft算法及LC-Raft算法均不可避免地會(huì)呈現(xiàn)出選舉耗時(shí)均值增加的情況，表明節(jié)點(diǎn)數(shù)量增加會(huì)惡化一致性算法在管理節(jié)點(diǎn)選舉過程的表現(xiàn)能力。同時(shí)，由曲線可知，改進(jìn)后的LC-Raft算法在選舉平均耗時(shí)均值增長斜率較Raft算法更加平緩，除去5～10個(gè)節(jié)點(diǎn)規(guī)模中個(gè)別情況均值表現(xiàn)較Raft算法更差之外，整體均值表現(xiàn)均優(yōu)于原Raft算法。表明LC-Raft一致性算法在平均情況下，選舉耗時(shí)開銷普遍小于原Raft一致性算法。

圖6為2種算法在各個(gè)節(jié)點(diǎn)規(guī)模下的標(biāo)準(zhǔn)差值對比折線圖，標(biāo)準(zhǔn)差的大小表明在某個(gè)節(jié)點(diǎn)規(guī)模下，2種一致性算法在選舉過程耗時(shí)的穩(wěn)定程度。由圖6可知，LC-Raft算法與Raft算法隨著節(jié)點(diǎn)數(shù)量增加，選舉耗時(shí)的不穩(wěn)定程度呈現(xiàn)增加的趨勢，同時(shí)，由于圖中Raft對應(yīng)數(shù)值在大部分情況下均大于LC-Raft算法對應(yīng)數(shù)值，表明改進(jìn)的LC-Raft一致性算法的穩(wěn)定性在節(jié)點(diǎn)規(guī)模為11～80之間時(shí)，均優(yōu)于原Raft一致性算法。

本實(shí)驗(yàn)通過在各個(gè)節(jié)點(diǎn)規(guī)模的多次循環(huán)實(shí)驗(yàn)，對改進(jìn)的LC-Raft一致性算法及原Raft一致性算法在選舉階段的耗時(shí)性能方面做了相應(yīng)統(tǒng)計(jì)驗(yàn)證，結(jié)論如下：

1)改進(jìn)后的LC-Raft一致性算法在選舉階段能夠避免由于選票瓜分而引起的多次超時(shí)選舉，有效實(shí)現(xiàn)了在最多一次超時(shí)時(shí)間內(nèi)完成分布式系統(tǒng)的恢復(fù)，重新選舉出新的管理節(jié)點(diǎn)。

2)LC-Raft一致性算法在同樣節(jié)點(diǎn)規(guī)模情況下，大部分選舉耗時(shí)均值少于原Raft算法，體現(xiàn)了該算法在選舉階段的可用性。

3)在穩(wěn)定性方面，LC-Raft一致性算法的選舉耗時(shí)較原Raft算法更加穩(wěn)定，出現(xiàn)極端情況較少，不存在因多次選票瓜分導(dǎo)致的多次超時(shí)選舉過程。

3 結(jié)束語

本文實(shí)現(xiàn)了一種基于歷史日志計(jì)算值的改進(jìn)一致性算法LC-Raft，在分布式系統(tǒng)的重新選舉階段，能夠?qū)崿F(xiàn)在短時(shí)間內(nèi)實(shí)現(xiàn)推舉出具有較好穩(wěn)定性的管理節(jié)點(diǎn)，同時(shí)避免出現(xiàn)多次超時(shí)選舉的極端情況。并且基于Docker容器引擎，設(shè)計(jì)了一套在單臺(tái)服務(wù)器上模擬實(shí)現(xiàn)各種節(jié)點(diǎn)規(guī)模選舉過程的實(shí)驗(yàn)環(huán)境，通過多次實(shí)驗(yàn)統(tǒng)計(jì)值驗(yàn)證了本算法在選舉過程中的良好性能，具有一定的實(shí)際應(yīng)用價(jià)值。