孫 偉,沈克勤,張鑫楠,何亞錦

(長安大學(xué) 信息工程學(xué)院,西安 710064)

近些年,隨著信息技術(shù)和大數(shù)據(jù)產(chǎn)業(yè)的發(fā)展,數(shù)據(jù)量激增,傳統(tǒng)集中存儲(chǔ)設(shè)備已無法滿足海量數(shù)據(jù)存儲(chǔ)要求.分布式存儲(chǔ)系統(tǒng)(DSS)應(yīng)運(yùn)而生,DDS是由許多廉價(jià)磁盤組成,具有成本低、可用性強(qiáng)和可擴(kuò)展性高等突出優(yōu)勢(shì).它作為可存儲(chǔ)大量數(shù)據(jù)的存儲(chǔ)系統(tǒng)已經(jīng)被許多互聯(lián)網(wǎng)企業(yè)應(yīng)用,例如Microsoft和Facebook[1,2].然而分布式存儲(chǔ)系統(tǒng)的節(jié)點(diǎn)易發(fā)生故障而造成數(shù)據(jù)丟失,所以故障節(jié)點(diǎn)的修復(fù)成為研究的重點(diǎn).

主要通過復(fù)制和編碼來保證數(shù)據(jù)的可靠性.傳統(tǒng)的DSS 多采用復(fù)制(replication)策略[3],其中三副本最為常見.將文件復(fù)制2 次即得到3 個(gè)副本,分別將其存儲(chǔ)到系統(tǒng)的不同節(jié)點(diǎn).當(dāng)有節(jié)點(diǎn)發(fā)生故障導(dǎo)致數(shù)據(jù)丟失,可以通過其他正常節(jié)點(diǎn)的副本進(jìn)行修復(fù).但是其占有的存儲(chǔ)系統(tǒng)開銷過于龐大.于是Dimakis 提出了糾刪碼(erasure codes)策略[4].與復(fù)制策略相比,經(jīng)典的糾刪碼具有更大的數(shù)據(jù)可靠性和較小的存儲(chǔ)開銷.其中最大距離可分(Maximum Distance Separable,MDS)碼獲得最優(yōu)的存儲(chǔ)開銷性能.但是糾刪碼修復(fù)故障節(jié)點(diǎn)時(shí)需要的修復(fù)帶寬開銷過大.由于上述缺陷,Dimakis等[4]開創(chuàng)性的提出并介紹了再生碼,研究發(fā)現(xiàn)在故障節(jié)點(diǎn)修復(fù)時(shí)其的修復(fù)帶寬開銷明顯降低.但是再生碼修復(fù)故障節(jié)點(diǎn)時(shí)需要大量有限域的運(yùn)算,計(jì)算復(fù)雜度大.

2010年Rouayheb 提出了部分重復(fù)(Fractional Repetition,FR)碼,FR 碼是一種精確最小帶寬再生碼,修復(fù)故障節(jié)點(diǎn)時(shí)的修復(fù)帶寬減小,同時(shí)不需要大量有限域的運(yùn)算,計(jì)算復(fù)雜度較小[5,6].所以越來越多研究人員開始研究FR 碼,Ramamoorthy 設(shè)計(jì)的FR 碼引入了組合設(shè)計(jì)的思想[7].相繼利用二部圖[8],Steiner 系[9]和序列[10]構(gòu)造FR 碼.隨后研究人員又研究了FR 碼的修復(fù)消耗最小化[11].

