分布式存儲中一種新的低修復(fù)帶寬的Hitchhiker碼

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

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

1 前 言

海量數(shù)據(jù)的增加導(dǎo)致存儲系統(tǒng)應(yīng)具有低價格和可擴(kuò)展的優(yōu)良特性.相比傳統(tǒng)的集中式存儲[1]，分布式存儲系統(tǒng)[2]利用廉價的商用PC機(jī)和成熟的網(wǎng)絡(luò)技術(shù)，形成了成本低廉且易擴(kuò)展的存儲系統(tǒng).為保證數(shù)據(jù)的可靠性，分布式存儲系統(tǒng)常利用多副本[3]和糾刪碼[4，5]這兩種容錯技術(shù).前者較成熟且最簡單，但空間利用率低；后者以其高容錯能力，高空間利用率等優(yōu)點(diǎn)得到學(xué)術(shù)界和工業(yè)界的關(guān)注，并廣泛應(yīng)用到Hadoop[6]、GFS[7]、Azure[8]等各大分布式存儲系統(tǒng)中.

Reed-Solomon Codes[9，10]是具有MDS[11]性質(zhì)的糾刪碼，能夠達(dá)到理論上的最高容錯能力和最低的存儲代價，但存在修復(fù)成本高昂的問題.為了降低修復(fù)帶寬，目前常用的有兩種降低修復(fù)帶寬的方式.一是Rashmi等人[12]提出了Piggybacking設(shè)計架構(gòu)，其中將易于工程實(shí)現(xiàn)的雙條帶MDS碼命名為Hitchhiker[13]碼，并給出了三種Hitchhiker碼的構(gòu)造方案，適用于各種(k,r)參數(shù)配置.二是Gopalan 等人[14-16]分別提出了局部修復(fù)性編碼(Locally Repairable Codes)，簡稱LRC.它通過添加局部校驗(yàn)來減少磁盤I/O，從而降低修復(fù)成本.目前RS碼、LRC和Hitchhiker碼都廣泛應(yīng)用于各大分布式存儲系統(tǒng)中.例如：RS(6,3),RS(8,4),RS(10,4)分別應(yīng)用到了Google文件系統(tǒng)[17]、Baidu Atlas云平臺[18]和Facebook存儲系統(tǒng)[19]中，在Hadoop分布式文件系統(tǒng)提供多種參數(shù)的RS(k,r)碼[20]供用戶選擇；LRC應(yīng)用在Azure和Hadoop中[21，22]，兩者的編碼方式有稍許差異；(10,4)-Hitchhiker已部署在Hadoop文件系統(tǒng)中.

目前Hitchhiker碼只針對系統(tǒng)單元的修復(fù)進(jìn)行了優(yōu)化，而對校驗(yàn)單元未做處理.LRC雖能顯著的降低單節(jié)點(diǎn)失效的修復(fù)帶寬，但由于增加了額外的存儲開銷，從而破壞了MDS性質(zhì).針對該問題，本文借鑒LRC中的信息位局部性的思想，構(gòu)造出兩種Hitchhiker碼與LRC相結(jié)合的新編碼，并命名為——Hitchhiker-LRC和Hitchhiker-LRC+.它們既沒有增加額外的存儲空間又降低數(shù)據(jù)單元和校驗(yàn)單元的修復(fù)帶寬，達(dá)到整體修復(fù)帶寬優(yōu)于原Hitchhiker碼.本文首先給出了將LRC碼加入到Hitchhiker碼的校驗(yàn)單元中的理論基礎(chǔ).其次，提出了Hitchhiker-LRC和Hitchhiker-LRC+的主要思想和編解碼方法.然后，對新提出的編碼的修復(fù)帶寬率、編碼時間和解碼時間進(jìn)行了理論的分析，并討論了參與局部校驗(yàn)的數(shù)量l與修復(fù)帶寬率關(guān)系.最后，實(shí)驗(yàn)證明了在2≤r

2 相關(guān)理論基礎(chǔ)

2.1 定義

首先參數(shù)列表，如表1所示.

表1 參數(shù)表

Table 1 Parameter list

