基于差集矩陣的部分重復碼構造

王 靜 何亞錦 雷 珂 劉向陽

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

②(西北工業大學電子信息學院 西安 710129)

1 引言

由于社交媒體和網絡信息的興起，數據呈現爆炸式增長，傳統的集中式存儲已經無法滿足需求。分布式存儲系統以其價格低廉、性能優異等優點，日益成為主流存儲系統。在分布式存儲系統中，即使存在故障節點的情況下，也需要保證數據存儲的完整性和數據訪問的速度。這個問題通常使用復制和糾刪碼策略[1,2]來解決。

復制策略就是將數據塊復制若干倍，然后將其分別存放在不同的存儲節點上。其中最常見的為3副本復制，如Google文件系統(Google File System,GFS)[3]。在節點故障的時候，由于副本的存在，只需簡單復制數據即可修復。整個修復過程簡單易實現，但是卻增加了分布式存儲系統的存儲負擔。為了進一步優化存儲開銷，提出糾刪碼策略。糾刪碼策略是將原始文件分成若干塊進行編碼產生冗余校驗塊來保證數據存儲的可靠性，目前在Windows[4],Facebook的Hadoop集群(Facebook’s Hadoop cluster)[5]等已經投入使用。雖然糾刪碼減少了存儲開銷，但是在節點故障修復的時候，需要下載整個原文件，過程復雜，且修復帶寬開銷大。

為了進一步優化存儲系統，文獻[6]提出了再生碼(Regenerating Codes, RC)，在單節點故障時，再生碼不需重構原文件就能修復，降低了修復帶寬開銷，但是在修復過程中涉及的計算量比較大。Papailiopoulos等人[7]利用線性組合的思想構造了無參數限制的最小帶寬再生碼(Minimum Bandwidth Regenerating, MBR)，結構簡單。Rashmi等人[8]提出了鋸齒狀最小存儲再生碼(Minimum Storage Regenerating, MSR)構造，在有限域F3上計算開銷較小。隨后，Guan等人[9]在較小的有限域內構造了MSR碼，構造復雜度低。為了降低故障節點的修復局部性，Gopalan等人[10]和Papailiopoulos等人[11]提出了局部修復碼(Locally Repairable Codes, LRC)的概念，即單個故障節點可以通過訪問最多r個存活節點來實現數據恢復。文獻[12]將再生碼和局部修復碼結合，提出了基于系統MSR碼的局部再生碼，節點故障修復時利用相鄰局部碼進行協作修復。文獻[13]給出具有(r,t)局部性的局部修復碼的最小距離上界，并且構造的LRC能容忍多節點故障，在修復過程中可以并行讀取數據，減少修復時間。

El Rouayheb等人[14]提出了部分重復(Fractional Repetition, FR)碼，它是基于最小帶寬點的精確修復再生碼，采用外部的最大距離可分(Maximum Distance Separable, MDS)碼和內部的重復碼構成。FR碼在修復故障節點時，只需要復制相應的編碼塊，無需編碼計算就可完成修復[15]。文獻[16]給出了基于Steiner系的FR碼的構造和仿射幾何等可分解組合設計，并利用Kronecker和構造出具有較低修復局部性的新FR碼。文獻[17]提出了基于部分有序集的普遍好的FR碼的簡單構造，構造的FR碼易于實現且可擴展，與MBR碼相比，允許存儲更大的文件。Zhu等人[18–20]研究了FR碼與其對偶碼之間的關系，進一步利用正則圖和組合設計構造達到最小距離上限的FR碼，并給出了FR碼重構度的下限。

此后，還有很多學者進行了這方面的研究，FR碼的構造一直是一個重要的研究課題。文獻[21]引入一種新的組合模型，構造具有均衡訪問頻率的最優FR碼。文獻[22]基于二部圖的任意周長構造出參數可調節的FR碼，并證明其最優性。Prajapati等人[23]使用部分正則圖構造異構的(每個節點上存儲的數據包數量不同)普遍好的FR碼，對于部分參數，使用環構造和t?設計構造普遍好的FR碼。上述構造的FR碼都是基于圖構造的，過程相對復雜，并且重復度通常是由結構固定，不能對任意參數的FR碼進行構造。

考慮到現有的FR碼的構造算法復雜且不能靈活地選擇構造參數，本文提出一種基于差集矩陣的FR碼的構造算法，可以同時調整數據塊的重復度和節點的存儲容量，且在參數選取上不受限制。進一步可以通過調整差集矩陣的參數λ，構造局部性較小的FR碼。實驗結果表明，構造的FR碼具有更低的修復局部性，修復簡單且效率高，減少了故障節點的修復時間。

