具有多個相交修復集的局部修復碼的新構造

2023-05-08 03:01:32滕佳明

計算機應用與軟件 2023年4期

滕佳明

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

0 引言

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

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

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

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

關于具有可用性的局部修復碼的研究相對于傳統局部可修復碼并不算多。文獻[6-9]中給出了關于此類編碼參數的界以及一系列構造。大部分關于此類編碼的文獻是關于信息位局部修復性以及可用性的[10]。但是局部修復碼中的可用性會降低其可到達的碼率上界[6]。

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

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

1 預備知識

1.1 局部修復碼

1.2 具有可用性的局部修復碼

(1)

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

(2)

文獻[6]改進了上述界,表示為:

(3)

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

(4)

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

(5)

1.3 WZL碼

由于本文的編碼構造依賴文獻[14]中的編碼構造思想的,因此在這里介紹一下WZL碼的相關概念。

(6)

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

(7)

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

1.4 具有多個相交修復集的局部修復碼

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

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

(8)

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

(9)

文獻[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 具有全局修復性的(r,t,x)-LRC新構造

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

2.1 構造方法

該構造基于校驗矩陣。對于任意的正整數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)的一些性質來幫助理解該編碼。

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

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

(14)

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

推論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)

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

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)的秩視為一個數列,記為P數列的第一項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)),以此類推,數列的第n項為:

(18)

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

結合推論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)

可以得到該數列的初始值:

P1=1

P2≥m-b+1

P3≥m-b

P4≥m-b+1

(21)

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

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

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

(22)

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

(23)

最后說明該編碼最小距離的性質。

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

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

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

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

(24)