国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

分布式存儲(chǔ)系統(tǒng)中的低修復(fù)成本糾刪碼

2020-10-18 12:57:36劉善政蔡紅亮
計(jì)算機(jī)應(yīng)用 2020年10期
關(guān)鍵詞:存儲(chǔ)系統(tǒng)原始數(shù)據(jù)解碼

張 航,劉善政,唐 聃,蔡紅亮

(成都信息工程大學(xué)軟件工程學(xué)院,成都 610225)

(*通信作者電子郵箱tangdan@foxmail.com)

0 引言

隨著信息技術(shù)的發(fā)展,人們產(chǎn)生的數(shù)據(jù)越來(lái)越多,各企業(yè)為了滿足人們的數(shù)據(jù)需求,紛紛搭建企業(yè)自己的數(shù)據(jù)中心并使用分布式存儲(chǔ)系統(tǒng)來(lái)存儲(chǔ)海量數(shù)據(jù)。據(jù)英特爾預(yù)測(cè),全球數(shù)據(jù)總量在2020 年將達(dá)到44 ZB(1 ZB=109TB),而中國(guó)產(chǎn)生的數(shù)據(jù)量將達(dá)到8 ZB,大約占據(jù)全球總數(shù)據(jù)量的1/5[1]。在商業(yè)存儲(chǔ)領(lǐng)域,數(shù)據(jù)增長(zhǎng)極大地推動(dòng)了分布式存儲(chǔ)系統(tǒng)的發(fā)展。為了保障分布式存儲(chǔ)系統(tǒng)海量數(shù)據(jù)的安全性和可靠性,常采用多副本[2]和糾刪碼[3]等容錯(cuò)技術(shù)。

多副本技術(shù)是將原始數(shù)據(jù)復(fù)制多份,并分別存儲(chǔ)在不同的存儲(chǔ)節(jié)點(diǎn)上。Hadoop 分布式文件系統(tǒng)(Hadoop Distributed File System,HDFS)[4]以及Ceph 分布式存儲(chǔ)[5]系統(tǒng)均采用了多副本中常見的三副本。多副本技術(shù)操作簡(jiǎn)單,易于實(shí)施,但是該方法存儲(chǔ)效率低。以常見的三副本為例,該方法將原始數(shù)據(jù)復(fù)制成三份,保存在三個(gè)不同的存儲(chǔ)節(jié)點(diǎn)上,磁盤存儲(chǔ)利用率僅有1/3,同時(shí)數(shù)據(jù)中心構(gòu)建成本高,存儲(chǔ)成本過(guò)大,造成嚴(yán)重的資源浪費(fèi)。

糾刪碼容錯(cuò)技術(shù)是一種數(shù)據(jù)保護(hù)方法,它將數(shù)據(jù)分割成片段,利用編碼算法生成冗余數(shù)據(jù)塊存儲(chǔ)在不同的位置,比如磁盤、存儲(chǔ)節(jié)點(diǎn)上。糾刪碼技術(shù)相比多副本技術(shù)能以更低的存儲(chǔ)開銷存儲(chǔ)更多的數(shù)據(jù),Hadoop3.0 以及Ceph 分布式存儲(chǔ)系統(tǒng)均采用了糾刪碼技術(shù)作為系統(tǒng)容錯(cuò)技術(shù)之一,同時(shí)微軟的存儲(chǔ)系統(tǒng)、亞馬遜的AWS(Amazon Web Services)[6]等也都支持糾刪碼技術(shù)作為容錯(cuò)技術(shù)。

然而,糾刪碼過(guò)高的修復(fù)成本極大地限制了其技術(shù)在分布式存儲(chǔ)系統(tǒng)中的實(shí)用性。糾刪碼在修復(fù)失效的數(shù)據(jù)塊時(shí),需要在多個(gè)節(jié)點(diǎn)讀取數(shù)據(jù)并傳輸,會(huì)占用大量的網(wǎng)絡(luò)帶寬。眾所周知,帶寬資源一直是分布式存儲(chǔ)系統(tǒng)中的稀缺資源。占用較高的網(wǎng)絡(luò)帶寬,會(huì)降低分布式存儲(chǔ)系統(tǒng)的數(shù)據(jù)讀取速度,從而影響到整個(gè)系統(tǒng)的穩(wěn)定性。

糾刪碼的修復(fù)成本主要由其自己的特性決定,設(shè)計(jì)糾刪碼的編碼結(jié)構(gòu)能從根本上降低修復(fù)成本[7]。目前,根據(jù)編碼結(jié)構(gòu)的不同,關(guān)于低修復(fù)成本的糾刪碼的主要分為兩類:分組碼和再生碼。分組碼是將一個(gè)條帶的數(shù)據(jù)塊進(jìn)行分組,利用組內(nèi)的原始數(shù)據(jù)塊生成局部冗余塊,在原始數(shù)據(jù)塊失效時(shí),利用組內(nèi)的局部冗余塊來(lái)恢復(fù)數(shù)據(jù)塊,能有效降低數(shù)據(jù)修復(fù)時(shí)需要的修復(fù)成本;再生碼是通過(guò)適當(dāng)增加冗余并且使新生節(jié)點(diǎn)從盡量多的節(jié)點(diǎn)下載數(shù)據(jù)塊來(lái)降低修復(fù)時(shí)需要傳輸?shù)臄?shù)據(jù)量[8]。

Huang 等[9-10]提出了LRC(Locally Repairable Codes)、Pyramid 等典型的層次分組碼。LRC 和Pyramid 碼都是通過(guò)增加局部冗余的方式來(lái)降低數(shù)據(jù)塊修復(fù)成本,但它們的修復(fù)成本依然過(guò)高。Facebook 采用了針對(duì)LRC 和Pyramid 上作出改進(jìn)的LRCs[11]和EXPyramid[12]層次分組碼。LRCs 主要針對(duì)全局冗余塊再編碼了一個(gè)局部冗余塊,能降低全局冗余塊的修復(fù)成本;EXPyramid 碼是將Pyramid 碼的編碼數(shù)據(jù)塊改為陣列結(jié)構(gòu),同時(shí)在橫向和縱向兩個(gè)方向編碼局部冗余塊,進(jìn)一步降低了數(shù)據(jù)塊的修復(fù)成本。林軒等[13]繼續(xù)在LRC、Pyramid 的基礎(chǔ)上提出了GRC(Group Repairable Codes)層次分組碼,GRC不僅將條帶進(jìn)行分組生成局部冗余塊,而且同時(shí)為編碼條帶生成局部冗余塊,在數(shù)據(jù)塊失效時(shí),利用兩種局部冗余塊參與恢復(fù),不需要條帶中所有數(shù)據(jù)塊參與修復(fù),進(jìn)一步降低了修復(fù)成本。但這三種改進(jìn)方法都需要消耗大量的存儲(chǔ)空間,并不適用大規(guī)模的分布式存儲(chǔ)系統(tǒng)。Meng 等[14]提出了一種新的分組碼DLRC(Dynamic Local Reconstruction Code),通過(guò)利用參數(shù)動(dòng)態(tài)地調(diào)整存儲(chǔ)開銷和重構(gòu)開銷的平衡;但在滿足多節(jié)點(diǎn)容錯(cuò)的情況下,單節(jié)點(diǎn)修復(fù)成本過(guò)大。Miyamae 等[15]提出了交叉分組碼SHEC(Shingled Erasure Code)。SHEC 是將條帶上的數(shù)據(jù)塊邏輯上進(jìn)行重疊并分組,進(jìn)而編碼出局部冗余塊,在數(shù)據(jù)塊失效時(shí),利用較少的組進(jìn)行局部修復(fù),從而降低修復(fù)成本;但SHEC 重疊編碼難以維持較低的修復(fù)成本和較高的容錯(cuò)能力,依然不適用于現(xiàn)有分布式存儲(chǔ)系統(tǒng)。

