分布式存儲(chǔ)系統(tǒng)中新型可修復(fù)噴泉碼構(gòu)造

周安安, 易本順, 劉羽升, 羅來(lái)干

(武漢大學(xué)電子信息學(xué)院, 湖北 武漢 430072)

0 引 言

隨著現(xiàn)代信息技術(shù)的快速發(fā)展,數(shù)據(jù)生成速度迅猛提高,根據(jù)IDC發(fā)布的最新版白皮書《Data Age 2025》顯示,預(yù)測(cè)2025年全球數(shù)據(jù)量將從2019年的45 ZB增長(zhǎng)到175 ZB,其中將近30%將需要實(shí)時(shí)處理[1]。在數(shù)據(jù)存儲(chǔ)領(lǐng)域,海量數(shù)據(jù)的增長(zhǎng)使得分布式存儲(chǔ)系統(tǒng)受到了更多關(guān)注。在大規(guī)模分布式存儲(chǔ)系統(tǒng)當(dāng)中,由于其組件通常來(lái)自成本較低但相對(duì)容易故障的設(shè)備集,因此故障的發(fā)生已經(jīng)成為一種常態(tài)。面對(duì)頻繁的設(shè)備(即存儲(chǔ)節(jié)點(diǎn))故障事件,存儲(chǔ)系統(tǒng)通常采用數(shù)據(jù)容錯(cuò)技術(shù)來(lái)保證存儲(chǔ)數(shù)據(jù)的高可靠性和可用性[2-3]。

多副本技術(shù)是分布式存儲(chǔ)系統(tǒng)采用的最簡(jiǎn)單的冗余方法[4]。然而,一份文件有多個(gè)副本,使得存儲(chǔ)開銷呈倍數(shù)增加。因此,犧牲更多的存儲(chǔ)空間來(lái)?yè)Q取存儲(chǔ)數(shù)據(jù)的可用性,在海量數(shù)據(jù)生成的今天并不可靠。作為替代冗余技術(shù),糾刪編碼在獲得相同存儲(chǔ)數(shù)據(jù)可靠性的情況下,比多副本技術(shù)節(jié)省更多的存儲(chǔ)空間[5-7]。因此,糾刪編碼技術(shù)已經(jīng)在許多大規(guī)模分布式存儲(chǔ)系統(tǒng)中得到了應(yīng)用,比如Google的ColossusFS和Facebook的HDFS-RAID[8]都部署了RS (reed-solomon)碼[9-10],并分別將存儲(chǔ)冗余降到了1.4倍和1.5倍,相比于三副本技術(shù)的3倍有著更強(qiáng)的優(yōu)勢(shì)。

然而,傳統(tǒng)的糾刪碼方案比如最大距離可分離(maximum distance separable,MDS)[11-12]和噴泉碼(fountain code,FC)[13-14],在處理故障節(jié)點(diǎn)修復(fù)問(wèn)題時(shí),需要訪問(wèn)多個(gè)可用節(jié)點(diǎn)數(shù)據(jù)并傳輸,不可避免地要消耗大量帶寬資源,而分布式存儲(chǔ)系統(tǒng)的帶寬資源卻很稀缺。為了解決這一問(wèn)題,Dimakis等人將網(wǎng)絡(luò)編碼部署到分布式存儲(chǔ)系統(tǒng)中,提出了再生碼 (regenerating codes, RCs),降低了存儲(chǔ)空間開銷和故障修復(fù)的帶寬資源開銷[15]。之后Rashimi等人在這個(gè)基礎(chǔ)上進(jìn)一步提出了最小存儲(chǔ)再生碼 (minimum storage regenerating codes, MSR)和最小帶寬再生碼 (minimum bandwidth regenerating codes, MBR),分別實(shí)現(xiàn)了存儲(chǔ)開銷最小和帶寬開銷最小的目的[16]。MSR碼和MBR碼雖然都能有效地完成故障節(jié)點(diǎn)的修復(fù)工作,卻會(huì)產(chǎn)生較高的磁盤I/O開銷(即節(jié)點(diǎn)修復(fù)過(guò)程需要訪問(wèn)的可用節(jié)點(diǎn)數(shù)量)。因此,一些學(xué)者在糾偏碼中引入了局部性的概念[17-19],并提出了相應(yīng)的編碼方案,其中最著名的就是局部可修碼(locally repairable codes, LRCs)[20-22]。更準(zhǔn)確地說(shuō),局部性被定義為需要訪問(wèn)以重建故障符號(hào)的其他符號(hào)數(shù)量。為了減少帶寬消耗,系統(tǒng)通常期待一個(gè)低的局部性。然而,LRCs碼的不足之處在于其構(gòu)造比較復(fù)雜,在大規(guī)模分布式存儲(chǔ)系統(tǒng)當(dāng)中靈活性不高。

