鄢喜愛，張大方，楊金民，張波云

（1. 湖南大學信息科學與工程學院，湖南 長沙 410082；2. 湖南警察學院信息技術(shù)系，湖南 長沙 410138）

面向云存儲容錯系統(tǒng)的RS再生碼

鄢喜愛1,2，張大方1，楊金民1，張波云2

（1. 湖南大學信息科學與工程學院，湖南 長沙 410082；2. 湖南警察學院信息技術(shù)系，湖南 長沙 410138）

面向云存儲容錯系統(tǒng)提出了一種RS再生糾刪碼，該編碼繼承了RS編碼容多錯的可靠性，又能實現(xiàn)容三錯的高效性。對RS再生碼中單節(jié)點故障混合修復方法進行了介紹，并求出了混合修復時磁盤讀取數(shù)的理論下界。從理論上對RS再生碼的存儲開銷、譯碼效率、修復帶寬進行了性能評估。實驗結(jié)果表明，RS再生糾刪碼比同類糾刪碼的修復性能有較大的提升，特別是采用混合修復算法以后，系統(tǒng)單故障恢復時間下降20.8%～28.2%。關(guān)鍵詞：云存儲；容錯；糾刪碼；RS碼；RDP碼

1 引言

在云存儲系統(tǒng)中，數(shù)據(jù)中心一般由非常多的數(shù)據(jù)節(jié)點組成，存儲的數(shù)據(jù)達EB級甚至ZB級，數(shù)據(jù)失效已成為一種常態(tài)，構(gòu)建云存儲系統(tǒng)必須考慮容錯機制。存儲容錯通常采取復制和糾刪碼2種方法。復制方法操作簡單，故障恢復快，但存儲開銷成倍增長，并存在副本一致性維護難的問題；糾刪碼在故障恢復時會消耗更多的網(wǎng)絡(luò)帶寬，但在容錯能力和存儲空間上占有絕對優(yōu)勢[1,2]。由于云平臺上存儲的數(shù)據(jù)呈指數(shù)級增長，云存儲系統(tǒng)的容錯方法逐漸從復制向糾刪碼轉(zhuǎn)換。

糾刪碼可分為陣列碼和 RS（Reed-Solomon）編碼兩大類。陣列碼只有簡單的異或運算，運算速度快，但一般只能容單錯或雙錯。常用的陣列碼有EVENODD碼、RDP碼和X-Code碼等[3～5]。RS編碼是可以容多錯的編碼，并且具備MDS（maximum distance separable）性質(zhì)，常用于對存儲要求較高的存儲系統(tǒng)中。目前一些主流的云平臺（Microsoft Azure、Google、HDFS等）逐步采用了RS編碼。

標準 RS編碼建立在二元有限域G(2ω)上。在G(2ω)中，加法的運算只需利用簡單的XOR實現(xiàn)；乘法的運算較為復雜，若ω很小，可通過查詢對數(shù)表和反對數(shù)表獲得，否則，必須通過反復的迭代計算才能獲得[6]。對RS編碼的性能優(yōu)化主要體現(xiàn)在解決有限域上乘法計算難的問題，主要的相關(guān)工作如下。BURGISSER等[7]提出借助拉格朗日插值方法可使RS的運算復雜度大大降低，但限制了糾刪碼的長度，并且當數(shù)據(jù)量增大時，時間消耗量仍然很大。LACAN等[8]提出用2個Vandermonde矩陣來構(gòu)造編碼，比一個Vandermonde矩陣加一個單位矩陣的構(gòu)造效率要高。Plank等[9]提出將Vandermonde矩陣變成Cauchy矩陣，將整個RS編碼的運算全部轉(zhuǎn)化為XOR運算，但編譯碼的時間復雜度仍是平方級，分別為 O(nlogn)和 O(n2)。KALCHER S等[10]針對 RS編碼提出一個基于矢量的多項式乘法的實現(xiàn)算法，并采用GPU進行加速。KHANO 等[11]通過旋轉(zhuǎn)和移位來降低RS編譯碼的復雜度，但更新和重構(gòu)的效率都有不同程度的降低。李小兵等[12]提出了RS編碼與X-code編碼相結(jié)合生成再生碼，在雙錯情況下采用X-code編碼，有效地提高了修復效率，但X-code編碼可擴展性不好，重構(gòu)時必須按照一定的順序進行迭代，不方便進行并行操作。

