王 靜，孫 偉*，何亞錦，沈克勤，張?chǎng)伍?，劉向?/p>

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

近年來，由于數(shù)據(jù)量的快速上升，急需一種適宜的大數(shù)據(jù)存儲(chǔ)系統(tǒng)。分布式存儲(chǔ)系統(tǒng)由許多廉價(jià)磁盤組成，以其突出優(yōu)勢(shì)成為海量數(shù)據(jù)存儲(chǔ)的有效系統(tǒng)，并被廣泛部署和使用[1]。但在分布式存儲(chǔ)系統(tǒng)中，節(jié)點(diǎn)容易發(fā)生故障，造成數(shù)據(jù)丟失。因此，故障節(jié)點(diǎn)的快速修復(fù)研究成為了分布式存儲(chǔ)系統(tǒng)可靠性的重中之重。

目前，分布式存儲(chǔ)系統(tǒng)主要通過復(fù)制和糾刪碼策略來恢復(fù)節(jié)點(diǎn)故障。復(fù)制策略中三副本復(fù)制最為常見，故障節(jié)點(diǎn)修復(fù)具有較低的修復(fù)帶寬開銷，但需要存儲(chǔ)大量的副本數(shù)據(jù)，存儲(chǔ)開銷較大。糾刪碼策略通過增加校驗(yàn)數(shù)據(jù)塊來確保數(shù)據(jù)存儲(chǔ)的可靠性，實(shí)現(xiàn)故障節(jié)點(diǎn)修復(fù)，且存儲(chǔ)開銷較小。雖然糾刪碼彌補(bǔ)了復(fù)制策略存儲(chǔ)開銷大的缺點(diǎn)，但是糾刪碼在修復(fù)故障節(jié)點(diǎn)時(shí)的修復(fù)帶寬開銷過大[2]。

鑒于復(fù)制和糾刪碼策略存在上述局限性，文獻(xiàn)[3]將網(wǎng)絡(luò)編碼應(yīng)用到分布式存儲(chǔ)中，提出了再生碼的概念，降低了故障節(jié)點(diǎn)的修復(fù)帶寬開銷。現(xiàn)在再生碼研究重點(diǎn)在最小存儲(chǔ)再生(minimum storage regeneration, MSR)碼和最小帶寬再生(minimum bandwidth regeneration, MBR)碼[4-5]。再生碼在修復(fù)故障節(jié)點(diǎn)時(shí)，需要連接大量存活節(jié)點(diǎn)以獲得較低的修復(fù)帶寬開銷，且在修復(fù)過程中涉及有限域運(yùn)算，計(jì)算復(fù)雜度相對(duì)較高。隨后，文獻(xiàn)[6]提出了局部修復(fù)碼(locally repairable codes, LRC)，使修復(fù)過程中需要連接的存活節(jié)點(diǎn)數(shù)較小，修復(fù)帶寬開銷較低，具有較好的修復(fù)局部性。將再生碼和局部修復(fù)碼結(jié)合，文獻(xiàn)[7-8]提出了局部再生碼的概念，達(dá)到存儲(chǔ)-帶寬開銷的最佳折中。其中，基于系統(tǒng)MSR碼的局部再生碼，故障局部碼可以通過相鄰局部碼進(jìn)行協(xié)作修復(fù)[9]。

文獻(xiàn)[10]提出了一種精確最小帶寬再生碼—部分重復(fù)(fractional repetition, FR)碼，故障節(jié)點(diǎn)修復(fù)過程中的計(jì)算復(fù)雜度和修復(fù)帶寬開銷都有所降低，可以實(shí)現(xiàn)故障節(jié)點(diǎn)的精確無編碼修復(fù)。近年來，許多研究人員對(duì)FR 碼進(jìn)行了研究，文獻(xiàn)[11]利用組合設(shè)計(jì)來構(gòu)造FR 碼。隨后，學(xué)者們又相繼給出了幾種基于組合結(jié)構(gòu)的FR 碼構(gòu)造，包括基于射影幾何的FR 碼構(gòu)造[12]、基于正則圖的FR 碼構(gòu)造[13]及基于可分組設(shè)計(jì)的FR 碼構(gòu)造[14]。

