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

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

（成都信息工程大學軟件工程學院，成都 610225）

（*通信作者電子郵箱tangdan@foxmail.com）

0 引言

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

多副本技術是將原始數據復制多份，并分別存儲在不同的存儲節(jié)點上。Hadoop 分布式文件系統(tǒng)（Hadoop Distributed File System，HDFS）［4］以及Ceph 分布式存儲［5］系統(tǒng)均采用了多副本中常見的三副本。多副本技術操作簡單，易于實施，但是該方法存儲效率低。以常見的三副本為例，該方法將原始數據復制成三份，保存在三個不同的存儲節(jié)點上，磁盤存儲利用率僅有1/3，同時數據中心構建成本高，存儲成本過大，造成嚴重的資源浪費。

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

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

糾刪碼的修復成本主要由其自己的特性決定，設計糾刪碼的編碼結構能從根本上降低修復成本［7］。目前，根據編碼結構的不同，關于低修復成本的糾刪碼的主要分為兩類：分組碼和再生碼。分組碼是將一個條帶的數據塊進行分組，利用組內的原始數據塊生成局部冗余塊，在原始數據塊失效時，利用組內的局部冗余塊來恢復數據塊，能有效降低數據修復時需要的修復成本；再生碼是通過適當增加冗余并且使新生節(jié)點從盡量多的節(jié)點下載數據塊來降低修復時需要傳輸的數據量［8］。

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

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

再生碼雖然可以大幅度地減少修復時的數據傳輸量，但在數據修復過程中，參與修復的節(jié)點需要把自己存儲的所有數據都讀取出來進行組合，會消耗大量的讀取成本。同時，再生碼編碼復雜度高、編碼耗時長等因素都不適用于現有的分布式存儲系統(tǒng)。

根據數據中心對分布式存儲系統(tǒng)故障的調查研究報告顯示，其中99.75%的故障來源于分布式存儲系統(tǒng)單節(jié)點失效［22］。因此針對現有的分布式存儲系統(tǒng)中頻繁的單節(jié)點失效且糾刪碼修復成本過高的問題，提出了一種低修復成本糾刪碼——旋轉分組修復碼（Rotation Group Repairable Codes，RGRC），并驗證了低成本修復性。RGRC 是將條帶組合成條帶集，對條帶集內的數據塊進行分層旋轉編碼來減少大容量單節(jié)點失效的修復帶寬。同時RGRC 在解決單節(jié)點修復成本高的問題時，依然保留著較高的容錯能力，且為滿足分布式存儲系統(tǒng)的不同需求，可以靈活地權衡其存儲開銷和修復成本。

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

分布式存儲系統(tǒng)使用糾刪碼作為容錯技術，能消耗更少的存儲空間，從而減少存儲硬件的使用，大幅降低存儲中心的構建成本?？梢姡m刪碼空間利用率高的特點在存儲海量數據時具有重大意義。

糾刪碼技術主要是通過糾刪碼算法將原始的數據塊進行編碼得到冗余塊，并將原始數據塊和冗余塊一并存儲起來，以達到容錯的目的。用(n，k)表示一個糾刪碼，K個原始數據塊D1，D2，…，DK經過計算產生了n個塊P1，P2，…，Pn，這一過程稱為編碼。當P1，P2，…，Pn中失效的塊小于該糾刪碼最大的容錯個數時，可以選取其中剩余的塊計算恢復出失效塊，這一過程稱為解碼。相關原理如圖1所示。

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

為了便于理解，現結合圖2 給出如下一些糾刪碼常用的基本概念的說明和定義：

1）極大距離可分（Maximum Distance Separable，MDS）碼：這一類碼在消耗相同存儲開銷的情況下，有最優(yōu)的容錯能力，因此被分布式存儲系統(tǒng)廣泛使用。對于一個參數為(n，k)的MDS糾刪碼來講，容錯能力為n-k。

2）系統(tǒng)性糾刪碼：數據塊經過計算產生的塊中包含原始的數據塊，因良好的訪問性能而成為分布式存儲系統(tǒng)的首選。