云存儲屬于歸檔式存儲，對系統(tǒng)的容錯能力、編譯碼效率、重構(gòu)效率都有較高的要求。針對有中心的云存儲系統(tǒng)，本文設(shè)計了一種 RS碼與擴展RDP（ERDP）碼相結(jié)合的RS再生糾刪碼。再生碼兼顧了RS碼與陣列碼的優(yōu)良特性，當節(jié)點故障在三錯以上仍采用容錯能力強的RS編碼進行修復，當節(jié)點故障在三錯以下，啟用只有 XOR運算的ERDP編碼進行修復；因單節(jié)點故障是云存儲系統(tǒng)中的主要故障類型，本文討論了RS再生糾刪碼中單節(jié)點故障的磁盤讀取方法，求出了磁盤讀取數(shù)的理論下界。從理論上對RS再生糾刪碼的存儲開銷、譯碼效率、修復帶寬進行了分析，最后通過實驗對系統(tǒng)性能進行了評估。

2 RS再生糾刪碼

2.1 RS編碼

RS編碼時，將每個存儲節(jié)點被分為 t個存儲單元，每個存儲節(jié)點的字長是ωbit，假設(shè)數(shù)據(jù)盤有n個，分別{D1,D2,…,Dn}，校驗盤有 m 個，分別為{C1,C2,…,Cm}，校驗盤存儲單元的數(shù)據(jù)的生成函數(shù)為F。

RS校驗編碼的生成矩陣一般采用 Vandermonde矩陣[13]，定義F為m×n的Vandermonde矩陣，其中，fi,j=ji?1，則編碼的生成可轉(zhuǎn)化為以下形式。

圖1是當n=6，m=3時RS編碼的生成框架。

圖1RS編碼生成框架（n=6, m=3）

2.2 標準RDP編碼

標準 RDP編碼是一種容雙錯橫式陣列碼，所有編碼存放在一個(p?1)×(p+1)的陣列中，其中，p為大于2的素數(shù)，前p?1列存放的是原始數(shù)據(jù)塊，后2列存放的是冗余校驗數(shù)據(jù)[14]。RDP編碼的生成公式如式(1)和式(2)所示，其中，式(1)生成的是行校驗碼，式(2)生成的是正對角線校驗碼。

ci,j表示第 i行第 j列數(shù)據(jù)位的值，式(2)中＜i?j＞p表示(i?j)mod p 。

圖2是當p=5時，標準RDP編碼的形成過程描述。

圖2RDP碼的形成過程描述（p=5）

2.3 RS再生碼（RS-ERDP）構(gòu)造

2.3.1 有限域上的計算加速處理

設(shè)F(x)=fxm+fxm?1+…+fx1+f 為不可

m m?110

約多項式，G(2ω)上 2個元素 A和 B可表示為：A(x)=am?1xm?1+…+a1x1+a0和B( x)=bm?1xm?1+…+b x1+b，其中，(f f…f )、(aa…

10mm?10m?1m?2

a1a0)、(bm?1bm?2…b1b0)的取值范圍為{0,1}，則A( x)和B( x)在G(2ω)上乘積可表示為

對于不可約多項式有

根據(jù)式(4)和有限域上交換律，式(3)可改寫為

將式(5)改寫為矩陣形式

若用A(i)表示矩陣的列向量，則

根據(jù)式(6)和式(7)，對于矩陣 C的第 k行，當i≥ 1時，可得

式(8)可進一步簡化為

從式(9)可知，矩陣的第一列是(a0a1…am?1)，隨后每一列是前一列左移一位，若前一列高位有溢出，則與(f0f1…fm?1)進行XOR運算。

根據(jù)以上的推導，有限域上的乘法就可演化為只含移位和XOR運算的計算，計算復雜度明顯降低。后續(xù)標準的 RS編碼和譯碼計算將按此方法處理。如在G(24)中，A=5，B=12，設(shè)定不可約多項式為F( x)=x4+x+1，則乘積C可通過下面方法獲得。

