楊松霖，張廣艷

清華大學(xué) 計算機(jī)科學(xué)與技術(shù)系，北京 100084

糾刪碼存儲系統(tǒng)中數(shù)據(jù)修復(fù)方法綜述*

楊松霖，張廣艷+

清華大學(xué) 計算機(jī)科學(xué)與技術(shù)系，北京 100084

Abstract:Erasure codes have the advantage of low storage overhead.However,they also have the drawbacks of long recovery time and high impact on application performance.This paper presents the computation model of the time for data recovery with erasure codes,and identifies the key factors that affect the recovery performance.Thereafter,this paper chooses the computation overhead,read/write overhead,and transmission overhead as the evaluation criterion for the recovery performance.In addition,this paper analyzes how the latest efforts in this field reduce overheads from the aspects of computation,read/write,and transmission.Finally,this paper compares existing coding schemes from the aspects of recovery performance,reliability,as well as storage overhead,and then points out the future research directions.

Key words:erasure codes;multiple replicas;data recovery;performance improvement

糾刪碼技術(shù)具有存儲開銷低的優(yōu)勢，然而在進(jìn)行數(shù)據(jù)修復(fù)時面臨修復(fù)時間長和對前端應(yīng)用性能影響高的缺陷。給出糾刪碼技術(shù)中數(shù)據(jù)修復(fù)完成時間的計算模型，指出影響修復(fù)性能的關(guān)鍵因素，進(jìn)而選取計算開銷、讀寫開銷、傳輸開銷作為修復(fù)性能的評價標(biāo)準(zhǔn)；分析了現(xiàn)有研究工作如何降低計算、讀寫和傳輸3種開銷，重點討論了其關(guān)鍵性技術(shù)的優(yōu)缺點；最后從修復(fù)性能、可靠性、存儲開銷等方面對現(xiàn)有編碼方案進(jìn)行對比，并指出未來可能的研究方向。

糾刪碼；多副本；數(shù)據(jù)修復(fù)；性能優(yōu)化

1 引言

隨著計算機(jī)技術(shù)的發(fā)展與互聯(lián)網(wǎng)的普及，數(shù)據(jù)呈現(xiàn)爆發(fā)式增長，有研究表明，過去兩年里產(chǎn)生的數(shù)據(jù)已經(jīng)占世界數(shù)據(jù)總量的90%[1]。數(shù)據(jù)成為當(dāng)今企業(yè)的核心資產(chǎn)，企業(yè)面臨著數(shù)據(jù)丟失和數(shù)據(jù)不可用的風(fēng)險，如何解決這些問題，對現(xiàn)代存儲系統(tǒng)提出了巨大的挑戰(zhàn)。多副本技術(shù)通過將數(shù)據(jù)的多個冗余副本分布在不同機(jī)器上，當(dāng)存儲節(jié)點發(fā)生故障時，自動將服務(wù)切換到其他副本，從而實現(xiàn)數(shù)據(jù)的高可靠和高可用。然而隨著數(shù)據(jù)的持續(xù)增長，在PB級別的數(shù)據(jù)中心，多副本技術(shù)會引入極大的存儲開銷。比如，現(xiàn)有的分布式存儲系統(tǒng)，如HDFS（Hadoop distributed file system）[2]、Ceph[3]，普遍采用三副本的配置，這將占用原始數(shù)據(jù)的3倍存儲空間。

面對如此情況，糾刪碼技術(shù)因其低存儲開銷的特點近年來受到越來越多的關(guān)注。其中，RS編碼（Reed-Solomon code）[4]是目前被廣泛使用的糾刪碼方案，它將k個數(shù)據(jù)塊按照一定的編碼規(guī)則，生成m個校驗塊，對于這k+m個編碼塊，其編碼性質(zhì)保證通過任意的k個編碼塊均能重建出所有數(shù)據(jù)。以RS（4,2）編碼為例，它只需占用1.5倍的存儲空間，就具有與三副本技術(shù)相同的容錯能力。

然而當(dāng)數(shù)據(jù)丟失時，糾刪碼技術(shù)數(shù)據(jù)修復(fù)的速度沒有多副本快。為了修復(fù)丟失的數(shù)據(jù)，多副本技術(shù)只需拷貝對應(yīng)數(shù)據(jù)的冗余副本。而糾刪碼需要讀取k塊數(shù)據(jù)，通過計算重建丟失的數(shù)據(jù)，相比之下，占用了更多的磁盤帶寬和網(wǎng)絡(luò)帶寬，也引入了額外的計算開銷。這不僅導(dǎo)致修復(fù)時間過長，而且也對前臺應(yīng)用帶來干擾。在大規(guī)模集群環(huán)境下，磁盤、服務(wù)器和網(wǎng)絡(luò)的錯誤已經(jīng)成為常態(tài)，如在Facebook的數(shù)據(jù)中心平均每天發(fā)生50起機(jī)器不可用事件[5]。在這種情況下，為了保持?jǐn)?shù)據(jù)可靠性，存儲系統(tǒng)需要頻繁進(jìn)行修復(fù)操作，進(jìn)一步加重了糾刪碼修復(fù)給系統(tǒng)帶來的壓力。

針對糾刪碼修復(fù)存在的性能缺陷，近年來涌現(xiàn)出很多理論設(shè)計和工程實現(xiàn)的工作。目前，國內(nèi)外存在少量糾刪碼技術(shù)的研究綜述[6-9]，其中文獻(xiàn)[8]主要關(guān)注編碼方案上的進(jìn)展，文獻(xiàn)[9]主要圍繞編碼實現(xiàn)、數(shù)據(jù)修復(fù)和數(shù)據(jù)更新等方面的最新研究進(jìn)展。本文將只聚焦于糾刪碼數(shù)據(jù)修復(fù)，從系統(tǒng)性能優(yōu)化的一般性原則出發(fā)，分析影響糾刪碼數(shù)據(jù)修復(fù)性能的關(guān)鍵因素，如圖1所示，圍繞讀寫、計算、傳輸3個層級，對現(xiàn)有的優(yōu)化技術(shù)進(jìn)行討論。其中，從減少計算量和加速計算執(zhí)行兩個角度介紹了計算優(yōu)化方面的工作；從降低I/O總量和提高I/O并行度兩個角度介紹了讀寫優(yōu)化方面的工作；從減少單個節(jié)點的傳輸量和減少參與修復(fù)節(jié)點數(shù)量兩個角度介紹了傳輸優(yōu)化方面的工作。最后，對比分析了針對修復(fù)性能優(yōu)化的編碼方案，并指出未來可能的研究方向。

Fig.1 Hierarchy of recovery performance optimization圖1 修復(fù)性能優(yōu)化層級圖

本文組織結(jié)構(gòu)如下：第2章介紹糾刪碼技術(shù)的相關(guān)背景；第3章論述從計算角度優(yōu)化糾刪碼修復(fù)性能的關(guān)鍵技術(shù)；第4章論述從讀寫角度優(yōu)化糾刪碼修復(fù)性能的關(guān)鍵技術(shù)；第5章論述從傳輸角度優(yōu)化糾刪碼修復(fù)性能的關(guān)鍵技術(shù)；第6章討論評價了現(xiàn)有的編碼方案；第7章總結(jié)全文，并展望未來研究方向。

2 基礎(chǔ)與關(guān)鍵因素

以下介紹糾刪碼的相關(guān)概念，闡述糾刪碼的修復(fù)過程，重點分析影響糾刪碼的數(shù)據(jù)修復(fù)性能的關(guān)鍵因素。

2.1 基本概念

為了便于理解，對本文出現(xiàn)的相關(guān)概念給出如下說明。

（1）數(shù)據(jù)塊：原始用戶數(shù)據(jù)被系統(tǒng)劃分形成的最小編碼單位。

（2）校驗塊：由數(shù)據(jù)塊經(jīng)過相關(guān)運(yùn)算得到的校驗數(shù)據(jù)。

