去中心化存儲(chǔ)下分布式低帶寬多節(jié)點(diǎn)修復(fù)方法

李 慧，李貴洋，周 悅，江小玉，韓鴻宇

(四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，成都 610101)

1 引 言

隨著信息技術(shù)的不斷發(fā)展，如移動(dòng)互聯(lián)網(wǎng)、人工智能和虛擬現(xiàn)實(shí)等，這些技術(shù)在改變?nèi)祟惖恼J(rèn)知及生活方式地同時(shí)也產(chǎn)生了許多關(guān)于個(gè)人行為、活動(dòng)的信息.為了便于使用與研究，這些信息不僅被數(shù)字化地描述出來，而且被還持久化存儲(chǔ)下來.公共云存儲(chǔ)，正是一種存儲(chǔ)大量數(shù)據(jù)信息的方式，已經(jīng)被證明是大型集中式云提供商的一個(gè)有吸引力的業(yè)務(wù)模型[1].中心化存儲(chǔ)系統(tǒng)因其高效性和商用性而廣受歡迎，但仍存在成本較高、安全性低、隱私泄漏等問題.而去中心化存儲(chǔ)系統(tǒng)通過共享世界各地(個(gè)人/公司)的閑置硬盤與帶寬來組成去中心化的網(wǎng)絡(luò)，其基于區(qū)塊鏈技術(shù)天然的去中心化、開放、自治、匿名、可溯源、不可篡改等特性，從而真正改善“中心化存儲(chǔ)”問題[2].

目前主流去中心化的分布式存儲(chǔ)平臺(tái)有IPFS、Sia、Storj和MaidSafe等.對(duì)標(biāo)中心化云服務(wù)市場(chǎng)的份額大約在一萬億美金左右，預(yù)測(cè)基于區(qū)塊鏈技術(shù)的分布式存儲(chǔ)將是下一個(gè)千億級(jí)市場(chǎng)[3].如此龐大的市場(chǎng)和需求吸引各大企業(yè)投資，也成為學(xué)術(shù)研究熱點(diǎn)之一[4].而為保證數(shù)據(jù)的有效性和完整性，去中心化系統(tǒng)主要采用糾刪碼來減少存儲(chǔ)空間和網(wǎng)絡(luò)帶寬消耗.RS(Reed-Solomon)碼常常是去中心化存儲(chǔ)系統(tǒng)的選擇之一，如Stroj[5]部署RS(40，20)，Siacoin[6]部署RS(30，10)，而MaidSafe[7]和Filecoin[8]則采用是f(n，m)的計(jì)算方法.然而，在去中心化存儲(chǔ)系統(tǒng)的節(jié)點(diǎn)雖然擁有充足的存儲(chǔ)空間和CPU能力，但它們的網(wǎng)絡(luò)帶寬是有限的，所以研究如何降低糾刪碼修復(fù)時(shí)所占用的網(wǎng)絡(luò)資源對(duì)促進(jìn)糾刪碼在去中心化存儲(chǔ)下的應(yīng)用具有重要意義.

當(dāng)節(jié)點(diǎn)失效時(shí)，為了降低修復(fù)帶寬、減少修復(fù)時(shí)間，主要從編碼結(jié)構(gòu)、數(shù)據(jù)傳輸模式進(jìn)行改進(jìn)[9].因去中心化存儲(chǔ)下網(wǎng)絡(luò)結(jié)構(gòu)的變化和節(jié)點(diǎn)的不穩(wěn)定性，導(dǎo)致糾刪碼已從分布式存儲(chǔ)下的高碼率轉(zhuǎn)化成低碼率，單節(jié)點(diǎn)修復(fù)轉(zhuǎn)化成多節(jié)點(diǎn)修復(fù)，所以本文主要優(yōu)化糾刪碼在多節(jié)點(diǎn)修復(fù)的數(shù)據(jù)傳輸.

目前糾刪碼數(shù)據(jù)傳輸優(yōu)化修復(fù)方法主要有星型結(jié)構(gòu)[10](Star Structure Based Repair，SSR)和樹型結(jié)構(gòu)[11](Tree Structure Based Serial Repair，TSR)和集中式結(jié)構(gòu)[12](Traffic Efficient Repair Scheme for Multiple Failures，TERS).當(dāng)節(jié)點(diǎn)失效時(shí)，系統(tǒng)立即啟動(dòng)修復(fù)機(jī)制，首先需選擇其他可用節(jié)點(diǎn)(稱為新替代節(jié)點(diǎn))來存儲(chǔ)修復(fù)數(shù)據(jù)塊.為了修復(fù)出原始失效數(shù)據(jù)塊，新替代節(jié)點(diǎn)需從多個(gè)可用數(shù)據(jù)節(jié)點(diǎn)中(稱為提供者節(jié)點(diǎn))下載數(shù)據(jù)塊進(jìn)行計(jì)算修復(fù).在去中心化系統(tǒng)的多節(jié)點(diǎn)修復(fù)中，串行的星型結(jié)構(gòu)方式或并行的樹型結(jié)構(gòu)方式，并不能充分利用在修復(fù)多個(gè)失效數(shù)據(jù)塊中提供者節(jié)點(diǎn)之間的數(shù)據(jù)冗余性和計(jì)算冗余性；而集中式結(jié)構(gòu)的中心節(jié)點(diǎn)存在帶寬瓶頸，也沒有利用多節(jié)點(diǎn)修復(fù)并行處理方式，增加了多節(jié)點(diǎn)修復(fù)過程中的帶寬開銷，延長(zhǎng)了修復(fù)時(shí)間.