A(0)=5=(a3a2a1a0)=(0101)2，=0，只需將A(0)左移1位，得A(1)=(1010)2；=1，將A(1)左移1位，再與(f0f1…fm?1)進行異或運算，A(2)=10100⊕10011=0111；因為=0，只需將A(2)左移1位，得A(3)=1110。計算結(jié)果與查詢對數(shù)表和反對數(shù)表一致。

2.3.2 擴展RDP編碼

為了增加 RDP編碼的容錯能力，本文構(gòu)建了一種可擴展 RDP編碼（ERDP）。編碼過程中，增加一個校驗節(jié)點，所有編碼存放在一個(p?1)×(p+2)的陣列中，p為大于2的素數(shù)，前p?1列存放的是原始數(shù)據(jù)塊，后3列存放的是冗余校驗數(shù)據(jù)。在后3列中，前2列存放的編碼與標準RDP的校驗碼一樣，最后一列存放的編碼為反對角線校驗碼，通過式(10)生成。

ci,j表示第i行第j列數(shù)據(jù)位的值，＜i+j ＞p表示(i+j)mod p 。

圖3是當p=5時，ERDP編碼的形成過程描述。

ERDP編碼是一個可容三錯的橫式陣列碼，在單錯或雙錯情況下，解碼方法與標準 RDP碼完全相同，當出現(xiàn)三錯時，啟用反對角線校驗碼。假設(shè)3個失效盤為Dx、Dy、Dz，3個修復的校驗算子分別為

圖3ERDP碼的形成過程描述（p=5）

2.3.3 RS再生碼的生成

結(jié)合RS編碼與ERDP編碼的特性，本文構(gòu)造了一種RS-ERDP的容錯糾刪碼。為了能容忍多錯，內(nèi)部編碼仍采用標準RS編碼，為了達到3個錯誤以內(nèi)高效地修復，外部采用只含 XOR運算的 RS再生碼，即外部采用在 RS編碼基礎(chǔ)上生成的ERDP編碼。由于RDP編碼對磁盤數(shù)提出了要求（p為素數(shù)），為了不破壞RS編碼對磁盤數(shù)無要求的優(yōu)良特性，在生成RS編碼之后，先分組再生成ERDP編碼。

假設(shè)RS編碼中數(shù)據(jù)盤數(shù)為n，RS編碼校驗盤數(shù)為m，ERDP編碼磁盤數(shù)為p+2，RS-ERDP編碼的構(gòu)造步驟如下。

表1一個RS單元的ERDP編碼生成過程

Step1將文件按條帶分成 n塊，利用Vandermonde矩陣生成RS編碼，一個條帶中會存在m+n個編碼塊。

Step2將條帶分組，每組編碼塊的個數(shù)為p?1(p 為素數(shù))，

Step3每組增加3個容錯節(jié)點，將每一組的原RS編碼生成ERDP編碼。其中，p列存放行校驗碼，p+1列存放正對角線校驗碼，p+2列存放反對角線校驗碼。

表 1是 n=3，m=3，p=7時，一個 RS單元的ERDP編碼生成情況。原始數(shù)據(jù)塊存儲在D0、D1、D2列，RS編碼存儲在D3、D4、D5列，ERDP編碼存儲在D6、D7、D8列。

3 RS-ERDP編碼中單節(jié)點故障修復的讀盤優(yōu)化

在云存儲系統(tǒng)中，單節(jié)點故障發(fā)生的概率占90%以上。一旦出現(xiàn)第1個失效節(jié)點，其他節(jié)點失效的概率會大大增加，更多節(jié)點失效會隨后發(fā)生[15]。因此，當系統(tǒng)中出現(xiàn)單節(jié)點失效時，需要盡快修復至正常狀態(tài)。影響單節(jié)點修復的關(guān)鍵因素是磁盤的讀取，讀取的磁盤數(shù)越少，則修復越快。如果失效節(jié)點是校驗節(jié)點，因為生成校驗時最多只參與了一次，所以只能重新生成編碼，磁盤的讀取沒有優(yōu)化空間；如果失效節(jié)點是數(shù)據(jù)節(jié)點，因為生成校驗時可能參與了多次，所以磁盤的讀取可以進行優(yōu)化。

