基于正交拉丁方的局部修復碼構造

劉帥帥，王靜，劉哲，徐忠環

(長安大學 信息工程學院，陜西 西安 710064)

分布式存儲系統在云計算時代得到了廣泛應用[1].為了保證系統的持續可靠運轉，須采用冗余策略來應對系統中的節點故障[2].“復制”策略操作簡單，但存儲效率較低；糾刪碼均衡了存儲開銷和糾錯性能，但在修復過程中須重構原始文件，帶來巨大的修復帶寬開銷[3].

Gopalan等[4]提出局部修復碼(locally repairable codes,LRCs).當一個數據節點發生故障時，系統會通過獲取r(r?k) 個節點的數據在局部組內修復故障節點，而不再重構原始文件，帶來了修復過程中帶寬消耗與磁盤訪問數量的減少，有效地提高了修復效率.文獻[4]證明 (n,k,r) 局部修復碼最小距離滿足Singleton-型界，其中，n為碼長，k為碼字中信息位個數，r為局部性參數.Tamo等[5]利用RS碼和特殊的MDS碼構造了一類最小距離最優局部修復碼，但須在較大的有限域上編碼，增加了實現的復雜性.Jin等[6]利用有理函數域上的自同構群推廣了RS碼的構造，得到一類字母表大小與碼長相當的最小距離最優局部修復碼，但參數須滿足 (r+1)|n.Luo等[7]基于循環碼和校驗多項式構造了一類碼長與字母表大小無關的局部修復碼，但只有在最小距離d∈{3,4} 時才能實現最小距離最優.

為了實現多故障節點修復，文獻[8]提出具有(r,t)局部性的局部修復碼，不相交的t個修復集提高了系統的魯棒性，同時支持數據的并行讀取.其中，t表示可用性參數.Jin等[9]利用有理函數域上的自同構群構造了具有多個修復集的局部修復碼，但碼的最小距離沒有達到上界且沒有考慮碼率.Hao等[10]通過替換正則矩陣中特定行和列的方法，得到一類參數為 (r,t,δ) 的最小距離最優局部修復碼，但字母表大小須滿足q≥r+δ-2，且碼率較低.Ma等[11]利用弱獨立集構造出維度最優的二元線性局部修復碼，但其參數須滿足r∈{2,3}.Tan等[12]利用線性代數和部分幾何構造信息位具有 (r,t) 局部性的局部修復碼，其最小距離最優且碼率較高，但當可用性較大時構造復雜度較高.Hao等[13]研究LDPC碼與局部修復碼之間的關系，并構造3種信息位具有 (r,t) 局部性的局部修復碼，實現了最小距離最優.其中，第1種基于射影平面的構造碼率只有0.5，參數須滿足r=t；第2種刪除仿射平面中特定點線的構造方法與第1種構造方法的性能相同；第3種基于陣列LDPC碼的構造須對循環排列矩陣進行多次矩陣乘法運算，帶來較大的計算開銷.

針對上述問題，提出基于正交拉丁方的二元局部修復碼構造方法，無須生成抽象幾何圖形和矩陣乘法運算，減小了構造復雜度.根據正交拉丁方元素與矩陣位置的對應關系構造關聯矩陣，得到一類具有全符號局部性的局部修復碼，該碼的碼率和碼長漸近邊界條件；將關聯矩陣級聯一個單位矩陣，構造出一類信息位具有 (r,t=2) 局部性的單校驗局部修復碼，該碼的最小距離和碼率均滿足邊界條件，為最優局部修復碼.為了修復系統中的高故障率節點，利用正交拉丁方完備組構造一類具有高可用性的單校驗局部修復碼，可根據節點故障概率來選擇可用性t，提高系統的魯棒性.

1 背景知識

1.1 局部修復碼

定義1 具有(r,t) 局部性的局部修 碼[8].在有限域Fq中的[n,k,d]q線性分組碼，給定集合{1,2,···,n}，c=[c1,c2,···,cn] 是一個碼字，如果其中 一個碼元符號ci具有局部性r和可用性t，那 么須滿足以下條件：

1）存在t個子集，R1(i),···,Rt(i)?{1,2,···,n}{i}，滿足

2）Rj(i)∩Rl(i)=?，j≠l且j,l∈{1,2,···,t} ；

