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

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

目前,將海量數(shù)據(jù)存儲在分布式存儲系統(tǒng)中的不同存儲節(jié)點上的數(shù)據(jù)存儲方式已在實際系統(tǒng)中得到了廣泛應用,如Google 文件系統(tǒng)[1]、Hadoop 文件系統(tǒng)等.為確保分布式存儲系統(tǒng)中數(shù)據(jù)的可用性和可靠性,通常采用諸如復制策略[2]或糾刪碼策略[3,4]的數(shù)據(jù)冗余策略.以復制策略中的三副本復制為例,三副本復制需要存儲大量副本數(shù)據(jù)以確保系統(tǒng)較高的可靠性,存儲代價過高;糾刪碼策略的提出使得修復造成的存儲開銷顯著降低,但其過大的修復帶寬開銷也成為了限制它的瓶頸.

2007年,Dimakis 等人指出存儲開銷和修復帶寬開銷之間存在某種平衡,平衡曲線上的點可通過再生碼來實現(xiàn)[5].再生碼基于網(wǎng)絡編碼的概念,其故障節(jié)點可通過連接一定數(shù)目的存活節(jié)點完成修復,相比于糾刪碼降低了修復帶寬開銷.目前再生碼的研究主要集中在最小存儲再生碼和最小帶寬再生碼[6].

El Rouayheb和Ramchandran為進一步降低修復過程中的運算復雜和帶寬開銷,提出了一種基于最小帶寬再生點的精確修復編碼-部分重復(Fractional Repetition,FR)碼[7].部分重復碼結(jié)合再生碼和復制策略的優(yōu)點,有效減少了修復帶寬開銷和磁盤I/O 開銷[8],并實現(xiàn)精確的無編碼修復.

目前,FR 碼主要采用分組設計[9]、可分解設計[10,11]等方法進行構(gòu)造.朱兵等人基于分組設計提出一種重復度異構(gòu)的FR 碼的構(gòu)造[12],使得常用數(shù)據(jù)的備份更加充分,且參數(shù)選取范圍較大,但同時也造成了較大的存儲開銷;Natalia Silberstein和Tuvi Etzion 等人基于組合設計和正則圖,提出了一種達到最大碼率的FR 碼的構(gòu)造方法[13],但其重復度受FR 碼結(jié)構(gòu)的約束,不能適用于任意參數(shù);Harout Aydinian和Holger Boche 等人則基于部分有序集構(gòu)造了一種普遍好的FR 碼[14],這種構(gòu)造方法雖然簡便,但其重復度卻也十分受限.為此,本文基于Harary 圖生成樹構(gòu)造出了一種新型的部分重復(Fractional Repetition based on Spanning trees of Harary graph,FRSH)碼,可以在很大范圍內(nèi)選擇構(gòu)造參數(shù)和數(shù)據(jù)塊的重復度,還能修復多個故障節(jié)點.通過調(diào)整Harary 圖的構(gòu)造參數(shù),可以構(gòu)造出不同重復度的FR 碼.相比現(xiàn)有的FR 碼,采用Harary 圖生成樹設計FR 碼更加簡潔直觀.相較于RS 碼和SRC[15],FRSH 碼在修復帶寬開銷、修復復雜度以及修復局部性等方面得到了更低的開銷,且改善了修復效率,并將故障節(jié)點修復時間縮短.

1 預備知識

1.1 Harary 圖的基礎知識

Harary 圖是一種正則圖,定義為Hk,m,其中k為每個節(jié)點所鄰接的節(jié)點個數(shù),即頂點的度;m為頂點個數(shù).根據(jù)k和m的取值,可分為3 種情況構(gòu)造Harary 圖.

(1)k是偶數(shù)

設k=2r,則H2r,m構(gòu)造如下:先給出它的頂點0,1,2,…,i,…,j,…,m?1,然后連接所有滿足|i?j|≤r的頂點,即可完成H2r,m的構(gòu)造.

(2)k是奇數(shù),m是偶數(shù)

