糾刪碼存儲系統中數據修復方法綜述*

楊松霖，張廣艷

清華大學 計算機科學與技術系，北京 100084

糾刪碼存儲系統中數據修復方法綜述*

楊松霖，張廣艷+

清華大學 計算機科學與技術系，北京 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

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

糾刪碼；多副本；數據修復；性能優化

1 引言

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

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

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

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

Fig.1 Hierarchy of recovery performance optimization圖1 修復性能優化層級圖

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

2 基礎與關鍵因素

以下介紹糾刪碼的相關概念，闡述糾刪碼的修復過程，重點分析影響糾刪碼的數據修復性能的關鍵因素。

2.1 基本概念

為了便于理解，對本文出現的相關概念給出如下說明。

（1）數據塊：原始用戶數據被系統劃分形成的最小編碼單位。

（2）校驗塊：由數據塊經過相關運算得到的校驗數據。

（3）條帶：多個數據塊與其對應的校驗塊構成的冗余集合，如果一定數目的編碼塊丟失，可以通過對所在條帶中剩余編碼塊進行運算而重新生成。

（4）容錯能力：編碼方案中最大允許出錯的節點數，當出錯的節點數超過其容錯能力時，將無法修復丟失的數據。

（5）最大距離可分碼（maximum distance separable，MDS）：滿足Singleton邊界[10]的線性編碼方式。與其他編碼相比，它在同等容錯能力的情況下擁有最低的存儲開銷。

（6）參與節點：參與數據修復的節點。它需要讀取本地數據來參與數據重建。

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

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

2.2 編碼修復過程

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

目前，多數分布式存儲系統采用集中式編碼實現[9]，數據修復過程一般包含4個步驟：

（1）參與節點從本地磁盤讀取所需數據。

（2）為了實現減少數據傳輸量等目標，參與節點對數據進行本地合并后生成傳輸數據。

（3）參與節點將傳輸數據通過網絡傳輸到修復節點。

（4）修復節點接收到修復需要的所有數據，通過計算重建出丟失數據。

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

2.3 修復性能的影響因素

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

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

其中，Ddisk、Dnet分別代表參與節點讀取的數據量和網絡傳輸的數據量；Sdisk、Snet分別代表磁盤的讀取速度和網絡的傳輸速度；Tcom代表計算所花費的時間；k代表修復過程中訪問的節點數量。

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

基于以上分析，計算操作、磁盤讀寫和網絡傳輸是影響糾刪碼修復性能的關鍵因素。因此，從這三方面入手，對現有的優化技術進行歸納，并選取計算開銷、讀寫開銷、傳輸開銷作為糾刪碼修復性能的評價標準。

3 計算優化

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

3.1 減少計算量

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

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

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

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

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

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

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

3.2 加速計算執行

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

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

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

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

4 讀寫優化

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

4.1 降低I/O總量

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

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

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

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

Fig.6 Comparison between rotated RS code and RS code圖6 循環RS編碼與RS編碼的對比

4.2 提高I/O并行度

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

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

Fig.7 Data layout of S2-RAID圖7 S2-RAID的數據布局

5 傳輸優化

傳統RS(k,m)編碼對k個數據塊生成m個校驗塊，在修復某塊數據時需要將k個參與節點上的數據傳輸到修復節點進行數據重建。以RS(8,2)為例，數據塊大小為128 MB，在數據修復過程中，整個網絡需要傳輸1 GB的數據量。這給分布式存儲系統帶來了較大的網絡負擔。目前，傳輸優化主要有減少單個參與節點傳輸量和減少參與節點數量兩種方式。

5.1 減少單個參與節點傳輸量

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

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

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

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

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

圖9展示了PM-MBR(6,3,4)編碼的具體修復過程。當節點出錯時，首先選擇出4個節點參與修復，讀取每個參與節點上的4個編碼子塊。然后，利用出錯節點對應的編碼向量將每個參與節點的編碼子塊線性組合成單個傳輸子塊。最后，修復節點利用所有參與節點的編碼向量構成解碼矩陣，通過其逆矩陣與傳輸子塊的乘積計算得到丟失的數據。在此過程中，節點修復只需傳輸4個編碼子塊，而傳統RS編碼需要傳輸9個編碼子塊，網絡傳輸量降低了55.6%。相比MSR編碼，PM-MBR能夠實現更低的網絡傳輸量。

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

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

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

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

5.2 減少參與節點數量

傳統RS編碼將多個數據塊通過線性組合的方式生成全局校驗塊，數據修復時需要讀取的數據量與參與構建的數據塊數量相等。在全局校驗塊數量固定的情況下，增加全局校驗組中數據塊的數量，能夠降低編碼的存儲開銷比率，卻會導致參與修復的節點數量增多，帶來網絡傳輸開銷和計算開銷的增加。

局部修復碼（local reconstruction code，LRC）[53]在傳統RS編碼的基礎上，引入局部分組的思想，將編碼塊劃分成多個小分組，分組內部生成局部校驗塊進行容錯保護。數據修復不再完全依賴于全局校驗組，優先使用局部分組內的數據進行重建，從而通過減少參與節點的數量，降低了修復過程中的網絡傳輸開銷和磁盤讀取開銷。

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

Fig.10 Pyramid code圖10 Pyramid編碼

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

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

Fig.11 Encoding structure of HDFS-Xorbas圖11 HDFS-Xorbas編碼結構

6 討論

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

為了提高糾刪碼存儲系統中數據修復效率，研究者主要從計算優化、讀寫優化和傳輸優化等三方面開展工作。

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

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

（3）傳輸優化方面：為了降低網絡傳輸量，研究者分別設計出RGC編碼和LRC編碼。RGC編碼通過降低單個參與節點的數據傳輸量，減少修復過程中的網絡開銷。LRC編碼通過引入局部分組，解除了修復參與節點數量與全局校驗組之間的關聯，以存儲開銷的增加換取修復參與節點數量的減少，從而降低修復過程中的磁盤讀寫開銷和網絡傳輸開銷。

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

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

7 總結與展望

本文分析了影響糾刪碼修復的關鍵因素，從計算、讀寫、傳輸三方面對優化糾刪碼修復性能的關鍵技術進行了探討。現有的編碼方案中大多未能兼顧計算、讀寫、傳輸三方面，如何從理論設計和系統實現上優化實現這三目標，還存在巨大的技術挑戰。

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

系統實現方面，結合設備特性，對編碼方案進行適配和調優。編碼的理論效果與工程實現存在巨大的鴻溝，以磁盤讀取為例，再生碼修復過程需要完整讀取磁盤上的數據，是否存在只讀取部分子塊的可能性？如果存在，當將原有的大塊連續讀取轉變為多次跳讀之后，雖然讀取總量有所降低，但其帶寬卻可能下降。針對不同的編碼方案，如何在工程實現中對計算、讀取、傳輸三方面進行適配和調優，也將是未來研究的重點。

[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.

附中文參考文獻：

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

[9]王意潔,許方亮,裴曉強.分布式存儲中的糾刪碼容錯技術研究[J].計算機學報,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(國家自然科學基金);the National Basic Research Program of China under Grant No.2014CB340402(國家重點基礎研究發展計劃(973計劃)).

Received 2017-01,Accepted 2017-06.

CNKI網絡優先出版: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—），男，清華大學碩士研究生，主要研究領域為網絡存儲，大數據處理等。

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—），男，清華大學副教授，主要研究領域為網絡存儲，分布式計算，大數據處理等。