基于數(shù)據(jù)流的多源并行高可靠數(shù)據(jù)容災算法

孫 也， 叢 巖

（1.吉林廣播電視大學教務處，長春130000；2.空軍航空大學模擬訓練中心，長春130022）

0 引 言

本文提出一種基于數(shù)據(jù)流的多源并行高可靠數(shù)據(jù)容災算法（MultiSourceParallelHighlyReliable Recovery，MSPR），該算法采用“一對多”的形式對數(shù)據(jù)進行快速備份和恢復，容災對象服務器通過網(wǎng)絡與多個備份服務器相連形成多點結構，將容災對象服務器的數(shù)據(jù)以數(shù)據(jù)流的形式傳輸?shù)絺浞莘掌髦校鎯Χ鄠€副本，利用相連接的多處備份服務器結合負載均衡技術并行下載差異數(shù)據(jù)。MSPR算法可充分考慮各個服務器的實際負載能力，合理分配數(shù)據(jù)傳輸任務，通過快慢協(xié)調保證數(shù)據(jù)恢復過程的同步與一致性。

1 MSPR算法分析

MRDBR算法［7-9］在對各個備份服務器分配任務時沒有考慮各個備份服務器的狀態(tài)差異，利用平均原則進行分配，這樣雖然簡化了分配的時間和資源開銷，但是由于各個鏈路負載不同、服務器性能不穩(wěn)定等因素，容易出現(xiàn)完成任務時間的嚴重不平衡情況，給再分配工作帶來巨大的壓力［10］。另外，數(shù)據(jù)在傳輸過程中缺乏必要的校驗機制，會造成資源和時間成本的浪費。鑒于以上問題，對MRDBR算法進行改進，提出一種基于數(shù)據(jù)流的MSPR，可以滿足以下要求：①利用負載均衡思想［11］，在恢復任務初次分配上，根據(jù)各個備份服務器不同的負載狀態(tài)進行分配，使分配更加均勻合理；②在數(shù)據(jù)傳輸過程中，加入針對一定數(shù)據(jù)粒度的校驗機制，避免數(shù)據(jù)傳輸前后不一致造成的資源浪費［12］。

MSPR具體算法分析如下：

設本地服務器P發(fā)生災難時，已經將本地數(shù)據(jù)D備份到不同位置的n臺備份服務器｛S1，S2，…，Sn｝中，數(shù)據(jù)大小均為d，而在P中災難發(fā)生后保留可用的數(shù)據(jù)為E，MAPR算法僅僅恢復E與D的差異部分F，從而減小工作量，提高恢復的針對性，差異F＝D－（E∩D），大小為f且f＜d。設方案整體的平均恢復速度為vw，恢復的整體時間tRTO＝f／vw，為了將tRTO降到最小，MAPR算法的核心任務是合理分配鏈路和并行恢復數(shù)據(jù)，并在考慮本地主機性能和硬件成本的情況下使vw達到一個最佳值。在分配傳輸任務前，要對各個備份服務器負載情況進行預分配，在分配過程中根據(jù)各個鏈路傳輸速度以及完成情況進行任務的動態(tài)調整再分配。

在預分配階段，各個備份服務器的負載指標作為最重要的參考，設N臺備份服務器對應的負載為Loadi（t），代表第i臺備份服務器在時刻t的負載情況。負載作為一個綜合性較強的指標，主要與t時刻第i臺備份服務器CPU使用率Ci（t）、內存占用率Mi（t）、磁盤I／O 占用率Ii（t）和響應時間用率Ri（t）有關，具體表達式為：式中：w1、w2、w3、w4分別表示CPU 使用率、內存占用率、磁盤I／O占用率和響應時間對整體負載的影響權值，且w1＋w2＋w3＋w4＝1。

不同情況下，各參數(shù)對負載的影響并不是一成不變的，因此權值也是根據(jù)具體的環(huán)境與實驗分析所確定的。在獲得負載指標后，根據(jù)下式將所要恢復數(shù)據(jù)F進行分配。

式中，F(xiàn)i表示第i臺備份服務器所需要傳輸?shù)臄?shù)據(jù)任務。

土體和直根的物理屬性和測試模型的物理屬性基本保持一致。土體和直根的泊松比0.3,密度2 000 kg/m3,土體楊氏模量1×106 Pa;直根楊氏模量1×107 Pa。摩擦系數(shù)定為0.5；重力加速度為10 m/s2；彈性滑動值一般設為總接觸長度的1%；拔出距離同具體只跟尺寸有關。

再分配階段負責動態(tài)調整任務分配，主要是由于預分配后，各個備份服務器在執(zhí)行過程中由于狀態(tài)的變化和不確定因素影響了恢復速度，常出現(xiàn)某一臺或幾臺備份服務器已完成了相應的傳輸任務量，而其他備份服務器任務卻沒有結束。設這種情況為t0時刻，某臺服務器SS已經完成預分配任務，此時將預計最長時間完成的備份服務器Sl的任務按照一定比例分配給SS。在分配階段，主要考慮各個服務器鏈路傳輸平均速度和剩余數(shù)據(jù)大小，通過算式max｛f′1／ˉv1，f′2／ˉv2，…，f′n／ˉvn｝找出最長恢復時間的備份服務器，并將未完成的任務量根據(jù)下式分配給SS共同完成。