現(xiàn)有FR 碼對(duì)于故障節(jié)點(diǎn)的修復(fù)，特別是多節(jié)點(diǎn)故障修復(fù)，其修復(fù)帶寬開銷和修復(fù)局部性較高，同時(shí)修復(fù)復(fù)雜度也較高。文獻(xiàn)[13]提出了基于正則圖構(gòu)造FR 碼，隨后文獻(xiàn)[15]提出了運(yùn)用網(wǎng)格構(gòu)造FR 碼，但其都只能修復(fù)單節(jié)點(diǎn)故障?；谙鄬?duì)差集的FR 碼構(gòu)造，能夠修復(fù)分布式存儲(chǔ)系統(tǒng)中的多節(jié)點(diǎn)故障，但是隨著參數(shù)的增大，其節(jié)點(diǎn)存儲(chǔ)容量和構(gòu)造復(fù)雜度會(huì)隨之增大[16]。而且常見的FR 碼構(gòu)造隨著系統(tǒng)規(guī)模和參數(shù)的增大，其節(jié)點(diǎn)數(shù)或節(jié)點(diǎn)容量增大，構(gòu)造復(fù)雜度也會(huì)增大。本文提出基于Hadamard 矩陣構(gòu)造FR 碼，同時(shí)對(duì)其進(jìn)行分組，運(yùn)用8 階Hadamard 矩陣提出了分組構(gòu)造FR(Hadamard grouping fractional repetition, HGFR)碼的一般算法，實(shí)現(xiàn)故障節(jié)點(diǎn)的局部修復(fù)?；贖adamard 矩陣分組構(gòu)造FR 碼可以對(duì)多個(gè)節(jié)點(diǎn)故障進(jìn)行快速精確無編碼修復(fù)，有效降低了運(yùn)算復(fù)雜度，同時(shí)運(yùn)用了分組可以實(shí)現(xiàn)組內(nèi)修復(fù)，復(fù)雜度進(jìn)一步降低，實(shí)現(xiàn)故障節(jié)點(diǎn)的快速修復(fù)。理論分析發(fā)現(xiàn)，與RS 碼和SRC 簡單再生碼相比，設(shè)計(jì)的FR 碼在分布式存儲(chǔ)系統(tǒng)節(jié)點(diǎn)發(fā)生故障時(shí)，修復(fù)局部性、修復(fù)復(fù)雜度和修復(fù)帶寬開銷進(jìn)一步降低，且修復(fù)效率提高，減少了故障節(jié)點(diǎn)的修復(fù)時(shí)間。

1 Hadamard 矩陣和部分重復(fù)碼

1.1 Hadamard 矩陣

Hadamard 矩陣是在工程技術(shù)上運(yùn)用較多的一類矩陣，Hadamard 矩陣是特殊的1、-1 二元矩陣，具體定義如下：

定義1[17-18]n階方陣 Hn，其元素為1 或-1，并且滿足：

稱 Hn為n階Hadamard 矩陣，其中 In是n階單位矩陣。

若Hn的第1 行和第1 列全是1，該Hn為Hadamard矩陣的標(biāo)準(zhǔn)型。以下所涉及的Hadamard 矩陣 Hn均為Hadamard 標(biāo)準(zhǔn)型矩陣。

Hadamard 矩陣有如下一些性質(zhì)：

1) 將Hadamard 矩陣的任意兩行(或兩列)交換，Hadamard 矩陣的任意一行(或一列)的所有元素乘以-1，得到的矩陣仍然為Hadamard 矩陣。

2) 若 Hn是 n階Hadamard 矩陣(n ＞2)，則 n是 4 的倍數(shù)。

定義2[19]令：

其中 Jn表示元素全為1 的n階矩陣，則得到n階0-1矩陣 Kn。

性質(zhì)1 矩陣 Kn中除第一行之外，每一行都有n/2個(gè)1 和 n/2個(gè)0。

1.2 FR 碼

FR 碼是在MBR 碼基礎(chǔ)上提出的，典型的FR碼由兩部分組成，外部的MDS 碼和內(nèi)部的重復(fù)碼[20]。

