王甜甜,王汗青,孟 潔,余春雷,王曉峰

(1.海軍航空大學(xué) 航空基礎(chǔ)學(xué)院,山東 煙臺(tái) 264000;2.四川文理學(xué)院 智能制造學(xué)院,四川 達(dá)州 635000)

0 引 言

現(xiàn)如今,海量數(shù)據(jù)仍迅速膨脹,針對(duì)大數(shù)據(jù)的可靠安全存儲(chǔ)問題被廣泛重視。大規(guī)模分布式存儲(chǔ)系統(tǒng)成為當(dāng)前存儲(chǔ)海量數(shù)據(jù)的有效途徑,因其具備可用性高、成本低、吞吐量高和可擴(kuò)展等優(yōu)勢(shì)[1]。由于系統(tǒng)中經(jīng)常發(fā)生存儲(chǔ)節(jié)點(diǎn)故障的情形,為了使分布式存儲(chǔ)系統(tǒng)提供可靠的存儲(chǔ)服務(wù),需要通過連接其他存活節(jié)點(diǎn)對(duì)故障節(jié)點(diǎn)進(jìn)行修復(fù)。通常需要采取一定的冗余策略,以保證數(shù)據(jù)存儲(chǔ)的有效性和可靠性。主流的冗余策略是復(fù)制(Replication)[2]和糾刪碼(Erasure Codes)[3]。復(fù)制策略的存儲(chǔ)成本太大,在修復(fù)故障節(jié)點(diǎn)時(shí)糾刪碼的帶寬開銷較高。

針對(duì)復(fù)制策略和糾刪碼策略在數(shù)據(jù)存儲(chǔ)和故障修復(fù)中存在的局限性,通過將“網(wǎng)絡(luò)編碼”的思路引入分布式存儲(chǔ)系統(tǒng)中,Dimakis等人提出了再生碼(Regenerating Codes,RC)[4],降低了修復(fù)帶寬開銷和節(jié)點(diǎn)存儲(chǔ)開銷[5]。根據(jù)存儲(chǔ)—帶寬開銷權(quán)衡曲線上的最佳極值點(diǎn),Rashmi等人提出了最小帶寬再生(Minimum Bandwidth Regeneration,MBR)碼和最小存儲(chǔ)再生(Minimum Storage Regeneration,MSR)碼[6]。但再生碼需要連接較多存活節(jié)點(diǎn)來修復(fù)故障節(jié)點(diǎn)。為了降低修復(fù)故障節(jié)點(diǎn)時(shí)的修復(fù)局部性,Papailiopoulos等人提出了局部性修復(fù)編碼(Locally Repairable Codes,LRC)[7],在局部修復(fù)組內(nèi)對(duì)故障節(jié)點(diǎn)進(jìn)行修復(fù)。結(jié)合RS碼與簡(jiǎn)單的異或運(yùn)算,Papailiopoulos提出了簡(jiǎn)單再生碼(Simple Regenerating Codes,SRC)[8]。再生碼和LRC需要通過大量運(yùn)算來修復(fù)故障節(jié)點(diǎn),其修復(fù)過程中的計(jì)算復(fù)雜度較高,導(dǎo)致修復(fù)時(shí)間較長(zhǎng)[9]。

