基于節(jié)點(diǎn)共邊的異構(gòu)部分重復(fù)碼構(gòu)造①

田松濤

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

當(dāng)今世界互聯(lián)網(wǎng)快速發(fā)展,數(shù)據(jù)海量化是互聯(lián)網(wǎng)技術(shù)發(fā)展的必然結(jié)果[1].如何快速、高效、可靠地存儲這些數(shù)據(jù)資源成為研究熱點(diǎn)和面臨的巨大挑戰(zhàn).傳統(tǒng)的集中式存儲將數(shù)據(jù)集中存放在專用服務(wù)器或者專用磁盤陣列中,存儲海量數(shù)據(jù)時存在諸多瓶頸,例如系統(tǒng)性能、存儲成本和可擴(kuò)展性.分布式存儲系統(tǒng)將海量數(shù)據(jù)存儲在多個廉價(jià)存儲設(shè)備中,海量存儲能力、高吞吐量、高可用性、高可擴(kuò)展性和低成本等突出優(yōu)勢使分布式存儲系統(tǒng)成為海量數(shù)據(jù)的有效存儲手段.但是實(shí)際的分布式存儲系統(tǒng)中不可避免地會出現(xiàn)節(jié)點(diǎn)故障,如何高效地修復(fù)故障節(jié)點(diǎn)來保障分布式存儲系統(tǒng)的高可靠性和高可用性成為目前急需解決的關(guān)鍵問題[2,3].

現(xiàn)有的復(fù)制和糾刪碼策略能修復(fù)分布式存儲系統(tǒng)中的節(jié)點(diǎn)故障,但都存在各自的缺陷.隨后,Dimakis 等人將網(wǎng)絡(luò)編碼應(yīng)用到分布式存儲系統(tǒng)中,提出了再生碼的概念[4],顯著降低了故障節(jié)點(diǎn)的修復(fù)帶寬開銷.再生碼雖然能有效降低故障節(jié)點(diǎn)修復(fù)時的帶寬開銷,但沒有考慮磁盤I/O 開銷和修復(fù)局部性.為了確保修復(fù)故障節(jié)點(diǎn)較低修復(fù)帶寬開銷的同時,需要連接的存活節(jié)點(diǎn)數(shù)也較少,Papailiopoulos 等人提出了局部修復(fù)碼(locally repairable codes,LRC)[5].進(jìn)一步,Hao 等人和Wang 等人分別研究了局部修復(fù)碼的構(gòu)造以及協(xié)作局部修復(fù)碼[6,7].

再生碼和局部修復(fù)碼在故障節(jié)點(diǎn)修復(fù)過程中涉及大量有限域運(yùn)算,計(jì)算復(fù)雜度較高.為了進(jìn)一步降低計(jì)算復(fù)雜度和修復(fù)帶寬開銷,El Rouayheb 等人提出一種精確修復(fù)的最小帶寬再生碼——部分重復(fù)(fractional repetition,FR)碼[8].目前對 FR 碼的研究主要有基于組合設(shè)計(jì)構(gòu)造FR 碼[9],基于序列構(gòu)造FR 碼[10],基于二分圖構(gòu)造局部修復(fù) FR 碼[11],FR 碼的修復(fù)消耗最小化[12].這些構(gòu)造算法復(fù)雜,并且大多只能構(gòu)造同構(gòu)的FR 碼,不能得到異構(gòu)的FR 碼.Silberstein 等人基于組合設(shè)計(jì)和正則圖,提出了一種達(dá)到最大碼率的FR 碼的構(gòu)造方法[13],但其重復(fù)度受 FR 碼結(jié)構(gòu)的約束,不能適用于任意參數(shù).基于Hadamard 矩陣構(gòu)造的異構(gòu)部分重復(fù)碼[14,15]修復(fù)復(fù)雜度和修復(fù)帶寬開銷都有所降低.基于矩陣變換和可調(diào)節(jié)環(huán)的部分重復(fù)碼構(gòu)造[16]可以大范圍的選擇參數(shù),構(gòu)造結(jié)構(gòu)簡單直觀.Zhu 等人提出基于組合設(shè)計(jì)的FR 碼,可以調(diào)整存儲節(jié)點(diǎn)的數(shù)量和節(jié)點(diǎn)的存儲容量[17].進(jìn)一步,Zhu 等人對一般好的部分重復(fù)碼的重復(fù)度限和重構(gòu)度限進(jìn)行了討論[18-21].在實(shí)際的分布式存儲系統(tǒng)中,數(shù)據(jù)存儲的結(jié)構(gòu)多為異構(gòu)的,并且需要動態(tài)存儲,即在增加或減少數(shù)據(jù)時,自動調(diào)節(jié)數(shù)據(jù)的存儲分布.