可修復(fù)噴泉碼(repairable fountain codes, RFC)是文獻(xiàn)[23]提出的分布式存儲(chǔ)系統(tǒng)容錯(cuò)代碼的一個(gè)新編碼方案。與LRC碼類似,RFC也有著較低的修復(fù)局部,另外同時(shí)兼?zhèn)鋰娙a的諸多優(yōu)點(diǎn):系統(tǒng)性、無(wú)率性、低編譯碼復(fù)雜度等。由于其在平衡存儲(chǔ)開銷和修復(fù)帶寬方面的潛力,吸引了越來(lái)越多的研究興趣。在文獻(xiàn)[24]中,作者設(shè)計(jì)了一種安全的RFC,通過(guò)在消息中附加隨機(jī)符號(hào)并通過(guò)Gabidulin碼進(jìn)行預(yù)編碼來(lái)實(shí)現(xiàn)安全。考慮到多層異構(gòu)存儲(chǔ)網(wǎng)絡(luò)中的數(shù)據(jù)緩存問(wèn)題,在文獻(xiàn)[25]中，作者設(shè)計(jì)了一種具有不等修復(fù)局部性的RFC,可以進(jìn)一步降低不同邊緣區(qū)域的整體通信開銷。Baik等人[26]提出了一種局部改進(jìn)RFC,通過(guò)逐項(xiàng)抽樣和行丟棄來(lái)構(gòu)造生成矩陣,從而實(shí)現(xiàn)在不降低譯碼性能的同時(shí)降低修復(fù)局部性。然而,對(duì)于RFC來(lái)說(shuō),為了保證譯碼的成功率,在傳輸編碼包的同時(shí)需要將對(duì)應(yīng)的生成矩陣進(jìn)行傳輸,這就產(chǎn)生了額外的帶寬資源消耗。傳統(tǒng)噴泉碼的每一個(gè)編碼符號(hào)也都需要攜帶相應(yīng)的鄰居信息,這些信息隨著消息符號(hào)的增加而非線性增加。這意味著會(huì)額外消耗帶寬和存儲(chǔ)資源。綜上所述,研究新的RFC方案,減少分布式存儲(chǔ)系統(tǒng)不必要的帶寬開銷具有重要意義。

在解決傳統(tǒng)噴泉碼或因傳輸編碼生成矩陣而產(chǎn)生的額外高傳輸帶寬開銷問(wèn)題上,已有學(xué)者研究了多種解決方法。文獻(xiàn)[27-28]提出了基于熵編碼的LT(luby transform)碼生成矩陣壓縮算法,在保持LT碼性能的同時(shí),大大減少了數(shù)據(jù)流量。文獻(xiàn)[29]提出了一種模擬噴泉壓縮傳感(analog fountain compressive sensing, AFCS)方法來(lái)實(shí)現(xiàn)二進(jìn)制稀疏信號(hào)的稀疏恢復(fù)。在文獻(xiàn)[30]中,作者提出了一種新的遞減冗余方法來(lái)壓縮噴泉碼源,實(shí)現(xiàn)無(wú)損解碼。在文獻(xiàn)[31]中,為了獲得線性時(shí)間復(fù)雜度和競(jìng)爭(zhēng)性能,提出了一種基于Raptor碼的通用變長(zhǎng)無(wú)損壓縮算法。