3）ci∈span(cl)，其中l∈Rj(i),j∈{1,2,···,t}，即向量ci屬于張成的線性空間.其中，稱Rj(i) 為ci的局部 修復組.

對于 (n,k) 局部修復碼，若其所有符號都具有 (r,t) 局部性，則稱該碼為具有全符號局部性的局部修復碼(all symbol-locally repairable codes,AS-LRCs)；若只有信息位符號具有 (r,t) 局部性，則稱為具有信息符號局部性的局部修復碼(information symbol-locally repairable codes,IS-LRCs)[8].

Rawat等[8]證明了當每個局部修復組中只包含一個校驗符號時，信息位符號具有 (r,t) 局部性LRCs的最小距離界為

滿足邊界條件(式(1))的LRCs，稱為最小距離最優的LRCs.

Tan等[12]證明對于信息位符號具有 (r,t) 局部性的 [n,k,d]q局部修復碼，其最小距離滿足

Tamo等[14]提出具有 (r,t) 局部性的LRCs碼率邊界為

式中：R為碼率.

Prakash等[15]提出，當可用性t=2 時，(n,k,r,t=2)-LRCs的碼率邊界和碼長邊界為

1.2 拉丁方

定 義2 拉丁方[16].設S={1,2,···,n} 為n元 集合為集合S上的n階方陣.如果方陣L的每行每列都是集合S中元素的一個全排列，則稱L為S上的一個n階拉丁方.

定理1[16]對于n元集S上的拉丁方，若n≠2,6，則必然存在一對n階正交拉丁方.

定義4 正交拉丁方組[16].對于n元集S上的t(t≥2) 個拉丁方，若它們兩兩正交，則它們組成n階(t個)正交拉丁方組.

定 理2[16]用N(n) 表 示n階正交 拉丁方組中拉丁方的最大個數，則N(n)≤n-1.

定義5 正交拉丁方完備組[16].若n階正交拉丁方組中含有N(n)=n-1 個拉丁方，則稱為n階正交拉丁方完備組.

定理3[16]若q為素數，v為正整數，p=qv為素數冪，且p≥3，則存在p階正交拉丁方完備組.

定義6 支撐集[17].給定向量v=[v1,v2,···,vn]，則它的支撐集為 supp(v)={i|vi≠0},i=1,2,···,n.

2 具有全符號局部性的局部修復碼構造

設集合 Ω={1,2,···,m2}，矩陣X為由集合 Ω 中m2個元素排列成的m階方陣，即

定理4將 關聯 矩陣作為校驗矩陣H1，可以構造參數為n=m2、k=(m-1)2、t=2、r=m-1的AS-LRCs，其中m≥3 且m≠6.

證明由關聯矩陣可知構造的局部修復碼的碼長n=m2，由于集合 Ω 中的每個元素在集合B1和B2中分別只出現1次，在集合B中共出現2次，故關聯矩陣中所有行向量構成了一個線性相關組，且其中不存在零向量.用bi(1≤i≤2m) 表示關聯矩陣的行向量，bi≠0，將所有行向量按分量相加得到零向量，即隨機刪除1個行向量bl(l∈{1,2,···,2m})，根據正交拉丁方的正交性，剩余的行向量構成線性無關組.因此關聯矩陣的秩為局部修復碼的維度為k=m2-(2m-1)=(m-1)2.關聯矩 陣每列漢明重量為2，且每列“1”元素所在的行向量的支撐集只在該“1”元素坐標處相交，所以每個符號位具有2個不相交的局部修復組，即可用性t=2.關聯矩陣每行漢明重量為m，當某個符號位丟失時須獲得另外m-1 個符號位的信息才能恢復，故修復局部性r=m-1.

由集合B和集合 Ω 的映射關系易得關聯矩陣：

將關聯 矩陣M6×9作 為校驗矩 陣H1，可以構造參數為n=9、k=4、t=2、r=2 的AS-LRCs.若 碼元符號c1故 障，其修復集為R1(1)={6,8} 和R2(1)={5,9}，故c1=c6⊕c8=c5⊕c9，其中 ⊕ 表示異或運算.其他碼元符號可以通過類似的方法進行修復.

定理5定理4構造的AS-LRCs的最小距離為d=4，且d＞t+1.