3）容錯度：糾刪碼可以容忍的丟失數據塊個數。

4）原始數據塊：用戶上傳的原始數據對象被系統(tǒng)劃分后得到的塊。

5）冗余塊：數據塊經過糾刪碼算法后產生的所有塊。

6）條帶：由多個數據塊和冗余塊組成，滿足同一糾刪碼算法。

7）條帶集：由多個條帶組成的集合。

圖2 數據塊、冗余塊、條帶和條帶集之間的相互關系Fig.2 Correlation between data blocks，redundant blocks，stripes and strip set

2 旋轉分組修復碼

2.1 糾刪碼數據修復問題定義

為了便于理解，基于文獻給出糾刪碼數據修復問題相關的定義。

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

定義2糾刪碼的修復時間。糾刪碼在進行數據修復時所消耗的時長。分布式存儲系統(tǒng)中，修復的快慢直接影響到系統(tǒng)的穩(wěn)定性，如果在數據量龐大的存儲系統(tǒng)中，一旦不能快速恢復數據，有可能導致在修復過程中因其他任務的影響而使其余數據塊再次失效，因此，對于分布式存儲系統(tǒng)中的糾刪碼來說，修復時間應該越小越好。

定義3糾刪碼的修復率。修復率是糾刪碼重要的指標之一。不同失效節(jié)點數時的修復率側面反映出了該糾刪碼的容錯能力。

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

定義5局部冗余塊。條帶中組內原始數據塊參與編碼計算得到的冗余塊。

表1為常用符號說明。

表1 常用符號Tab.1 Common symbols

2.2 編碼算法

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

系統(tǒng)型MDS 碼的編碼過程為：首先在有限域上構造編碼矩陣，編碼矩陣與原始數據塊在有限域中執(zhí)行乘法運算得到編碼塊。

如編碼公式（1）所示，D1，D2，…，DK總共K個原始數據塊與編碼矩陣相乘，計算產生了C1，C2，…，Cn，共n個塊，其中產生的n個塊中包含了k個原始數據塊。

RGRC的編碼過程如下：

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

步驟2 多個條帶組合成條帶集，形成每個條帶集包含S個條帶，每個條帶包含L個小組的結構。小組Li的倒數第二個組內局部冗余塊稱為前段冗余塊（Rotation Front block，RF），最后一個組內局部冗余塊稱為后段冗余塊（Rotation Back block，RB），RF 通過前段數據旋轉編碼方式得到，RB 的通過后段數據旋轉編碼得到。相應的編碼結構如圖3所示。

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

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

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

1）全局冗余塊生成公式：

2）組內局部冗余塊生成公式：

設條帶集包含S個條帶，RFs，l表示條帶集中第s條帶中第l小組的前段冗余塊，RBs，l表示條帶集中第s條帶中第l小組的后段冗余塊。

3）前段、后段冗余塊生成公式如下：

下面從(14，10)的MDS碼出發(fā)，構造(18，10)RGRC演示編碼過程。圖4 展示的(14，10)的編碼結構，D1，D2，…，D10為10個原始數據塊，P1，P2，…，P4為經過編碼計算后產生的4個全局冗余塊。

圖4 (14，10)MDS碼的編碼結構Fig.4 Encoding structure of(14，10)MDS code

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

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

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

圖6 前段旋轉編碼結構Fig.6 Anterior rotary coding structure

如圖7 所示，P41為后段冗余塊列。按照RBs，l生成公式構造出如圖7的后段冗余塊。

圖7 后段旋轉編碼結構Fig.7 Posterior rotary coding structure

相較于MDS 碼，RGRC 先通過對數據條帶進行分組產生組內局部冗余塊，組合條帶構成條帶集進行旋轉編碼，這種設計可以保障在單節(jié)點失效時快速在組內恢復，同時以條帶集為單位進行恢復，大幅減少修復需要讀取的數據量，從而降低修復時的修復成本和數據傳輸量。

2.3 解碼算法

