一種P2P分布式系統高可靠數據恢復模型

姜春茂，張國印，曲明成

(1.哈爾濱工程大學計算機科學與技術學院，黑龍江哈爾濱150001;2.哈爾濱師范大學計算機科學技術與信息工程學院，黑龍江哈爾濱150025;3.哈爾濱工業大學計算機科學與技術學院，黑龍江哈爾濱150001)

在基于P2P的分布式系統中，數據的可靠存儲與恢復一直是熱點問題[1].確保分布式系統中存儲的海量數據的完整性、可用性是亟待解決的關鍵問題.由于P2P分布式系統節點的具有很高的動態性，導致不可靠，在節點發生失效時，必須確保數據的完整可用，因此必須盡快地選出新節點并進行災難節點的數據備份恢復[2].

通過維護高可靠性的部分節點集合，針對其中某些節點對其在集合中的異地建立和維護冗余數據，利用地理分散性來保證數據對災難事件的抵御能力[3].根據容災的概念可知，容災的核心就是增加數據冗余度，當災難發生時，讓數據的副本被同時毀壞的概率降到可以接受的程度，降低數據副本被同時毀壞的概率，提升數據的恢復速度，保證整體數據具有較高的可用性、較低的失效概率[4].

目前基于P2P的分布式系統中對抗數據失效技術實現方法雖然各不相同，多副本是一項主要手段，較多的是基于雙副本[2-3，5].使用雙副本容災，當發生災難時(節點損壞或短期內不可用)，從一個副本節點進行數據恢復，由于受到傳輸鏈路和節點網絡帶寬限制，其恢復速度明顯較慢，由于數據恢復期較長，在恢復期內備份節點發生失效的概率隨之增大.如何在節點發生災難后對數據進行快速恢復以降低整體數據失效概率是目前亟待解決的關鍵問題.

GridFTP是為快速傳輸而設計的傳輸協議，針對GridFTP協議，很多學者分別基于Linux、Unix和Windows操作系統進行實現方法研究，取得了良好的應用效果[6-8].GridFTP提供了條狀數據傳輸方式，即GridFTP客戶端可以并行的從多個GridFTP服務器端下載不同數據塊.基于GridFTP協議出現了很多的并行傳輸算法，這大幅度提高了中數據的傳輸速度[2，4，9-11].

基于P2P的分布式存儲模型和并行傳輸的算法[12]基本達到了與基于全副本進行并行傳輸的性能，而且存儲空間使用較少.基于存儲模型和并行傳輸給出的數據失效模型雖然達到了可靠存儲、快速數據恢復的目標，但是其假定了下載速度隨著并行傳輸數的增加呈線性增加，其約束過于理想[12].

由于以往的研究假定Sk-Sk-1為常數，而從實際角度來看Sk-Sk-1為變值，本文從實際應用的角度提出分布式模型和對各個參數進行詳細的分析.

1 分布式模型

定義1 ω等分.令總數據量為M，對整個數據進行等分，令分割的份數等于k(k-1)ω，k為副本節點的個數.分割方式為:先將數據等分成k(k-1)份，再將每一份等分成ω份，這里ω是一個可變參數.則每一份的數據量m為

定義2 本地數據.將定義1中分割的k(k-1)ω份數據平均分配到k個節點上，則每個節點存儲(k-1)ω份數據.稱這些數據為節點Ni的本地數據Li.其中:L表示本地數據，Li表示節點i的本地數據.

定義3 本地數據虛擬組.將節點Ni存儲的本地數據塊進行虛擬組劃分，即將ω個數據劃為一組，將劃分后的組進行節點內編號.由定義2知，一個節點本地數據可以劃分的虛擬組數為(k-1)個，令虛擬組為Gji(0≤i≤k-1，0≤j≤k-2).令 Gi表示節點Ni的所有虛擬組，G表示當前虛擬組.

