異構部分重復碼的構造①

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

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

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

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

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

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

1 基礎知識

1.1 Hadamard 矩陣

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

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

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

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

本文所需的Hadamard 矩陣均為標準型,即Hn的第1 行和第1 列全是1.

1.2 部分重復碼

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

另外還需滿足以下兩個條件:

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

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

如果d和ρ 分別都為固定值則為同構FR 碼,如果d不是固定的值則為存儲容量異構的FR 碼;如果 ρ不是固定的值則為重復度異構的FR 碼.

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

2 基于Hadamard 矩陣構造異構部分重復碼

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

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

步驟2.取一個n+1階 標準型Hadamard 矩陣Hn+1(n+1為4的倍數(shù)),由式(1)對Hn+1進行簡單變換:

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

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

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

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

圖1 12 階Hadamard 矩陣

圖2 K11 矩陣

圖3 K111 矩陣

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

圖4 存儲容量異構的FR 碼節(jié)點存儲結構圖

3 可擴展的異構部分重復碼

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

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

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

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

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

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

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

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

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

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

圖6 圖形結構

圖7 FR 碼節(jié)點存儲結構圖

圖8 擴展圖形結構

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

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

4 性能分析

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

4.1 修復帶寬開銷

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

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

4.2 修復局部性

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

圖9 修復帶寬開銷對比

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

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

5 結論

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