基于矩陣變換和可調(diào)節(jié)環(huán)的部分重復(fù)碼構(gòu)造①

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

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

隨著大數(shù)據(jù)時(shí)代的到來,數(shù)據(jù)資源呈現(xiàn)出快速增長的趨勢,數(shù)據(jù)的存儲(chǔ)容量也隨之不斷增加.傳統(tǒng)的數(shù)據(jù)存儲(chǔ)系統(tǒng)已經(jīng)不能適應(yīng)當(dāng)前海量數(shù)據(jù)存儲(chǔ),分布式存儲(chǔ)系統(tǒng)逐漸成為主流存儲(chǔ)方式.通過將海量數(shù)據(jù)分散的存儲(chǔ)在多臺(tái)互相獨(dú)立物理設(shè)備上,分布式存儲(chǔ)系統(tǒng)不僅很好的分擔(dān)了存儲(chǔ)負(fù)載,而且成本低廉,可擴(kuò)展性能好,但是分布式存儲(chǔ)系統(tǒng)中的這些物理存儲(chǔ)設(shè)備容易發(fā)生故障,可造成大量數(shù)據(jù)丟失.因此,如何提高數(shù)據(jù)存儲(chǔ)的可靠性就成為了分布式存儲(chǔ)亟需解決的問題[1-3].

為保證數(shù)據(jù)存儲(chǔ)時(shí)的高可靠性和高可用性,傳統(tǒng)的分布式存儲(chǔ)系統(tǒng)中生成冗余數(shù)據(jù)的策略通常有“復(fù)制”和“糾刪碼”策略[4,5].谷歌文件系統(tǒng)和Hadoop 系統(tǒng)運(yùn)用了三副本復(fù)制策略,將原始數(shù)據(jù)塊復(fù)制成三個(gè)副本然后存儲(chǔ)在系統(tǒng)中來保證存儲(chǔ)的可靠性,這樣會(huì)導(dǎo)致存儲(chǔ)開銷過大；為了減小存儲(chǔ)開銷,在實(shí)際系統(tǒng)中引入糾刪碼的冗余策略,但該策略在修復(fù)故障節(jié)點(diǎn)時(shí)會(huì)帶來巨大的帶寬開銷.針對(duì)上述問題,Dimakis 等將網(wǎng)絡(luò)編碼的思想運(yùn)用到分布式存儲(chǔ)中,提出了再生碼的概念[6],有效減少了存儲(chǔ)開銷和修復(fù)帶寬開銷.目前對(duì)再生碼的研究表明,主要表現(xiàn)在存儲(chǔ)和帶寬均衡曲線上的兩個(gè)極值點(diǎn),一個(gè)極值點(diǎn)對(duì)應(yīng)最小存儲(chǔ)再生碼

MSRC (Minimum Storage Regenerating Code),另一個(gè)極值點(diǎn)對(duì)應(yīng)最小帶寬再生碼MBRC (Minimum Bandwidth Regenerating Code).文獻(xiàn)[7-9]給出了一些好的再生碼的構(gòu)造方法.

但是,再生碼的缺陷在于,在進(jìn)行故障節(jié)點(diǎn)修復(fù)時(shí),需要大量基于有限域上的計(jì)算,計(jì)算復(fù)雜度高,修復(fù)局部性復(fù)雜.為解決上述問題,EI Rouayheb 和Ram chan dram 在MBRC 的研究基礎(chǔ)上提出了一種新型碼——部分重復(fù)碼(Fractional Repetition Codes,FRC)[10],該碼可以進(jìn)行精確無編碼有效的修復(fù).一般意義上的FRC由兩部分組成：外部的編碼是最大距離可分碼 (Maximum Distance Sparable,MDS)和內(nèi)部是重復(fù)碼,該碼修復(fù)故障節(jié)點(diǎn)無需任何編碼操作,可以很好地降低故障修復(fù)時(shí)所需的帶寬和磁盤I/O 開銷.目前對(duì)FRC 的研究主要有基于組合設(shè)計(jì)構(gòu)造的FRC[11],基于圖構(gòu)造的FRC[12],基于偏序集構(gòu)造的FRC[13],基于二分圖構(gòu)造的局部修復(fù)的FRC[14],這些構(gòu)造算法復(fù)雜,并且大多只能構(gòu)造同構(gòu)的FRC,不能得到異構(gòu)的FRC.