（3）條帶：多個數(shù)據(jù)塊與其對應(yīng)的校驗塊構(gòu)成的冗余集合，如果一定數(shù)目的編碼塊丟失，可以通過對所在條帶中剩余編碼塊進(jìn)行運(yùn)算而重新生成。

（4）容錯能力：編碼方案中最大允許出錯的節(jié)點數(shù)，當(dāng)出錯的節(jié)點數(shù)超過其容錯能力時，將無法修復(fù)丟失的數(shù)據(jù)。

（5）最大距離可分碼（maximum distance separable，MDS）：滿足Singleton邊界[10]的線性編碼方式。與其他編碼相比，它在同等容錯能力的情況下?lián)碛凶畹偷拇鎯﹂_銷。

（6）參與節(jié)點：參與數(shù)據(jù)修復(fù)的節(jié)點。它需要讀取本地數(shù)據(jù)來參與數(shù)據(jù)重建。

（7）修復(fù)節(jié)點：重建丟失數(shù)據(jù)的節(jié)點。它通過從參與修復(fù)的節(jié)點中收集所需數(shù)據(jù)，計算得到丟失的數(shù)據(jù)。

（8）存儲利用率：原始用戶數(shù)據(jù)量與編碼后所占存儲空間的比值。由于提供容錯保護(hù)需要存儲冗余信息，從而糾刪碼的存儲利用率總是小于1。

2.2 編碼修復(fù)過程

在現(xiàn)有的分布式存儲系統(tǒng)中，RS編碼是一種常見的糾刪碼編碼方案，它支持任意數(shù)目的數(shù)據(jù)塊與校驗塊參數(shù)配置，其生成矩陣采用范德蒙矩陣或柯西矩陣進(jìn)行構(gòu)造。如圖2所示，RS編碼利用生成矩陣G與原始數(shù)據(jù)向量的乘積，生成整個條帶的數(shù)據(jù)。當(dāng)數(shù)據(jù)塊出現(xiàn)丟失，首先從生成矩陣中去掉丟失數(shù)據(jù)塊對應(yīng)的行，構(gòu)造出殘余矩陣；然后求解殘余矩陣的逆矩陣，并取出丟失數(shù)據(jù)塊所對應(yīng)的行向量；最后將行向量與存活數(shù)據(jù)相乘，恢復(fù)出丟失數(shù)據(jù)。

目前，多數(shù)分布式存儲系統(tǒng)采用集中式編碼實現(xiàn)[9]，數(shù)據(jù)修復(fù)過程一般包含4個步驟：

（1）參與節(jié)點從本地磁盤讀取所需數(shù)據(jù)。

（2）為了實現(xiàn)減少數(shù)據(jù)傳輸量等目標(biāo)，參與節(jié)點對數(shù)據(jù)進(jìn)行本地合并后生成傳輸數(shù)據(jù)。

（3）參與節(jié)點將傳輸數(shù)據(jù)通過網(wǎng)絡(luò)傳輸?shù)叫迯?fù)節(jié)點。

（4）修復(fù)節(jié)點接收到修復(fù)需要的所有數(shù)據(jù)，通過計算重建出丟失數(shù)據(jù)。

Fig.2 Encoding and recovery process of RS code圖2 RS編碼的編碼和修復(fù)過程

2.3 修復(fù)性能的影響因素

當(dāng)分布式存儲系統(tǒng)中出現(xiàn)數(shù)據(jù)失效時，兩種操作將觸發(fā)數(shù)據(jù)修復(fù)：降級讀（degrade read）和主動修復(fù)（proactive repair）。前者是用戶訪問失效數(shù)據(jù)時，觸發(fā)存儲系統(tǒng)對相應(yīng)數(shù)據(jù)進(jìn)行修復(fù)；后者是存儲系統(tǒng)檢測到節(jié)點失效或數(shù)據(jù)失效，主動進(jìn)行的數(shù)據(jù)修復(fù)行為。對于前者，用戶請求的響應(yīng)需要等待數(shù)據(jù)修復(fù)完成，顯著增加了請求延遲。而后者的修復(fù)操作極大占用系統(tǒng)的計算資源、磁盤資源和網(wǎng)絡(luò)資源，對用戶的性能造成干擾。由此可見，加快數(shù)據(jù)修復(fù)過程，降低修復(fù)開銷是糾刪碼修復(fù)面臨的主要問題。

RS編碼的修復(fù)中傳輸數(shù)據(jù)與磁盤讀取數(shù)據(jù)等同，不需要步驟（2）的數(shù)據(jù)加工處理（見2.2節(jié)）。但是，也存在不少編碼方案[11-12]，參與節(jié)點需要對磁盤讀取數(shù)據(jù)進(jìn)行線性組合，減少傳輸?shù)臄?shù)據(jù)量。因此，數(shù)據(jù)修復(fù)所花費的時間可以如下表示：

其中，Ddisk、Dnet分別代表參與節(jié)點讀取的數(shù)據(jù)量和網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)量；Sdisk、Snet分別代表磁盤的讀取速度和網(wǎng)絡(luò)的傳輸速度；Tcom代表計算所花費的時間；k代表修復(fù)過程中訪問的節(jié)點數(shù)量。

在基于流水線的修復(fù)模式下，最大修復(fù)帶寬受限于上述4個步驟中的最小處理帶寬，修復(fù)時間受到計算開銷、磁盤讀寫開銷和網(wǎng)絡(luò)傳輸開銷的共同影響。由于大部分分布式系統(tǒng)都搭建在廉價的服務(wù)器上，CPU計算能力、磁盤性能和網(wǎng)卡速度均有可能成為制約修復(fù)帶寬的瓶頸。如果能夠降低計算處理、磁盤讀取和網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)量，加快計算執(zhí)行、磁盤讀取和網(wǎng)絡(luò)傳輸?shù)乃俣?，將減少糾刪碼的修復(fù)時間，并降低數(shù)據(jù)修復(fù)對應(yīng)用性能的影響。

基于以上分析，計算操作、磁盤讀寫和網(wǎng)絡(luò)傳輸是影響糾刪碼修復(fù)性能的關(guān)鍵因素。因此，從這三方面入手，對現(xiàn)有的優(yōu)化技術(shù)進(jìn)行歸納，并選取計算開銷、讀寫開銷、傳輸開銷作為糾刪碼修復(fù)性能的評價標(biāo)準(zhǔn)。

3 計算優(yōu)化

RS編碼的運(yùn)算法則建立在迦羅瓦域GF(2w)上，修復(fù)過程不僅涉及殘余矩陣的求逆運(yùn)算，同時涉及復(fù)雜的有限域運(yùn)算。GF(2w)上的加法等同于異或運(yùn)算，而乘法的計算相對復(fù)雜，涉及多項式乘法和取余運(yùn)算。目前針對計算的優(yōu)化主要分為兩類：減少計算量和加速計算執(zhí)行。

3.1 減少計算量

在柯西編碼的生成矩陣中，“1”的數(shù)量反映計算過程中需要的異或次數(shù)，因此大量的研究工作試圖通過尋找低密度生成矩陣的編碼方案來減少計算量[13-15]。然而對于低密度的編碼矩陣，其解碼矩陣可能非常稠密，無法在修復(fù)時也同樣減少計算量。

為了降低矩陣密度對計算量的直接影響，已有工作采用計算調(diào)度的方式來減少計算過程中的計算量[16]。其基本思想是調(diào)整計算的執(zhí)行順序，最大可能地利用計算過程中的中間結(jié)果來減少重復(fù)的計算。如圖3所示，在B=AX的計算中，為了計算B中4個目標(biāo)塊的值，傳統(tǒng)的計算方式如圖3中右邊所示，整個計算需要12次異或操作。如果利用b2=b1+x1，可以將整體的操作次數(shù)從12降低至9。然而，如何根據(jù)給定的生成矩陣尋找最優(yōu)的計算調(diào)度方案，已經(jīng)被Huang等人推測是NP完全問題[17]，現(xiàn)有的解決方式主要基于貪心原則和啟發(fā)式搜索尋找次優(yōu)的調(diào)度方案。