證明AS-LRCs的最小距離d=4 表明其校驗矩陣H1即關聯矩陣中任意3列線性無關，且存在4列線性相關.

1）若3列選自同一組，則對應于拉丁方同一行上的3個不同元素，由拉丁方的性質可知這3個元素處于不同的m-子集中，故這3列必然線性無關，如例1中 {h1,h2,h3} ；

2）若3列中2列選自同一組，剩余1列選自其他組，同一組的2列必然線性無關，同組的2列相加可以得到一個漢明重量為4的列向量，而選自其他組的列向量漢明重量為2，因此這3列必然線性無關，如例1中 {h1,h2,h4} ；

3）若3列分別選自不同組，且對應于拉丁方中3個不同的元素，則與3列選自同一組的情況1)相同，3個列向量線性無關，如例1中 {h1,h4,h7} ；若選自不同組的3列對應于拉丁方中2個不同的元素，則對應于同一個元素的2列相加可以得到一個漢明重量為2的列向量，且2個“1”元素所在的2行所對應的m-子集處于同一個Bh(h=1,2)中，而剩余1個列向量中“1”元素所在的2行所對應的m-子集分別處于不同的Bh(h=1,2) 中，故這3列必然線性無關，如例1中 {h1,h6,h7} ；若選自不同組的3列均對應于拉丁方中同一個元素，則3列所對應的集合 Ω 中的元素所構成的子集只能在Bh(h=1,2)中某個m-子集出現一次，在另一個集合Bh(h=1,2) 中，子集中3個元素必處于3個不同的m-子集中，故這3列必然線性無關，如例1中 {h1,h6,h8}.綜上所述，關聯矩陣中任意3列線性無關，所以d≥4.

綜上所述，定理4構造的AS-LRCs最小距離為d=4，且滿足d＞t+1=2+1=3，得證.

如表1所示為幾種典型的AS-LRCs在可用性t=2 時的參數.表中，w為任意正整數，m(m≥3,m≠6) 為拉丁方的階數.可以發現，當可用性t=2時，定理4構造的AS-LRCs最小距離最大，并且滿足d＞t+1.

表1 幾種典型AS-LRCs構造參數對比Tab.1 Comparison of structural parameters of several typical AS-LRCs

由于不存在一對6階的正交拉丁方，定理4無法構造局部性r=5 的AS-LRCs.下面通過改變集合的構造方法，可以得到任意局部性r≥2 的AS-LRCs.

定理6在m階方陣X上疊合一個m階標準型拉丁方，即該拉丁方第1行與第1列的元素均按順序排列.集 合仍然利用前面的方法構造，而集合則利用標準型拉丁方每列元素在方陣X中對應的位置索引構 造，集 合B=B1∪B2.將集合B和集合Ω 的關聯矩陣作為校驗矩陣，可以構造參數為n=m2、=(m-1)2、t=2、r=m-1 的AS-LRCs，其中m≥3.

可以證明定理6構造出來的AS-LRCs最小距離仍滿足定理5.

例2當m=6時，Ω={1，2，···，36}，方陣X為

6階標準型拉丁方如下：

由集合B和集合Ω 的映射關系得到關聯矩陣M12×36，將其作為校驗矩陣可以構造一個參數為n=36、k=25、t=2、r=5的AS-LRCs.

所構造的AS-LRCs碼率為

如圖1所示為定理6構造的AS-LRCs碼率與Prakash等[15]提出的碼率邊界的比較.圖中，R為碼率，R=k/n.可以發現，隨著局部性參數r的增大，即拉丁方階數m的增大，AS-LRCs的碼率將逐漸接近碼率邊界，即式(4)中的邊界條件.

圖1 可用性 t=2 時的碼 率比較Fig.1 Code rate comparison with availability t=2

不過，由于

定理6中的AS-LRCs碼率始終小于邊界條件(式(4)).

將碼的參數代入碼長邊界（式(5)），可以得到

可以看出，定理6構造的AS-LRCs碼長僅比最優碼長界大1，能夠更好地均衡系統的冗余.

3 具有信息位局部性的局部修復碼構造

3.1 信息位具有 (r,t=2) 局部性的局部修復碼

