去中心化存儲下分布式低帶寬多節點修復方法

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

(四川師范大學 計算機科學學院，成都 610101)

1 引 言

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

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

當節點失效時，為了降低修復帶寬、減少修復時間，主要從編碼結構、數據傳輸模式進行改進[9].因去中心化存儲下網絡結構的變化和節點的不穩定性，導致糾刪碼已從分布式存儲下的高碼率轉化成低碼率，單節點修復轉化成多節點修復，所以本文主要優化糾刪碼在多節點修復的數據傳輸.

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

針對目前糾刪碼的數據修復傳輸方法在去中心化系統多節點修復中存在修復成本高和修復效率低的問題，本文提出一種基于去中心化存儲的分布式低帶寬多節點修復方法DSMR(Distributed Structure Based Multinode Repair).

2 糾刪碼

糾刪碼是一種數據冗余備份機制，因其具有高可靠性和低存儲空間等性質，常被部署在各類存儲系統中以保證數據的可靠性.

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

2.1 糾刪碼的編碼原理

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

(1)

2.2 糾刪碼的修復原理

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

(2)

3 分布式低帶寬多節點修復方法

本節首先介紹分布式低帶寬多節點修復模型DSMR，主要闡述系統中節點的不同特征和多節點修復的四大步驟；然后詳細描述DSMR的重要算法，包括節點選擇算法和數據傳輸算法.

3.1 DSMR修復模型

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

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

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

當m個節點失效時，系統啟動DSMR多節點修復模型，具體分為如下4步：

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

(3)

2)數據下載計算：每個新替代節點Yi(i=1,…,m)下載提供節點X′j(j=1,…,qi)的全部數據C′j(j=1,…,qi)和編碼塊對應的修復逆矩陣系數(ω1ω2…ωk)，如式(4)所示，計算得到m份與m個失效節點相關的數據集pi,u；

(4)

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

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

(5)

在整個DSMR修復過程中，我們發現節點的不同選擇方式和數據的網絡傳輸結構會影響去中心化存儲系統下的多節點修復性能.因此，本文通過分析去中心化存儲系統中節點特性和網絡結構，提出以最大化節點帶寬的節點選擇算法、以最大化數據傳輸效率的數據傳輸算法來提高系統修復性能.

3.2 DSMR的節點選擇

在去中心化存儲系統中，節點選擇會影響數據修復性能的因素主要包括：一是節點負載，包括節點所承受的計算和存儲負載；二是帶寬大小，節點能為數據傳輸提供的帶寬；三是網絡跳數，節點之間的物理鏈路數目；四是節點穩定性，節點發生失效的頻率.由于去中心化系統網絡的實時變化，從而導致節點負載和帶寬大小也發生變化，如果選取這兩點作為節點選擇算法的標準，使得節點選擇算法也需實時計算，會額外增加了存儲系統的開銷.其實可用網絡距離表來衡量節點間的網絡跳數[15]，而且節點間的可用帶寬關系也可通過網絡跳數來表示.因為大部分存儲系統的網絡結構都采用樹形拓撲來實現節點之間的通信，而一般在低層次交換機上的節點更少，高層次交換機上的節點更多，所以在同等帶寬網絡狀態下，節點通過均分占有網絡帶寬，那么低層次交換機的節點實現通信的帶寬就更大，需要跳轉的網絡距離也就越短，從而節點間的網絡跳數也就更小.因此，節點間的帶寬較小，則網絡跳數越大；反之，節點間的帶寬較大，則網絡跳數越小.此外，與分布式存儲系統對比，顯然在去中心化存儲系統中的節點穩定性更低，從而導致節點存儲數據塊更容易發生短暫或長久性丟失.為降低節點通信次數和節點修復重傳頻率，可通過BitSwap協議表[16]來衡量節點穩定性高低.對于樂于分享數據，上傳數據量大，存儲貢獻大，節點通信次數多的這一類節點，可定為高穩定性節點.反之，對于僅僅下載數據，無過多存儲貢獻，節點通信次數少的這一類節點，可定為低穩定性節點.

因此在DSMR修復過程中，可依據“網絡跳數”和“節點穩定性”兩個指標選擇節點：新替代節點和提供者節點，以減少去中心化系統的網絡負載和修復時間，具體如算法1所示.

算法1.選擇節點算法

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