定義3(FR 碼)[21]分布式存儲(chǔ)系統(tǒng)中參數(shù)為(n,k,d)的部分重復(fù)碼C=(η,M)，將數(shù)據(jù)塊復(fù)制ρ倍(即重復(fù)度為 ρ)，特定地， n個(gè)子集的集合M={M1,M2,···,Mn}，子集中的元素都來自于集合η={1,2,···,θ}。

同時(shí)應(yīng)滿足以下兩個(gè)條件：

1)每個(gè)子集的大小均為d ；

2) η中的每個(gè)元素屬于 M中的ρ個(gè)子集。

上述定義中，數(shù)據(jù)塊是經(jīng)過MDS 編碼后的數(shù)據(jù)塊。FR 碼的實(shí)質(zhì)是將數(shù)據(jù)塊復(fù)制ρ倍，然后將其排列到n個(gè)節(jié)點(diǎn)，同時(shí)使相同的數(shù)據(jù)塊不出現(xiàn)在同一個(gè)節(jié)點(diǎn)上。圖1 為經(jīng)過(12,9)MDS 編碼后構(gòu)成(12,9,4)FR 碼，其中ρ為2，數(shù)據(jù)復(fù)制2 倍，每個(gè)節(jié)點(diǎn)存放4 個(gè)編碼數(shù)據(jù)塊。

FR 碼修復(fù)故障節(jié)點(diǎn)時(shí)直接從未失效節(jié)點(diǎn)中下載丟失的所需數(shù)據(jù)塊，不進(jìn)行編譯碼操作即可完成故障節(jié)點(diǎn)的迅速修復(fù)。FR 碼可實(shí)現(xiàn)精確無編碼修復(fù)，修復(fù)帶寬開銷和修復(fù)時(shí)間較低，修復(fù)復(fù)雜度較小，同時(shí)能夠容忍ρ-1個(gè)節(jié)點(diǎn)故障。

圖1 (12,9,4)FR 碼

2 基于Hadamard 矩陣構(gòu)造FR 碼

本節(jié)基于Hadamard 矩陣構(gòu)造FR 碼。首先選取一個(gè)4t(t=1,2,3,···)階的Hadamard 矩陣，對(duì)其進(jìn)行簡單的變換得到所需要的矩陣；再將矩陣與分布式存儲(chǔ)節(jié)點(diǎn)和編碼數(shù)據(jù)塊相對(duì)應(yīng)，矩陣的行代表存儲(chǔ)節(jié)點(diǎn)，矩陣中不同的列表示不同的編碼數(shù)據(jù)塊。由Hadamard 矩陣引出FR 碼一般性構(gòu)造算法，其具體步驟如下：

1) 將原始文件 M分成k個(gè)原始數(shù)據(jù)塊，這里k ≥2。對(duì)該 k個(gè)原始數(shù)據(jù)塊采用(n,k)MDS 編碼(n ≥k)，得到n個(gè)編碼數(shù)據(jù)塊c1,···,ck-1,ck,ck+1,···,cn，n個(gè)編碼數(shù)據(jù)塊包括k個(gè)原始數(shù)據(jù)塊和n-k個(gè)校驗(yàn)數(shù)據(jù)塊；

2) 取一個(gè)n+1 階標(biāo)準(zhǔn)型Hadamard 矩陣Hn+1，其中n+1=1,2，或n+1=0(mod4)；

3) 根據(jù)公式：

得到0-1 矩陣K′n+1(n ≥k)，其中Jn+1表示元素全為1 的n+1階矩陣，Hn+1為標(biāo)準(zhǔn)Hadamard 矩陣，需滿足n+1為4 的倍數(shù)；

4) 對(duì)0-1 矩陣K′n+1進(jìn)行變換，將第一行第一列刪去得到新矩陣 Kn；

5) 通過矩陣 Kn構(gòu)造FR 碼，具體過程為：

① 矩陣 Kn中每一行代表一個(gè)節(jié)點(diǎn)，用矩陣Kn中的第i行表示分布式存儲(chǔ)系統(tǒng)中的第i個(gè)存儲(chǔ)節(jié)點(diǎn) Ni，共有n個(gè)存儲(chǔ)節(jié)點(diǎn)，i=1,2,···,n；

② 由以下公式構(gòu)造FR 碼：

