自適應(yīng)可分解部分重復(fù)碼的擴展構(gòu)造

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

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

0 引 言

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

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

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

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

1 基礎(chǔ)知識

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

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

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

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

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

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

(4)θρ=nd。

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

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

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

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

1.2 超 圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在圖4所示(12,4,16,3)自適應(yīng)可分解FR碼的基礎(chǔ)上,當(dāng)數(shù)據(jù)塊數(shù)減小為θ=12時,為滿足θρ=nd,則減小節(jié)點存儲容量為d=3。在圖3所示(4,3)-超圖基礎(chǔ)上,刪除頂點{v13,v14,v15,v16},得到圖5所示(3,3)-子超圖,對應(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,ρ)-超圖實現(xiàn)自適應(yīng)可分解FR碼的擴展,能夠在給定參數(shù)范圍內(nèi)構(gòu)造全部自適應(yīng)可分解FR碼。表1為自適應(yīng)可分解FR碼在存儲節(jié)點數(shù)20個以內(nèi)的全部(n,d,θ,ρ)參數(shù)。如表1所示,全部(n,d,θ,ρ)FR碼均可通過基于(d,ρ)-超圖的擴展實現(xiàn)。例如,針對存儲節(jié)點數(shù)n=8,通過存儲文件規(guī)模變化時的擴展方法,能夠?qū)崿F(xiàn)(8,2,8,2)自適應(yīng)可分解FR碼向(8,3,12,2)和(8,4,16,2)自適應(yīng)可分解FR碼的擴展。

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

3 性能分析

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

3.1 修復(fù)局部性

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

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

圖7 修復(fù)局部性

3.2 修復(fù)帶寬開銷

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

4 結(jié)束語

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