定義4 剩余節點集合.令刨除節點Ni后的所有參與存儲的節點集合為剩余節點集合，即

定義5 交叉存儲.將節點Ni的數據Gi存儲到刨除Ni的其他k-1個節點上，即，并滿足如下規則1))modk，p≤k-1}，p為指定的常數，“→”表示存儲到，稱這種存儲方式為交叉存儲.

分布式存儲模型:節點Ni存儲的所有數據Ai包括本地數據Li，和其他節點的交叉存儲數據Oi，有

式中:p為指定的常數，稱其為分布式存儲模型.其中:O表示本地數據，Oi表示節點i的本地數據.

定理1 P完整性.如數據滿足存儲模型，則當有任意p個節點不可用時，其余k-p個節點中數據的并集仍然等于整體數據量M，即完整的數據，稱這種性質為P完整性.(證明略)

引理1 滿足數據存儲模型的數據，其整體存儲數據量可以表示為:k(1+p)(k-1)ω.

定義6 存儲空間使用量率U.采用存儲模型總體數據存儲量與采用x個完整副本存儲的總數據量比值定義為存儲空間使用量率U.由定義1和引理1可得U如下:

2 數據恢復模型

2.1 基本定義

引理2 為了使分布式存儲模型占用的存儲空間與雙副本存儲相同，p必須等于1.

證明:首先必須滿足定義6中的存儲空間使用量率S等于1，由于采用雙副本，則式(2)中的x等于2，則有

定義7 數據失效概率f.將當前可用的存儲了同一數據的所有節點的數據作并集處理，如果得到的數據是不完整的，則稱發生了數據失效，發生的概率為 f.

定義8 節點失效概率F.當節點發生異常時，節點不再可用或短期不再可用，稱節點在單位時間(tr)發生異常的概率為節點失效概率，記為F.

約束1:為了方便后續模型的推導，給定約束中一個節點從另一個節點傳送數據所能達到的平均速度為V.

定義9 非線性速度和Sk.當從備份節點向新節點恢復速度時，從k個節點同時傳送數據，令所能夠達到的平均傳輸速度為Lk，令Sk=Lk/V，稱Sk為非線性速度和.由約束1可知，S1=1.

從定義7、8可知，當發生節點失效時未必會發生數據失效.比如在雙副本存儲中，如果一個節點發生了失效，另一個可用節點存儲的數據仍然是完整的，此時沒有發生數據失效.在模型中，由引理2可知，在發生了1個節點失效時，剩余節點存儲的數據仍然是完整的，也沒有發生數據失效.

如果只是靜態地考慮節點失效對數據失效造成的影響，而不考慮數據恢復，顯然，由于分布式存儲模型中的k值(采用的節點數)大于等于2，在相同的時間內，存儲模型的數據失效概率更大.

2.2 數據恢復模型

約束2 在進行基于分布式存儲模型的數據恢復模型推導時，令分布式存儲模型中的p=1，參見引理2.

只考慮靜態節點失效是不完備的，當有節點失效時為了保證數據的完整性，應該立即選取新的節點，將失效節點的數據恢復到新節點，以此提升數據存儲的可靠性.如圖1(a)所示，雙副本存儲，當副本2的存儲節點失效時，從副本1向新節點恢復數據，這里M為數據量，V為速度(約束1)，恢復時間為T.

圖1 雙副本存儲數據恢復與數據失效Fig.1 Double replica storage retrieved and data failure

數據交換中心:在向新節點備份時，數據首先要經過一個帶寬和可靠性較高的數據交換中心，數據在交換中臨時緩存，以此來保證向新節點的數據恢復更可靠，當再備份期新節點發生故障時，由數據中心選取新的節點并繼續備份.一旦數據被完全傳送到數據中心則認為備份完成，當數據從數據中心完全成功的備份到一個新節點時，數據中心刪除臨時存儲的數據.這樣的結構使備份更可靠，速度更快.如果沒有數據交換中心，在數據恢復期新節點也有可能失效，需要重新選擇新節點來重新傳送，使數據恢復時間過長，導致僅存的副本節點失效概率增大，致使數據失效概率增大.

