基于Paxos的強一致性復(fù)制在天文數(shù)據(jù)存儲中的應(yīng)用研究*

童 彬， 王 鋒， 劉應(yīng)波，2， 張 帆

(1.昆明理工大學云南省計算機技術(shù)應(yīng)用重點實驗室，云南昆明 650500；2.云南省科學技術(shù)情報研究院，云南昆明 650051)

近幾年來，我國天文觀測設(shè)備的研制取得了較大的進展。以太陽觀測為例，1 m新真空太陽望遠鏡(New Vacuum Solar Telescope，NVST)和光學/近紅外太陽爆發(fā)探測儀(Optical and Near-Infrared Solar Eruption Tracer，ONSET)望遠鏡已經(jīng)相繼投入觀測。其中，1 m太陽望遠鏡主要是通過焦面設(shè)備采集獲取太陽光球和色球的高分辨率圖像。圖像用天文普適圖像傳輸系統(tǒng)(Flexible Image Transport System，F(xiàn)ITS)格式保存。以其中一個焦面設(shè)備的CCD(分辨率2 048×2 048)為例，每個像素存儲時使用16位編碼，則編碼后文件大小為8 MB。若要求設(shè)備每秒采集10幀，則采集速率為80 MB/s。當4個焦面設(shè)備同時采集時，采集數(shù)據(jù)的峰值可達320 MB/s。按平均日觀測時間7.5小時計算，每天觀測數(shù)據(jù)量達到8.24 TB。

為確保這些海量科學觀測資源的存儲，傳統(tǒng)方法采用直接附加存儲、網(wǎng)絡(luò)附加存儲或存儲區(qū)域網(wǎng)絡(luò)技術(shù)，通過廉價磁盤冗余陣列提高數(shù)據(jù)的安全性，但在實際應(yīng)用中會受到諸如無法實時擴充空間、存儲速度受限于總線、多機共享困難等問題的困擾。近幾年，分布式存儲系統(tǒng)領(lǐng)域出現(xiàn)了基于廉價硬件分布式存儲的系統(tǒng)構(gòu)架方法，在有效控制成本的前提下可靠地保存超過PB級總量的數(shù)據(jù)且具有良好的訪問性能，為海量天文數(shù)據(jù)的存儲帶來了新的思路[1-2]。

在天文觀測系統(tǒng)中，采集工作站負責將焦面探測設(shè)備(如CCD)生成的數(shù)據(jù)提交至存儲系統(tǒng)。原始觀測圖像一般先緩存在工作站有限的內(nèi)存中，編碼后再盡快提交至存儲系統(tǒng)，以免造成內(nèi)存的溢出。外掛式存儲通常由硬件機制保證數(shù)據(jù)的安全性，可靠性較高；而組成分布式存儲系統(tǒng)的廉價存儲節(jié)點平均失效率為0.034%[3]，數(shù)據(jù)安全性能和數(shù)據(jù)恢復(fù)手段均比外掛式存儲設(shè)備復(fù)雜。為了彌補存儲節(jié)點數(shù)據(jù)安全性的不足，只能通過復(fù)制手段把數(shù)據(jù)拷貝至多個節(jié)點中以確保存儲數(shù)據(jù)的安全性，而組成分布式存儲系統(tǒng)的硬件并不具有保證所有復(fù)制過程無差錯的數(shù)據(jù)復(fù)制，因此每當復(fù)制操作執(zhí)行之后還需確認所有拷貝的存儲狀態(tài)。只有當所有參與復(fù)制的節(jié)點均完成數(shù)據(jù)持久化存儲后才能確保最低的數(shù)據(jù)丟失概率，進而使得工作站達到確認存儲完成并安全釋放內(nèi)存的條件。為滿足釋放條件，復(fù)制操作必須具有確定數(shù)據(jù)達成一致性的能力。

