最優(yōu)局部修復碼的構造

楊佳蓉，王 娥，李靜輝，余春雷

(1.長安大學 信息工程學院，西安 710018; 2.四川文理學院 智能制造學院，四川 達州 635002)

0 引言

在大數(shù)據(jù)時代，由于數(shù)據(jù)的急劇增長，分布式存儲系統(tǒng)變得越來越重要[1]。分布式存儲技術是將互聯(lián)網(wǎng)上產(chǎn)生的各種數(shù)據(jù)和信息同步、分散地存儲在多個獨立設備中的技術。它可以通過使用網(wǎng)絡將數(shù)千個存儲節(jié)點連接在一起，以支持數(shù)據(jù)的持續(xù)增長，同時分布式系統(tǒng)還具有高訪問、高性能、低成本等優(yōu)點。但是分布式存儲系統(tǒng)中存在不同種類的設備，包括存儲節(jié)點、路由器和交換機，這些設備可能會不時出現(xiàn)故障，導致系統(tǒng)無法正常工作。為了保證存儲節(jié)點故障的可靠性，在分布式存儲系統(tǒng)中采用了各種編碼技術。

最簡單的方法是直接復制，但是復制方案會導致較大的存儲開銷，與復制相比，糾刪碼在保證數(shù)據(jù)可靠性的同時，可以大大降低存儲負載，極大地提高了存儲設備的利用率。然而在故障節(jié)點的修復過程中，經(jīng)典的糾刪碼在訪問的輔助節(jié)點數(shù)量、修復帶寬等方面效率低下。為了保證數(shù)據(jù)的可靠性和節(jié)點的有效修復，后續(xù)的研究中陸續(xù)提出了再生碼和局部修復碼(LRCs, locally repairable codes)。再生碼可以通過提高修復程度和減少從每個節(jié)點下載的數(shù)據(jù)來減少修復帶寬，而局部修復碼則可以有效修復故障節(jié)點，通過在修復過程中使用少量的節(jié)點來降低修復成本[2]。

許多學者已經(jīng)對局部修復碼進行了研究，Gopalan等在文獻[3]中首次提出局部修復碼，并證明了適用于任意碼字的Singleton-like限。文獻[4]和文獻[5]分別介紹了修復局部性的概念，如果碼字的第i個碼元能夠被其它至多r個碼元修復，則稱該碼元具有修復局部性r。文獻[6]證明了在分布式存儲系統(tǒng)中使用局部修復碼時可以更有效地修復故障點，還提出了一個最優(yōu)的和顯式的局部修復碼，實現(xiàn)了任意高的數(shù)據(jù)率。在文獻[7-8]中，Shahabineja等研究了局部修復碼的信息位的最優(yōu)平均局部性，實現(xiàn)了奇偶校驗位的最優(yōu)最大局部性，但在構造算法中復雜度較高。Wang等人[9]推導出了每個修復組中包含多個奇偶校驗符號時的最小距離界。Tamo等人在文獻[10]中提出了所有符號具有(r,t)局部性的局部修復碼的最小距離界。在文獻[11]中，Pamies-Juarez等人利用部分幾何圖構造了具有多個不相交修復組的局部修復碼[11]。

在構造最優(yōu)局部修復碼方面，Tamo在文獻[12]中提出了一組使用多項式構造最優(yōu)局部修復碼的方法，但碼率不高。在文獻[13]和文獻[14]中，Tamo和Luo等人提出了環(huán)狀局部修復碼的構造方法，其最小距離達到了最優(yōu)界，但是碼率較小。在文獻[15]中Hao等人給出了最優(yōu)三元局部修復碼的分類。Kruglik等人在文獻[16]中從二分圖的角度出發(fā)構造二元LRCs，并對Tamo等人提出的所有符號具有(r,t)局部性的局部修復碼的最小距離的界進行了改進，達到了最小距離最優(yōu)，但是其構造算法略復雜。Jung-Hyun Kim等人提出一種基于超圖的二進制局部修復碼的構造[17]，給出了具有(r,t)局部性的超圖存在的必要條件，增加了最小距離，但是碼率受超圖參數(shù)的影響較大。在文獻[18]中，Wang等人利用區(qū)組設計中的DBBD設計構造二元局部修復碼，其最小距離和碼率都達到了最優(yōu)界，但是局部性有所限制。Silberstein等人在文獻[19]中提出了基于各種反編碼的二元最優(yōu)局部修復碼，但是其局部性只能取2或3，不能適用于任意局部性的情況。張茂等利用不相交局部修復組、sunflower和射影幾何等理論構造了一般域上的兩類局部修復碼[20]，所構造的兩類碼在相同的碼的最小距離和局部度下提高了碼率，但是碼率沒有達到最優(yōu)。