設k=2r+1,則H2r+1,m構(gòu) 造如下:首先構(gòu)造出H2r,m,為滿足k=2r+1,還需添加一些邊:這些邊連接了每個頂點i與頂點連接完即可得到H2r+1,m.

(3)k是奇數(shù),m是奇數(shù)

設k=2r+1,此時的H2r+1,m構(gòu)造如下:首先構(gòu)造出H2r,m,為滿足k=2r+1,需要添加一些邊:這些邊連接了頂點0與頂點和再將每個頂點i連到頂點如此連接即可完成構(gòu)造.

圖1所示是構(gòu)造的k=4,m=8的Harary 圖H4,8.

1.2 生成樹的基礎知識

無圈圖是指不包含圈的圖,連通的無圈圖定義為樹.無圈圖的生成樹是指頂點與無圈圖相同、邊集是無圈圖的邊集子集,且含邊數(shù)最少的連通子圖.圖2中T1是完全圖K8的生成樹,它包含K8中的所有9個頂點,邊集是完全圖K8 邊集的子集,且包含了最小數(shù)目的邊數(shù).

圖1 Harary 圖H4,8

圖2 完全圖K8和它的生成樹T1

由構(gòu)造的Harary 圖G=Hk,m,以頂點1為起始頂點得出生成樹.具體構(gòu)造步驟如下[16]:

步驟1.畫出邊(1,v+1)和(1,m-v+1),v=1,2,…,

步驟2.令p=+1,j=,畫出邊(m?p+1,m?p?j+1),(m?p?j+1,m?p?2j+1),…,直到形成從頂點m?p+1 到頂點1的路徑時停止.

步驟3.令q=p+1,重復步驟2 畫出邊(m?q+1,m?q?j+1),(m?q?j+1,m?q?2j+1),…,當存在從頂點m?p+1 到頂點1的路徑時停止,否則轉(zhuǎn)至步驟1.

圖3為基于H4,8,且以頂點1為起始頂點構(gòu)造的生成樹.

1.3 離心率的基礎知識

對于連通圖G的一個頂點v,v的離心率定義為v 到G中除v 外所有頂點的距離的最大值.例如圖4中頂點1的離心率值為3,由于距離頂點1 最長的頂點是頂點6,而從頂點1 到頂點6的路徑中共經(jīng)過3個頂點,即距離為3,故頂點1的離心率,其它頂點同理.G的半徑定義為G中所有頂點離心率的最小值,直徑則定義為G的最大離心率,分別記為rad(G)和diam(G).在圖4中頂點最小離心率為2,最大離心率為4,所以有rad(G)=2,diam(G)=4.

圖3 基于H4,8的生成樹

圖4 離心率參考圖

2 基于Harary 圖生成樹的部分重復碼構(gòu)造

2.1 構(gòu)造方法

ρ的FRSH 碼的構(gòu)造算法,具體步驟如算法1.

基于Harary 圖生成樹與離心率,給出重復度為

算法1.基于Harary 圖生成樹的部分重復碼構(gòu)造1)給定一個Harary 圖的設計參數(shù)k和m,其中k為每個節(jié)點所連接的節(jié)點個數(shù),即節(jié)點的度,m為頂點個數(shù),m>0.本文暫且只考慮k為偶數(shù)的情況.2)根據(jù)給出的設計參數(shù)k和m 構(gòu)造Harary 圖.3)選定Harary 圖上任一頂點作為頂點1,并從頂點1 開始給Harary圖的頂點順時針編號,每個頂點存儲與其編號相同的數(shù)據(jù)塊.4)由構(gòu)造的Harary 圖以頂點1為起始頂點構(gòu)造生成樹.n(n≥1)5)對得到的生成樹的頂點按離心率分組,將第一個生成樹G的頂點按離心率分為組,分組后每組頂點的離心率相同,并將各組頂點按編號從小到大的順序分別寫入n個節(jié)點中,得到第一組節(jié)點.ρ(ρ≥1)ρ?1 n?(ρ?1)6)按照所需構(gòu)造部分重復碼的重復度 更換起始頂點,重復步驟4)和步驟5)再得到個生成樹,并將它們的頂點按離心率分組后分別寫入個新的節(jié)點中.

