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

（成都信息工程大學(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)中，具有很好的前景性。