最優局部修復碼的構造

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

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

0 引言

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

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

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

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

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

1 基礎知識

局部修復碼屬于線性碼，設碼C是有限域Fq上的[n,k]線性碼，碼C的第i位具有局部性r是指第i位是其它r位在有限域Fq中的線性組合，如果碼C的任意位都具有局部性r，則稱碼C是具有局部性r的局部修復碼。局部修復碼是一種特殊的糾刪碼，當分布式存儲系統的一個節點發生故障時，該節點可以通過其它不超過r個存活節點進行修復，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個節點同時出現故障，分布式存儲系統就不能被修復[23]。

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

(1)

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

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

d≥t+1

(2)

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

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

(3)

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

(4)

2 最優局部修復碼的構造

2.1 方形網絡

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

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

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

圖1 3×3方形網絡

2.2 基于方形網絡構造局部修復碼

本小節基于方形網絡構造局部修復碼，將方形網絡的頂點與分布式存儲中需要存儲的數據塊相對應，方形網絡中水平方向和垂直方向的直線對應于分布式存儲系統中的存儲節點。

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

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

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

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

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

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

(5)

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

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

(6)

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

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

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

(7)

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

2.3 基于方形網絡構造擴展局部修復碼

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

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

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

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

(8)

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

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

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

(9)

(10)

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

(11)

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

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

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

(12)

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

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

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

(13)

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

3 性能分析

3.1 碼率分析

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

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

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

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

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

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

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

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

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

3.2 局部性分析

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

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

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

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

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

4 結束語

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