針對上述問題，本文提出一種基于方形網(wǎng)絡的局部修復碼的構造方法。具體地，利用方形網(wǎng)絡中頂點與邊的對應關系構造關聯(lián)矩陣，然后在關聯(lián)矩陣右側添加單位矩陣得到局部修復碼的校驗矩陣，進而基于該校驗矩陣構造局部修復碼，所構造的局部修復碼最小距離和碼率都達到了最優(yōu)界；進一步地，將方形網(wǎng)絡中水平方向和垂直方向的的關聯(lián)矩陣分別進行擴展，新構造的局部修復碼參數(shù)選擇靈活，算法復雜度較低，在修復故障節(jié)點時可以實現(xiàn)故障節(jié)點的快速精確修復。與現(xiàn)有局部修復碼相比，本文構造局部修復碼在滿足最小距離最優(yōu)界的同時碼率也達到了最優(yōu)，且適用于任意局部性。

1 基礎知識

局部修復碼屬于線性碼，設碼C是有限域Fq上的[n,k]線性碼，碼C的第i位具有局部性r是指第i位是其它r位在有限域Fq中的線性組合，如果碼C的任意位都具有局部性r，則稱碼C是具有局部性r的局部修復碼。局部修復碼是一種特殊的糾刪碼，當分布式存儲系統(tǒng)的一個節(jié)點發(fā)生故障時，該節(jié)點可以通過其它不超過r個存活節(jié)點進行修復，r稱為碼的修復局部性。除了局部性之外，局部修復碼的另一個重要特性是可用性，如果碼字符號可以從t個不相交修復集中恢復，則這個符號具有(r,t)可用性。

定義1[21-22]:如果一個碼字符號ci滿足以下三個屬性則說明它具有(r,t)局部性:

如果只有k個信息符號具有(r,t)局部性，則稱該碼為具有信息局部性的(n,k,r,t)-LRCs。

簡單來說，LRCs是糾刪碼的一種，可以用n表示碼長，k表示維度，d表示碼的最小距離。如果局部修復碼的所有信息位碼元都具有(r,t)可用性，則可以稱該碼具有(r,t)可用性的局部修復碼，記作(n,k,r,t)iLRCs。如果其信息位碼元的每個修復集都只有一個校驗位碼元，那么稱該碼為單校驗(n,k,r,t)iLRCs，如果局部修復碼的所有碼元都具有(r,t)可用性，那么這個碼稱為全符號(n,k,r,t)aLRCs，本文主要研究單校驗(n,k,r,t)iLRCs。

令u和v是線性碼C中任意兩個非零碼字，兩個碼字之間不相等， 碼C的最小距離可以表示為d=min{d(u,v)}，也就是碼字之間的最小漢明距離，對于碼(n,k,d)，如果d個節(jié)點同時出現(xiàn)故障，分布式存儲系統(tǒng)就不能被修復[23]。

定理1[24]：若局部修復碼信息位碼元的每個修復集中只含有一個校驗位，那么該單校驗(n,k,r,t)iLRCs的最小距離滿足：

(1)

稱達到式(1)中邊界的局部修復碼是最小距離最優(yōu)的單校驗(n,k,r,t)iLRCs。

定理2[25]:若線性分組碼C是信息位具有局部性r和可用性t的局部修復碼，最小距離滿足:

d≥t+1

(2)

如果上式中局部修復碼的最小距離d取等號，則此局部修復碼為最小距離最優(yōu)的局部修復碼。

定理3[26]:(n,k,d)LRC碼的局部參數(shù)r滿足:

(3)

定理4[27]:特別地，Prakash等人提出了可用性t=2的最優(yōu)碼率的(n,k,r,t=2)LRCs，該碼滿足:

(4)

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

2.1 方形網(wǎng)絡

定義2[28]:由若干個單位邊長的正方形拼接而成的網(wǎng)絡稱為方形網(wǎng)絡，方形網(wǎng)絡中水平向上和垂直向上的直線相等。