式中，j=1,2,···,n； i表示第i個(gè)FR 節(jié)點(diǎn)； aij表示矩陣第i 行第j 列的值； Ni表示FR 碼的存儲(chǔ)節(jié)點(diǎn)。 Ni中包含的數(shù)據(jù)塊為矩陣 Kn中第i行所有1 所對(duì)應(yīng)的列數(shù)，將列數(shù)提取出即得到一個(gè)節(jié)點(diǎn)所存儲(chǔ)的數(shù)據(jù)塊，構(gòu)成了所需FR 碼。

采用上述FR 碼的一般性構(gòu)造算法，在包含n=11個(gè)存儲(chǔ)節(jié)點(diǎn)的分布式存儲(chǔ)系統(tǒng)中，構(gòu)造FR 碼。選取如式(3)所示的12 階Hadamard 矩陣，利用式(1)對(duì)該Hadamard 矩陣進(jìn)行變換，進(jìn)一步得到所需的11 階矩陣 K11，如式(4)所示。采用該 K11矩陣，按照步驟5)構(gòu)造得到FR 碼，該FR 碼的節(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)具體如圖2 所示。其中矩陣的行代表分布式存儲(chǔ)系統(tǒng)中的存儲(chǔ)節(jié)點(diǎn)，矩陣中不同的列表示不同的編碼數(shù)據(jù)塊，每個(gè)存儲(chǔ)節(jié)點(diǎn)存儲(chǔ)d=5個(gè)編碼塊，編碼塊的重復(fù)度ρ=5。

圖2 FR 碼的節(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)圖

當(dāng)一個(gè)節(jié)點(diǎn)發(fā)生故障時(shí)，可以運(yùn)用其他節(jié)點(diǎn)對(duì)故障節(jié)點(diǎn)進(jìn)行修復(fù)，在其他節(jié)點(diǎn)中找到并下載含有故障節(jié)點(diǎn)的數(shù)據(jù)塊，故障節(jié)點(diǎn)即完成了修復(fù)，且該過程不需要進(jìn)行編碼譯碼操作。對(duì)于圖2 中的FR碼，若節(jié)點(diǎn) N1發(fā)生故障，可以分別從存活節(jié)點(diǎn) N3中下載數(shù)據(jù)塊4 和6，從存活節(jié)點(diǎn) N4中下載數(shù)據(jù)塊2 和5，以及存活節(jié)點(diǎn) N5中下載數(shù)據(jù)塊10，實(shí)現(xiàn)節(jié)點(diǎn) N1的修復(fù)。對(duì)于兩個(gè)節(jié)點(diǎn)發(fā)生故障的情況，與一個(gè)節(jié)點(diǎn)故障修復(fù)的方法相同。

3 基于Hadamard 矩陣構(gòu)造分組FR 碼

運(yùn)用Hadamard 矩陣構(gòu)造FR 碼發(fā)現(xiàn)，隨著Hadamard 矩陣階數(shù)的增加，F(xiàn)R 碼的重復(fù)度和節(jié)點(diǎn)存儲(chǔ)容量也會(huì)隨之增加，從而導(dǎo)致存儲(chǔ)開銷也相應(yīng)地增加，故障節(jié)點(diǎn)修復(fù)性能受到一定限制。為此，本節(jié)引入分組構(gòu)造的思想構(gòu)造部分重復(fù)碼。當(dāng)Hadamard 矩陣的階數(shù)為12 時(shí)構(gòu)造的FR 碼的重復(fù)度為5，重復(fù)度較大；當(dāng)階數(shù)為8 時(shí)FR 碼的重復(fù)度降為3，更滿足實(shí)際存儲(chǔ)需求，所以本文利用8 階標(biāo)準(zhǔn)Hadamard 矩陣構(gòu)造分組FR 碼。

3.1 基于Hadamard 矩陣構(gòu)造分組部分重復(fù)碼

對(duì)分布式存儲(chǔ)系統(tǒng)節(jié)點(diǎn)進(jìn)行分組，并利用8 階Hadamard 矩陣構(gòu)造分組FR 碼(hadamard grouping fractional repetition, HGFR)。分組FR 碼的具體構(gòu)造算法如下：