輸出：新替代節點newreplaces；提供者節點providers；分組連接提供節點列表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的節點選擇算法主要分析去中心化存儲系統節點的具體作用，用節點穩定性來確定新替代節點、用網絡跳數來確定提供者節點，以提高系統存儲數據的穩定性、縮短修復數據的路徑長短.

3.3 DSMR的數據傳輸

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

算法2.數據傳輸算法

輸入：已選擇新替代節點列表newreplaces；分組連接提供節點列表linkList

輸出：修復塊(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

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

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

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

圖2 DSMR數據傳輸示意圖

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

在DSMR修復過程中，利用分組傳輸和計算交互的方法極大地降低了去中心化存儲系統中多節點修復帶寬過高的問題.通過選擇節點分組連接、數據下載計算、節點交互傳輸和計算恢復數據四個步驟完成了分布式低帶寬多節點修復.

4 對比分析結果

本節先通過理論分析SSR、TERS和DSMR多節點修復模型的存儲開銷和修復帶寬；再以實驗方式測試多節點修復過程中的平均修復時間，通過失效節點數、條帶數和碼率系數三方面來對比DSMR與其他典型修復方法的性能以驗證在多節點修復過程中的優勢.

4.1 理論對比

在多節點修復過程中，影響RS碼在去中心化系統中應用的兩個因素分別是存儲成本和修復成本.控制編碼的存儲成本是所有存儲系統的標準要求之一，越低的存儲成本能直接降低系統成本，而較少的修復帶寬開銷能降低系統網絡負載、增強系統穩定性.而RS碼的多節點修復包括數據傳輸和數據計算.

數據傳輸：隨著去中心化系統的逐漸發展，用戶的不斷加入，那么系統的數據容量也就逐漸增多，從而導致平均節點數據失效次數變大.當修復過程中需傳輸大量數據時，頻繁的操作則會影響去中心化存儲系統中的數據訪問效率，造成網絡資源緊缺.

數據計算：在多節點修復過程中包括不同計算步驟.對比單節點串行修復方式和多節點集中式修復方式，DSMR主要通過并行傳輸計算和數據交互計算來修復所有失效節點.因為在多節點失效修復中節點的數據計算存在重疊，DSMR可通過分組連接數據塊與相應系數并行計算從而提高數據的計算效率.此外，DSMR修復能大幅度減少數據傳輸量，因為m個新替代節點共下載k個數據塊即可修復，同時新替代節點間只需傳輸m個中間計算結果.

具體來講，三種修復方法的存儲成本和修復成本對比，如表1所示.

表1 修復方法的存儲成本和修復成本對比

Table 1 Repair methods of storage and repair costs

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

1)SSR：在串行星型修復中，當m個節點失效后，每個新替代節點從k個提供者節點下載k份數據塊來修復，其中每個節點的數據存儲量為α，每個失效塊修復帶寬為kα，而SSR 以串行方式逐漸修復m個失效塊.因此SSR的存儲開銷為nα，修復m個塊的總帶寬開銷為ΦSSR=mkα.

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

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

綜上對比可知，在去中心化存儲系統的RS(n，k，m)編碼中，SSR、TERS和DSMR的存儲開銷保持不變；在多節點修復過程中，DSMR采用分組并行交互修復方法，使得總的帶寬開銷最小，即平均修復一個數據塊所傳輸的數據量最小.

4.2 實驗對比

實驗基于NS3事件驅動模擬器，模擬一個去中心化存儲系統，由一系列不同網絡帶寬和穩定性的節點組成.實驗目標是選擇在不同RS編碼參數下關注DSMR與其他典型修復方法在修復時間方面的對比.由于在去中心化存儲中會設置不同失效塊閾值來判斷是否啟動修復，因此選取平均修復時間t來評判修復方法的優劣.

實驗考慮一種混合計時器/閾值(T/TH)策略來模擬去中心化存儲下啟動修復的方式.根據以下情況觸發修復操作規則：

1)當一個節點失效并且可用節點數e較小或等于TH：e≤TH→立即執行已失效塊的修復.

2)當一個節點失效并且e>TH→等待時間T時，如果失效節點仍然不可用，則轉向判斷條件1.

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

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

圖3 失效節點數m和條帶數s變化的平均修復時間對比

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

綜上對比可知，在任意條帶數、失效節點數和碼率系數的變化情況下，DSMR的平均修復時間t始終在三種修復方法中保持最少.

圖4 失效節點數m和碼率系數l變化的平均修復時間對比

5 總 結

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