部分重復(fù)碼的現(xiàn)有編碼方式節(jié)點(diǎn)的存儲(chǔ)容量基本相同,同時(shí)重復(fù)度也基本相同,都屬于同構(gòu)編碼方式,但是分布式存儲(chǔ)系統(tǒng)由于設(shè)備故障,硬件差別等原因,導(dǎo)致存儲(chǔ)成本不同,各個(gè)節(jié)點(diǎn)存儲(chǔ)容量不同,因此需要異構(gòu)編碼方式.本文提出基于Hadamard 矩陣和[7,3,4]圖形分別構(gòu)造異構(gòu)的部分重復(fù)碼的一般算法.與現(xiàn)有的FR 碼相比,采用Hadamard 矩陣和[7,3,4]圖形構(gòu)造FR 碼更加簡潔明了,其中基于Hadamard 矩陣可實(shí)現(xiàn)由同構(gòu)經(jīng)過簡單變換為異構(gòu)編碼方式;基于[7,3,4]圖形構(gòu)造FR 碼可實(shí)現(xiàn)擴(kuò)展延伸,若當(dāng)前結(jié)構(gòu)無法滿足需求,可對(duì)其進(jìn)行擴(kuò)展,直至滿足需求,而且無需改變現(xiàn)有結(jié)構(gòu).經(jīng)過與RS 碼理論分析對(duì)比發(fā)現(xiàn),設(shè)計(jì)的兩種異構(gòu)FR 碼的修復(fù)局部性、修復(fù)帶寬開銷進(jìn)一步降低,且可以實(shí)現(xiàn)故障節(jié)點(diǎn)精確無編碼修復(fù),修復(fù)復(fù)雜度較低,修復(fù)效率較高,減少了修復(fù)故障節(jié)點(diǎn)的時(shí)間.

1 基礎(chǔ)知識(shí)

1.1 Hadamard 矩陣

定義1[12].滿足:HnHnT=nIn>;Hn是一個(gè)n階方陣其由1 或?1 構(gòu)成,In是一個(gè)n階單位矩陣,稱Hn為n階Hadamard 矩陣.

Hadamard 矩陣具有如下性質(zhì):

(1)將Hadamard 矩陣的任意兩行(列)交換,矩陣的任意一行(列)的所有元素乘?1,得到的矩陣仍然是Hadamard 矩陣.

(2)若Hn是n階Hadamard 矩陣,需要滿足n是4的倍數(shù)(n＞2).

本文所需的Hadamard 矩陣均為標(biāo)準(zhǔn)型,即Hn的第1 行和第1 列全是1.

1.2 部分重復(fù)碼

定義2[13].FR 碼.給定一個(gè)部分重復(fù)碼C=(?,M),其中參數(shù)為(n,k,d),將重復(fù)度設(shè)為ρ(即編碼數(shù)據(jù)塊復(fù)制ρ倍),特定地,M={M1,···,Mn}為n個(gè)子集的集合,Mi(1 ＜=i＜=n)中的每一個(gè)元素都屬于集合?={1,···,θ}.

另外還需滿足以下兩個(gè)條件:

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

2)?中每一個(gè)元素分別存在于M的ρ個(gè)子集中.

如果d和ρ 分別都為固定值則為同構(gòu)FR 碼,如果d不是固定的值則為存儲(chǔ)容量異構(gòu)的FR 碼;如果 ρ不是固定的值則為重復(fù)度異構(gòu)的FR 碼.

FR 碼的本質(zhì)為將經(jīng)過MDS 編碼后的數(shù)據(jù)塊復(fù)制ρ倍,隨后將其分別放置在n個(gè)不同節(jié)點(diǎn)中,其中同一個(gè)的編碼數(shù)據(jù)塊不能出現(xiàn)在一個(gè)節(jié)點(diǎn)中.

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

本節(jié)基于Hadamard 矩陣構(gòu)造存儲(chǔ)容量不同的異構(gòu)部分重復(fù)碼.首先選一個(gè)4s(s=1,2,3,···)階的Hadamard矩陣,再將此Hadamard 矩陣進(jìn)行簡單變換即可得到所需矩陣.將編碼數(shù)據(jù)塊與矩陣進(jìn)行類比聯(lián)系,分布式存儲(chǔ)系統(tǒng)中的節(jié)點(diǎn)對(duì)應(yīng)矩陣的行,而不同的編碼塊對(duì)應(yīng)于矩陣的列.根據(jù)Hadamard 矩陣,引出存儲(chǔ)容量不同的異構(gòu)FR 碼一般性構(gòu)造算法,其具體步驟如下:

步驟1.首先采用(n,k)MDS 編碼(n≥k)對(duì)原始文件進(jìn)行編碼,得到n個(gè)編碼數(shù)據(jù)塊c1,···,ck?1,ck,ck+1,···,cn,其中包括k個(gè)原始數(shù)據(jù)塊和n?k個(gè)校驗(yàn)數(shù)據(jù)塊[6];

步驟2.取一個(gè)n+1階 標(biāo)準(zhǔn)型Hadamard 矩陣Hn+1(n+1為4的倍數(shù)),由式(1)對(duì)Hn+1進(jìn)行簡單變換:

矩陣Jn+1中 元素全為1,Hn+1為標(biāo)準(zhǔn)Hadamard 矩陣,得到的K′n+1(n≥k)是一個(gè)0-1 矩陣,將K′n+1的第一行和第一列同時(shí)刪去得到所需矩陣Kn;

步驟3.將矩陣Kn中第j列出現(xiàn)的第(j+1)mod個(gè)1 改為0 得到新的矩陣Kn1,然后計(jì)算式(1):

其中,j=1,2···,n,i表示第i個(gè)FR 節(jié)點(diǎn),aij表示矩陣第i行第j列的值.其中表示異構(gòu)FR 碼的存儲(chǔ)節(jié)點(diǎn),將矩陣Kn1中第i行中全部的1 所分別對(duì)應(yīng)的列數(shù)提取出來,即可得到一個(gè)節(jié)點(diǎn)Ni存儲(chǔ)的數(shù)據(jù)塊,得到節(jié)點(diǎn)存儲(chǔ)容量不同的異構(gòu)FR 碼.

具體的,選取一個(gè)12 階的Hadamard 矩陣如圖1所示,對(duì)其按步驟2 操作得到11 階矩陣K11如圖2所示,每一列的第個(gè)1 改為0 得到新的矩陣K111如圖3所示.隨后節(jié)點(diǎn)對(duì)應(yīng)矩陣的行,而不同的編碼塊對(duì)應(yīng)于矩陣的列.所以我們得到了存儲(chǔ)容量不同的異構(gòu)的FR 碼,每個(gè)節(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)如圖4所示,其節(jié)點(diǎn)的存儲(chǔ)容量d=3,4,5,編碼塊的重復(fù)度 ρ=4.

圖1 12 階Hadamard 矩陣

圖2 K11 矩陣

圖3 K111 矩陣

單個(gè)節(jié)點(diǎn)發(fā)生故障時(shí),可以根據(jù)存活的其他節(jié)點(diǎn)直接下載所需的數(shù)據(jù),即可恢復(fù)故障節(jié)點(diǎn).例如在圖4中,若第二個(gè)節(jié)點(diǎn)N2發(fā)s生故障,通過下載節(jié)點(diǎn)N7恢復(fù)數(shù)據(jù)塊5和11,下載N9恢復(fù)數(shù)據(jù)塊3和7,即可完成節(jié)點(diǎn)N2的恢復(fù);同時(shí)也可以根據(jù)節(jié)點(diǎn)N3>,N8>,N11分別下載數(shù)據(jù)塊3,5,7,11,也可完成故障節(jié)點(diǎn)N2的恢復(fù).單節(jié)點(diǎn)發(fā)生故障可采用多種方式來恢復(fù),同時(shí)也實(shí)現(xiàn)故障節(jié)點(diǎn)的精確無編碼修復(fù).當(dāng)兩個(gè)節(jié)點(diǎn)發(fā)生故障時(shí),方法同一個(gè)故障節(jié)點(diǎn)修復(fù).

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

3 可擴(kuò)展的異構(gòu)部分重復(fù)碼

本小節(jié)提出一種基于[7,3,4]簡單圖形構(gòu)造可擴(kuò)展異構(gòu)部分重復(fù)碼的算法,此算法可以簡單對(duì)部分重復(fù)碼進(jìn)行擴(kuò)展,如現(xiàn)有結(jié)構(gòu)不滿足已有需求需要進(jìn)行擴(kuò)容,則不需破壞已有的結(jié)構(gòu),只需在圖形尾部直接旋轉(zhuǎn)拼接圖形擴(kuò)展,使得FR 碼可擴(kuò)展,具體構(gòu)造步驟如下所示:

步驟1.首先采用(n,k)M DS 編碼(n≥k)對(duì)原始文件進(jìn)行編碼,得到n個(gè)編碼數(shù)據(jù)塊c1,···,ck?1,ck,ck+1,···,cn,其中包括k個(gè)原始數(shù)據(jù)塊和n?k個(gè)校驗(yàn)數(shù)據(jù)塊[6];

步驟2.取一個(gè)[7,3,4]簡單圖形,如圖5所示.

圖5 [7,3,4]簡單代碼圖形

步驟3.通過 [7,3,4]簡單圖形構(gòu)造FR 碼:將外圍3 個(gè)頂點(diǎn)當(dāng)作存儲(chǔ)節(jié)點(diǎn),將內(nèi)部的4 個(gè)頂點(diǎn)當(dāng)作數(shù)據(jù)塊,數(shù)據(jù)塊按照順時(shí)針存放,臨近存儲(chǔ)節(jié)點(diǎn)的3 個(gè)數(shù)據(jù)塊存放在該存儲(chǔ)節(jié)點(diǎn).

將 [7,3,4]簡單圖形的外圍3 個(gè)頂點(diǎn)當(dāng)作存儲(chǔ)節(jié)點(diǎn),將[7,3,4]簡單圖形內(nèi)部的4 個(gè)頂點(diǎn)當(dāng)作數(shù)據(jù)塊,數(shù)據(jù)塊按照順時(shí)針存放,臨近存儲(chǔ)節(jié)點(diǎn)的3 個(gè)數(shù)據(jù)塊存放在該存儲(chǔ)節(jié)點(diǎn).

步驟4.通過將 [7,3,4]簡單圖形旋轉(zhuǎn)拼接構(gòu)造可擴(kuò)展FR 碼:

1)將擴(kuò)展的[7,3,4]簡單圖形的外圍羅馬數(shù)字代表一個(gè)節(jié)點(diǎn),外圍的第i個(gè)點(diǎn)表示分布式存儲(chǔ)系統(tǒng)中的第i個(gè)存儲(chǔ)節(jié)點(diǎn)Ni,共有n個(gè) 存儲(chǔ)節(jié)點(diǎn)(i=I,II,···,n);將與存儲(chǔ)節(jié)點(diǎn)直接相連的數(shù)據(jù)塊當(dāng)作該存儲(chǔ)節(jié)點(diǎn)存放的數(shù)據(jù)塊,即可得到存儲(chǔ)容量和重復(fù)度異構(gòu)的FR 碼.

2)當(dāng)數(shù)據(jù)塊n=3t+4 時(shí),需要t+1個(gè) [7,3,4]簡單圖形旋轉(zhuǎn)拼接,構(gòu)造出具有t+3個(gè) 存儲(chǔ)節(jié)點(diǎn),n個(gè)數(shù)據(jù)塊的FR 碼.當(dāng)數(shù)據(jù)塊n=4+3t+s(s=1,2)時(shí),需要t+2個(gè)[7,3,4] 簡單圖形旋轉(zhuǎn)拼接,構(gòu)造出具有t+3個(gè)存儲(chǔ)節(jié)點(diǎn),n個(gè)數(shù)據(jù)塊的FR 碼.

若構(gòu)造一個(gè)具有6 個(gè)存儲(chǔ)節(jié)點(diǎn),13 個(gè)數(shù)據(jù)塊的FR碼.可將基本圖形翻轉(zhuǎn)拼接3 次,得到如圖6所示圖形,按上述方法可得到6 個(gè)存儲(chǔ)節(jié)點(diǎn)所存放的數(shù)據(jù)塊,如圖7所示,若當(dāng)前結(jié)構(gòu)無法滿足需求,可對(duì)其進(jìn)行擴(kuò)展,直至滿足需求,而且無需改變現(xiàn)有結(jié)構(gòu),如圖8所示.