雙副本存儲數據失效概率:在數據中心存在的情況下，對于雙副本存儲，如果有1個節點失效，則立即進行數據恢復，那么當在恢復期內[t0，t1]，時間長度為T，如果另1個副本節點發生失效，則會造成數據失效，如圖1(b)所示.顯然如果引入數據恢復動態行為，那么對于雙副本發生數據失效的概率如下:

式中:α為失效概率，θ為數據恢復時間長度T與失效單位時間tr(定義8)的比值，由于單位時間的節點失效概率為F，那么

表示θ個單位時間發生節點失效的概率，即在T內發生數據失效的概率.

基于存儲模型的數據失效概率 由約束2，本部分令p=1，因此與雙副本類似，當有1個節點失效時，根據定理1，剩余節點存儲數據的并集為完整數據，此時選取新節點進行數據恢復，恢復時需要從其他k-1個節點并行傳輸，如圖2(a)所示.

由分布式存儲模型可知采用k個節點存儲，總數據量為2倍副本2M，則每個節點存儲數據為2M/k，從k個節點并行傳輸的速度為Lk-1，則恢復時間:

顯然如果分布式存儲模型存儲，在任意區間[t0，t1]，時間長度為 T'內，當有 0或 1個節點失效時，不會出現數據失效，如圖2(b).那么在[t0，t1]內，任意1個節點發生失效的概率f如下

由分布式存儲模型、泊松分布、并行恢復策略可以推出數據恢復模型:

式中:β表示數據失效概率，k為節點數.

圖2 模型存儲數據恢復與數據失效Fig.2 The model of data retrieved and data failure

證畢.

3 數據恢復模型特性分析

從數據恢復模型的構建過程可以看出，模型是動態的，在動態基礎上給出了數據失效概率，并且其性能受到Sk的影響.在互聯網上同一個節點在從多個節點進行并行數據傳輸時，所能得到的帶寬與并行數不成正比，如果客戶端帶寬較高，一般情況下在合理的并行數內，帶寬會隨著并行數呈現出一定的上升趨勢.

那么數據恢復模型與雙副本存儲2種方式帶來的數據失效概率之間的理論關系，以及數據恢復模型與Sk之間的理論關系需要仔細分析.

3.1 β與α的比較

定理2 對于數據恢復模型公式(7)，當θ，F，k一定時，β為Sk-1的單調減函數.

證明:令常數e為自然對數函數的底數，由泊松分布可知，β可以進行如下變換:

β的一階導數小于0，所以β為Sk-1的單調減函，證畢.

對定理2 進行檢測，令 θ=550，f=0.000 5，k=4，Sk-1∈(1.2，1.3，1.4，1.5，1.6，1.7)逐漸增加，這里應該保證θf＜1，否則由式(2)可知，α大于1，則數據失效必然發生，失去實際意義.

結論:從圖3中可以看出，β隨著Sk-1的增加呈現下降趨勢，為Sk-1的減函數，與定理2的一致.

圖3 β與S的關系Fig.3 Relation of β and S

在保證β＜α的前提下，數據恢復模型才具有實際意義，那么當k取不同值時，Sk-1必須滿足什么條件才能保證β＜α，基于此前提條件由式(2)、(8)可以得出

根據定理2，當 θ，F，k一定時，β 為 Sk-1的單調減函數，因此可以先令不等式(9)為1個等式，求出邊界值，只要不等式的Sk-1大于根據等式求解出的Sk-1' ，就可以滿足β＜α.

由于根據不等式(9)得出的等式方程為高次方程，可以采用 matlab求解，令 θ=550，F={0.000 1，0.000 2，…，0.000 5}，逐漸增加 k 值，求出Sk-1，由定義9可知S1=1，所得數據如表1所示.