在 RDP編碼中，傳統(tǒng)的節(jié)點故障修復的方法是通過單一的行校驗來進行修復，即讀取行校驗節(jié)點和存儲節(jié)點的所有數(shù)據(jù)，數(shù)據(jù)節(jié)點的讀取次數(shù)為(p?1)2。傳統(tǒng)的修復方法忽視了對角線校驗的存在，行校驗與對角線校驗會存在一些公共數(shù)據(jù)節(jié)點（同時參與了行校驗與對角線校驗）。對于公共數(shù)據(jù)節(jié)點，如果采用行校驗和對角線校驗進行混合修復，節(jié)點只需讀一次就可以了，這樣可以有效降低磁盤的讀取次數(shù)。XIANG等[16]提出了一種容雙錯RDP編碼中單節(jié)點故障的混合修復方法，行校驗和對角線校驗修復各取一半，得出數(shù)據(jù)節(jié)點的讀取次數(shù)的理論下界為

在 RS-ERDP編碼中，增加了一個反對角線校驗，存在的公共數(shù)據(jù)節(jié)點會更多。下面本文來探討容三錯 RS-ERDP編碼中單節(jié)點故障修復的讀盤優(yōu)化問題。

定義1

1) 設(shè)行校驗集合為

2) 設(shè)對角線校驗集合D為

3) 設(shè)反對角線校驗集合B為

從定義可知|R|=|D|=|B|=p?1。

引理1

證明1) 根據(jù)定義1可知，當r=(i?j)mod p時，若0≤r≤p?2，有di,＜i?j＞p∈Ri若i+r≡i+(i?j)=j(modp)，有di,＜i?j＞p∈Dj，從而可推導di,＜i?j＞p∈Ri∩Dj，也即Ri∩Dj≠?；由于 p是素數(shù)，有且僅有，即

2) 證明方法同1)。

假設(shè)在進行單節(jié)點修復時，選用3種校驗方案進行混合修復，假設(shè)有λ個行校驗組，ρ個對角線校驗組，γ個反對角線校驗組。又假設(shè)行校驗組與對角線校驗組公共節(jié)點數(shù)為SRD，行校驗組與反對角線校驗組公共節(jié)點數(shù)為SRB，對角線校驗組與反對角線校驗組公共節(jié)點數(shù)為SDB，總公共節(jié)點數(shù)為S。根據(jù)引理1，有

結(jié)合式(14)、式(15)有

總公共節(jié)點數(shù)的理論上界為1(p?1)2設(shè)混合3，修復時節(jié)點讀取數(shù)為W，單一修復數(shù)據(jù)節(jié)點的讀取次數(shù)為(p?1)2，則W的理論下界為

由式(17)可知，當采用行校驗、對角線校驗、反對角線校驗三者進行混合修復時，且3組的取值相近會逼近最少的磁盤讀取數(shù)

4 RS-ERDP編碼的性能分析

4.1 存儲開銷

假設(shè)原文件大小為1 MB，容錯時若采用目前常用的3副本完全復制容錯方式，則存儲空間占用3 MB；若采用RS編碼方式，每個編碼塊的大小為，則存儲空間占用

若假設(shè)原文件大小為50 MB，3副本完全復制、RS編碼、RS-ERDP編碼3種容錯的存儲開銷比較如圖4所示。從圖4(a)可看出，當p值固定，且m不變時，RS編碼、RS-ERDP編碼的存儲開銷都隨著n的增大而降低，S趨向于；從圖 4(b)可看出，當（n,m）固定時，RS-ERDP編碼的存儲開銷隨著 p的增大而降低，S趨向于

4.2 譯碼效率

為了便于比較，定義每個數(shù)據(jù)塊的大小為1 bit，譯碼效率每個數(shù)據(jù)源信息塊的平均異或次數(shù)（修復失效數(shù)據(jù)總異或次數(shù)與源數(shù)據(jù)比特數(shù)之比）。對容三錯的RS-ERDP編碼、RS編碼、EVENODD編碼的譯碼性能進行比較。