受RFC和壓縮算法的啟發(fā),基于改進(jìn)的稀疏矩陣壓縮存儲(chǔ)算法提出了一種新的RFC編碼結(jié)構(gòu)。與非系統(tǒng)噴泉編碼不同,RFC由于其系統(tǒng)形式而具有更好的可壓縮性。在提出的方案中,編碼包的鄰域信息被建模為序列,并以生成矩陣的列為單位進(jìn)行無(wú)損壓縮。除此之外,還提出了一個(gè)新的性能指標(biāo)—有效吞吐量來(lái)分析該方案的性能。在保留RFC的編碼性能前提下,該方案可以有效減少故障節(jié)點(diǎn)修復(fù)和源文件恢復(fù)時(shí)因?yàn)樯删仃嚨膫鬏攷?lái)的額外數(shù)據(jù)傳輸量。

1 RFC及矩陣壓縮存儲(chǔ)模型

1.1 RFC的構(gòu)造

RFC是Asteris等人[23]為了解決分布式存儲(chǔ)系統(tǒng)可靠性問(wèn)題所提出的容錯(cuò)編碼方案。RFC擁有多個(gè)優(yōu)點(diǎn),包括系統(tǒng)性、稀疏性、近MDS性、邏輯局部性以及無(wú)率性。其中系統(tǒng)性對(duì)于分布式存儲(chǔ)系統(tǒng)來(lái)講至關(guān)重要,因?yàn)樗硎究梢栽诓恍枰獯a操作的情況下讀取到源文件信息,避免了更多的帶寬資源消耗,符合目前許多分布式存儲(chǔ)系統(tǒng)應(yīng)用的實(shí)際需求。近MDS性是另外一個(gè)有利于高效下載數(shù)據(jù)的屬性,表示當(dāng)選擇(1+ε)k個(gè)編碼符號(hào)時(shí)可以高概率譯碼源信息,其中ε>0。對(duì)于邏輯局部性,表示修復(fù)一個(gè)故障節(jié)點(diǎn)需要訪問(wèn)的節(jié)點(diǎn)數(shù)為d(k)=C(lgk),其中C是常數(shù)。

原始文件被分成k份,并且用U=(u1,u2,…,uk)表示k個(gè)信息符號(hào),其中U是有限域Fq上的k長(zhǎng)信息符號(hào)序列。隨后對(duì)信息符號(hào)進(jìn)行k×n大小的生成矩陣G編碼操作之后得到n個(gè)編碼符號(hào)序列V=(v1,v2,…,vn)。需要注意的是,n個(gè)編碼符號(hào)當(dāng)中前k個(gè)編碼符號(hào)是信息符號(hào)的副本,這也就表示編碼符號(hào)為系統(tǒng)符號(hào)與校驗(yàn)符號(hào)的集合。通過(guò)下面的幾個(gè)步驟可以得到余下的校驗(yàn)符號(hào)vj,j=k+1,k+2,…,n。

步驟 1依次獨(dú)立、均勻地從k個(gè)信息符號(hào)中隨機(jī)選擇d(k)個(gè)信息符號(hào);

步驟 2針對(duì)步驟1中選取的每一個(gè)消息符號(hào),在有限域Fq當(dāng)中隨機(jī)地為其選擇一個(gè)對(duì)應(yīng)的系數(shù)進(jìn)行加權(quán);

步驟 3完成步驟2工作之后,將加權(quán)之后的消息符號(hào)進(jìn)行線性組合,最終得到校驗(yàn)符號(hào)。

因此,通過(guò)重復(fù)上述步驟1～步驟3的過(guò)程,即可將余下的校驗(yàn)符號(hào)全部生成。在前面的假設(shè)中,已知向量u表示信息符號(hào)向量,則ui表示第i個(gè)信息符號(hào),ui是有限域中的元素。用向量v表示編碼符號(hào)向量,vj表示第j個(gè)編碼符號(hào),則其生成表達(dá)式可以表示為

vj=uG(j)=∑ωijui,j=k+1,k+2,…,n

(1)

