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

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

0 引 言

作為云計算基礎(chǔ)的大規(guī)模分布式容錯存儲系統(tǒng)[1,2]，采用糾刪碼作為數(shù)據(jù)冗余技術(shù)能比多副本技術(shù)以更低的存儲開銷獲得相同的數(shù)據(jù)可靠性。例如Google文件系統(tǒng)[3]部署RS(9,6)碼、Baidu Atlas云平臺[4]部署RS(12,8)碼、Facebook 存儲系統(tǒng)[5]部署RS(14,10)碼，Hadoop分布式文件系統(tǒng)[6]則提供多種參數(shù)的RS (n,k) 碼，以供用戶選擇。在分布式存儲系統(tǒng)中，節(jié)點失效是一種常態(tài)。比如在Facebook的3000個節(jié)點生產(chǎn)集群中，每天發(fā)生高達20個或更多節(jié)點故障[7,8]，從而觸發(fā)修復(fù)作業(yè)，導(dǎo)致修復(fù)帶寬占比高達10%-20%。過高的修復(fù)帶寬使得糾刪碼技術(shù)在實際中的應(yīng)用受到限制，所以如何降低修復(fù)帶寬問題成為糾刪碼的研究熱點之一[9,10]。

Reed-Solomon碼[11]常常是分布式存儲系統(tǒng)的標準設(shè)計選擇，但是其高昂的修復(fù)成本被認為是高存儲效率和高可靠性不可避免的代價。為降低修復(fù)成本，Rashmi等提出了Piggybacking設(shè)計框架，保證在較低的存儲開銷下，進一步減少修復(fù)帶寬；Rashmi等對Piggybacking框架進一步完善補充[12]?；赑iggybacking框架，Rashmi等又提出了一種在工程中易于實現(xiàn)的雙條帶結(jié)構(gòu)Hitchhiker碼[13]。Hitchhiker碼不僅具有RS碼的通用性，同時適用于各種 (n,k) 參數(shù)配置，在Facebook存儲系統(tǒng)和Hadoop分布式系統(tǒng)中已部署實現(xiàn)。

本文基于Hitchhiker碼，提出一種結(jié)合不同參數(shù) (n,k) 值動態(tài)選擇的數(shù)據(jù)分配算法DSDA(dynamic selection of data allocation algorithm)，構(gòu)造出一種最優(yōu)分配的OHitchhiker碼，可以針對不同 (n,k) 值選擇具有最小修復(fù)代價的編碼結(jié)構(gòu)，進一步降低下載帶寬。

1 相關(guān)工作

本文定義了如下參數(shù)，見表1。

表1 參數(shù)

糾刪碼可通過 (n,k) 兩個參數(shù)表示，其包含編碼、解碼兩個過程。編碼是指通過k個數(shù)據(jù)塊 {A1,…,Ak} 計算產(chǎn)生n個塊 {C1,…,Cn}。 解碼是指當 {C1,…,Cn} 中不大于n-k個塊失效時，則可任選其中k個未失效的塊，計算恢復(fù)失效塊數(shù)據(jù)。分布式系統(tǒng)中使用的糾刪碼通常滿足兩個性質(zhì)：①最大距離可分性(MDS性質(zhì))，即能實現(xiàn)所需的容錯基礎(chǔ)上保證存儲冗余也最?。虎谙到y(tǒng)性，即編碼后的n個節(jié)點中，有k個節(jié)點存儲原始數(shù)據(jù)，則r個節(jié)點存儲校驗數(shù)據(jù)。

通常，我們將n個節(jié)點(數(shù)據(jù)節(jié)點和校驗節(jié)點)統(tǒng)稱為一個條帶，條帶中的節(jié)點將會被分到不同的機架(如存儲服務(wù)器)上去分布式存儲。由于數(shù)據(jù)的分布式存儲，導(dǎo)致節(jié)點故障頻率增高，修復(fù)過程也就頻繁發(fā)生。所謂的修復(fù)過程，傳統(tǒng)的糾刪碼在分布式存儲系統(tǒng)環(huán)境中不是最優(yōu)的：因為當一個節(jié)點失效時，通常會從存儲在該節(jié)點中的每個子條帶中丟失一個塊。以RS碼和Hitchhiker碼為例進行分析，Hitchhiker碼編碼思想：在雙條帶RS碼上利用異或操作將第一子條帶原始數(shù)據(jù)塊 {a1,…,ak} 附加在第二子條帶的校驗數(shù)據(jù)塊上，以此減少修復(fù)成本。Hitchhiker碼主要采用均分的數(shù)據(jù)分配思想。由于數(shù)據(jù)分配算法的不同，Hitchhiker碼可細分為兩種：Hitchhiker-XOR碼和Hitchhiker-XOR+碼。