由文獻[5]得知，容三錯EVENODD編碼異或的總次數(shù)為(4ld?2+3p)(p?1)?3。由文獻[17]得知，基于XOR的RS編碼異或的總次數(shù)約為krL2，k表示碼的信息位，r表示冗余校驗位長度，L表示有限域的大小，為了便于比較，取相同的冗余校驗位r=3。

在容三錯RS-ERDP編碼中，根據(jù)式(11)～式(13)容易得知，3個校驗算子總異或次數(shù)之和為3p2?11p+6，將校驗算子作為方程組，通過消元計算出恢復三錯中一個失效列總異或次數(shù)之和為3(ld?1)(p?1)+(p?2)，剩余兩錯按常規(guī)的RDP容雙錯處理，總異或次數(shù)之和為4(p?2)?1[18]，RS-ERDP譯碼總異或次數(shù)為上述3部分之和。

圖4存儲開銷對比

數(shù)據(jù)源比特數(shù)為2(p?1)，RS-ERDP碼、RS碼、EVENODD碼的譯碼效率如圖5所示。

圖5譯碼效率比較

從圖 5可看出，當節(jié)點數(shù)量少（p＜11）時，RS-ERDP碼的譯碼效率在略高于EVENODD碼，但當節(jié)點數(shù)增長（p＞11）時，RS-ERDP碼的平均異或次數(shù)較EVENODD碼增長更緩慢，而且譯碼效率要高。RS碼的譯碼效率最低，主要與有限域的大小相關(guān)，并且隨著域的擴大而增加。

4.3 單節(jié)點故障修復帶寬

假設(shè)每個編碼塊的大小為1 MB，在RS碼中，根據(jù)RS（n,m）思想[19]，恢復一個失效數(shù)據(jù)塊，需要獲取n個數(shù)據(jù)塊，一個節(jié)點含有p?1個數(shù)據(jù)塊，所以期間若單節(jié)點發(fā)生故障其修復帶寬為(p?1)nMB ，對于傳統(tǒng)RDP碼單故障修復帶寬視p的大小決定，在RS-ERDP碼單故障修復時，本文采用混合修復的方法，由于行、對角線、反對角線存在公共節(jié)點，修復帶寬可進一步減少。RS碼、RDP碼、RS-ERDP碼單節(jié)點故障修復帶寬如表 2所示。RS-ERDP碼只是局部單元修復組修復，一般p＜n，所以RS-ERDP修復帶寬最低。

表2單節(jié)點故障修復帶寬比較

5 基于RS-ERDP編碼的云存儲容錯架構(gòu)

基于 RS-ERDP編碼的有中心云存儲容錯架構(gòu)如圖 6所示。存儲客戶端將待存儲的文件生成RS-ERDP編碼發(fā)至云端文件服務器。文件服務器包括元數(shù)據(jù)信息管理模塊和心跳感知模塊。元數(shù)據(jù)信息管理模塊負責處理編碼塊的名字空間、索引記錄、編碼塊到存儲節(jié)點映射等方面的信息。心跳感知模塊通過心跳感知存儲節(jié)點是否發(fā)生故障，并根據(jù)故障節(jié)點數(shù)來決定采用RS編碼還是RS-ERDP編碼，并將相關(guān)信息反饋給元數(shù)據(jù)信息管理模塊。心跳感知模塊執(zhí)行編碼選擇的方案如表3所示。文件讀取時，客戶端首先從服務器獲取文件編碼塊的偏移信息，再從存儲集群節(jié)點中讀取，讀取分為正常讀取和故障讀取2種方式。

表3編碼選擇方案

圖6基于RS-ERDP編碼的云存儲容錯架構(gòu)

文件服務器是系統(tǒng)架構(gòu)的核心部分，為增強其可靠性，本文采用雙機熱備的方式進行工作。兩臺同構(gòu)的服務器同時加電工作，一個任務同時發(fā)送到主從服務器。正常情況下從服務器不指揮工作，當主服務器發(fā)生物理故障時才接管指揮工作。主從服務器周期性地做檢查點并比較檢查點結(jié)果（狀態(tài)）是否相同，若相同，說明系統(tǒng)正常，若不相同，判定其中一臺服務器發(fā)生軟故障，主從服務器同時回卷到上一個檢查點狀態(tài)，重新執(zhí)行工作。