Fig.3 Data encoding process under 01 matrix圖3 01矩陣下的數(shù)據(jù)編碼過程

基于貪心的原則，Hafner等人[18]提出了CSHR（code specific hybrid reconstruction）調(diào)度算法，其思想是讓向量B中已經(jīng)計算出的目標(biāo)塊bi參與待求解目標(biāo)塊bj的計算。比如，b2的求解可以借助于b1。相比傳統(tǒng)計算方式下，目標(biāo)塊的求解固定使用一種編碼等式，CSHR算法大大增加了編碼等式可選的方案數(shù)量。得益于目標(biāo)塊之間存在公共的計算部分，CSHR算法在不使用額外空間的情況下，能夠減少總的計算次數(shù)。

然而，CSHR算法只用目標(biāo)塊bi的值優(yōu)化其他目標(biāo)塊的求解，卻忽略了多個目標(biāo)塊的編碼等式中存在更細(xì)粒度的公共計算部分。比如圖3中的例子，x3+x4+x5均出現(xiàn)在b1、b2和b3的編碼等式中。如果預(yù)先計算并保存x3+x4+x5的值，那么只需額外3次計算即可求解出b1、b2和b3。文獻(xiàn)[17]中，Huang等人提出的Subex（common subexpressions）算法恰好解決了這個問題。Subex算法首先統(tǒng)計任意計算單元組合(xi,xj)在所有編碼等式中成對出現(xiàn)的次數(shù)，在圖4（a）的完全圖中展示了生成矩陣A中所有計算單元對的統(tǒng)計情況，邊權(quán)代表兩個端點構(gòu)成的計算單元對出現(xiàn)的次數(shù)，此時邊權(quán)最大值為3。然后移除邊權(quán)低于3的邊，在剩余圖中利用最大權(quán)匹配算法選出最多的非交叉邊，如圖4（b）所示。Subex算法優(yōu)先計算出這些邊對應(yīng)的計算組合，并用來替換目標(biāo)塊需要的運(yùn)算，重復(fù)以上步驟，經(jīng)過多次迭代，最終求解出所有目標(biāo)塊。

Fig.4 Illustration of Subex圖4 Subex算法說明

除了單一從算法設(shè)計對調(diào)度進(jìn)行優(yōu)化，Zhang等人[19]提出的CaCo算法將低密度編碼設(shè)計和計算調(diào)度結(jié)合在一起。該算法分為矩陣選取和調(diào)度選取兩個階段，首先使用多種矩陣生成算法得到多個低密度的柯西矩陣，然后對每個生成矩陣嘗試不同的計算調(diào)度算法得到多種調(diào)度方案，最后在所有方案中選取計算量最小的調(diào)度方案。CaCo算法將現(xiàn)有的矩陣生成算法和計算調(diào)度算法融入到統(tǒng)一的計算框架中，相比單一算法，能夠產(chǎn)生更多的選擇，進(jìn)而得到計算量更低的調(diào)度方案。

3.2 加速計算執(zhí)行

有限域的乘法運(yùn)算存在計算復(fù)雜的問題，為了加快執(zhí)行速度，目前有兩種優(yōu)化方式：位運(yùn)算轉(zhuǎn)換法和查表法。位運(yùn)算轉(zhuǎn)換法[20]基于有限域上的元素都可以采用二進(jìn)制矩陣進(jìn)行表示，它將生成矩陣轉(zhuǎn)換為GF(2)域空間上的01矩陣，因此整個計算過程只存在異或運(yùn)算，降低了計算的復(fù)雜度。

查表法是工程實現(xiàn)中一種常見方式，它通過預(yù)先生成有限域乘法表，在計算過程中避免復(fù)雜的多項式計算，只需查詢相應(yīng)的計算結(jié)果。在GF(2w)中，二維乘法表需要耗費O((2w)2)的存儲空間，隨著w的增大，該方式不再適用。由于有限域的非零元素均能用本原元的指數(shù)形式表示，進(jìn)而有限域的乘法能夠轉(zhuǎn)換為指數(shù)上的加法運(yùn)算。因此，在選定本原元的情況下，借助對數(shù)表（數(shù)字到指數(shù)的映射）和反對數(shù)表（指數(shù)到數(shù)字的映射），兩數(shù)的乘法運(yùn)算只需兩次對數(shù)表查詢得到相應(yīng)的指數(shù)數(shù)值，然后通過求和運(yùn)算獲得乘法結(jié)果的對應(yīng)指數(shù)數(shù)值，最后通過一次反對數(shù)表查詢，即可得到乘法運(yùn)算的結(jié)果。該方式只需O(2w)的存儲空間。查表法用訪存操作替代計算，將執(zhí)行速度的瓶頸從處理器轉(zhuǎn)移到內(nèi)存。最近，由于英特爾 SIMD（single instruction multiple data）技術(shù)[21]的發(fā)展，處理器中已經(jīng)普遍支持SIMD指令集，Plank等人[22]利用SIMD技術(shù)，將查詢表放入寄存器中，一次同時查詢多個乘法計算結(jié)果，使得乘法速度能夠達(dá)到8 GB/s。

隨著多核CPU和GPU的發(fā)展，并行執(zhí)行也被用于糾刪碼的計算加速[23]。針對多核CPU，文獻(xiàn)[24-26]分別完成了柯西RS編碼、EVENODD編碼[27]、RDP（row-diagonal parity）編碼[28]的并行設(shè)計，相比傳統(tǒng)RDP編碼，修復(fù)能夠提高40%的解碼速度。并行加速的難點在于如何進(jìn)行任務(wù)切分，使負(fù)載能夠均衡分布在每一個核上。目前，主要存在塊級別和等式級別的兩種切分方式：前者按塊對數(shù)據(jù)切分，采用數(shù)據(jù)并行的方式達(dá)到并行執(zhí)行的效果；而后者采用分配編碼等式的方式，使得每個核負(fù)責(zé)一定數(shù)量的編碼等式。相對于塊級別的并行，等式級別的并行可以使數(shù)據(jù)的訪問聚集在每一個核中的特定區(qū)域，能夠達(dá)到更均衡的分配。除此之外，在非對稱編碼的并行修復(fù)中，文獻(xiàn)[29]提出了一種新劃分方式，其發(fā)現(xiàn)修復(fù)過程中存在獨立的出錯塊，并據(jù)此對校驗矩陣切分，從而實現(xiàn)出錯的數(shù)據(jù)塊的并行修復(fù)。

由于RS編碼中涉及大量的矩陣向量乘運(yùn)算，相比CPU，GPU的數(shù)據(jù)矢量化和并行處理能力更加適合這種計算模型。Gibraltar[30]是基于GPU實現(xiàn)的RS編碼庫，相比Jerasure[31]，Gibraltar能夠達(dá)到更高的吞吐量，并且解碼性能幾乎與編碼性能一樣。

4 讀寫優(yōu)化

磁盤讀取的時間開銷受讀取的數(shù)據(jù)總量和并行度控制，通過降低I/O總量和提高I/O并行度兩種方式，均可以有效降低單盤負(fù)載，從而減少磁盤讀取的時間開銷。

4.1 降低I/O總量

陣列碼EVENODD和RDP是常見的RAID6（redundant arrays of independent disks）編碼，在其編碼布局中均存在水平校驗組和對角線校驗組。當(dāng)單個數(shù)據(jù)盤出錯時，傳統(tǒng)修復(fù)方式采用水平校驗組對數(shù)據(jù)進(jìn)行修復(fù)。如圖5（a）所示的RDP(6,2)數(shù)據(jù)布局，一共6塊磁盤，其中數(shù)據(jù)盤4塊。當(dāng)磁盤D0損壞時，采用水平校驗組，需要從D1、D2、D3、D4讀取16塊數(shù)據(jù)，該修復(fù)方式不僅未使用磁盤D5，同時忽略了兩種校驗組間存在的數(shù)據(jù)重疊。