M=(ms,t)1≤s≤nρ,1≤t≤m 7)由生成樹頂點按離心率的分組得到關(guān)聯(lián)矩陣 ().關(guān)聯(lián)矩陣構(gòu)造公式如下(vt 代表生成樹中的任一頂點,es 代表任一離心率取值):ms,t=■■■■■■■■■1,若vt與es相關(guān)聯(lián)0,其它情況d ρ ρ再將生成樹的關(guān)聯(lián)矩陣等價為FR 碼的關(guān)聯(lián)矩陣,關(guān)聯(lián)矩陣的行向量對應FR 碼的存儲節(jié)點,列向量對應FR 碼的編碼塊.行向量的重表示表示節(jié)點存儲容量,列向量的重表示編碼塊重復度.由此即可得到重復度為的FR 碼.

綜上,重復度為ρ的FRSH 碼的構(gòu)造過程中,其包含的不同數(shù)據(jù)塊個數(shù)即為Harary 圖的頂點數(shù)m;重復度 ρ由生成樹個數(shù)決定;包含的節(jié)點個數(shù)為nρ.

具體地,我們以構(gòu)造 ρ=3的FR 碼的過程為例說明構(gòu)造方法.令k=4,m=11,構(gòu)造Harary 圖H4,11,并給其頂點編號,如圖5(a)所示.再由構(gòu)造的Harary 圖以頂點1為起始頂點得出第一個生成樹,如圖5(b)所示.

圖5 H 4,11和它的生成樹

將圖5(b)中給出的生成樹的頂點按離心率分組,相同離心率頂點對應的數(shù)據(jù)塊寫入同一分組.為滿足重復度 ρ=3,需重復步驟4)和步驟5),分別以頂點3和頂點5為起始頂點再得到第2個生成樹和第3個生成樹(此處圖略).進一步將第2個生成樹和第3個生成樹的頂點存儲數(shù)據(jù)按離心率分組,構(gòu)造關(guān)聯(lián)矩陣M.以圖5(b)中的生成樹為例,本例中所有生成樹頂點的離心率es共有n=3個取值:e1=3、e2=4、e3=5.圖5(b)中頂點2、3、4、5的離心率都為e1=3,即v2、v3、v4、v5與e1相關(guān)聯(lián),故有m1,2=m1,3=m1,4=m1,5=1,以此類推便得到關(guān)聯(lián)矩陣M.

根據(jù)關(guān)聯(lián)矩陣M,構(gòu)造重復度 ρ=3的FR 碼,構(gòu)成的FR 碼如圖6.

圖6 FR 碼

2.2 故障節(jié)點修復

本論文構(gòu)造的任意FRSH 碼都包含 ρ個平行類,且最多可容忍 ρ?1個節(jié)點故障,具體修復方案如下:

(1)當單個節(jié)點失效時,新生節(jié)點從存活平行類中下載失效節(jié)點對應數(shù)據(jù)塊,即可完成修復.如節(jié)點N1故障時,損壞的數(shù)據(jù)塊2、3、4、5 可從剩余兩個平行類N4、N5、N6或N7、N8、N9中下載.這里選擇連接存活節(jié)點N4、N9并分別下載4、5、2、3,即可修復故障節(jié)點N1.

(2)當多個節(jié)點同時出現(xiàn)故障,由于仍至少存在一個平行類包含全部數(shù)據(jù)塊,而本方法構(gòu)造的FR 碼的任一平行類中包含的節(jié)點個數(shù)等于離心率分組數(shù)n,故至多連接n個節(jié)點即可完成修復.具體地,當多個故障節(jié)點所包含的數(shù)據(jù)塊個數(shù)d<αmin+αmax(這里αmin和αmax分別表示FRSH 碼中節(jié)點存儲的最小數(shù)據(jù)塊個數(shù)和最大數(shù)據(jù)塊個數(shù))時,僅需連接n?1個故障節(jié)點即可完成修復.例如當N2和N5同時失效時,故障節(jié)點N2和N5共包含d=6個數(shù)據(jù)塊,滿足d<αmin+αmax.此時,修復故障節(jié)點N2和N5需要連接n?1=2個存活節(jié)點完成修復.這里選擇存活節(jié)點N7和N9,并分別從存活節(jié)點N7和N9下載數(shù)據(jù)塊6、7、8、9和1、3,實現(xiàn)故障節(jié)點N2和N5的修復.