6 實驗性能評估

6.1 實驗環(huán)境

本實驗在開源的分布式存儲系統(tǒng)NCFS中進行[20]。NCFS連接各存儲設(shè)備,并根據(jù)配置的不同編碼機制將數(shù)據(jù)分塊并按照條帶編碼分散存儲在相關(guān)的存儲設(shè)備中。

實驗的硬件環(huán)境如表4所示。

表4實驗環(huán)境的硬件配置

6.2 節(jié)點故障修復時間比較

為了比較不同編碼的修復性能，本文在 NCFS存儲系統(tǒng)中分別實現(xiàn)了 RS碼、RS-cauchy碼、RS-ERDP碼，為了便于比較，還構(gòu)建了容三錯的RS-EVENODD碼。節(jié)點失效利用斷電的方式離線處理。實驗中通過調(diào)整p值的大小來比較系統(tǒng)的整體修復時間（下載數(shù)據(jù)時間、修復時間、寫數(shù)據(jù)時間）。實驗測試了不同編碼在參數(shù) p值不同的情況下的修復性能。實驗結(jié)果如圖7所示。

實驗結(jié)果表明，在容三錯的范圍內(nèi)，由于全部采用只含XOR運算的陣列碼來容錯，RS-ERDP碼的恢復性能較 RS編碼、RS-cauchy都有明顯的提升，而且隨著存儲節(jié)點、故障節(jié)點的增多，優(yōu)化性能越明顯。此外，隨著存儲規(guī)模地增大，RS-ERDP碼的修復性能變化平緩，非常適合于大規(guī)模的云存儲容錯。RS-ERDP碼與RS-EVENODD碼的比較結(jié)果是：節(jié)點數(shù)量?。╬＜11）時，RS-ERDP碼性能略低；當節(jié)點數(shù)量增多（p＞11）時，RS-ERDP碼性能要高于RS-EVENODD碼。這是由于RS-ERDP編碼多一列參與對角線校驗，節(jié)點數(shù)量少時，每比特譯碼的平均XOR次數(shù)略高于RS-EVENODD碼，當節(jié)點數(shù)增多時，每比特譯碼的平均XOR次數(shù)會低于RS-EVENODD碼，并且RDP的小寫性能和數(shù)據(jù)讀取平衡性優(yōu)于EVENODD。

圖7不同節(jié)點數(shù)情況下各類編碼的恢復性能比較

6.3 單節(jié)點故障修復性能比較

針對于單節(jié)點故障修復，本文對傳統(tǒng)的修復與混合修復進行了比較。實驗測試了 RS-ERDP編碼在參數(shù)p不同的情況下的修復性能。實驗中數(shù)據(jù)塊大小分別取值為 1024 KB、2048 KB，p∈{5,7,13,17,19,23}，傳統(tǒng)修復只采用行校驗，混合修復采用行校驗、對角線校驗、反對角線校驗三者混合修復，且3組取值接近，實驗結(jié)果如圖8所示。

圖8傳統(tǒng)修復與混合修復在不同節(jié)點個數(shù)情況下的性能對比

柱狀圖頂端的數(shù)字表示優(yōu)化百分比。實驗結(jié)果表明，當數(shù)據(jù)塊的大小為1024 KB時，數(shù)據(jù)修復時間減少20.8%～26.6%，當數(shù)據(jù)塊的大小為2048 KB時，數(shù)據(jù)修復時間減少25.8%～28.2%；從變化趨勢可看出，節(jié)點個數(shù)越多，優(yōu)化效果越好，這是由于存在更多公共數(shù)據(jù)塊的原因。理論的下界是減少33.3%，優(yōu)化的結(jié)果離理論下界還有一定的差距，這是由于混合修復時磁頭不是連續(xù)讀，在尋道上有一定的延時。

7 結(jié)束語

