局部修復(fù)碼的最優(yōu)構(gòu)造

何亞錦 ，孫 偉，沈克勤，張鑫楠，劉向陽

(1.長安大學(xué) 信息工程學(xué)院，陜西 西安 710064；2.國防科技大學(xué) 信息通信學(xué)院，陜西 西安 710106)

0 引 言

隨著計算機存儲能力的提升，近年來數(shù)據(jù)呈指數(shù)型增長，如何可靠存儲這些數(shù)據(jù)引起人們的思考?，F(xiàn)如今，社交媒體服務(wù)和云服務(wù)的用戶經(jīng)常上傳圖像和視頻等大型數(shù)據(jù)文件，需要巨大的存儲空間，這種存儲空間是以分布式存儲的形式實現(xiàn)的[1-2]。分布式存儲系統(tǒng)存儲規(guī)模大，節(jié)點數(shù)量增長迅速，無法避免磁盤故障和節(jié)點失效等情況。為了保證分布式存儲系統(tǒng)在節(jié)點故障時的正常工作，復(fù)制策略和糾刪碼策略被提出并在實際系統(tǒng)中應(yīng)用[3-4]。

復(fù)制策略較為簡單，通過對數(shù)據(jù)進行直接復(fù)制得到多個副本，最常見的是三副本復(fù)制。由于復(fù)制策略是對所有的數(shù)據(jù)復(fù)制若干倍，增加了系統(tǒng)的存儲開銷。當前數(shù)據(jù)海量化增長，復(fù)制策略使得存儲開銷成本變得更高。糾刪碼策略是將原文件分成k個等大小的數(shù)據(jù)塊，編碼生成n個數(shù)據(jù)塊，分別存儲在n個不同的節(jié)點上。糾刪碼策略解決了存儲開銷大這一缺點，保證了數(shù)據(jù)傳輸?shù)目煽啃?，但是也有一定的弊端?？紤]故障節(jié)點的修復(fù)開銷，傳統(tǒng)復(fù)制策略中，只需要復(fù)制數(shù)據(jù)到新的存儲節(jié)點上就可以修復(fù)故障節(jié)點了，修復(fù)過程簡單。而糾刪碼策略在對故障節(jié)點進行修復(fù)時，需要對k個數(shù)據(jù)塊重新編碼生成原文件再進行編碼，這個過程涉及的計算復(fù)雜度高，修復(fù)帶寬開銷明顯比傳統(tǒng)的復(fù)制策略高。

為了減小節(jié)點故障時的修復(fù)開銷，再生碼(regenerating codes)在文獻[5]中被提出，但在修復(fù)過程中需要連接的節(jié)點數(shù)目較多，計算復(fù)雜。為了減小所涉及的節(jié)點數(shù)目，即磁盤I/O開銷，文獻[6-7]提出了局部修復(fù)碼(locally repairable codes，LRC)，只需要連接少量的節(jié)點就能完成故障節(jié)點的修復(fù)，明顯降低了修復(fù)成本，提高了修復(fù)效率。如果一個碼元最多可以被r個其他碼元來修復(fù)，就稱該碼具有局部度r。局部修復(fù)碼因其高效的修復(fù)效率和低的修復(fù)成本，在分布式系統(tǒng)中廣泛應(yīng)用。在分布式文件Hadoop中，文獻[8]中的Face book和文獻[9]中的WindowsAzure存儲使用的都是LRC。文獻[10]采用多項式運算的方法構(gòu)造LRC，使得節(jié)點修復(fù)時僅需要連接2或3個節(jié)點。文獻[11]構(gòu)造的LRC采用雙層編碼結(jié)構(gòu)，編碼復(fù)雜且節(jié)點修復(fù)復(fù)雜度較高。

許多學(xué)者開始對二元LRC的構(gòu)造展開研究。文獻[12]提出了(r,t)局部度的概念，即對于局部修復(fù)碼來說，一個故障節(jié)點可以被其他t個不相集的節(jié)點分別修復(fù)，并且修復(fù)集的大小為r，則稱(r,t)局部修復(fù)碼。文獻[13]提出了基于最小距離d=4的(n,k,d,r)LRC碼的構(gòu)造，但其需滿足r+1整除n的條件。文獻[14]構(gòu)造的LRC的最小距離d≥6，局部性r≥2。文獻[15]中構(gòu)造的LRC碼的局部性為r=2和r=3。