2 預備知識

2.1 FR碼

(n,k,d)分布式存儲系統(Distributed Storage System, DSS)中，其中n表示的是系統中的存儲節點總數，k表示重構原始文件需要連接的節點數，d(≥k)表示修復單個故障節點需要連接的節點數。當存儲節點故障時，新生節點需要從其他存活節點下載β個數據塊進行精確修復，即修復后的數據和失效時的數據是完全一樣的。文獻[23]指出在精確修復模式下，當β=1時 ，系統的存儲容量CMBR為

在DSS中，FR碼外部采用MDS碼，將MDS碼編碼后的θ個編碼塊復制ρ倍，再將它們分別存放在n個不同的存儲節點上，每個節點的存儲大小為α，連接任意k個節點就可以重構原始文件，記為FR(n,θ,ρ,α)?？紤]到節點之間會存儲相同編碼塊，本文給出FR碼的文件大小M(k) 的定義，即任意k個節點Vi(i ∈{1,2,...,k})所獲得的不同數據塊的個數即求并集

文獻[13]指出如果滿足M(k)≥CMBR(n,k,d)，則稱該FR碼是最優的。

2.2 差集矩陣

如果矩陣G表示一個p階可加群，其元素為0,1,...,p ?1。 給定一個矩陣D，如果矩陣D中的任意兩列的有序差中，G的每個元素都出現且出現的次數相同，本文稱矩陣D為差集矩陣(difference matrix)，用D(λp,q;p)表 示。它是元素屬于G的一個具有p水 平的λp×q的差集矩陣，λ表示D中的任意兩列的有序差中，G中的每個元素出現的次數。

2.3 Kronecker和及正交排列

G表示一個n階可加群，其元素為0 ,1,...,n ?1。假設矩陣A=(aij)n×r,B=(bij)m×s，則矩陣A和B的Kronecker和為

其中，aij+B表 示aij與B中 的每個元素做模n加法運算。接下來，為了后面表述更加方便，用1r表示r×1 階 的 全1 矩 陣，(r) 表 示r×1 矩 陣(0,1,...,r ?1)T。

一個λn2×l的 矩陣，如果滿足矩陣的任意兩列由G的n個元素所構成的n2個序對，任一序對都出現在這兩列的λ個行中，則稱這個矩陣為正交排列，記為O A(n,l;λ)。

3 基于差集矩陣的FR碼構造

本節利用差集矩陣構造FR碼，構造的FR碼可以調整編碼塊的重復度，并且可以通過設計參數λ，進一步調節節點之間共有的編碼塊數，達到減小修復局部性的目的。

3.1 基于差集矩陣的FR碼的構造算法

設G為p階可加群，元素為0 ,1,...,p ?1。若存在元素屬于G的一個差集矩陣D(λp,q;p)，構造矩陣為

具體地，基于差集矩陣λ=1的FR碼的具體構造步驟如下所示：

當l>1,p>1 且l≤q+1(q為p的 最 小 素 因數)時，給出了 OA(p,(q+1);1)的通用構造方法，并在此基礎上構造了普遍好的FR碼。

設α=[0,1,...,p ?1]T,αi=[i,i,...,i]T(i=0,1,...,p ?1)， 定義函數Mj(α)=[0+j, 1+j, ...,p ?1+j]T，其中i+j(i=0,1,...,p ?1)表 示模p加 ，構造如式(5)的正交矩陣

矩陣O A可以進一步表示成

根據差集矩陣的定義，O A(p,(q+1);1)=[D(p,q;p)⊕(p),(p)⊕0p]，可以驗證得

是一個模p加法群上的差集矩陣。這里的OA(p,(q+1);1),D(p,q;p) 中 的(p ?1) 和(q ?1)分 別 表示數p?1 和數q?1 ，而(p)=(0,1,...,p ?1)T。

定理1正交排列 OA(p,(q+1);λ)構造FR碼，共有p(q+1)個 節點，λp2個 編碼塊，重復度為q+1，節點存儲大小為λp，即F R(λp2,p(q+1),q+1,λp)。節點故障時，需要連接p個節點修復。