文獻(xiàn)[32]中，Xiang等人對RDP恢復(fù)進(jìn)行了優(yōu)化，首次提出同時使用兩種校驗組的混合修復(fù)方式。如圖5（b）所示，對于丟失的4個數(shù)據(jù)塊，其中一半數(shù)據(jù)塊的修復(fù)采用水平校驗組，另一半數(shù)據(jù)塊修復(fù)采用對角線校驗組。該修復(fù)方式下，讀取的數(shù)據(jù)塊存在4塊重疊，需要讀取的數(shù)據(jù)塊數(shù)量降低為12，從而減少了25%的I/O讀取總量。混合修復(fù)方式通過尋找讀取過程中最大的重疊區(qū)域來降低數(shù)據(jù)讀取總量，基于同樣的思想，文獻(xiàn)[33-35]分別針對EVENODD編碼、X-Code編碼[36]和HDP（horizontal-diagonal parity）編碼[35]提出了單節(jié)點故障下的快速恢復(fù)算法。然而，上述的雙容錯編碼由于其特定的數(shù)據(jù)布局，只需考慮兩種校驗組，當(dāng)將該方式擴(kuò)展到容錯能力為3的STAR編碼[37]或者更通用的柯西RS編碼時，復(fù)雜的數(shù)據(jù)布局導(dǎo)致使用指數(shù)級的搜索時間來尋找最大的重疊區(qū)域[38]。為了降低時間開銷，Zhu等人提出一種更替修復(fù)算法[39]，其通過啟發(fā)式爬山算法來尋找次優(yōu)的修復(fù)方案。

Fig.5 Data layout and recovery method of RDP(6,2)圖5 RDP(6,2)編碼的數(shù)據(jù)布局及修復(fù)方式

為了將數(shù)據(jù)重疊的思想引入到RS編碼，Khan等人通過對標(biāo)準(zhǔn)RS編碼進(jìn)行改造，設(shè)計出一種新型編碼——循環(huán)RS編碼[38]。如圖6所示，標(biāo)準(zhǔn)RS編碼中多個校驗塊的生成來自對數(shù)據(jù)塊不同系數(shù)的選取，而循環(huán)RS編碼采取不同的生成方式，借助多個組合在一起的條帶，從相鄰條帶內(nèi)選取不同的數(shù)據(jù)塊形成新的校驗塊。當(dāng)磁盤D0出錯時，標(biāo)準(zhǔn)RS編碼恢復(fù)3個條帶需要讀取18個數(shù)據(jù)塊，而循環(huán)RS編碼由于存在3塊數(shù)據(jù)重疊，只需15個數(shù)據(jù)塊。

Fig.6 Comparison between rotated RS code and RS code圖6 循環(huán)RS編碼與RS編碼的對比

4.2 提高I/O并行度

傳統(tǒng)磁盤陣列在運(yùn)行過程中，為了及時替換出錯的磁盤，往往配備了熱備盤。然而在沒有發(fā)生磁盤失效的正常狀態(tài)下，熱備盤只能空閑等待。針對這個問題，文獻(xiàn)[40]中，Menon等人提出了分布式空閑塊的思想，不再設(shè)置專門的熱備盤，而使用磁盤中的空閑區(qū)域作為修復(fù)使用的存儲空間。在正常狀態(tài)下，該方式讓熱備盤也加入使用，所有的磁盤都能參與服務(wù)，提高了I/O處理能力；失效修復(fù)時，更多磁盤的參與降低了修復(fù)時間。

除了熱備盤的利用，分簇技術(shù)（parity declustering）[41]在恢復(fù)數(shù)據(jù)讀取總量不變的情況下，通過使用更多的磁盤，顯著降低了修復(fù)的時間開銷。以S2-RAID[42]編碼設(shè)計為例，S2-RAID在條帶大小不變的情況下，允許加入更多的磁盤參與修復(fù)。如圖7所示，當(dāng)磁盤D4出錯時，由于條帶的大小為3，{1.1，3.1，8.1}3個數(shù)據(jù)塊的修復(fù)需要讀取6個數(shù)據(jù)塊，傳統(tǒng)磁盤陣列的修復(fù)需要從兩塊磁盤上各讀取3塊數(shù)據(jù)，而S2-RAID使用6塊磁盤參與數(shù)據(jù)讀取，每塊磁盤只需讀取1個數(shù)據(jù)塊，大大降低了單盤上的負(fù)載。

Fig.7 Data layout of S2-RAID圖7 S2-RAID的數(shù)據(jù)布局

5 傳輸優(yōu)化

傳統(tǒng)RS(k,m)編碼對k個數(shù)據(jù)塊生成m個校驗塊，在修復(fù)某塊數(shù)據(jù)時需要將k個參與節(jié)點上的數(shù)據(jù)傳輸?shù)叫迯?fù)節(jié)點進(jìn)行數(shù)據(jù)重建。以RS(8,2)為例，數(shù)據(jù)塊大小為128 MB，在數(shù)據(jù)修復(fù)過程中，整個網(wǎng)絡(luò)需要傳輸1 GB的數(shù)據(jù)量。這給分布式存儲系統(tǒng)帶來了較大的網(wǎng)絡(luò)負(fù)擔(dān)。目前，傳輸優(yōu)化主要有減少單個參與節(jié)點傳輸量和減少參與節(jié)點數(shù)量兩種方式。

5.1 減少單個參與節(jié)點傳輸量

RS編碼將節(jié)點上存儲的數(shù)據(jù)作為單一整體進(jìn)行計算，因而修復(fù)過程需要參與節(jié)點讀取并傳輸所有數(shù)據(jù)。如果將節(jié)點上的數(shù)據(jù)劃分成子塊，以子塊作為最小編碼單位，則參與節(jié)點可以只傳輸部分子塊數(shù)據(jù)用于修復(fù)。

為了降低單個參與節(jié)點的數(shù)據(jù)傳輸量，Dimakis等人提出了一類新型編碼——再生碼（regenerating code，RGC）[11-12,43-44]。參數(shù)為(n,k,d)的再生碼，滿足任意k個節(jié)點能夠重建整個數(shù)據(jù)，單節(jié)點出錯時，從任意d(k≤d≤n-1)個節(jié)點上傳輸數(shù)據(jù)進(jìn)行修復(fù)。與RS編碼相比，雖然RGC編碼需要更多的節(jié)點參與修復(fù)，但是每個節(jié)點的數(shù)據(jù)傳輸量低，從而能夠降低整體的網(wǎng)絡(luò)傳輸量。目前，RGC編碼主要關(guān)注兩類：MSR（minimum storage regenerating）編碼和MBR（minimum bandwidth regenerating）編碼。MSR編碼與RS編碼同等存儲開銷下，具有更低的網(wǎng)絡(luò)開銷，而MBR編碼允許存儲更多的數(shù)據(jù)來獲得更低的網(wǎng)絡(luò)開銷。

干擾對齊（interference alignment）技術(shù)是構(gòu)造MSR編碼的一種主要方式，其思想是同時消去多個不需要的變量。如圖8所示的EMSR(4,2,3)（exact-repair MSR）編碼[43]，當(dāng)節(jié)點0出錯時，剩余的3個存活節(jié)點讀取本地存放的兩個編碼子塊，通過求和的方式將兩個子塊合并成單個子塊，并將其傳輸?shù)叫迯?fù)節(jié)點。此時，修復(fù)節(jié)點得到{B1+B2,A1+2A2+B1+B2,2A1+A2+B1+B2}3個編碼子塊。利用編碼子塊B1+B2可以同時消去剩余兩個編碼子塊中的B1和B2，從而得到{A1+2A2,2A1+A2},通過對這兩個編碼子塊運(yùn)算即可求解出丟失的數(shù)據(jù)子塊A1和A2。在該過程中，數(shù)據(jù)修復(fù)只需傳輸3個編碼子塊，而如果只利用節(jié)點1和節(jié)點2的數(shù)據(jù)進(jìn)行修復(fù)，需要傳輸4個編碼子塊。相比之下，EMSR編碼降低了25%的網(wǎng)絡(luò)傳輸量。Wu等人[11]最早將該技術(shù)用于MDS編碼的精確修復(fù)，不過只解決了k=2的MSR精確編碼。隨后，Suh等人[44]進(jìn)行改進(jìn)，解決了d≥2k-1的MSR精確編碼。