針對上面構(gòu)造方法的復(fù)雜性和參數(shù)限制較大的問題，該文提出構(gòu)造新二元LRC的兩種方法，方法一利用非循環(huán)相對差構(gòu)造一個二元正則校驗矩陣，方法二利用酉設(shè)計定義一個關(guān)聯(lián)矩陣。

1 相關(guān)概念

在本節(jié)中，給出了一些關(guān)于LRC的基礎(chǔ)知識，介紹了LRC參數(shù)的一定界限，描述了LRC具有給定參數(shù)的最優(yōu)性。

1.1 系統(tǒng)碼

1.2 局部性修復(fù)碼

1.3 (r,t)可用性

假設(shè)碼C的每個編碼都可以從大小為r的t個不相交子集中恢復(fù)，就稱碼C具有(r,t)局部度。在下面正式定義具有(r,t)局部度的線性碼。

對于線性碼(n,k,d)，第i個編碼ci(1≤i≤n)具有(r,t)局部度，滿足以下條件：

1.4 最小距離

碼的最小距離是兩個碼字之間的所有元素取不同時的元素個數(shù)的最小值，即d=min{d(u,v)}，其中d(u,v)是兩個碼字u,v的漢明距離，對于線性碼(n,k,d)，出現(xiàn)d個節(jié)點故障時就不能獲取原始文件了。

對于單校驗(n,k,r,t)LRC，最小距離滿足d≥t+1，文獻[16]給出了碼的最小距離的上界：

(1)

文獻[17]單校驗(n,k,r,t)LRC，給出了一個碼的最小距離的上界：

(2)

2 最優(yōu)局部修復(fù)碼的構(gòu)造

2.1 基于非循環(huán)相對差集的二元單校驗(r,t)LRC

本節(jié)旨在構(gòu)造(r,t)正則矩陣，首先給出了相對差集的定義，又進一步給出LRC校驗矩陣的具體構(gòu)造方式。

在下面的描述中，符號⊕表示直接求和，Zp表示模p的加群。讓Gn是pn階阿貝爾群的元素，即Zp的n元組。RDS的具體構(gòu)造過程如下：

首先，令G=Zp⊕Gn，N=Zp⊕{0}，D={(f(m),m)|m=(m1,m2,…,mn)∈Gn}，得到一個G相對于N的相對差集即(pn,p,pn,pn-1)，f(m)如下：

ai≠0(modp),i=1,2,…,n

(3)

由于感興趣的λ=1的相對差集，因此令上述公式中n=1，進一步得到f(m)=a1m2(modp),m∈Zp，得到相對差集D(p,p,p,1)。

由于D的元素之間沒有明確的順序，在構(gòu)造LRC時候假定一個字典順序定義為：

i=f(m)×p+m,m∈Zp,i∈(0,p2-1)

(4)

構(gòu)造1：設(shè)非循環(huán)RDSD(p,p,p,1)，其中p是素數(shù)。對于(i1,i2),(j1,j2)∈G，得到字典順序i=p×i1+i2和j=p×j1+j2，則校驗矩陣H=[I(C)I]。其中I(C)定義如下：I(C)=[ci,j]0≤i,j

D+(i1,i2)={(d+i1,d+i2)|(d1,d2)∈D}

(5)

由校驗矩陣H=[I(C)I]構(gòu)造的局部修復(fù)碼參數(shù)為n=2p2,k=p2,r=p,t=p。

定理1：基于非循環(huán)相對差集D(p,p,p,1)構(gòu)造的局部修復(fù)碼(n=2p2,k=p2,r=p,t=p)是最優(yōu)的，滿足邊界條件。

