具有多個相交修復(fù)集的局部修復(fù)碼的新構(gòu)造

滕 佳 明

(復(fù)旦大學(xué)計算機科學(xué)技術(shù)學(xué)院上海市智能信息處理重點實驗室 上海 200082)

0 引 言

進(jìn)入大數(shù)據(jù)時代,傳統(tǒng)的集中式網(wǎng)絡(luò)存儲已經(jīng)難以滿足日益增長的大規(guī)模存儲空間的需求,而分布式存儲系統(tǒng)因其海量存儲能力、高擴展性和低成本的特點被廣泛使用和開發(fā)。分布式存儲系統(tǒng)規(guī)模往往非常龐大,一般包含幾千到幾千萬個存儲節(jié)點不等。然而數(shù)量龐大的節(jié)點集群經(jīng)常會產(chǎn)生如網(wǎng)絡(luò)中斷、系統(tǒng)維修等故障,致使節(jié)點失效頻發(fā)。分布式存儲系統(tǒng)一般通過引入冗余來提高系統(tǒng)的容錯性。良好的容錯技術(shù)要求存儲系統(tǒng)具有低的冗余開銷、低修復(fù)帶寬、高的錯誤容忍度。

最常見的容錯技術(shù)是多副本機制,只要有一個副本可用,系統(tǒng)就可以容忍數(shù)據(jù)的丟失。但是其存儲負(fù)載過大,存儲效率很低。另一種常見的容錯技術(shù)是糾刪碼。傳統(tǒng)的糾刪碼使用MDS(Maximum Distance Separable)碼,是一類存儲開銷與可靠性達(dá)到最優(yōu)權(quán)衡的碼,著名的Reed-Solomon碼就是MDS碼的典型代表。在糾刪碼分布式存儲方案中,原始文件首先被分成k個數(shù)據(jù)塊,接著編碼成n個編碼塊,存儲在n個節(jié)點中。當(dāng)有存儲節(jié)點失效后,訪問任意k個節(jié)點就可以譯碼恢復(fù)出原始文件,然后再編碼生成失效節(jié)點的數(shù)據(jù)。由于糾刪碼對原始數(shù)據(jù)進(jìn)行了編碼,所以減少了冗余占有的存儲空間,提高了存儲效率。但是在修復(fù)節(jié)點時,數(shù)據(jù)傳輸量遠(yuǎn)大于失效節(jié)點本身的數(shù)據(jù)量,當(dāng)節(jié)點在網(wǎng)絡(luò)中分布較分散時,節(jié)點的修復(fù)需要消耗大量的網(wǎng)絡(luò)帶寬。

針對糾刪碼的這一問題,Gopalan等[1]最早提出了局部修復(fù)碼的概念。局部修復(fù)碼修復(fù)任意一個節(jié)點只需要訪問至多r<

但是當(dāng)局部修復(fù)碼的一個修復(fù)集中存在多個錯誤時,局部修復(fù)的特性便不再可用,退化到傳統(tǒng)糾刪碼的修復(fù)策略。具有可用性的局部可修復(fù)碼的提出就是為了解決該問題。在具有可用性的局部可修復(fù)碼(即具有多個不相交修復(fù)集的局部可修復(fù)碼)中,每個節(jié)點都對應(yīng)多個彼此不相交修復(fù)集,其中每個修復(fù)集都可以單獨用來修復(fù)故障節(jié)點。局部修復(fù)碼中的可用性使得該編碼可以對碼字中的任意元素進(jìn)行并行讀取。該特性對于熱數(shù)據(jù)(hot data),即同時會被大量用戶同時訪問的數(shù)據(jù),是非常重要的。

關(guān)于具有可用性的局部修復(fù)碼的研究相對于傳統(tǒng)局部可修復(fù)碼并不算多。文獻(xiàn)[6-9]中給出了關(guān)于此類編碼參數(shù)的界以及一系列構(gòu)造。大部分關(guān)于此類編碼的文獻(xiàn)是關(guān)于信息位局部修復(fù)性以及可用性的[10]。但是局部修復(fù)碼中的可用性會降低其可到達(dá)的碼率上界[6]。

為了解決該問題,文獻(xiàn)[10]提出了一類一般化的局部修復(fù)碼,該構(gòu)造允許碼字中每個符號的不同修復(fù)集在少量坐標(biāo)位置相交。這個特性使得這類編碼可以達(dá)到更高的碼率上界,并且同時可以保持局部可修復(fù)碼的負(fù)載平衡特性。文獻(xiàn)[10]還給出了一個該類編碼的顯示構(gòu)造,并利用該類構(gòu)造推導(dǎo)得出了該類編碼的碼率下界。