參數(shù)意 義n單元總數(shù)k存放原始數(shù)據(jù)單元的個數(shù)r校驗(yàn)單元數(shù)量l參與局部校驗(yàn)的數(shù)量pk與r-1的商,每個校驗(yàn)中附加的數(shù)據(jù)的個數(shù)qk與r-1的余數(shù),每個校驗(yàn)附加后剩下的數(shù)據(jù)的個數(shù)δ修復(fù)每個單元所需的幫助數(shù)量之和δ-修復(fù)每個單元所需的平均下載量γ修復(fù)失效單元的平均下載量占原數(shù)據(jù)總量的百分比

其次給出相關(guān)性質(zhì)與定義.

性質(zhì)1.將原始數(shù)據(jù)分為等大小的k份，進(jìn)行編碼產(chǎn)生r(r=n-k)個校驗(yàn)，將數(shù)據(jù)擴(kuò)大到n份并存儲到不同的n個節(jié)點(diǎn)上.任何k份數(shù)據(jù)都能恢復(fù)全部的n個節(jié)點(diǎn)中的數(shù)據(jù).稱這種性質(zhì)為MDS性質(zhì).

定義1(單元).單元即units，代表某個節(jié)點(diǎn)中在同一個編碼區(qū)域中的數(shù)據(jù).

定義2(條帶).條帶即stripe，代表同一組編碼的n個units的集合，n個units由k個原始數(shù)據(jù)單元和r個校驗(yàn)數(shù)據(jù)單元組成.子條帶為一個條帶分為多個子條帶，用substripe表示.

2.2 LRC

局部修復(fù)編碼(LRC)是以存儲資源換取帶寬資源的MR[23]碼，由Gopalan、Oggier、Papailiopoulos等人分別提出.C.Huang 等人提出的金字塔碼[24]在Azure云中得到應(yīng)用.結(jié)果顯示：LRC碼有效的減少了磁盤I/O開銷，從而降低單節(jié)點(diǎn)失效的修復(fù)帶寬.圖1為LRC(10，6，2)的編碼，稱由全部數(shù)據(jù)單元產(chǎn)生的校驗(yàn)p1，p2為全局校驗(yàn)，由部分?jǐn)?shù)據(jù)單元產(chǎn)生的校驗(yàn)lp1,2，lp2,1為局部校驗(yàn).通常局部校驗(yàn)與全局校驗(yàn)有一定的數(shù)量關(guān)系.在金字塔碼中，全局校驗(yàn)與局部校驗(yàn)的數(shù)量關(guān)系如公式(1)所示.

px=lpx,1+lpx,2+…+lpx,y

(1)

它是將全局校驗(yàn)拆分成y個局部校驗(yàn).存儲時，其中的一個局部校驗(yàn)不存儲，達(dá)到節(jié)省存儲空間的目的.那么圖1中的p1=p1,1+p1,2，p2=p2,1+p2,2，其中p1,1和p2,2不存儲.

2.3 Hitchhiker碼

圖2 Hitchhiker(10，4)與RS(10，4)編碼的結(jié)構(gòu)

3 改進(jìn)的Hitchhiker碼

3.1 Hitchhiker-LRC碼

3.1.1 編碼過程

Hitchhiker-LRC的編碼主要分為三步：一是按照Hitchhiker-nonXOR的編碼.二是利用LRC的思想對第一個子條帶中的校驗(yàn)單元求局部校驗(yàn)，并將結(jié)果存放在已通過局部校驗(yàn)的形式捎帶在第二個子條帶的校驗(yàn)的位置之上.三是利用橫向減法來存儲第一步中需要捎帶在第一個子條帶的校驗(yàn)單元中的數(shù)據(jù).現(xiàn)以例子敘述Hitchhiker-LRC的編碼過程.如圖3所示，其中l(wèi)=r=4.

第1步，按照Hitchhiker-nonXOR的方式進(jìn)行編碼，計算p=3，q=1，如公式(2)所示.

(2)

可知在unit12-14的第二個子條帶中分別存儲3個數(shù)據(jù)，在unit12的第一個子條帶中存儲1個數(shù)據(jù).如圖3(a)所示.

3.1.2 解碼過程