證明正交排列OA(p,(q+1);λ)=[D(λp,q;p)⊕(p),(p)⊕0λp]矩 陣是一個λp2×(q+1)矩 陣，O A 的λp2行對應λp2個不同的編碼塊，O A 的q+1列對應著FR碼的重復度。由構造過程可知， OA 的任一列都包含了所有的編碼塊，且每個編碼塊都正好與唯一的節點相關聯，因此由正交排列 OA矩陣構造的FR碼有q+1個 平行類，即正交排列O A矩陣的每一列都是一個平行類，本文稱FR碼是可分解的。每列取p個不同的元素，每個元素在該列中出現λp次。針對某列，將取相同元素所在行編碼塊放置在一個節點中，節點之間有λ個相同的編碼塊。故單節點故障時，只需從p個節點上下載λ個編碼塊即可修復?？紤]多節點故障時，因為每個平行類含有p個節點，故多節點故障時同樣僅需從p個節點中下載數據即可完成修復。 證畢

定理2由上述λ=1的差集矩陣構造的FR碼是最優的FR碼。

證明λ=1時 ，正交排列O A(p,(q+1);1)，矩陣O A任兩列的元素所組成的有序對僅出現1次，即任意兩列中的兩行的元素對不會完全相同。由FR碼的構造方法可知，每一列對應一個平行類，所以平行類之間的存儲節點有一個編碼塊相同。假定FR碼每個節點存儲大小為d，即修復度，連接任意k個節點可以重構原文件。因為兩個節點之間最多相交一個編碼塊，所以當連接k個不同的節點時，最多可以得到個重復數據塊，根據FR碼原文件大小的定義可得M(k)≥kd ?()=CMBR。因此，由λ=1的差集矩陣構造的FR碼是最優的FR碼。 證畢

引理1當λ=1 且p為素數時，構造的FR碼的重復度ρ=2。

證明p為素數時，其最小素因子q=1，則構造的差集矩陣為D(p,1;p)， 進一步得到一個p×2的正交矩陣 O A(p,2;1)，已知正交矩陣有兩列，故構造的FR碼的重復度ρ=2。 證畢

引理2當p為合數時，構造的FR碼的重復度ρ ≥3。

證明p為合數時，可知其最小素因子最小為q(q ≥2) ， 構造的差集矩陣為D(p,q;p)，進一步得到一個p×(q+1)的 正交矩陣O A(p,(q+1);1)，又已知構造的FR碼的重復度為q+1(q+1≥3)，所以構造的FR碼的重復度ρ≥3。 證畢

定理3由λ=2的差集矩陣構造的FR碼，令k=p+1 ，且k= 3w+v，任意連接k個節點所獲得的最小文件大小為

證明考慮λ=2 ，故λp的最小素因子為2，即q=2 ，則進一步構造基于λ=2 的差集矩陣的FR(2p2, 3p, 3, 2p)碼 。FR碼每個節點存儲大小為2p， 一個平行類含有p個節點，不論單節點還是多節點的節點故障，僅需連接p個節點即可修復。

考慮節點故障修復的局部性，令k=p+1 ，其中k= 3w+v，文件大小為M(k)=min|Ui∈kVi|,k ∈{1,2,...,p},|k|=k

考慮兩個節點相交的編碼塊數，優先考慮不在一個平行類中的節點。任取k個節點所獲得的編碼塊為2kp，根據k= 3w+v可知，有3?v個 平行類取w個 節點，有v個平行類取w+1個節點。由于同一平行類內的節點之間無相交編碼塊，而平行類間的兩節點之間有一個相同的編碼塊。當0w＜2時 ，k個節點至少有2[()?v]個 編碼塊，w≥2 時，k個節點至少有2 [()?v()?(3?v)()]個 相同編碼塊。考慮p是每個節點存儲的編碼塊數，p最小取2，故k最小為3。由構造過程可知，分別從3個平行類中取1個節點，則3個節點最少相交1個編碼塊。故

3.2 構造法的應用

例1當p為素數且p=3 時，其最小素因數q=1 ，則構造正交矩陣OA(3,2;1)=[D(3,1;3)]⊕(3),(3)⊕03] 如式(11)所示，矩陣O A(3,2;1)后面為所對應的編碼塊。

由于 O A(3,2;1)矩陣的每一列都包含了所有的編碼塊，且每個編碼塊只對應唯一的一個節點。因此每一列都是一個平行類?？紤]矩陣的最后一列，前3個元素取第1水平0，即水平“0”，于是把“1,2,3”放到p2的第“1”個節點中。類似地，把“4,5,6”放到p2的第“2”個節點中，把“7,8,9”放到p2的第“3”個節點中，這3個節點構成平行類p2。 同理可以得到平行類p1的3個節點，最終得到6個節點。