但是該類編碼有一些局限性,雖然碼率得到了提高,但是其編碼的最小距離僅為2,這意味著該編碼不容許出現(xiàn)任意一位以上的錯誤,容錯性很差。本文提出的編碼最小距離大于2,并且存在大量最小距離較大的實例,解決了該類構(gòu)造編碼最小距離過小的問題。本文推廣了Wang等[14]提出的WZL碼,使其適用于修復(fù)集可以相交的情況。事實上,WZL碼是本文提出的構(gòu)造的一個特例。同時本文給出了碼率的上下界,通過程序發(fā)現(xiàn)存在許多碼率大于WZL碼的實例。本文研究了具有多個相交修復(fù)集的局部修復(fù)碼,提出了一種新的構(gòu)造方法。該編碼是基于二元域的,因此編解碼效率很高,具有一定的實用價值。本文提出的編碼的最小距離優(yōu)于文獻(xiàn)[10]構(gòu)造(目前唯一已知的修復(fù)集可以相交的可用性局部修復(fù)碼構(gòu)造),提供了更好的容錯性。

1 預(yù)備知識

1.1 局部修復(fù)碼

1.2 具有可用性的局部修復(fù)碼

(1)

在下面簡要的列舉一些現(xiàn)有結(jié)論。第一個關(guān)于編碼最小距離d的界由文獻(xiàn)[11-12]給出:

(2)

文獻(xiàn)[6]改進(jìn)了上述界,表示為:

(3)

同時該文獻(xiàn)也給出了(r,t)-LRC碼率的界:

(4)

該界同時適用于線性和非線性碼。文獻(xiàn)[13]給出了針對線性碼更緊的界,表示為:

(5)

1.3 WZL碼

由于本文的編碼構(gòu)造依賴文獻(xiàn)[14]中的編碼構(gòu)造思想的,因此在這里介紹一下WZL碼的相關(guān)概念。

(6)

上述定義的矩陣H(m,t)具有如下結(jié)構(gòu):

(7)

式中:H(m,m)=H(m,1)T=(1,…,1)T,且dim(H(m,1))=dim(H(m,m))=m。同時,文章也給出了上述矩陣的秩。

1.4 具有多個相交修復(fù)集的局部修復(fù)碼

現(xiàn)在將(r,t)-LRC推廣至允許修復(fù)集合最多相交x位的情況,文獻(xiàn)[10]給出了(r,t,x)-LRC的定義。

(1) 對于每一對l,l′∈[t],l≠l′:

(8)

(2) 對于所有j=1,…,t以及碼字中的一對元素a,a′∈q,a≠a′,有:

(9)

文獻(xiàn)[15]給出了(r,t,x)-LRC的最小距離上界。

(10)

接下來對(r,t,x)-LRC的概念做一個擴展,給出信息位(r,t,x)-LRC的定義:

(1) 對于每一對l,l′∈[t],l≠l′:

(11)

(2) 對于所有j=1,2,…,t以及碼字中的一對元素a,a′∈q,a≠a′:

(12)

2 具有全局修復(fù)性的(r,t,x)-LRC新構(gòu)造

這一節(jié)正式提出具有全局修復(fù)性的(r,t,x)-LRC的構(gòu)造方法。本文將WZL碼的構(gòu)造方法加以推廣,使其修復(fù)集合可以相交,并給出該構(gòu)造的碼率和最小距離的上下界。

2.1 構(gòu)造方法

該構(gòu)造基于校驗矩陣。對于任意的正整數(shù)a、b、m,滿足a

(13)

下面給出一個H(m,a,b)的具體例子。

例1由H(5,1,3)作為校驗矩陣的編碼,可以得到r=6,t=3,x=2,該編碼的碼長為10,維度為5,碼率為1/2,最小距離為4。

接下來證明該矩陣H(m,a,b)的一些性質(zhì)來幫助理解該編碼。

2.2 H(m,a,b)的性質(zhì)

引理4對于任意的正整數(shù)a、b、m,滿足a

(14)

下面給出了矩陣H(m,a,b)的秩的一些性質(zhì)。

推論1rank(H(m,a,b))≥max{rank(H(m-1,a,b)),rank(H(m-1,a-1,b-1))+rank(H(m-1,a,b))}

(15)

其中:

(16)

上述推論是關(guān)于矩陣H(m,a,b)的秩的一個粗略估計,若去掉其中的max函數(shù),僅取:

rank(H(m,a,b))≥rank(H(m-1,a-1,b-1))+

rank(H(m-1,a,b))

(17)

利用上述推論,可以通過遞推式計算出rank(H(m,a,b))的最小值。方法如下:

將矩陣H(m,a,b)的秩視為一個數(shù)列,記為P數(shù)列的第一項P1=rank(H(m-a,0,b-a)),第二項P2=rank(H(m-a,1,b-a)),第三項P3=rank(H(m-a,1,b-a+1)),第四項P4=rank(H(m-a+1,1,b-a+1)),以此類推,數(shù)列的第n項為:

(18)

則P3a+1=rank(H(m,a,b))。

結(jié)合推論1可得:

rank(H(m,a,b))=P3a+1≥P3a+P3a-2

(19)

然后計算a=1時矩陣秩的最小值:

rank(H(m,1,b))≥rank(H(m-1,0,b-1))+

rank(H(m-1,1,b))=

1+rank(H(m-1,1,b))≥

2+rank(H(m-2,1,b))≥

?

m-b+rank(H(b,1,b))=

m-b+1

(20)

可以得到該數(shù)列的初始值:

P1=1

P2≥m-b+1

P3≥m-b

P4≥m-b+1

(21)

由此,問題便化簡為解一個三階線性遞歸序列,其特征方程為λ3-λ2-1=0。具體求解過程可以參考相關(guān)文獻(xiàn)。由于該結(jié)果較為復(fù)雜,故不在此列出。

綜上結(jié)果,可以給出該編碼的維度的取值范圍。

引理5以矩陣H(m,a,b)作為校驗矩陣的編碼的維度為:

(22)

推論2以矩陣H(m,a,b)作為校驗矩陣的編碼的碼率界為:

(23)

最后說明該編碼最小距離的性質(zhì)。

引理6以H(m,a,b)作為校驗矩陣的編碼的最小距離d≥3。

證明要證明最小距離d≥3,只需證明校驗矩陣H(m,a,b)任意兩列不相等。矩陣中任意兩列的關(guān)聯(lián)集合至少有一位不相等,記為x1∈Fi,x1?Fj,x2∈Fj,x2?Fi,而每一行的關(guān)聯(lián)集合都不相等,所以必定存在一行的關(guān)聯(lián)集合E包含x1∈E,但不包含x2?E,剩下的元素包含在Fi中,所以E?Fi,EFj,因此i列和j列不相等,得證。

再結(jié)合式(1)與式(4),可以給出該編碼最小距離的界:

推論3以H(m,a,b)作為校驗矩陣的編碼的最小距離的取值范圍:

(24)

2.3 對比其他構(gòu)造

目前,關(guān)于具有相交修復(fù)集的局部修復(fù)碼的構(gòu)造還很少,僅有的一篇為文獻(xiàn)[10]利用WZL碼給出了一類(r,t,x)-LRC的顯示構(gòu)造。首先選擇一個(r,t)-WZL碼的校驗矩陣H(r+t,t),之后利用H(r+t,t)構(gòu)造一個(r,t,x)-LRC的校驗矩陣H,構(gòu)造方法如下:

(25)

但是當(dāng)x≥1時,其校驗矩陣的每一列都有x列與其相等,所以用這種方法構(gòu)造的編碼的最小距離僅為2。當(dāng)該編碼出現(xiàn)大于1個錯誤時,該編碼無法恢復(fù)原有碼字。

而本文構(gòu)造的編碼最小距離大于2,并且存在大量最小距離達(dá)到t+1的例子,現(xiàn)舉一例如下:

例2由H(7,2,4)作為校驗矩陣的編碼,可以得到r=9,t=6,x=3的,該編碼的碼長為35,維度為14,碼率為2/5,最小距離為7。

表1列出了更多關(guān)于最小距離的例子。

表1 (r,t,x)-LRC最小距離對比

相較于WZL碼,本文的編碼在一些情況下碼率大于(r,t)-WZL碼,在此舉出一例:

例3由H(7,1,4)作為校驗矩陣的編碼,可以得到r=19,t=4,x=9,該編碼的碼長為35,維度為29,碼率為29/35,最小距離為3。與其對應(yīng)的(r=19,t=4)-WZL碼的碼率為19/23<29/35。

表2列出了一些在r、t相同時WZL碼與本文構(gòu)造的碼率對比。

表2 (r,t)相同時碼率對比

表3列出了WZL碼[14]、Kruglik等[10]構(gòu)造的碼與本文構(gòu)造三者的參數(shù)對比。

表3 三種構(gòu)造參數(shù)對比

3 構(gòu)造信息位的(r,t,x)-LRC

由于矩陣H(m,a,b)的秩很難求出,只能得到該構(gòu)造的一個不緊的碼率上下界,所以考慮構(gòu)造信息位的(r,t,x)-LRC來解決此問題。

構(gòu)造一個校驗矩陣H′(m,a,b):

(26)

證明由定理1證明可知,這等同于證明矩陣H′(m,a,b)的每一行都有r+1個1,信息位的每一列有t個1,任意兩列有最多x+1個元素相交。

(27)

由此可見,該編碼的碼率與WZL碼相同。

例4由H′(5,1,3)作為校驗矩陣的編碼,可以得到r=6,t=3,x=3,該編碼的碼長為15,維度為10,碼率為2/3,最小距離為4。該編碼碼率與最小距離WZL碼一致。

4 結(jié) 語