圖3 Hitchhiker-LRC(10，4)編碼示意圖

第1步為根據(jù)丟失單元位置，判斷丟失的單元的類型.如算法1中Step 1所示.

第2步為解碼數(shù)據(jù)單元或解碼校驗(yàn)單元.

解碼數(shù)據(jù)單元利用Hitchhiker-nonXOR中的捎帶法則或者校驗(yàn)單元,其思想為：利用MDS性質(zhì)恢復(fù)第二個子條帶中的bx，接著用第一個子條帶中的LRC和橫向減法來恢復(fù)ax.需用到丟失的數(shù)據(jù)單元unitx和附加在第幾個校驗(yàn)單元的臨時變量p′，其中p′為：

(3)

修復(fù)dr型的方法與原Hitchhiker相同；修復(fù)dl需先利用MDS性質(zhì)恢復(fù)bx，再利用校驗(yàn)單元中第一個子條帶中的LRC和橫向減法來恢復(fù)ax.如算法1中Step 2所示.

g=xmod(k-2)

(4)

對ps而言，需下載捎帶在該校驗(yàn)第二個子條帶的數(shù)據(jù)，計算恢復(fù)第二個子條帶的數(shù)據(jù).第一個子條帶的修復(fù)同樣利用LRC的修復(fù)方式.最后，修復(fù)pa類型的第二個子條帶與ps相同；不同之處在于修復(fù)第一個子條帶，由于橫向減法的原因，會少下載unitk+i|i∈{3,…,r}中的第一個數(shù)據(jù).如算法1中Step 3所示.

算法1.Hitchhiker-LRC的解碼算法

輸入：unitx|x∈{1,…,k}、type、p、q、dr、dl、pn、ps、pa.

Step 1.判斷丟失單元的類型.臨時變量p′.

執(zhí)行公式(3)；

SWITCH(TRUE)

CASEx∈[1，p×(r-1)]:type=dr；BREAK；

CASEx∈[p×(r-1)+1,k]:type=dl；BREAK；

CASEx=k+1:type=pn；BREAK；

CASEx=k+2:type=ps；BREAK；

CASEx∈[k+3，k+r]:type=pa；BREAK；

DEFAULT：error；BREAK；

Step 2.解碼數(shù)據(jù)單元.

下載bi|i∈{1,…，k}{x},f1(b)得到bx；

IFtype==drTHEN

下載ai|i∈{p×p′+1,…,p×p′+p}{x}、fp′+2(b)?f2(ai)|i∈{p×p′+1,…,p×p′+p}得到ax.

ELSE IFtype==dlTHEN

下載unitk+i|i∈{1,…,r}的第一個子條帶、unitk+i|i∈{3,…,r}的第二個子條帶和ai|i∈{p×p′+1,…,p×p′+q}{x}，得ax.

END IF

Step 3.解碼校驗(yàn)單元，臨時變量g.

下載bi|i∈{1,…,k}得到fxmodk(b)；

IFtype==pnTHEN

再下載unitk+i|i∈{1,…,r}{xmodk}的第一個子條帶、unitk+i|i∈{3,…,r}的第二個子條帶和ai|i∈{p×p′+1,…,p×p′+q}{x}，計算得到fxmodk(a).

ELSE

執(zhí)行公式(4)；

下載ai|i∈{g×p+1,…,g×p+p}，得unitx|x∈{0,…,k}的第二個子條帶.再下載unitk+i|i∈{1,…,r}{xmodk}的第一個子條帶和ai|i∈{p×(r-1)+1,…,p×(r-1)+q}{x}.

IFtype==psTHEN

下載unitk+i|i∈{3,…,r}的第二個子條帶即可.

ELSE IFtype==paTHEN

下載unitk+i|i∈{4,…,r}的第二個子條帶，得fxmodk(a).

END IF

END IF

以(k=10,r=4,p=3,q=1)為例，描述5種單元丟失后的解碼方式，如圖4所示.若dr型unit8丟失，需下載幫助數(shù)據(jù)如圖4(a)所示.修復(fù)dl型unit10，下載的幫助數(shù)據(jù)如圖4(b)所示.修復(fù)pn型unit11，下載的幫助數(shù)據(jù)如圖4(c)所示.修復(fù)ps型unit12，下載的幫助數(shù)據(jù)如圖4(d)所示.若pa型的unit13丟失，下載的幫助數(shù)據(jù)如圖4(e)所示.

