陳 陸,黃樹成*，徐克輝

(1.江蘇科技大學 計算機學院,鎮(zhèn)江 212003)(2.中國船舶重工集團有限公司 第七二四研究所，南京 211153)

分布式領(lǐng)域中的一致性[1]、可用性和分區(qū)容錯性理論(consistency,availability,partition tolerance,CAP)告訴我們,任何一個分布式系統(tǒng)都無法同時滿足一致性、可用性和分區(qū)容錯性這3個基本需求，最多只能滿足其中兩項．但是,一個分布式系統(tǒng)無論在CAP三者之間如何權(quán)衡,都無法徹底放棄一致性,如果真的放棄一致性,那么就說明這個系統(tǒng)中的數(shù)據(jù)根本不可信,數(shù)據(jù)也就沒有意義,那么這個系統(tǒng)也就沒有任何價值可言．

一致性問題指多個服務(wù)器在狀態(tài)上達成一致.但是在一個分布式系統(tǒng)中,因為各種意外,有的服務(wù)器可能會崩潰或變得不可靠,它就不能和其他服務(wù)器達成一致狀態(tài)．這樣就需要一種一致性協(xié)議.一致性協(xié)議是為了確保容錯性,也就是即使系統(tǒng)中有一兩個服務(wù)器宕機,也不會影響其處理過程．過去,Paxos一直是分布式一致性協(xié)議的標準,但是Paxos難于理解,更難以實現(xiàn),Google的分布式鎖系統(tǒng)Chubby[2]作為Paxos的實現(xiàn)，曾經(jīng)出現(xiàn)很多問題．

Raft是由斯坦福大學的文獻[3]中提出的一種基于復制狀態(tài)機的分布式一致性算法．Raft算法在沒有對Paxos的性能和精確度作讓步的情況下,擴大了應(yīng)用場景并且比Paxos更易于理解．

文中基于文獻[3]中關(guān)于Raft的性能分析實驗,將Raft算法部署在由5臺虛擬機組成的集群上,在應(yīng)用Raft一致性的集群上的實驗結(jié)果表明:文中提出的事務(wù)磁盤持久化、網(wǎng)絡(luò)日志同步，與傳統(tǒng)的Raft相比,在頻繁更新日志信息條目的情況下獲得了良好的效果．此外,較傳統(tǒng)的Raft而言,優(yōu)化過的Raft極大程度降低了讀寫磁盤的頻率,進而提高了Raft算法的效率．

1 相關(guān)研究

分布式系統(tǒng)的一致性框架是以復制狀態(tài)機為原型搭建的(圖1).

圖1 復制狀態(tài)機部件Fig.1 Components of the replicated state machine

復制狀態(tài)機的原型由狀態(tài)機(支持容錯功能)、日志存儲模塊、一致性模塊3部分組成．當前最流行的開源分布式一致性應(yīng)用程序ZooKeeper和被應(yīng)用于Google FileSystem和 BigTable的支持容錯恢復的分布式鎖服務(wù)Chubby都基于此而實現(xiàn)．

保證復制日志相同是一致性算法的工作．在一臺處于Leader角色的服務(wù)器上,一致性模塊接收客戶端發(fā)送來的指令，然后增加到自己的日志中．它和其他服務(wù)器上的一致性模塊進行通信來保證每一個服務(wù)器上的日志最終都以相同的順序包含相同的指令,盡管有些服務(wù)器會宕機．一旦指令被正確復制,每一個服務(wù)器的狀態(tài)機按照日志順序處理他們,然后輸出結(jié)果被返回給客戶端．因此,服務(wù)器集群看起來形成一個高可靠的狀態(tài)機．

2 改進的Raft算法

2.1 算法假設(shè)

Raft算法成立的前提條件和Multi-Paxos[4-6]一樣,其基本假設(shè):

(1) 分布式系統(tǒng)是異步的,例如,消息傳遞的延遲時間沒有上界或者執(zhí)行計算的時間也沒有限制．我們不能假設(shè)此分布式系統(tǒng)是時鐘同步的．

(2) 集群中節(jié)點間的網(wǎng)絡(luò)通信是不可靠的,包括網(wǎng)絡(luò)延遲、數(shù)據(jù)包丟失等情況．