表1 β=α時S的取值Table 1 The value when β=α

圖4 β=α時S的取值Fig.4 S value when the β = α

從表1和圖4可以看出，當β=α時，相應的S取值都較小，事實上這么小的S是在實際應用中是很容易達到.在k=3時，最小的Sk-1僅為1.087 8，若 V 等于 100，k=3，并行數為 2，則 S2=1.087 8，L2=108.8;k=8 時最大的 S7=1.295，L7=129.5.

結論:在保證β＜α情況下，數據恢復模型隨著k的增加對傳輸速度增加的依賴很低.

3.2 β 與 S、k、θF 的關系

用戶在從多節點進行并行傳輸時，隨著并行數的增加，速度增加呈現緩降趨勢.而數據恢復模型需要從k-1個節點進行數據恢復，在這種情況失效概率呈現出怎樣的趨勢.

采用公比小于1的等比數列來模擬Sk-1，即隨著并行數的增加，下載速度和的增加逐漸減緩，以此來檢測β與S、k的關系.Sk-1與k的關系如下:

將式(10)代入式(8)可以得到

令 θF=0.23，取不同的 q={0.2，0.3，0.4，0.5，0.6，0.7}，逐漸增加 k，觀測 β 的變化情況(如表2).

表2 Sk-1增速減緩對β的影響Table 2 The influence of Sk-1slowing growth on β

從該測試中可以看出在q逐漸增加，即速度的增幅Sk-Sk-1=qk-1(k≥1)逐漸增大時，β曲線的變化過程是:始終上升→先下降后上升(最低點逐漸右移，且曲線增幅逐漸減緩)→始終下降(下降趨勢逐漸增大).

結論:很顯然在實際的應用中根據各種網絡情況，選擇β曲線最低點出現時k的取值作為數據恢復模型的參數效果最為理想，同時還必須保證β＜α.

在進行上述分析時，θF都為定值，因此需要改變θF的取值，觀測其對 β曲線的影響.令q=0，θF∈(0.20，0.23，0.26，0.29，0.32，0.35)，計算 β取值.通過實驗，發現在θF取不同值時，隨著k的增加，β曲線的形狀基本沒有變化.

結論:由于θF對曲線的形狀沒有影響，因此β曲線的最低點(在k-1個并行數存在時，數據失效概率最小)可以根據k與Sk-1值確定.

3.3 網絡流量分析

定理3 在保證數據不失效的前提下，雙副本數據恢復與數據恢復模型2個動態系統對網絡流量的影響是相同的.

證明:令時間跨度為T，節點在單位時間ts內的失效概率為F，數據副本大小為M，模型采用k存儲.

1)對于雙副本，一個節點在時間T內的期望失效次數為c1=T/ts，每次恢復傳輸數據量為M，則2個節點在T內帶來的網絡流量為c1=2TM/ts.

2)對于恢復模型，由于采用雙副本，則總存儲數據量由定義6、引理2、約束2可知為2M，則每個節點存儲數據量為2M/k，則k個節點在T內帶來的網絡流量可以表示為，證畢.

結論:數據恢復模型并沒有節省網絡流量，但是其使得數據失效概率明顯降低.

4 實驗

在數據恢復模型中引入了基于數據交換中心的結構，交互中心具有較大的帶寬和較高的可靠性.實驗主要開展以不同節點作為數據交換中心，并行傳輸數變化時，交換中心所能夠達到的平均下載帶寬(Sk-1).根據并行數k-1，和Sk-1給出實際的β和α取值，并對二者進行對比分析.

4.1 數據觀測

1)數據交換中心為教育網內普通PC節點，數據存儲節點分別位于如下主機.采用網絡探測工具探測本地速度最大為157 kB，實測數據如表3.