式中：f″S、f″L分別代表備份服務器SS、Sl再分配后的任務量；LoadS（t0）、LoadL（t0）為備份服務器SS、Sl在t0時刻的負載；ˉvS、ˉvL為備份服務器SS、Sl恢復數(shù)據(jù)過程中的平均速度；β為服務器當前負載對傳輸任務重新分配的影響系數(shù)。

本地服務器與備份服務器Si在連接過程和傳輸過程中所需要的總時間ti為

式中：tconnect為本地服務器與備份服務器建立連接所需要的時間；tresponse為每次數(shù)據(jù)請求的響應時間。這兩段時間數(shù)據(jù)并沒有傳輸，帶寬沒有得到利用。為了避免數(shù)據(jù)分散過細導致總的數(shù)據(jù)響應時間與連接時間延長，從而造成資源浪費，設置一個數(shù)據(jù)閾值δ，當再次分配時，預計最長時間未完成的任務數(shù)據(jù)量f′L＜δ時，不需將剩余部分再分配給其他服務器。

為保證MSPR算法數(shù)據(jù)傳輸過程數(shù)據(jù)恢復的一致性，首先將要傳輸?shù)臄?shù)據(jù)按照一定大小分成j個數(shù)據(jù)塊，余出部分同樣分在一起。然后在備份服務器數(shù)據(jù)發(fā)送端對數(shù)據(jù)流進行分析，并計算出每個傳輸數(shù)據(jù)塊的特征值，通過對比判斷確定數(shù)據(jù)傳輸前后的一致性。

2 MSPR算法流程

當本地服務器發(fā)生災難，造成數(shù)據(jù)丟失時啟動MSPR算法，整個算法分為前期處理階段、預分配傳輸階段、再分配傳輸階段以及校驗階段，具體流程如圖1所示［12-15］。

圖1 MSPR算法流程

（1）前期處理階段。當災難發(fā)生時，首先由F＝D－（E∩D）獲取需要恢復數(shù)據(jù)部分，確定需要恢復數(shù)據(jù)內容F和大小f后，由本地服務器P向各個備份服務器｛S1，S2，…，Sn｝發(fā)送傳輸請求，同時記錄各個備份服務器的反饋負載信息Loadi（t）。

（2）預分配階段。在獲得各個備份服務器的負載信息Loadi（t）后，根據(jù)式（2）劃分數(shù)據(jù)，完成預分配恢復任務，并對各備份服務器發(fā)送相應的備份服務器恢復的任務記錄Ri，格式為：

式中：rec為容災表示；offset為對應備份服務器所要恢復任務的偏移地址；fi為對應備份服務器需恢復數(shù)據(jù)大小。

各個備份服務器在接收到來自本地服務器發(fā)來的任務記錄后，按照指定的偏移量及數(shù)據(jù)大小讀取各自數(shù)據(jù)Fi，同時根據(jù)MD5算法在傳輸端利用函數(shù)H（Fi）算出數(shù)據(jù)Fi的特征值γbi，存儲任務記錄反饋R′i中發(fā)送給本地服務器。記錄反饋格式為：

本地服務器接收到來自各備份服務器的數(shù)據(jù)，將數(shù)據(jù)按照偏移量進行順序存儲，逐步完成數(shù)據(jù)的恢復。

（3）再分配階段。當其中的某個備份服務器完成其分配的任務時，需要按照式（3）將此時預計需要最長時間完成的備份服務器Sl的任務分配給SS，并執(zhí)行預分配之后的步驟。為了減小不必要的再分配造成時間響應浪費，設置一個數(shù)據(jù)閾值δ，當再次分配時，預計最長時間未完成的任務數(shù)據(jù)量f′L＜δ時，不必將剩余部分再分配給其他服務器。

（4）數(shù)據(jù)校驗階段。數(shù)據(jù)校驗階段貫穿于數(shù)據(jù)恢復的整個過程，在備份服務器的數(shù)據(jù)發(fā)送端利用WinPcap將數(shù)據(jù)流捕獲并進行分析，并結合MD5算法計算出一定大小χ傳輸數(shù)據(jù)塊的特征值γbij，當對應數(shù)據(jù)在本地服務器接收后再次利用函數(shù)H（Fi）算出對應接收數(shù)據(jù)的特征值γaij，通過判斷是否滿足γbij＝γaij來確定數(shù)據(jù)傳輸前后的一致性，以保證數(shù)據(jù)恢復的準確性，若γbij≠γaij需要重新傳輸對應的數(shù)據(jù)塊。

3 MSPR算法測試

為驗證MSPR算法整體的有效性和各項性能，在千兆局域網(wǎng)中搭建實驗環(huán)境，包括本地主服務器1臺，備份服務器6臺。服務器CPU型號為Intel E5-2600 V4，8GB 內存，操作系統(tǒng)為Windows Server 2008，本地服務器的網(wǎng)卡帶寬為1 Gb／s，備份服務器的網(wǎng)卡帶寬為100 Mb／s。其他參數(shù)配置見表1。