1) 取一個(gè)8 階標(biāo)準(zhǔn)Hadamard 矩陣 H8；由上節(jié)構(gòu)造部分重復(fù)碼方法的步驟1)～步驟4)得到新矩陣 K7，并利用新矩陣 K7構(gòu)造FR 碼；

2) 記原始文件M 包含s個(gè)原始數(shù)據(jù)塊，將原始數(shù)據(jù)塊進(jìn)行分組，得到t個(gè)局部修復(fù)組，每組分配k=5個(gè)原始數(shù)據(jù)塊。包含以下幾種情況：

① 如果s可以被k=5整除，即s=tk ，此時(shí)每個(gè)局部修復(fù)組內(nèi)首先進(jìn)行(7, 5)MDS 碼編碼，然后采用步驟3)中的矩陣 K7構(gòu)造FR 碼；

② 如果s不能被k=5整除，即s=tk+m且m=1，前t-1 個(gè)局部修復(fù)組采用(7, 5)MDS 碼以及矩陣K7構(gòu)造FR 碼，第t 個(gè)局部修復(fù)組采用(7,6)MDS碼以及矩陣 K7構(gòu)造FR 碼；

③ 若s=tk+m且m=2，前t-2個(gè)局部修復(fù)組采用(7, 5)MDS 碼以及矩陣 K7構(gòu)造FR 碼，第t-1 個(gè)和第t 個(gè)局部修復(fù)組采用(7, 6)MDS 碼以及矩陣K7構(gòu)造FR 碼；

④ 若s=tk+m且m=3或者4 時(shí)，前t-1 個(gè)局部修復(fù)組采用(7,5)MDS 碼以及矩陣 K7構(gòu)造FR 碼，第t 個(gè)局部修復(fù)組采用(7,m)MDS 碼以及矩陣 K7構(gòu)造FR 碼。

以包含s=11個(gè)數(shù)據(jù)塊的原始文件為例，s=2k+1，這里m=1，滿足情況②。第1 個(gè)局部修復(fù)組采用(7,5)MDS 碼以及矩陣 K7構(gòu)造FR 碼，第

2 個(gè)局部修復(fù)組采用(7,6)MDS 碼以及矩陣 K7構(gòu)造FR 碼。構(gòu)造的分組FR 碼如圖3 所示。

圖3 分組FR 碼的節(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)圖

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

下面考慮分布式存儲(chǔ)系統(tǒng)采用基于Hadamard矩陣的分組FR 碼，其故障節(jié)點(diǎn)的修復(fù)?？紤]到3 個(gè)以上節(jié)點(diǎn)同時(shí)故障的概率很低，本文只考慮分布式存儲(chǔ)系統(tǒng)中1 個(gè)、2 個(gè)或者3 個(gè)節(jié)點(diǎn)故障，且在同一個(gè)或者不同局部修復(fù)組內(nèi)的情況。具體故障節(jié)點(diǎn)修復(fù)過程如下：

1)當(dāng)分布式存儲(chǔ)系統(tǒng)只有1 個(gè)節(jié)點(diǎn)故障，此時(shí)只需考慮在一個(gè)局部修復(fù)組內(nèi)對(duì)單一故障節(jié)點(diǎn)進(jìn)行修復(fù)。具體地，在該局部修復(fù)組內(nèi)其他存活節(jié)點(diǎn)中找到含有故障節(jié)點(diǎn)的數(shù)據(jù)塊，直接下載故障節(jié)點(diǎn)丟失的數(shù)據(jù)塊，即可完成故障節(jié)點(diǎn)修復(fù)，該過程不需要進(jìn)行編碼操作。如圖2 所示，如第一個(gè)局部修復(fù)組中第一個(gè)節(jié)點(diǎn)發(fā)生故障，可以下載節(jié)點(diǎn) N2、 N4、N6中的2、4 和6 這3 個(gè)數(shù)據(jù)塊完成第一個(gè)節(jié)點(diǎn)的修復(fù)。