針對(duì)目前糾刪碼的數(shù)據(jù)修復(fù)傳輸方法在去中心化系統(tǒng)多節(jié)點(diǎn)修復(fù)中存在修復(fù)成本高和修復(fù)效率低的問題，本文提出一種基于去中心化存儲(chǔ)的分布式低帶寬多節(jié)點(diǎn)修復(fù)方法DSMR(Distributed Structure Based Multinode Repair).

2 糾刪碼

糾刪碼是一種數(shù)據(jù)冗余備份機(jī)制，因其具有高可靠性和低存儲(chǔ)空間等性質(zhì)，常被部署在各類存儲(chǔ)系統(tǒng)中以保證數(shù)據(jù)的可靠性.

糾刪碼通常用兩個(gè)參數(shù)(n，k)來表示，即先將原始數(shù)據(jù)M分成k份大小相等的數(shù)據(jù)塊D1,D2,…,Dk，再對(duì)這k個(gè)數(shù)據(jù)塊進(jìn)行線性組合編碼，最后生成n(n=k+r)個(gè)大小不變的編碼塊C1,C2,…,Cn，分別存儲(chǔ)到n個(gè)存儲(chǔ)節(jié)點(diǎn)(Node)上，即為一個(gè)條帶.當(dāng)原始?jí)K數(shù)k大于校驗(yàn)塊數(shù)r時(shí)，此碼為高碼率，即碼率系數(shù)(l=k/r)>1；反之為低碼率，即碼率系數(shù)(l=k/r)≤1.當(dāng)任意不大于r個(gè)存儲(chǔ)節(jié)點(diǎn)失效時(shí)，都可通過下載任意k份未失效節(jié)點(diǎn)數(shù)據(jù)來解碼恢復(fù)原始數(shù)據(jù)，該性質(zhì)被稱為MDS(maximum distance separable)屬性.

2.1 糾刪碼的編碼原理

目前在去中心化存儲(chǔ)系統(tǒng)中普遍采用的糾刪碼是線性RS碼.即每一個(gè)編碼塊Ci都是數(shù)據(jù)塊D1,D2,…,Dk的線性組合，如式(1)所示，其中系數(shù)矩陣G的大小為n×k，一般由范德蒙矩陣或柯西矩陣構(gòu)成，其中g(shù)ij∈Fq,(i=1,2,…,n,j=1,2,…,k)，而Fq則是大小為q的有限域(galois field).

(1)

2.2 糾刪碼的修復(fù)原理

當(dāng)節(jié)點(diǎn)Nodei失效時(shí)，節(jié)點(diǎn)Nodei存儲(chǔ)編碼塊Ci就丟失.為了修復(fù)失效編碼塊Ci，可以通過下載未失效編碼塊及組合系數(shù)，其中需要對(duì)編碼時(shí)的系數(shù)矩陣進(jìn)行求逆[13]，然后計(jì)算得到Ci的線性組合.對(duì)于RS碼而言，修復(fù)時(shí)需要下載任意k個(gè)未失效編碼塊C′1,C′2,…,C′k，求得編碼塊的修復(fù)逆矩陣系數(shù)(ω1ω2…ωk)，ωj∈Fq,(j=1,2,…,k)，計(jì)算得到與Ci內(nèi)容大小相同的編碼塊Hi，存儲(chǔ)在新替代節(jié)點(diǎn)Node′i中，如式(2)所示.

(2)

3 分布式低帶寬多節(jié)點(diǎn)修復(fù)方法

本節(jié)首先介紹分布式低帶寬多節(jié)點(diǎn)修復(fù)模型DSMR，主要闡述系統(tǒng)中節(jié)點(diǎn)的不同特征和多節(jié)點(diǎn)修復(fù)的四大步驟；然后詳細(xì)描述DSMR的重要算法，包括節(jié)點(diǎn)選擇算法和數(shù)據(jù)傳輸算法.

3.1 DSMR修復(fù)模型

DSMR修復(fù)模型在RS編碼基礎(chǔ)上，利用編碼在去中心化存儲(chǔ)系統(tǒng)下的低碼率和多節(jié)點(diǎn)修復(fù)性質(zhì)[14]，將傳統(tǒng)串行、集中式修復(fù)方式轉(zhuǎn)化成分布式修復(fù)方式，以減少網(wǎng)絡(luò)帶寬、降低修復(fù)時(shí)間.本文通過DSMR(n,k,m)模型來說明在去中心化存儲(chǔ)下RS碼的分布式低帶寬多節(jié)點(diǎn)修復(fù)，如圖1所示.

圖1 DSMR(n,k,m)修復(fù)模型圖

