一種P2P分布式系統(tǒng)高可靠數(shù)據(jù)恢復(fù)模型

姜春茂，張國印，曲明成

(1.哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱150001;2.哈爾濱師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)與信息工程學(xué)院，黑龍江哈爾濱150025;3.哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱150001)

在基于P2P的分布式系統(tǒng)中，數(shù)據(jù)的可靠存儲與恢復(fù)一直是熱點(diǎn)問題[1].確保分布式系統(tǒng)中存儲的海量數(shù)據(jù)的完整性、可用性是亟待解決的關(guān)鍵問題.由于P2P分布式系統(tǒng)節(jié)點(diǎn)的具有很高的動(dòng)態(tài)性，導(dǎo)致不可靠，在節(jié)點(diǎn)發(fā)生失效時(shí)，必須確保數(shù)據(jù)的完整可用，因此必須盡快地選出新節(jié)點(diǎn)并進(jìn)行災(zāi)難節(jié)點(diǎn)的數(shù)據(jù)備份恢復(fù)[2].

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

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

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

基于P2P的分布式存儲模型和并行傳輸?shù)乃惴╗12]基本達(dá)到了與基于全副本進(jìn)行并行傳輸?shù)男阅埽掖鎯臻g使用較少.基于存儲模型和并行傳輸給出的數(shù)據(jù)失效模型雖然達(dá)到了可靠存儲、快速數(shù)據(jù)恢復(fù)的目標(biāo)，但是其假定了下載速度隨著并行傳輸數(shù)的增加呈線性增加，其約束過于理想[12].

由于以往的研究假定Sk-Sk-1為常數(shù)，而從實(shí)際角度來看Sk-Sk-1為變值，本文從實(shí)際應(yīng)用的角度提出分布式模型和對各個(gè)參數(shù)進(jìn)行詳細(xì)的分析.

1 分布式模型

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

定義2 本地?cái)?shù)據(jù).將定義1中分割的k(k-1)ω份數(shù)據(jù)平均分配到k個(gè)節(jié)點(diǎn)上，則每個(gè)節(jié)點(diǎn)存儲(k-1)ω份數(shù)據(jù).稱這些數(shù)據(jù)為節(jié)點(diǎn)Ni的本地?cái)?shù)據(jù)Li.其中:L表示本地?cái)?shù)據(jù)，Li表示節(jié)點(diǎn)i的本地?cái)?shù)據(jù).

定義3 本地?cái)?shù)據(jù)虛擬組.將節(jié)點(diǎn)Ni存儲的本地?cái)?shù)據(jù)塊進(jìn)行虛擬組劃分，即將ω個(gè)數(shù)據(jù)劃為一組，將劃分后的組進(jìn)行節(jié)點(diǎn)內(nèi)編號.由定義2知，一個(gè)節(jié)點(diǎn)本地?cái)?shù)據(jù)可以劃分的虛擬組數(shù)為(k-1)個(gè)，令虛擬組為Gji(0≤i≤k-1，0≤j≤k-2).令 Gi表示節(jié)點(diǎn)Ni的所有虛擬組，G表示當(dāng)前虛擬組.

定義4 剩余節(jié)點(diǎn)集合.令刨除節(jié)點(diǎn)Ni后的所有參與存儲的節(jié)點(diǎn)集合為剩余節(jié)點(diǎn)集合，即

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

分布式存儲模型:節(jié)點(diǎn)Ni存儲的所有數(shù)據(jù)Ai包括本地?cái)?shù)據(jù)Li，和其他節(jié)點(diǎn)的交叉存儲數(shù)據(jù)Oi，有

式中:p為指定的常數(shù)，稱其為分布式存儲模型.其中:O表示本地?cái)?shù)據(jù)，Oi表示節(jié)點(diǎn)i的本地?cái)?shù)據(jù).

定理1 P完整性.如數(shù)據(jù)滿足存儲模型，則當(dāng)有任意p個(gè)節(jié)點(diǎn)不可用時(shí)，其余k-p個(gè)節(jié)點(diǎn)中數(shù)據(jù)的并集仍然等于整體數(shù)據(jù)量M，即完整的數(shù)據(jù)，稱這種性質(zhì)為P完整性.(證明略)

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

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

2 數(shù)據(jù)恢復(fù)模型

2.1 基本定義

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

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

定義7 數(shù)據(jù)失效概率f.將當(dāng)前可用的存儲了同一數(shù)據(jù)的所有節(jié)點(diǎn)的數(shù)據(jù)作并集處理，如果得到的數(shù)據(jù)是不完整的，則稱發(fā)生了數(shù)據(jù)失效，發(fā)生的概率為 f.