再生碼的研究主要關(guān)注MBR(Minimun Bandwidth Rrgenerating)碼[16]和MSR(Minimun Storage Regenerating)碼[17]。MSR 碼主要擁有最低的存儲(chǔ)開銷,MBR 碼主要擁有最低的數(shù)據(jù)修復(fù)成本。在2011年,Rashmi等[18]首次利用矩陣乘的方法,用統(tǒng)一的方法構(gòu)造出MBR 碼和MSR 碼。Liu 等[19]提出了再生碼GFR(General Functional Regenerating),通過(guò)設(shè)定一個(gè)可自由調(diào)節(jié)的參數(shù)來(lái)實(shí)現(xiàn)分布式存儲(chǔ)系統(tǒng)的修復(fù)成本和存儲(chǔ)成本之間的平衡,同時(shí)使用一種啟發(fā)式算法來(lái)找到修復(fù)單節(jié)點(diǎn)失效數(shù)據(jù)的最小修復(fù)成本。Liu 等[20]同時(shí)提出了最小再生碼Z 碼,Z 碼把置換矩陣作為元矩陣,組合構(gòu)造出最優(yōu)修復(fù)成本的生成矩陣,同時(shí)利用矩陣的張量乘積,迭代出任意參數(shù)下的生成矩陣,并依然保持最優(yōu)修復(fù)成本。Xie等[21]提出了AZ-CODE(Availability Zones Codes),AZ-CODE 結(jié)合了MSR 碼和LRC的編碼方式,利用其混合優(yōu)點(diǎn),能有效降低修復(fù)成本。

再生碼雖然可以大幅度地減少修復(fù)時(shí)的數(shù)據(jù)傳輸量,但在數(shù)據(jù)修復(fù)過(guò)程中,參與修復(fù)的節(jié)點(diǎn)需要把自己存儲(chǔ)的所有數(shù)據(jù)都讀取出來(lái)進(jìn)行組合,會(huì)消耗大量的讀取成本。同時(shí),再生碼編碼復(fù)雜度高、編碼耗時(shí)長(zhǎng)等因素都不適用于現(xiàn)有的分布式存儲(chǔ)系統(tǒng)。

根據(jù)數(shù)據(jù)中心對(duì)分布式存儲(chǔ)系統(tǒng)故障的調(diào)查研究報(bào)告顯示,其中99.75%的故障來(lái)源于分布式存儲(chǔ)系統(tǒng)單節(jié)點(diǎn)失效[22]。因此針對(duì)現(xiàn)有的分布式存儲(chǔ)系統(tǒng)中頻繁的單節(jié)點(diǎn)失效且糾刪碼修復(fù)成本過(guò)高的問(wèn)題,提出了一種低修復(fù)成本糾刪碼——旋轉(zhuǎn)分組修復(fù)碼(Rotation Group Repairable Codes,RGRC),并驗(yàn)證了低成本修復(fù)性。RGRC 是將條帶組合成條帶集,對(duì)條帶集內(nèi)的數(shù)據(jù)塊進(jìn)行分層旋轉(zhuǎn)編碼來(lái)減少大容量單節(jié)點(diǎn)失效的修復(fù)帶寬。同時(shí)RGRC 在解決單節(jié)點(diǎn)修復(fù)成本高的問(wèn)題時(shí),依然保留著較高的容錯(cuò)能力,且為滿足分布式存儲(chǔ)系統(tǒng)的不同需求,可以靈活地權(quán)衡其存儲(chǔ)開銷和修復(fù)成本。

1 分布式存儲(chǔ)系統(tǒng)中糾刪碼的相關(guān)概念

分布式存儲(chǔ)系統(tǒng)使用糾刪碼作為容錯(cuò)技術(shù),能消耗更少的存儲(chǔ)空間,從而減少存儲(chǔ)硬件的使用,大幅降低存儲(chǔ)中心的構(gòu)建成本??梢?,糾刪碼空間利用率高的特點(diǎn)在存儲(chǔ)海量數(shù)據(jù)時(shí)具有重大意義。

糾刪碼技術(shù)主要是通過(guò)糾刪碼算法將原始的數(shù)據(jù)塊進(jìn)行編碼得到冗余塊,并將原始數(shù)據(jù)塊和冗余塊一并存儲(chǔ)起來(lái),以達(dá)到容錯(cuò)的目的。用(n,k)表示一個(gè)糾刪碼,K個(gè)原始數(shù)據(jù)塊D1,D2,…,DK經(jīng)過(guò)計(jì)算產(chǎn)生了n個(gè)塊P1,P2,…,Pn,這一過(guò)程稱為編碼。當(dāng)P1,P2,…,Pn中失效的塊小于該糾刪碼最大的容錯(cuò)個(gè)數(shù)時(shí),可以選取其中剩余的塊計(jì)算恢復(fù)出失效塊,這一過(guò)程稱為解碼。相關(guān)原理如圖1所示。

圖1 編碼、解碼示意圖Fig.1 Schematic diagram of encoding and decoding

為了便于理解,現(xiàn)結(jié)合圖2 給出如下一些糾刪碼常用的基本概念的說(shuō)明和定義:

1)極大距離可分(Maximum Distance Separable,MDS)碼:這一類碼在消耗相同存儲(chǔ)開銷的情況下,有最優(yōu)的容錯(cuò)能力,因此被分布式存儲(chǔ)系統(tǒng)廣泛使用。對(duì)于一個(gè)參數(shù)為(n,k)的MDS糾刪碼來(lái)講,容錯(cuò)能力為n-k。

2)系統(tǒng)性糾刪碼:數(shù)據(jù)塊經(jīng)過(guò)計(jì)算產(chǎn)生的塊中包含原始的數(shù)據(jù)塊,因良好的訪問(wèn)性能而成為分布式存儲(chǔ)系統(tǒng)的首選。

3)容錯(cuò)度:糾刪碼可以容忍的丟失數(shù)據(jù)塊個(gè)數(shù)。

4)原始數(shù)據(jù)塊:用戶上傳的原始數(shù)據(jù)對(duì)象被系統(tǒng)劃分后得到的塊。

5)冗余塊:數(shù)據(jù)塊經(jīng)過(guò)糾刪碼算法后產(chǎn)生的所有塊。

6)條帶:由多個(gè)數(shù)據(jù)塊和冗余塊組成,滿足同一糾刪碼算法。

7)條帶集:由多個(gè)條帶組成的集合。

圖2 數(shù)據(jù)塊、冗余塊、條帶和條帶集之間的相互關(guān)系Fig.2 Correlation between data blocks,redundant blocks,stripes and strip set

2 旋轉(zhuǎn)分組修復(fù)碼

2.1 糾刪碼數(shù)據(jù)修復(fù)問(wèn)題定義

為了便于理解,基于文獻(xiàn)給出糾刪碼數(shù)據(jù)修復(fù)問(wèn)題相關(guān)的定義。