圖1中Src表示系統(tǒng)的根節(jié)點(diǎn)，完成文件編碼工作，包括文件分塊、數(shù)據(jù)編碼和節(jié)點(diǎn)分發(fā).具體先將原始數(shù)據(jù)文件M分成k個(gè)大小為α的數(shù)據(jù)塊，編碼產(chǎn)生n個(gè)相同大小數(shù)據(jù)塊X1,X2,…,Xn，再分發(fā)存儲(chǔ)在n個(gè)不同節(jié)點(diǎn)中.當(dāng)m個(gè)節(jié)點(diǎn)失效時(shí)，系統(tǒng)啟動(dòng)多節(jié)點(diǎn)修復(fù)，其中X1,X2,…,Xn-m表示未失效的數(shù)據(jù)節(jié)點(diǎn)，Y1,Y2,…,Ym表示m個(gè)新替代節(jié)點(diǎn)，βi,j表示提供節(jié)點(diǎn)Xi向新替代節(jié)點(diǎn)Yj傳輸?shù)臄?shù)據(jù)量，pi,j表示新替代節(jié)點(diǎn)Yi向新替代節(jié)點(diǎn)Yj傳輸?shù)臄?shù)據(jù)量.Des表示系統(tǒng)的目標(biāo)節(jié)點(diǎn)，通過下載任意k個(gè)節(jié)點(diǎn)數(shù)據(jù)，解碼計(jì)算得出原始數(shù)據(jù)M.

當(dāng)m個(gè)節(jié)點(diǎn)失效時(shí)，系統(tǒng)啟動(dòng)DSMR多節(jié)點(diǎn)修復(fù)模型，具體分為如下4步：

1)節(jié)點(diǎn)分組連接：系統(tǒng)首先找到m個(gè)新替代節(jié)點(diǎn)Y1,Y2,…,Ym.為了保證能完整修復(fù)失效節(jié)點(diǎn)數(shù)據(jù)，m個(gè)新替代節(jié)點(diǎn)一共需連接下載k個(gè)提供者節(jié)點(diǎn)數(shù)據(jù).那么每個(gè)替代節(jié)點(diǎn)Yi(i=1,…,m)通過均分分組連接qi個(gè)未失效的提供節(jié)點(diǎn)X′1,X′2,…,X′k，如式(3)所示，通過判斷k能否整除m來進(jìn)行分組；

(3)

2)數(shù)據(jù)下載計(jì)算：每個(gè)新替代節(jié)點(diǎn)Yi(i=1,…,m)下載提供節(jié)點(diǎn)X′j(j=1,…,qi)的全部數(shù)據(jù)C′j(j=1,…,qi)和編碼塊對(duì)應(yīng)的修復(fù)逆矩陣系數(shù)(ω1ω2…ωk)，如式(4)所示，計(jì)算得到m份與m個(gè)失效節(jié)點(diǎn)相關(guān)的數(shù)據(jù)集pi,u；

(4)

3)節(jié)點(diǎn)交互傳輸：新替代節(jié)點(diǎn)Yi(i=1,…,m)將中間結(jié)果pi,u(u=1,…,m)與其他新替代節(jié)點(diǎn)Yu進(jìn)行數(shù)據(jù)交互，即每個(gè)新替代節(jié)點(diǎn)Yi(i=1,…,m)將中間數(shù)據(jù)集pi,u(u=1,…,m)保留對(duì)應(yīng)的數(shù)據(jù)pi,i在本地，另外的m-1份數(shù)據(jù){pi,1,pi,2,…,pi,m}pi,i都傳輸給對(duì)應(yīng)的新替代節(jié)點(diǎn){Y1,Y2,…,Ym}Yi；

4)計(jì)算恢復(fù)數(shù)據(jù)：每個(gè)新替代節(jié)點(diǎn)Yi(i=1,…,m)將m份與失效節(jié)點(diǎn)相關(guān)的數(shù)據(jù)pu,i(u=1,…,m)進(jìn)行合并計(jì)算得到失效節(jié)點(diǎn)的編碼塊.即每個(gè)新替代節(jié)點(diǎn)將從其他新替代節(jié)點(diǎn)接收的數(shù)據(jù){p1,i,p2,i,…,pm,i}pi,i和自身保留的數(shù)據(jù)pi,i進(jìn)行合并，如式(5)所示，計(jì)算恢復(fù)出失效節(jié)點(diǎn)編碼塊Hi.

(5)

在整個(gè)DSMR修復(fù)過程中，我們發(fā)現(xiàn)節(jié)點(diǎn)的不同選擇方式和數(shù)據(jù)的網(wǎng)絡(luò)傳輸結(jié)構(gòu)會(huì)影響去中心化存儲(chǔ)系統(tǒng)下的多節(jié)點(diǎn)修復(fù)性能.因此，本文通過分析去中心化存儲(chǔ)系統(tǒng)中節(jié)點(diǎn)特性和網(wǎng)絡(luò)結(jié)構(gòu)，提出以最大化節(jié)點(diǎn)帶寬的節(jié)點(diǎn)選擇算法、以最大化數(shù)據(jù)傳輸效率的數(shù)據(jù)傳輸算法來提高系統(tǒng)修復(fù)性能.