定義8 節(jié)點(diǎn)失效概率F.當(dāng)節(jié)點(diǎn)發(fā)生異常時(shí)，節(jié)點(diǎn)不再可用或短期不再可用，稱節(jié)點(diǎn)在單位時(shí)間(tr)發(fā)生異常的概率為節(jié)點(diǎn)失效概率，記為F.

約束1:為了方便后續(xù)模型的推導(dǎo)，給定約束中一個(gè)節(jié)點(diǎn)從另一個(gè)節(jié)點(diǎn)傳送數(shù)據(jù)所能達(dá)到的平均速度為V.

定義9 非線性速度和Sk.當(dāng)從備份節(jié)點(diǎn)向新節(jié)點(diǎn)恢復(fù)速度時(shí)，從k個(gè)節(jié)點(diǎn)同時(shí)傳送數(shù)據(jù)，令所能夠達(dá)到的平均傳輸速度為Lk，令Sk=Lk/V，稱Sk為非線性速度和.由約束1可知，S1=1.

從定義7、8可知，當(dāng)發(fā)生節(jié)點(diǎn)失效時(shí)未必會發(fā)生數(shù)據(jù)失效.比如在雙副本存儲中，如果一個(gè)節(jié)點(diǎn)發(fā)生了失效，另一個(gè)可用節(jié)點(diǎn)存儲的數(shù)據(jù)仍然是完整的，此時(shí)沒有發(fā)生數(shù)據(jù)失效.在模型中，由引理2可知，在發(fā)生了1個(gè)節(jié)點(diǎn)失效時(shí)，剩余節(jié)點(diǎn)存儲的數(shù)據(jù)仍然是完整的，也沒有發(fā)生數(shù)據(jù)失效.

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

2.2 數(shù)據(jù)恢復(fù)模型

約束2 在進(jìn)行基于分布式存儲模型的數(shù)據(jù)恢復(fù)模型推導(dǎo)時(shí)，令分布式存儲模型中的p=1，參見引理2.

只考慮靜態(tài)節(jié)點(diǎn)失效是不完備的，當(dāng)有節(jié)點(diǎn)失效時(shí)為了保證數(shù)據(jù)的完整性，應(yīng)該立即選取新的節(jié)點(diǎn)，將失效節(jié)點(diǎn)的數(shù)據(jù)恢復(fù)到新節(jié)點(diǎn)，以此提升數(shù)據(jù)存儲的可靠性.如圖1(a)所示，雙副本存儲，當(dāng)副本2的存儲節(jié)點(diǎn)失效時(shí)，從副本1向新節(jié)點(diǎn)恢復(fù)數(shù)據(jù)，這里M為數(shù)據(jù)量，V為速度(約束1)，恢復(fù)時(shí)間為T.

圖1 雙副本存儲數(shù)據(jù)恢復(fù)與數(shù)據(jù)失效Fig.1 Double replica storage retrieved and data failure

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

雙副本存儲數(shù)據(jù)失效概率:在數(shù)據(jù)中心存在的情況下，對于雙副本存儲，如果有1個(gè)節(jié)點(diǎn)失效，則立即進(jìn)行數(shù)據(jù)恢復(fù)，那么當(dāng)在恢復(fù)期內(nèi)[t0，t1]，時(shí)間長度為T，如果另1個(gè)副本節(jié)點(diǎn)發(fā)生失效，則會造成數(shù)據(jù)失效，如圖1(b)所示.顯然如果引入數(shù)據(jù)恢復(fù)動(dòng)態(tài)行為，那么對于雙副本發(fā)生數(shù)據(jù)失效的概率如下:

式中:α為失效概率，θ為數(shù)據(jù)恢復(fù)時(shí)間長度T與失效單位時(shí)間tr(定義8)的比值，由于單位時(shí)間的節(jié)點(diǎn)失效概率為F，那么

表示θ個(gè)單位時(shí)間發(fā)生節(jié)點(diǎn)失效的概率，即在T內(nèi)發(fā)生數(shù)據(jù)失效的概率.

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

由分布式存儲模型可知采用k個(gè)節(jié)點(diǎn)存儲，總數(shù)據(jù)量為2倍副本2M，則每個(gè)節(jié)點(diǎn)存儲數(shù)據(jù)為2M/k，從k個(gè)節(jié)點(diǎn)并行傳輸?shù)乃俣葹長k-1，則恢復(fù)時(shí)間:

顯然如果分布式存儲模型存儲，在任意區(qū)間[t0，t1]，時(shí)間長度為 T'內(nèi)，當(dāng)有 0或 1個(gè)節(jié)點(diǎn)失效時(shí)，不會出現(xiàn)數(shù)據(jù)失效，如圖2(b).那么在[t0，t1]內(nèi)，任意1個(gè)節(jié)點(diǎn)發(fā)生失效的概率f如下

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

式中:β表示數(shù)據(jù)失效概率，k為節(jié)點(diǎn)數(shù).

圖2 模型存儲數(shù)據(jù)恢復(fù)與數(shù)據(jù)失效Fig.2 The model of data retrieved and data failure

證畢.

3 數(shù)據(jù)恢復(fù)模型特性分析

從數(shù)據(jù)恢復(fù)模型的構(gòu)建過程可以看出，模型是動(dòng)態(tài)的，在動(dòng)態(tài)基礎(chǔ)上給出了數(shù)據(jù)失效概率，并且其性能受到Sk的影響.在互聯(lián)網(wǎng)上同一個(gè)節(jié)點(diǎn)在從多個(gè)節(jié)點(diǎn)進(jìn)行并行數(shù)據(jù)傳輸時(shí)，所能得到的帶寬與并行數(shù)不成正比，如果客戶端帶寬較高，一般情況下在合理的并行數(shù)內(nèi)，帶寬會隨著并行數(shù)呈現(xiàn)出一定的上升趨勢.

那么數(shù)據(jù)恢復(fù)模型與雙副本存儲2種方式帶來的數(shù)據(jù)失效概率之間的理論關(guān)系，以及數(shù)據(jù)恢復(fù)模型與Sk之間的理論關(guān)系需要仔細(xì)分析.

3.1 β與α的比較

定理2 對于數(shù)據(jù)恢復(fù)模型公式(7)，當(dāng)θ，F(xiàn)，k一定時(shí)，β為Sk-1的單調(diào)減函數(shù).

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

β的一階導(dǎo)數(shù)小于0，所以β為Sk-1的單調(diào)減函，證畢.

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

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

圖3 β與S的關(guān)系Fig.3 Relation of β and S

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

根據(jù)定理2，當(dāng) θ，F(xiàn)，k一定時(shí)，β 為 Sk-1的單調(diào)減函數(shù)，因此可以先令不等式(9)為1個(gè)等式，求出邊界值，只要不等式的Sk-1大于根據(jù)等式求解出的Sk-1' ，就可以滿足β＜α.

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

表1 β=α?xí)rS的取值Table 1 The value when β=α

圖4 β=α?xí)rS的取值Fig.4 S value when the β = α

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

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

3.2 β 與 S、k、θF 的關(guān)系

用戶在從多節(jié)點(diǎn)進(jìn)行并行傳輸時(shí)，隨著并行數(shù)的增加，速度增加呈現(xiàn)緩降趨勢.而數(shù)據(jù)恢復(fù)模型需要從k-1個(gè)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)恢復(fù)，在這種情況失效概率呈現(xiàn)出怎樣的趨勢.

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

將式(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)逐漸增大時(shí)，β曲線的變化過程是:始終上升→先下降后上升(最低點(diǎn)逐漸右移，且曲線增幅逐漸減緩)→始終下降(下降趨勢逐漸增大).

結(jié)論:很顯然在實(shí)際的應(yīng)用中根據(jù)各種網(wǎng)絡(luò)情況，選擇β曲線最低點(diǎn)出現(xiàn)時(shí)k的取值作為數(shù)據(jù)恢復(fù)模型的參數(shù)效果最為理想，同時(shí)還必須保證β＜α.

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

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

3.3 網(wǎng)絡(luò)流量分析

定理3 在保證數(shù)據(jù)不失效的前提下，雙副本數(shù)據(jù)恢復(fù)與數(shù)據(jù)恢復(fù)模型2個(gè)動(dòng)態(tài)系統(tǒng)對網(wǎng)絡(luò)流量的影響是相同的.

證明:令時(shí)間跨度為T，節(jié)點(diǎn)在單位時(shí)間ts內(nèi)的失效概率為F，數(shù)據(jù)副本大小為M，模型采用k存儲.

1)對于雙副本，一個(gè)節(jié)點(diǎn)在時(shí)間T內(nèi)的期望失效次數(shù)為c1=T/ts，每次恢復(fù)傳輸數(shù)據(jù)量為M，則2個(gè)節(jié)點(diǎn)在T內(nèi)帶來的網(wǎng)絡(luò)流量為c1=2TM/ts.