定義1糾刪碼修復(fù)成本。糾刪碼在進(jìn)行數(shù)據(jù)修復(fù)過(guò)程中需要讀取的數(shù)據(jù)量。在分布式存儲(chǔ)系統(tǒng)中,網(wǎng)絡(luò)帶寬資源一直是稀缺資源,在修復(fù)的過(guò)程中讀取的數(shù)據(jù)量越小,傳輸?shù)臄?shù)據(jù)量就小,占用的網(wǎng)絡(luò)帶寬的資源就越少,從而避免了修復(fù)過(guò)程對(duì)分布式存儲(chǔ)系統(tǒng)中其他任務(wù)的影響,提升了系統(tǒng)的穩(wěn)定性。

定義2糾刪碼的修復(fù)時(shí)間。糾刪碼在進(jìn)行數(shù)據(jù)修復(fù)時(shí)所消耗的時(shí)長(zhǎng)。分布式存儲(chǔ)系統(tǒng)中,修復(fù)的快慢直接影響到系統(tǒng)的穩(wěn)定性,如果在數(shù)據(jù)量龐大的存儲(chǔ)系統(tǒng)中,一旦不能快速恢復(fù)數(shù)據(jù),有可能導(dǎo)致在修復(fù)過(guò)程中因其他任務(wù)的影響而使其余數(shù)據(jù)塊再次失效,因此,對(duì)于分布式存儲(chǔ)系統(tǒng)中的糾刪碼來(lái)說(shuō),修復(fù)時(shí)間應(yīng)該越小越好。

定義3糾刪碼的修復(fù)率。修復(fù)率是糾刪碼重要的指標(biāo)之一。不同失效節(jié)點(diǎn)數(shù)時(shí)的修復(fù)率側(cè)面反映出了該糾刪碼的容錯(cuò)能力。

定義4全局冗余塊。條帶中所有原始數(shù)據(jù)塊參與編碼計(jì)算得到的冗余塊。

定義5局部冗余塊。條帶中組內(nèi)原始數(shù)據(jù)塊參與編碼計(jì)算得到的冗余塊。

表1為常用符號(hào)說(shuō)明。

表1 常用符號(hào)Tab.1 Common symbols

2.2 編碼算法

本文提出的RGRC是在系統(tǒng)型MDS碼上作出改進(jìn)的一種分組糾刪碼,所以本節(jié)先介紹系統(tǒng)型MDS 碼的編碼過(guò)程,然后介紹RGRC的編碼過(guò)程,最后舉例演示RGRC的編碼過(guò)程。

系統(tǒng)型MDS 碼的編碼過(guò)程為:首先在有限域上構(gòu)造編碼矩陣,編碼矩陣與原始數(shù)據(jù)塊在有限域中執(zhí)行乘法運(yùn)算得到編碼塊。

如編碼公式(1)所示,D1,D2,…,DK總共K個(gè)原始數(shù)據(jù)塊與編碼矩陣相乘,計(jì)算產(chǎn)生了C1,C2,…,Cn,共n個(gè)塊,其中產(chǎn)生的n個(gè)塊中包含了k個(gè)原始數(shù)據(jù)塊。

RGRC的編碼過(guò)程如下:

步驟1 根據(jù)系統(tǒng)性MDS 碼的編碼方式,生成m個(gè)全局冗余塊表示成P1,P2,…,Pm,記為Pi(i=1,2,…,m)。數(shù)據(jù)條帶分為L(zhǎng)個(gè)小組,記為L(zhǎng)i(i=1,2,…,l;0 <l<k),每個(gè)小組包含k0個(gè)原始數(shù)據(jù)塊。保持糾刪碼前m0個(gè)全局冗余塊不變,為每個(gè)小組計(jì)算ml=m-m0個(gè)組內(nèi)局部冗余塊(其中m1≥3),假設(shè)每個(gè)組內(nèi)前m1-2 個(gè)局部冗余塊稱為R,小組Li的組內(nèi)局部冗余塊Ri(i=1,2,…,ml-2)的計(jì)算方法和Pi一樣,只是將其他數(shù)據(jù)塊置0。

步驟2 多個(gè)條帶組合成條帶集,形成每個(gè)條帶集包含S個(gè)條帶,每個(gè)條帶包含L個(gè)小組的結(jié)構(gòu)。小組Li的倒數(shù)第二個(gè)組內(nèi)局部冗余塊稱為前段冗余塊(Rotation Front block,RF),最后一個(gè)組內(nèi)局部冗余塊稱為后段冗余塊(Rotation Back block,RB),RF 通過(guò)前段數(shù)據(jù)旋轉(zhuǎn)編碼方式得到,RB 的通過(guò)后段數(shù)據(jù)旋轉(zhuǎn)編碼得到。相應(yīng)的編碼結(jié)構(gòu)如圖3所示。

圖3 RF、RB示意圖Fig.3 Schematic diagram of RF and RB

步驟3Li小組內(nèi)包含k0個(gè)原始數(shù)據(jù)塊,設(shè)前t個(gè)原始數(shù)據(jù)塊為前段數(shù)據(jù)塊,其中0 <t<k0,則t1=k0-t個(gè)原始數(shù)據(jù)塊為后段數(shù)據(jù)塊。前段數(shù)據(jù)旋轉(zhuǎn)編碼方式以條帶集為編碼單位。取每個(gè)小組前t個(gè)原始數(shù)據(jù)塊,加上前一個(gè)條帶內(nèi)同一位置小組內(nèi)的后段數(shù)據(jù)塊組合成新的數(shù)據(jù)塊集合,用新的數(shù)據(jù)塊集合參與編碼計(jì)算,計(jì)算方法和Pi一樣,只是將其他數(shù)據(jù)塊置0。后段數(shù)據(jù)旋轉(zhuǎn)編碼方式與前段數(shù)據(jù)旋轉(zhuǎn)編碼類似,只不過(guò)新的數(shù)據(jù)塊集合由該小組的后段數(shù)據(jù)塊加上前一個(gè)條帶內(nèi)同一位置小組內(nèi)的前段數(shù)據(jù)塊組成。

所有類型的冗余塊編碼公式如下。

1)全局冗余塊生成公式:

2)組內(nèi)局部冗余塊生成公式:

設(shè)條帶集包含S個(gè)條帶,RFs,l表示條帶集中第s條帶中第l小組的前段冗余塊,RBs,l表示條帶集中第s條帶中第l小組的后段冗余塊。

3)前段、后段冗余塊生成公式如下:

下面從(14,10)的MDS碼出發(fā),構(gòu)造(18,10)RGRC演示編碼過(guò)程。圖4 展示的(14,10)的編碼結(jié)構(gòu),D1,D2,…,D10為10個(gè)原始數(shù)據(jù)塊,P1,P2,…,P4為經(jīng)過(guò)編碼計(jì)算后產(chǎn)生的4個(gè)全局冗余塊。

圖4 (14,10)MDS碼的編碼結(jié)構(gòu)Fig.4 Encoding structure of(14,10)MDS code

如圖5所示,將MDS碼的10個(gè)原始數(shù)據(jù)塊分成2個(gè)小組,每個(gè)小組包含5 個(gè)原始數(shù)據(jù)塊,其中L1={D1,D2,D3,D4,D5}L2={D6,D7,D8,D9,D10},保持1 個(gè)全局冗余塊不變,則每個(gè)小組產(chǎn)生的組內(nèi)局部冗余塊個(gè)數(shù)為3。L1組的局部冗余塊為{P21,P31,P41},L2組的局部冗余塊為{P22,P32,P42}。