證明由校驗矩陣H2可知構造的局部修復碼的碼長n=2m+m2，且右邊級聯單位矩陣I2m×2m使得校驗矩陣H2滿秩，因此局部修復碼的維度矩陣H2的前m2列對應信息位符號，后 2m列對應校驗位符號.關聯矩陣中每列的漢明重量為2，且每列“1”元素所在行向量的支撐集只在該“1”元素坐標處相交，所以每個信息位具有2個不相交的局部修復組，即可用性t=2.同時，校驗矩陣H2每行的漢明重量為m+1，當某個信息位符號丟失時須獲得另外m個符號位的信息才能恢復，故修復局部性r=m，且每個局部修復組中只有一個校驗符號.

定理8定理7構造的IS-LRCs的最小距離為d=3，且最小距離最優.

證明校驗矩陣H2的前m2列漢明重量均為2，后2m列為單位矩陣I2m×2m.從校驗矩陣H2的前m2列中任選一個列向量，表示為ξ，它是單位陣I2m×2m中特定2列的線性組合，故矩陣H2中存在3列線性相關，d≤3.另一方面，從校驗矩陣H2中任選2個列向量 {hs1,hs2}，其中 1 ≤s1,s2≤2m+m2，若2列都選自單位陣I2m×2m，顯然它們線性無關；若2列都選自關聯矩陣類似于定理5可以證明它們線性無關；若其中一列選自單位陣I2m×2m，另一列選自關聯矩陣由于列重不同，它們必然線性無關.因此，校驗矩陣H2中任意2列線性無關，從而d≥3.綜上所述，定理7構造的IS-LRCs的最小距離為d=3.

將參數n=2m+m2、k=m2、t=2、r=m代 入最小距離邊界條件(式(1))，可得

滿足邊界條件(式(1))，所以定理7構造的ISLRCs最小距離最優.

定理7構造的IS-LRCs碼率為

滿足碼率邊界條件（式(4)），因此定理7構造的IS-LRCs碼率最優.

此外，局部性r與維度k的比值為

即當系統發生單節點故障時，新生節點需要連接的幫助節點數僅為同參數下糾刪碼的 1/m，能夠有效降低修復過程中的磁盤I/O開銷，加快修復效率.

3.2 信息位具有 (r,t) 局部性的局部修復碼

3.1節構造的IS-LRCs的可用性參數僅局限于t=2，對于存儲系統中的高故障率節點，可能無法確保數據的可靠訪問，須為其提供更高等級的保護.利用正交拉丁方完備組構造可以靈活調節可用性參數的局部修復碼.

故障率 τ 是指節點發生故障的頻率，即單位時間內節點發生故障的次數[20].通常用系統的平均無故障時間(mean time to failure,MTTF)來表示節點故障率，即

式中：MTTF為系統從開始運行到發生故障的平均工作時間.

對第2章中的構造進行擴展，將方陣X與s個m階相互正交拉丁方疊合，其中 2 ≤s≤m-1，m為素數冪，且m≥3，s的取值規則為

式中：τmax為系統中信息位節點故障率的最大值，τmax=,i=1,2,···,k.

其中，0≤k≤(s+1)m,0≤j≤m2.

定理9在關聯矩陣M1右邊級聯(s+1)m階單位矩 陣I(s+1)m×(s+1)m，構造校 驗矩陣H3，即H3=[M1|I(s+1)m×(s+1)m]，其中m為素數冪，且m≥3.由校驗矩陣H3可構造參數為n=sm+m+m2、k=m2、t=s+1、r=m的單校驗IS-LRCs，且最小距離最優，d=s+2=t+1.

證明由校驗矩陣H3可知構造的局部修復碼碼長n=sm+m+m2，且右邊級聯單位矩陣使得校驗矩陣H3滿秩，因此局部修復碼的維度k=m2.矩陣H3的前m2列對應信息位，后(s+1)m列對應校驗位.將關聯矩陣M1的行按順序分為s+1 組，每組包含m個行向量，每組對應一個子集Bh(h=1,2,···,s,c)，集合 Ω 中的每個元素在每個子集Bh(h=1,2,···,s,c) 中出現一次，故關聯矩陣M1的列重 為s+1，且每列“1”元素所在s+1 行中任 意2行的支撐集只在該“1”元素坐標處相交，所以每個信息位具有s+1 個不相交的局部修復組，即可用性為t=s+1.同時，校驗矩 陣H3的行重為m+1，所以當某個信息位符號丟失時須獲得其他m個符號位的信息才能恢復，故修復局部性r=m，且每個局部修復組中只有一個校驗符號.