Fig.8 Recovery process of EMSR(4,2,3)code圖8 EMSR(4,2,3)編碼修復(fù)過程

矩陣乘（product matrix，PM）[12]是構(gòu)造再生碼的另一種主要方式，它可以同時構(gòu)造出MSR編碼和MBR編碼。再生碼的矩陣構(gòu)造由編碼矩陣和數(shù)據(jù)矩陣構(gòu)成，式（1）展示了PM-MBR(6,3,4)的矩陣構(gòu)造，與RS編碼相比，PM編碼采用數(shù)據(jù)矩陣替換了數(shù)據(jù)向量，并且在數(shù)據(jù)矩陣中存在重復(fù)的數(shù)據(jù)子塊。

圖9展示了PM-MBR(6,3,4)編碼的具體修復(fù)過程。當(dāng)節(jié)點出錯時，首先選擇出4個節(jié)點參與修復(fù)，讀取每個參與節(jié)點上的4個編碼子塊。然后，利用出錯節(jié)點對應(yīng)的編碼向量將每個參與節(jié)點的編碼子塊線性組合成單個傳輸子塊。最后，修復(fù)節(jié)點利用所有參與節(jié)點的編碼向量構(gòu)成解碼矩陣，通過其逆矩陣與傳輸子塊的乘積計算得到丟失的數(shù)據(jù)。在此過程中，節(jié)點修復(fù)只需傳輸4個編碼子塊，而傳統(tǒng)RS編碼需要傳輸9個編碼子塊，網(wǎng)絡(luò)傳輸量降低了55.6%。相比MSR編碼，PM-MBR能夠?qū)崿F(xiàn)更低的網(wǎng)絡(luò)傳輸量。

Fig.9 Recovery process of PM-MBR(6,3,4)code圖9 PM-MBR(6,3,4)編碼修復(fù)過程

在數(shù)據(jù)傳輸之前，再生碼需要參與節(jié)點讀取所有的編碼子塊，然后計算得到傳輸子塊。修復(fù)過程中，再生碼降低網(wǎng)絡(luò)開銷的同時，卻顯著增加了磁盤讀寫開銷和計算開銷。

為了解決上述問題，Rashmi等人[45]設(shè)計的PMRBT（product matrix reconstruct-by-transfer）編碼，通過預(yù)先存儲計算結(jié)果的方式，有效減少了在線修復(fù)時所需的計算和讀取。Chen等人[46]設(shè)計了F-MSR（functional MSR）編碼，修復(fù)出的數(shù)據(jù)為原始數(shù)據(jù)子塊的線性組合，能夠繼續(xù)保持?jǐn)?shù)據(jù)容錯能力不變。對于單節(jié)點的修復(fù)，F(xiàn)-MSR編碼只需從剩余所有存活節(jié)點上直接讀取一個編碼子塊，無需參與節(jié)點進(jìn)行計算。Shah等人[47]設(shè)計了MBR-RBT（MBR reconstructby-transfer）編碼，傳輸?shù)臄?shù)據(jù)即為磁盤讀取的數(shù)據(jù)，不僅降低了磁盤讀取開銷，而且也避免了計算開銷。

上述編碼解決了單節(jié)點故障下的傳輸優(yōu)化，然而在真實業(yè)務(wù)場景中，節(jié)點故障往往相互關(guān)聯(lián)，從而存在多節(jié)點同時故障的風(fēng)險[48-49]。在并發(fā)故障模型下，存儲系統(tǒng)可以延遲修復(fù)操作，累積故障節(jié)點數(shù)量超過一定閾值時，才開始執(zhí)行修復(fù)[50-51]。這種方式能夠在短暫故障下出現(xiàn)數(shù)據(jù)不可用時，避免無效的數(shù)據(jù)修復(fù)，同時增加了在傳輸節(jié)點上合并相關(guān)數(shù)據(jù)，減少傳輸量的可能性。除了從編碼設(shè)計上來降低單個節(jié)點的傳輸開銷，Subedi等人[52]從修復(fù)的機(jī)制出發(fā)，提出了一種結(jié)合緩存，共同合作，并主動重建的數(shù)據(jù)修復(fù)機(jī)制——CoARC（cooperative，aggressive recovery and caching）。在現(xiàn)有的分布式系統(tǒng)中，比如Hadoop，其客戶端觸發(fā)的降級讀操作獨立于自主的修復(fù)過程?？蛻舳嗽谑褂猛陻?shù)據(jù)后，將丟棄降級讀操作產(chǎn)生的重建數(shù)據(jù)。此時，單個客戶端對相同出錯條帶的訪問，或者多個客戶端觸發(fā)相同數(shù)據(jù)塊的修復(fù)，都將給系統(tǒng)的網(wǎng)絡(luò)和計算帶來極大的負(fù)荷。CoARC通過對修復(fù)的數(shù)據(jù)進(jìn)行緩存，過濾掉相同的重建操作，并且它在每次降級讀觸發(fā)的修復(fù)中，主動重建出錯條帶上所有不可用的數(shù)據(jù)。在這種提前修復(fù)和緩存的方式下，能夠顯著減少數(shù)據(jù)重建的次數(shù)，避免單個節(jié)點上相同數(shù)據(jù)的多次傳輸，從而有效降低整個網(wǎng)絡(luò)的傳輸量。

5.2 減少參與節(jié)點數(shù)量

傳統(tǒng)RS編碼將多個數(shù)據(jù)塊通過線性組合的方式生成全局校驗塊，數(shù)據(jù)修復(fù)時需要讀取的數(shù)據(jù)量與參與構(gòu)建的數(shù)據(jù)塊數(shù)量相等。在全局校驗塊數(shù)量固定的情況下，增加全局校驗組中數(shù)據(jù)塊的數(shù)量，能夠降低編碼的存儲開銷比率，卻會導(dǎo)致參與修復(fù)的節(jié)點數(shù)量增多，帶來網(wǎng)絡(luò)傳輸開銷和計算開銷的增加。

局部修復(fù)碼（local reconstruction code，LRC）[53]在傳統(tǒng)RS編碼的基礎(chǔ)上，引入局部分組的思想，將編碼塊劃分成多個小分組，分組內(nèi)部生成局部校驗塊進(jìn)行容錯保護(hù)。數(shù)據(jù)修復(fù)不再完全依賴于全局校驗組，優(yōu)先使用局部分組內(nèi)的數(shù)據(jù)進(jìn)行重建，從而通過減少參與節(jié)點的數(shù)量，降低了修復(fù)過程中的網(wǎng)絡(luò)傳輸開銷和磁盤讀取開銷。

目前存在多種LRC編碼方案，如圖10所示的Pyramid編碼[53]，數(shù)據(jù)塊被劃分成多個分組，每個分組內(nèi)引入一個局部校驗塊。由于分組之間形成嵌套關(guān)系，當(dāng)同一個小分組內(nèi)出現(xiàn)多個數(shù)據(jù)塊丟失時，Pyramid編碼可以借助其上層分組進(jìn)行修復(fù)，從而在多節(jié)點失效時依然可以降低參與節(jié)點的數(shù)量。由于多節(jié)點同時失效的概率較低，在Azure系統(tǒng)中目前只使用了一層局部校驗組[54]。

Fig.10 Pyramid code圖10 Pyramid編碼

Pyramid編碼只對數(shù)據(jù)塊引入了局部分組，全局校驗塊的修復(fù)依然需要讀取所有的數(shù)據(jù)。為了解決這個問題，Sathiamoorthy等人[55]在HDFS-Xorbas系統(tǒng)中對全局校驗塊也引入了局部分組，并選取特定的系數(shù)對存儲開銷進(jìn)行優(yōu)化。如圖11所示，HDFSXorbas系統(tǒng)為RS(10,4)編碼生成了3個局部校驗塊S1、S2和S3，通過特定系數(shù)的選取使S1+S2+S3=0，從而S3的值可以根據(jù)-S1-S2計算得到，S3作為隱式校驗塊無需存儲。在該方式下，任意單個節(jié)點的修復(fù)，只需訪問5個節(jié)點的數(shù)據(jù)，同時全局校驗塊的保護(hù)沒有引入額外的存儲開銷。實驗表明，HDFS-Xorbas以額外的14%(2/(10+4))的存儲開銷將網(wǎng)絡(luò)流量減少了50%。