復(fù)制操作過程中數(shù)據(jù)的多份冗余存儲在有效提高數(shù)據(jù)安全性的同時，不可避免地增加了“確定存儲狀態(tài)”的復(fù)雜度?；谝蕴W(wǎng)構(gòu)建的分布式存儲系統(tǒng)存在消息丟失和復(fù)制兩種異常，在此條件下容忍分布式存儲中的所有錯誤并達成一致性結(jié)果至少需要三輪信息交換。如何在分布式天文數(shù)據(jù)的存儲過程中，在保障觀測數(shù)據(jù)復(fù)制成功的同時，能夠讓復(fù)制的數(shù)據(jù)副本一致是需要重點研究的問題。

1 相關(guān)工作

軟件復(fù)制過程中的一致性相關(guān)算法一直以來都是該領(lǐng)域研究的熱點和難點。復(fù)制算法可分為事務(wù)復(fù)制、虛同步復(fù)制以及狀態(tài)機復(fù)制3種，事務(wù)復(fù)制方法的普適步驟是先復(fù)制，后同步，其同步(一致性達成)的方式選擇靈活，可以獲得最強的容錯能力。

在高容錯一致性達成算法方面，文[4-5]的Paxos算法被認為是解決一致性最有效的算法，但實現(xiàn)也有一定困難，因此產(chǎn)生了其他一致性算法，例如Zap，Raft等。這些算法中最核心的Quorum商議理論被認為是當前高容錯前提下解決一致問題最通用的方法[6]。圍繞Quorum商議方法產(chǎn)生了很多各具特色的改進，例如文[7]在消息延遲數(shù)量上減少了一個輪次，文[8]將FastPaxos與ClassicalPaxos用于分布式提交方面，比經(jīng)典的2PC方法具有更強的容錯能力。

常規(guī)的復(fù)制場景通常追求最小的復(fù)制完成時間，例如Isis協(xié)議可以實現(xiàn)至少一輪至多三輪消息交換即可完成復(fù)制；用于MySQL數(shù)據(jù)庫中日志復(fù)制的主從協(xié)議則更加簡單高效，完全利用傳輸控制協(xié)議的有序特性實現(xiàn)有序單播，保證復(fù)制結(jié)果的一致。在這些研究中，復(fù)制延遲的減少都是以容錯性為代價的，上述兩種算法對通訊及進程產(chǎn)生異常的種類都有苛刻限制。在實踐過程中，天文觀測數(shù)據(jù)存儲時對復(fù)制完成時間并不敏感，更加重視算法的容錯能力與數(shù)據(jù)安全性。過分注重存儲完成時間，弱化提交完成時一致性結(jié)果的復(fù)制算法并不適用于天文場景。

文[8]提出的一系列基于Quorum商議方法都可以實現(xiàn)高容錯，但用于實現(xiàn)強一致性復(fù)制或者事務(wù)語義有一定前提。要實現(xiàn)分布式環(huán)境下的事務(wù)，不但需要達成一致性的方法，而且為了保證并發(fā)事務(wù)執(zhí)行，必須要對讀寫操作串行化。而基于Quorum商議的算法需要三輪消息交換與兩輪日志持久化才可以通過決議選出一個操作，用于實現(xiàn)串行化將過多地增加事務(wù)完成的時間，很難在延遲上達到常規(guī)的復(fù)制場景的需求，因此不可行。但天文觀測數(shù)據(jù)的特殊性在于存儲系統(tǒng)中的FITS文件不允許更改和刪除，且任意FITS文件之間兩兩獨立無任何相關(guān)性，因此可以避免發(fā)生并發(fā)寫。無須考慮并發(fā)串行化的事務(wù)僅需對FITS文件持久化的結(jié)果達成一致即可，避免了引入有序多播機制的巨大開銷。在此種特殊的場景下，事務(wù)復(fù)制方法變得具有可用性。

2 改進的細粒度數(shù)據(jù)復(fù)制算法