云存儲是大規(guī)模的海量存儲，必須具有可靠而又高效的容錯特性。本文設(shè)計了兼?zhèn)銻S碼與陣列碼優(yōu)良特性的 RS-ERDP容錯糾刪碼，當發(fā)生多個節(jié)點故障時可啟用內(nèi)部RS編碼進行修復，當節(jié)點故障在3個以下時可啟用只含XOR運算的ERDP碼，并討論了容三錯ERDP碼中單節(jié)點故障的磁盤讀取問題，通過混合修復降低了磁盤讀取數(shù)，求出了三容錯中磁盤讀取的理論下界。從理論和實驗 2個方面對編碼的容錯性能維護開銷進行了分析，結(jié)果表明 RS-ERDP容錯糾刪碼通過少量的額外存儲代價可獲得準確高效的數(shù)據(jù)修復效果，適應于對實時性、可靠性要求較高的云存儲系統(tǒng)。

[1]王意潔, 孫偉東, 周松, 等. 云計算環(huán)境下的分布存儲關(guān)鍵技術(shù)[J].軟件學報, 2012, 23(4): 962-986 WANG Y J, SUN W D, ZHOU S, et al. Key technologies of distributed storage for cloud computing[J]. Journal of Software, 2012, 23(4):962-986.

[2]譚鵬許, 陳越, 蘭巨龍, 等. 用于云存儲的安全容錯編碼[J]. 通信學報, 2014, 35(3): 109-115.TAN P X, CHEN Y, LAN J L, et al. Secure fault-tolerant code for cloud storage[J]. Journal on Communications, 2014, 35(3): 109-115.

[3]LUO J Q, MOCHAN S, XU L H, et al. Efficient encoding schedules for XOR-based erasure codes[J]. IEEE Transactions on Computers,2014, 63(9): 2259-2272.

[4]LI M, SHU J. On cyclic lowest density MDS array codes constructed using starters[J]. IEEE International Symposium on Information Theory, 2010, 41(3): 1315-1319.

[5]萬武南, 吳震, 陳運, 等. 一種基于3容錯陣列碼的RAID數(shù)據(jù)布局[J]. 計算機學報, 2007, 30(10): 1722-1730.WAN W N, WU Z, CHEN Y, et al. A data placement based on toleration on triple failures array codes in RAID[J]. Chinese Journal of Computers, 2007, 30(10): 1722-1730.

[6]KVASHENNIKOV V V. Application of fast polynoamial transformations over GALOIS GF(2m) fields in Reed-Solomon coding and decoding[J]. Telecommunications and Radio Engineering, 2012, 71(10):85-90.

[7]BURGISSER P, CLAUSEN M, SHOKROLLAHI MA. Algebraic complexity theory[M]. Springer Verlag Heidelberg. 1996.

[8]LACAN J, FIMES J. Systematic MDS erasure codes based on Vandermonde matrices[J]. IEEE Communications Letters, 2004, 8(9):570-582.

[9]PLANK J S, XU L.Optimizing cauchy Reed-Solomon codes for fault-tolerant network storage applications [C]//The 5th IEEE International Symposium on Network Computing and Applications (IEEE NCA06). Cambridge, MA, 2006: 1-8.

[10]KALCHER S, LINDENSTRUTH V. Accelerating Galois field arithmetic for Reed-Solomon erasure codes in storage applications[C]//IEEE International Conference on Cluster Computing. 2011: 290-298.

[11]KHAN O, BURNS R, PLANK J S. Rethinking erasure codes for cloud file systems: minimizing I/O for recovery and degraded reads[C]//USENIX. FAST 2012: 10th USENIX Conference on File and Storage Technologies. San Jose, CA, 2012: 1-14.

[12]李小兵, 許胤龍, 林一施, 等. 再生碼:一類適用于云存儲的準確修復編碼[J]. 計算機應用與軟件, 2014, 31(8): 241-244.LI X B, XU Y L, LIN Y S, et al. X regenerating codes: a class of accurate repair codes for cloud storage [J]. Computer Applications and Software, 2014, 31(8): 241-244.

[13]PLANK J S. A tutorial on Reed-Solomon coding for fault-tolerance in RAID-like systems[J]. Software: Practice and Experience, 1997, 27(9):995-1012.

[14]CORBETT P, ENGLISH B, GOEL A, et al. Row diagonal parity for double disk failure correction [C]//Proceedings of the Third USENIX Conference on File and Storage Technologies. Berkeley, CA, USA,2004: 1-14.