式中:G(j)表示生成矩陣G中的第j列元素;ωij表示第j個(gè)編碼符號(hào),在選擇第i個(gè)信息符號(hào)時(shí)對(duì)應(yīng)的系數(shù)。其編碼過(guò)程用圖1來(lái)表示,為了統(tǒng)一表示,將編碼符號(hào)中的前i個(gè)用來(lái)表示系統(tǒng)符號(hào)。

同時(shí),也可以利用矩陣的形式表示其編碼過(guò)程,則RFC系統(tǒng)形式的生成矩陣可以表示為G=[Ik|P],其中Ik是k階的單位矩陣。生成矩陣如圖2所示。

在圖2中,生成矩陣的每一列表示一個(gè)編碼符號(hào),單位矩陣Ik反映編碼符號(hào)中的系統(tǒng)符號(hào)部分,P對(duì)應(yīng)的是其中的校驗(yàn)符號(hào)。生成矩陣的具體生成過(guò)程如下:

步驟 1首先生成一個(gè)k×n的矩陣G,其中包括兩個(gè)子矩陣,即k×k方法的單位矩陣Ik和k×(n-k)方法的全零矩陣;

步驟 2根據(jù)前面生成校驗(yàn)符號(hào)vj的過(guò)程,記錄選取的d(k)個(gè)信息符號(hào)的序號(hào)以及對(duì)應(yīng)的系數(shù);

步驟 3對(duì)矩陣G中的全零子矩陣進(jìn)行操作,將其第j列中d(k)個(gè)序號(hào)對(duì)應(yīng)行的零元素替換成相應(yīng)的系數(shù),其中j=k+1,k+2,…,n;

步驟 4重復(fù)步驟2和步驟3,直到矩陣G中的n列全部生成完畢。

從圖3中可以看出,每一個(gè)校驗(yàn)符號(hào)最多由d(k)個(gè)信息符號(hào)加權(quán)組合而成。因此,一個(gè)校驗(yàn)符號(hào)和對(duì)應(yīng)的d(k)個(gè)信息符號(hào)組成一個(gè)局部組。表示在局部組中修復(fù)單個(gè)故障節(jié)點(diǎn)只需要訪問(wèn)本組中d(k)個(gè)剩余符號(hào)即可。另外,根據(jù)編碼規(guī)則可知,每個(gè)信息符號(hào)都有多個(gè)不相交的局部組,這使得系統(tǒng)符號(hào)的修復(fù)可以通過(guò)訪問(wèn)其中任意一個(gè)不相交的局部組來(lái)實(shí)現(xiàn)。

1.2 稀疏矩陣壓縮存儲(chǔ)

對(duì)于稀疏矩陣,非零元素很少且隨機(jī)出現(xiàn)。在許多實(shí)際應(yīng)用中,稀疏矩陣中零元素的存儲(chǔ)和計(jì)算是沒(méi)有意義的。為此,提出了稀疏矩陣壓縮技術(shù)來(lái)解決這一問(wèn)題。該技術(shù)對(duì)矩陣的行/列中的非零元素進(jìn)行運(yùn)算,避免了由零元素引起的不必要的運(yùn)算成本。對(duì)稀疏矩陣的列進(jìn)行操作時(shí),即壓縮列存儲(chǔ)(compressed column storage, CCS),提取矩陣中所有非零元素,并按列行順序存儲(chǔ)在一維數(shù)組中。同時(shí),提取每個(gè)非零元素對(duì)應(yīng)的行位置并保存到另一個(gè)一維數(shù)組中。因此,還有一種壓縮行存儲(chǔ)(compressed row storage, CRS)算法,該算法對(duì)矩陣的行進(jìn)行操作。從可修復(fù)噴泉碼的生成矩陣G來(lái)看,每一列相當(dāng)于一個(gè)傳輸?shù)臄?shù)據(jù)包。因此,為了保持可修復(fù)噴泉碼的性能,提出了一種基于改進(jìn)壓縮列存儲(chǔ)算法的可修復(fù)噴泉碼結(jié)構(gòu)來(lái)實(shí)現(xiàn)數(shù)據(jù)壓縮。

1.3 相關(guān)參數(shù)定義

為了更全面地分析所提出的方案,本文給出了幾個(gè)定義。