圖4 5種不同類型的解碼

3.2 Hitchhiker-LRC+碼

3.2.1 Hitchhiker-LRC+的架構(gòu)

隨著r的增加，參與LRC的校驗(yàn)增加，修復(fù)時需要的幫助單元也會增加.因此利用LRC來修復(fù)的校驗(yàn)單元和余下的q個數(shù)據(jù)單元都會受此影響.為了減少r增大對修復(fù)帶寬率的影響，使r取值范圍更廣，滿足目前的參數(shù)配置，提出了第二種編碼Hitchhiker-LRC+.它將所有的數(shù)據(jù)捎帶在第二個子條帶，避免余下的q個數(shù)據(jù)受校驗(yàn)增加的影響，達(dá)到降低其修復(fù)帶寬率的目的.它雖不能保證數(shù)據(jù)單元的最優(yōu)修復(fù)，但能降低整體的修復(fù)度帶寬率.其架構(gòu)如圖5所示.

圖5 Hitchhiker-LRC+的架構(gòu)

3.2.2 編碼過程

編碼過程包括計算校驗(yàn)并分配捎帶數(shù)據(jù)、第一個子條帶求LRC和橫向減法三步.后兩步的方式與Hitchhiker-LRC相同，不同之處為第一步中的數(shù)據(jù)捎帶分配.其如算法2所示.

算法2.Hitchhiker-LRC+的數(shù)據(jù)分配算法

輸入：k、r、p、A.

Step 1.計算p,q的值.

執(zhí)行公式(2).

Step 2.附加p×(r-1-q)數(shù)據(jù)到前r-1-q校驗(yàn)上.

FORi=0;i

pi=pi?f2(ap×i+1,ap×i+2,…,ap×i+p)

END FOR

Step 3.附加(p+1)×q個數(shù)據(jù)到P中的后q個校驗(yàn)上.

FORi=r-1-q;i

pi=pi?f2(ap×i+1,ap×i+2,…,ap×i+p，ap×i+p+1)

END FOR

首先按照公式(2)計算p,q的值；其次給P中的前r-1-q個校驗(yàn)附加p個A中的數(shù)據(jù)；然后給P中的后q個校驗(yàn)附加p+1個A中的數(shù)據(jù)；最后保證每一次附加的數(shù)據(jù)都是Q中后r-1個校驗(yàn)中的同一個校驗(yàn)的局部校驗(yàn).按照上訴方法k個數(shù)據(jù)將完整的捎帶在p中的校驗(yàn)上.

以(k=10,r=4)作為編碼的例子，其中l(wèi)=r=4.第1步計算校驗(yàn)并分配捎帶數(shù)據(jù).按照RS(10,4)的編碼方式計算校驗(yàn)，將10個數(shù)據(jù)編碼得到4個線性無關(guān)的校驗(yàn).接著按照算法2來分配捎帶的數(shù)據(jù)，其中p=3,q=1，即P中的前2個校驗(yàn)存儲3個A中的數(shù)據(jù)，最后一個校驗(yàn)存儲4個A中的數(shù)據(jù).如圖6(a)所示.第2步和第3步的編碼方式與Hitchhiker-LRC相同，不再贅述，分別如圖6(b)、圖6(c)所示.

3.2.3 解碼過程