3.2 DSMR的節(jié)點(diǎn)選擇

在去中心化存儲(chǔ)系統(tǒng)中，節(jié)點(diǎn)選擇會(huì)影響數(shù)據(jù)修復(fù)性能的因素主要包括：一是節(jié)點(diǎn)負(fù)載，包括節(jié)點(diǎn)所承受的計(jì)算和存儲(chǔ)負(fù)載；二是帶寬大小，節(jié)點(diǎn)能為數(shù)據(jù)傳輸提供的帶寬；三是網(wǎng)絡(luò)跳數(shù)，節(jié)點(diǎn)之間的物理鏈路數(shù)目；四是節(jié)點(diǎn)穩(wěn)定性，節(jié)點(diǎn)發(fā)生失效的頻率.由于去中心化系統(tǒng)網(wǎng)絡(luò)的實(shí)時(shí)變化，從而導(dǎo)致節(jié)點(diǎn)負(fù)載和帶寬大小也發(fā)生變化，如果選取這兩點(diǎn)作為節(jié)點(diǎn)選擇算法的標(biāo)準(zhǔn)，使得節(jié)點(diǎn)選擇算法也需實(shí)時(shí)計(jì)算，會(huì)額外增加了存儲(chǔ)系統(tǒng)的開銷.其實(shí)可用網(wǎng)絡(luò)距離表來衡量節(jié)點(diǎn)間的網(wǎng)絡(luò)跳數(shù)[15]，而且節(jié)點(diǎn)間的可用帶寬關(guān)系也可通過網(wǎng)絡(luò)跳數(shù)來表示.因?yàn)榇蟛糠执鎯?chǔ)系統(tǒng)的網(wǎng)絡(luò)結(jié)構(gòu)都采用樹形拓?fù)鋪韺?shí)現(xiàn)節(jié)點(diǎn)之間的通信，而一般在低層次交換機(jī)上的節(jié)點(diǎn)更少，高層次交換機(jī)上的節(jié)點(diǎn)更多，所以在同等帶寬網(wǎng)絡(luò)狀態(tài)下，節(jié)點(diǎn)通過均分占有網(wǎng)絡(luò)帶寬，那么低層次交換機(jī)的節(jié)點(diǎn)實(shí)現(xiàn)通信的帶寬就更大，需要跳轉(zhuǎn)的網(wǎng)絡(luò)距離也就越短，從而節(jié)點(diǎn)間的網(wǎng)絡(luò)跳數(shù)也就更小.因此，節(jié)點(diǎn)間的帶寬較小，則網(wǎng)絡(luò)跳數(shù)越大；反之，節(jié)點(diǎn)間的帶寬較大，則網(wǎng)絡(luò)跳數(shù)越小.此外，與分布式存儲(chǔ)系統(tǒng)對(duì)比，顯然在去中心化存儲(chǔ)系統(tǒng)中的節(jié)點(diǎn)穩(wěn)定性更低，從而導(dǎo)致節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)塊更容易發(fā)生短暫或長(zhǎng)久性丟失.為降低節(jié)點(diǎn)通信次數(shù)和節(jié)點(diǎn)修復(fù)重傳頻率，可通過BitSwap協(xié)議表[16]來衡量節(jié)點(diǎn)穩(wěn)定性高低.對(duì)于樂于分享數(shù)據(jù)，上傳數(shù)據(jù)量大，存儲(chǔ)貢獻(xiàn)大，節(jié)點(diǎn)通信次數(shù)多的這一類節(jié)點(diǎn)，可定為高穩(wěn)定性節(jié)點(diǎn).反之，對(duì)于僅僅下載數(shù)據(jù)，無過多存儲(chǔ)貢獻(xiàn)，節(jié)點(diǎn)通信次數(shù)少的這一類節(jié)點(diǎn)，可定為低穩(wěn)定性節(jié)點(diǎn).

因此在DSMR修復(fù)過程中，可依據(jù)“網(wǎng)絡(luò)跳數(shù)”和“節(jié)點(diǎn)穩(wěn)定性”兩個(gè)指標(biāo)選擇節(jié)點(diǎn)：新替代節(jié)點(diǎn)和提供者節(jié)點(diǎn)，以減少去中心化系統(tǒng)的網(wǎng)絡(luò)負(fù)載和修復(fù)時(shí)間，具體如算法1所示.

算法1.選擇節(jié)點(diǎn)算法

輸入：參數(shù)(n,k,m);待選擇新替代節(jié)點(diǎn)列表newreplaceList；待選擇提供者節(jié)點(diǎn)列表providerList

輸出：新替代節(jié)點(diǎn)newreplaces；提供者節(jié)點(diǎn)providers；分組連接提供節(jié)點(diǎn)列表linkList

forifrom 1 to 2m

newreplacei← random(newreplaceList)

computecomi

Y1,Y2,…,Ym← Arrays.sort(com1,com2,…,com2m)

newreplaces.add(Y1,Y2,…,Ym)

for eachnewreplaceiin newreplaces

forjfrom 1 tok

providerj← random(providerList)