RGRC 的解碼過程大致為：利用現有數據組合出對應的剩余編碼矩陣的逆矩陣與剩余活躍的塊在有限域中進行乘法運算，從而求得丟失的數據塊。

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

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

當失效節(jié)點為單節(jié)點時，以條帶集為單位進行解碼。假設失效單節(jié)點在Li組，且S為偶數時，解碼過程按如下步驟進行解碼：

步驟1 條帶集以2 個條帶進行集合劃分Ai={Sq，Sp}，（其中i=1，2，…，S/2），Sq、Sp為旋轉編碼相關聯(lián)的兩個條帶。

步驟2 當失效節(jié)點在前段數據塊列時，恢復Sq條帶中的失效數據塊時，讀取Sq條帶中Li組的前k0個未失效的原始數據塊和局部冗余塊組成新的塊集合，并保存在緩存中?；謴蚐p條帶中的失效數據塊時，讀取Sp條帶中Li組的未失效的前段數據塊，前段旋轉編碼產生的RF塊和緩存中需用到的塊組成新的塊集合。新的塊集合和對應的剩余編碼矩陣的逆矩陣相乘來恢復2 個條帶中的失效數據塊。照此方法循環(huán)迭代，恢復條帶集中所有的失效數據塊，并進一步恢復整個節(jié)點失效的數據塊。

步驟3 當失效節(jié)點在后段數據塊列時，恢復Sq條帶中的失效數據塊，讀取Sq條帶中Li組的前k0個未失效的原始數據塊和局部冗余塊組成新的數據塊集合，并保存在緩存中。恢復Sp條帶中的失效數據塊時，讀取Sp條帶中Li組的未失效的后段數據塊，后段旋轉編碼產生的RB塊和緩存中需用到的塊組成新的塊集合。

新的塊集合和對應的剩余編碼矩陣的逆矩陣相乘來恢復2 個條帶中的失效數據塊。照此方法循環(huán)迭代，恢復條帶集中所有的失效數據塊，并進一步恢復整個節(jié)點失效的數據塊。

假設失效單節(jié)點在Li組，且S為奇數時，解碼過程按如下步驟進行解碼：

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

步驟2 恢復Ai集合與S為偶數時一樣?；謴虰集合中的失效數據塊時，讀取SS條帶中Li組的前k0個未失效的原始數據塊和局部冗余塊組成新的塊集合，新的塊集合和對應的剩余編碼矩陣的逆矩陣相乘來恢復失效數據塊。

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

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

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

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

條帶集組解碼是指利用和失效節(jié)點在同一小組內的條帶集中未失效的塊來解碼恢復失效塊。由于條帶集中小組內塊數較少，在恢復失效塊時需讀取的塊數較少，解碼成本能降到最低。當條帶集組內解碼無法恢復失效塊時，使用條帶集全局解碼恢復失效塊。條帶集全局解碼利用條帶集內全局未失效塊來恢復失效塊，為了降低讀取成本，當利用條帶集全局解碼恢復出某些失效塊后，為可以滿足條帶集組解碼條件時，條帶集全局解碼應馬上轉換成條帶集組解碼進行解碼。

根據以上原則，對多節(jié)點失效的貪心策略的解碼算法過程分為兩個階段：

1）條帶集組解碼。對于條帶集中每個小組，當失效塊數小于局部冗余塊數，則啟用條帶集組解碼恢復數據，當解碼成功后，標記為活躍塊，可以參與下一步的解碼。若失效塊全部解碼成功完全恢復，則程序結束。

2）條帶集全局解碼。當失效塊不能被條帶集組解碼恢復數據時，則啟用條帶集全局解碼，并標記條帶集中未失效塊為活躍塊。在全局層面，如果條帶集內每個條帶的活躍塊大于失效塊個數，則解碼條帶集中每個條帶同一位置的失效塊，并標記為活躍。同時檢查可否進入第一階段條帶集組解碼：如果可以，則轉入第一階段解碼；若不行，程序結束。

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

2.4 修復率分析

修復率是衡量一個糾刪碼性能的重要指標之一。在本小節(jié)中用于測試糾刪碼修復率的方法如下：

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

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