為此,本文提出了兩種構(gòu)造方法,一種是基于矩陣變換構(gòu)造的異構(gòu)FRC,該構(gòu)造用于構(gòu)造重復(fù)度為2,節(jié)點(diǎn)存儲(chǔ)容量異構(gòu)的FRC,該方法計(jì)算復(fù)雜度低,只需進(jìn)行簡單的異或運(yùn)算就可得到節(jié)點(diǎn)存儲(chǔ)容量異構(gòu)的FRC,相比現(xiàn)有的運(yùn)用正則圖構(gòu)造的同構(gòu)FRC,該構(gòu)造在節(jié)點(diǎn)存儲(chǔ)容量上更符合現(xiàn)實(shí)的存儲(chǔ)系統(tǒng)；另外,本文還提出了運(yùn)用可調(diào)節(jié)環(huán)構(gòu)造的FRC,該方法根據(jù)一定的存放規(guī)則能得到不同重復(fù)度的FRC,主要構(gòu)造重復(fù)度 的情況,因?yàn)榇蟛糠謱?duì)部分重復(fù)碼的研究中重復(fù)度都是2 或3,同時(shí)該方法也可靈活的調(diào)節(jié)節(jié)點(diǎn)存儲(chǔ)容量,即可得到節(jié)點(diǎn)存儲(chǔ)容量同構(gòu)的FRC 也可得到節(jié)點(diǎn)存儲(chǔ)容量異構(gòu)的FRC,可大范圍選擇參數(shù),構(gòu)造結(jié)構(gòu)簡單直觀.同時(shí)本文上最大的應(yīng)用價(jià)值在于能無編碼的修復(fù)節(jié)點(diǎn)存儲(chǔ)容量異構(gòu)的分布式存儲(chǔ)系統(tǒng)中的故障節(jié)點(diǎn),應(yīng)用前景好,具有很好的實(shí)用價(jià)值.

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

目前研究表明,對(duì)MDS 碼的研究已經(jīng)十分成熟了,各種參數(shù)的MDS 碼都可得到.所以對(duì)部分重復(fù)碼的研究主要體現(xiàn)在內(nèi)部重復(fù)碼的構(gòu)造上.FRC 實(shí)際上是復(fù)制倍數(shù)為ρ 的 θ 個(gè)數(shù)據(jù)塊在節(jié)點(diǎn)上的一種排列組合,復(fù)制生成的數(shù)據(jù)塊都分別存儲(chǔ)在不同的系統(tǒng)節(jié)點(diǎn)上.內(nèi)部的重復(fù)碼可用 (n,k,d,θ,ρ,α)FRC 表示,其中n表示存儲(chǔ)系統(tǒng)的節(jié)點(diǎn)數(shù),θ表示存儲(chǔ)在節(jié)點(diǎn)中的數(shù)據(jù)塊個(gè)數(shù),ρ表示數(shù)據(jù)塊的復(fù)制次數(shù),α表示每個(gè)節(jié)點(diǎn)的存儲(chǔ)容量,d表示修復(fù)一個(gè)失效節(jié)點(diǎn)需連接的存活節(jié)點(diǎn)數(shù),一般認(rèn)為α=d.數(shù)學(xué)上的定義如下：

定義1[15].參數(shù)為(n,k,d)分布式存儲(chǔ)系統(tǒng)的部分重復(fù)碼C=(M,U),復(fù)制倍數(shù)為ρ,是指特定的n個(gè)子集的集合U={U1,U2,···,Un},每個(gè)子集的元素均來自于符號(hào)集M={1,2,···,θ}.并且節(jié)點(diǎn)存儲(chǔ)容量同構(gòu)的FRC 還需要滿足下面條件：

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

2)M中的每一個(gè)元素都屬于U中的子集,每個(gè)子集數(shù)大小為ρ；