與Hitchhiker-LRC相比，Hitchhiker-LRC+的解碼過程相對簡單.A和B中數(shù)據(jù)的恢復(fù)只與校驗(yàn)P有關(guān)，與校驗(yàn)Q無關(guān)；同理，校驗(yàn)的恢復(fù)只與校驗(yàn)Q和P中捎帶的A中的數(shù)據(jù)有關(guān)，與A中其他數(shù)據(jù)無關(guān).由于所有的數(shù)據(jù)都捎帶在P中，所以數(shù)據(jù)的解碼只有一類，同Hitchhiker-LRC，將其稱為dr型.校驗(yàn)單元同樣還是pn型、ps型和pa型這三類.數(shù)據(jù)單元和校驗(yàn)單元的解碼方法均可按照算法1中的方法解碼.對數(shù)據(jù)單元而言，沒有dl類型，因此在算法1中的Step 1進(jìn)行類型比較時，不需判斷數(shù)據(jù)單元的類型，其均為dr類型.由于前r-1-q個校驗(yàn)與后q個校驗(yàn)中捎帶的數(shù)據(jù)量不同，因此下載A中數(shù)據(jù)的數(shù)量不同.前p×(r-1-q)個數(shù)據(jù)單元的恢復(fù)與算法1中的dr相同；后q×(p+1)個數(shù)據(jù)單元的恢復(fù)則需多下載一個幫助的數(shù)據(jù)，由原來的p-1增加到現(xiàn)在的p.即將原來的ai|i∈{p×p′+1,…,p×p′+p}{x}替換成現(xiàn)在的ai|i∈{p×p′+1,…,p×p′+p+1}{x}，將原來的fp′+2(b)?f2(ai)|i∈{p×p′+1,…,p×p′+p}替換成現(xiàn)在的fp′+2(b)?f2(ai)|i∈{p×p′+1,…,p×p′+p+1}.對校驗(yàn)單元而言，三種類型都不需下載A中余下的q個數(shù)據(jù)，即不需要下載ai|i∈{p×p′+1,…,p×p′+q}{x}(pn所需)和ai|p×(r-1)+1,…，p×(r-1)+q}{x}(ps和pa所需).

圖6 Hitchhiker-LRC+(10，4)編碼示意圖

4 理論分析

4.1 修復(fù)帶寬率

當(dāng)單元失效時，修復(fù)該單元的平均下載量占原數(shù)據(jù)總量的百分比，稱為修復(fù)帶寬率γ.

(5)

(6)

圖7 Hitchhiker-LRC+(10，4)解碼方式

其中δ為總修復(fù)下載量，是修復(fù)每個單元所需下載的幫助數(shù)量之和.

δ=δsys+δpar

(7)

4.1.1 Hitchhiker-nonXOR

(8)

4.1.2 Hitchhiker-LRC

(9)

4.1.3 Hitchhiker-LRC+

(10)

4.2 編碼與解碼的時間復(fù)雜度

讓參與編碼的碼字都在有限域GF(2t)內(nèi)，為方便分析，假設(shè)加法或減法的時間復(fù)雜度為O(t)，乘法的時間復(fù)雜度為O(t2)[25].實(shí)際上，一個(k,r)的MDS碼，生成一個校驗(yàn)或修復(fù)一個系統(tǒng)節(jié)點(diǎn)需要k次乘法和k-1次加法.分析每種編碼的編碼時間復(fù)雜度和平均解碼時間復(fù)雜度.

4.2.1 編碼的時間復(fù)雜度

a)Hitchhiker-nonXOR共有2r個校驗(yàn)，其生成有三步，分為捎帶前、捎帶和橫向減法.捎帶前即為產(chǎn)生一個(k,r)的MDS碼，那么生成2r個校驗(yàn)的時間復(fù)雜度為O(2r(kt2+(k-1)t)).第二步為捎帶，每個節(jié)點(diǎn)捎帶p個數(shù)據(jù)，可看做(p,1)的MDS碼，時間復(fù)雜度為O(pt2+(p-1)t).其計算的結(jié)果還需與捎帶位置的校驗(yàn)相加.一共有r-1個節(jié)點(diǎn)需捎帶數(shù)據(jù)，因此，捎帶的時間復(fù)雜度為O((r-1)(pt2+pt)).剩下的橫向減法的時間復(fù)雜度為O(t).所以，Hitchhiker-nonXOR的編碼時間復(fù)雜度為O(2r(kt2+(k-1)t)+(r-1)(pt2+pt)+t).

b)Hitchhiker-LRC的是在Hitchhiker-nonXOR橫向減法之前多了求局部校驗(yàn)這一步，其余步驟相同.一共有r個校驗(yàn)參與，也就是把r個校驗(yàn)相加，其時間復(fù)雜度為O(r-1).所以Hitchhiker-LRC的編碼時間復(fù)雜度為O(2r(kt2+(k-1)t)+(r-1)(pt2+pt)+t+r-1).