2)當(dāng)分布式存儲(chǔ)系統(tǒng)中有2 個(gè)節(jié)點(diǎn)同時(shí)發(fā)生故障時(shí)，存在以下兩種情況：① 2 個(gè)故障節(jié)點(diǎn)在同一局部修復(fù)組內(nèi)，可以從剩余的5 個(gè)存活節(jié)點(diǎn)中下載故障節(jié)點(diǎn)所含有的數(shù)據(jù)塊，完成故障節(jié)點(diǎn)的快速修復(fù)；② 發(fā)生故障的2 個(gè)節(jié)點(diǎn)不在同一局部修復(fù)組，則需要在兩個(gè)修復(fù)組內(nèi)分別對(duì)其組內(nèi)的故障節(jié)點(diǎn)進(jìn)行修復(fù)。在圖2 中，如節(jié)點(diǎn) N2和節(jié)點(diǎn) N10發(fā)生故障導(dǎo)致數(shù)據(jù)塊丟失，可以在第一個(gè)局部修復(fù)組內(nèi)從節(jié)點(diǎn) N1、 N4、 N5中分別下載數(shù)據(jù)塊4、1 和5 完成節(jié)點(diǎn) N2的修復(fù)，在第二個(gè)局部修復(fù)組內(nèi)從節(jié)點(diǎn)N9、 N11、 N13下載數(shù)據(jù)塊11、10 和14 完成節(jié)點(diǎn)N10的快速修復(fù)。

3)當(dāng)分布式存儲(chǔ)系統(tǒng)中有3 個(gè)節(jié)點(diǎn)同時(shí)發(fā)生故障，存在以下兩種情況：①發(fā)生故障的3 個(gè)節(jié)點(diǎn)不在同一局部修復(fù)組，該情況下的故障節(jié)點(diǎn)修復(fù)與前面兩種修復(fù)過程完全一樣，只需直接從局部修復(fù)組中下載所需的數(shù)據(jù)塊；②發(fā)生故障的3 個(gè)節(jié)點(diǎn)在同一局部修復(fù)組中，如果3 個(gè)故障節(jié)點(diǎn)中沒有同時(shí)含有同一個(gè)數(shù)據(jù)塊，則可以直接從其他存活節(jié)點(diǎn)中下載丟失的數(shù)據(jù)塊，完成故障節(jié)點(diǎn)的修復(fù)；否則，需要運(yùn)用MDS 編碼進(jìn)行修復(fù)。如圖2 中節(jié)點(diǎn) N1、N2、 N3發(fā)生故障，剩余存活節(jié)點(diǎn)無法直接修復(fù)，需要從存活節(jié)點(diǎn)下載數(shù)據(jù)塊進(jìn)行MDS 編碼修復(fù)數(shù)據(jù)塊4，即完成故障節(jié)點(diǎn) N1、 N2、 N3的精確修復(fù)。

4 性能分析

本節(jié)對(duì)提出的基于Hadamard 矩陣構(gòu)造分組FR 碼進(jìn)行性能分析，修復(fù)帶寬開銷、修復(fù)局部性、修復(fù)復(fù)雜度為分析的主要性能，并與SRC 簡單再生碼以及RS 碼進(jìn)行比較。取文件大小M=1 000 Mb，SRC 簡單再生碼的子文件數(shù)f =4。

4.1 修復(fù)帶寬開銷

當(dāng)節(jié)點(diǎn)發(fā)生故障時(shí)，修復(fù)故障節(jié)點(diǎn)被下載的數(shù)據(jù)量大小稱為修復(fù)帶寬開銷。在分布式存儲(chǔ)系統(tǒng)中，原文件大小為 M，當(dāng)發(fā)生單節(jié)點(diǎn)故障時(shí)，若采用(n,k)RS 碼，則需要下載全部的原文件來修復(fù)故障節(jié)點(diǎn)，所以采用(n,k)RS 碼修復(fù)單節(jié)點(diǎn)故障的修復(fù)帶寬開銷為文件大小 M；對(duì)于(n,k,f)SRC 簡單再生碼，每個(gè)節(jié)點(diǎn)存儲(chǔ)f+1個(gè)數(shù)據(jù)塊，每個(gè)數(shù)據(jù)塊大小為M/fk，當(dāng)一個(gè)數(shù)據(jù)塊發(fā)生故障， f個(gè)數(shù)據(jù)塊被下載進(jìn)行修復(fù)，所以1 個(gè)節(jié)點(diǎn)發(fā)生故障的修復(fù)帶寬開銷為(f+1)M/k；如果采用基于Hadamard 矩陣的分組FR 碼，每個(gè)數(shù)據(jù)塊大小為M/k，每個(gè)節(jié)點(diǎn)含有3 個(gè)數(shù)據(jù)塊，所以基于Hadamard 矩陣的分組FR 碼的單節(jié)點(diǎn)故障的修復(fù)帶寬開銷為3M/k。單節(jié)點(diǎn)故障的3 種編碼方式修復(fù)帶寬開銷對(duì)比如圖4所示。