為了保證修復(fù)故障節(jié)點(diǎn)時(shí)具有較低修復(fù)帶寬開銷,同時(shí)進(jìn)一步提高修復(fù)效率,Ramchandran等人提出了一種實(shí)現(xiàn)對(duì)故障節(jié)點(diǎn)進(jìn)行精確無編碼修復(fù)的MBR碼——部分重復(fù)(Fractional Repetition,FR)碼[10]。實(shí)際的分布式存儲(chǔ)系統(tǒng)是一種動(dòng)態(tài)的隨機(jī)變化的環(huán)境,也就是說,存儲(chǔ)節(jié)點(diǎn)故障和部分?jǐn)?shù)據(jù)丟失等情況隨時(shí)可能發(fā)生[11]。針對(duì)這一問題,朱兵提出了自適應(yīng)FR碼[11],以使FR碼適用于動(dòng)態(tài)分布式存儲(chǔ)系統(tǒng)。采用自適應(yīng)FR碼的分布式存儲(chǔ)系統(tǒng)中,在節(jié)點(diǎn)中部分?jǐn)?shù)據(jù)丟失并無法修復(fù)的情況下,通過簡(jiǎn)單調(diào)整系統(tǒng)結(jié)構(gòu)以滿足FR碼特性,無需重新配置存儲(chǔ)系統(tǒng)[12]。隨后,Oktay Olmez提出了可分解FR碼[13-15],并提出了基于組合設(shè)計(jì)的構(gòu)造方法?？煞纸釬R碼中每個(gè)平行類均存儲(chǔ)原文件大小的數(shù)據(jù)量,在部分節(jié)點(diǎn)故障的情況下,剩余平行類中存活節(jié)點(diǎn)仍滿足FR碼特性。Su Yisheng結(jié)合自適應(yīng)FR碼與可分解FR碼的特性,提出了自適應(yīng)可分解FR碼,并提出了基于仿射置換矩陣(Affine Permutation Matrices,APMs)與循環(huán)置換矩陣(Circulant Permutation Matrices,CPMs)的構(gòu)造方法[16],有效適應(yīng)了節(jié)點(diǎn)存儲(chǔ)容量和數(shù)據(jù)塊重復(fù)度在動(dòng)態(tài)存儲(chǔ)系統(tǒng)中的隨機(jī)動(dòng)態(tài)變化。為了使系統(tǒng)中存儲(chǔ)節(jié)點(diǎn)數(shù)和節(jié)點(diǎn)存儲(chǔ)容量易于擴(kuò)展,朱兵提出了可擴(kuò)展FR碼的顯式構(gòu)造方法[17]。Krishna提出了具有非對(duì)稱參數(shù)的廣義部分重復(fù)(Generalized Fractional Repetition,GFR)碼,并建立了GFR碼與超圖的對(duì)應(yīng)關(guān)系[18]。

基于上述研究基礎(chǔ),該文在自適應(yīng)可分解FR碼原始構(gòu)造方案的基礎(chǔ)上,提出了利用超圖實(shí)現(xiàn)自適應(yīng)可分解FR碼的擴(kuò)展構(gòu)造方法,實(shí)現(xiàn)FR碼在動(dòng)態(tài)分布式存儲(chǔ)系統(tǒng)中的靈活擴(kuò)展。當(dāng)文件規(guī)模或分布式存儲(chǔ)系統(tǒng)規(guī)模發(fā)生變化時(shí),根據(jù)超圖中邊和頂點(diǎn)對(duì)應(yīng)于FR碼中節(jié)點(diǎn)和數(shù)據(jù)塊的關(guān)系,通過增加或刪除超圖中對(duì)應(yīng)的邊和頂點(diǎn),實(shí)現(xiàn)動(dòng)態(tài)分布式存儲(chǔ)系統(tǒng)中自適應(yīng)可分解FR碼的擴(kuò)展構(gòu)造。通過這種基于超圖的擴(kuò)展構(gòu)造方法,能夠擴(kuò)展出給定參數(shù)范圍內(nèi)的所有自適應(yīng)可分解FR碼,該文列舉出了存儲(chǔ)節(jié)點(diǎn)數(shù)20以內(nèi)自適應(yīng)可分解FR碼的所有參數(shù)。自適應(yīng)可分解FR碼與SRC和RS碼相比,在修復(fù)局部性和修復(fù)帶寬開銷方面具有一定優(yōu)勢(shì)。

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

1.1 自適應(yīng)可分解FR碼

在(n,k,d)分布式存儲(chǔ)系統(tǒng)中,假定節(jié)點(diǎn)存儲(chǔ)容量為α,從n個(gè)存儲(chǔ)節(jié)點(diǎn)中至少連接任意k個(gè)存活節(jié)點(diǎn)即可重構(gòu)原文件,單節(jié)點(diǎn)故障需要至少連接d個(gè)存活節(jié)點(diǎn)實(shí)現(xiàn)修復(fù),則滿足條件k≤d≤n-1,且d=α。