定義 1壓縮比(η):表示壓縮后的數(shù)據(jù)量與壓縮前的數(shù)據(jù)量的比值;

定義 2單節(jié)點(diǎn)修復(fù)有效吞吐量(γrepair):表示修復(fù)單個(gè)故障節(jié)點(diǎn)所需傳輸?shù)臄?shù)據(jù)量;

定義 3成功解碼有效吞吐量(γdecoded):表示成功解碼源文件所需傳輸?shù)臄?shù)據(jù)量。

2 新型RFC的構(gòu)造設(shè)計(jì)

為了進(jìn)一步降低分布式存儲(chǔ)系統(tǒng)的帶寬和存儲(chǔ)資源開銷,本節(jié)提出了基于改進(jìn)壓縮列存儲(chǔ)算法的新型RFC (RFC based on improved compressed column storage, ICCS-RFC)的構(gòu)造方法,該方案通過(guò)壓縮編碼符號(hào)所攜帶的鄰居信息來(lái)進(jìn)一步減少傳輸?shù)臄?shù)據(jù)量。改進(jìn)壓縮列存儲(chǔ)算法的思想源于壓縮列存儲(chǔ)算法與碼本壓縮算法的結(jié)合,后者通過(guò)利用M個(gè)二進(jìn)制位來(lái)表示非零元素的位置來(lái)實(shí)現(xiàn)。

根據(jù)RFC生成矩陣的特點(diǎn)和改進(jìn)壓縮列存儲(chǔ)算法的原理,提出的方案應(yīng)遵循以下幾個(gè)原則:

(1) 生成矩陣的稀疏性原則。該方案將提取生成矩陣中少數(shù)非零元素的值和位置作為有用信息,并將其視作提出方案的信息源進(jìn)行編碼操作。

(2) 編碼符號(hào)的獨(dú)立性原則。在ICCS-RFC方案的編碼過(guò)程當(dāng)中,每個(gè)編碼符號(hào)的生成是相互獨(dú)立的。因此,壓縮操作應(yīng)該圍繞每個(gè)編碼符號(hào)完成,即在生成矩陣的列上執(zhí)行,以保持可修復(fù)噴泉碼的特性。

(3) 最大度值原則。為了達(dá)到壓縮的目的,存在一個(gè)最大的度值來(lái)保證存儲(chǔ)信道上傳輸?shù)泥従有畔⒌娜哂喽茸钚　?/p>

2.1 壓縮模型的構(gòu)造

首先,建立一個(gè)壓縮模型來(lái)提取生成矩陣G的非零數(shù)據(jù)。如圖3所示,描述了n=10,k=8,d=2時(shí)，可修復(fù)噴泉碼用于壓縮模型的鄰域信息提取的示例。

根據(jù)壓縮模型可知,生成矩陣G中的非零元素被提取出來(lái)后存儲(chǔ)在一維陣列Val中,元素對(duì)應(yīng)的位置被存儲(chǔ)在另一個(gè)一維陣列Row中。完成生成矩陣G的非零元素提取操作后,利用碼本壓縮技術(shù),對(duì)提取出來(lái)的信息進(jìn)行編碼。令Lj,j=1,2,…,n表示非零元素的數(shù)量,Dmax表示非零元素?cái)?shù)目的最大值,稱為最大度值。利用M二進(jìn)制比特表示提取的鄰域信息。根據(jù)最大度值原則,可以得到定理1如下。

證畢

2.2 ICCS-RFC方案的編碼過(guò)程

根據(jù)上述壓縮模型的設(shè)計(jì)方案,ICCS-RFC方案的編碼過(guò)程可以描述如下。

步驟 1k個(gè)信息符號(hào)U=(u1,u2,…,uk)通過(guò)(n,k)可修復(fù)噴泉碼編碼成n個(gè)編碼符號(hào)V=(v1,v2,…,vn),根據(jù)第1.1節(jié)給出的生成矩陣的生成過(guò)程,得到生成矩陣G。然后計(jì)算出最大度值Dmax,并與生成矩陣當(dāng)中的度值d(k)比較,若d(k)