圖4 單節(jié)點(diǎn)故障時(shí)的修復(fù)帶寬開銷

當(dāng)2 個(gè)節(jié)點(diǎn)發(fā)生故障時(shí)，若采用(n,k)RS 碼，仍然需要下載全部的原文件來修復(fù)故障節(jié)點(diǎn)，所以(n,k)RS 碼修復(fù)2 個(gè)故障節(jié)點(diǎn)的修復(fù)帶寬開銷仍為M；對(duì)于(n,k,f)SRC 簡單再生碼，如果2 個(gè)故障節(jié)點(diǎn)數(shù)大于f-1，則2 個(gè)節(jié)點(diǎn)發(fā)生故障的修復(fù)帶寬開銷為2(f+1)M/k，如果2 個(gè)故障節(jié)點(diǎn)數(shù)小于f-1，需要先恢復(fù)原文件，所以修復(fù)帶寬開銷為 M，這里f=4，所以2 個(gè)節(jié)點(diǎn)故障時(shí)，SRC 簡單再生碼的修復(fù)帶寬開銷為M；如果采用基于Hadamard 矩陣的分組FR 碼，2 個(gè)故障節(jié)點(diǎn)在同一修復(fù)組時(shí)，修復(fù)帶寬開銷為3M/k，不在同一修復(fù)組時(shí)，修復(fù)帶寬開銷為6M/k。修復(fù)帶寬開銷對(duì)比如圖5 所示。

圖5 2 個(gè)節(jié)點(diǎn)故障時(shí)的修復(fù)帶寬開銷

從圖4 和圖5 可以看出，基于Hadamard 矩陣的分組FR 碼，單節(jié)點(diǎn)和兩節(jié)點(diǎn)故障時(shí)的修復(fù)帶寬開銷性能明顯優(yōu)于RS 碼和SRC 簡單再生碼，且在圖5 中RS 碼和SRC 簡單再生碼由于修復(fù)帶寬開銷一樣，所以曲線重合。

4.2 修復(fù)局部性

修復(fù)局部性是指故障節(jié)點(diǎn)修復(fù)過程中需要連接的存活節(jié)點(diǎn)數(shù)目，即修復(fù)過程中的磁盤I/O 開銷。首先對(duì)于單節(jié)點(diǎn)失效，簡單再生碼修復(fù)時(shí)需要連接2 f個(gè)存活節(jié)點(diǎn)，所以局部修復(fù)性為 2 f；RS 碼發(fā)生單節(jié)點(diǎn)故障時(shí)，需要連接k個(gè)節(jié)點(diǎn)恢復(fù)原文件修復(fù)故障節(jié)點(diǎn)，所以RS 碼修復(fù)局部性為k；基于Hadamard矩陣的分組FR 碼，連接3 個(gè)未發(fā)生故障的節(jié)點(diǎn)來恢復(fù)單個(gè)節(jié)點(diǎn)故障，所以其修復(fù)局部性為3。單節(jié)點(diǎn)故障時(shí)的修復(fù)局部性對(duì)比如圖6 所示。

對(duì)于2 個(gè)節(jié)點(diǎn)發(fā)生故障，SRC 簡單再生碼需要先恢復(fù)原文件才可以修復(fù)故障節(jié)點(diǎn)，所以SRC簡單再生碼的修復(fù)局部性為k；對(duì)于RS 碼，仍然需要恢復(fù)原文件，所以修復(fù)2 個(gè)節(jié)點(diǎn)的修復(fù)局部性也為k；基于Hadamard 矩陣的分組FR 碼，分兩種情況：1) 如果一個(gè)修復(fù)組中發(fā)生2 個(gè)節(jié)點(diǎn)故障，從3 個(gè)未失效節(jié)點(diǎn)中下載所需數(shù)據(jù)，修復(fù)局部性為3；2) 2 個(gè)故障節(jié)點(diǎn)不在同一個(gè)局部修復(fù)組內(nèi)，其修復(fù)兩個(gè)故障節(jié)點(diǎn)需要連接6 個(gè)存活節(jié)點(diǎn)，修復(fù)局部性為6。