3)同構(gòu)的FRC 滿足nα=ρθ.

定義2[16].(d1,d2,···,dm)正 則圖G(V,E)是一個(gè)無向圖,其中 |V|=n,V1,V2,···,Vm?V,并且Vi∩Vj=? .頂點(diǎn)Vi的度為di(1 ≤i≤m),若G(V,E)所有頂點(diǎn)的度都等于d,則該G(V,E)叫 作d-正則圖,若G(V,E)頂點(diǎn)的度不相等分別為d1,d2,···,dm,則稱該G(V,E)為(d1,d2,···,dm)-正則圖,也叫部分正則圖.

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

本節(jié)運(yùn)用矩陣變換的思想,結(jié)合部分正則圖提出了一種新的節(jié)點(diǎn)存儲(chǔ)容量異構(gòu)的部分重復(fù)碼,相比文獻(xiàn)[10]和文獻(xiàn)[16]中運(yùn)用正則圖和部分正則圖構(gòu)造的部分重復(fù)碼,本構(gòu)造能得到節(jié)點(diǎn)存儲(chǔ)容量更加多樣的FRC,和傳統(tǒng)RS 碼相比,在修復(fù)單節(jié)點(diǎn)故障時(shí),修復(fù)局部性更好,修復(fù)復(fù)雜度更優(yōu),無需任何編碼操作,計(jì)算復(fù)雜低.具體構(gòu)造算法如下：

該構(gòu)造主要用于構(gòu)造節(jié)點(diǎn)存儲(chǔ)容量異構(gòu)的FRC,適用于分布式存儲(chǔ)系統(tǒng)節(jié)點(diǎn)數(shù)n為奇數(shù)的情況,且構(gòu)造的FRC 中數(shù)據(jù)塊的重復(fù)度ρ 等于2；具體步驟如下：

步驟1.定義一個(gè)n階的二進(jìn)制循環(huán)置換矩陣Cn(d?1),其中n代 表節(jié)點(diǎn)數(shù),d?1表示每個(gè)節(jié)點(diǎn)存儲(chǔ)容量同時(shí)也表示矩陣中每一行1 的個(gè)數(shù),且需滿足的條件為d＞3,d為奇數(shù)；同時(shí)我們?cè)O(shè)定Cn(d?1)矩陣的第一行在數(shù)學(xué)上滿足的表達(dá)式為：c(t)=t+t2+···+t(d?1)/2+tn?(d?1)/2+···+tn?1.

在矩陣的第一行確定后,矩陣后面的每一行依次向右移動(dòng)一位,共移動(dòng)n?1次,最后生成Cn(d?1)矩陣；

步驟2.為得到節(jié)點(diǎn)存儲(chǔ)容量異構(gòu)的FRC,在步驟1 的基礎(chǔ)上引入矩陣Sn去 調(diào)節(jié)步驟1 中的Cn(d?1)矩陣,Sn矩 陣生成方法為：在(n?1)階副對(duì)角線都為1,其他元素全為0 的方陣后面加一行0 和一列0,生成n×n階的Sn矩陣；

步驟3.將步驟1 中的矩陣Cn(d?1)和步驟2 中的矩陣Sn進(jìn) 行模2 運(yùn)算,得到二進(jìn)制矩陣P=Cn(d?1)+Sn(mod 2),矩陣P和部分正則圖存在相關(guān)聯(lián)的關(guān)系,用P=(mij)n×n,1 ≤i,j≤n表示部分正則圖的關(guān)聯(lián)矩陣,關(guān)聯(lián)規(guī)則如下：

由上面關(guān)系可知,部分正則圖的每一個(gè)頂點(diǎn)的度和矩陣的每一行中1 的個(gè)數(shù)是相等的,經(jīng)過算法的驗(yàn)證,發(fā)現(xiàn)矩陣P的不同行中會(huì)出現(xiàn)有d,d?1,d?2個(gè)1 的情況,因此對(duì)應(yīng)的部分正則圖的度有d,d?1,d?2三種情況,記作(d,d?1,d?2)-部分正則圖,也就對(duì)應(yīng)著構(gòu)造的FRC 的節(jié)點(diǎn)存儲(chǔ)容量有d,d?1,d?2三種情況.