當一個系統(tǒng)節(jié)點Nodei失效時，3種碼的修復(fù)下載量：雙條帶RS碼需要下載2k個數(shù)據(jù)塊；當Nodei中ai∈Sj,(i=1,…,k),(j=1,…,r-1)， Hitchhiker-XOR碼和Hitchhiker-XOR+碼都需要下載k+|Sr| 個數(shù)據(jù)塊；當Nodei中ai∈Sr時，Hitchhiker-XOR+碼則需要下載k+|Sr|+r-2個數(shù)據(jù)塊。

以參數(shù) (n,k)=(13,10) 為例，當節(jié)點Node8失效時，此時RS碼、Hitchhiker-XOR和Hitchhiker-XOR+碼的修復(fù)下載情況，如圖1所示。

圖1 (n,k)=(13,10) 3種糾刪碼

從圖1中可以發(fā)現(xiàn)，Hitchhiker-XOR碼將原數(shù)據(jù)塊 {a1,…,a10} 均分成2份，其分塊情況S={5,5}， 其中S1={a1,…,a5},S2={a6,…,a10}， Hitchhiker-XOR+碼則分成3份，分塊情況S={4,4,2}， 其中S1={a1,a2,a3,a4},S2={a5,a6,a7,a8},S3={a9,a10}。 由于不同的編碼結(jié)構(gòu)，系統(tǒng)節(jié)點修復(fù)帶寬存在差異。

2 OHitchhiker碼

本文提出一種最優(yōu)分配的OHitchhiker編碼，通過在編碼的分配環(huán)節(jié)引入一種高效的動態(tài)算法，使得OHitchhiker編碼可以針對不同 (n,k) 值選擇具有最小修復(fù)代價的編碼結(jié)構(gòu)。

2.1 動態(tài)選擇的數(shù)據(jù)分配算法

根據(jù)數(shù)學推理和OHitchhiker碼的特征，本文提出了動態(tài)選擇的數(shù)據(jù)分配算法DSDA(dynamic selection of data allocation algorithm)。DSDA執(zhí)行兩步分配：均分分配和移動分配。

為了更好地描述根據(jù)不同(n,k)值來動態(tài)選擇最優(yōu)的分配，現(xiàn)引入兩個參數(shù)q和p， 其中q表示商，即q=k/r；p表示余數(shù)，即p=k%r。

均分分配：將原始數(shù)據(jù)塊 {a1,…,ak} 劃分成r份，每一份存放的數(shù)據(jù)塊數(shù)為ti=q,(i=1,…,r)； 當k不能整除r時，將余下數(shù)據(jù)塊存放到第r份中，即tr=q+p。 分塊情況S={|S1|,…,|Sr|}; 其中 |Si|=ti,(i=1,…,r-1),|Sr|=tr。 此時系統(tǒng)節(jié)點數(shù)據(jù)aj和bj,(j=1,…,k) 的修復(fù)下載量為

(1)

此時系統(tǒng)節(jié)點的平均修復(fù)數(shù)據(jù)下載量為

(2)

將兩者的平均修復(fù)數(shù)據(jù)下載量相減，得到

(3)

當Δβsys>0時，即表示移動后的下載量更少，則需要移動分配，進一步降低修復(fù)成本。

移動分配：即當Δβsys>0時，則需要將Sr中的數(shù)據(jù)移動一塊到Si,(i=1,…,r-1) 中，再更新p=p-1， 循環(huán)m次移動后，直到Δβsys>0不滿足為止。最后得到分塊情況S={|S1|,…,|Sr|}; 其中|Si|=q+1, |Sj|=q， |Sr|=q+p-m,(i=1,…,m;j=m+1,…,r-1)。

