基于分布式存儲的OHitchhiker碼

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

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

0 引 言

作為云計算基礎的大規(guī)模分布式容錯存儲系統(tǒng)[1,2]，采用糾刪碼作為數(shù)據(jù)冗余技術能比多副本技術以更低的存儲開銷獲得相同的數(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ā)修復作業(yè)，導致修復帶寬占比高達10%-20%。過高的修復帶寬使得糾刪碼技術在實際中的應用受到限制，所以如何降低修復帶寬問題成為糾刪碼的研究熱點之一[9,10]。

Reed-Solomon碼[11]常常是分布式存儲系統(tǒng)的標準設計選擇，但是其高昂的修復成本被認為是高存儲效率和高可靠性不可避免的代價。為降低修復成本，Rashmi等提出了Piggybacking設計框架，保證在較低的存儲開銷下，進一步減少修復帶寬；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) 值選擇具有最小修復代價的編碼結(jié)構(gòu)，進一步降低下載帶寬。

1 相關工作

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

表1 參數(shù)

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

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

當一個系統(tǒng)節(jié)點Nodei失效時，3種碼的修復下載量：雙條帶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+碼的修復下載情況，如圖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é)點修復帶寬存在差異。

2 OHitchhiker碼

本文提出一種最優(yōu)分配的OHitchhiker編碼，通過在編碼的分配環(huán)節(jié)引入一種高效的動態(tài)算法，使得OHitchhiker編碼可以針對不同 (n,k) 值選擇具有最小修復代價的編碼結(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) 的修復下載量為

(1)

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

(2)

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

(3)

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

移動分配：即當Δβ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碼在修復過程中首先實現(xiàn)全局均分分配，大幅度降低修復帶寬；然后通過不同 (n,k) 參數(shù)判斷執(zhí)行移動分配，達到最優(yōu)動態(tài)選擇模式，從而降低修復時所需的總數(shù)據(jù)下載量，保證系統(tǒng)節(jié)點的平均修復帶寬最低。

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

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

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ù)。

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

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

2.3 OHitchhiker修復過程

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

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

(1)下載第二子條帶中的數(shù)據(jù){b1,…,bk,f1(b)}/bi， 共k個數(shù)據(jù)，據(jù)MDS性質(zhì)，計算恢復出原數(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ù)，相互異或恢復出數(shù)據(jù)ai； 此時共下載 |Sj| 個數(shù)據(jù)。

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

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

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

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

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，通過設置不同 (n,k) 參數(shù)和4種編碼策略(OHitchhiker碼、RS碼、Hitchhiker-XOR碼和Hitchhiker-XOR+碼)，將每個文件分塊編碼分布式存儲在DataNode節(jié)點中。

3.2 實驗分析

3.2.1 平均修復帶寬

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

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

3.2.2 修復帶寬率

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

(4)

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

圖4 Hitchhiker和OHitchhiker碼的修復率對比

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

3.2.3 總修復下載量

修復每個系統(tǒng)節(jié)點所需的下載量之和，稱為總修復下載量δ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é)點總修復下載量。

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

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

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

4 結(jié)束語

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

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