為了解決上述問題,本文構(gòu)造了一種基于節(jié)點(diǎn)共邊的異構(gòu)部分重復(fù)碼(heterogeneous fractional repetition codes based on node common edge,HFRC-NCE).具體地,結(jié)合節(jié)點(diǎn)共邊的特性,將熱數(shù)據(jù)存儲在多點(diǎn)共邊上,將冷數(shù)據(jù)存儲在兩點(diǎn)共邊上,使得熱數(shù)據(jù)具有較高的重復(fù)度,同時各個節(jié)點(diǎn)存儲的數(shù)據(jù)容量不同,實(shí)現(xiàn)數(shù)據(jù)的動態(tài)存儲和異構(gòu)存儲.性能分析表明,與文獻(xiàn)[8]基于完全圖和文獻(xiàn)[22]基于部分正則圖構(gòu)造的部分重復(fù)碼相比,雖然HFRC-NCE的存儲開銷和修復(fù)帶寬開銷略大,但其構(gòu)造簡單,減小了文件的重構(gòu)度,節(jié)點(diǎn)的修復(fù)選擇度更高,節(jié)點(diǎn)存儲的數(shù)據(jù)容量更加多樣性,使得系統(tǒng)能更高效地修復(fù)故障節(jié)點(diǎn).

1 點(diǎn)共邊和部分重復(fù)碼

1.1 點(diǎn)共邊

圖G通常用G=(V,E) 表示,其中V(G)和E(G)分別為圖G中的節(jié)點(diǎn)集和邊集.圖G中節(jié)點(diǎn)的個數(shù)稱為圖G的階,與節(jié)點(diǎn)相關(guān)聯(lián)的邊的總數(shù)稱為節(jié)點(diǎn)的度,將ρ 點(diǎn)存在同一條邊上記為Eρ,如圖1所示.如果圖G中任意兩個不同的節(jié)點(diǎn)通過邊相互連接,稱圖G為完全圖.當(dāng)圖G中每個節(jié)點(diǎn)都具有相同的度,則稱圖G為正則圖.

圖1 ρ點(diǎn) 共邊的Eρ

n階完全圖的各個節(jié)點(diǎn)相連的邊的總和為完全圖可視為由個E2構(gòu)成的圖,在任意兩點(diǎn)都通過邊相連的前提下,當(dāng)圖G中邊的總和小于時,說明圖G中的邊不僅有兩點(diǎn)相連的情況,還存在多點(diǎn)共邊的情況.

圖2為ρ點(diǎn)共邊時相對于n階完全圖減少的邊數(shù).當(dāng)一個3 階完全圖變?yōu)? 點(diǎn)共邊E3會減少兩條邊,一個4 階完全圖變?yōu)? 點(diǎn)共邊E4會減少5 條邊.以此類推,n階完全圖變?yōu)棣?點(diǎn)共邊Eρ會減少條邊.當(dāng)圖中邊的總和θ小于時,圖中必然存在3 點(diǎn)及以上多點(diǎn)共邊.將 ρ 點(diǎn)共邊Eρ的個數(shù)記為Pρ,則:

圖2 多點(diǎn)共邊時減少的邊數(shù)

具體地以圖3中的6 階圖為例,圖中共有9 條邊,n=6,θ=9.根據(jù)式(1)和式(2),得到P2=6和P3=3,則圖3存在3 條3 點(diǎn)共邊的邊E3和6 條2 點(diǎn)共邊的邊E2.

圖3 E 2和E3組合圖

1.2 部分重復(fù)碼

部分重復(fù)碼的實(shí)質(zhì)是由外部的最大距離可分碼(maximum distance separable,MDS)和內(nèi)部重復(fù)碼構(gòu)成,首先將原始文件分成M個原始數(shù)據(jù)塊,原始數(shù)據(jù)塊通過(θ,M)M DS 碼編碼后,生成θ 個編碼數(shù)據(jù)塊,再將生成的編碼數(shù)據(jù)塊復(fù)制 ρ倍分別存儲到n個節(jié)點(diǎn)中,每個節(jié)點(diǎn)存儲d個不同的編碼塊,得到一個(n,d,θ,ρ)部分重復(fù)碼,滿足nd=θρ.