FR碼[10]:在(n,k,d)分布式存儲(chǔ)系統(tǒng)中,設(shè)定FR碼C=(Ω,N)由n個(gè)子集組成的集合N={N1,…,Nn}表示,其中,每個(gè)子集均由符號(hào)集Ω={1,…,θ}中元素描述,且符號(hào)集Ω中元素的重復(fù)度均為ρ,該FR碼亦可描述為(n,d,θ,ρ)FR碼[19]。該(n,d,θ,ρ)FR碼滿足以下條件:

(1)子集Ni(i=1,…,n)的大小均為d;

(2)符號(hào)集Ω中每個(gè)元素均屬于集合N中的ρ個(gè)子集;

(3)子集Ni和Nj(i≠j)最多包含符號(hào)集Ω中的一個(gè)元素;

(4)θρ=nd。

自適應(yīng)FR碼[11]:在FR碼C=(Ω,N)中,如果?S?Ω,且由非空子集N0S,N1S,…,Nn-1S組成的集合也是一個(gè)FR碼C',則C為自適應(yīng)FR碼。

當(dāng)存儲(chǔ)系統(tǒng)中部分?jǐn)?shù)據(jù)永久性故障而無法恢復(fù)時(shí),原來的自適應(yīng)FR碼C通過簡(jiǎn)單調(diào)整得到新的FR碼C',以適應(yīng)新的分布式存儲(chǔ)系統(tǒng)。

通過改變可分解FR碼中的平行類數(shù),即可改變數(shù)據(jù)塊的重復(fù)度。由于每個(gè)平行類中的節(jié)點(diǎn)均存儲(chǔ)全部數(shù)據(jù)塊,因此重構(gòu)原始文件可以通過下載任一平行類中的數(shù)據(jù)塊實(shí)現(xiàn),進(jìn)而修復(fù)故障節(jié)點(diǎn)。當(dāng)FR碼中包含多個(gè)平行類時(shí),即使刪除該故障節(jié)點(diǎn)所在的平行類,其余節(jié)點(diǎn)仍滿足FR碼特性。

自適應(yīng)可分解FR碼同時(shí)滿足自適應(yīng)FR碼和可分解FR碼的特性,能夠有效適應(yīng)于動(dòng)態(tài)分布式存儲(chǔ)系統(tǒng)[15]。

1.2 超 圖

超圖[20]:對(duì)于離散集合H=(V,E),其中V=(v1,…,vn)是離散元素的有限集合,E=(E1,…,Em)是V中各非空子集的集合,則超圖就是離散集合H=(V,E)。在超圖中,頂點(diǎn)的集合為V,邊的集合為E,任意非零數(shù)量的頂點(diǎn)連接成超圖的邊。

簡(jiǎn)單超圖:超圖的邊集E=(E1,…,Em)中,如果滿足Ei?Ej,則i=j,即任意兩條邊Ei、Ej沒有包含關(guān)系,則該超圖為簡(jiǎn)單超圖。

線性超圖:超圖的邊集E=(E1,…,Em)中,當(dāng)i≠j時(shí),|Ei∩Ej|≤1,即任意兩條邊Ei、Ej連接不超過一個(gè)共同頂點(diǎn),則該超圖為線性超圖。

r-一致超圖:超圖的秩記為r(H)=maxj|Ej|,超圖的下秩記為s(H)=minj|Ej|,當(dāng)滿足r(H)=s(H)時(shí),超圖H稱為一致超圖。每條邊均連接r個(gè)頂點(diǎn)的超圖,簡(jiǎn)記為r-一致超圖。

t-正則超圖:超圖H中,連接頂點(diǎn)vi(i=1,…,n)的邊數(shù)為頂點(diǎn)vi的度,凡所有頂點(diǎn)的度均相同的超圖稱為正則超圖[21]。每個(gè)頂點(diǎn)均由t條邊連接的超圖,簡(jiǎn)記為t-正則超圖。