(3) 不能發(fā)生拜占庭錯誤．

(4) 客戶端的應(yīng)用程序只能和集群中的Leader節(jié)點交互,并且一個集群中的Leader節(jié)點是通過集群自身的選舉算法選舉出來的．

(5) 集群中的每一個節(jié)點都有一個單調(diào)遞增的紀元值(term)．

(6) 運行在每一個節(jié)點上的狀態(tài)機初始狀態(tài)都相同,并且根據(jù)客戶端的操作準確返回交互信息．

2.2 Leader選舉

集群中的Leader節(jié)點每隔Timeout時間就會向Follower發(fā)送空的心跳包,如果Timeout時間內(nèi),Leader收到了Follower的心跳包的回復,那么它就會始終保持Follower狀態(tài)．如果節(jié)點在Timeout時間之內(nèi)沒有收到來自Leader節(jié)點的心跳包,它就會認為集群中的Leader節(jié)點出現(xiàn)了故障,那么處于Follower狀態(tài)的節(jié)點就會升級成Candidate．

一旦一個節(jié)點的狀態(tài)從Follower變成Candidate,該節(jié)點的紀元值就會在原來的基礎(chǔ)上加1,發(fā)起選舉,圖2是一個用非確定型有窮自動機表示的Raft算法中各節(jié)點的狀態(tài)轉(zhuǎn)換圖．

通常這樣的一組進程Π={P1,P2,P3,…,PN} 組成的分布式系統(tǒng)中,其每一個進程都存在于各自的節(jié)點上,各進程節(jié)點之間通過互相通信來實現(xiàn)消息傳遞,每一個進程都有可能因一次或者多次的進程崩潰而退出,這些進程也會在恢復原來狀態(tài)之后重新加入到Π中,當進程Px(1≤x≤N)收到Π中大部分的節(jié)點發(fā)送的Request Vote數(shù)據(jù)包,該進程所在的節(jié)點當選為Leader節(jié)點,我們將投票的節(jié)點子集稱為Quorum，文中用Q表示,并且其滿足:

∧ ?Q,Q?Π

∧ ?Q1和Q2,Q1∩Q2 ≠φ

其中Q1和Q2 為Π中的任意兩個子集．

如圖2,選舉的結(jié)果會有兩種可能性．① 某節(jié)點收到了集群中大多數(shù)節(jié)點的Request Vote數(shù)據(jù)包,該節(jié)點贏得此次選舉,從Candidate狀態(tài)升級為Leader；② 集群中沒有一個節(jié)點收到集群中的大多數(shù)節(jié)點的Request Vote,因此,該集群重新發(fā)起一次選舉．

圖2 Raft算法狀態(tài)轉(zhuǎn)換模型Fig.2 State transition model for Raft algorithm

2.3 改進算法的策略

既然當一個節(jié)點已經(jīng)被選舉為該集群中的Leader,那么它就能為復制狀態(tài)機處理來自客戶端的事務(wù)請求,客戶端通過指令來和Leader節(jié)點交互,Leader把客戶端的指令都提交到復制狀態(tài)機中．Leader節(jié)點把每一條接收到的指令加上索引,保存到自己日志當中．Leader節(jié)點將收到的這條指令拷貝到為該節(jié)點投票的集群中的大多數(shù)節(jié)點中,保存到各節(jié)點的日志中,然后提交執(zhí)行[7]．

如圖3,當Leader節(jié)點,即節(jié)點1的一致性模塊收到了y←9這條指令,節(jié)點1首先將它復制到自身日志中,然后通過RPC,以Append Entries Request數(shù)據(jù)包的形式發(fā)送到處于Follower狀態(tài)的節(jié)點2和節(jié)點3中,假設(shè)不會發(fā)生任何異常,節(jié)點2和3將這條指令復制到自身的日志中,并且返回SUCCESS給節(jié)點1．節(jié)點1收到SUCCESS后,將該條指令條目提交,并且向節(jié)點2和節(jié)點3發(fā)送Commit,節(jié)點2和節(jié)點3提交指令,最終集群中的節(jié)點狀態(tài)達到一致．

圖3 日志提交的簡單示例Fig.3 Simple example of log submission