對(duì)構(gòu)造的FRC 的故障節(jié)點(diǎn)修復(fù)進(jìn)行分析可知,因?yàn)樵揊RC 的重復(fù)度 ρ=2,所以本構(gòu)造能容忍單個(gè)節(jié)點(diǎn)出現(xiàn)故障,又由于異構(gòu)FRC 的節(jié)點(diǎn)容量有d,d?1,d?2三種情況,所以分以下3 種情況討論：

1)若存儲(chǔ)容量為d的節(jié)點(diǎn)出現(xiàn)故障,那么只需要從另外的d個(gè)節(jié)點(diǎn)分別下載一個(gè)數(shù)據(jù)塊即可直接修復(fù)；

2)若存儲(chǔ)容量為d?1的節(jié)點(diǎn)出現(xiàn)故障,那么只需要從另外的d?1個(gè)節(jié)點(diǎn)分別下載一個(gè)數(shù)據(jù)塊即可直接修復(fù)；

3)若存儲(chǔ)容量為d?2的節(jié)點(diǎn)出現(xiàn)故障,那么只需要從另外的d?2個(gè)節(jié)點(diǎn)分別下載一個(gè)數(shù)據(jù)塊即可直接修復(fù).

當(dāng)系統(tǒng)中出現(xiàn)故障節(jié)點(diǎn),只需直接從其他存活的節(jié)點(diǎn)下載數(shù)據(jù)塊修復(fù),修復(fù)選擇性高,無編碼操作,計(jì)算復(fù)雜度低.根據(jù)上述構(gòu)造算法給出如下具體實(shí)例.

例1.給定n=7,d=5,根據(jù)構(gòu)造方法步驟1 得到矩陣C7(4),其中C7(4)是一個(gè)7 ×7的二進(jìn)制矩陣且第一行表示為c(t)=t+t2+t5+t6,第一行確定后,后面的每一行依次向右移動(dòng)一位,最后生成C7(4)矩陣,如下所示：

進(jìn)一步運(yùn)用矩陣S7調(diào)節(jié)矩陣C7(4),S7矩陣是在6 階副對(duì)角線都為1,其他元素全為0 的矩陣后面加一行0 和一列0 生成的,如下所示：

得到S7矩 陣后,通過P=C7(4)+S7(mod 2)算得矩陣P,如下所示：

根據(jù)矩陣P能得到 (3,4,5)-部分正則圖,即部分正則圖的度有5,4,3 這三種情況,也就對(duì)應(yīng)節(jié)點(diǎn)存儲(chǔ)容量有5,4,3 三種情況,如圖1所示.

若節(jié)點(diǎn)U1發(fā)生故障,需連接U2,U3,U7這3 個(gè)節(jié)點(diǎn)進(jìn)行修復(fù),即從U2,U3,U7這3 個(gè)節(jié)點(diǎn)下載1,6,7數(shù)據(jù)塊進(jìn)行修復(fù),修復(fù)過程如圖2所示.同理,其他節(jié)點(diǎn)發(fā)生故障也可用相同的方法進(jìn)行修復(fù).

圖1 (3,4,5)-部分正則圖和對(duì)應(yīng)FRC 數(shù)據(jù)塊存儲(chǔ)結(jié)構(gòu)圖

圖2 故障節(jié)點(diǎn)修復(fù)圖

3 基于可調(diào)節(jié)環(huán)的FRC 構(gòu)造