表1 實驗環(huán)境參數(shù)

3.1 測試結果

測試分為6組，每組實驗所需要的備份服務器的數(shù)量分別為1～6。在測試過程中，各備份服務器持續(xù)不斷地向本地服務器傳輸數(shù)據(jù)，分別測得每組實驗中組內所有備份服務器的數(shù)據(jù)恢復速度。考慮到初始傳輸狀態(tài)數(shù)據(jù)傳輸速度不穩(wěn)定，測量過程以第10 s時間為基準，在輸出開始10 s測量各組中各個服務器的數(shù)據(jù)恢復速度，則不同備份源服務器的數(shù)據(jù)恢復速度如圖2所示。

測得備份服務器數(shù)量變化情況下，各組實驗本地服務器數(shù)據(jù)恢復的整體速度，時間從0 s開始，如圖3所示。

實驗證明，在一定范圍內，本地服務器的數(shù)據(jù)恢復速度與并行連接的備份服務器數(shù)量呈明顯的遞增趨勢，充分證明了利用多源并行數(shù)據(jù)恢復可以利用多條鏈路帶寬，大幅提高數(shù)據(jù)整體恢復速率。利用恢復算法進行并行恢復過程中，各個鏈路達到速度穩(wěn)定值所用時間為3～4 s，具有比較短的初始響應時間。當備份服務器數(shù)量達到5以上時，本地服務器數(shù)據(jù)恢復速度受制于處理性能和存儲性能，達到本地服務器網(wǎng)卡帶寬值的60%左右，恢復速率不能繼續(xù)增長保持在一定水平收斂。因此，考慮到資源成本利用的最大化，為了達到最佳恢復速率且兼顧成本代價，本實驗環(huán)境備份服務器設為4或5。

圖2 不同備份源服務器的數(shù)據(jù)恢復速度

圖3 本地服務器數(shù)據(jù)恢復的整體速度

3.2 性能對比

備份服務器數(shù)量分別設為5，設置恢復數(shù)據(jù)大小為1～10 GB，測試本文改進算法MSPR與傳統(tǒng)多點恢復數(shù)據(jù)MRPTC算法的恢復時間。其中，MRPTC采取數(shù)據(jù)恢復鏈路平均分配的方法，分配系數(shù)σ＝0.2。兩種算法恢復時間RTO對比結果如圖4所示。

在傳輸速率上，設置恢復數(shù)據(jù)大小為10 GB，備份服務器數(shù)量為5，在10～150 s測得兩種算法整體恢復速度如圖5所示。

在可靠性上利用第3方特征值計算工具MD5sum，分別設置恢復數(shù)據(jù)大小為1～10 GB，測試恢復數(shù)據(jù)在傳輸前和恢復后是否一致，兩種算法恢復數(shù)據(jù)的錯誤率對比如圖6所示。

圖4 兩種算法RTO對比

圖5 數(shù)據(jù)恢復速度對比圖

圖6 錯誤率對比

RTO對比實驗證明，兩種算法在相同恢復任務的情況下，MSPR算法充分利用多條鏈路帶寬，整體恢復速度更加迅速，當恢復數(shù)據(jù)超過3.5 GB時恢復時間指標具有明顯優(yōu)勢。數(shù)據(jù)恢復速度測試結果再一次驗證了MSPR算法按照各路實時負載情況分配任務比MRPTC算法更加合理，減小再分配階段的次數(shù)和復雜性。從數(shù)據(jù)傳輸過程速率波動次數(shù)可以看出，MSPR算法提高了首次分配準確性，正是由于MSPR數(shù)據(jù)傳輸過程速率波動次數(shù)少且更加平穩(wěn)，從而提高了整體傳輸速度。數(shù)據(jù)恢復錯誤率實驗說明在可靠性方面，MSPR算法在傳輸兩端加入特征值驗證環(huán)節(jié)，因此數(shù)據(jù)恢復錯誤率幾乎為0，當恢復數(shù)據(jù)增加時MSPR算法并沒有隨著恢復數(shù)據(jù)的增大而明顯增加，可以證明這種特征值驗證方式在不明顯提高時間成本情況下，有效提高了數(shù)據(jù)傳輸與恢復過程的可靠性。

4 結 語

本文給出一種基于數(shù)據(jù)流的多源并行高可靠恢復算法MSPR，這種算法在傳統(tǒng)多源恢復方案的基礎上，通過改進普遍使用的MRPTC算法得到，可滿足信息系統(tǒng)高可靠應急的需求，實現(xiàn)在極短的時間鎖定所需的目標數(shù)據(jù)并準確恢復的功能。研究結果表明，該算法對于初始任務的分配更合理，減小了再分配階段的次數(shù)和復雜性，從而提高了整體傳輸速度，且具有校驗機制，在傳輸可靠性上具有明顯優(yōu)勢。