將原文件M分成6 個數據塊，采用(9, 6)MDS碼編碼，得到9個編碼塊。用戶連接任意3個節點至少可以獲得6個不同的數據塊，即可重構原文件M。又由CMBR=3×3?=6，所以構造的FR碼是最優的。構造的FR碼的重復度ρ=2，并且有2個平行類，每個平行類包含了所有的數據塊。

例2令p=4， 其最小素因子q=2，則可以得到一個 4×2 的差集矩陣D(4,2;4)。利用差集矩陣D(4,2;4) ，構造得到矩陣OA(4,3;1)=[D(4,2;4)⊕(4),(4)⊕04]， 如式(13)所示。矩陣O A(4,3;1)后面附的是相對應的編碼塊

采用系統( 16,13)MDS碼，每個節點存儲4個編碼塊。如果選取其中的任意兩個平行類，則可以得到一個重復度ρ=2的FR碼；如果取3個平行類，就得到了重復度ρ=3的FR碼。

例3考慮λ=2 ， 利用差集矩陣D(6,2;3)，構造得到矩陣O A(3,3;2)=[D(6,2;3)⊕(3),(3)⊕06]，如下所示。通過該設計，我們可以得到一個ρ=3的FR碼，并且有3個平行類。更具體地說，采用系統(18, 15)MDS碼，對15個數據塊編碼，可以生成3個校驗塊，其中每個節點存儲6個數據包。如果節點V1故障，則新生節點可以從節點V4下載{1,10}，從V5下 載{4,13}，從V6下載{7,16}，來修復故障節點V1；或者從V7下載{1,4}，從V8下載{7,10}，從V9下 載{13,16}，實現故障節點V1的修復。進一步可以看出，任意連接k=4個節點，用戶都可以恢復原文件。且當λ=2時，上述構造出來的FR碼是局部修復碼，單節點的修復局部性為3

3.3 故障節點修復

分布式存儲系統中出現節點故障，在修復過程中需要連接的節點集合稱為修復組。本節主要從單節點故障、兩節點故障以及多節點故障進行分類討論，具體修復過程如下：

當單節點故障的時候，只需要連接任意一個完整平行類即可進行精確無編碼修復。如例2構造的FR碼，當第1個平行類p1中 的節點V1故障時，可以從平行類p2中 的節點V5下載編碼塊1，從節點V6下載編碼塊5，從節點V7下載編碼塊9，從節點V8下載編碼塊13，進行無編碼精確修復。節點V1故障也可以從平行類p3中 的4個節點{V9,V10,V11,V12}進行修復，或者利用平行類p2和p3混合修復如修復集{V5,V6,V11,V12}等多種修復選擇方案。連接任意修復組中的4個節點通過復制相關編碼塊即可進行無編碼精確修復故障節點。

當系統中出現兩個節點同時故障時，分為以下情況：如果重復度ρ=2，兩個故障節點在同一個平行類中，則可以利用另一個平行類進行修復；如果兩個故障節點不在同一個平行類，且兩個故障節點有一個編碼塊相同，這種情況下就不能采用復制的方式進行修復，需要利用其余存活節點恢復原文件，進一步修復故障節點。如例1中的節點V1和V2故 障，兩個故障節點都在平行類p1，則可以用另一個平行類p2中 的3個節點{V4,V5,V6}來修復故障節點。如果節點V1和 節點V4同時故障，由于兩個故障節點中含有相同編碼塊，故不能采用簡單復制的方式，可以連接其余兩個節點V2和V3進行MDS碼編碼恢復原文件，進一步精確修復故障節點V1和V4。針對重復度ρ>2的情況，不論是兩個故障節點在一個平行類，還是其他情況，均可以利用其他平行類中的節點下載相應編碼塊進行精確修復。如例2中的節點V1和V5故障，可以利用平行類p3中的4個節點{V9,V10,V11,V12}進行修復。

對于修復多個故障節點，可以分為以下4種情況：(1) 若多個故障節點都在同一個平行類，則可以利用其他平行類進行修復；(2)對于多個故障節點不在同一個平行類的情況，若還存在不包括故障節點的平行類，那么就可以直接用不包括故障節點的平行類進行修復；(3)若多個故障節點分布在所有平行類中，且不存在所有平行類中的故障節點都包含同一個或者多個編碼塊的情況，此時可以通過連接多個平行類中的存活節點來修復故障節點。(4)若多個故障節點分布在所有平行類中，且有一個或者多個編碼塊無法從現有存活節點中獲得，此時無法再采用復制方式進行修復，需要利用存活節點先恢復原文件，從而修復故障節點。