X′1,X′2,…,X′qi←Arrays.sort(hopListi)

linkListi.add(X′1,X′2,…,X′qi)

provider.add(linkListi)

providerList.delete(X′1,X′2,…,X′qi)

DSMR的節(jié)點(diǎn)選擇算法主要分析去中心化存儲(chǔ)系統(tǒng)節(jié)點(diǎn)的具體作用，用節(jié)點(diǎn)穩(wěn)定性來確定新替代節(jié)點(diǎn)、用網(wǎng)絡(luò)跳數(shù)來確定提供者節(jié)點(diǎn)，以提高系統(tǒng)存儲(chǔ)數(shù)據(jù)的穩(wěn)定性、縮短修復(fù)數(shù)據(jù)的路徑長(zhǎng)短.

3.3 DSMR的數(shù)據(jù)傳輸

在去中心化存儲(chǔ)系統(tǒng)中，DSMR的數(shù)據(jù)傳輸主要分為兩步：一是提供者節(jié)點(diǎn)與新替代節(jié)點(diǎn)之間的數(shù)據(jù)傳輸，二是新替代節(jié)點(diǎn)之間的數(shù)據(jù)傳輸.由于在去中心化存儲(chǔ)系統(tǒng)中采用的是RS碼，因此提供者節(jié)點(diǎn)需將存儲(chǔ)全部數(shù)據(jù)傳輸給新替代節(jié)點(diǎn).為保證失效編碼塊的有效修復(fù)，利用MDS性質(zhì)可知，下載k個(gè)未失效編碼塊的全部數(shù)據(jù)都能修復(fù)得到失效塊數(shù)據(jù).因此，在DSMR修復(fù)過程中，m個(gè)新替代節(jié)點(diǎn)共同讀取k個(gè)提供者節(jié)點(diǎn)數(shù)據(jù)，然后每個(gè)新替代節(jié)點(diǎn)計(jì)算出m份中間結(jié)果進(jìn)行交互，最后合并恢復(fù)出每個(gè)失效節(jié)點(diǎn)的編碼塊，具體如算法2所示.

算法2.數(shù)據(jù)傳輸算法

輸入：已選擇新替代節(jié)點(diǎn)列表newreplaces；分組連接提供節(jié)點(diǎn)列表linkList

輸出：修復(fù)塊(H1,H2,…,Hm)

for eachnewreplaceiin newreplaces

for eachproviderjinlinkListi

Yi←C′j

forufrom 1 tom

for eachnewreplaceiin newreplaces

for eachnewreplaceuin newreplaces

ifi≠uthen

Yi←pu,i

for eachnewreplaceiin newreplaces

提供者節(jié)點(diǎn)與新替代節(jié)點(diǎn)之間的數(shù)據(jù)傳輸：每個(gè)替代節(jié)點(diǎn)Yi(i=1,…,m)通過連接qi個(gè)未失效的提供節(jié)點(diǎn)X′1,X′2,…,X′qi，并獲取節(jié)點(diǎn)存儲(chǔ)全部數(shù)據(jù)C′i.每個(gè)新替代節(jié)點(diǎn)接收完提供者節(jié)點(diǎn)的數(shù)據(jù)塊，即C′1,C′2,…,C′qi，然后通過修復(fù)操作得到m個(gè)失效塊的中間結(jié)果pi,u(u=1,…,m).

新替代節(jié)點(diǎn)之間的數(shù)據(jù)傳輸：每個(gè)新替代節(jié)點(diǎn)Yi(i=1,…,m)先將修復(fù)自身數(shù)據(jù)的中間塊pi,i存儲(chǔ)在當(dāng)前節(jié)點(diǎn)之中，再把剩下m-1個(gè)中間塊{pi,1,pi,2,…,pi,u}pi,i發(fā)給新替代節(jié)點(diǎn){Y1,Y2,…,Ym}Yi.每個(gè)新替代節(jié)點(diǎn)在收到其他新替代節(jié)點(diǎn)發(fā)來的所有中間塊數(shù)據(jù)pu,i(u=1,…,m)，最后進(jìn)行線性組合得到失效塊數(shù)據(jù)Hi.

DSMR的多節(jié)點(diǎn)數(shù)據(jù)修復(fù)傳輸模型，如圖2所示.其中，m個(gè)新替代節(jié)點(diǎn){Y1,…,Ym}與k個(gè)提供者節(jié)點(diǎn){X1,…,Xk}以并行模式進(jìn)行傳輸，與單節(jié)點(diǎn)SSR星型結(jié)構(gòu)不同的是，DSMR中的k個(gè)提供者節(jié)點(diǎn)只需要傳輸一次數(shù)據(jù)即可修復(fù)m個(gè)失效節(jié)點(diǎn)，大大減少了數(shù)據(jù)傳輸量.與多節(jié)點(diǎn)TERS集中結(jié)構(gòu)不同的是，DSMR中不存在中心節(jié)點(diǎn)，每個(gè)新替代節(jié)點(diǎn)均分連接提供者節(jié)點(diǎn)組進(jìn)行數(shù)據(jù)傳輸，節(jié)點(diǎn)相互不影響、可并行傳輸，降低數(shù)據(jù)傳輸時(shí)間和節(jié)點(diǎn)負(fù)載.由于新替代節(jié)點(diǎn)需要通過原始編碼塊計(jì)算出m個(gè)失效節(jié)點(diǎn)的中間結(jié)果，而TSR樹形結(jié)構(gòu)最大特點(diǎn)就是中間節(jié)點(diǎn)會(huì)進(jìn)行組合計(jì)算，這會(huì)導(dǎo)致傳輸?shù)脑紨?shù)據(jù)不完整，所以DSMR的數(shù)據(jù)傳輸不能使用樹形結(jié)構(gòu).