證明：基于非循環(huán)相對差集構(gòu)造的碼的長度為2p2，維數(shù)為p2，I的每一列對應(yīng)著奇偶校驗位，I(C)的每一列代表信息位，I(C)的每一列碼重為p，也就是說每個信息符號有t=p個修復(fù)集。每一行的行重為p，并且任意兩行之間最多有一個公共的位置，因此局部性r=p。每個修復(fù)集只包含一個校驗位。注意校驗矩陣的每一行的行重為p+1，又因為有d≥t+1=p+1。因此最小距離d=p+1，很明顯構(gòu)造出的碼是最優(yōu)的。進一步地，由碼率R的計算公式可以得到R=k/n=1/2。

(6)

例1：令Z3={0,1,2},G=Z3⊕Z3，p=3,n=1,a1=1，f(m)=m2(mod 3)，計算D={(f(m),m)|m∈{0,1,2}}得到D(3,3,3,1)，即D={(0，0)，(1，1)，(1，2)}。對于G=Z3⊕Z3中的所有元素，有以下D的集合：

通過使用字典順序，可以得到關(guān)聯(lián)矩陣：

由校驗矩陣H=[I(C)I]定義的單校驗(18,9,3,3)LRC，最小距離d=t+1=4。通過式(2)可知，它是最優(yōu)的LRC，且碼率R=k/n=1/2。

2.2 基于酉設(shè)計構(gòu)造(r,t)LRC

酉設(shè)計是基于射影幾何構(gòu)造的Steiner設(shè)計，在本節(jié)首先介紹酉設(shè)計的定義，進一步利用酉設(shè)計構(gòu)造稀疏(r,t)正則矩陣，給出LRC校驗矩陣的具體構(gòu)造方式，并證明得到的碼是最優(yōu)的。

酉設(shè)計構(gòu)造：設(shè)P=PG(2,q)用齊次坐標表示，酉設(shè)計上的點(x:y:z)滿足xxq+yyq+zzq=0，稱這個酉設(shè)計是一條Hermitian曲線。

例2：要構(gòu)造一個酉設(shè)計，在偶數(shù)階q=m2的射影平面PG(2,q)有m3+1個點，每條線有m+1個點。在PG(2,m2)中，Hermitian曲線酉設(shè)計上的點(x,y,z)滿足下面性質(zhì)f(x,y,z)=xm+1+ym+1+zm+1=0。由上面給出的平面PG(2,22)點的集合滿足x3+y3+z3=0，點集110,011,1α0,01α,1β0,01β,101,10α,10β線[11β],[010],[1β1],[βα1],[1α1],[111],[001],[β11],[100],[11α],[1αβ]。所有這些都包含酉極性中的3個點，所有其他線都包含這些點之一。酉設(shè)計具有酉極性的點集作為點，對于射影平面中滿足酉極性的點集的線，都包含酉極性中的m+1個點。

構(gòu)造2：酉設(shè)計參數(shù)如下：

m+1,r=m2

(7)

酉設(shè)計的v×b的關(guān)聯(lián)矩陣如下所示，其中每一行表示點Pi，每一列表示塊Bj：

(8)

由校驗矩陣H=[I(C)Iv]構(gòu)造的LRC的參數(shù)如下所示：n=b+v=m4+m2+1,k=b=m2(m2-m+1),r=m2,t=m+1。

定理2：基于酉設(shè)計構(gòu)造的局部修復(fù)碼n=b+v=m4+m2+1,k=b=m2(m2-m+1),r=m2,t=m+1是最優(yōu)的，且滿足邊界條件是最優(yōu)的。

證明：酉設(shè)計構(gòu)造的v×b的關(guān)聯(lián)矩陣，每行有m2個1，并且任意兩行之間最多有一個公共的位置，因此局部性r=m2；每列有m+1個1，說明每個數(shù)據(jù)塊有t=m+1個修復(fù)集。在此關(guān)聯(lián)矩陣右側(cè)添加單位矩陣，可知校驗矩陣的每一行的行重為m2+1，又因為有d≥t+1=m+2。因此最小距離d=m+2，很明顯構(gòu)造出的碼是最優(yōu)的。進一步地，可以計算其碼率R如下：

例3：由例2射影平面PG(22)上的酉極性導(dǎo)出的酉設(shè)計(9,12,4,3)，如下所示：