圖4為基于完全圖構(gòu)造的部分重復(fù)碼,由外部的(15,14)M DS 碼和內(nèi)部重復(fù)度ρ=2的重復(fù)碼構(gòu)成.將MDS碼編碼后的15 個數(shù)據(jù)塊依次存放在完全圖的不同邊上,每個節(jié)點(diǎn)存儲5 個數(shù)據(jù)塊.每個節(jié)點(diǎn)故障時需要連接其他5 個存活節(jié)點(diǎn)進(jìn)行修復(fù),所以d=5.此系統(tǒng)至少需要4 個節(jié)點(diǎn)來重構(gòu)原文件,所以k=4,并且滿足nd=θρ.

圖4 基于完全圖構(gòu)造的(6,5,15,2)部分重復(fù)碼

2 基于節(jié)點(diǎn)共邊的異構(gòu)部分重復(fù)碼

2.1 基于節(jié)點(diǎn)共邊的異構(gòu)部分重復(fù)碼構(gòu)造

在實(shí)際的分布式存儲系統(tǒng)中,存儲節(jié)點(diǎn)的存儲容量大多異構(gòu).為了滿足分布式存儲系統(tǒng)存儲容量異構(gòu)的特點(diǎn),結(jié)合節(jié)點(diǎn)共邊的特性,按照熱數(shù)據(jù)重復(fù)度高和冷數(shù)據(jù)重復(fù)度低的原則構(gòu)造異構(gòu)部分重復(fù)碼.具體步驟如下.

步驟1.首先將原始文件分成M(M=θ-1)個原始數(shù)據(jù)塊,原始數(shù)據(jù)塊通過(θ,M) M DS 碼編碼后生成θ 個編碼數(shù)據(jù)塊,將其存儲到具有n個 節(jié)點(diǎn)的n階圖中.

步驟2.設(shè)Pρ為一個未知參數(shù),Pρ表示 ρ點(diǎn)共邊Eρ的數(shù)目.將MDS 碼編碼后的一個數(shù)據(jù)塊存放在共邊Eρ上,則該共邊Eρ上的所有 ρ個節(jié)點(diǎn)都將存儲該數(shù)據(jù)塊,相當(dāng)于將此數(shù)據(jù)塊重復(fù)存儲了ρ 倍.本文中數(shù)據(jù)塊的重復(fù)度 ρ最大取4,所以只會出現(xiàn)P2、P3和P4三個未知參數(shù).

步驟3.通過已知的節(jié)點(diǎn)個數(shù)n和編碼后的數(shù)據(jù)塊個數(shù)θ,結(jié)合式(1)和式(2),可以解出符合條件的未知參數(shù)P2、P3和P4.將MDS 碼編碼后的數(shù)據(jù)塊分為熱數(shù)據(jù)塊和冷數(shù)據(jù)塊,將熱數(shù)據(jù)塊存儲在3 點(diǎn)共邊或者4 點(diǎn)共邊的邊上,將冷數(shù)據(jù)塊存儲在2 點(diǎn)共邊的邊上,通過以上的編碼過程可以得到一個異構(gòu)的部分重復(fù)碼.

具體地,通過例1 來說明構(gòu)造的過程.

例1.首先將原始文件分成M=7個原始數(shù)據(jù)塊,通過(8,7)M DS 碼編碼生成θ=8個編碼數(shù)據(jù)塊,將這些編碼后的數(shù)據(jù)塊存儲到n=6個存儲節(jié)點(diǎn)中,在滿足參數(shù)要求的情況下,將節(jié)點(diǎn)數(shù)和編碼后的數(shù)據(jù)塊個數(shù)代入式(1)和式(2)中:解得未知參數(shù)P3為1,P4為1,表示有1 條3 點(diǎn)共邊的邊和1 條4 點(diǎn)共邊的邊,通過與MDS 碼編碼生成的θ=8個 編碼數(shù)據(jù)塊做差,得到P2為6,即有6 條兩點(diǎn)共邊的邊,將編碼后的數(shù)據(jù)塊1,2 看作熱數(shù)據(jù)塊,將3,4,5,6,7,8 看作冷數(shù)據(jù)塊,將熱數(shù)據(jù)塊1 存儲在4 點(diǎn)共邊上,將熱數(shù)據(jù)塊2 存儲在3 點(diǎn)共邊上,將冷數(shù)據(jù)塊3,4,5,6,7,8 依次存儲在2 點(diǎn)共邊上,通過此編碼過程可以得到6 個節(jié)點(diǎn)的數(shù)據(jù)塊存儲分布如圖5所示.

