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

周安安, 易本順, 劉羽升, 羅來干

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

0 引 言

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

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

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

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

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

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

1 RFC及矩陣壓縮存儲模型

1.1 RFC的構(gòu)造

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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

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

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

1.2 稀疏矩陣壓縮存儲

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

證畢

2.2 ICCS-RFC方案的編碼過程

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

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

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

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

2.3 有效吞吐量的分析

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

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

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

對于提出的ICCS-RFC編碼方案：

(2)

對于RFC編碼方案：

(3)

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

2.3.2 源文件下載場景

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

對于提出的ICCS-RFC編碼方案:

(4)

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

對于RFC編碼方案:

(5)

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

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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