當有數(shù)據(jù)時,Leader向Follower不斷發(fā)出Append Entries Request數(shù)據(jù)包,每個Append Entries Request可以包含多個日志條目,每個Append Entries Request被正常處理后，F(xiàn)ollower都會發(fā)回一個Append Entries Response.為了簡單起見,Leader在超時未收到Append Entries Response的情況，不會發(fā)出下一個Append Entries Request,此時即使Leader有比上次發(fā)出的Append Entries Request所包含的最后一個日志條目更加新的日志條目,也要等到收到Append Entries Response后才開始同步．在這種單步的日志同步方式下,網(wǎng)絡(luò)的延時越長,就對Leader節(jié)點同步提交的吞吐量的影響越大．

基于TCP協(xié)議中的滑動窗和長肥管道機制中,窗口相當于一個緩沖,TCP傳輸報文要求每個都有確認．在實際傳輸數(shù)據(jù)的時候不可能每個報文發(fā)送后就立即收到確認,如果每發(fā)送一次報文就等待確認,會導致傳輸速率變慢,所以TCP允許在沒收到上一個確認前發(fā)送下N個報文,但是發(fā)送報文不能超過窗口大小.如果窗口設(shè)置較小,而此時又處于長肥網(wǎng)絡(luò)當中,就會導致有些響應(yīng)報文還未到達發(fā)送端時,發(fā)送端就已經(jīng)達到窗口大小,這時發(fā)送端就必須重新發(fā)送之前的報文(而實際上只是接收端的響應(yīng)未到達發(fā)送端),這樣就會導致報文有大量重傳,疊加效應(yīng)就會導致傳輸速度遠低于帶寬(被無用的重傳占用了).相反,窗口足夠大,發(fā)送端連續(xù)發(fā)送的N個報文都能在窗口內(nèi)收到響應(yīng),不會有數(shù)據(jù)重傳,理論上的傳輸速度就會等于帶寬值．

根據(jù)此理論，可以將同步方式改進為:如果連續(xù)多次發(fā)送的Append Entries Request數(shù)據(jù)包都及時收到了Follower節(jié)點的回復,那么則認為網(wǎng)絡(luò)連接是通暢的,就可以改同步單條的提交模式為異步多條．此時Leader將多個Append Entries Request先后發(fā)出,然后統(tǒng)一等待回包．采用這種方式可以提高日志同步的吞吐量,但卻增加了實現(xiàn)的復雜度,要增加兩個模式的跳轉(zhuǎn),異步模式時的回包亂序,重放處理等．

出于持久化的目的,提交到復制狀態(tài)機的日志條目都會寫進磁盤,因此每次提交日志都需要讀寫一次磁盤,大大降低了效率．因此,在類UNIX系統(tǒng)平臺上,一般通過將數(shù)據(jù)寫入內(nèi)存后調(diào)用Fsync來使日志從內(nèi)存保存到磁盤．服務(wù)器使用的機械盤每秒進行讀寫操作的次數(shù)(inpnt/output operations per second,IOPS)只有300～400次，而固態(tài)硬盤SSD的IOPS有幾千次,如果每次將一條日志條目寫入磁盤就調(diào)用一次fsync,那么每秒的寫吞吐量只有對應(yīng)的IOPS,是相當?shù)偷模绻麑sync操作的時延平攤到多個日志條目,也就是采用批量寫入磁盤加上fsync的方式,則可以提高每秒吞吐量．若將進行fsync寫的每批日志條目數(shù)定義為M,將每秒最多可以完成的fsync寫操作的次數(shù)定義為N,那么吞吐量IOPS為M×N.IOPS值對于M的變化曲線是一個類似倒U型曲線，如圖4.經(jīng)測試,對于固態(tài)硬盤,當M=2 000,N=300的時候曲線到達高點,此時的吞吐量約為600 000,此后,隨著數(shù)據(jù)包內(nèi)的日志條目的增加,IOPS值會隨之減?。捎眠@種方法可以提高當有事務(wù)操作時磁盤的吞吐量,但卻增加了日志條目的寫平均延時．

圖4 IPOS值變化曲線Fig.4 Changeing curve of IPOS values

3 實驗及性能分析