表2 RGRC的修復能力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的修復率對比；在失效節(jié)點數為4時，所有的糾刪碼都可以完全修復；當失效節(jié)點數為5 時，(14，10)RS 碼數據丟失；當失效節(jié)點數為6 時，(10，2，3)LRC、(10，2，3)pLRC 數據丟失；當失效節(jié)點數為7 時，(3，3，3)，ρ=1的UFP-LRC 數據丟失，而RGRC 依然保持著較高的修復率。而RGRC因為和basic-Pyamid碼消耗的冗余存儲空間一樣，所以它們的容錯能力和修復率幾乎一樣。綜合來說，(17，10)RGRC 的容錯能力和修復率均強于(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 修復率對比Fig.9 Comparison of repair rate

3 實驗與結果分析

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

3.1 實驗環(huán)境

實驗使用的糾刪碼測試平臺包含20個節(jié)點，包括：1個客戶端、1 個Monitor 節(jié)點和18 個OSD 存儲節(jié)點。每個節(jié)點的機器參數為：CPU Intel Core i7、內存8 GB、磁盤500 GB，所有節(jié)點安裝Centos 7系統(tǒng)和Python 2.7運行環(huán)境。

圖10 糾刪碼測試平臺體系結構Fig.10 Erasure code test platform architecture

3.2 實驗對比指標和方法

實驗對比指標有修復成本、修復時間和存儲開銷。修復成本指修復過程中實際的數據讀取量，也反映修復操作對網絡帶寬資源的占用情況；修復時間指修復過程的快慢，反映出算法的實時能力；存儲開銷指原始文件經糾刪碼算法計算后實際存儲所占用的存儲空間，存儲開銷越小，分布式存儲系統(tǒng)的可靠性越好。針對以上實驗對比指標，根據單節(jié)點修復和多節(jié)點修復兩種情況分別設計實驗來監(jiān)測和統(tǒng)計其數據。

3.2.1 修復成本實驗

1）單節(jié)點失效修復成本測試。

實驗設計為隨機單節(jié)點故障來模擬實際應用中的節(jié)點故障規(guī)律。上傳至糾刪碼測試平臺的測試文件大小分別為1 MB～10 MB 依次遞增，數據塊默認大小為1 KB。讀取糾刪碼測試平臺記錄的各個糾刪碼修復讀取的數據量進行對比。

2）多節(jié)點修復成本測試。

實驗設計為隨機生成失效節(jié)點，假設失效節(jié)點個數為x，且x不斷增大。根據糾刪碼測試平臺記錄的每次失效x節(jié)點時用于恢復所需要的數據讀取量進行對比。實驗用的測試文件大小為10 MB，數據塊默認大小為1 KB。

3.2.2 修復時間實驗

1）單節(jié)點失效修復時間實驗。

實驗設計為以10 MB 的存儲數據作為測試數據，數據塊分塊大小默認為1 KB，分別設置10次單節(jié)點失效數據修復測試，讀取糾刪碼測試平臺記錄的各個糾刪碼修復時間進行對比。

2）多節(jié)點失效修復時間實驗。

實驗設計為以10 MB 的存儲數據作為測試數據，數據塊分塊大小默認為1 KB，分別設置隨機不同失效節(jié)點個數情況下的數據修復測試，讀取糾刪碼測試平臺記錄的各個糾刪碼修復時間進行對比。

3.2.3 存儲開銷實驗

實驗分別上傳10 MB、25 MB、50 MB 的文件至糾刪碼測試平臺，統(tǒng)計平臺記錄的各個糾刪碼在節(jié)點中占據的實際存儲空間進行對比測試。

為了探究數據塊和冗余塊個數對RGRC 的容錯能力和單節(jié)點修復成本的影響，分別使用不同編碼方案的RGRC 測試其容錯能力和單節(jié)點修復成本。

3.3 實驗對比糾刪碼

實驗中對比的糾刪碼分別是(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 初始都將原始數據塊分成兩組，每組產生1 個組內局部冗余塊，為整個數據條帶生成3 個全局冗余塊；(17，10)basic-Pyamid 碼將原始數據塊分為2個小組，每組產生3 個組內局部冗余塊，為整個數據條帶生成1 個全局冗余塊；(10，2，4，3)的DLRC 為整個數據條帶生成2個全局冗余塊，將總共12 個塊分成3 組，每組產生1 個組內局部冗余塊；(17，10)的GRC 將原始數據塊分成2組，每組產生2個組內局部冗余塊，為整個數據條帶生成2 個全局冗余塊，同時2 個全局冗余塊生成1 個額外冗余塊；(3，3，3)，ρ=1 的UFP-LRC將原始數據塊分成3個組，每組產生1個組內局部冗余塊，為整個數據條帶生成3 個全局冗余塊；(17，10)RGRC 將原始數據塊分成2 組，每組產生3 個組內局部冗余塊，為整個數據條帶生成1個全局冗余塊。

3.4 實驗結果和分析

3.4.1 單節(jié)點修復

1）單節(jié)點修復成本實驗。

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

2）單節(jié)點修復時間實驗。

圖12為單節(jié)點平均修復時間對比。

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

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

圖12 各糾刪碼碼的單節(jié)點平均修復時間對比Fig.12 Comparison of average repair time of single node by different erasure codes

3.4.2 多節(jié)點修復

1）多節(jié)點修復成本實驗。

圖13 為多節(jié)點失效的平均修復成本對比，修復成本為節(jié)點失效恢復需要的平均數據讀取量。由于隨著失效節(jié)點個數的增多，橫向對比的碼會超出自身的容錯能力，因此，實驗設計節(jié)點最大失效個數為4，來測試其平均修復成本。

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

2）多節(jié)點修復時間實驗。

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

分布式存儲系統(tǒng)中大多數的故障來源于單節(jié)點失效，快速修復單節(jié)點失效可以有效降低存儲系統(tǒng)中多節(jié)點失效情況。由于本次設計的糾刪碼主要對單節(jié)點修復進行改良，降低其修復成本和修復時間。因此，相較于單節(jié)點修復實驗，RGRC 在多節(jié)點的修復成本和修復時間無法達到單節(jié)點修復的降低幅度，關于多節(jié)點修復的改良將會在下一步的研究中進一步展開。

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

圖14 各糾刪碼的多節(jié)點平均修復時間對比Fig.14 Comparison of average repair time of multiple nodes by different erasure codes

3.4.3 存儲開銷實驗

RGRC 因為其旋轉編碼方式，能降低單節(jié)點修復成本，減少修復時間，但卻消耗了一定的存儲空間。圖15 為糾刪碼存儲開銷對比。從圖15 可知，(17，10)RGRC 相較于(14，10)RS碼存儲開銷約增加 21%，相較于(10，2，3)LRC、(10，2，3)pLRC、(10，2，4，3)DLRC 和(3，3，3)，ρ=1 的UFP-LRC 存儲開銷約增加13%，相較于(17，10)basic-Pyamid碼和（17，10）GRC 不增加額外的存儲開銷。根據實驗數據的對比，雖然增加了一定的存儲開銷，但相比其降低的修復成本和減少的修復時間，仍可在接受的范圍內。

圖16 展示了不同參數下的RGRC 的最大容錯能力。從圖16 可以看出RGRC 的容錯能力與冗余塊個數有關，隨著冗余塊個數的增加，RGRC相應的容錯能力也會隨著增加。

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

圖15 各糾刪碼的存儲開銷對比Fig.15 Comparison of storage overhead by different erasure codes

圖16 最大容錯數和冗余塊數的關系Fig.16 Relationship between maximum number of failure tolerance and number of redundant blocks

4 結語

在分布式存儲系統(tǒng)中其中大約99.75%故障為單節(jié)點失效故障，過高的修復成本將影響分布式存儲系統(tǒng)的系統(tǒng)性能，為此，針對現有糾刪碼中單節(jié)點失效修復成本過大、修復時間過長的問題，提出了RGRC。

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