步驟 2利用改進(jìn)的壓縮列存儲(chǔ)算法對(duì)步驟1中提取的鄰域信息進(jìn)行壓縮處理,然后用壓縮之后的鄰域信息序列替換原來(lái)的鄰域信息序列,并將其與對(duì)應(yīng)的編碼符號(hào)進(jìn)行組合傳輸;

步驟 3重復(fù)上面的步驟,直到完成n個(gè)編碼符號(hào)的傳輸。

2.3 有效吞吐量的分析

令源文件的大小為F比特,將源文件等分成k份,則每一份信息包的大小為α=F/k。不失一般性,假設(shè)每個(gè)存儲(chǔ)節(jié)點(diǎn)所存儲(chǔ)的數(shù)據(jù)包數(shù)量為α。為了全面分析有效吞吐量,考慮兩個(gè)場(chǎng)景:單故障節(jié)點(diǎn)修復(fù)和源文件下載。

2.3.1 單故障節(jié)點(diǎn)修復(fù)場(chǎng)景

從第1.1節(jié)可知,一個(gè)校驗(yàn)符號(hào)及其對(duì)應(yīng)的消息符號(hào)組成一個(gè)局部組。因此,當(dāng)出現(xiàn)單節(jié)點(diǎn)故障時(shí),通常在對(duì)應(yīng)的局部組中進(jìn)行節(jié)點(diǎn)修復(fù),即通過(guò)訪問(wèn)局部組中余下的節(jié)點(diǎn)來(lái)實(shí)現(xiàn)故障節(jié)點(diǎn)修復(fù)。因此,可以計(jì)算修復(fù)單個(gè)故障節(jié)點(diǎn)的有效吞吐量。需要注意的是,因?yàn)榫植拷M包含的節(jié)點(diǎn)包括消息節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn),所以需要分別考慮,具體計(jì)算結(jié)果如下所示。

對(duì)于提出的ICCS-RFC編碼方案：

(2)

對(duì)于RFC編碼方案：

(3)

式中:d(k)表示修復(fù)局部。從式(2)和式(3)可以知道,當(dāng)一個(gè)系統(tǒng)符號(hào)丟失時(shí),需要在局部組中訪問(wèn)d(k)-1個(gè)系統(tǒng)符號(hào)以及一個(gè)校驗(yàn)符號(hào)進(jìn)行丟失數(shù)據(jù)的重建。當(dāng)一個(gè)校驗(yàn)符號(hào)丟失時(shí),需要鏈接局部組內(nèi)d(k)個(gè)系統(tǒng)符號(hào)進(jìn)行丟失數(shù)據(jù)的重建。因此,必需的數(shù)據(jù)包傳輸量和對(duì)應(yīng)的鄰域信息量相加,即可得到有效吞吐量。

2.3.2 源文件下載場(chǎng)景

為了實(shí)現(xiàn)高概率的成功解碼,需要下載一組(1+ε)k編碼符號(hào),其中ε>0。因此,成功解碼所需的有效吞吐量可計(jì)算如下。

對(duì)于提出的ICCS-RFC編碼方案:

(4)

式中:d1表示接收到的度值為1的編碼符號(hào)數(shù)量。因此,在接收到的編碼符號(hào)中度值為d(k)的數(shù)量為((1+ε)k-d1)。

對(duì)于RFC編碼方案:

(5)

式中:(1+ε)kk表示接收數(shù)據(jù)包的鄰域信息的數(shù)量;α(1+ε)k表示接收數(shù)據(jù)包的數(shù)量。

3 系統(tǒng)仿真與結(jié)果分析

本文仿真平臺(tái)是Win10系統(tǒng),CPU為2.50 GHz,內(nèi)存是8 GB,采用Matlab 2014a軟件仿真。

在這一部分中,通過(guò)實(shí)驗(yàn)結(jié)果分析了ICCS-RFC方案的性能,并在有效吞吐量方面與文獻(xiàn)[9]中的傳統(tǒng)RFC方案進(jìn)行了比較。具體計(jì)算了不同消息符號(hào)長(zhǎng)度k下改進(jìn)的壓縮列存儲(chǔ)算法實(shí)現(xiàn)前后的數(shù)據(jù)傳輸量,數(shù)值結(jié)果如表1所示。