4 性能分析

基于差集矩陣構造的FR碼的性能分析主要集中在節點修復選擇度、修復復雜度、修復帶寬開銷和修復局部性這幾方面，并將其與里德-所羅門(Reed-Solomon, RS)碼和簡單再生碼(Simple Regenerating Codes, SRC)進行性能比較。

表1給出了相同文件情況下RS碼、SRC和基于λ=1差集矩陣構造的FR碼的修復帶寬開銷和修復局部性。本文構造的FR碼外部采用(k+3,k)MDS碼。

表1 RS碼、SRC和FR碼的故障節點修復性能比較

4.1 節點修復選擇度

節點修復選擇度指的是故障節點修復過程中的修復選擇方案。考慮單節點故障的修復選擇度，對于 (n,k)R S碼，從n?1 個存活節點隨機選取k個來修復故障節點。因此， (n,k)RS碼的修復選擇度為。 對于SRC，從n?1個 存活節點隨機選取f個存活節點來修復故障節點，故其修復選擇度為。 基于λ=1差集矩陣構造的FR碼，其選擇度主要與重復度ρ和節點存儲大小α有關。如果構造的FR碼的重復度ρ=2，那么節點故障時的修復選擇度僅為1，只需要連接具有相同編碼塊的存活節點即可修復。如果構造的FR碼的重復度ρ>2時，故障節點修復可以有多種修復方案。對于任意單節點故障，都可以從其他ρ?1個存活節點選擇修復。對于重復度為ρ、節點存儲大小為α的FR碼，節點故障的時候，只需要從其他副本中下載相應的數據塊即可。由于任意兩個節點之間最多相交1個編碼塊，修復一個節點中的第1個編碼塊和第2個編碼塊均有ρ?1 種選取方案，故其修復選擇度為(ρ ?1)α。從圖1看出，當FR碼節點存儲大小α=3時，基于λ=1差集矩陣構造的FR碼節點修復選擇度隨著重復度的增加呈指數倍增加。

圖1 節點修復選擇度與重復度ρ 之間的關系，其中α=3

4.2 修復復雜度

對于(n,k)R S碼，在修復過程中需要連接k個節點恢復原文件，再重新編碼生成故障節點。整個故障節點修復過程涉及大量的有限域運算，需要k2+k次有限域乘法運算和k2?1次有限域加法運算，因此RS碼在單節點故障時的修復復雜度為O(2k2+k ?1)。對于SRC，修復一個編碼塊需要進行f?1 次 異或運算，由于每個節點存儲f+1個編碼塊，因此SRC的修復過程需要(f+1)(f ?1)次異或運算，其修復復雜度為O(f2?1)。基于差集矩陣構造的FR碼，整個過程只涉及文件的讀取，無需編碼，過程簡單，修復復雜度明顯低于RS碼和SRC這兩種編碼方案。

4.3 修復帶寬開銷

分布式存儲系統中出現節點故障，在修復過程中下載的數據量大小稱為修復帶寬開銷。針對單節點故障，傳統的(n,k)RS碼在修復過程中需要下載整個原文件來修復故障節點，故單節點修復帶寬開銷為M；對于(n,k,f)SRC, SRC在修復過程中需要連接f個存活節點，每個節點存儲f+1個數據塊，且單個數據塊大小為M/fk，故單節點修復帶寬開銷為 (f+1)M/k；針對本文基于λ=1差集矩陣構造的FR碼，由構造可知一個平行類中有λp2個編碼塊，節點存儲大小為λp， 由于外部采用系統(k+3,k)M DS碼，故有λp2=k+3，經計算可知，一個平行類中含有p=個節點，每個數據塊大小為M/k， 故基于λ=1差集矩陣構造的FR碼的修復帶寬開銷為?？紤]到基于λ=1構造的FR碼是最優的，由文獻[13]可知，M(k)≥CMBR√(n,k,d)， 故可以得出M(k)≥?(k ?1)k/2。因此可以計算出FR碼的最小修復帶寬開銷為k+3?，可計算出k=1時最小，修復帶寬開銷為4，此時M(k)≥2。