圖6 圖形結(jié)構(gòu)

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

圖8 擴(kuò)展圖形結(jié)構(gòu)

可以看出共有6 個(gè)存儲(chǔ)節(jié)點(diǎn).存儲(chǔ)節(jié)點(diǎn)N1和N5的存儲(chǔ)容量是5,存儲(chǔ)節(jié)點(diǎn)N3和N4的存儲(chǔ)容量是7,并且重復(fù)度 ρ為2 或3的一個(gè)異構(gòu)的FR 碼.

當(dāng)單個(gè)節(jié)點(diǎn)發(fā)生故障時(shí),如圖7中,當(dāng)?shù)诙€(gè)節(jié)點(diǎn)N2發(fā)生故障時(shí),通過下載節(jié)點(diǎn)N1恢復(fù)數(shù)據(jù)塊1和4,下載N3恢復(fù)數(shù)據(jù)塊2,來完成節(jié)點(diǎn)N2的恢復(fù);當(dāng)節(jié)點(diǎn)N3發(fā)生故障時(shí),通過下載節(jié)點(diǎn)N1恢復(fù)數(shù)據(jù)塊3,4和7,下載N2恢復(fù)數(shù)據(jù)塊2,下載N4恢復(fù)數(shù)據(jù)塊6和10,下載N5恢復(fù)數(shù)據(jù)塊8,即可完成節(jié)點(diǎn)N3的恢復(fù).具體修復(fù)方式可選擇性較大,同時(shí)實(shí)現(xiàn)故障節(jié)點(diǎn)的精確無編碼修復(fù).

4 性能分析

本小節(jié)對(duì)基于Hadamard 矩陣構(gòu)造存儲(chǔ)容量異構(gòu)的部分重復(fù)碼和基于[7,3,4]簡單圖形構(gòu)造可擴(kuò)展的異構(gòu)部分重復(fù)碼進(jìn)行性能分析,主要考慮修復(fù)帶寬開銷和修復(fù)局部性方面的性能,并與常見的RS 編碼進(jìn)行性能比較.為了便于比較,基于Hadamard 矩陣構(gòu)造存儲(chǔ)容量異構(gòu)的部分重復(fù)碼算法選取(11,9)FR 碼,基于[7,3,4]簡單圖形構(gòu)造可擴(kuò)展異構(gòu)部分重復(fù)碼的算法選取(13,9)F R 碼,取M=1000 Mbit.

4.1 修復(fù)帶寬開銷

修復(fù)帶寬開銷指的是恢復(fù)失效節(jié)點(diǎn)時(shí)下載的數(shù)據(jù)量大小.例如采用(11,9)RS 編碼,由于RS 編碼恢復(fù)故障節(jié)點(diǎn)需要下載全部原文件,所以修復(fù)帶寬開銷為η=M;采用基于Hadamard 矩陣構(gòu)造存儲(chǔ)容量不同的異構(gòu)部分重復(fù)碼構(gòu)造(11,9)FR 碼時(shí),發(fā)生節(jié)點(diǎn)故障時(shí)的修復(fù)帶寬開銷為η=3M/k,5M/k或者7M/k.為便于比較,本文選取中間值作為代表值.在采用基于[7,3,4]簡單圖形構(gòu)造可擴(kuò)展異構(gòu)部分重復(fù)碼的算法構(gòu)造(13,9)FR 碼時(shí),發(fā)生節(jié)點(diǎn)故障的修復(fù)帶寬開銷為η=3M/k,5M/k或者 7M/k,而采用(13,9)RS 編碼時(shí),發(fā)生節(jié)點(diǎn)故障的修復(fù)帶寬開銷為η=M.由于圖形特殊構(gòu)造,隨著節(jié)點(diǎn)增多修復(fù)帶寬開銷基本都是7M/k,所以選取其為代表值.以上2 項(xiàng)數(shù)據(jù)與RS 碼仿真對(duì)比如圖9所示.