(3)當多個節(jié)點同時出現(xiàn)故障,且多個故障節(jié)點所包含的數(shù)據(jù)塊個數(shù)d≥αmin+αmax時,需連接n?1或n個不同節(jié)點即可完成故障節(jié)點修復.同樣先考慮圖6中的節(jié)點N4和N5發(fā)生故障,此時故障節(jié)點N4和N5包含d=7個數(shù)據(jù)塊,滿足d≥αmin+αmax.為修復故障節(jié)點N4和N5需要從n?1=2個存活節(jié)點中下載對應數(shù)據(jù)塊,這里選擇存活節(jié)點N1和N7,并分別從N1和N7下載數(shù)據(jù)塊3、4、5和6、7、8、9,即可修復故障節(jié)點N4和N5.另當N2和N7發(fā)生故障時,此時故障節(jié)點N2和N7包含d=7個數(shù)據(jù)塊,同樣滿足d≥αmin+αmax.而此時修復N2和N7需連接n=3個存活節(jié)點N4、N5和N6,并分別下載6、7、8、9和1 便可修復N2和N7.

綜上,對于重復度為ρ的FRSH 碼,修復單節(jié)點故障時在剩余平行類中連接對應存活節(jié)點(連接的節(jié)點數(shù)至多為n?1個)下載所需數(shù)據(jù)塊即可;修復多節(jié)點故障時,當多個故障節(jié)點所包含的數(shù)據(jù)塊個數(shù)d<αmin+αmax時,僅需連接n?1個故障節(jié)點即可完成修復;當多個故障節(jié)點所包含的數(shù)據(jù)塊個數(shù)d≥αmin+αmax時,需連接n?1或n個不同節(jié)點即可完成故障節(jié)點修復.

3 性能分析

基于Harary 圖生成樹構(gòu)造的FR 碼的性能分析主要集中在修復局部性、修復帶寬開銷和運算復雜度這幾方面,并將其與傳統(tǒng)的RS 碼和簡單再生碼(Simple Regenerating Codes,SRC)進行性能比較.表1給出了SRC、RS 碼與FRSH 碼在一般情況下的的節(jié)點存儲開銷、修復帶寬開銷以及修復局部性的計算公式,之后我們會在給定具體文件大小和編碼數(shù)據(jù)等條件下用柱狀圖的形式把上文構(gòu)造的ρ=3的FR 碼與SRC、RS 碼的各種性能逐一進行比較.

表1 幾種編碼方案的性能分析

3.1 修復局部性

修復局部性是衡量構(gòu)造出的部分重復碼性能的重要指標之一,其定義為節(jié)點故障修復過程中連接的存活節(jié)點數(shù)目,即磁盤I/O 開銷.此處為方便比較,我們假設原文件大小M=1000 Mb,存儲節(jié)點數(shù)則為n=11,SRC 子文件數(shù)f=3,RS 碼和SRC的原文件重構(gòu)度為k=8,FRSH 碼外部采用(11,8)MDS 編碼.本小節(jié)僅考慮兩種節(jié)點故障情況:單節(jié)點故障與兩節(jié)點故障.

當單節(jié)點出現(xiàn)故障時,SRC在修復失效節(jié)點時需要連接2f個節(jié)點,這里取f=3,則SRC的修復局部性為6;若采用(11,8)RS 碼,需要連接k=8個節(jié)點以恢復出完整的原文件,再由原文件修復故障節(jié)點,故其修復局部性為8;而本文構(gòu)造的FRSH 碼需要連接2個節(jié)點來修復故障節(jié)點,修復局部性為2.