定義1：數(shù)據(jù)復(fù)制原子性，如果整個FITS文件的復(fù)制結(jié)果只能是“提交”或“回滾(復(fù)制失敗)”，那么算法就滿足原子性。

在觀測數(shù)據(jù)存儲的場合下，回滾失敗的處理方法不適合FITS文件的實時存儲。在傳統(tǒng)關(guān)系型數(shù)據(jù)庫中，較多寫操作在事務(wù)提交前僅執(zhí)行日志操作并改變內(nèi)存中對應(yīng)數(shù)據(jù)，因此可以不考慮事務(wù)中已影響的記錄數(shù)目，一旦事務(wù)失敗執(zhí)行回滾即可。但在高速觀測數(shù)據(jù)流復(fù)制中執(zhí)行回滾操作，必將放棄大量已經(jīng)成功復(fù)制的數(shù)據(jù)塊，浪費過多的輸入輸出資源，嚴重制約應(yīng)用，尤其是采用分布式存儲的場合。除此之外，回滾操作還將在一個短時間內(nèi)增加采集工作站內(nèi)存中緩存的觀測數(shù)據(jù)的總量，一旦數(shù)據(jù)來不及存儲，數(shù)據(jù)丟失，將影響數(shù)據(jù)存儲的安全性。因此，在保證一致性的前提下恰當減弱事務(wù)回滾發(fā)生的條件有利于FITS文件的存儲，這是能夠保障天文數(shù)據(jù)觀測過程中數(shù)據(jù)存儲的有效方案，既保障了一定的存儲性能，又提高了數(shù)據(jù)存儲的安全性。

要減少事務(wù)回滾的發(fā)生概率，需要對原子性的要求作改進，使得異常發(fā)生情況下采集服務(wù)器(下稱客戶端)有機會對提交進行補償。為了處理這種問題，論文改進了數(shù)據(jù)復(fù)制方法，主要思路是借助減少數(shù)據(jù)提交粒度的方法。

定義2：一個FITS文件被切割成P個數(shù)據(jù)塊：[P1，...，Pn]，對應(yīng)存儲狀態(tài)為[S1，...，Sn]，每個狀態(tài) S ∈ { ″replicated″， ″unreplicated″}， ″replicated″： 表示數(shù)據(jù)塊i為已復(fù)制， 反之為未復(fù)制， 當且僅當?Pi∈[P1，...，Pn]，Si＝″replicated″，即所有塊都達成 “提交”決議時，F(xiàn)ITS文件提交成功。

為了說明復(fù)制操作的過程，設(shè)P值為2，即需要復(fù)制2份。參考Paxos算法(文中涉及的投票、編號等術(shù)語均來自該算法)[4-5]，將復(fù)制操作(下稱算法)中執(zhí)行的過程依邏輯劃分成5部分，每部分均接收并發(fā)送特定消息，這5部分為Client，Proposer，Acceptor，Learner與StorageNode。采集工作站中包含Client與Proposer兩個角色，二者只是邏輯上的劃分。算法實例的運行最先由這兩個角色同時發(fā)起。Client發(fā)起實際的數(shù)據(jù)復(fù)制操作，向負責數(shù)據(jù)持久化的StorageNode傳輸FITS文件；Proposer與3個Acceptor配合發(fā)起對存儲結(jié)果的裁決，之后Acceptor，StorageNode與Learner這3部分之間發(fā)生一系列消息傳遞用于完成FITS數(shù)據(jù)的復(fù)制。圖1描述了整個消息傳遞與日志記錄的流程，復(fù)制算法詳細步驟如下：

步驟0：Client選定復(fù)制組[SN0，SN1，SN2]，并決定主要拷貝所在的組[SN0，SN1]，執(zhí)行主從復(fù)制； 同時向 Leader Proposer提交 BeginCommit([SN0，SN1]，[SN0，SN1，SN2])消息；