經(jīng)過對(duì)比不難發(fā)現(xiàn)本文提出的兩種異構(gòu)部分重復(fù)碼構(gòu)造的算法,節(jié)點(diǎn)發(fā)生故障時(shí)修復(fù)帶寬開銷比RS 編碼明顯降低.當(dāng)節(jié)點(diǎn)數(shù)少于16 時(shí),基于Hadamard 矩陣構(gòu)造的異構(gòu)FR 碼修復(fù)帶寬開銷小于基于[7,3,4]簡單圖形構(gòu)造異構(gòu)FR 碼.但是當(dāng)節(jié)點(diǎn)數(shù)逐漸增大,基于[7,3,4]簡單圖形構(gòu)造異構(gòu)FR 碼的修復(fù)帶寬開銷小于基于Hadamard 矩陣構(gòu)造的異構(gòu)FR 碼.

4.2 修復(fù)局部性

發(fā)生節(jié)點(diǎn)故障時(shí)需要連接的存活節(jié)點(diǎn)數(shù)目稱為修復(fù)局部性.當(dāng)發(fā)生單節(jié)點(diǎn)故障時(shí),(11,9)RS 編碼需要連接9 個(gè)節(jié)點(diǎn)恢復(fù)原文件用以修復(fù)故障節(jié)點(diǎn),修復(fù)局部性為9;而基于Hadamard 矩陣構(gòu)造存儲(chǔ)容量異構(gòu)的FR 碼構(gòu)造的(11,9)FR 碼,單節(jié)點(diǎn)故障時(shí)需要連接2 個(gè)或者3 個(gè)節(jié)點(diǎn)來修復(fù),故修復(fù)局部性為2 或者3.

圖9 修復(fù)帶寬開銷對(duì)比

采用基于[7,3,4]簡單圖形構(gòu)造可擴(kuò)展異構(gòu)部分重復(fù)碼的算法構(gòu)造(13,9)FR 碼時(shí),發(fā)生節(jié)點(diǎn)故障時(shí)需要連接2,3 或者4 個(gè)節(jié)點(diǎn)來恢復(fù)故障節(jié)點(diǎn),所以修復(fù)局部性為2,3 或4;而(13,9)RS 碼發(fā)生單節(jié)點(diǎn)故障時(shí),RS碼修復(fù)局部性為9.

分析發(fā)現(xiàn)修復(fù)單個(gè)故障節(jié)點(diǎn)時(shí),基于Hadamard 矩陣構(gòu)造存儲(chǔ)容量異構(gòu)的FR 碼和基于[7,3,4]簡單圖形構(gòu)造可擴(kuò)展異構(gòu)FR 碼的修復(fù)局部性,優(yōu)于RS 編碼的修復(fù)局部性.但是[7,3,4]簡單圖形構(gòu)造的異構(gòu)FR 碼無法修復(fù)多節(jié)點(diǎn)故障,是下一步研究的方向.

5 結(jié)論

本文提出基于Hadamard 矩陣和[7,3,4]圖形分別構(gòu)造異構(gòu)的部分重復(fù)碼的一般算法.與現(xiàn)有的FR 碼相比,采用Hadamard 矩陣和[7,3,4]圖形構(gòu)造FR 碼更加簡潔明了,其中基于Hadamard 矩陣可實(shí)現(xiàn)由同構(gòu)經(jīng)過簡單變換為異構(gòu)編碼方式;基于[7,3,4]圖形構(gòu)造FR 碼可實(shí)現(xiàn)擴(kuò)展延升,若當(dāng)前結(jié)構(gòu)無法滿足需求,可對(duì)其進(jìn)行擴(kuò)展,直至滿足需求,且無需改變現(xiàn)有結(jié)構(gòu).經(jīng)過與RS 碼理論分析對(duì)比發(fā)現(xiàn),設(shè)計(jì)的兩種異構(gòu)FR 碼的修復(fù)局部性、修復(fù)帶寬開銷進(jìn)一步降低,性能進(jìn)一步提高.