圖5 條帶分組后局部冗余塊的編碼Fig.5 Encoding of local redundant blocks after strip grouping

如圖6 所示,將4 個(gè)條帶組合成條帶集,以第一個(gè)小組為例。設(shè)t=2,則D1、D2列為前段數(shù)據(jù)塊列,D3、D4、D5列為后段數(shù)據(jù)塊列。P31列為前段冗余塊列。按照RFs,l生成公式構(gòu)造出如圖6的前段冗余塊。

圖6 前段旋轉(zhuǎn)編碼結(jié)構(gòu)Fig.6 Anterior rotary coding structure

如圖7 所示,P41為后段冗余塊列。按照RBs,l生成公式構(gòu)造出如圖7的后段冗余塊。

圖7 后段旋轉(zhuǎn)編碼結(jié)構(gòu)Fig.7 Posterior rotary coding structure

相較于MDS 碼,RGRC 先通過(guò)對(duì)數(shù)據(jù)條帶進(jìn)行分組產(chǎn)生組內(nèi)局部冗余塊,組合條帶構(gòu)成條帶集進(jìn)行旋轉(zhuǎn)編碼,這種設(shè)計(jì)可以保障在單節(jié)點(diǎn)失效時(shí)快速在組內(nèi)恢復(fù),同時(shí)以條帶集為單位進(jìn)行恢復(fù),大幅減少修復(fù)需要讀取的數(shù)據(jù)量,從而降低修復(fù)時(shí)的修復(fù)成本和數(shù)據(jù)傳輸量。

2.3 解碼算法

RGRC 的解碼過(guò)程大致為:利用現(xiàn)有數(shù)據(jù)組合出對(duì)應(yīng)的剩余編碼矩陣的逆矩陣與剩余活躍的塊在有限域中進(jìn)行乘法運(yùn)算,從而求得丟失的數(shù)據(jù)塊。

在進(jìn)行解碼時(shí),單節(jié)點(diǎn)失效雖然在節(jié)點(diǎn)故障中占比大,但是多節(jié)點(diǎn)失效在分布式存儲(chǔ)系統(tǒng)中并不少見,因此,本文針對(duì)RGRC的解碼分為單節(jié)點(diǎn)解碼和多節(jié)點(diǎn)解碼。

2.3.1 單節(jié)點(diǎn)解碼步驟

當(dāng)失效節(jié)點(diǎn)為單節(jié)點(diǎn)時(shí),以條帶集為單位進(jìn)行解碼。假設(shè)失效單節(jié)點(diǎn)在Li組,且S為偶數(shù)時(shí),解碼過(guò)程按如下步驟進(jìn)行解碼:

步驟1 條帶集以2 個(gè)條帶進(jìn)行集合劃分Ai={Sq,Sp},(其中i=1,2,…,S/2),Sq、Sp為旋轉(zhuǎn)編碼相關(guān)聯(lián)的兩個(gè)條帶。

步驟2 當(dāng)失效節(jié)點(diǎn)在前段數(shù)據(jù)塊列時(shí),恢復(fù)Sq條帶中的失效數(shù)據(jù)塊時(shí),讀取Sq條帶中Li組的前k0個(gè)未失效的原始數(shù)據(jù)塊和局部冗余塊組成新的塊集合,并保存在緩存中?;謴?fù)Sp條帶中的失效數(shù)據(jù)塊時(shí),讀取Sp條帶中Li組的未失效的前段數(shù)據(jù)塊,前段旋轉(zhuǎn)編碼產(chǎn)生的RF塊和緩存中需用到的塊組成新的塊集合。新的塊集合和對(duì)應(yīng)的剩余編碼矩陣的逆矩陣相乘來(lái)恢復(fù)2 個(gè)條帶中的失效數(shù)據(jù)塊。照此方法循環(huán)迭代,恢復(fù)條帶集中所有的失效數(shù)據(jù)塊,并進(jìn)一步恢復(fù)整個(gè)節(jié)點(diǎn)失效的數(shù)據(jù)塊。

步驟3 當(dāng)失效節(jié)點(diǎn)在后段數(shù)據(jù)塊列時(shí),恢復(fù)Sq條帶中的失效數(shù)據(jù)塊,讀取Sq條帶中Li組的前k0個(gè)未失效的原始數(shù)據(jù)塊和局部冗余塊組成新的數(shù)據(jù)塊集合,并保存在緩存中?;謴?fù)Sp條帶中的失效數(shù)據(jù)塊時(shí),讀取Sp條帶中Li組的未失效的后段數(shù)據(jù)塊,后段旋轉(zhuǎn)編碼產(chǎn)生的RB塊和緩存中需用到的塊組成新的塊集合。

新的塊集合和對(duì)應(yīng)的剩余編碼矩陣的逆矩陣相乘來(lái)恢復(fù)2 個(gè)條帶中的失效數(shù)據(jù)塊。照此方法循環(huán)迭代,恢復(fù)條帶集中所有的失效數(shù)據(jù)塊,并進(jìn)一步恢復(fù)整個(gè)節(jié)點(diǎn)失效的數(shù)據(jù)塊。

假設(shè)失效單節(jié)點(diǎn)在Li組,且S為奇數(shù)時(shí),解碼過(guò)程按如下步驟進(jìn)行解碼:

步驟1 條帶集以2 個(gè)條帶進(jìn)行集合劃分Ai={Sq,Sp}(其中i=1,2,…,(S-1)/2),B={SS},Sq、Sp為旋轉(zhuǎn)編碼相關(guān)聯(lián)的兩個(gè)條帶,SS為條帶集中最后一個(gè)條帶。

步驟2 恢復(fù)Ai集合與S為偶數(shù)時(shí)一樣?;謴?fù)B集合中的失效數(shù)據(jù)塊時(shí),讀取SS條帶中Li組的前k0個(gè)未失效的原始數(shù)據(jù)塊和局部冗余塊組成新的塊集合,新的塊集合和對(duì)應(yīng)的剩余編碼矩陣的逆矩陣相乘來(lái)恢復(fù)失效數(shù)據(jù)塊。

下面以(18,10),S=4 的RGRC 在L1組單節(jié)點(diǎn)失效為例,演示其解碼過(guò)程。圖8 中陰影表示數(shù)據(jù)塊失效。條帶集以2個(gè)條帶進(jìn)行集合劃分A1={S1,S2},A2={S3,S4}。在A1中恢復(fù)第1 條帶的D1塊,需讀取第1 個(gè)條帶的(D2,D3,D4,D5,P21)5 個(gè)塊;恢復(fù)第2 條帶的D1塊,需讀取第2 個(gè)條帶的D2和第一條帶的P31共計(jì)兩個(gè)塊。A2集合恢復(fù)失效塊方法和A1一樣。相較于(14,10)的MDS 碼恢復(fù)4 個(gè)條帶的D1列失效需讀取40塊,RGRC 只需讀取14 塊數(shù)據(jù),比MDS 碼相比修復(fù)成本降低65%。

圖8 單節(jié)點(diǎn)失效解碼Fig.8 Decoding of single-node failure

2.3.2 多節(jié)點(diǎn)解碼步驟