圖6 單節(jié)點(diǎn)故障時(shí)的修復(fù)局部性

修復(fù)故障節(jié)點(diǎn)時(shí)，可以看出基于Hadamard 矩陣的分組FR 碼的修復(fù)局部性，優(yōu)于簡單再生碼和RS 碼的修復(fù)局部性。

4.3 修復(fù)復(fù)雜度

本文提出的基于Hadamard 矩陣的分組FR碼，當(dāng)發(fā)生節(jié)點(diǎn)故障時(shí)，可以直接從其他存活節(jié)點(diǎn)下載數(shù)據(jù)塊進(jìn)行修復(fù)，無需進(jìn)行編碼運(yùn)算。對(duì)于RS 碼修復(fù)故障節(jié)點(diǎn)需要先恢復(fù)原文件，之后再編碼生成所需要的數(shù)據(jù)塊，編碼數(shù)據(jù)塊由k個(gè)數(shù)據(jù)塊在有限域GF(q)上運(yùn)算得到。所以RS 碼在修復(fù)單節(jié)點(diǎn)故障時(shí)需要k2+k次有限域乘法運(yùn)算和k2-1次有限域加法運(yùn)算。對(duì)于SRC 簡單再生碼，其修復(fù)一個(gè)故障節(jié)點(diǎn)需要進(jìn)行(f-1)(f+1)次異或運(yùn)算?？梢钥闯觯疚臉?gòu)造的FR 碼修復(fù)復(fù)雜度明顯低于RS 碼和SRC 簡單再生碼的修復(fù)復(fù)雜度，可以快速修復(fù)故障節(jié)點(diǎn)，修復(fù)時(shí)間減少。

表1 給出了分布式存儲(chǔ)系統(tǒng)中，RS 碼、簡單再生碼和基于Hadamard 矩陣的分組FR 碼分別在修復(fù)帶寬開銷、修復(fù)局部性及節(jié)點(diǎn)存儲(chǔ)開銷三方面的性能比較。從表1 可以看出，基于Hadamard 矩陣的分組FR 碼其修復(fù)局部性和帶寬開銷較低。而且，基于Hadamard 矩陣的分組FR 碼在修復(fù)節(jié)點(diǎn)故障時(shí)可以實(shí)現(xiàn)精確無編碼修復(fù)，運(yùn)算復(fù)雜度較低，修復(fù)時(shí)間減少，可靠性提高。

5 結(jié) 束 語

現(xiàn)有傳統(tǒng)編碼方式對(duì)于故障節(jié)點(diǎn)的修復(fù)，特別是對(duì)多故障節(jié)點(diǎn)的修復(fù)，其修復(fù)帶寬開銷和修復(fù)局部性能受限，同時(shí)修復(fù)復(fù)雜度較高。為此，本文提出了基于Hadamard 矩陣的FR 碼，同時(shí)對(duì)其進(jìn)行分組，運(yùn)用8 階Hadamard 矩陣提出了分組FR 碼的一般性構(gòu)造算法。理論分析發(fā)現(xiàn)，基于Hadamard矩陣的分組FR 碼可以對(duì)多故障節(jié)點(diǎn)進(jìn)行快速精確無編碼修復(fù)，有效降低了運(yùn)算復(fù)雜度，同時(shí)運(yùn)用了分組可以實(shí)現(xiàn)組內(nèi)修復(fù)，復(fù)雜度進(jìn)一步降低。與RS 碼和SRC 簡單再生碼相比，發(fā)生故障時(shí)的修復(fù)局部性、修復(fù)復(fù)雜度和修復(fù)帶寬開銷進(jìn)一步降低，且修復(fù)效率提高，減少了故障節(jié)點(diǎn)的修復(fù)時(shí)間。