給定一個方形網(wǎng)絡，其中頂點p2(p≥2)個，p為正整數(shù)。p表示方形網(wǎng)絡中水平方向和垂直方向的每條直線上的頂點數(shù)量，由此可知，方形網(wǎng)絡中水平和垂直方向上的直線也分別為p條。令方形網(wǎng)絡的頂點表示分布式存儲系統(tǒng)中的數(shù)據(jù)包，水平方向和垂直方向的直線代表分布式存儲系統(tǒng)中的存儲節(jié)點，我們將這樣的p×p方形網(wǎng)絡稱為分布式存儲系統(tǒng)中的方形網(wǎng)絡。

給出分布式存儲系統(tǒng)中的一個3×3的方形網(wǎng)絡，這里p=3，如圖1所示。該方形網(wǎng)絡在水平方向和垂直方向上共有6條直線v1,v2，…,v6，代表分布式存儲系統(tǒng)中的6個存儲節(jié)點，方形網(wǎng)絡中的9個頂點d1,d2,…,d9，代表分布式存儲系統(tǒng)中節(jié)點存儲的數(shù)據(jù)包。

圖1 3×3方形網(wǎng)絡

2.2 基于方形網(wǎng)絡構造局部修復碼

本小節(jié)基于方形網(wǎng)絡構造局部修復碼，將方形網(wǎng)絡的頂點與分布式存儲中需要存儲的數(shù)據(jù)塊相對應，方形網(wǎng)絡中水平方向和垂直方向的直線對應于分布式存儲系統(tǒng)中的存儲節(jié)點。

構造1:利用方形網(wǎng)絡構造局部修復碼的具體步驟如下:

步驟1: 給定一個p×p方形網(wǎng)絡，p為正整數(shù)且p≥2。將方形網(wǎng)絡中的頂點dj(1≤j≤p2)按照先從上到下再從左到右的規(guī)則進行編號，直線vi(1≤i≤2p)也按照同樣的規(guī)則進行編號。

步驟2：根據(jù)2.1，給定的方形網(wǎng)絡中一共有2p條直線和p2個頂點,。令第i條直線對應于局部修復碼中的第i個存儲節(jié)點，第j個頂點對應局部修復碼中第j個的數(shù)據(jù)塊。

步驟3：構造基于方形網(wǎng)絡的局部修復碼的校驗矩陣H=[M|I2p]，其中關聯(lián)矩陣M=(nij)2p×p2，當方形網(wǎng)絡的頂點dj(1≤j≤p2)正好在其直線vi(1≤i≤2p)上時，第i個節(jié)點存儲頂點上的數(shù)據(jù)塊dj，基于方形網(wǎng)絡的關聯(lián)矩陣中nij=1，否則為0。

步驟4：由校驗矩陣構造的碼C是信息位具有局部性r和可用性t的局部修復碼，碼C的參數(shù)滿足條件n=2p+p2,k=p2,r=p,t=2。由于M是基于方形網(wǎng)絡的關聯(lián)矩陣，每一列的漢明權重都等于2，這意味著每個信息符號都有t=2個修復集，M的每一行都有漢明權重p，且M的任意兩個不同的行最多有一個位置是相同的，因此該碼具有局部性r=p，每個信息符號的修復集是不相交的，每個修復集只包含一個校驗位。

例1:給定一個方形網(wǎng)絡，其中p=3，如圖1所示。根據(jù)方形網(wǎng)絡中頂點與直線的對應關系可以構造關聯(lián)矩陣:

(5)

定理5:基于方形網(wǎng)絡構造的(n=2p+p2,k=p2,r=p,t=2)局部修復碼為最小距離最優(yōu)的局部修復碼，并且d=t+1。

證明:基于方形網(wǎng)絡構造的(n=2p+p2,k=p2,r=p,t=2)局部修復碼，其信息位碼元的每一個修復集中只包含一個校驗位，根據(jù)定理1，將其參數(shù)代入邊界條件:

(6)

即d≤t+1，又根據(jù)定理2可得d≥t+1，因此所構造的局部修復碼的最小距離d=t+1，達到了最小距離最優(yōu)界，是最小距離最優(yōu)的局部修復碼。

定理6:基于方形網(wǎng)絡構造的(n=2p+p2,k=p2,r=p,t=2)局部修復碼的碼率是最優(yōu)的。

證明:(n=2p+p2,k=p2,r=p,t=2)局部修復碼的碼率:

(7)

其碼率滿足定理4中Prakash等人提出的可用性t=2時局部修復碼的邊界，所以此碼是碼率最優(yōu)的局部修復碼。

2.3 基于方形網(wǎng)絡構造擴展局部修復碼

上節(jié)中基于方形網(wǎng)絡構造的局部修復碼是最小距離最優(yōu)的碼，并且達到了碼率最優(yōu)界，但是該局部修復碼的局部性有所限制。為進一步提高局部度，本節(jié)運用方形網(wǎng)絡構造擴展關聯(lián)矩陣，以此構造局部修復碼的校驗矩陣，可以得到適用于任意局部性的局部修復碼。

構造2:基于方形網(wǎng)絡構造擴展局部修復碼的具體步驟如下：

步驟1：首先將方形網(wǎng)絡中的頂點dj(1≤j≤p2)按照構造1的規(guī)則進行編號，直線vi(1≤i≤2p)也按照同樣的規(guī)則進行編號。其中第i條直線對應于局部修復碼中的第i個存儲節(jié)點，第j個頂點對應局部修復碼中第j個數(shù)據(jù)塊。

步驟2：如構造1步驟3中直線與頂點的存儲關系，將基于方形網(wǎng)絡中水平方向構造的關聯(lián)矩陣定義為M1，垂直方向構造的關聯(lián)矩陣定義為M2，另外用Ip表示p階單位矩陣，Sp表示副對角線為1的單位矩陣?；诜叫尉W(wǎng)絡構造擴展局部修復碼的關聯(lián)矩陣為:

(8)

步驟3：將矩陣M′與單位矩陣級聯(lián)作為方形網(wǎng)絡的擴展校驗矩陣H′=[M′|I2p]，由此擴展校驗矩陣可以構造參數(shù)為(n=p2+3p,k=p2+p,r=p+1,t=2)的局部修復碼。

由于M′是基于方形網(wǎng)絡擴展的關聯(lián)矩陣，由方形網(wǎng)絡的性質可以知道每一列的漢明權重都等于2，這意味著每個信息符號都有t=2個修復集，M′的每一行都有漢明權重p+1，M′的任意兩個不同的行最多有一個位置是相同的，因此基于方形網(wǎng)絡擴展矩陣構造的局部修復碼具有局部性r=p+1，每個修復集只包含一個校驗位。

例2:給定一個方形網(wǎng)絡，其中p=3，如圖1所示，基于方形網(wǎng)絡得到的關聯(lián)矩陣為M，根據(jù)水平方向構造關聯(lián)矩陣M1和垂直方向構造關聯(lián)矩陣M2：

(9)

(10)

將M1和M2上下級聯(lián)，并在新矩陣的右方級聯(lián)一個3階單位矩陣和一個副對角線為1的3階矩陣，進而可得矩陣:

(11)

最后將M′作為方形網(wǎng)絡的擴展關聯(lián)矩陣，和單位矩陣I2p級聯(lián)生成校驗矩陣H′=[M′|I2p]，由此可以構造出(n=18,k=12,r=4,t=2)的局部修復碼，從兩種構造的參數(shù)對比可知，與例1相比，基于方形網(wǎng)絡擴展矩陣的局部修復碼適用于任意局部性的情況。

定理7:基于方形網(wǎng)絡的擴展矩陣構造的(n=p2+3p,k=p2+p,r=p+1,t=2)局部修復碼為最小距離最優(yōu)的局部修復碼，并且d=t+1。

證明:基于方形網(wǎng)絡的擴展矩陣構造的(n=p2+3p,k=p2+p,r=p+1,t=2)局部修復碼，根據(jù)定理1，將其參數(shù)代入邊界條件:

(12)

即d≤t+1，又根據(jù)定理2可得d≥t+1，因此所構造的局部修復碼的最小距離d=t+1，正好達到最小距離最優(yōu)界，是最小距離最優(yōu)的局部修復碼。

定理8:基于方形網(wǎng)絡的擴展矩陣構造的(n=p2+3p,k=p2+p,r=p+1,t=2)局部修復碼的碼率是最優(yōu)的。

證明: (n=p2+3p,k=p2+p,r=p+1，t=2)局部修復碼的碼率:

(13)

其碼率滿足定理4中Prakash等人提出的可用性t=2時局部修復碼的邊界，所以此碼是碼率最優(yōu)的局部修復碼。