RGRC 與MDS 碼有所區(qū)別,并不滿足當(dāng)失效塊個(gè)數(shù)大于n-k則不能恢復(fù),而是某些情況下當(dāng)失效塊數(shù)大于n-k依然可以恢復(fù)。基于RGRC 的特征,本文提出了貪心策略的解碼算法,該解碼算法分為2 類解碼:條帶集組解碼、條帶集全局解碼。

條帶集組解碼是指利用和失效節(jié)點(diǎn)在同一小組內(nèi)的條帶集中未失效的塊來(lái)解碼恢復(fù)失效塊。由于條帶集中小組內(nèi)塊數(shù)較少,在恢復(fù)失效塊時(shí)需讀取的塊數(shù)較少,解碼成本能降到最低。當(dāng)條帶集組內(nèi)解碼無(wú)法恢復(fù)失效塊時(shí),使用條帶集全局解碼恢復(fù)失效塊。條帶集全局解碼利用條帶集內(nèi)全局未失效塊來(lái)恢復(fù)失效塊,為了降低讀取成本,當(dāng)利用條帶集全局解碼恢復(fù)出某些失效塊后,為可以滿足條帶集組解碼條件時(shí),條帶集全局解碼應(yīng)馬上轉(zhuǎn)換成條帶集組解碼進(jìn)行解碼。

根據(jù)以上原則,對(duì)多節(jié)點(diǎn)失效的貪心策略的解碼算法過(guò)程分為兩個(gè)階段:

1)條帶集組解碼。對(duì)于條帶集中每個(gè)小組,當(dāng)失效塊數(shù)小于局部冗余塊數(shù),則啟用條帶集組解碼恢復(fù)數(shù)據(jù),當(dāng)解碼成功后,標(biāo)記為活躍塊,可以參與下一步的解碼。若失效塊全部解碼成功完全恢復(fù),則程序結(jié)束。

2)條帶集全局解碼。當(dāng)失效塊不能被條帶集組解碼恢復(fù)數(shù)據(jù)時(shí),則啟用條帶集全局解碼,并標(biāo)記條帶集中未失效塊為活躍塊。在全局層面,如果條帶集內(nèi)每個(gè)條帶的活躍塊大于失效塊個(gè)數(shù),則解碼條帶集中每個(gè)條帶同一位置的失效塊,并標(biāo)記為活躍。同時(shí)檢查可否進(jìn)入第一階段條帶集組解碼:如果可以,則轉(zhuǎn)入第一階段解碼;若不行,程序結(jié)束。

多節(jié)點(diǎn)解碼算法根據(jù)RGRC 的編碼特點(diǎn)設(shè)計(jì),條帶集組解碼優(yōu)先,在條帶集組解碼失效后,再轉(zhuǎn)換成條帶集全局解碼,一旦系統(tǒng)檢查滿足組內(nèi)解碼條件,再轉(zhuǎn)換成條帶集組解碼。這種方式保證了在解碼過(guò)稱中讀取的數(shù)據(jù)量較少,大幅減少系統(tǒng)的修復(fù)成本,同時(shí)將修復(fù)時(shí)間降到最低。

2.4 修復(fù)率分析

修復(fù)率是衡量一個(gè)糾刪碼性能的重要指標(biāo)之一。在本小節(jié)中用于測(cè)試糾刪碼修復(fù)率的方法如下:

假設(shè)一個(gè)參數(shù)為(n,k)的糾刪碼,在分布式存儲(chǔ)系統(tǒng)中,由于硬盤發(fā)生故障,失效的節(jié)點(diǎn)個(gè)數(shù)為x,根據(jù)概率學(xué),共有種失效方式,在這些失效方式中,能夠修復(fù)的失效方式和全部失效方式的比值則為該糾刪碼失效x節(jié)點(diǎn)的修復(fù)率。不同失效節(jié)點(diǎn)數(shù)時(shí)的修復(fù)率側(cè)面反映出了該糾刪碼的容錯(cuò)能力。

表2 為不同參數(shù)下RGRC 在多節(jié)點(diǎn)失效時(shí)修復(fù)率和容錯(cuò)能力。從表2 可以看出在數(shù)據(jù)塊個(gè)數(shù)不變的情況下,冗余塊個(gè)數(shù)越多,RGRC的容錯(cuò)能力就越強(qiáng),多節(jié)點(diǎn)失效時(shí)的修復(fù)率也越高。此外,冗余塊個(gè)數(shù)越接近數(shù)據(jù)塊個(gè)數(shù)時(shí),相應(yīng)修復(fù)節(jié)點(diǎn)的修復(fù)率也將越高。由表2 可知RGRC 的容錯(cuò)能力以及修復(fù)率可以滿足大部分分布式存儲(chǔ)系統(tǒng)的需求,可以根據(jù)具體的業(yè)務(wù)情況,合理地定制不同參數(shù)下的編碼方案。

表2 RGRC的修復(fù)能力Tab.2 Repair capability of RGRC

圖9 展示的分別是(14,10)的RS(Reed-Solomon)碼[23]、(10,2,3)的LRC、(17,10)的basic-Pyamid 碼、(10,2,4,3)的DLRC、(10,2,3) 的 pLRC (proactive Locally Repairable Codes)[24]、(17,10) 的 GRC、(3,3,3),ρ=1 的 UFP-LRC(Unequal Failure Protection based Local Reconstruction Code)[25]與(17,10)的RGRC的修復(fù)率對(duì)比;在失效節(jié)點(diǎn)數(shù)為4時(shí),所有的糾刪碼都可以完全修復(fù);當(dāng)失效節(jié)點(diǎn)數(shù)為5 時(shí),(14,10)RS 碼數(shù)據(jù)丟失;當(dāng)失效節(jié)點(diǎn)數(shù)為6 時(shí),(10,2,3)LRC、(10,2,3)pLRC 數(shù)據(jù)丟失;當(dāng)失效節(jié)點(diǎn)數(shù)為7 時(shí),(3,3,3),ρ=1的UFP-LRC 數(shù)據(jù)丟失,而RGRC 依然保持著較高的修復(fù)率。而RGRC因?yàn)楹蚥asic-Pyamid碼消耗的冗余存儲(chǔ)空間一樣,所以它們的容錯(cuò)能力和修復(fù)率幾乎一樣。綜合來(lái)說(shuō),(17,10)RGRC 的容錯(cuò)能力和修復(fù)率均強(qiáng)于(14,10)的RS 碼、(10,2,3) 的LRC、(10,2,4,3) 的DLRC、(10,2,3) 的pLRC、(17,10)的GRC和(3,3,3),ρ=1的UFP-LRC。

圖9 修復(fù)率對(duì)比Fig.9 Comparison of repair rate

3 實(shí)驗(yàn)與結(jié)果分析