表3 普通PC機作為數據交換中心獲得的單節點傳輸實測數據Table 3 Single node transmission measurement data by using PC as data excharge center

取上述各平均速度的平均值作為從一個節點傳輸數據的速度，為117 kB，即V=L1=117.

2)采用上述類似的觀測方法，設置交換中心為3G無線網絡內的普通筆記本，觀測主機如表4，平均V(L1)=163.采用網絡探測工具探測本地速度為最大246 kB.

表4 普通PC機作為數據交換中心獲得的多節點并行傳輸實測數據Table 4 Multi node parallel transmission measurement data by using PC as data exchange center

表5 3G無線網絡的筆記本作為數據交換中心獲得的單節點傳輸實測數據Table 5 Single node transmission measurement data by using 3G wireless network notebook as data exchange center

表6 企業內部服務器作為數據交換中心獲得的單節點傳輸實測數據Table 6 Single node transmission measurment data by using enterprise internal server as data exchange center

3)上述的數據存儲節點本身帶寬較大，而數據交換中本身帶寬較小(尤其在教育網內時).

采用普通PC節點，分別位于校園網學生宿舍(2臺式PC，2臺筆記本)、聯通寬帶(3臺)電腦安裝IIS服務器，由于這些主機都具有獨立IP地址，因此可以作為臨時服務其，在其上發布32M相同數據.數據中心設置于黑龍江聯通公司，探測數據中心的最大下載速度為423 kB.取表5各平均速度的平均值作為從一個節點傳輸數據的速度，為104 kB，即V=L1=104，實測數據如表6.

4.2 數據分析

由于非線性速度和函數是影響數據恢復模型的關鍵，其對β有較大的影響.令各節點的失效概率與數據恢復時間θF=0.23，則由式(2)可以得出α=(θF)2=0.052 9.根據式(7)以及4.1 節中觀測到的Si值計算出相應的β值，如表7.

表7 β數值Table 7 The value of β

根據3.2節的分析，β值受Sk-1的影響很大，對于上述觀測的β取值，必須滿足下式，以此來確定最佳的k值:

當數據交換中心為一個教育網內普通PC，由于帶寬較小，測試時最大速度為157 kB，因此隨著k的增加(并行數增加)，Lk和Sk的增幅較小，導致β只是略低于α，比值均在1～1.5之間.而在實驗(2)中，測試時的帶寬稍高一些，達到了246 kB，因此的α/β 最大值達到了3.19.

從前2個實驗可以看出，數據中心的本身帶寬較小，導致了數據恢復模型的性能只是略好于雙副本數據恢復策略.而在實驗3中，由于數據交換中心的節點位于帶寬較高的聯通公司內部，而數據節點為普通用戶PC和普通寬帶網絡，所以可以看出隨著k的增加α/β一直升高，相應的β一直降低.

實驗(3)充分說明了，2.2節中提出的以可靠性較高、帶寬較大的節點作為數據交換中心策略的實用性和正確性.

在圖5中，可以看出，拐點預示β數值將增大，因此選取第一個拐點出現處的k值作為恢復模型的參數較為適宜，在3個試驗中，拐點處k取值分別為4、5，此時的并行數為 3、4，此時 α/β 分別為 1.38、3.19、7.15，效果較好.

4.3 實驗小結

圖5 3種β的第一個拐點分析Fig.5 Three β analysis of the first inflection point

如果數據中心帶寬較大，則可以將數據恢復模型中的k值適當放大，但是也要考慮到數據中心網絡擁塞使帶寬極度降低的情況，這樣將導致并行恢復速度較慢，使數據失效概率增大.從實驗結果看，在一般情況下數據恢復模型均能使數據的失效概率小于雙副本存儲恢復機制.

5結論