根據(jù)以上原則，動態(tài)選擇數(shù)據(jù)分配算法DSDA的過程如算法1所示：①初始分塊，得到平均分塊數(shù)q和剩余分塊數(shù)p；②均分分配，將原數(shù)據(jù) {a1,…,ak} 劃分成r份；③移動分配，當Δβsys>0時，將Sr中的數(shù)據(jù)移一塊到Sj,(j=1,…,r-1) 中，更新p， 循環(huán)直到Δβsys≤0； ④分配結(jié)束，輸出分塊情況S。

算法1： 動態(tài)選擇的數(shù)據(jù)分配算法DSDA

輸入：k—數(shù)據(jù)節(jié)點

r—校驗節(jié)點數(shù)

輸出：

S—數(shù)據(jù)分配情況

過程：

步驟1 初始分塊：

q=k/r,p=k%r

步驟2 均分分配：

Foriin len (S)

Si←q

IFq>0 Then

Sr←q+p

步驟3 移動分配：

While Δβsys>0

Si←Sr,q--

步驟4 結(jié)束， 輸出S。

動態(tài)選擇數(shù)據(jù)分配算法DSDA緊密契合了OHitchhiker碼的雙條帶結(jié)構(gòu)特性，使得OHitchhiker碼在修復(fù)過程中首先實現(xiàn)全局均分分配，大幅度降低修復(fù)帶寬；然后通過不同 (n,k) 參數(shù)判斷執(zhí)行移動分配，達到最優(yōu)動態(tài)選擇模式，從而降低修復(fù)時所需的總數(shù)據(jù)下載量，保證系統(tǒng)節(jié)點的平均修復(fù)帶寬最低。

2.2 OHitchhiker編碼結(jié)構(gòu)

OHitchhiker碼繼承Hitchhiker碼的雙條帶結(jié)構(gòu)，利用異或操作將數(shù)據(jù)節(jié)點塊疊加在校驗節(jié)點上的方式，根據(jù)動態(tài)選擇的數(shù)據(jù)分配算法，將系統(tǒng)節(jié)點的修復(fù)成本降到最低。

OHitchhiker編碼過程分成如下3步：

(1)利用RS編碼，將原始k個數(shù)據(jù) {a1,…,ak} 進行編碼，計算產(chǎn)生r個校驗塊；然后將數(shù)據(jù)塊和校驗塊，共n個塊 {a1,…,ak,f1(a),…fr(a)} 分布式存儲在n個節(jié)點中，即為一個條帶；

(2)根據(jù)DSDA分配算法，首先均分分配，將原始數(shù)據(jù)塊 {a1,…,ak} 劃分成r份；然后根據(jù)式(3)判斷Δβsys， 當Δβsys>0時，進行移動分配；得到分塊情況S={|S1|,…,|Sr|}; 其中 |Si|=q+1,|Sj|=q， |Sr|=q+p-m,(i=1,…,m;j=m+1,…,r-1)；

(3)利用RS編碼生成兩個條帶拼接合成一個條帶，細分為第一子條帶 {a1,…,ak,f1(a),…fr(a)} 和第二子條帶 {b1,…,bk,f1(b),…fr(b)}。 通過將第一子條帶的系統(tǒng)節(jié)點數(shù)據(jù) {a1,…,ak} 分塊疊加在第二子條帶的校驗節(jié)點上 {f2(b),…fr(b)}。 為保證MDS性質(zhì)，第一個校驗節(jié)點中的數(shù)據(jù)不作修改。首先利用第一子條帶的數(shù)據(jù)分塊情況S， 將前r-1份數(shù)據(jù)Si,(i=1,…,r-1) 與第二子條帶中的后r-1 個校驗節(jié)點數(shù)據(jù)進行異或操作，更新保存到校驗節(jié)點中。然后將第r份數(shù)據(jù)Sr通過橫向減法原則間接保存在第一子條帶中的第二個校驗節(jié)點中，即第一子條帶的第二個校驗節(jié)點的數(shù)據(jù)減去同一節(jié)點的第二子條帶數(shù)據(jù)。

以O(shè)Hitchhiker碼 (n=13,k=10) 為例，編碼結(jié)構(gòu)如圖2所示。