在兩節(jié)點故障的情況下,SRC與(11,8)RS 碼都需要連接k=8個存活節(jié)點以修復故障節(jié)點,故它們的修復局部性都為8;而基于Harary 圖生成樹構(gòu)造的FRSH碼的修復局部性為2 或3,為便于對比,此處取恒為3 作為比較.由圖7可見,在單節(jié)點故障與兩節(jié)點故障情況下,本文構(gòu)造的FRSH 碼的修復局部性都優(yōu)于SRC和RS 碼.

圖7 修復局部性

另與基于圖因子構(gòu)造的部分重復碼相比,在單節(jié)點故障時兩種部分重復碼都需要連接兩個節(jié)點進行修復;在兩節(jié)點故障時,基于圖因子的部分重復碼需要連接4個節(jié)點進行修復,而FRSH 碼至多需連接3個節(jié)點進行修復,可見在兩節(jié)點故障時FRSH 碼具有顯著優(yōu)勢.

3.2 修復帶寬開銷

在單節(jié)點故障的情況下,SRC 需下載f個數(shù)據(jù)塊以完成修復,而每個數(shù)據(jù)塊的大小為M/fk,因此SRC的帶寬開銷為(f+1)M/k;由于RS 碼在單節(jié)點故障的情況下完成修復需下載整個原文件,故RS 碼的帶寬開銷為原文件大小M;而本文構(gòu)造的FRSH 碼在單節(jié)點故障的情況下需要通過連接2個存活節(jié)點完成修復,因此FRSH 碼的帶寬開銷為2M/k.

當兩節(jié)點同時故障時,RS 碼與SRC的帶寬開銷均為M.FRSH 碼的帶寬開銷為3M/k.

假設原文件大小為M=1000 Mb,存儲節(jié)點數(shù)n=11,SRC 子文件數(shù)f=3,RS 碼和SRC的原文件重構(gòu)度為k=8,FRSH 碼外部采用(11,8)MDS 編碼.當單節(jié)點故障時,RS 碼的帶寬開銷為1000 Mb,SRC的帶寬開銷為500 Mb,FRSH 碼的帶寬開銷為250 Mb;當兩個節(jié)點故障時,(11,8)RS 碼修復帶寬開銷為1000 Mb,SRC的帶寬開銷同樣為1000 Mb,為方便對比FRSH 碼的帶寬開銷取較大值3M/k=375 Mb.如圖8所示,無論單節(jié)點還是兩節(jié)點故障,FRSH 碼的修復帶寬開銷都相對較低.

圖8 修復帶寬開銷對比

3.3 構(gòu)造算法運算復雜度

除去修復局部性與修復帶寬開銷這兩種直觀性能,構(gòu)造算法復雜度體現(xiàn)了算法在執(zhí)行時的難易程度,是衡量一個算法好壞的重要指標.所謂運算復雜度,即將算法寫成程序在實際的計算機系統(tǒng)中運行時涉及的計算量.本文構(gòu)造的FRSH 碼構(gòu)造時不需要任何計算量,只需調(diào)節(jié)Harary 圖與其生成樹的參數(shù)即可.相較于可達到同等性能的FRC,減少了大量的運算時間.

將基于Harary 圖生成樹的FRSH與運用圖因子分解構(gòu)造的FRC[17]在構(gòu)造算法運算復雜度進行對比分析,在文獻[17]中,構(gòu)造算法時運用到了加法,乘法運算和基于一次方程上的運算共3 種運算方式,相較于本文僅需調(diào)整Harary 圖參數(shù),可知本文的構(gòu)造算法運算復雜度更優(yōu).

4 結(jié)論與展望

針對部分重復碼的有效修復問題,本文基于Harary圖生成樹構(gòu)造出了一種新型的部分重復碼.這種FRSH碼在構(gòu)造方面的優(yōu)勢在于參數(shù)選擇范圍較廣且運算復雜度極低.在性能方面,實驗結(jié)果表明,相較于現(xiàn)有的RS 碼和SRC,FRSH 碼在修復帶寬開銷、修復局部性等方面得到了更低的開銷,且改善了修復效率,并將故障節(jié)點的修復時間縮短;又與可達到類似性能的圖因子分解的部分重復碼在運算復雜度方面進行比較,得出本文的構(gòu)造算法運算復雜度更優(yōu).