(r,t)-超圖:對(duì)于線性超圖,如果所有的邊均包含r個(gè)頂點(diǎn),且所有頂點(diǎn)均存在于t條邊中,則稱為線性r-一致t-正則超圖,簡(jiǎn)記為(r,t)-超圖。

子超圖:對(duì)于超圖H=(V,E),頂點(diǎn)子集A?V,其子超圖為HA=(A,{e∩A|e∈E∧e∩A≠?})。在原超圖的基礎(chǔ)上去掉某些頂點(diǎn)后的超圖,就是子超圖。

部分超圖:超圖H=(V,E)中,邊集E={ei|i∈Ie∧ei?V∧ei≠?}的索引集為Ie,對(duì)于I?Ie,該超圖的部分超圖為HI=(V,{ei|i∈I})。

2 自適應(yīng)可分解FR碼的擴(kuò)展構(gòu)造

建立(d,ρ)-超圖與(n,d,θ,ρ)自適應(yīng)可分解FR碼的對(duì)應(yīng)關(guān)系,超圖中邊和頂點(diǎn)分別對(duì)應(yīng)FR碼中存儲(chǔ)節(jié)點(diǎn)和數(shù)據(jù)塊。通過對(duì)(d,ρ)-超圖進(jìn)行擴(kuò)展,實(shí)現(xiàn)自適應(yīng)可分解FR碼在動(dòng)態(tài)分布式存儲(chǔ)系統(tǒng)中的擴(kuò)展,而無需對(duì)系統(tǒng)進(jìn)行重新配置。本節(jié)基于(d,ρ)-超圖,從存儲(chǔ)系統(tǒng)規(guī)模和存儲(chǔ)文件規(guī)模變化這兩個(gè)方面,對(duì)自適應(yīng)可分解FR碼進(jìn)行擴(kuò)展構(gòu)造,使擴(kuò)展后的FR碼仍滿足自適應(yīng)和可分解特性。

2.1 存儲(chǔ)系統(tǒng)規(guī)模變化

當(dāng)存儲(chǔ)系統(tǒng)規(guī)模發(fā)生變化時(shí),通過改變存儲(chǔ)節(jié)點(diǎn)數(shù)和數(shù)據(jù)塊重復(fù)度,即可對(duì)原自適應(yīng)可分解FR碼進(jìn)行擴(kuò)展構(gòu)造。

如果存儲(chǔ)系統(tǒng)規(guī)模減小,即存儲(chǔ)節(jié)點(diǎn)數(shù)n減小,假定節(jié)點(diǎn)存儲(chǔ)容量d和存儲(chǔ)文件規(guī)模(即數(shù)據(jù)塊數(shù)θ)均不變,為滿足FR碼的存在條件(即θρ=nd),則需要減小數(shù)據(jù)塊重復(fù)度ρ。因?yàn)镕R碼中平行類的存儲(chǔ)節(jié)點(diǎn)與超圖的染色邊相對(duì)應(yīng),刪除(d,ρ)-超圖中對(duì)應(yīng)染色邊,就能實(shí)現(xiàn)向(d,ρ-1)-部分超圖的擴(kuò)展。根據(jù)(d,ρ-1)-部分超圖中邊和頂點(diǎn)對(duì)應(yīng)于FR碼中節(jié)點(diǎn)和數(shù)據(jù)塊的關(guān)系,實(shí)現(xiàn)分布式存儲(chǔ)系統(tǒng)規(guī)模變化時(shí)的擴(kuò)展。

圖1為(4,4)-超圖,圖2為對(duì)應(yīng)的(16,4,16,4)自適應(yīng)可分解FR碼。當(dāng)存儲(chǔ)節(jié)點(diǎn)數(shù)減小為n=12時(shí),為滿足θρ=nd,則減小數(shù)據(jù)塊重復(fù)度為ρ=3。在(4,4)-超圖基礎(chǔ)上,刪除染色邊{e13,e14,e15,e16},得到圖3所示(4,3)-部分超圖,對(duì)應(yīng)得到圖4所示(12,4,16,3)自適應(yīng)可分解FR碼。