圖2 OHitchhiker碼 (n=13,k=10) 的編碼結(jié)構(gòu)

2.3 OHitchhiker修復(fù)過程

當節(jié)點失效時，通過下載一定數(shù)據(jù)塊，利用MDS性質(zhì)計算恢復(fù)出節(jié)點數(shù)據(jù)，將失效的塊重新寫入，這個過程被稱為數(shù)據(jù)修復(fù)。OHitchhiker碼最多能容忍r個節(jié)點失效，而在分布式存儲系統(tǒng)中單節(jié)點失效占比高達90%，所以本文主要討論單節(jié)點失效而啟動修復(fù)的過程。

OHitchhiker碼的修復(fù)過程分成如下4步：假設(shè)節(jié)點Nodei失效，即數(shù)據(jù)ai,bi失效。

(1)下載第二子條帶中的數(shù)據(jù){b1,…,bk,f1(b)}/bi， 共k個數(shù)據(jù)，據(jù)MDS性質(zhì)，計算恢復(fù)出原數(shù)據(jù)bi。

(2)通過動態(tài)選擇數(shù)據(jù)分配算法DSDA生成分塊情況S， 判斷節(jié)點Nodei中ai屬于Sj,(j=1,…,r-1) 還是Sr。

(3)如果數(shù)據(jù)ai∈Sj,(j=1,…,r-1)， 即存放在第二個子條帶的校驗節(jié)點中。那么首先下載含有數(shù)據(jù)ai的校驗塊 [f2(b)⊕Sj]， 因為此時b已經(jīng)全都下載，那么線性組合f2(b) 也就得到；再下載{Sj}/ai， 共|Sj|-1個數(shù)據(jù)，相互異或恢復(fù)出數(shù)據(jù)ai； 此時共下載 |Sj| 個數(shù)據(jù)。

以O(shè)Hitchhiker碼 (n=13,k=10) 為例，當節(jié)點Node8失效時，修復(fù)過程如圖3所示。

圖3 OHitchhiker碼 (n=13,k=10) 的節(jié)點修復(fù)

3 實驗結(jié)果與分析

本文在HDFS-RAID[14]中實現(xiàn)OHitchhiker碼，通過插件方式將編碼加入HDFS中，此時的分布式容錯存儲系統(tǒng)稱為HDFS-OHitchhiker。根據(jù)實驗結(jié)果，對比分析OHitchhiker碼與RS碼、Hitchhiker-XOR碼和Hitchhiker-XOR+碼的平均修復(fù)帶寬、修復(fù)帶寬率和總修復(fù)下載量。

3.1 實驗環(huán)境

實驗通過部署分布式系統(tǒng)集群，集群由一個NameNode節(jié)點和19個DateNode節(jié)點組成。所有節(jié)點運行在Ubuntu16.04系統(tǒng)和JDK1.7.0_37中，其中每個節(jié)點配置兩個8核Intel 2.5 GHz處理器，48 G RAM，2T硬盤和 2 GB/s 以太網(wǎng)卡。

實驗數(shù)據(jù)為500個640M文件，保持默認HDFS的數(shù)據(jù)塊大小64 M，通過設(shè)置不同 (n,k) 參數(shù)和4種編碼策略(OHitchhiker碼、RS碼、Hitchhiker-XOR碼和Hitchhiker-XOR+碼)，將每個文件分塊編碼分布式存儲在DataNode節(jié)點中。

3.2 實驗分析

3.2.1 平均修復(fù)帶寬

為了更全面的比較，我們通過實驗計算并對比了滿足k∈{1,…,100},n∈{k+1,…,2k} 的所有取值下4種編碼的實際平均修復(fù)帶寬，發(fā)現(xiàn)OHitchhiker碼在所有 (n,k) 參數(shù)情況下都是最優(yōu)的。

表2 系統(tǒng)節(jié)點平均修復(fù)帶寬對比

3.2.2 修復(fù)帶寬率

當系統(tǒng)節(jié)點失效時，修復(fù)節(jié)點下載量占原數(shù)據(jù)總量的百分比，稱為修復(fù)帶寬率rsys

(4)