[15]邱麗娜, 王芳, 李楚, 等. 一種容三盤失效糾刪碼的單數(shù)據(jù)盤失效快速重建方法[J]. 計算機學報, 2013, 36(10): 2041-2051.QIU L N, WANG F, LI C, et al．EDS: a novel scheme for boosting single disk failure recovery of triple erasure correcting code storage systems[J]. Chinese Journal of Computers, 2013, 36(10): 2041-2051.

[16]XIANG L，XU Y, LUI J C S, et al. Optimal recovery of single disk failure in RDP code storage systems[J]. ACM Sigmetrics Performance Evaluation Review[J]. ACM, 2010, 38(1): 119-130.

[17]BLOEMER J M, KALFANE M, KARPINSKI R. An XOR-based erasure-resilient coding scheme[R]. Technical Report at ICSI, 1995.

[18]萬武南, 王拓, 索望. 一種三容錯數(shù)據(jù)布局[J]. 電子與信息學報,2013, 35(10): 2341-2346.WAN W N, WANG T, SUO W, et al. A data placement based on toleration triple failures[J]. Journal of Electronics amp; Information Technology, 2013, 35(10): 2341-2346.

[19]LI J, LI B. Erasure coding for cloud storage systems: a survey[J].Tsinghua Science and Technology, 2013, 18(3): 259-272.

[20]HU Y, YU M C, LEE P P C, et al. NCFS: on the praticatity and extensibility of a network-coding based distributed file system[C]// International Symposium on Network Coding. Beijing, 2011: 1-6.

RS regenerating codes for cloud storage fault-tolerant system

YAN Xi-ai1,2, ZHANG Da-fang1, YANG Jin-min1,ZHANG Bo-yun2
(1. College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082, China;2. Department of Information Technology,Hunan Police Academy, Changsha 410138, China)

RS(Reed-Solomon) regenerating erasure codes was proposed for cloud storage fault-tolerant system, which not only inherited the reliability of the RS encoding, but also achieved the high efficiency of tolerance three faults. Hybrid recovery method of the single fault node based on RS regenerating erasure codes was introduced. And the theoretical lower bound of the number of accessing disks was computed. In theory, the performance evaluation of the storage overhead, decoding efficiency, and repair bandwidth of the RS regenerating erasure codes was carried out. Experiments results show that the repair performance of RS regenerating erasure codes is improved greatly than the similar erasure codes, and the total recovery time of the system is reduced by 20.8%～28.2% using hybrid recovery algorithm in the case of single fault.

cloud storage, fault tolerance, erasure codes, RS encoding, RDP encoding

s:The National Natural Science Foundation of China(No.61472130，No. 61471169), The National Key Basic Research and Development Program of China (973 Program) (No.2012CB315805), Ministry of Public Security Public Security Theory and Soft Science Research Projects (No.2013LLYJHNST040), Hunan Provincial Science and Technology Department Research Projects(No.2014FJ3049), Hunan Provincial Key Laboratory of Network Investigational Technology Research Projects (No. 2016WLZC006)

TP391

A

10.11959/j.issn.1000-436x.2016197

2016-02-22；

2016-05-23

國家自然科學基金資助項目（No.61472130，No.61471169）；國家重點基礎(chǔ)研究發(fā)展計劃（“973”計劃）基金資助項目（No. 2012CB315805）；公安部公安理論及軟科學研究計劃基金資助項目（No.2013LLYJHNST040）；湖南省科技廳科研基金資助項目（No. 2014FJ3049）；網(wǎng)絡(luò)偵查技術(shù)湖南省重點實驗室基金資助項目（No. 2016WLZC006）

鄢喜愛（1972-），男，湖南長沙人，湖南大學博士生，湖南警察學院教授，主要研究方向為分布式存儲、容錯計算。

張大方（1959-），男，湖南長沙人，湖南大學教授、博士生導師，主要研究方向為可信系統(tǒng)與網(wǎng)絡(luò)、系統(tǒng)容錯。

楊金民（1967-），男，湖南長沙人，博士，湖南大學教授，主要研究方向為軟件工程、系統(tǒng)容錯。

張波云（1972-），男，湖南長沙人，博士，湖南警察學院教授，主要研究方向為信息安全、系統(tǒng)容錯。