圖5 n=6,θ=8的HFRC-NCE

2.2 節(jié)點(diǎn)修復(fù)

本文異構(gòu)部分重復(fù)碼是基于節(jié)點(diǎn)共邊來構(gòu)造的,因此當(dāng)節(jié)點(diǎn)發(fā)生故障時,可以簡單直觀的通過圖中的數(shù)據(jù)分布來修復(fù)節(jié)點(diǎn),當(dāng)節(jié)點(diǎn)故障時只需連接圖中相鄰的存活節(jié)點(diǎn)進(jìn)行修復(fù),下面分單節(jié)點(diǎn)故障和多節(jié)點(diǎn)故障進(jìn)行討論.

單節(jié)點(diǎn)故障修復(fù):HFRC-NCE 每個數(shù)據(jù)塊最小的重復(fù)度為2,即每條邊的數(shù)據(jù)塊最少存儲在兩個節(jié)點(diǎn)上,故當(dāng)單個節(jié)點(diǎn)發(fā)生故障時可從相鄰的存活節(jié)點(diǎn)下載數(shù)據(jù)塊進(jìn)行修復(fù),并且當(dāng)故障節(jié)點(diǎn)存儲的數(shù)據(jù)塊位于E3或E4時,故障節(jié)點(diǎn)修復(fù)將有更多的選擇方案.如圖5中的節(jié)點(diǎn)1 發(fā)生故障時,節(jié)點(diǎn)1 中的3和6 數(shù)據(jù)塊可連接節(jié)點(diǎn)5和6 下載相應(yīng)的數(shù)據(jù)塊進(jìn)行修復(fù),節(jié)點(diǎn)1 中的1 數(shù)據(jù)塊位于E4上,所以可通過連接節(jié)點(diǎn)2、3、4 中的任意一個下載數(shù)據(jù)塊1 進(jìn)行修復(fù).

多節(jié)點(diǎn)故障修復(fù):HFRC-NCE 每個數(shù)據(jù)塊最大的重復(fù)度為4,即每條邊的數(shù)據(jù)塊最多存放在4 個節(jié)點(diǎn)上,故最多能同時修復(fù)3 個故障節(jié)點(diǎn),存在以下3 種情況:

(1)當(dāng)同時修復(fù)3 個故障節(jié)點(diǎn)時,這3 個節(jié)點(diǎn)應(yīng)在同一個E4上.

(2)當(dāng)同時修復(fù)2 個故障節(jié)點(diǎn)時,這2 個節(jié)點(diǎn)應(yīng)在同一個E3上.

(3)當(dāng)故障節(jié)點(diǎn)不在同一個E3或E4時,只能修復(fù)單節(jié)點(diǎn)故障不能修復(fù)多節(jié)點(diǎn)故障.

圖5中的節(jié)點(diǎn)1、2和3 同時發(fā)生故障時,節(jié)點(diǎn)1、2和3 中的數(shù)據(jù)塊1 均可連接節(jié)點(diǎn)4 下載數(shù)據(jù)塊1 進(jìn)行修復(fù),節(jié)點(diǎn)1、2和3 中的其他數(shù)據(jù)塊可連接相鄰的存活節(jié)點(diǎn)下載相應(yīng)的數(shù)據(jù)塊進(jìn)行修復(fù).當(dāng)節(jié)點(diǎn)5和6 同時發(fā)生故障時,節(jié)點(diǎn)5和6 可以通過連接存活節(jié)點(diǎn)1、2、3和4 下載相應(yīng)的數(shù)據(jù)塊進(jìn)行修復(fù).當(dāng)節(jié)點(diǎn)3和6 同時發(fā)生故障時,由于節(jié)點(diǎn)3和6 不在同一多點(diǎn)共邊上,數(shù)據(jù)塊8 沒有存活節(jié)點(diǎn)可供下載,故不能同時修復(fù)節(jié)點(diǎn)3和6.