本節(jié)運(yùn)用可調(diào)節(jié)環(huán)結(jié)構(gòu)構(gòu)造FRC,根據(jù)一定的存放規(guī)則去調(diào)節(jié)重復(fù)度的大小和節(jié)點(diǎn)存儲(chǔ)容量,規(guī)則是將數(shù)據(jù)元素放入相鄰的節(jié)點(diǎn)所在環(huán)的邊之間,規(guī)定當(dāng)每一個(gè)數(shù)據(jù)塊依次放在兩個(gè)相鄰的節(jié)點(diǎn)之間時(shí),此時(shí)FRC 的重復(fù)度為 ρ=2；當(dāng)每一個(gè)數(shù)據(jù)塊都放在3 個(gè)相鄰的節(jié)點(diǎn)之間,此時(shí)FRC 的重復(fù)度為 ρ=3,同理可用相同的存放規(guī)則去調(diào)節(jié)重復(fù)度.由同構(gòu)FRC 參數(shù)滿足的條件nα=ρθ可知,當(dāng)給定的參數(shù)滿足該條件時(shí),可得到同構(gòu)的FRC,若該等式不成立,則可用可調(diào)節(jié)環(huán)構(gòu)造節(jié)點(diǎn)存儲(chǔ)容量異構(gòu)的FRC,根據(jù)已有的對(duì)FRC 的研究中發(fā)現(xiàn),大部分只考慮重復(fù)度為2,3 的情況,具體構(gòu)造算法如下.

3.1 用可調(diào)節(jié)環(huán)去構(gòu)造重復(fù)度ρ=2的FRC

假設(shè)系統(tǒng)中節(jié)點(diǎn)用U1,U2,···,Un表示,節(jié)點(diǎn)中的數(shù)據(jù)塊用θ 表示,且[θ]={1,2,···,θ},將數(shù)據(jù)塊按一定規(guī)則放入環(huán)中,即從節(jié)點(diǎn)U1開 始,將數(shù)據(jù)塊1 放在U1和U2所在的邊上,將數(shù)據(jù)塊2 放在U2和U3所在的邊上,數(shù)據(jù)塊3 放到U3和U4所 在邊上,以此類推,直到將θ 個(gè)數(shù)據(jù)塊放完為止.

根據(jù)上述算法可以得到重復(fù)度 ρ=2的FRC.因?yàn)槊恳粋€(gè)數(shù)據(jù)塊存在于相鄰的2 個(gè)節(jié)點(diǎn)所在環(huán)的邊上,每個(gè)數(shù)據(jù)塊都會(huì)被兩個(gè)節(jié)點(diǎn)所共有,即得到的是重復(fù)度 ρ=2 的FRC.若所給參數(shù)滿足nα=ρθ,用可調(diào)節(jié)環(huán)可以構(gòu)造節(jié)點(diǎn)存儲(chǔ)容量同構(gòu)的FRC,否則用可調(diào)節(jié)環(huán)可以構(gòu)造節(jié)點(diǎn)存儲(chǔ)容量異構(gòu)的FRC.具體實(shí)例如下,其中,例2 給定的是用可調(diào)節(jié)環(huán)構(gòu)造的重復(fù)度 ρ=2的同構(gòu)FRC,例3 給定的是用可調(diào)節(jié)環(huán)構(gòu)造的重復(fù)度ρ=2的異構(gòu)FRC.

例2.給定n=6,θ=12,用可調(diào)節(jié)環(huán)去構(gòu)造FRC,環(huán)結(jié)構(gòu)和節(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu),如圖3所示.

圖3 可調(diào)節(jié)環(huán)結(jié)構(gòu)和節(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)

由節(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)圖可知該FRC 滿足nα=ρθ,是同構(gòu)的FRC,重復(fù)度ρ=2,節(jié)點(diǎn)儲(chǔ)存容量為α=4,若節(jié)點(diǎn)U1故障,需要從U2下載數(shù)塊1,7,從U6下載數(shù)據(jù)塊6 和12 修復(fù)U1,其他節(jié)點(diǎn)故障也可用相同的修復(fù)方式進(jìn)行修復(fù),無需編碼操作.

例3.給定n=8,θ=21,用可調(diào)節(jié)環(huán)去構(gòu)造FRC,環(huán)結(jié)構(gòu)和節(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)圖,如圖4.

圖4 可調(diào)節(jié)環(huán)結(jié)構(gòu)和節(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)圖

由節(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)圖可知,該FRC 不滿足nα=ρθ,是異構(gòu)的FRC,且重復(fù)度 ρ=2,節(jié)點(diǎn)存儲(chǔ)容量有4,5,6 三種情況,可修復(fù)單節(jié)點(diǎn)故障,修復(fù)方式是直接從存活節(jié)點(diǎn)下載相應(yīng)數(shù)據(jù)塊進(jìn)行修復(fù).