1.相應(yīng)的區(qū)組設(shè)計如下：

2.關(guān)聯(lián)矩陣：

由校驗矩陣H=[I(C)I9]構(gòu)造的單校驗(21,12,4,3)LRC，最小距離d=t+1=4，碼率R=k/n=4/7。

3 性能分析

由于LRC主要考慮其最小距離和碼率的問題，文中提出的兩種碼很容易證明滿足最小距離界，并進一步證明是最優(yōu)的，所以本節(jié)主要從碼率和故障節(jié)點修復(fù)兩方面進行了比較。

3.1 碼 率

本節(jié)主要從碼率方面與可達任意(r,t)局部度的LRC進行了比較。首先在表1中給出了文中構(gòu)造的兩類碼與文獻[19]中的直積碼的構(gòu)造參數(shù)，并為了方便觀察其大小，給出了如圖1所示的曲線。

表1 局部修復(fù)碼構(gòu)造參數(shù)

經(jīng)上面計算分析可知，局部度r相同時，當t>1時，基于酉設(shè)計構(gòu)造的碼的碼率比直積碼的碼率高。當r>t時，基于酉設(shè)計構(gòu)造的碼的碼率高于1/2。

為了更加直觀地觀察表中三種碼的碼率的大小，給出了r=3時，t-k/n的曲線，如圖1所示。

圖1 r=3，三種碼的碼率與可用性t的關(guān)系

由圖1可知，當r=3，構(gòu)造2的碼率是恒大于直積碼的碼率，而構(gòu)造1的碼率在一定條件下也是高于直積碼的碼率。

3.2 故障節(jié)點修復(fù)

節(jié)點故障可分為單節(jié)點故障和多節(jié)點故障。考慮單個編碼塊故障的情況，又可以分為單個數(shù)據(jù)塊故障和單個校驗塊故障。針對單個數(shù)據(jù)塊故障的時候，可以選取任意一個修復(fù)集就可以完成修復(fù)，可選擇性較多；針對校驗塊故障，只需要通過相關(guān)的數(shù)據(jù)塊通過異或即可修復(fù)。單節(jié)點故障修復(fù)較為簡單，接下來考慮多節(jié)點故障的情形。

對于兩個或多個故障塊，修復(fù)可以分為并行修復(fù)和順序修復(fù)。并行修復(fù)是指兩個故障塊分開各自利用現(xiàn)有的完整的編碼塊進行修復(fù)；而順序修復(fù)是指先修復(fù)好一個故障塊，然后利用修復(fù)好的一個故障塊和現(xiàn)有的編碼塊修復(fù)另一個故障塊。由于每個修復(fù)集中只含有一個校驗數(shù)據(jù)塊，因此優(yōu)先選取并行修復(fù)方案。如果不能選取并行修復(fù)方案，則選取順序修復(fù)方案?？紤]到一個修復(fù)集中全部節(jié)點故障發(fā)生的概率較小，因此并行修復(fù)方案為主要方案。

4 結(jié)束語

在分布式存儲系統(tǒng)中，由于局部修復(fù)碼在節(jié)點故障修復(fù)時所連接的節(jié)點數(shù)小于其維數(shù)k，實用性價值高。對一些不經(jīng)常使用的數(shù)據(jù)，使用局部修復(fù)碼能節(jié)約很多修復(fù)成本。在對那些經(jīng)常使用的數(shù)據(jù)時，采用二元局部修復(fù)碼，編碼過程相對簡單，在修復(fù)時可進行并行修復(fù)，修復(fù)效率高。利用(r,t)局部修復(fù)碼，可以容忍多節(jié)點故障并對其修復(fù)采用并行修復(fù)，且在修復(fù)過程中所連接的節(jié)點數(shù)大大減少，減少了修復(fù)復(fù)雜度和修復(fù)時間?？梢娝岢龅亩M制LRC在系統(tǒng)實現(xiàn)方面有很大的研究價值。該文只給出了各節(jié)點存儲數(shù)量相同局部修復(fù)碼的構(gòu)造，構(gòu)造節(jié)點存儲容量不同的局部修復(fù)碼將是接下來需要考慮的問題之一。