表1 ICCS-RFC編碼方案的結(jié)果

對(duì)于表1,度數(shù)d(k)=Clg(k),設(shè)置C=1。第2列表示在實(shí)現(xiàn)ICCS算法之前需要傳輸?shù)泥従有畔⒘?第3列表示ICCS算法實(shí)現(xiàn)后需要傳輸?shù)泥従有畔⒘俊?/p>

在表1中,隨著消息長(zhǎng)度k的增加,兩種方案的鄰居信息量都急劇增加。從實(shí)驗(yàn)結(jié)果可以看出,在實(shí)現(xiàn)ICCS算法之前,要實(shí)現(xiàn)高概率的成功解碼,鄰域信息量是巨大的。經(jīng)過(guò)ICCS算法壓縮后,鄰域信息量明顯減少。當(dāng)k=700時(shí),壓縮比降低到0.1以下,這意味著鄰域信息量被壓縮了90%。而且,可以看到,k值越大,壓縮比的降低越小。因此,該方案可以顯著減少傳輸數(shù)據(jù)量,節(jié)省帶寬資源。

從圖4(a)可以看出,對(duì)于不同的消息長(zhǎng)度k,ICCS-RFC方案在修復(fù)單個(gè)故障節(jié)點(diǎn)時(shí)有著更小的有效吞吐量,比如,當(dāng)k=2 000時(shí),RFC方案的有效吞吐量為4.406×104,ICCS-RFC方案的有效吞吐量?jī)H為250左右。另外,在圖4(b)中,可以看到,在源文件下載過(guò)程中,ICCS-RFC方案的壓縮效果也非常顯著。當(dāng)k=2 000時(shí),ICCS-RFC方案的有效吞吐量為1.826×105,與RFC方案的4.401×106相比,需要傳輸?shù)臄?shù)據(jù)量明顯減少。因此,本文提出的方案在進(jìn)一步降低帶寬資源開銷方面具有明顯優(yōu)勢(shì),特別是在單故障節(jié)點(diǎn)修復(fù)的場(chǎng)景下。

在圖5中可以看到,在兩種場(chǎng)景中,隨著消息長(zhǎng)度k的增長(zhǎng),壓縮比也是隨之降低,但降低的速率逐漸減小。尤其在單故障節(jié)點(diǎn)修復(fù)場(chǎng)景中,當(dāng)k>1 000時(shí),ICCS-RFC編碼方案將壓縮比下降到了10-3個(gè)數(shù)量級(jí)。所以,可以看出,ICCS-RFC方案能夠明顯降低存儲(chǔ)信道的傳輸冗余,尤其是在單故障節(jié)點(diǎn)修復(fù)場(chǎng)景中。

在圖6中,基于熵編碼的LT碼相關(guān)參數(shù)設(shè)為(c=0.1,δ=0.01),隨著消息長(zhǎng)度k的增加,這兩種方案的壓縮比都下降。當(dāng)ICCS-RFC方案中度值包含的常數(shù)C=2時(shí),該方案的壓縮比大于基于熵編碼的LT碼。當(dāng)該參數(shù)C取1和0.7時(shí),該方案的壓縮比則要低于基于熵編碼的LT碼。綜上所述,參數(shù)C在ICCS-RFC方案中起著重要作用。因此,選擇合適的C值是保證方案性能的關(guān)鍵。

4 結(jié) 論

本文提出了一種基于ICCS算法的新型可修復(fù)噴泉碼結(jié)構(gòu)。理論分析和仿真結(jié)果表明,該方案能顯著降低帶寬資源開銷,尤其是在修復(fù)單個(gè)故障節(jié)點(diǎn)時(shí)。與傳統(tǒng)可修復(fù)噴泉碼方案相比,提出的ICCS-RFC方案在節(jié)省帶寬資源方面具有更好的性能。未來(lái),我們將重點(diǎn)研究ICCS-RFC方案在異構(gòu)分布式存儲(chǔ)系統(tǒng)中的應(yīng)用,以達(dá)到信息保護(hù)和通信成本節(jié)約的目的。