步驟1a：Leader Proposer收到BeginCommit消息后，按照自己的日志選擇一個比所有已發(fā)起的投票號都要大的編號，然后向所有的Acceptor發(fā)送Prepare(N，[SN0，SN1，SN2])消息，嘗試開始編號為N的決議投票；

步驟1b：Acceptor1收到Prepare(N)消息后，如果沒有向別的進程承諾過不表決小于N的投票，則向Leader Proposers回復(fù)Promise(N，V1)消息，V1表示Acceptor1承諾過的最大投票編號。同時Acceptor0與Acceptor2也執(zhí)行相同的邏輯；

步驟2a1：Leader Proposer收到半數(shù)以上Promise(N，Vx)，x∈{0，1，2}的消息后，根據(jù)Promise消息中的(V0，V1，V2)值計算Max(V0，V1，V2)，如果Leader Proposer處于正常流程，則應(yīng)滿足條件N＝Max(V0，V1，V2)，此時依據(jù)BeginCommit消息中指示的復(fù)制組，向所有組內(nèi)成員發(fā)送Prepare(N)消息；

步驟2a2：SN0收到Prepare消息后，在自身的存儲中查詢主從復(fù)制的執(zhí)行情況，如果已經(jīng)完成FITS文件的復(fù)制，則向所有的Acceptor廣播Accept(N，[P0，P1])消息，其中P0＝P1＝″replicated″。同時SN1與SN2也執(zhí)行相同的邏輯；

步驟2b：Acceptor1需要依據(jù)步驟1a中Prepare消息獲得的復(fù)制服務(wù)器列表，等待每份復(fù)制的完成向量SN x.[P0，P1]，x∈{0，1，2}。從所有SN節(jié)點返回的復(fù)制完成向量可以判斷復(fù)制是否完全完成，但此處不必做判斷，只需將生成決議的結(jié)果向量r＝[SN0.[P0，P1]，SN1.[P0，P1]，SN2.[P0，P1]]，并通過消息Accepted(N，r)發(fā)送給Leader Proposer；

步驟3：Leader Proposer接收到半數(shù)以上的Acceptor發(fā)來的Accepted消息即可認為已經(jīng)對提交結(jié)果達成一致，廣播一致結(jié)果至所有的SN和Client節(jié)點。

至此已達成對提交結(jié)果的一致性決策結(jié)果[P1，P2]。如果i∈{1，2}，Pi＝″unsuccessful″，則Client應(yīng)對復(fù)制失敗的數(shù)據(jù)塊進行重試。重試的操作等價于重新執(zhí)行一次復(fù)制算法的實例。很多情況下該操作可以代替回滾，但要完全避免回滾發(fā)生是不可能的，例如，采集服務(wù)器硬件異常發(fā)生在FITS文件未完全提交的情況下，必須執(zhí)行回滾操作代替重試操作。如果不執(zhí)行回滾則永遠不能達成含義為提交成功的一致結(jié)果，而且有可能導致存儲復(fù)制操作陷入循環(huán)。

由圖1可以看出，算法以Quorum商議①Q(mào)uorum商議，即大多數(shù)協(xié)商決策，一般認為在對某個決議的過程中，某決議得到了超過半數(shù)的投票，即認為通過。文中因算法上下文需要因此沿用該詞。為核心，結(jié)合主備復(fù)制的優(yōu)點，保證了高效并發(fā)與強一致性。文件復(fù)制路徑由多主節(jié)點的主備復(fù)制算法決定，主節(jié)點故障時系統(tǒng)的性能損失較小。在一致性達成算法上，步驟1a與步驟1b沿用了Classic Paxos協(xié)議的第1輪過程，主要用于保證Quorum商議中的B3約束[5]；步驟2a1與步驟2a2之間，設(shè)有一個上限時間，用于限制復(fù)制完成的時間。這兩步加入了復(fù)制過程與一致性算法之間的必要交互流程，在保證不破壞Quorum商議中可進展條件的情況下計算FITS分片的持久化狀態(tài)向量。當然由于Quorum商議方法可以支持完全異步的網(wǎng)絡(luò)模型，此處用于失效判定的算法選擇很多，例如累積失效檢測器[9]，定長失效檢驗等方法都是可行的。