圖4描述在 (n,k)={(8,5),(9,6),(12,8)} 這3種取值下，Hitchhiker-XOR，Hitchhiker-XOR+和OHitchhiker碼之間的系統(tǒng)節(jié)點修復(fù)率對比圖，圖中的橫坐標表示參數(shù) (n,k)， 縱坐標表示系統(tǒng)節(jié)點的修復(fù)帶寬率。

圖4 Hitchhiker和OHitchhiker碼的修復(fù)率對比

從圖4中可以發(fā)現(xiàn)，OHitchhiker碼的系統(tǒng)節(jié)點修復(fù)率始終保持最低。在參數(shù)為 (n,k)=(8,5) 時，OHitchhiker碼的修復(fù)帶寬率相比于Hitchhiker-XOR碼降低了6%，與Hitchhiker-XOR碼則相同。在參數(shù)為 (n,k)=(9,6) 時，OHitchhiker碼的修復(fù)帶寬率相比于Hitchhiker-XOR碼和Hitchhiker-XOR+碼都降低了5.6%。在參數(shù)為 (n,k)=(12,8) 時，OHitchhiker碼的修復(fù)帶寬率相比于Hitchhiker-XOR和Hitchhiker-XOR+碼都降低1.6%。

3.2.3 總修復(fù)下載量

修復(fù)每個系統(tǒng)節(jié)點所需的下載量之和，稱為總修復(fù)下載量δsys

(5)

圖5(a)描述在保持總節(jié)點數(shù) (n=12) 不變的情況下，隨著校驗節(jié)點數(shù) (r=1,…,6) 增加，RS碼、Hitchhi-ker-XOR碼、Hitchhiker-XOR+碼和OHitchhiker碼之間的下載量對比折線圖。圖中橫坐標表示校驗節(jié)點數(shù)，縱坐標表示系統(tǒng)節(jié)點總修復(fù)下載量。

圖5 RS、Hitchhiker和OHitchhiker碼的總修復(fù)下載量對比

圖5(b)描述在保持校驗節(jié)點數(shù) (r=3) 不變的情況下，隨著總節(jié)點數(shù) (n=7,…,12) 增加，RS碼、Hitchhiker-XOR碼、Hitchhiker-XOR+碼和OHitchhiker碼之間的下載量對比折線圖。圖中橫坐標表示總節(jié)點數(shù)，縱坐標表示系統(tǒng)節(jié)點總修復(fù)下載量。

從圖5中可發(fā)現(xiàn)，隨著r的增加，RS碼、Hitchhiker-XOR碼、Hitchhiker-XOR+碼和OHitchhiker碼的修復(fù)下載量整體減少；隨著n的增加，RS碼、Hitchhiker-XOR碼、Hitchhiker-XOR+碼和OHitchhiker碼的修復(fù)下載量整體增加。所以不管是總節(jié)點還是校驗節(jié)點怎樣變化，相比于RS碼、Hitchhiker-XOR碼和Hitchhiker-XOR+碼，OHitchhiker碼的總修復(fù)下載量始終保持最低。

4 結(jié)束語

本文通過研究分布式存儲系統(tǒng)的Hitchhiker碼，在分析均分數(shù)據(jù)分配算法的基礎(chǔ)上，提出一種最優(yōu)分配的OHitchhiker碼。它可針對不同 (n,k) 值動態(tài)選擇最優(yōu)的數(shù)據(jù)分配算法，利用DSDA算法使得編碼結(jié)構(gòu)具有最小修復(fù)帶寬，進一步降低修復(fù)成本。理論分析及實驗結(jié)果表明，在任意 (n,k) 參數(shù)取值下，對比RS碼和Hitchhiker碼，OHitchhiker碼始終保持最低修復(fù)下載帶寬。

但是本文基于Pigyybacking框架下設(shè)計的OHitchhiker碼，只降低了系統(tǒng)節(jié)點失效時的修復(fù)下載帶寬；當校驗節(jié)點失效時，仍根據(jù)MDS性質(zhì)下載任意k個數(shù)據(jù)進行修復(fù)，沒有進行任何改進。下一步工作將關(guān)注校驗節(jié)點的修復(fù)過程，進一步減少校驗節(jié)點的修復(fù)下載帶寬。