LRC編碼通過局部分組的方式減少了修復(fù)訪問的節(jié)點數(shù)量，顯著降低了網(wǎng)絡(luò)帶寬和磁盤帶寬的占用。由于其實現(xiàn)簡單，只需在標(biāo)準(zhǔn)RS編碼的基礎(chǔ)上引入多個局部校驗塊，因而已被用于Microsoft[54]、Facebook[55]的存儲系統(tǒng)中。為了結(jié)合LRC編碼和RGC編碼各自的優(yōu)勢，Xia等人[56]將PM編碼和LRC編碼進(jìn)行混合使用，根據(jù)數(shù)據(jù)訪問熱度的不同，對于熱數(shù)據(jù)采用數(shù)據(jù)修復(fù)快的編碼，從而減少修復(fù)過程對前臺應(yīng)用帶來的延遲增大，而對于冷數(shù)據(jù)采用低存儲開銷的編碼，能夠有效減少存儲系統(tǒng)的空間開銷。在這種混編方式，整個存儲系統(tǒng)能夠同時獲得快速修復(fù)能力和高存儲空間利用率。

Fig.11 Encoding structure of HDFS-Xorbas圖11 HDFS-Xorbas編碼結(jié)構(gòu)

6 討論

服務(wù)領(lǐng)域的存儲系統(tǒng)需要提供連續(xù)不停機(jī)的存儲服務(wù)，因此數(shù)據(jù)修復(fù)操作必須在線進(jìn)行。一方面，基于糾刪碼的存儲系統(tǒng)的修復(fù)完成時間受到計算開銷、磁盤讀寫開銷和網(wǎng)絡(luò)傳輸開銷等因素的共同影響。另一方面，因為數(shù)據(jù)修復(fù)操作和前臺I/O操作共享甚至競爭存儲系統(tǒng)的I/O資源，數(shù)據(jù)修復(fù)操作對計算資源、磁盤帶寬和網(wǎng)絡(luò)帶寬的占用又會給前臺應(yīng)用性能帶來明顯干擾。因此，計算開銷、讀寫開銷和傳輸開銷是影響糾刪碼修復(fù)性能的三大關(guān)鍵因素。

為了提高糾刪碼存儲系統(tǒng)中數(shù)據(jù)修復(fù)效率，研究者主要從計算優(yōu)化、讀寫優(yōu)化和傳輸優(yōu)化等三方面開展工作。

（1）計算優(yōu)化方面：計算硬件的發(fā)展允許通過SIMD技術(shù)實現(xiàn)數(shù)據(jù)級并行，允許對多個數(shù)據(jù)單元同時執(zhí)行相同的操作，顯著加快了基于有限域運(yùn)算的編碼計算。而通過調(diào)整計算的執(zhí)行順序，避免了計算過程中不必要的重復(fù)計算，能夠有效減少計算量，進(jìn)一步降低計算開銷。

（2）讀寫優(yōu)化方面：通過合理選擇修復(fù)使用的條帶，讓數(shù)據(jù)恢復(fù)所需的數(shù)據(jù)出現(xiàn)重疊，使得讀取同一塊數(shù)據(jù)能夠用于多塊數(shù)據(jù)的修復(fù)，減少了數(shù)據(jù)讀取總量。另一方面，在不減少數(shù)據(jù)讀取總量的情況下，通過將更多磁盤引入到數(shù)據(jù)恢復(fù)中來，降低單盤上的讀取負(fù)載，從而減少整體的讀取時間。

（3）傳輸優(yōu)化方面：為了降低網(wǎng)絡(luò)傳輸量，研究者分別設(shè)計出RGC編碼和LRC編碼。RGC編碼通過降低單個參與節(jié)點的數(shù)據(jù)傳輸量，減少修復(fù)過程中的網(wǎng)絡(luò)開銷。LRC編碼通過引入局部分組，解除了修復(fù)參與節(jié)點數(shù)量與全局校驗組之間的關(guān)聯(lián)，以存儲開銷的增加換取修復(fù)參與節(jié)點數(shù)量的減少，從而降低修復(fù)過程中的磁盤讀寫開銷和網(wǎng)絡(luò)傳輸開銷。

為了全面對比現(xiàn)有的編碼方案，表1在以計算開銷、讀寫開銷、傳輸開銷作為修復(fù)性能評價標(biāo)準(zhǔn)的基礎(chǔ)上，結(jié)合容錯能力、存儲利用率等指標(biāo)對現(xiàn)有的編碼方案進(jìn)行了對比?？梢钥闯?，沒有一種方案可以很好地滿足所有指標(biāo)，LRC編碼的修復(fù)雖然在計算開銷、讀寫開銷和傳輸開銷上都取得良好表現(xiàn)，但它不是MDS編碼，節(jié)點的修復(fù)只能訪問固定的節(jié)點集合，而且局部校驗塊的計算也在其編碼階段引入了額外的計算量。MSR編碼和MBR編碼雖然能夠降低網(wǎng)絡(luò)開銷，但是卻引入了更多的計算開銷和讀寫開銷。雖然PM-RBT(12,6,11)和MBR-RBT(5,3,4)引入“修復(fù)即傳輸”的思想來降低計算開銷和讀寫開銷，但是PM-RBT編碼是基于MSR編碼的改進(jìn)，參數(shù)的選取受到一定程度的限制。而MBR-RBT編碼的修復(fù)需要從剩余所有節(jié)點上傳輸數(shù)據(jù)，在面臨多個節(jié)點失效時，無法降低網(wǎng)絡(luò)傳輸開銷。陣列碼RDP(6,2)、EVENODD(7,2)和循環(huán) RS(6,3)兩類編碼在磁盤開銷和網(wǎng)絡(luò)開銷方面都有降低，但均存在參數(shù)受限，容錯能力不高的缺陷。

Table 1 Comparison of various code scheme表1 各編碼方案的對比評價

7 總結(jié)與展望

本文分析了影響糾刪碼修復(fù)的關(guān)鍵因素，從計算、讀寫、傳輸三方面對優(yōu)化糾刪碼修復(fù)性能的關(guān)鍵技術(shù)進(jìn)行了探討。現(xiàn)有的編碼方案中大多未能兼顧計算、讀寫、傳輸三方面，如何從理論設(shè)計和系統(tǒng)實現(xiàn)上優(yōu)化實現(xiàn)這三目標(biāo)，還存在巨大的技術(shù)挑戰(zhàn)。

理論設(shè)計方面，同等容錯能力下，MSR編碼能夠在不增加額外存儲開銷的情況下，顯著降低網(wǎng)絡(luò)傳輸量。但是MSR編碼在高容錯能力時還存在參數(shù)選取受限，計算復(fù)雜和存儲利用率過低等缺陷。如何設(shè)計高編碼率、高可靠和低復(fù)雜度的MSR編碼將會是未來的一個重要研究方向。

系統(tǒng)實現(xiàn)方面，結(jié)合設(shè)備特性，對編碼方案進(jìn)行適配和調(diào)優(yōu)。編碼的理論效果與工程實現(xiàn)存在巨大的鴻溝，以磁盤讀取為例，再生碼修復(fù)過程需要完整讀取磁盤上的數(shù)據(jù)，是否存在只讀取部分子塊的可能性？如果存在，當(dāng)將原有的大塊連續(xù)讀取轉(zhuǎn)變?yōu)槎啻翁x之后，雖然讀取總量有所降低，但其帶寬卻可能下降。針對不同的編碼方案，如何在工程實現(xiàn)中對計算、讀取、傳輸三方面進(jìn)行適配和調(diào)優(yōu)，也將是未來研究的重點。