實驗的運行環(huán)境如下:3臺虛擬機內(nèi)存為4GB, CPU 為Intel Core i3-2310M 2.39 GHz,2臺虛擬機內(nèi)存為4GB, CPU 為Intel Core i3-2310M 2.39 GHz,5臺虛擬機在同一網(wǎng)段內(nèi),操作系統(tǒng)為Ubuntu 14.04,IDE為LiteIDE,使用編程語言為Golang．

為了評估文中提出的改進的Raft算法的有效性,從3個方面對改進前后的算法進行對比分析:① 測試在600 ms和900 ms內(nèi),當集群中的Leader節(jié)點出現(xiàn)錯誤,未能在Timeout時間內(nèi)對Follower節(jié)點發(fā)送Append Entries Response數(shù)據(jù)包,集群中重新選舉出新 Leader節(jié)點的成功的概率；② 當集群中出現(xiàn)2臺虛擬機(非Leader節(jié)點且小于半數(shù)的機器)宕機時[8],集群能恢復對外服務(wù)所需要的時間；③ 當集群中出現(xiàn)節(jié)點移動、網(wǎng)絡(luò)稀疏或信號衰減等各種原因常常導致網(wǎng)絡(luò)連接中斷和網(wǎng)絡(luò)分割(network partition),此時出現(xiàn)2個或多個Leader,當網(wǎng)絡(luò)連接恢復后,集群恢復正常狀態(tài)所需的時間．

表1、2為根據(jù)Follower狀態(tài)節(jié)點Timeout值，不同算法在一定時間內(nèi)選舉出Leader節(jié)點的成功概率．實驗結(jié)果表明,改進Raft算法顯著縮短了集群中選舉出Leader節(jié)點的時間,進而提高了效率．

表1 原始Raft算法和改進后Raft算法在600 ms內(nèi)不同的Timeout下選出Leader節(jié)點的成功率Table 1 Success rates of selecting Leader node in 600 ms of Timeout of initial and improved Raft algorithm %

表2 原始Raft算法和改進后Raft算法在900 ms內(nèi)不同的Timeout下選出Leader節(jié)點的成功率Table 2 Success rates of selecting Leader node in 900 ms of Timeout of initial and improved Raft algorithm %

設(shè)定了5組實驗,實驗中每次都使集群中的相同的兩臺虛擬機宕機,然后測試集群繼續(xù)恢復對外服務(wù)所需的時間．

圖5 在小部分節(jié)點發(fā)生故障的情況下,集群恢復服務(wù)所需的時間Fig.5 Time required for the cluster to restore the service in the case of minority of nodes failure

從圖5可以看出,優(yōu)化過的Raft恢復的時間要明顯少于未優(yōu)化過的算法版本．

在實際應(yīng)用的大型分布式系統(tǒng)中,多個集群會不在同一地域內(nèi),但仍然對外提供相同的服務(wù)[9]．因此,在虛擬機集群中模擬了出現(xiàn)網(wǎng)絡(luò)分區(qū)故障的情況,同樣設(shè)定了5組實驗,每次使相同的兩臺機器出現(xiàn)分區(qū),然后再恢復網(wǎng)絡(luò)連接,從而測出恢復對外服務(wù)的時間(圖6)．

圖6 在出現(xiàn)網(wǎng)絡(luò)分區(qū)故障的情況下集群恢復服務(wù)所需的時間Fig.6 Time required for the cluster to restore the service in the case of network partition failure

4 結(jié)論

文中對解決分布式系統(tǒng)中的一致性問題的Raft算法進行了探討.在傳統(tǒng)的Raft算法中,由于需要保證日志條目不會因為節(jié)點中進程崩潰而消失,因此需要將條目不停地保存到磁盤中,并且傳統(tǒng)的Raft算法每次收到一個條目便寫一次磁盤,大大耗費了時間．并且,Leader節(jié)點只有在正常確認發(fā)送給每一個Follower節(jié)點的Append Entries Request得到正?；貜筒艜^續(xù)地工作,這會導致一旦某個節(jié)點異常,集群中的leader節(jié)點始終無法發(fā)送下一條指令．為了緩解不足,文中針對上述問題提出了優(yōu)化方法．實驗結(jié)果表明,文中提出的寫磁盤持久化和日志的網(wǎng)絡(luò)同步能夠在保持算法準確運行的同時,提升算法的效率．