圖2 DSMR數(shù)據(jù)傳輸示意圖

在DSMR的數(shù)據(jù)傳輸過程中，每個(gè)提供者節(jié)點(diǎn)Xi將存儲(chǔ)的全部數(shù)據(jù)βi,j=α都發(fā)送給新替代節(jié)點(diǎn)Yj.新替代節(jié)點(diǎn)在計(jì)算失效數(shù)據(jù)塊時(shí)采用RS碼的計(jì)算修復(fù)方式，得到m個(gè)中間組合結(jié)果，從而新替代節(jié)點(diǎn)Yi向新替代節(jié)點(diǎn)Yj傳輸?shù)臄?shù)據(jù)量pi,j=1.因此在DSMR修復(fù)過程中，修復(fù)m個(gè)節(jié)點(diǎn)所需傳輸?shù)臄?shù)據(jù)量為kα+(m-1)m.

在DSMR修復(fù)過程中，利用分組傳輸和計(jì)算交互的方法極大地降低了去中心化存儲(chǔ)系統(tǒng)中多節(jié)點(diǎn)修復(fù)帶寬過高的問題.通過選擇節(jié)點(diǎn)分組連接、數(shù)據(jù)下載計(jì)算、節(jié)點(diǎn)交互傳輸和計(jì)算恢復(fù)數(shù)據(jù)四個(gè)步驟完成了分布式低帶寬多節(jié)點(diǎn)修復(fù).

4 對(duì)比分析結(jié)果

本節(jié)先通過理論分析SSR、TERS和DSMR多節(jié)點(diǎn)修復(fù)模型的存儲(chǔ)開銷和修復(fù)帶寬；再以實(shí)驗(yàn)方式測(cè)試多節(jié)點(diǎn)修復(fù)過程中的平均修復(fù)時(shí)間，通過失效節(jié)點(diǎn)數(shù)、條帶數(shù)和碼率系數(shù)三方面來對(duì)比DSMR與其他典型修復(fù)方法的性能以驗(yàn)證在多節(jié)點(diǎn)修復(fù)過程中的優(yōu)勢(shì).

4.1 理論對(duì)比

在多節(jié)點(diǎn)修復(fù)過程中，影響RS碼在去中心化系統(tǒng)中應(yīng)用的兩個(gè)因素分別是存儲(chǔ)成本和修復(fù)成本.控制編碼的存儲(chǔ)成本是所有存儲(chǔ)系統(tǒng)的標(biāo)準(zhǔn)要求之一，越低的存儲(chǔ)成本能直接降低系統(tǒng)成本，而較少的修復(fù)帶寬開銷能降低系統(tǒng)網(wǎng)絡(luò)負(fù)載、增強(qiáng)系統(tǒng)穩(wěn)定性.而RS碼的多節(jié)點(diǎn)修復(fù)包括數(shù)據(jù)傳輸和數(shù)據(jù)計(jì)算.

數(shù)據(jù)傳輸：隨著去中心化系統(tǒng)的逐漸發(fā)展，用戶的不斷加入，那么系統(tǒng)的數(shù)據(jù)容量也就逐漸增多，從而導(dǎo)致平均節(jié)點(diǎn)數(shù)據(jù)失效次數(shù)變大.當(dāng)修復(fù)過程中需傳輸大量數(shù)據(jù)時(shí)，頻繁的操作則會(huì)影響去中心化存儲(chǔ)系統(tǒng)中的數(shù)據(jù)訪問效率，造成網(wǎng)絡(luò)資源緊缺.

數(shù)據(jù)計(jì)算：在多節(jié)點(diǎn)修復(fù)過程中包括不同計(jì)算步驟.對(duì)比單節(jié)點(diǎn)串行修復(fù)方式和多節(jié)點(diǎn)集中式修復(fù)方式，DSMR主要通過并行傳輸計(jì)算和數(shù)據(jù)交互計(jì)算來修復(fù)所有失效節(jié)點(diǎn).因?yàn)樵诙喙?jié)點(diǎn)失效修復(fù)中節(jié)點(diǎn)的數(shù)據(jù)計(jì)算存在重疊，DSMR可通過分組連接數(shù)據(jù)塊與相應(yīng)系數(shù)并行計(jì)算從而提高數(shù)據(jù)的計(jì)算效率.此外，DSMR修復(fù)能大幅度減少數(shù)據(jù)傳輸量，因?yàn)閙個(gè)新替代節(jié)點(diǎn)共下載k個(gè)數(shù)據(jù)塊即可修復(fù)，同時(shí)新替代節(jié)點(diǎn)間只需傳輸m個(gè)中間計(jì)算結(jié)果.