3 性能分析

3.1 碼率分析

碼率是局部修復碼中一個重要的參數(shù)，碼率表示碼字中信息碼元所占的比例。碼的碼率越大，表示其傳輸效率越高。本小節(jié)主要對基于方形網(wǎng)絡構造的局部修復碼的碼率進行最優(yōu)化分析。

3.1.1 與校驗矩陣構造的LRCs比較

本小節(jié)將構造1、構造2與基于射影平面和基于仿射平面的局部修復碼[24]進行比較。這四種局部修復碼都是由校驗矩陣構造的，但是構造方式有所不同，基于射影平面的局部修復碼是利用低密度奇偶校驗碼的校驗矩陣構造，基于仿射平面的局部修復碼是將仿射平面的一個固定的點和經(jīng)過這個點的線刪除之后得到關聯(lián)矩陣，由關聯(lián)矩陣來構造局部修復碼的校驗矩陣。

圖2 t=2時基于校驗矩陣的LRCs的碼率R和 局部性r的關系

3.1.2 與任意(r,t)局部性的LRCs的比較

將本文構造的局部修復碼與可達到任意局部性(r,t)的局部修復碼進行比較，碼的參數(shù)比較如表2所示。

表2 與可達任意局部性的LRCs參數(shù)比較表

如圖3所示，為最優(yōu)碼率界，將本文構造的局部修復碼與可達任意局部性的基于直積碼的局部修復碼進行碼率比較?？梢钥闯觯瑃=2時構造1和構造2的碼率與Prakash等人提出的最優(yōu)碼率界重合，且始終大于基于直積碼的局部修復碼的碼率。

圖3 t=2時可達任意局部度的LRCs的碼率R和 局部性r的關系

3.2 局部性分析

局部修復碼中的局部性r意味著它最多可以從r個其它碼字符號中修復故障節(jié)點，局部性將直接影響磁盤I/O和修復過程中需要連接的節(jié)點數(shù)量。將構造1和構造2進行對比分析可知，構造1的局部性r=p，而構造2的局部性r=p+1，構造2所構造的局部修復碼在不犧牲碼率和最小距離等關鍵參數(shù)的情況下，適用于任意局部性的情況。

表3是不同局部修復碼局部性的參數(shù)對比分析，將本文構造的局部修復碼與基于區(qū)組設計的局部修復碼[18]、基于反編碼構造的局部修復碼[19]以及基于循環(huán)移位的局部修復碼[29]相比，基于區(qū)組設計的局部修復碼的局部性為2，限制了局部性的可選范圍，從表3中可以看出基于區(qū)組設計的局部修復碼的碼率較低且不能適用于任意局部性的情況。

表3 不同LRCs關于局部性r的參數(shù)對比表

基于反編碼構造的局部修復碼的局部性為2或者3，局部性r的取值較小，只適用于具有小局部性的局部修復碼，除此之外，此碼的局部性r的可選擇范圍也被限制，無法靈活地構造不同局部性下的局部修復碼。

基于循環(huán)移位的局部修復碼的局部性也為2，其中大部分的局部修復組都只有一個信息符號和兩個校驗符號，每個信息符號的局部修復不能通過訪問其它信息符號來實現(xiàn)，只能通過訪問校驗符號來實現(xiàn)，局部性有所限制。相比之下，本文構造的局部修復碼的局部性可以達到任意值，參數(shù)選擇更加靈活。

4 結束語

本文針對已有的局部修復碼在最小距離最優(yōu)的條件下碼率不高，局部性無法適用于任意情況的問題，提出了基于方形網(wǎng)絡構造局部修復碼的方法，首先利用方形網(wǎng)絡中頂點與邊的對應關系來構造局部修復碼的校驗矩陣，所構造的局部修復碼達到了最優(yōu)碼率界。為了進一步提升局部性，將方形網(wǎng)絡水平方向和垂直方向上關聯(lián)矩陣進行擴展，用擴展的關聯(lián)矩陣構造局部修復碼的校驗矩陣，所構造的新的局部修復碼不僅在最小距離最優(yōu)界時達到了碼率最優(yōu)，并且提高了局部性。經(jīng)過對碼率和局部性的性能分析可知，本文構造的局部修復碼不僅滿足最小距離最優(yōu)，并且達到了碼率最優(yōu)界，參數(shù)選擇靈活，適用于任意局部性的情況。