圖1 無異常情況下復(fù)制算法執(zhí)行路徑與一致性達成的過程Fig.1 Replication algorithm execution path and the consistency-reaching produce under no fault condition

3 算法性能分析

研究[10-11]表明，同時加強容錯與一致性存在矛盾，更強的一致性約束與復(fù)制延遲也存在必然矛盾，復(fù)制延遲對訪問性能有一定的影響。鑒于上述矛盾，算法設(shè)計時最重要的工作是根據(jù)具體的應(yīng)用場景，在容錯性、一致性與延遲之間給出最優(yōu)的平衡[12-13]。

假設(shè)將FITS文件切分成兩部分，有N個StorageNode進程，并且系統(tǒng)為容忍F個進程失敗設(shè)立了2F＋1個acceptor，在只將Prepare類型的消息發(fā)送給F＋1(acceptor中的大多)個acceptor的情況下，其日志延遲和消息延遲情況如表1。如果數(shù)據(jù)的持久化時間、日志持久化的耗時、消息的發(fā)送時間均相同，由表1可知消息延遲與日志延遲的總量為7，由于數(shù)據(jù)持久化過程與一致性達成過程可能并發(fā)執(zhí)行，最終由復(fù)制算法造成的延遲倍數(shù)在7～8之間(簡稱為放大系數(shù))，即1次復(fù)制操作比不使用復(fù)制操作帶來7～8倍的延遲，但從保障一致性的角度來看，即使不采用基于Quorum商議算法，使用傳統(tǒng)經(jīng)典的2PC方式，雖然能夠節(jié)省1次日志寫入時間，但同樣有5～6倍的延遲，因此采用Quorum商議達到一致性的方式具有可行性。

算法在復(fù)制數(shù)據(jù)塊時，僅要求采集工作站將數(shù)據(jù)提交至單臺存儲節(jié)點，并稱該節(jié)點為主節(jié)點，再由主節(jié)點執(zhí)行后續(xù)的復(fù)制。此種方法稱為主備復(fù)制，是被動復(fù)制方式的一種。相比與其對應(yīng)的主動復(fù)制，被動復(fù)制算法在容錯性上略弱[14]。

主動復(fù)制中，由采集服務(wù)器直接傳輸數(shù)據(jù)至所有存儲節(jié)點，就可以避免主備復(fù)制中由主節(jié)點失敗導致的后續(xù)問題。假設(shè)復(fù)制份數(shù)為3，每臺機器失效的概率均為p，被動復(fù)制異常的概率為p3＋2p2＋p，而主動復(fù)制為p3。

為便于討論，假設(shè)發(fā)生異常后即回滾。設(shè)執(zhí)行復(fù)制所需的一致性開銷為C，復(fù)制粒度為M，F(xiàn)ITS文件的大小為S，回滾產(chǎn)生的IO代價為M/2。

每次復(fù)制時，異?？赡軒淼腎O代價為

其中，p，C，S均為常數(shù)，M與異常可能帶來的IO代價成正比，與復(fù)制一個FITS文件的一致性開銷成反比。通過實驗測定失效概率p與一致性開銷為C可確定復(fù)制粒度M的最優(yōu)值。

p和C與硬件有直接關(guān)系，需要在實際生產(chǎn)環(huán)境中測得，因此只能給出測定M的方法，無法給出一個表征M普適的常數(shù)。

表1 日志延遲和消息延遲Table 1 Delay caused by Log and Message-Passing

4 實驗及討論

