基于數據流的多源并行高可靠數據容災算法

孫 也， 叢 巖

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

0 引 言

本文提出一種基于數據流的多源并行高可靠數據容災算法（MultiSourceParallelHighlyReliable Recovery，MSPR），該算法采用“一對多”的形式對數據進行快速備份和恢復，容災對象服務器通過網絡與多個備份服務器相連形成多點結構，將容災對象服務器的數據以數據流的形式傳輸到備份服務器中，存儲多個副本，利用相連接的多處備份服務器結合負載均衡技術并行下載差異數據。MSPR算法可充分考慮各個服務器的實際負載能力，合理分配數據傳輸任務，通過快慢協調保證數據恢復過程的同步與一致性。

1 MSPR算法分析

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

MSPR具體算法分析如下：

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

在預分配階段，各個備份服務器的負載指標作為最重要的參考，設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。

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

式中，Fi表示第i臺備份服務器所需要傳輸的數據任務。

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

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

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

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

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

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

2 MSPR算法流程

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

圖1 MSPR算法流程

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

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

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

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

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

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

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

3 MSPR算法測試

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

表1 實驗環境參數

3.1 測試結果

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

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

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

圖2 不同備份源服務器的數據恢復速度

圖3 本地服務器數據恢復的整體速度

3.2 性能對比

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

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

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

圖4 兩種算法RTO對比

圖5 數據恢復速度對比圖

圖6 錯誤率對比

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

4 結 語

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