3.2 用可調(diào)節(jié)環(huán)去構(gòu)造重復(fù)度ρ=3的FRC

若分布式存儲(chǔ)系統(tǒng)的節(jié)點(diǎn)用U1,U2,···,Un表示,θ表示存儲(chǔ)在節(jié)點(diǎn)中的數(shù)據(jù)塊,且[θ]={1,2,···,θ},將θ個(gè)數(shù)據(jù)塊按一定的規(guī)則放入環(huán)中,即從U1節(jié)點(diǎn)開始,將數(shù)據(jù)塊1 分別放到U1U2和U2U3所在的邊上,將數(shù)據(jù)塊2 分別放到U2U3和U3U4所在邊上,數(shù)據(jù)塊3 放到U3U4和U4U5所 在邊上,以此類推,直到將θ 個(gè)數(shù)據(jù)塊放完為止.

根據(jù)上述算法可得到重復(fù)度ρ=3的FRC.因?yàn)槊恳粋€(gè)數(shù)據(jù)塊存在于相鄰的3 個(gè)節(jié)點(diǎn)所在的環(huán)之間,即每個(gè)數(shù)據(jù)塊都會(huì)被3 個(gè)節(jié)點(diǎn)共有,則得到的是重復(fù)度ρ=3的FRC.若所給參數(shù)滿足nα=ρθ,用可調(diào)節(jié)環(huán)可以構(gòu)造節(jié)點(diǎn)存儲(chǔ)容量同構(gòu)的FRC,否則可以構(gòu)造節(jié)點(diǎn)存儲(chǔ)容量異構(gòu)的FRC.具體實(shí)例如下,其中,例4 給定的是用可調(diào)節(jié)環(huán)構(gòu)造的重復(fù)度ρ=3的同構(gòu)FRC,如圖5所示,例5 給定的是用可調(diào)節(jié)環(huán)構(gòu)造的重復(fù)度 ρ=3的異構(gòu)FRC,如圖6所示.

例4.給定θ=n=4,則用可調(diào)節(jié)環(huán)去構(gòu)造FRC,結(jié)構(gòu)如下.

由上面的可調(diào)節(jié)環(huán)結(jié)構(gòu)圖和節(jié)點(diǎn)存儲(chǔ)圖可知,構(gòu)造得到的碼是重復(fù)度 ρ=3,節(jié)點(diǎn)存儲(chǔ)容量為3 的同構(gòu)FRC.該FRC 的故障節(jié)點(diǎn)修復(fù)方式為,當(dāng)U1發(fā)生故障,可以直接重U3中下載1,3 兩個(gè)數(shù)據(jù)塊,再從U2或U4中下載4 這個(gè)數(shù)據(jù)塊；當(dāng)U1和U2同時(shí)發(fā)生故障時(shí),可以直接從U3和U4節(jié)點(diǎn)中下載數(shù)據(jù)塊進(jìn)行修復(fù),修復(fù)方式簡單,無需任何編碼.

圖5 可調(diào)節(jié)環(huán)結(jié)構(gòu)和節(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)圖

圖6 可調(diào)節(jié)環(huán)結(jié)構(gòu)和節(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)圖

例5.給定 θ=16,n=8,用可調(diào)節(jié)環(huán)去構(gòu)造FRC,結(jié)構(gòu)如下.

由上面的可調(diào)節(jié)環(huán)結(jié)構(gòu)圖和節(jié)點(diǎn)存儲(chǔ)圖可知,構(gòu)造得到的FRC 是重復(fù)度 ρ=3,節(jié)點(diǎn)存儲(chǔ)容量異構(gòu)的FRC,節(jié)點(diǎn)容量出現(xiàn)7,6,5 三種情況.該FRC 的故障節(jié)點(diǎn)修復(fù)方式為,直接從存活節(jié)點(diǎn)下載數(shù)據(jù)塊,可最多修復(fù)兩個(gè)故障節(jié)點(diǎn).

4 性能分析