為了在真實(shí)的分布式環(huán)境下對(duì)RGRC 的各方面進(jìn)行測(cè)試,并與現(xiàn)在常用的糾刪碼進(jìn)行比較,基于Ceph 分布式存儲(chǔ)系統(tǒng)搭建了糾刪碼測(cè)試平臺(tái)。糾刪碼測(cè)試平臺(tái)系統(tǒng)主要分為三個(gè)部分,分別為OSD(Object Storage Device)存儲(chǔ)節(jié)點(diǎn)、Monitor 監(jiān)測(cè)節(jié)點(diǎn)以及客戶端。OSD 節(jié)點(diǎn)負(fù)責(zé)存儲(chǔ)數(shù)據(jù)、恢復(fù)數(shù)據(jù)、平衡數(shù)據(jù),Monitor 負(fù)責(zé)監(jiān)視集群的健康狀態(tài)以及控制集群節(jié)點(diǎn)相關(guān)操作,客戶端用于提供用戶操作集群界面。糾刪碼測(cè)試平臺(tái)體系結(jié)構(gòu)如圖10所示。

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)使用的糾刪碼測(cè)試平臺(tái)包含20個(gè)節(jié)點(diǎn),包括:1個(gè)客戶端、1 個(gè)Monitor 節(jié)點(diǎn)和18 個(gè)OSD 存儲(chǔ)節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)的機(jī)器參數(shù)為:CPU Intel Core i7、內(nèi)存8 GB、磁盤500 GB,所有節(jié)點(diǎn)安裝Centos 7系統(tǒng)和Python 2.7運(yùn)行環(huán)境。

圖10 糾刪碼測(cè)試平臺(tái)體系結(jié)構(gòu)Fig.10 Erasure code test platform architecture

3.2 實(shí)驗(yàn)對(duì)比指標(biāo)和方法

實(shí)驗(yàn)對(duì)比指標(biāo)有修復(fù)成本、修復(fù)時(shí)間和存儲(chǔ)開銷。修復(fù)成本指修復(fù)過(guò)程中實(shí)際的數(shù)據(jù)讀取量,也反映修復(fù)操作對(duì)網(wǎng)絡(luò)帶寬資源的占用情況;修復(fù)時(shí)間指修復(fù)過(guò)程的快慢,反映出算法的實(shí)時(shí)能力;存儲(chǔ)開銷指原始文件經(jīng)糾刪碼算法計(jì)算后實(shí)際存儲(chǔ)所占用的存儲(chǔ)空間,存儲(chǔ)開銷越小,分布式存儲(chǔ)系統(tǒng)的可靠性越好。針對(duì)以上實(shí)驗(yàn)對(duì)比指標(biāo),根據(jù)單節(jié)點(diǎn)修復(fù)和多節(jié)點(diǎn)修復(fù)兩種情況分別設(shè)計(jì)實(shí)驗(yàn)來(lái)監(jiān)測(cè)和統(tǒng)計(jì)其數(shù)據(jù)。

3.2.1 修復(fù)成本實(shí)驗(yàn)

1)單節(jié)點(diǎn)失效修復(fù)成本測(cè)試。

實(shí)驗(yàn)設(shè)計(jì)為隨機(jī)單節(jié)點(diǎn)故障來(lái)模擬實(shí)際應(yīng)用中的節(jié)點(diǎn)故障規(guī)律。上傳至糾刪碼測(cè)試平臺(tái)的測(cè)試文件大小分別為1 MB~10 MB 依次遞增,數(shù)據(jù)塊默認(rèn)大小為1 KB。讀取糾刪碼測(cè)試平臺(tái)記錄的各個(gè)糾刪碼修復(fù)讀取的數(shù)據(jù)量進(jìn)行對(duì)比。

2)多節(jié)點(diǎn)修復(fù)成本測(cè)試。

實(shí)驗(yàn)設(shè)計(jì)為隨機(jī)生成失效節(jié)點(diǎn),假設(shè)失效節(jié)點(diǎn)個(gè)數(shù)為x,且x不斷增大。根據(jù)糾刪碼測(cè)試平臺(tái)記錄的每次失效x節(jié)點(diǎn)時(shí)用于恢復(fù)所需要的數(shù)據(jù)讀取量進(jìn)行對(duì)比。實(shí)驗(yàn)用的測(cè)試文件大小為10 MB,數(shù)據(jù)塊默認(rèn)大小為1 KB。

3.2.2 修復(fù)時(shí)間實(shí)驗(yàn)

1)單節(jié)點(diǎn)失效修復(fù)時(shí)間實(shí)驗(yàn)。

實(shí)驗(yàn)設(shè)計(jì)為以10 MB 的存儲(chǔ)數(shù)據(jù)作為測(cè)試數(shù)據(jù),數(shù)據(jù)塊分塊大小默認(rèn)為1 KB,分別設(shè)置10次單節(jié)點(diǎn)失效數(shù)據(jù)修復(fù)測(cè)試,讀取糾刪碼測(cè)試平臺(tái)記錄的各個(gè)糾刪碼修復(fù)時(shí)間進(jìn)行對(duì)比。

2)多節(jié)點(diǎn)失效修復(fù)時(shí)間實(shí)驗(yàn)。

實(shí)驗(yàn)設(shè)計(jì)為以10 MB 的存儲(chǔ)數(shù)據(jù)作為測(cè)試數(shù)據(jù),數(shù)據(jù)塊分塊大小默認(rèn)為1 KB,分別設(shè)置隨機(jī)不同失效節(jié)點(diǎn)個(gè)數(shù)情況下的數(shù)據(jù)修復(fù)測(cè)試,讀取糾刪碼測(cè)試平臺(tái)記錄的各個(gè)糾刪碼修復(fù)時(shí)間進(jìn)行對(duì)比。

3.2.3 存儲(chǔ)開銷實(shí)驗(yàn)

實(shí)驗(yàn)分別上傳10 MB、25 MB、50 MB 的文件至糾刪碼測(cè)試平臺(tái),統(tǒng)計(jì)平臺(tái)記錄的各個(gè)糾刪碼在節(jié)點(diǎn)中占據(jù)的實(shí)際存儲(chǔ)空間進(jìn)行對(duì)比測(cè)試。

為了探究數(shù)據(jù)塊和冗余塊個(gè)數(shù)對(duì)RGRC 的容錯(cuò)能力和單節(jié)點(diǎn)修復(fù)成本的影響,分別使用不同編碼方案的RGRC 測(cè)試其容錯(cuò)能力和單節(jié)點(diǎn)修復(fù)成本。

3.3 實(shí)驗(yàn)對(duì)比糾刪碼

實(shí)驗(yàn)中對(duì)比的糾刪碼分別是(14,10)的RS碼、(10,2,3)的LRC、(17,10) 的basic-Pyamid 碼、(10,2,4,3) 的DLRC、(10,2,3) 的 pLRC、(17,10) 的 GRC 和(3,3,3),ρ=1 的UFP-LRC。(10,2,3)的LRC 和pLRC 初始都將原始數(shù)據(jù)塊分成兩組,每組產(chǎn)生1 個(gè)組內(nèi)局部冗余塊,為整個(gè)數(shù)據(jù)條帶生成3 個(gè)全局冗余塊;(17,10)basic-Pyamid 碼將原始數(shù)據(jù)塊分為2個(gè)小組,每組產(chǎn)生3 個(gè)組內(nèi)局部冗余塊,為整個(gè)數(shù)據(jù)條帶生成1 個(gè)全局冗余塊;(10,2,4,3)的DLRC 為整個(gè)數(shù)據(jù)條帶生成2個(gè)全局冗余塊,將總共12 個(gè)塊分成3 組,每組產(chǎn)生1 個(gè)組內(nèi)局部冗余塊;(17,10)的GRC 將原始數(shù)據(jù)塊分成2組,每組產(chǎn)生2個(gè)組內(nèi)局部冗余塊,為整個(gè)數(shù)據(jù)條帶生成2 個(gè)全局冗余塊,同時(shí)2 個(gè)全局冗余塊生成1 個(gè)額外冗余塊;(3,3,3),ρ=1 的UFP-LRC將原始數(shù)據(jù)塊分成3個(gè)組,每組產(chǎn)生1個(gè)組內(nèi)局部冗余塊,為整個(gè)數(shù)據(jù)條帶生成3 個(gè)全局冗余塊;(17,10)RGRC 將原始數(shù)據(jù)塊分成2 組,每組產(chǎn)生3 個(gè)組內(nèi)局部冗余塊,為整個(gè)數(shù)據(jù)條帶生成1個(gè)全局冗余塊。