2)對于恢復(fù)模型，由于采用雙副本，則總存儲數(shù)據(jù)量由定義6、引理2、約束2可知為2M，則每個(gè)節(jié)點(diǎn)存儲數(shù)據(jù)量為2M/k，則k個(gè)節(jié)點(diǎn)在T內(nèi)帶來的網(wǎng)絡(luò)流量可以表示為，證畢.

結(jié)論:數(shù)據(jù)恢復(fù)模型并沒有節(jié)省網(wǎng)絡(luò)流量，但是其使得數(shù)據(jù)失效概率明顯降低.

4 實(shí)驗(yàn)

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

4.1 數(shù)據(jù)觀測

1)數(shù)據(jù)交換中心為教育網(wǎng)內(nèi)普通PC節(jié)點(diǎn)，數(shù)據(jù)存儲節(jié)點(diǎn)分別位于如下主機(jī).采用網(wǎng)絡(luò)探測工具探測本地速度最大為157 kB，實(shí)測數(shù)據(jù)如表3.

表3 普通PC機(jī)作為數(shù)據(jù)交換中心獲得的單節(jié)點(diǎn)傳輸實(shí)測數(shù)據(jù)Table 3 Single node transmission measurement data by using PC as data excharge center

取上述各平均速度的平均值作為從一個(gè)節(jié)點(diǎn)傳輸數(shù)據(jù)的速度，為117 kB，即V=L1=117.

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

表4 普通PC機(jī)作為數(shù)據(jù)交換中心獲得的多節(jié)點(diǎn)并行傳輸實(shí)測數(shù)據(jù)Table 4 Multi node parallel transmission measurement data by using PC as data exchange center

表5 3G無線網(wǎng)絡(luò)的筆記本作為數(shù)據(jù)交換中心獲得的單節(jié)點(diǎn)傳輸實(shí)測數(shù)據(jù)Table 5 Single node transmission measurement data by using 3G wireless network notebook as data exchange center

表6 企業(yè)內(nèi)部服務(wù)器作為數(shù)據(jù)交換中心獲得的單節(jié)點(diǎn)傳輸實(shí)測數(shù)據(jù)Table 6 Single node transmission measurment data by using enterprise internal server as data exchange center

3)上述的數(shù)據(jù)存儲節(jié)點(diǎn)本身帶寬較大，而數(shù)據(jù)交換中本身帶寬較小(尤其在教育網(wǎng)內(nèi)時(shí)).

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

4.2 數(shù)據(jù)分析

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

表7 β數(shù)值Table 7 The value of β

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

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

從前2個(gè)實(shí)驗(yàn)可以看出，數(shù)據(jù)中心的本身帶寬較小，導(dǎo)致了數(shù)據(jù)恢復(fù)模型的性能只是略好于雙副本數(shù)據(jù)恢復(fù)策略.而在實(shí)驗(yàn)3中，由于數(shù)據(jù)交換中心的節(jié)點(diǎn)位于帶寬較高的聯(lián)通公司內(nèi)部，而數(shù)據(jù)節(jié)點(diǎn)為普通用戶PC和普通寬帶網(wǎng)絡(luò)，所以可以看出隨著k的增加α/β一直升高，相應(yīng)的β一直降低.

實(shí)驗(yàn)(3)充分說明了，2.2節(jié)中提出的以可靠性較高、帶寬較大的節(jié)點(diǎn)作為數(shù)據(jù)交換中心策略的實(shí)用性和正確性.

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

4.3 實(shí)驗(yàn)小結(jié)

圖5 3種β的第一個(gè)拐點(diǎn)分析Fig.5 Three β analysis of the first inflection point

如果數(shù)據(jù)中心帶寬較大，則可以將數(shù)據(jù)恢復(fù)模型中的k值適當(dāng)放大，但是也要考慮到數(shù)據(jù)中心網(wǎng)絡(luò)擁塞使帶寬極度降低的情況，這樣將導(dǎo)致并行恢復(fù)速度較慢，使數(shù)據(jù)失效概率增大.從實(shí)驗(yàn)結(jié)果看，在一般情況下數(shù)據(jù)恢復(fù)模型均能使數(shù)據(jù)的失效概率小于雙副本存儲恢復(fù)機(jī)制.

5結(jié)論

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

[1]陳貴海，吳帆，李宏興.基于DHT的P2P系統(tǒng)中高可用數(shù)據(jù)冗余機(jī)制[J].計(jì)算機(jī)學(xué)報(bào)，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]曲明成，吳翔虎，廖明宏，等.一種數(shù)據(jù)網(wǎng)格容災(zāi)存儲模型及其數(shù)據(jù)失效模型[J].電子學(xué)報(bào)，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.