c)Hitchhiker-LRC+與Hitchhiker-LRC的不同點(diǎn)在于捎帶的方式.該方式是前r-1-q個校驗(yàn)捎帶的是p個數(shù)據(jù)，后q個校驗(yàn)捎帶的是p+1個數(shù)據(jù).可分別看做(p,1)的MDS碼和(p+1,1)的MDS碼，再加上與捎帶位置的校驗(yàn)的加法的時間復(fù)雜度，得到捎帶的時間復(fù)雜度為O((r-1)(pt2+pt)+q(t2+t)).所以，Hitchhiker-LRC+的編碼時間復(fù)雜度為O(2r(kt2+(k-1)t)+(r-1)(pt2+pt)+q(t2+t)+t+r-1).

4.2.2 解碼的時間復(fù)雜度

解碼分為數(shù)據(jù)單元和校驗(yàn)單元，其中第一個子條帶與第二個子條帶也分開計算.

(11)

(12)

(13)

4.3 (k,r)的最優(yōu)修復(fù)帶寬率

Hitchhiker-LRC和Hitchhiker-LRC+兩種編碼的修復(fù)帶寬率都會隨著r的增加漸漸次于原Hitchhiker碼.歸其原因?yàn)閮煞N編碼都讓第一個子條帶中的全部校驗(yàn)都參與了局部校驗(yàn)的計算.若想讓r的增大不直接影響修復(fù)帶寬率，可讓參與局部校驗(yàn)的數(shù)量l隨著r的增加而減少.這樣在修復(fù)某一個校驗(yàn)單元的時，下載的幫助節(jié)點(diǎn)變少.當(dāng)然，如果參與局部校驗(yàn)的數(shù)量太少，采用LRC的方式降低校驗(yàn)節(jié)點(diǎn)的修復(fù)帶寬也不明顯.因此對于任意一個(k,r)的參數(shù)取值，都存在l，使得兩種編碼的修復(fù)帶寬達(dá)到最優(yōu)，其中2≤l≤r.通過分析Hitchhiker-LRC+的解碼過程，得到l動態(tài)變化后的總修復(fù)下載量δhl+如公式(14)所示.

(14)

其中k,r,q,p已知，且k>0,2≤r

5 實(shí)驗(yàn)分析

本文在HDFS-RAID中實(shí)現(xiàn)了Hitchhiker-LRC和Hitchhiker-LRC+兩種編碼，通過策略的方式添加到HDFS中，稱這兩種策略分別為HDFS-HHLRC和HDFS-HHLRC+.根據(jù)實(shí)驗(yàn)結(jié)果，對比分析Hitchhiker-nonXOR、Hitchhiker-LRC和Hitchhiker-LRC+這三種編碼的修復(fù)帶寬率.

5.1 實(shí)驗(yàn)平臺

實(shí)驗(yàn)部署在分布式系統(tǒng)集群中(Hadoop)，集群中由1個NameNode節(jié)點(diǎn)和19個DataNode節(jié)點(diǎn)組成.所有的節(jié)點(diǎn)運(yùn)行在Ubuntu16.04系統(tǒng)和JDK1.8中，其中每個節(jié)點(diǎn)配置2個8核Intel 2.5GHz處理器，48G RAM，2T硬盤和2GB/s以太網(wǎng)卡.實(shí)驗(yàn)數(shù)據(jù)為500個640M文件，保持默認(rèn)HDFS的數(shù)據(jù)塊大小64M，編碼有限域選擇GF(28)設(shè)置不同(k,r)參數(shù)來分析三種編碼的修復(fù)帶寬率.

5.2 實(shí)驗(yàn)結(jié)果

通過實(shí)驗(yàn)，并結(jié)合4.1節(jié)中的公式，觀察k與r的關(guān)系.圖8(a)描繪在k=10,r={3,4,5,6,7,8}時，三種編碼 Hitchhiker-nonXOR、Hitchhiker-LRC和Hitchhiker-LRC+的修復(fù)帶寬率.將Hitchhiker-nonXOR碼作為修復(fù)帶寬率的上界，不難看出，當(dāng)2≤r