3 性能分析

本節(jié)主要分析HFRC-NCE的節(jié)點(diǎn)修復(fù)選擇度、節(jié)點(diǎn)存儲容量、重構(gòu)度、存儲開銷和修復(fù)帶寬開銷,并與完全圖和部分正則圖構(gòu)造的部分重復(fù)碼進(jìn)行對比.

3.1 節(jié)點(diǎn)修復(fù)選擇度

修復(fù)故障節(jié)點(diǎn)可選的方案數(shù),叫做該節(jié)點(diǎn)的修復(fù)選擇度.基于節(jié)點(diǎn)共邊的異構(gòu)部分重復(fù)碼的節(jié)點(diǎn)修復(fù)選擇度與各個數(shù)據(jù)塊的重復(fù)度 ρ和節(jié)點(diǎn)容量d相關(guān).由于每個編碼數(shù)據(jù)塊存儲到不同的共邊上,故每個數(shù)據(jù)塊的重復(fù)度并不相同,每個節(jié)點(diǎn)存儲著不同數(shù)量的數(shù)據(jù)塊.當(dāng)單節(jié)點(diǎn)發(fā)生故障時,需要分情況討論:當(dāng)發(fā)生故障的節(jié)點(diǎn)在3 點(diǎn)或4 點(diǎn)共邊時,單節(jié)點(diǎn)的修復(fù)選擇度為ρ-1;當(dāng)發(fā)生的節(jié)點(diǎn)存儲在多節(jié)點(diǎn)共邊相交的位置時,單節(jié)點(diǎn)的修復(fù)選擇度為(ρmax-1)×(ρmax-2),當(dāng)發(fā)生故障的節(jié)點(diǎn)在2 點(diǎn)共邊時,單節(jié)點(diǎn)的修復(fù)選擇度為1.當(dāng)多節(jié)點(diǎn)發(fā)生故障時,多個節(jié)點(diǎn)需位于同一條共邊上否則將無法修復(fù),多故障節(jié)點(diǎn)的修復(fù)選擇度為ρ-2.圖6所示為3 種構(gòu)造的部分重復(fù)碼,節(jié)點(diǎn)故障的最大修復(fù)選擇度對比.

圖6 節(jié)點(diǎn)故障的最大修復(fù)選擇度對比

如圖5當(dāng)節(jié)點(diǎn)1、2、3 中的一個發(fā)生故障時,單節(jié)點(diǎn)的修復(fù)選擇度為3;當(dāng)節(jié)點(diǎn)5、6 中的一個發(fā)生故障時,單節(jié)點(diǎn)的修復(fù)選擇度為2;當(dāng)節(jié)點(diǎn)4 發(fā)生故障時,單節(jié)點(diǎn)的修復(fù)選擇度為6.當(dāng)節(jié)點(diǎn)1和2 同時故障時,節(jié)點(diǎn)修復(fù)選擇度為2;當(dāng)節(jié)點(diǎn)1和6 同時故障時,由于節(jié)點(diǎn)1 在4 點(diǎn)共邊上,節(jié)點(diǎn)6 在3 點(diǎn)共邊上,導(dǎo)致數(shù)據(jù)塊6 沒有存活節(jié)點(diǎn)供其下載修復(fù),無法進(jìn)行多節(jié)點(diǎn)修復(fù).

基于完全圖和部分正則圖構(gòu)造的部分重復(fù)碼,單節(jié)點(diǎn)的節(jié)點(diǎn)修復(fù)選擇度為1,并且當(dāng)2 個及以上節(jié)點(diǎn)故障時均不能進(jìn)行修復(fù).因此HFRC-NCE 提高了單節(jié)點(diǎn)及多節(jié)點(diǎn)的節(jié)點(diǎn)修復(fù)選擇度,并增加了故障節(jié)點(diǎn)可修復(fù)的個數(shù).

3.2 節(jié)點(diǎn)存儲容量

節(jié)點(diǎn)存儲容量及每個節(jié)點(diǎn)存儲的數(shù)據(jù)塊容量,表1為完全圖和部分正則圖構(gòu)造的部分重復(fù)碼和HFRCNCE 節(jié)點(diǎn)存儲容量的對比.