對(duì)本文提出的兩種新的構(gòu)造進(jìn)行性能分析,主要與現(xiàn)有的FRC 對(duì)比分析,發(fā)現(xiàn)本文構(gòu)造的FRC 在節(jié)點(diǎn)存儲(chǔ)容量上具有異構(gòu)的特點(diǎn),修復(fù)局部性好,同時(shí)在構(gòu)造算法運(yùn)算復(fù)雜度低,可以大范圍的選擇參數(shù),構(gòu)造結(jié)構(gòu)簡單直觀.

4.1 節(jié)點(diǎn)存儲(chǔ)容量對(duì)比分析

對(duì)矩陣變換構(gòu)造的異構(gòu)FRC 和已有的用正則圖和部分正則圖構(gòu)造的FRC 進(jìn)行對(duì)比分析,主要分析節(jié)點(diǎn)存儲(chǔ)容量,如表1.

表1 節(jié)點(diǎn)存儲(chǔ)容量對(duì)比分析

表1只列舉了部分情況,可以發(fā)現(xiàn)本文提出的基于矩陣構(gòu)造的異構(gòu)FRC 相比于正則圖構(gòu)造的FRC 在節(jié)點(diǎn)存儲(chǔ)容量上是異構(gòu)的,并且本文提出的構(gòu)造方法在節(jié)點(diǎn)修復(fù)選擇度上更優(yōu).

對(duì)基于可調(diào)節(jié)環(huán)構(gòu)造的FRC 進(jìn)行對(duì)比分析,相比于文獻(xiàn)[10]提出的運(yùn)用正則圖構(gòu)造的FRC 本構(gòu)造在重復(fù)度上的選擇性更靈活,正則圖只能構(gòu)造 ρ=2的同構(gòu)FRC,用可環(huán)結(jié)構(gòu)可以得到重復(fù)度多樣的同構(gòu)或異構(gòu)的FRC,構(gòu)造算法更簡單直觀.

4.2 參數(shù)選擇對(duì)比分析

根據(jù)已有研究表明,大多數(shù)構(gòu)造FRC 的方法都對(duì)參數(shù)有明顯的限制,對(duì)比分析得本文提出的基于可調(diào)節(jié)環(huán)構(gòu)造的FRC,在參數(shù)選擇上更具有靈活性,對(duì)比分析結(jié)果,如表2.分析結(jié)果.表2中各參數(shù)含義解釋如下：α是FRC 的節(jié)點(diǎn)存儲(chǔ)容量,d表示修復(fù)單個(gè)節(jié)點(diǎn)時(shí)需要連接的節(jié)點(diǎn)數(shù),一般意義上 α=d,ρ表示FRC 的數(shù)據(jù)重復(fù)度,θ表示系統(tǒng)中數(shù)據(jù)塊,n表示系統(tǒng)中的節(jié)點(diǎn)數(shù),q是 素?cái)?shù),h是Hadamard 矩陣的階數(shù).

4.3 修復(fù)局部性對(duì)比分析

修復(fù)局部性是指在修復(fù)故障節(jié)點(diǎn)時(shí)需要連接的存活節(jié)點(diǎn)數(shù).當(dāng)單節(jié)點(diǎn)出現(xiàn)故障時(shí),運(yùn)用正則圖構(gòu)造的FRC 需要連接的節(jié)點(diǎn)數(shù)為d,即修復(fù)局部性為d,運(yùn)用基于矩陣變換構(gòu)造的異構(gòu)FRC 需要連接的節(jié)點(diǎn)數(shù)有d,d?1,d?2 三 種情況,即修復(fù)局部性為d,d?1,d?2三種情況,修復(fù)局部性更好.另外,當(dāng)出現(xiàn)單節(jié)點(diǎn)故障時(shí),(n,k)RS 碼需要連接k個(gè)節(jié)點(diǎn)先恢復(fù)原始文件來修復(fù)出現(xiàn)故障的節(jié)點(diǎn),修復(fù)局部性為k；基于矩陣變換構(gòu)造的異構(gòu)FRC 需要連接的節(jié)點(diǎn)數(shù)有d,d?1,d?2三種情況,修復(fù)局部性為d,d?1,d?2三種情況,又由于研究的FRC 都是d＜k,所以可知和(n,k)RS 對(duì)比,基于矩陣變換構(gòu)造的異構(gòu)FRC 具有更好的修復(fù)局部性.