本文基于分布式存儲模型提出的數據恢復模型，基于數據交換中心、并行傳輸和非線性速度和函數，較以往研究具有更強的實用價值.對模型的理論分析顯示出對于數據恢復模型，當模型的并行數增加時，在保證β不小于α的前提下，模型對速度和的增加值要求較小;模型中β的形狀受到Sk的影響，而θF只是影響到了起到平移曲線的作用并不改變其形狀;模型使用與雙副本一樣的存儲空間，達到了降低數據失效概率的目標，但是兩種策略對網絡流量的影響是一樣的.實驗顯示，在一般情況下數據恢復模型都具有較好的性能，而基于數據交換中策略使模型性能進一步提升，使數據失效概率均小于雙副本機制.由于本文提出的數據恢復模型中不假定下載速度隨著并行數呈線性增長，因此這較先前研究有質的區別，取得的成果具有更實際的意義，將為分布式數據存儲和恢復提供有意的參考.

[1]陳貴海，吳帆，李宏興.基于DHT的P2P系統中高可用數據冗余機制[J].計算機學報，2008，31(10):1695-1704.CHEN Guihai， WU Fan， LIHongxing. Redundancy schemes for high availability in DHTs[J].Chinese Journal of Computers，2008，31(10):1695-1704.

[2]YU Xiangzhan，WU Guanjun，WANG Dong.An disaster tolerance model based on dataflow replication[C]//Proceedings of the 2008 IEEE International Conference on Information Automation. Zhangjiajie:IEEE Computer Society，2008:1590-1594.

[3]PITKANEN M，MOUSSA R，SWANY M，et al.Erasure codes for increasing the availability of grid data storage[C]//International Conference on Internet and Web Applications and Services，AICT/ICIW ＇06.Guadeloupe:IEEE Computer Society，2006:1-10.

[4]WILKINS R S，DU X，COCHRAN R A，et al.Disaster tolerant Wolfpack geo-clusters[C]//Proceedings of the 2002 IEEE International Conference on Cluster Computing.Chicago:IEEE Computer Society 2002:1-6.

[5]WANG Y，LI Z，LIN W.Rwar:a resilient window-consistent asynchronous replication protocol[C]//Proceedings of the TheSecO International Conference Availability，Reliability and Security.Vienna:IEEE Computer Society，2007:499-505.

[6]FENG J，CUI L，WASSON G，et al.Toward seamless grid data access:design and implementation of gridftp on.net[C]//The 6th IEEE/ACM International Workshop.Vienna:IEEE Computer Society，2005:1-8.

[7]VAZHKUDAI S.Enabling the co-allocation of grid data transfers[C]//Proceedings of the Fourth International Workshop on Grid Computing.Phoenix:IEEE Computer Society，2003:1-8.

[8]BHUVANESWARAN R S，KATAYAMA Y，TAKAHASHI N.Dynamic co-allocation scheme for parallel data transfer in grid environment[C]//Proceedings of the First International Conference on Semantics，Knowledge，and Grid.Beijing:IEEE Computer Society，2006:1-6.

[9]ALLCOCK W，BRESNAHAN J.The globus striped Grid-FTP framework and server[C]//Proceedings of the 2005 ACM/IEEE SC|05 Conference.Seattle:IEEE Computer Society，2005:1-11.

[10]VAZHKUDAI S.Distributed downloads of bulk，replicated grid data[J].Journal of Grid Computing，2004，2(1):31-42.

[11]KHANNA G，CATALYUREK U，KURC T，et al.A dynamic scheduling approach for coordinated wide-area data transfers using Grid TP[C]//Proceedings of the 22nd IEEE International Parallel and Distributed Processing Symposium.Miami:IEEE Computer Society，2008:1-12.

[12]曲明成，吳翔虎，廖明宏，等.一種數據網格容災存儲模型及其數據失效模型[J].電子學報，2010，38(2):315-320.QU Mingcheng，WU Xianghu，LIAO Minghong，et al.A disaster-tolerant storage model and a low data failure model for data grid[J].Acta Electronica Sinica，2010，38(2):315-320.