表1 不同構(gòu)造部分重復(fù)碼存儲容量的對比

通過部分節(jié)點(diǎn)的存儲容量對比發(fā)現(xiàn)HFRC-NCE的節(jié)點(diǎn)存儲容量更加多樣化,更適用于實(shí)際的分布式存儲系統(tǒng)中.

相對于靜態(tài)存儲,動態(tài)存儲更適用于實(shí)際的分布式存儲系統(tǒng),HFRC-NCE 在增刪原始文件M時,即更改MDS 碼編碼后的數(shù)據(jù)塊θ,可以根據(jù)式(1)和式(2),快速求得Eρ的邊數(shù),使得數(shù)據(jù)塊復(fù)制的倍數(shù)有所變化,進(jìn)而改變節(jié)點(diǎn)的存儲分布,達(dá)到動態(tài)存儲,同時也體現(xiàn)了HFRC-NCE的節(jié)點(diǎn)存儲容量的多樣化.

3.3 重構(gòu)度

用k表示文件的重構(gòu)度,k的定義為重構(gòu)原文件所需的最少節(jié)點(diǎn)數(shù).CMBR(n,k,d)=kd-=M,CMBR表示最小帶寬再生碼的存儲容量,等于從系統(tǒng)中任意k個節(jié)點(diǎn)所能獲得的文件大小M.n階完全圖構(gòu)造的部分重復(fù)碼原始文件M=θ-1,每個節(jié)點(diǎn)存儲的數(shù)據(jù)塊容量d為n-1,將d和M代入CMBR的公式中可以求得k=n-2,即重構(gòu)原始文件至少需要n-2個節(jié)點(diǎn).HFRCNCE的各個節(jié)點(diǎn)的數(shù)據(jù)塊容量d不同,當(dāng)節(jié)點(diǎn)位于多點(diǎn)共邊相交的位置時,節(jié)點(diǎn)存儲的數(shù)據(jù)塊容量d最小;當(dāng)節(jié)點(diǎn)位于兩點(diǎn)共邊不位于多點(diǎn)共邊時,節(jié)點(diǎn)存儲的數(shù)據(jù)塊容量d最大.在HFRC-NCE 中,當(dāng)只存在E2和x個E3時,數(shù)據(jù)塊容量d最小為n-1-x,最大為n-1;當(dāng)只存在E2和x個E4時,數(shù)據(jù)塊容量d最小為n-2-x,最大為n-1.HFRC-NCE的重構(gòu)度會隨選取節(jié)點(diǎn)的不同而變化.下面通過表2不同的節(jié)點(diǎn)數(shù)和編碼后的數(shù)據(jù)塊來分析重構(gòu)度.

通過表2可以得出,在節(jié)點(diǎn)個數(shù)相同的情況下,HFRC-NCE的最小重構(gòu)度k為n-4,完全圖構(gòu)造的部分重復(fù)碼的重構(gòu)度k為n-2,HFRC-NCE的重構(gòu)度小于基于完全圖構(gòu)造的部分重復(fù)碼的重構(gòu)度.由于HFRCNCE 增加了部分?jǐn)?shù)據(jù)塊的重復(fù)度,MDS 碼編碼后的數(shù)據(jù)塊相對于完全圖構(gòu)造的部分重復(fù)碼的編碼塊較少,所以HFRC-NCE的重構(gòu)度有所降低.

表2 不同參數(shù)下文件的重構(gòu)度

3.4 存儲開銷和修復(fù)帶寬開銷

存儲開銷為各個節(jié)點(diǎn)存儲數(shù)據(jù)塊所需的空間與原始文件M的比值.n階完全圖構(gòu)造的部分重復(fù)碼,將原始文件M經(jīng)過MDS碼編碼后生成 θ=個編碼塊,每個節(jié)點(diǎn)存儲n-1 個數(shù)據(jù)塊,其存儲開銷為×n×(n-1)=2M.n階部分正則圖構(gòu)造的部分重復(fù)碼的存儲開銷也為2M.HFRC-NCE的原始文件M經(jīng)過MDS碼編碼后生成 θ＜個編碼塊,編碼塊復(fù)制不同的倍數(shù)存儲到各個節(jié)點(diǎn)中,編碼塊復(fù)制的倍數(shù)取決于此編碼塊所在的Eρ,存儲的數(shù)據(jù)塊總和為當(dāng)HFRCNCE 只存在E2和E3時,結(jié)合式(1)式(2)可推導(dǎo)出HFRCNCE的存儲開銷為若HFRC-NCE的存儲開銷等于 2M需滿足但HFRC-NCE的θ＜故HFRC-NCE的存儲開銷大于2M,即大于基于完全圖和部分正則圖構(gòu)造的部分重復(fù)碼的存儲開銷.同理,當(dāng)HFRC-NCE只存在E2和E4時,結(jié)合式(1)式(2)可推導(dǎo)出HFRCNCE的存儲開銷為HFRC-NCE的θ＜故HFRC-NCE的存儲開銷仍大于2M.圖7所示,當(dāng)原始文件大小M=1000 MB時,3 種構(gòu)造的部分重復(fù)碼存儲開銷的對比.