圖2 (16,4,16,4)自適應(yīng)可分解FR碼

圖3 (4,3)-部分超圖

圖4 (12,4,16,3)自適應(yīng)可分解FR碼

2.2 存儲(chǔ)文件規(guī)模變化

當(dāng)存儲(chǔ)文件規(guī)模發(fā)生變化時(shí),通過改變數(shù)據(jù)塊數(shù)和節(jié)點(diǎn)存儲(chǔ)容量,即可對(duì)原自適應(yīng)可分解FR碼進(jìn)行擴(kuò)展構(gòu)造。

如果存儲(chǔ)文件規(guī)模減小,假定數(shù)據(jù)塊大小不變,則數(shù)據(jù)塊數(shù)θ減小,存儲(chǔ)節(jié)點(diǎn)數(shù)n不變,為滿足FR碼的存在條件(即θρ=nd),保持?jǐn)?shù)據(jù)塊重復(fù)度ρ不變,則需要減小節(jié)點(diǎn)存儲(chǔ)容量d。因?yàn)镕R碼的數(shù)據(jù)塊與超圖的頂點(diǎn)相對(duì)應(yīng),刪除(d,ρ)-超圖中對(duì)應(yīng)頂點(diǎn),就能實(shí)現(xiàn)向(d-1,ρ)-子超圖的擴(kuò)展。根據(jù)(d-1,ρ)-子超圖中邊和頂點(diǎn)對(duì)應(yīng)于FR碼中節(jié)點(diǎn)和數(shù)據(jù)塊的關(guān)系,實(shí)現(xiàn)存儲(chǔ)文件規(guī)模變化時(shí)的擴(kuò)展。

在圖4所示(12,4,16,3)自適應(yīng)可分解FR碼的基礎(chǔ)上,當(dāng)數(shù)據(jù)塊數(shù)減小為θ=12時(shí),為滿足θρ=nd,則減小節(jié)點(diǎn)存儲(chǔ)容量為d=3。在圖3所示(4,3)-超圖基礎(chǔ)上,刪除頂點(diǎn){v13,v14,v15,v16},得到圖5所示(3,3)-子超圖,對(duì)應(yīng)得到圖6所示(12,3,12,3)自適應(yīng)可分解FR碼。

圖5 (3,3)-子超圖

圖6 (12,3,12,3)自適應(yīng)可分解FR碼

2.3 自適應(yīng)可分解FR碼的參數(shù)范圍

利用(d,ρ)-超圖實(shí)現(xiàn)自適應(yīng)可分解FR碼的擴(kuò)展,能夠在給定參數(shù)范圍內(nèi)構(gòu)造全部自適應(yīng)可分解FR碼。表1為自適應(yīng)可分解FR碼在存儲(chǔ)節(jié)點(diǎn)數(shù)20個(gè)以內(nèi)的全部(n,d,θ,ρ)參數(shù)。如表1所示,全部(n,d,θ,ρ)FR碼均可通過基于(d,ρ)-超圖的擴(kuò)展實(shí)現(xiàn)。例如,針對(duì)存儲(chǔ)節(jié)點(diǎn)數(shù)n=8,通過存儲(chǔ)文件規(guī)模變化時(shí)的擴(kuò)展方法,能夠?qū)崿F(xiàn)(8,2,8,2)自適應(yīng)可分解FR碼向(8,3,12,2)和(8,4,16,2)自適應(yīng)可分解FR碼的擴(kuò)展。

表1 (n,d,θ,ρ)自適應(yīng)可分解FR碼的參數(shù)范圍 (n≤20)

3 性能分析