在性能分析部分提前設定相關參數，文件大小恒為M= 1000 Mb ，SRC的子文件數f=4。單節點故障時，SRC的修復帶寬開銷為5M/k，采用例2中構造的FR碼的修復帶寬開銷為4M/k，由于文件大小為M= 1000 Mb ，并且基于λ=1構造的FR碼是最優的，滿足M(k)≥CMBR(n,k,d)，因此k存在最大值，當k取最大值時，修復帶寬開銷最小。單節點故障修復帶寬開銷如圖2所示。

當兩節點故障時，傳統的 (n,k)RS碼在修復過程中需要下載整個原文件來修復故障節點，故兩節點修復帶寬開銷依舊為M；對于(n,k,f)SRC，其修復帶寬受兩個故障節點之間的節點數影響。如果節點數大于f?1，那么這兩個故障節點可以分別連接f個存活節點來修復，此時的修復帶寬開銷為2(f+1)M/k，反之如果節點數小于f?1，不能按照單節點故障修復方法進行修復，需要先恢復原文件，進一步修復故障節點，故修復帶寬為M。針對本文基于λ=1差集矩陣構造的FR碼，由于一個平行類含有個節點，故兩個節點故障時的修復帶寬開銷依舊為。

兩個節點故障時，采用例2中FR碼的修復帶寬開銷為4M/k， 而RS碼和SRC的修復帶寬開銷為M。兩節點故障修復帶寬開銷如圖3所示，其中RS碼和SRC的曲線重合。

從圖2和圖3可以看出，不論是單節點故障還是多節點故障，基于λ=1差集矩陣構造的FR碼的修復帶寬開銷明顯優于RS碼和SRC簡單再生碼。

圖2 λ =1時單節點故障修復帶寬開銷性能對比

圖3 λ =1時兩節點故障修復帶寬開銷性能對比

4.4 修復局部性

考慮單節點故障時，(n,k)RS碼在修復過程中，需要連接k個節點，修復局部性為k；而SRC需要連接2f個節點，修復局部性為2f；針對基于差集矩陣構造的FR碼，由構造可知一個平行類中共有λp2個編碼塊，節點存儲大小為λp，一個平行類中包含p個節點，故單節點故障修復局部性為p。采用系統(k+3,k)MDS碼，故有λp2=k+3，經計算可知，單節點故障的修復局部性為p=。

考慮兩節點故障，SRC和 (n,k)RS碼的修復局部性均為k。而本文提出的基于差集矩陣的FR碼，一個平行類含有p個節點，故p個節點即√可以修復任意節點故障，因此修復局部性恒為p=。

假設F R 碼外部采用 (k+3,k)M D S 碼中的k=13 ， 則λ=1構 造的FR碼外部采用( 16, 13)MDS碼。如圖4所示，考慮單節點故障，( 16, 13)RS碼的修復局部性為13；當f取4時，SRC的修復局部性為8；采用例2中構造的FR碼的修復局部性為4。當兩個節點故障時，( 16, 13)RS碼和SRC的修復局部性均為13，采用例2中FR碼的修復局部性仍為4，具體如圖4所示。與RS碼和SRC相比，無論單節點故障還是兩節點故障，基于λ=1的差集矩陣構造的FR碼都具有較優的修復局部性。

圖4 λ =1時單節點故障修復局部性性能對比

假設FR碼外部采用(k+3,k)M DS碼中的k=15，則基于λ=2的差集矩陣構造的FR碼外部采用(18, 15)M DS碼。如圖5所示，單節點故障時，(18, 15)RS碼的修復局部性為15；當f取4時，SRC的修復局部性為8；采用例3中FR碼的修復局部性為3?？紤]兩節點故障時， ( 18, 15)RS碼和SRC的修復局部性均為15，采用例3中FR碼的修復局部性仍為3。與RS碼和SRC相比，無論單節點故障還是兩節點故障，基于差集矩陣λ>1的FR碼都具有較小的修復局部性。

圖5 λ =2時兩節點故障修復局部性性能對比

5 結論

針對目前基于部分圖構造的FR碼，構造過程復雜，本文提出了一種基于差集矩陣的FR碼的構造算法，可以容忍多節點故障，同時可以任意調整節點間的共有編碼塊數，在參數選取上比較靈活。進一步證明了提出的基于差集矩陣λ=1的FR碼是最優的，并給出了基于差集矩陣λ=2構造的FR碼的文件大小，且其修復局部性明顯減小。性能分析和仿真結果表明，與傳統的RS碼和SRC相比，構造的FR碼雖然犧牲了存儲開銷，但是可以顯著減少故障節點的修復局部性和修復帶寬開銷，降低修復復雜度。