圖8(b)描述的是當(dāng)2

圖8(c)是工業(yè)界中常用的參數(shù)配置(k,r)=(5,2),(6,3),(8,4),(10,4)時Hitchhiker-nonXOR、Hitchhiker-LRC和Hitchhiker-LRC+修復(fù)帶寬率對比圖.圖8(c)中可發(fā)現(xiàn)Hitchhiker-LRC+始終保持最低.在參數(shù)(k,r)=(5,2),(6,3)時Hitchhiker-LRC和Hitchhiker-LRC+碼相比于Hitchhiker-nonXOR的修復(fù)帶寬率都降低了4.2%.在參數(shù)(k,r)=(8,4)時，Hitchhiker-LRC因r的增加，修復(fù)帶寬率高于Hitchhiker-nonXOR和Hitchhiker-LRC+；Hitchhiker-LRC+的修復(fù)帶寬率最低，相對于Hitchhiker-nonXOR降低了2.5%，相對于Hitchhiker-LRC降低了5.2%.在(k,r)=(10,4)時，Hitchhiker-LRC相比于Hitchhiker-nonXOR降低了1.7%；而Hitchhiker-LRC+碼相比于Hitchhiker-nonXOR降低了2.5%.

圖8(d)是工業(yè)中常用的參數(shù)配置(k,r)=(5,2),(6,3),(8,4),(10,4)時Hitchhiker-nonXOR、Hitchhiker-LRC和Hitchhiker-LRC+編碼時間開銷.三種編碼在這四種參數(shù)配置上的時間開銷相互持平，在(k,r)=(5,2)時Hitchhiker-LRC和Hitchhiker-LRC+比Hitchhiker-nonXOR高0.0056%.在(k,r)=(6,3)時Hitchhiker-LRC和Hitchhiker-LRC+比Hitchhiker-nonXOR高高0.0067%，在(k,r)=(8,4)時，Hitchhiker-LRC比Hitchhiker-nonXOR高0.006%；Hitchhiker-LRC+比Hitchhiker-nonXOR高0.29%.在(k,r)=(10,4)時，Hitchhiker-LRC比Hitchhiker-nonXOR高0.0047%；Hitchhiker-LRC+比Hitchhiker-nonXOR高0.12%.

圖8(e)是工業(yè)中常用的參數(shù)配置(k,r)=(5,2),(6,3),(8,4),(10,4)時Hitchhiker-nonXOR、Hitchhiker-LRC和Hitchhiker-LRC+解碼時間開銷.在參數(shù)(k,r)=(5,2)時，Hitchhiker-LRC和Hitchhiker-LRC+的解碼時間開銷略低于Hitchhiker-nonXOR；在(k,r)=(6,3),(8,4),(10,4)時，Hitchhiker-LRC和Hitchhiker-LRC+的解碼時間開銷略高于Hitchhiker-nonXOR.

圖8(f)是工業(yè)中常用的參數(shù)配置(k,r)=(5,2),(6,3),(8,4),(10,4)時Hitchhiker-nonXOR、Hitchhiker-LRC和Hitchhiker-LRC+修復(fù)時間開銷(傳輸時間+解碼時間).根據(jù)圖8(f)可知，除了在(k,r)=(8,4)時Hitchhiker-LRC比Hitchhiker-nonXOR的修復(fù)時間高，其余參數(shù)下Hitchhiker-nonXOR的時間都是最高.實(shí)驗(yàn)證明網(wǎng)絡(luò)開銷是Hadoop等平臺的主要瓶頸，增加少量的計算時間，可節(jié)省更多的傳輸時間，達(dá)到降低整體時間的目的.

圖8 不同k,r的總修復(fù)帶寬率、編碼時間、解碼時間和修復(fù)時間

6 結(jié)束語

本文通過對原Hitchhiker的部分校驗(yàn)求局部校驗(yàn)，并讓其存放的位置做橫向減法的方式，構(gòu)造出兩種新的編碼Hitchhiker-LRC和Hitchhiker-LRC+.這兩種編碼在2≤r