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

楊松霖，張廣艷

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

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

楊松霖，張廣艷+

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

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

1 引言

隨著計(jì)算機(jī)技術(shù)的發(fā)展與互聯(lián)網(wǎng)的普及，數(shù)據(jù)呈現(xiàn)爆發(fā)式增長(zhǎng)，有研究表明，過(guò)去兩年里產(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)，如何解決這些問(wèn)題，對(duì)現(xiàn)代存儲(chǔ)系統(tǒng)提出了巨大的挑戰(zhàn)。多副本技術(shù)通過(guò)將數(shù)據(jù)的多個(gè)冗余副本分布在不同機(jī)器上，當(dāng)存儲(chǔ)節(jié)點(diǎn)發(fā)生故障時(shí)，自動(dòng)將服務(wù)切換到其他副本，從而實(shí)現(xiàn)數(shù)據(jù)的高可靠和高可用。然而隨著數(shù)據(jù)的持續(xù)增長(zhǎng)，在PB級(jí)別的數(shù)據(jù)中心，多副本技術(shù)會(huì)引入極大的存儲(chǔ)開(kāi)銷。比如，現(xiàn)有的分布式存儲(chǔ)系統(tǒng)，如HDFS（Hadoop distributed file system）[2]、Ceph[3]，普遍采用三副本的配置，這將占用原始數(shù)據(jù)的3倍存儲(chǔ)空間。

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

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

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

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

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

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

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

2.1 基本概念

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

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

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

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

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

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

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

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

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

2.2 編碼修復(fù)過(guò)程

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

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

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

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

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

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

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

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

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

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

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

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

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

3 計(jì)算優(yōu)化

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

3.1 減少計(jì)算量

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

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

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

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

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

Fig.4 Illustration of Subex圖4 Subex算法說(shuō)明

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

3.2 加速計(jì)算執(zhí)行

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

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

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

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

4 讀寫(xiě)優(yōu)化

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

4.1 降低I/O總量

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

文獻(xiàn)[32]中，Xiang等人對(duì)RDP恢復(fù)進(jìn)行了優(yōu)化，首次提出同時(shí)使用兩種校驗(yàn)組的混合修復(fù)方式。如圖5（b）所示，對(duì)于丟失的4個(gè)數(shù)據(jù)塊，其中一半數(shù)據(jù)塊的修復(fù)采用水平校驗(yàn)組，另一半數(shù)據(jù)塊修復(fù)采用對(duì)角線校驗(yàn)組。該修復(fù)方式下，讀取的數(shù)據(jù)塊存在4塊重疊，需要讀取的數(shù)據(jù)塊數(shù)量降低為12，從而減少了25%的I/O讀取總量。混合修復(fù)方式通過(guò)尋找讀取過(guò)程中最大的重疊區(qū)域來(lái)降低數(shù)據(jù)讀取總量，基于同樣的思想，文獻(xiàn)[33-35]分別針對(duì)EVENODD編碼、X-Code編碼[36]和HDP（horizontal-diagonal parity）編碼[35]提出了單節(jié)點(diǎn)故障下的快速恢復(fù)算法。然而，上述的雙容錯(cuò)編碼由于其特定的數(shù)據(jù)布局，只需考慮兩種校驗(yàn)組，當(dāng)將該方式擴(kuò)展到容錯(cuò)能力為3的STAR編碼[37]或者更通用的柯西RS編碼時(shí)，復(fù)雜的數(shù)據(jù)布局導(dǎo)致使用指數(shù)級(jí)的搜索時(shí)間來(lái)尋找最大的重疊區(qū)域[38]。為了降低時(shí)間開(kāi)銷，Zhu等人提出一種更替修復(fù)算法[39]，其通過(guò)啟發(fā)式爬山算法來(lái)尋找次優(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等人通過(guò)對(duì)標(biāo)準(zhǔn)RS編碼進(jìn)行改造，設(shè)計(jì)出一種新型編碼——循環(huán)RS編碼[38]。如圖6所示，標(biāo)準(zhǔn)RS編碼中多個(gè)校驗(yàn)塊的生成來(lái)自對(duì)數(shù)據(jù)塊不同系數(shù)的選取，而循環(huán)RS編碼采取不同的生成方式，借助多個(gè)組合在一起的條帶，從相鄰條帶內(nèi)選取不同的數(shù)據(jù)塊形成新的校驗(yàn)塊。當(dāng)磁盤D0出錯(cuò)時(shí)，標(biāo)準(zhǔn)RS編碼恢復(fù)3個(gè)條帶需要讀取18個(gè)數(shù)據(jù)塊，而循環(huán)RS編碼由于存在3塊數(shù)據(jù)重疊，只需15個(gè)數(shù)據(jù)塊。

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

4.2 提高I/O并行度

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

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

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

5 傳輸優(yōu)化

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

5.1 減少單個(gè)參與節(jié)點(diǎn)傳輸量

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

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

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

矩陣乘（product matrix，PM）[12]是構(gòu)造再生碼的另一種主要方式，它可以同時(shí)構(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ù)過(guò)程。當(dāng)節(jié)點(diǎn)出錯(cuò)時(shí)，首先選擇出4個(gè)節(jié)點(diǎn)參與修復(fù)，讀取每個(gè)參與節(jié)點(diǎn)上的4個(gè)編碼子塊。然后，利用出錯(cuò)節(jié)點(diǎn)對(duì)應(yīng)的編碼向量將每個(gè)參與節(jié)點(diǎn)的編碼子塊線性組合成單個(gè)傳輸子塊。最后，修復(fù)節(jié)點(diǎn)利用所有參與節(jié)點(diǎn)的編碼向量構(gòu)成解碼矩陣，通過(guò)其逆矩陣與傳輸子塊的乘積計(jì)算得到丟失的數(shù)據(jù)。在此過(guò)程中，節(jié)點(diǎn)修復(fù)只需傳輸4個(gè)編碼子塊，而傳統(tǒng)RS編碼需要傳輸9個(gè)編碼子塊，網(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ù)過(guò)程

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

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

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

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

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

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

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

Fig.10 Pyramid code圖10 Pyramid編碼

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

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

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

6 討論

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

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

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

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

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

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

Table 1 Comparison of various code scheme表1 各編碼方案的對(duì)比評(píng)價(jià)

7 總結(jié)與展望

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

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

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

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

[9]王意潔,許方亮,裴曉強(qiáng).分布式存儲(chǔ)中的糾刪碼容錯(cuò)技術(shù)研究[J].計(jì)算機(jī)學(xué)報(bào),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(國(guó)家自然科學(xué)基金);the National Basic Research Program of China under Grant No.2014CB340402(國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(973計(jì)劃)).

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)域?yàn)榫W(wǎng)絡(luò)存儲(chǔ)，大數(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)域?yàn)榫W(wǎng)絡(luò)存儲(chǔ)，分布式計(jì)算，大數(shù)據(jù)處理等。