分布式存儲(chǔ)系統(tǒng)在修復(fù)故障節(jié)點(diǎn)時(shí)的兩個(gè)重要性能是修復(fù)局部性和修復(fù)帶寬開銷。本節(jié)從這兩個(gè)方面分析自適應(yīng)可分解FR碼的性能,并對(duì)比最常見的SRC和RS碼,通過Matlab仿真給出這三種編碼方式的性能對(duì)比。

3.1 修復(fù)局部性

在分布式存儲(chǔ)系統(tǒng)中,假設(shè)原文件大小為M,存儲(chǔ)節(jié)點(diǎn)數(shù)為n,重構(gòu)原文件需要至少連接任意k個(gè)存活節(jié)點(diǎn)。(n,k)RS碼中,只要故障節(jié)點(diǎn)數(shù)小于等于n-k,均需要連接k個(gè)存活節(jié)點(diǎn)的數(shù)據(jù)解碼重構(gòu)原文件,再編碼恢復(fù)故障節(jié)點(diǎn)數(shù)據(jù),則修復(fù)局部性為k。(n,k,f)SRC中,原文件由f個(gè)采用(n,k)RS編碼的子文件組成,通過連接2f個(gè)存活節(jié)點(diǎn)能夠修復(fù)單節(jié)點(diǎn)故障,則單節(jié)點(diǎn)故障的修復(fù)局部性為2f;當(dāng)兩節(jié)點(diǎn)同時(shí)故障時(shí),需要連接k個(gè)存活節(jié)點(diǎn)解碼重構(gòu)原文件后進(jìn)行故障修復(fù),則兩節(jié)點(diǎn)同時(shí)故障的修復(fù)局部性為k。(n,d,θ,ρ)自適應(yīng)可分解FR碼中,當(dāng)單節(jié)點(diǎn)故障時(shí),需要連接任一平行類的d個(gè)存活節(jié)點(diǎn)下載相應(yīng)數(shù)據(jù)塊,則修復(fù)局部性為d。當(dāng)兩節(jié)點(diǎn)同時(shí)故障時(shí),若重復(fù)度ρ>2,通過任一平行類的min{n/ρ,2d}個(gè)存活節(jié)點(diǎn)下載相應(yīng)數(shù)據(jù)塊,則修復(fù)局部性為min{n/ρ,2d};若重復(fù)度ρ=2,且兩個(gè)故障節(jié)點(diǎn)存儲(chǔ)相同數(shù)據(jù)塊,連接任意k個(gè)存活節(jié)點(diǎn)重構(gòu)原文件進(jìn)行故障修復(fù),則修復(fù)局部性為k;若重復(fù)度ρ=2,且兩個(gè)故障節(jié)點(diǎn)沒有存儲(chǔ)相同數(shù)據(jù)塊,需要連接n/ρ或2d個(gè)存活節(jié)點(diǎn),則修復(fù)局部性為n/ρ或2d。

設(shè)定(n,k,f)SRC和(n,k)RS碼的存儲(chǔ)節(jié)點(diǎn)數(shù)為n=12,重構(gòu)原文件需要至少連接任意k=9個(gè)存活節(jié)點(diǎn)。SRC中原文件由f=3個(gè)子文件組成,每個(gè)子文件均采用(12,9)RS編碼。為便于性能分析,設(shè)定(n,d,θ,ρ)自適應(yīng)可分解FR碼外部采用(12,9)MDS編碼,其編碼數(shù)據(jù)塊的數(shù)目θ=12,數(shù)據(jù)塊重復(fù)度ρ=3,因此節(jié)點(diǎn)存儲(chǔ)容量為d=3。如圖7所示,相比于(12,9,3)SRC和(12,9)RS碼,外部采用(12,9)MDS編碼的(12,3,12,3)自適應(yīng)可分解FR碼在修復(fù)局部性上具有較大優(yōu)勢(shì)。

圖7 修復(fù)局部性

3.2 修復(fù)帶寬開銷