3.4 實(shí)驗(yàn)結(jié)果和分析

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

1)單節(jié)點(diǎn)修復(fù)成本實(shí)驗(yàn)。

圖11 為單節(jié)點(diǎn)失效平均修復(fù)成本對(duì)比,修復(fù)成本為單節(jié)點(diǎn)失效恢復(fù)需要的平均數(shù)據(jù)讀取量。RGRC 因在修復(fù)多條帶單節(jié)點(diǎn)失效時(shí),只需讀取少量組內(nèi)數(shù)據(jù)塊和組內(nèi)局部冗余塊,同時(shí)可以利用緩存中的塊數(shù)據(jù),使得RGRC 的修復(fù)成本可以大幅度減少,從圖11 可知(17,10)RGRC 相較于(14,10)RS 碼修復(fù)成本約降低61.8%,相較于(10,2,3)LRC 修復(fù)成本約降低36.4%,相較于(17,10)basic-Pyamid 碼修復(fù)成本約降低29.4%,相較于(10,2,4,3)DLRC 修復(fù)成本約降低25.3%,相較于(17,10)GRC 修復(fù)成本約降低29.5%,相較于(3,3,3),ρ=1UFP-LR 碼修復(fù)成本約降低14.8%。pLRC 雖然修復(fù)單節(jié)點(diǎn)時(shí)會(huì)轉(zhuǎn)換成(2,1)模式進(jìn)行修復(fù)來(lái)降低修復(fù)成本,但前期需要讀取數(shù)據(jù)塊進(jìn)行轉(zhuǎn)移,間接增加了其修復(fù)成本,綜合pLRC 碼前期轉(zhuǎn)移數(shù)據(jù)塊的讀取成本和后期修復(fù)時(shí)的讀取成本,(17,10)RGRC 相較于(10,2,3)pLRC 修復(fù)成本約降低57.6%。另一方面,由于RGRC 的修復(fù)成本與條帶數(shù)量相關(guān),隨著上傳文件數(shù)據(jù)量的增大,相應(yīng)條帶變多,其單節(jié)點(diǎn)修復(fù)成本相較于RS 碼、LRC、basic-Pyamid 碼、DLRC、pLRC、GRC、UFP-LRC將會(huì)進(jìn)一步降低。

2)單節(jié)點(diǎn)修復(fù)時(shí)間實(shí)驗(yàn)。

圖12為單節(jié)點(diǎn)平均修復(fù)時(shí)間對(duì)比。

RGRC 恢復(fù)時(shí)讀取的塊數(shù)量較少,修復(fù)成本縮減,同時(shí)單節(jié)點(diǎn)失效解碼結(jié)構(gòu)簡(jiǎn)單,相比其他糾刪碼能大幅減少修復(fù)時(shí)間。從圖12 可知,(17,10)RGRC 相較于(14,10)RS 碼修復(fù)時(shí)間約減少58.7%,相較于(10,2,3)LRC 修復(fù)時(shí)間約減少34.6%,相較于(17,10)basic-Pyamid 碼修復(fù)時(shí)間約減少30.2%,相較于(10,2,4,3)DLRC 修復(fù)時(shí)間約減少14.2%,相較于(10,2,3)pLRC 修復(fù)時(shí)間約減少53.2%,相較于(17,10)GRC 修復(fù)時(shí)間約減少 33.1%,相較于(3,3,3),ρ=1UFP-LRC修復(fù)時(shí)間約減少23.6%。

圖11 單節(jié)點(diǎn)失效時(shí)各糾刪碼的平均修復(fù)成本對(duì)比Fig.11 Comparison of average repair cost of different erasure codes with single-node failure

圖12 各糾刪碼碼的單節(jié)點(diǎn)平均修復(fù)時(shí)間對(duì)比Fig.12 Comparison of average repair time of single node by different erasure codes

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

1)多節(jié)點(diǎn)修復(fù)成本實(shí)驗(yàn)。

圖13 為多節(jié)點(diǎn)失效的平均修復(fù)成本對(duì)比,修復(fù)成本為節(jié)點(diǎn)失效恢復(fù)需要的平均數(shù)據(jù)讀取量。由于隨著失效節(jié)點(diǎn)個(gè)數(shù)的增多,橫向?qū)Ρ鹊拇a會(huì)超出自身的容錯(cuò)能力,因此,實(shí)驗(yàn)設(shè)計(jì)節(jié)點(diǎn)最大失效個(gè)數(shù)為4,來(lái)測(cè)試其平均修復(fù)成本。

RGRC 在修復(fù)單節(jié)點(diǎn)失效時(shí),可以利用分層旋轉(zhuǎn)編碼的方式大幅降低修復(fù)成本。在修復(fù)多個(gè)節(jié)點(diǎn)失效時(shí),由于牽涉到組解碼恢復(fù)和全局解碼恢復(fù),修復(fù)成本會(huì)相應(yīng)增多,低修復(fù)成本優(yōu)勢(shì)會(huì)逐漸減小。但綜合平均修復(fù)成本,進(jìn)行多節(jié)點(diǎn)修復(fù)時(shí),RGRC 的修復(fù)成本相較于RS 碼、LRC、basic-Pyamid 碼、DLRC、pLRC、GRC、UFP-LRC依然是有所減少的。

2)多節(jié)點(diǎn)修復(fù)時(shí)間實(shí)驗(yàn)。

圖14為多節(jié)點(diǎn)失效的平均修復(fù)時(shí)間對(duì)比。從圖14可知,單節(jié)點(diǎn)修復(fù)時(shí)RGRC 的修復(fù)時(shí)間最少,隨著節(jié)點(diǎn)失效個(gè)數(shù)的增加,相應(yīng)的修復(fù)時(shí)間逐漸增加,相較于其他糾刪碼,其優(yōu)勢(shì)逐漸變小。綜合平均修復(fù)時(shí)間,相較于RS 碼、LRC、basic-Pyamid碼、DLRC、pLRC、GRC、UFP-LRC,RGRC在多節(jié)點(diǎn)時(shí)的修復(fù)時(shí)間,雖不及單節(jié)點(diǎn)的幅度,但依然是有所減少的。

分布式存儲(chǔ)系統(tǒng)中大多數(shù)的故障來(lái)源于單節(jié)點(diǎn)失效,快速修復(fù)單節(jié)點(diǎn)失效可以有效降低存儲(chǔ)系統(tǒng)中多節(jié)點(diǎn)失效情況。由于本次設(shè)計(jì)的糾刪碼主要對(duì)單節(jié)點(diǎn)修復(fù)進(jìn)行改良,降低其修復(fù)成本和修復(fù)時(shí)間。因此,相較于單節(jié)點(diǎn)修復(fù)實(shí)驗(yàn),RGRC 在多節(jié)點(diǎn)的修復(fù)成本和修復(fù)時(shí)間無(wú)法達(dá)到單節(jié)點(diǎn)修復(fù)的降低幅度,關(guān)于多節(jié)點(diǎn)修復(fù)的改良將會(huì)在下一步的研究中進(jìn)一步展開。