類似于定理8，可以證明校驗矩陣H3中任意s+1 列線性無關，且存在s+2 列線性相關，故最小距離為d=s+2.此外，將碼的參數代入式(1)得到

代入式(2)得到

因此最小距離d=t+1，定理9構造的IS-LRCs最小距離最優.

例3令m=4，則 Ω={1，2，···，16}，矩陣X為

假設系統中至少有一個信息節點在單位時間內的故障次數大于等于4，即 τmax≥4，則s=m-1=3.給出3個兩兩正交的4階拉丁方:

由集合B和集合 Ω 的映射關系得到關聯矩陣M16×16，由H3=[M16×16|I16×16] 可以得 到參數 為n=32、k=16、t=4、r=4的IS-LRCs，且最小距離d=t+1=5.

假設系統中所有信息節點在單位時間內的故障次數均小于4，且最大故障率為3，即 τmax=3，則s=τmax-1=2.任意選擇2個4階正交拉丁方與集合Bc構造關 聯矩陣M12×16，由H3=[M12×16|I12×12] 可以得到參數為n=28、k=16、t=3、r=4的IS-LRCs，且最小距離d=t+1=4.

定理9構造的IS-LRCs局部性r與維度k的比值為

在大規模分布式存儲系統中，局部性r與維度k的比值將隨著拉丁方階數m的增大而顯著減小，因此該IS-LRCs能夠有效減小故障節點修復時間，提升修復效率.

進一步可以得到碼率：

又因為 2≤s≤m-1，故

即定理9構造的IS-LRCs碼率下界為0.5.

如表2所示為幾種典型的基于校驗矩陣構造的IS-LRCs與定理9構造的IS-LRCs的碼率對比.表中，參數n、k均用可用性t和局部性r表示，基于陣列LDPC碼構造的IS-LRCs可用性t只能取偶數，v為大于1的正整數.

表2 幾種典型IS-LRCs構造參數對比Tab.2 Comparison of structural parameters of several typical IS-LRCs

為了更加直觀地對比幾種方法構造出的局部修復碼的碼率，如圖2所示給出了當局部性r=11時，幾種方法構造出的局部修復碼碼率與Tamo等[14]提出的碼率上界的比較.可以看出，定理9構造的IS-LRCs碼率始終大于基于陣列LDPC碼和基于正則矩陣構造的IS-LRCs碼率，當局部性r取其他值時，可以得到相同的結論.隨著可用性t的增大，系統中存儲的冗余數據增多，碼率將緩慢減小，體現了可用性t和碼率R這2個參數之間的均衡關系.此外，Tamo等[14]提出的碼率上界適用于有限域Fq上的二元及多元局部修復碼，而定理9構造的是二元局部修復碼，有限域的大小在一定程度上限制了碼率的提高.

圖2 局部性 r=11 時的碼 率比較Fig.2 Code rate comparison with locality r=11

4 結語

考慮到具有 (r,t) 局部性的局部修復碼不僅可以實現多故障節點的局部修復，還支持數據的并行讀取，提出利用正交拉丁方構造二元局部修復碼的方法，分別構造出全符號具有 (r,t=2) 局部性和信息位具有 (r,t=2) 局部性的局部修復碼.進一步考慮到系統中存在高故障率節點，利用正交拉丁方完備組構造一類擴展可用性的單校驗局部修復碼，提高了系統的可靠性.理論分析表明，所構造的具有全符號局部性的局部修復碼碼率和碼長漸近邊界條件；信息位具有 (r,t=2) 局部性的單校驗局部修復碼的最小距離和碼率均滿足邊界條件，為最優局部修復碼；擴展可用性的單校驗局部修復碼最小距離最優，碼率較高，始終大于等于0.5.此外，所有的構造均基于二元有限域，即所有的編解碼只涉及異或運算，大大提高了編解碼速度，更加適用于實際的分布式存儲系統.

本研究構造的局部修復碼的參數與正交拉丁方的階數相關，故正交拉丁方的存在性在一定程度上限制了參數的取值，構造參數能夠更加靈活取值的局部修復碼是未來值得研究的問題.