具體來講，三種修復(fù)方法的存儲(chǔ)成本和修復(fù)成本對(duì)比，如表1所示.

表1 修復(fù)方法的存儲(chǔ)成本和修復(fù)成本對(duì)比

Table 1 Repair methods of storage and repair costs

修復(fù)方法存儲(chǔ)成本修復(fù)成本SSRnαmkαTERSnα(k+m-1)αDSMRnαkα+m(m-1)

1)SSR：在串行星型修復(fù)中，當(dāng)m個(gè)節(jié)點(diǎn)失效后，每個(gè)新替代節(jié)點(diǎn)從k個(gè)提供者節(jié)點(diǎn)下載k份數(shù)據(jù)塊來修復(fù)，其中每個(gè)節(jié)點(diǎn)的數(shù)據(jù)存儲(chǔ)量為α，每個(gè)失效塊修復(fù)帶寬為kα，而SSR 以串行方式逐漸修復(fù)m個(gè)失效塊.因此SSR的存儲(chǔ)開銷為nα，修復(fù)m個(gè)塊的總帶寬開銷為ΦSSR=mkα.

2)TERS：在多節(jié)點(diǎn)集中式修復(fù)中，所有m個(gè)失效塊都在新替代節(jié)點(diǎn)中選取中心節(jié)點(diǎn)完成修復(fù)，然后由中心節(jié)點(diǎn)傳輸已修復(fù)數(shù)據(jù)塊給其他新替代節(jié)點(diǎn)，所以中心節(jié)點(diǎn)與提供者節(jié)點(diǎn)之間的數(shù)據(jù)傳輸量和新替代節(jié)點(diǎn)之間的數(shù)據(jù)傳輸量都為α.因此，TERS的存儲(chǔ)開銷為nα，修復(fù)m個(gè)塊的總帶寬開銷為ΦTERS=(k+m-1)α.

3)DSMR：在分布式多節(jié)點(diǎn)修復(fù)中，當(dāng)m個(gè)節(jié)點(diǎn)失效后，m個(gè)新替代節(jié)點(diǎn)通過分組共連接k個(gè)提供者節(jié)點(diǎn)下載數(shù)據(jù)組合計(jì)算，然后節(jié)點(diǎn)間通過數(shù)據(jù)交互完成修復(fù).其中提供者節(jié)點(diǎn)向新替代節(jié)點(diǎn)傳輸數(shù)據(jù)為α，新替代節(jié)點(diǎn)之間傳輸?shù)臄?shù)據(jù)量為m-1.因此，DSMR的存儲(chǔ)開銷為nα，修復(fù)m個(gè)塊的總帶寬開銷為ΦDSMR=kα+m(m-1).

綜上對(duì)比可知，在去中心化存儲(chǔ)系統(tǒng)的RS(n，k，m)編碼中，SSR、TERS和DSMR的存儲(chǔ)開銷保持不變；在多節(jié)點(diǎn)修復(fù)過程中，DSMR采用分組并行交互修復(fù)方法，使得總的帶寬開銷最小，即平均修復(fù)一個(gè)數(shù)據(jù)塊所傳輸?shù)臄?shù)據(jù)量最小.

4.2 實(shí)驗(yàn)對(duì)比

實(shí)驗(yàn)基于NS3事件驅(qū)動(dòng)模擬器，模擬一個(gè)去中心化存儲(chǔ)系統(tǒng)，由一系列不同網(wǎng)絡(luò)帶寬和穩(wěn)定性的節(jié)點(diǎn)組成.實(shí)驗(yàn)?zāi)繕?biāo)是選擇在不同RS編碼參數(shù)下關(guān)注DSMR與其他典型修復(fù)方法在修復(fù)時(shí)間方面的對(duì)比.由于在去中心化存儲(chǔ)中會(huì)設(shè)置不同失效塊閾值來判斷是否啟動(dòng)修復(fù)，因此選取平均修復(fù)時(shí)間t來評(píng)判修復(fù)方法的優(yōu)劣.

實(shí)驗(yàn)考慮一種混合計(jì)時(shí)器/閾值(T/TH)策略來模擬去中心化存儲(chǔ)下啟動(dòng)修復(fù)的方式.根據(jù)以下情況觸發(fā)修復(fù)操作規(guī)則：

1)當(dāng)一個(gè)節(jié)點(diǎn)失效并且可用節(jié)點(diǎn)數(shù)e較小或等于TH：e≤TH→立即執(zhí)行已失效塊的修復(fù).

2)當(dāng)一個(gè)節(jié)點(diǎn)失效并且e>TH→等待時(shí)間T時(shí)，如果失效節(jié)點(diǎn)仍然不可用，則轉(zhuǎn)向判斷條件1.