圖7 存儲開銷對比

修復(fù)帶寬開銷為修復(fù)故障節(jié)點(diǎn)時所需下載的數(shù)據(jù)量的大小.n階完全圖構(gòu)造的部分重復(fù)碼,原始文件大小為M,經(jīng)過MDS 碼編碼后生成θ=個編碼塊,每個節(jié)點(diǎn)存儲n-1個數(shù)據(jù)塊,則單故障節(jié)點(diǎn)的修復(fù)帶寬開銷為n階部分正則圖構(gòu)造的部分重復(fù)碼,原始文件大小為M,經(jīng)過MDS 碼編碼后生成θ=個編碼塊,其中n-1個節(jié)點(diǎn)每個節(jié)點(diǎn)存儲n-2 個 數(shù)據(jù)塊,1 個節(jié)點(diǎn)存儲n-3個數(shù)據(jù)塊,則單故障節(jié)點(diǎn)的修復(fù)帶寬開銷為(n-3).HFRC-NCE 每個節(jié)點(diǎn)存儲的數(shù)據(jù)塊數(shù)量不同,故不同節(jié)點(diǎn)故障時的修復(fù)帶寬開銷不同.圖8所示,當(dāng)原始文件大小M=1000 MB時,3 種構(gòu)造的部分重復(fù)碼節(jié)點(diǎn)修復(fù)帶寬開銷的對比.

圖8 節(jié)點(diǎn)修復(fù)帶寬開銷對比

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

衡量一個算法的好壞,其算法運(yùn)算復(fù)雜度是一個重要的指標(biāo).本文構(gòu)造的HFRC-NCE 碼,在構(gòu)造時只需根據(jù)已知的節(jié)點(diǎn)數(shù)和邊數(shù)結(jié)合式(1)和式(2)求出兩點(diǎn)共邊和多點(diǎn)共邊的情況,之后將冷數(shù)據(jù)和熱數(shù)據(jù)塊分別存儲在邊上,構(gòu)造出的HFRC-NCE 碼簡單直觀.本文的構(gòu)造與文獻(xiàn)[13]相比,文獻(xiàn)[13]運(yùn)用大量組合設(shè)計(jì)的知識,所需判斷的情況過多,加大運(yùn)算復(fù)雜度,因此本文的算法復(fù)雜度更優(yōu).

4 結(jié)論

當(dāng)前部分重復(fù)碼的構(gòu)造大多為同構(gòu)的并且為靜態(tài)存儲,不太適用于實(shí)際的分布式存儲系統(tǒng).本文結(jié)合節(jié)點(diǎn)共邊的特性,并將實(shí)際分布式系統(tǒng)的冷熱數(shù)據(jù)塊相結(jié)合,構(gòu)造的HFRC-NCE 簡單直觀,便于進(jìn)行快速的節(jié)點(diǎn)修復(fù).通過與完全圖和部分正則圖構(gòu)造的部分重復(fù)碼對比,可以發(fā)現(xiàn),HFRC-NCE 雖然具有較高的存儲開銷和修復(fù)帶寬開銷,但能實(shí)現(xiàn)更多故障節(jié)點(diǎn)的修復(fù),降低了文件的重構(gòu)度,提高了節(jié)點(diǎn)的修復(fù)選擇度,使節(jié)點(diǎn)容量更加多樣化,并且在增刪原始數(shù)據(jù)時,能快速地調(diào)整節(jié)點(diǎn)的存儲分布,實(shí)現(xiàn)動態(tài)存儲.