實驗服務(wù)器集群拓撲結(jié)構(gòu)如圖2，該集群由16臺搭載單塊SATA硬盤和一塊千兆網(wǎng)卡的存儲服務(wù)器充當StorageNode角色，3臺同樣配置的服務(wù)器充當Acceptor角色；1臺搭載6塊千兆網(wǎng)卡的采集工作站充當Client和Proposer角色，向集群提交隨機生成的FITS文件并生成2份拷貝。分塊大小取4 MB，并發(fā)復(fù)制實例為節(jié)點數(shù)的兩倍共32個，復(fù)制時間如圖3，上方曲線為達成一致性復(fù)制的時間，下方曲線為僅傳輸FITS文件所用的時間，二者比值時延均值在1.67左右，不到1 s，表明在存儲FITS文件的時候，可以同時通過引入一致性保障機制，保證分布式實時存儲的可行性，即在高速存儲和一致性要求之間進行了有效的平衡。

復(fù)制算法使得分布式存儲系統(tǒng)在獲得一致性的同時讓訪問延遲成為需要關(guān)注的性能參數(shù)，減少同步延遲可以減少數(shù)據(jù)在采集工作站中緩存的時間，有利于在采集工作站發(fā)生單點故障的時候減少數(shù)據(jù)丟失的數(shù)量。另外，在一致性與延遲的矛盾中，文中算法傾向容錯性較強的一致性達成方法，不可避免地增加了復(fù)制數(shù)據(jù)之間的一致性達成時間，也就決定了算法不適合KB級的小數(shù)據(jù)復(fù)制。但針對天文圖像數(shù)據(jù)的普遍大小MB級的情況，綜合考慮復(fù)制算法能夠?qū)﹀e誤異常的處理，采用Quorum商議適合天文高速觀測數(shù)據(jù)存儲的場景。

圖2 實驗環(huán)境設(shè)計Fig.2 Experimental environment

圖3 數(shù)據(jù)復(fù)制耗時與數(shù)據(jù)提交耗時的對比Fig.3 Time elapse comparison of replication operation and the commit operation

理論認為，在不存在欺騙的異步網(wǎng)絡(luò)模型中能夠容忍所有異常的一致性算法最低需要交換3輪消息[10]，本文描述的算法也使用了3輪，但是對于復(fù)制數(shù)據(jù)的大小不同，其影響程度不同。在外掛式存儲中延遲主要由機械硬盤的硬件性能決定，磁盤調(diào)度等算法因素造成的影響較?。坏诜植即鎯^程中，復(fù)制算法中的商議過程不但發(fā)生了3輪通訊還執(zhí)行4次(最少可減少到2次)記錄日志操作。系統(tǒng)在寫入KB為單元的小數(shù)據(jù)時，同樣的數(shù)據(jù)量需要更多的信息交換，對復(fù)制結(jié)果的商議過程耗時遠遠高于機械硬盤存儲數(shù)據(jù)的延遲，從而造成整體訪問延遲成倍增加。而FITS文件的典型值處在4 MB以上時，由于復(fù)制算法引入的通訊和傳輸延遲在整體延遲中所占比例減少，硬盤訪問速度依舊為延遲的主要因素，通過分析和實驗來看，兩倍的延遲在可容忍的范圍，可以采用訪問延遲較低的固態(tài)硬盤作為數(shù)據(jù)復(fù)制暫存盤，這樣能極大提高性能。

5 結(jié)束語

在上述對比實驗和理論分析中，本文提出的算法具有如下特點：(1)與主動復(fù)制方法相比，降低了采集工作站的IO開銷，增加了復(fù)制階段發(fā)生錯誤的概率，即減弱了可用性。(2)與經(jīng)典的2PC方法相比，增加了一定的延遲，獲得了容忍半數(shù)節(jié)點宕機的能力，即加強了可用性；(3)與直接寫入外掛式存儲器相比，延遲較高，但放大系數(shù)在可接受的范圍內(nèi)。雖然相應(yīng)的改進增加了延遲，但這些改進更利于安全存儲FITS文件，在性能上完全可以滿足高速觀測數(shù)據(jù)可靠存儲的需要，具有實際應(yīng)用價值。