對(duì)于每一組測(cè)試，條帶數(shù)s分別取1，2，4，6各做一組實(shí)驗(yàn)，以考察條帶數(shù)對(duì)測(cè)試結(jié)果的影響；失效節(jié)點(diǎn)數(shù)目m分別取2，4，6，8各做一組實(shí)驗(yàn)，以考察失效節(jié)點(diǎn)個(gè)數(shù)對(duì)測(cè)試結(jié)果的影響；編碼系數(shù)l(k/r)分別取1，0.8，0.5，0.3各做一組實(shí)驗(yàn)，以考察RS編碼參數(shù)對(duì)測(cè)試結(jié)果的影響.在NS3模擬器中，通過控制變量法來對(duì)比SSR、TSR和DSMR三種修復(fù)方法的平均修復(fù)時(shí)間t.

圖3表示在RS(n=30,k=10,r=20)時(shí)，失效節(jié)點(diǎn)數(shù)m和條帶數(shù)s變化的平均修復(fù)時(shí)間對(duì)比.從整體上看，在同等條帶數(shù)s下，隨著一個(gè)條帶中失效節(jié)點(diǎn)數(shù)m的不斷增加，DSMR的平均修復(fù)時(shí)間t也隨著減少.因?yàn)樵诰幋a參數(shù)(n,k)不變的情況下，失效節(jié)點(diǎn)數(shù)m越多，平均分組數(shù)也就越多，使得每個(gè)新替代節(jié)點(diǎn)連接提供者節(jié)點(diǎn)數(shù)也就越少，節(jié)省帶寬就越多，那么平均修復(fù)時(shí)間t也就減少.從局部上看，通過任意子圖可發(fā)現(xiàn)，隨著條帶數(shù)s的增加，DSMR的平均修復(fù)時(shí)間t也隨著減少.因?yàn)樵跅l帶數(shù)s較小時(shí)，修復(fù)過程中所需傳輸?shù)臄?shù)據(jù)總量也較少，沒有充分利用多節(jié)點(diǎn)并行修復(fù)效率.而隨著條帶數(shù)s的不斷增加，修復(fù)所需數(shù)據(jù)量不斷增多，整體的并行效率也就提高，那么平均修復(fù)時(shí)間t就逐漸減少.而隨著失效節(jié)點(diǎn)數(shù)m的增加、條帶數(shù)s的增加，SSR的平均修復(fù)時(shí)間保持不變且最多、TERS的平均修復(fù)時(shí)間隨著減少但緩慢.

圖3 失效節(jié)點(diǎn)數(shù)m和條帶數(shù)s變化的平均修復(fù)時(shí)間對(duì)比

圖4表示在RS(n=30,s=4)時(shí)，失效節(jié)點(diǎn)數(shù)m和碼率系數(shù)l變化的平均修復(fù)時(shí)間對(duì)比.從整體上看，隨著編碼系數(shù)l的減小，SSR、TERS和DSMR方法的修復(fù)時(shí)間t也隨之減少.因?yàn)楫?dāng)n不變時(shí)，編碼系數(shù)l變小時(shí)，意味著k就變小，那么新替代節(jié)點(diǎn)連接的節(jié)點(diǎn)數(shù)就更少，而節(jié)點(diǎn)之間傳輸數(shù)據(jù)量一樣.所以隨著k的減小，用以修復(fù)的數(shù)據(jù)總量也將減少，因此DSMR方法的平均修復(fù)時(shí)間t會(huì)隨著編碼系數(shù)l的減小而減少.從局部上看，當(dāng)編碼系數(shù)l相同時(shí)，隨著失效節(jié)點(diǎn)m的增大，TERS和DSMR的平均修復(fù)時(shí)間t逐漸減小，而SSR的平均修復(fù)時(shí)間t保持不變.

綜上對(duì)比可知，在任意條帶數(shù)、失效節(jié)點(diǎn)數(shù)和碼率系數(shù)的變化情況下，DSMR的平均修復(fù)時(shí)間t始終在三種修復(fù)方法中保持最少.

圖4 失效節(jié)點(diǎn)數(shù)m和碼率系數(shù)l變化的平均修復(fù)時(shí)間對(duì)比

5 總 結(jié)

針對(duì)RS碼的數(shù)據(jù)修復(fù)傳輸方法在去中心化系統(tǒng)多節(jié)點(diǎn)修復(fù)中存在修復(fù)成本高和修復(fù)效率低的問題，本文提出一種分布式低帶寬多節(jié)點(diǎn)修復(fù)方法DSMR.基于網(wǎng)絡(luò)跳數(shù)選擇穩(wěn)定性節(jié)點(diǎn)以充分利用去中心化存儲(chǔ)系統(tǒng)的節(jié)點(diǎn)可用帶寬，通過均分分組連接和并行數(shù)據(jù)傳輸來讀取節(jié)點(diǎn)數(shù)據(jù)，最后利用節(jié)點(diǎn)交互數(shù)據(jù)傳輸方法來修復(fù)多個(gè)失效塊.理論及實(shí)驗(yàn)結(jié)果表明，對(duì)比典型的編碼修復(fù)方法，在任意條帶數(shù)、失效節(jié)點(diǎn)數(shù)和碼率系數(shù)變化的情況下，DSMR方式保持較低存儲(chǔ)空間地同時(shí)進(jìn)一步降低修復(fù)帶寬、減少修復(fù)時(shí)間.