圖13 各糾刪碼的多節(jié)點(diǎn)失效平均修復(fù)成本對(duì)比Fig.13 Comparison of average repair cost of multi-node failure by different erasure codes

圖14 各糾刪碼的多節(jié)點(diǎn)平均修復(fù)時(shí)間對(duì)比Fig.14 Comparison of average repair time of multiple nodes by different erasure codes

3.4.3 存儲(chǔ)開銷實(shí)驗(yàn)

RGRC 因?yàn)槠湫D(zhuǎn)編碼方式,能降低單節(jié)點(diǎn)修復(fù)成本,減少修復(fù)時(shí)間,但卻消耗了一定的存儲(chǔ)空間。圖15 為糾刪碼存儲(chǔ)開銷對(duì)比。從圖15 可知,(17,10)RGRC 相較于(14,10)RS碼存儲(chǔ)開銷約增加 21%,相較于(10,2,3)LRC、(10,2,3)pLRC、(10,2,4,3)DLRC 和(3,3,3),ρ=1 的UFP-LRC 存儲(chǔ)開銷約增加13%,相較于(17,10)basic-Pyamid碼和(17,10)GRC 不增加額外的存儲(chǔ)開銷。根據(jù)實(shí)驗(yàn)數(shù)據(jù)的對(duì)比,雖然增加了一定的存儲(chǔ)開銷,但相比其降低的修復(fù)成本和減少的修復(fù)時(shí)間,仍可在接受的范圍內(nèi)。

圖16 展示了不同參數(shù)下的RGRC 的最大容錯(cuò)能力。從圖16 可以看出RGRC 的容錯(cuò)能力與冗余塊個(gè)數(shù)有關(guān),隨著冗余塊個(gè)數(shù)的增加,RGRC相應(yīng)的容錯(cuò)能力也會(huì)隨著增加。

實(shí)驗(yàn)結(jié)果顯示,RGRC 在單節(jié)點(diǎn)修復(fù)時(shí),相較于對(duì)照的其他糾刪碼能大幅度降低修復(fù)成本和修復(fù)時(shí)間。在多節(jié)點(diǎn)的修復(fù)時(shí),隨著節(jié)點(diǎn)個(gè)數(shù)的增加,優(yōu)化幅度逐漸減小,但綜合在多個(gè)節(jié)點(diǎn)修復(fù)時(shí)的修復(fù)成本和修復(fù)時(shí)間后,RGRC 的修復(fù)成本和修復(fù)時(shí)間依然有所改善。雖然RGRC 增加了額外的存儲(chǔ)開銷,但其本身的修復(fù)能力增強(qiáng),最大容錯(cuò)個(gè)數(shù)以及多節(jié)點(diǎn)修復(fù)率都有所提高。綜合來(lái)說(shuō),RGRC 通過(guò)增加冗余同時(shí)利用分層旋轉(zhuǎn)編碼的方式,改善修復(fù)能力、修復(fù)成本和修復(fù)時(shí)間是行之有效的。

圖15 各糾刪碼的存儲(chǔ)開銷對(duì)比Fig.15 Comparison of storage overhead by different erasure codes

圖16 最大容錯(cuò)數(shù)和冗余塊數(shù)的關(guān)系Fig.16 Relationship between maximum number of failure tolerance and number of redundant blocks

4 結(jié)語(yǔ)

在分布式存儲(chǔ)系統(tǒng)中其中大約99.75%故障為單節(jié)點(diǎn)失效故障,過(guò)高的修復(fù)成本將影響分布式存儲(chǔ)系統(tǒng)的系統(tǒng)性能,為此,針對(duì)現(xiàn)有糾刪碼中單節(jié)點(diǎn)失效修復(fù)成本過(guò)大、修復(fù)時(shí)間過(guò)長(zhǎng)的問(wèn)題,提出了RGRC。

RGRC 對(duì)條帶進(jìn)行分組編碼,同時(shí)把條帶組合成條帶集,以條帶集為單位編碼組內(nèi)局部冗余塊。RGRC 在擁有多容錯(cuò)能力的同時(shí),具備低修復(fù)成本和低修復(fù)時(shí)間的特性,特別針對(duì)單節(jié)點(diǎn)失效,具有最佳的修復(fù)成本和讀取成本。實(shí)驗(yàn)結(jié)果表明,與RS 碼相比,RGRC 能降低單節(jié)點(diǎn)修復(fù)成本約61.8%,修復(fù)時(shí)間減少約58.7%,僅需增加約21%的存儲(chǔ)開銷;與LRC、DLRC、pLRC、UFP-LRC 相比,RGRC 能降低單節(jié)點(diǎn)修復(fù)成本14.8%~57.6%,修復(fù)時(shí)間減少14.2%~53.2%,僅需增加約13%的存儲(chǔ)開銷;與basic-Pyamid 碼、GRC 相比,RGRC 能降低單節(jié)點(diǎn)修復(fù)成本約29%,修復(fù)時(shí)間減少約30%,不需要增加額外的存儲(chǔ)開銷。同時(shí),RGRC 在多節(jié)點(diǎn)失效時(shí)也有較高的恢復(fù)率和低修復(fù)成本性,同時(shí)RGRC 靈活性高,能很好地嵌入到分布式存儲(chǔ)系統(tǒng)中,具有很好的前景性。

猜你喜歡
存儲(chǔ)系統(tǒng)原始數(shù)據(jù)解碼
GOLDEN OPPORTUNITY FOR CHINA-INDONESIA COOPERATION
《解碼萬(wàn)噸站》
受特定變化趨勢(shì)限制的傳感器數(shù)據(jù)處理方法研究
分布式存儲(chǔ)系統(tǒng)在企業(yè)檔案管理中的應(yīng)用
哈爾濱軸承(2020年2期)2020-11-06 09:22:36
解碼eUCP2.0
天河超算存儲(chǔ)系統(tǒng)在美創(chuàng)佳績(jī)
NAD C368解碼/放大器一體機(jī)
Quad(國(guó)都)Vena解碼/放大器一體機(jī)
全新Mentor DRS360 平臺(tái)借助集中式原始數(shù)據(jù)融合及直接實(shí)時(shí)傳感技術(shù)實(shí)現(xiàn)5 級(jí)自動(dòng)駕駛
汽車零部件(2017年4期)2017-07-12 17:05:53
華為震撼發(fā)布新一代OceanStor 18000 V3系列高端存儲(chǔ)系統(tǒng)
林口县| 临汾市| 廊坊市| 翼城县| 麟游县| 霍邱县| 东丽区| 茶陵县| 怀安县| 平邑县| 阆中市| 平陆县| 沛县| 南通市| 新郑市| 洛川县| 巨鹿县| 将乐县| 虹口区| 化德县| 灵寿县| 盐津县| 城口县| 大渡口区| 雷波县| 开阳县| 怀宁县| 南投市| 加查县| 长岛县| 兰坪| 鄄城县| 中宁县| 株洲县| 通渭县| 北票市| 大足县| 海晏县| 临汾市| 鞍山市| 河曲县|