表2 不同構(gòu)造方法參數(shù)對(duì)比分析圖

圖7給定的實(shí)例是基于矩陣變換構(gòu)造的異構(gòu)FRC和(n,k)RS 碼的在修復(fù)局部性方面的對(duì)比情況,當(dāng)修復(fù)節(jié)點(diǎn)存儲(chǔ)容量為d(d＜k)的節(jié)點(diǎn)時(shí),可知基于矩陣變換構(gòu)造的異構(gòu)FRC 的修復(fù)局部性恒為d(d＜k),但RS 碼的修復(fù)局部性與k(正整數(shù))是一次線性關(guān)系.

圖7 修復(fù)局部性與數(shù)據(jù)塊k 的關(guān)系圖

4.4 構(gòu)造算法運(yùn)算復(fù)雜度

衡量一個(gè)算法的優(yōu)劣,通常需要考慮算法構(gòu)造時(shí)涉及的運(yùn)算復(fù)雜度,即將算法寫成程序在實(shí)際的計(jì)算機(jī)系統(tǒng)中運(yùn)行時(shí),涉及的計(jì)算量.本文基于矩陣變換的異構(gòu)FRC,由構(gòu)造算法可知,構(gòu)造一個(gè)異構(gòu)的FRC 需要進(jìn)行d?1次 加法運(yùn)算和n2次模2 加運(yùn)算；運(yùn)用可調(diào)節(jié)環(huán)構(gòu)造的FRC,構(gòu)造時(shí)不需要任何計(jì)算量,只需在環(huán)上直接進(jìn)行調(diào)節(jié)即可,相比于基于矩陣變換的異構(gòu)FRC,用可調(diào)節(jié)環(huán)得到的FRC,在構(gòu)造算法運(yùn)算復(fù)雜度表現(xiàn)的更優(yōu).

將基于矩陣變換的異構(gòu)FRC 和運(yùn)用偏序集構(gòu)造的FRC[10]在構(gòu)造算法運(yùn)算復(fù)雜度進(jìn)行對(duì)比分析,在文獻(xiàn)[10]中,構(gòu)造算法時(shí)運(yùn)用到了加法,乘法運(yùn)算和基于集合上的運(yùn)算,明顯可知本文算法運(yùn)算復(fù)雜度更低.

5 結(jié)論

考慮實(shí)際的分布式存儲(chǔ)系統(tǒng)大多需要滿足異構(gòu)的特性.為此,本文提出了兩種構(gòu)造方法,一種是基于矩陣變換構(gòu)造的異構(gòu)FRC,該構(gòu)造主要用于構(gòu)造重復(fù)度為2,節(jié)點(diǎn)存儲(chǔ)容量異構(gòu)的FRC,相比用正則圖構(gòu)造的同構(gòu)FRC,該構(gòu)造更符合現(xiàn)實(shí)的存儲(chǔ)系統(tǒng)；另外,本文還提出了運(yùn)用可調(diào)節(jié)環(huán)構(gòu)造的FRC,構(gòu)造得到了重復(fù)度為2 或3 的FRC,該方法即可得到節(jié)點(diǎn)存儲(chǔ)容量同構(gòu)的FRC 也可得到節(jié)點(diǎn)存儲(chǔ)容量異構(gòu)的FRC.與現(xiàn)有的FRC 對(duì)比分析,發(fā)現(xiàn)本文構(gòu)造的FRC 在節(jié)點(diǎn)存儲(chǔ)容量上具有異構(gòu)的特點(diǎn),修復(fù)局部性好,同時(shí)在構(gòu)造算法運(yùn)算復(fù)雜度低,可以大范圍的選擇參數(shù),構(gòu)造結(jié)構(gòu)簡單直觀.將來如何去構(gòu)造更多樣的異構(gòu)FRC 是研究的熱點(diǎn).