[1]Big data and what it means[EB/OL].[2016-11-27].http://www.uschamberfoundation.org/bhq/big-data-andwhat-it-means.

[2]Shvachko K,Kuang Hairong,Radia S,et al.The hadoop distributed file system[C]//Proceedings of the 26th Symposium on Mass Storage Systems and Technologies,Lake Tahoe,USA,May 3-7,2010.Washington:IEEE Computer Society,2010:1-10.

[3]Weil S A,Brandt S A,Miller E L,et al.Ceph:a scalable,high-performance distributed file system[C]//Proceedings of the 7th Symposium on Operating Systems Design and Implementation,Seattle,USA,Nov 6-8,2006.Berkeley,USA:USENIXAssociation,2006:307-320.

[4]Reed I S,Solomon G.Polynomial codes over certain finite fields[J].Journal of the Society for Industrial&AppliedMathematics,1960,8(2):300-304.

[5]Rashmi K V,Shah N B,Gu Dikang,et al.A solution to the network challenges of data recovery in erasure-coded distributed storage systems:a study on the Facebook warehouse cluster[C]//Proceedings of the 5th Workshop on Hot Topics in Storage and File Systems,San Jose,USA,Jun 27-28,2013.Berkeley,USA:USENIXAssociation,2013:1-5.

[6]Dimakis A G,Ramchandran K,Wu Yunnan,et al.A survey on network codes for distributed storage[J].Proceedings of the IEEE,2011,99(3):476-489.

[7]Li Jun,Li Baochun.Erasure coding for cloud storage systems:a survey[J].Tsinghua Science and Technology,2013,18(3):259-272.

[8]Luo Xianghong,Shu Jiwu.Summary of research for erasure code in storage system[J].Journal of Computer Research and Development,2012,49(1):1-11.

[9]Wang Yijie,Xu Fangliang,Pei Xiaoqiang.Research on erasure code-based fault-tolerant technology for distributed storage[J].Chinese Journal of Computers,2017,40(1):236-255.

[10]MacWilliams F J,Sloane N JA.The theory of error-correcting codes[M].Amsterdam:Elsevier North-Holland,Inc,1977.

[11]Wu Yunnan,Dimakis A G.Reducing repair traffic for erasure coding-based storage via interference alignment[C]//Proceedings of the 2009 International Symposium on Information Theory,Seoul,Jun 28-Jul 3,2009.Piscataway,USA:IEEE,2009:2276-2280.

[12]Rashmi K V,Shah N B,Kumar P V.Optimal exact-regenerating codes for distributed storage at the MSR and MBR points via a product-matrix construction[J].IEEE Transactions on Information Theory,2011,57(8):5227-5239.

[13]Blaum M,Roth R M.On lowest density MDS codes[J].IEEE Transactions on Information Theory,1999,45(1):46-59.

[14]Plank J S,Luo Jianqiang,Schuman C D,et al.A performance evaluation and examination of open-source erasure coding libraries for storage[C]//Proceedings of the 7th Conference on File and Storage Technologies,San Francisco,USA,Feb 24-27,2009.Berkeley,USA:USENIX Association,2009:253-265.

[15]Plank J S,Xu Lihao.Optimizing Cauchy Reed-Solomon codes for fault-tolerant network storage applications[C]//Proceedings of the 5th International Symposium on Network Computing and Applications,Cambridge,USA,Jul 24-26,2006.Washington:IEEE Computer Society,2006:173-180.

[16]Plank J S.XOR's,lower bounds and MDS codes for storage[C]//Proceedings of the Information Theory Workshop,Paraty,Brazil,Oct 16-20,2011.Piscataway,USA:IEEE,2011:503-507.

[17]Huang Cheng,Li Jin,Chen Minghua.On optimizing XOR-based codes for fault-tolerant storage applications[C]//Proceedings of the Information Theory Workshop,Tahoe City,USA,Sep 2-6,2007.Piscataway,USA:IEEE,2007:218-223.

[18]Hafner J L,Deenadhayalan V,Rao K K,et al.Matrix methods for lost data reconstruction in erasure codes[C]//Proceedings of the 4th Conference on File and Storage Technologies,San Francisco,USA,Dec 13-16,2005.Berkeley,USA:USENIXAssociation,2005:15-30.

[19]Zhang Guangyan,Wu Guiyong,Wang Shupeng,et al.CaCo:an efficient cauchy coding approach for cloud storage systems[J].IEEE Transactions on Computers,2016,65(2):435-447.

[20]Blomer J,Kalfane M,Karp R,et al.An XOR-based erasureresilient coding scheme[C]//ProcACM SIGCOMM,1995.

[21]Intel Corporation.Intel?64 and IA-32 architectures software developer manuals.combined volumes:1,2A,2B,2C,3A,3B and 3C.Order Number:325462-044US,2012.

[22]Plank J S,Greenan K M,Miller E L.Screaming fast Galois field arithmetic using intel SIMD instructions[C]//Proceedings of the 11th Conference on File and Storage Technologies,San Jose,USA,Feb 12-15,2013.Berkeley,USA:USENIX Association,2013:299-306.

[23]Chen H B,Fu Song.Parallel erasure coding:exploring task parallelism in erasure coding for enhanced bandwidth and energy efficiency[C]//Proceedings of the 2016 International Conference on Networking,Architecture and Storage,Long Beach,USA,Aug 8-10,2016.Washington:IEEE Computer Society,2016:1-4.

[24]Sobe P.Parallel Reed/Solomon coding on multicore processors[C]//Proceedings of the 2010 International Workshop on Storage Network Architecture and Parallel I/Os,Incline Village,USA,May 3,2010.Washington:IEEE Computer Society,2010:71-80.

[25]Feng Jun,Chen Yu,Summerville D.EEO:an efficient MDS-like RAID-6 code for parallel implementation[C]//Proceedings of the 33rd Conference on Sarnoff,Princeton,USA,Apr 12-14,2010.Piscataway,USA:IEEE,2010:16-20.

[26]Feng Jun,Chen Yu,Summerville D,et al.An extension of RDP code with parallel decoding procedure[C]//Proceedings of the Consumer Communications and Networking Conference,Las Vegas,USA,Jan 14-17,2012.Piscataway,USA:IEEE,2012:154-158.

[27]Blaum M,Brady J,Bruck J,et al.EVENODD:an efficient scheme for tolerating double disk failures in RAID architectures[J].IEEE Transactions on Computers,1995,44(2):192-202.

[28]Corbett P,English B,Goel A,et al.Row-diagonal parity for double disk failure correction[C]//Proceedings of the 3rd Conference on File and Storage Technologies,San Francisco,USA,Mar 31-Apr 2,2004.Berkeley,USA:USENIX Association,2004:1-14.

[29]Li Shiyi,Cao Qiang,Wan Shenggang,et al.PPM:a partitioned and parallel matrix algorithm to accelerate encoding/decoding process of asymmetric parity erasure codes[C]//Proceedings of the 44th International Conference on Parallel Processing,Beijing,Sep 1-4,2015.Washington:IEEE Computer Society,2015:460-469.

[30]Curry M L,Skjellum A,WardH L,et al.Gibraltar:a Reed-Solomon coding library for storage applications on programmable graphics processors[J].Concurrency and Computation:Practice and Experience,2011,23(18):2477-2495.

[31]Plank J S,Simmerman S,Schuman C D.Jerasure:a library in C/C++facilitating erasure coding for storage applications-Version 1.2,CS-08-627[R].Knoxville:University of Tennessee,2008.

[32]Xiang Liping,Xu Yinlong,Lui J C S,et al.Optimal recovery of single disk failure in RDP code storage systems[J].ACM SIGMETRICS Performance Evaluation Review,2010,38(1):119-130.

[33]Wang Zhiying,Dimakis A G,Bruck J.Rebuilding for array codes in distributed storage systems[C]//Proceedings of the Global Communication Conference Exhibition and Industry Forum,Miami,USA,Dec 6-10,2010.Piscataway,USA:IEEE,2011:1905-1909.