(n,k)RS碼中,只要故障節(jié)點(diǎn)數(shù)小于等于n-k,均需要連接k個(gè)存活節(jié)點(diǎn)并分別下載M/k的數(shù)據(jù)量,則修復(fù)帶寬開銷為M。(n,k,f)SRC中,當(dāng)單節(jié)點(diǎn)故障時(shí),下載f個(gè)數(shù)據(jù)塊并進(jìn)行異或運(yùn)算能夠修復(fù)一個(gè)故障數(shù)據(jù)塊,由于每個(gè)節(jié)點(diǎn)存儲(chǔ)f+1個(gè)數(shù)據(jù)量為M/fk的數(shù)據(jù)塊,則單節(jié)點(diǎn)故障的修復(fù)帶寬開銷為(f+1)M/k;當(dāng)兩節(jié)點(diǎn)同時(shí)故障時(shí),同(n,k)RS碼一樣,修復(fù)帶寬開銷為M[22]。采用(θ,j)MDS編碼的(n,d,θ,ρ)自適應(yīng)可分解FR碼,每個(gè)數(shù)據(jù)塊的數(shù)據(jù)量為M/j,當(dāng)單節(jié)點(diǎn)故障時(shí),通過d個(gè)存活節(jié)點(diǎn)下載相應(yīng)故障數(shù)據(jù)塊即可,則單節(jié)點(diǎn)故障的修復(fù)帶寬開銷為Md/j。當(dāng)兩節(jié)點(diǎn)同時(shí)故障時(shí),若重復(fù)度ρ>2,這兩個(gè)故障節(jié)點(diǎn)最多存儲(chǔ)一個(gè)相同數(shù)據(jù)塊,則修復(fù)帶寬開銷為M(2d-1)/j或2Md/j;若重復(fù)度ρ=2,且兩個(gè)故障節(jié)點(diǎn)存儲(chǔ)相同數(shù)據(jù)塊,需要重構(gòu)原文件進(jìn)行故障修復(fù),則修復(fù)帶寬開銷為M;若重復(fù)度ρ=2,且兩個(gè)故障節(jié)點(diǎn)不包含相同數(shù)據(jù)塊,只需要從存活節(jié)點(diǎn)中下載相應(yīng)故障數(shù)據(jù),則修復(fù)帶寬開銷為2Md/j。

在3.1節(jié)(12,9,3)SRC、(12,9)RS碼和(12,3,12,3)自適應(yīng)可分解FR碼的基礎(chǔ)上,設(shè)定原始文件大小M=1 000 Mb。如圖8所示,相比于(12,9,3)SRC和(12,9)RS碼,外部采用(12,9)MDS編碼的(12,3,12,3)自適應(yīng)可分解FR碼,在修復(fù)帶寬開銷上具有較大優(yōu)勢(shì)。

4 結(jié)束語(yǔ)

針對(duì)動(dòng)態(tài)分布式存儲(chǔ)系統(tǒng)中FR碼的靈活擴(kuò)展問題,提出一種利用超圖實(shí)現(xiàn)自適應(yīng)可分解FR碼的擴(kuò)展構(gòu)造方法,能夠?qū)崿F(xiàn)當(dāng)文件規(guī)模變化和存儲(chǔ)系統(tǒng)規(guī)模變化時(shí)的擴(kuò)展構(gòu)造。具體地,建立(d,ρ)-超圖與(n,d,θ,ρ)自適應(yīng)可分解FR碼的對(duì)應(yīng)關(guān)系,在原FR碼構(gòu)造和原超圖結(jié)構(gòu)的基礎(chǔ)上,通過增加或刪除超圖中邊和頂點(diǎn),實(shí)現(xiàn)對(duì)動(dòng)態(tài)分布式存儲(chǔ)系統(tǒng)中自適應(yīng)可分解FR碼的擴(kuò)展構(gòu)造?；谶@種方法,能夠擴(kuò)展構(gòu)造出給定參數(shù)范圍內(nèi)所有自適應(yīng)可分解FR碼。自適應(yīng)可分解FR碼相比于SRC和RS碼,具有較優(yōu)的修復(fù)局部性和修復(fù)帶寬開銷。