[34]Xu Silei,Li Runhui,Lee P P C,et al.Single disk failure recovery for X-code-based parallel storage systems[J].IEEE Transactions on Computers,2014,63(4):995-1007.

[35]Wu Chentao,He Xubin,Wu Guanying,et al.HDP code:a horizontal-diagonal parity code to optimize I/O load balancing in RAID-6[C]//Proceedings of the 41st International Conference on Dependable Systems Networks,Hong Kong,China,Jun 27-30,2011.Washington:IEEE Computer Society,2011:209-220.

[36]Xu Lihao,Bruck J.X-code:MDS array codes with optimal encoding[J].IEEE Transactions on Information Theory,1999,45(1):272-276.

[37]Huang Cheng,Xu Lihao.STAR:an efficient coding scheme for correcting triple storage node failures[J].IEEE Transactions on Computers,2007,57(7):889-901.

[38]Khan O,Burns R C,Plank J S,et al.Rethinking erasure codes for cloud file systems:minimizing I/O for recovery and degraded reads[C]//Proceedings of the 10th Conference on File and Storage Technologies,San Jose,USA,Feb 14-17,2012.Berkeley,USA:USENIX Association,2012:251-264.

[39]Zhu Yunfeng,Lee P P C,Xu Yinlong,et al.On the speedup of recovery in large-scale erasure-coded storage systems[J].IEEE Transactions on Parallel&Distributed Systems,2014,25(7):1830-1840.

[40]Menon J,Mattson D.Distributed sparing in disk arrays[C]//Proceedings of the 37th International Conference on Compion,San Francisco,USA,Feb 24-28,1992.Piscataway,USA:IEEE,1992:410-421.

[41]Holland M,Gibson G A.Parity declustering for continuous operation in redundant disk arrays[C]//Proceedings of the 5th International Conference on Architectural Support for Programming Languages and Operating Systems,Boston,USA,Oct 12-15,1992.New York:ACM,1992:23-35.

[42]Wan Jiguang,Wang Jibin,Yang Qing,et al.S2-RAID:a new RAID architecture for fast data recovery[C]//Proceedings of the 26th Symposium on Mass Storage Systems and Technologies,Incline Village,USA,May 3-7,2010.Washington:IEEE Computer Society,2010:1-9.

[43]Shah N B,Rashmi K V,Kumar P V,et al.Interference alignment in regenerating codes for distributed storage:necessity and code constructions[J].IEEE Transactions on Information Theory,2012,58(4):2134-2158.

[44]Suh C,Ramchandran K.Exact-repair MDS codes for distributed storage using interference alignment[C]//Proceedings of the 2010 IEEE International Symposium on Information Theory,Austin,USA,Jun 13-18,2010.Piscataway,USA:IEEE,2010:161-165.

[45]Rashmi K V,Nakkiran P,Wang Jingyan,et al.Having yourcake and eating it too:jointly optimal erasure codes for I/O,storage,and network-bandwidth[C]//Proceedings of the 13th Conference on File and Storage Technologies,Santa Clara,USA,Feb 16-19,2015.Berkeley,USA:USENIX Association,2015:81-94.

[46]Chen H C H,Hu Yuchong,Lee P P C,et al.NCCloud:a network-coding-based storage system in a cloud-of-clouds[J].IEEE Transactions on Computers,2014,63(1):31-44.

[47]Shah N B,Rashmi K V,Kumar P V,et al.Distributed storage codes with repair-by-transfer and nonachievability of interior points on the storage-bandwidth tradeoff[J].IEEE Transactions on Information Theory,2012,58(3):1837-1852.

[48]Ford D,Labelle F,Popovici F I,et al.Availability in globally distributed storage systems[C]//Proceedings of the 9th Conference on Operating Systems Design and Implementation,Vancouver,Canada,Oct 4-6,2010.Berkeley,USA:USENIX Association,2010:61-74.

[49]Schroeder B,Gibson G A.Disk failures in the real world:what does an MTTF of 1,000,000 hours mean to you?[C]//Proceedings of the 5th Conference on File and Storage Technologies,San Jose,USA,Feb 13-16,2007.Berkeley,USA:USENIXAssociation,2007:1-16.

[50]Pei Xiaoqiang,Wang Yijie,Ma Xingkong,et al.Repairing multiple failures adaptively with erasure codes in distributed storage systems[J].Concurrency and Computation:Practice and Experience,2016,28(5):1437-1461.

[51]Li Runhui,Lin Jian,Lee P P C.Enabling concurrent failure recovery for regenerating-coding-based storage systems:from theory to practice[J].IEEE Transactions on Computers,2015,64(7):1898-1911.

[52]Subedi P,Huang Ping,Liu Tong,et al.CoARC:co-operative,aggressive recovery and caching for failures in erasure coded hadoop[C]//Proceedings of the 45th International Conference on Parallel Processing,Philadelphia,USA,Aug 16-19,2016.Washington:IEEE Computer Society,2016:288-293.

[53]Huang Cheng,Chen Minghua,Li Jin.Pyramid codes:flexible schemes to trade space for access efficiency in reliable data storage systems[J].ACM Transactions on Storage,2013,9(1):3.

[54]Huang Cheng,Simitci H,Xu Yikang,et al.Erasure coding in windows Azure storage[C]//Proceedings of the Annual Technical Conference,Boston,USA,Jun 13-15,2012.Berkeley,USA:USENIXAssociation,2012:15-26.

[55]Sathiamoorthy M,Asteris M,Papailiopoulos D,et al.Xoring elephants:novel erasure codes for big data[J].Proceedings of the VLDB Endowment,2013,6(5):325-336.

[56]Xia Mingyuan,Saxena M,Blaum M,et al.Atale of two erasure codes in HDFS[C]//Proceedings of the 13th Conference on File and Storage Technologies,Santa Clara,USA,Feb 16-19,2015.Berkeley,USA:USENIX Association,2015:213-226.

附中文參考文獻(xiàn)：

[8]羅象宏,舒繼武.存儲系統(tǒng)中的糾刪碼研究綜述[J].計算機(jī)研究與發(fā)展,2012,49(1):1-11.

[9]王意潔,許方亮,裴曉強(qiáng).分布式存儲中的糾刪碼容錯技術(shù)研究[J].計算機(jī)學(xué)報,2017,40(1):236-255.

Review of Data Recovery in Storage Systems Based on Erasure Codes*

YANG Songlin,ZHANG Guangyan+
Department of Computer Science and Technology,Tsinghua University,Beijing 100084,China

A

TP393

+Corresponding author:E-mail:gyzh@tsinghua.edu.cn

YANG Songlin,ZHANG Guangyan.Review of data recovery in storage systems based on erasure codes.Journal of Frontiers of Computer Science and Technology,2017,11(10)：1531-1544.

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2017/11(10)-1531-14

10.3778/j.issn.1673-9418.1701044

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

*The National Natural Science Foundation of China under Grant Nos.61672315,F020803(國家自然科學(xué)基金);the National Basic Research Program of China under Grant No.2014CB340402(國家重點基礎(chǔ)研究發(fā)展計劃(973計劃)).

Received 2017-01,Accepted 2017-06.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2017-06-21,http://kns.cnki.net/kcms/detail/11.5602.TP.20170621.1105.002.html

YANG Songlin was born in 1992.He is an M.S.candidate at Tsinghua University.His research interests include network storage and big data processing,etc.

楊松霖（1992—），男，清華大學(xué)碩士研究生，主要研究領(lǐng)域為網(wǎng)絡(luò)存儲，大數(shù)據(jù)處理等。

ZHANG Guangyan was born in 1976.He is an associate professor and M.S.supervisor at Tsinghua University.His research interests include network storage,distributed computing and big data processing,etc.

張廣艷（1976—），男，清華大學(xué)副教授，主要研究領(lǐng)域為網(wǎng)絡(luò)存儲，分布式計算，大數(shù)據(jù)處理等。