卞建超　查雅行　羅守山　李　偉

(北京郵電大學(xué)計算機(jī)學(xué)院　北京　100876)(災(zāi)備技術(shù)國家工程實驗室(北京郵電大學(xué))　北京　100876)

?

一種基于磁盤內(nèi)和磁盤間冗余的混合編碼方案

卞建超查雅行羅守山李偉

(北京郵電大學(xué)計算機(jī)學(xué)院北京100876)(災(zāi)備技術(shù)國家工程實驗室(北京郵電大學(xué))北京100876)

(bianjianchao@bupt.edu.cn)

云計算的發(fā)展和應(yīng)用對存儲系統(tǒng)的容錯能力提出了更高要求.糾刪碼被廣泛運用于計算磁盤級冗余以抵抗磁盤錯誤，但抵抗扇區(qū)錯誤時磁盤利用率較低，現(xiàn)有針對扇區(qū)錯誤的優(yōu)化方案只能抵抗較小數(shù)目或者特定分布的扇區(qū)錯誤.為此，利用MDS(maximum distance separable)碼的同態(tài)性質(zhì)，提出了一種將磁盤間冗余與磁盤內(nèi)冗余相結(jié)合的混合編碼(intra- and inter-device redundancy, IIDR).添加校驗磁盤抵抗磁盤錯誤的同時，在數(shù)據(jù)磁盤中添加全局校驗扇區(qū)以抵抗扇區(qū)錯誤，利用磁盤內(nèi)編碼添加本地校驗扇區(qū)，以優(yōu)化處理單個扇區(qū)錯誤的性能.最后，正確性證明及性能分析的結(jié)果表明所提方案能抵抗磁盤錯誤和任意分布的扇區(qū)錯誤，并且恢復(fù)單個扇區(qū)錯誤計算開銷低，更新性能較好，同時與傳統(tǒng)的磁盤內(nèi)編碼方案相比，有較高的磁盤利用率.

云計算；磁盤錯誤；潛在扇區(qū)錯誤；糾刪碼；磁盤內(nèi)冗余

隨著云計算相關(guān)技術(shù)的發(fā)展，各大廠商也陸續(xù)推出了商用的云服務(wù)，用戶量的激增、業(yè)務(wù)模式的擴(kuò)展、服務(wù)保障要求的提高，都對數(shù)據(jù)的可用性提出了更高要求，現(xiàn)有數(shù)據(jù)容錯機(jī)制的改進(jìn)加強(qiáng)迫在眉睫.造成數(shù)據(jù)丟失的設(shè)備故障可以分為磁盤錯誤(device failures)和扇區(qū)錯誤(sector failures)[1]，磁盤錯誤會導(dǎo)致出錯磁盤上的數(shù)據(jù)全部丟失，扇區(qū)錯誤則會導(dǎo)致單個扇區(qū)上的數(shù)據(jù)不可用.造成設(shè)備故障的因素有很多，介質(zhì)材料不合格、松動微粒引起的介質(zhì)劃痕、高飛寫入(high fly writes)造成的異常位模式、振動、磁頭觸及介質(zhì)、偏離磁道的讀寫都有可能造成設(shè)備故障[2].隨著使用垂直記錄技術(shù)的幾千兆級磁盤打入市場，其更高的磁錄密度、更窄的磁道寬度、更貼近磁盤的浮動磁頭，也更容易被軟顆粒污染物劃傷[2].此外，隨著固態(tài)硬盤(solid state drive, SSD)生產(chǎn)成本降低，大規(guī)模應(yīng)用成為可能，但與機(jī)械硬盤(hard disk drive, HDD)不同的是，SSD的單個扇區(qū)錯誤發(fā)生的概率是隨著寫操作的次數(shù)增長而增大的[3].

相對于設(shè)備錯誤，潛在扇區(qū)錯誤(latent sector errors, LSEs)在讀取該扇區(qū)的數(shù)據(jù)之前無法檢測，這種類型故障對數(shù)據(jù)的可用性造成了很大風(fēng)險.當(dāng)設(shè)備錯誤出現(xiàn)后，需要使用獨立冗余磁盤陣列(redundant arrays of independent disks, RAID)重建數(shù)據(jù)，但此時有磁盤出現(xiàn)LSEs就有可能造成數(shù)據(jù)重建失敗[4].

1　相關(guān)工作

針對扇區(qū)錯誤開展的研究有很多，目前主要有2種解決方案：1)scrubbing方案[5]，該方案是周期性地在后臺對各磁盤進(jìn)行掃描，發(fā)現(xiàn)LSEs后使用RAID冗余對其進(jìn)行修復(fù)，該方案已經(jīng)在NetApp的系統(tǒng)上部署商用了；2)IDR(intra-disk redundancy)方案，該方案在每個磁盤內(nèi)添加校驗冗余，并配合具有磁盤間冗余的RAID一起應(yīng)用.一些文件系統(tǒng)[6]在磁盤中對部分元數(shù)據(jù)進(jìn)行備份，IRON(internal robustness)文件系統(tǒng)[7]對每個文件添加校驗單元.Dholakia等人[8]提出了對1個磁盤中所有數(shù)據(jù)塊添加校驗冗余的方案，其實就是糾刪碼在單個磁盤內(nèi)的應(yīng)用，但以上方案都需要與磁盤間容錯的RAID搭配應(yīng)用.Iliadis等人[9]對比分析了scrubbing方案與IDR方案，指出scrubbing方案在數(shù)據(jù)量極為龐大的今天，周期地掃描每塊磁盤的做法顯然效率低下.然而，IDR方案在每個磁盤添加冗余的方法，其磁盤利用率也很低.特別是在同時出現(xiàn)磁盤錯誤和LSEs的混合錯誤模式下，以上方案都無法獨立解決，但傳統(tǒng)的糾刪碼為了容忍額外的扇區(qū)錯誤需要添加整塊的冗余磁盤，容錯效率同樣低下.

針對混合錯誤模式，2013年 Plank等人[10-11]提出了SD Codes，該方案在校驗磁盤的基礎(chǔ)上添加全局校驗扇區(qū)對抗扇區(qū)錯誤，如在添加1塊校驗磁盤和2個全局校驗扇區(qū)的情況下，SD Codes是介于RAID5與RAID6之間的解決方案.相對于傳統(tǒng)糾刪碼，該方案能夠容忍1個磁盤錯誤、2個扇區(qū)錯誤，而不用添加第2塊冗余校驗磁盤.相對于IDR方案在每塊磁盤上添加同等數(shù)量的校驗扇區(qū)，該方案在磁盤利用率上有很大優(yōu)勢.但該方案最多只能容忍每個條帶3個扇區(qū)錯誤，而且還有其他參數(shù)限制.

2014年Li等人[1,12]提出了STAIR Codes方案，該方案提出了一種更一般化的應(yīng)對混合錯誤模式的編碼方法，使用向量e表示扇區(qū)錯誤分布，在數(shù)據(jù)磁盤上添加相應(yīng)分布的全局校驗扇區(qū)以抵抗扇區(qū)錯誤.該方案需要2種MDS(maximum distance separable)碼分別承擔(dān)行編碼和列編碼，相比于SD Codes，該方案能夠容忍更多扇區(qū)錯誤，并能靈活套用任意系統(tǒng)MDS碼，相比于傳統(tǒng)的IDR方案，STAIR Codes有更高的磁盤利用率.但STAIR Codes需要向量來表示錯誤分布情況，即STAIR Codes只能容忍特定分布的s個扇區(qū)錯誤，在實際部署時有一定局限性.Schroeder等人[4]的扇區(qū)錯誤分析指出，不同類型的磁盤90%～98%的扇區(qū)錯誤是單獨出現(xiàn)，即存儲系統(tǒng)面臨的風(fēng)險絕大多數(shù)來自孤立的扇區(qū)錯誤.但在處理單個扇區(qū)錯誤時，STAIR Codes仍需讀取多個磁盤以恢復(fù)數(shù)據(jù)，IO及計算開銷比傳統(tǒng)IDR方案大.

針對現(xiàn)有方案的缺陷，本文提出了一種基于磁盤內(nèi)和磁盤間冗余的混合編碼算法(intra- and inter-device redundancy, IIDR)方案.本方案結(jié)合了磁盤內(nèi)編碼在修復(fù)小規(guī)模扇區(qū)錯誤時IO、計算開銷上的優(yōu)勢，又解決了其對抗大規(guī)模扇區(qū)錯誤時磁盤利用率急劇下降的缺點.相對于STAIR Codes方案，本方案犧牲了一定的磁盤利用率，解決了其不能抵抗任意扇區(qū)錯誤的問題，并優(yōu)化了在應(yīng)對小規(guī)模特別是單個扇區(qū)錯誤時的IO及計算性能.

2　混合編碼方案

本節(jié)首先給出預(yù)備知識及基本定義，然后分別介紹本方案編碼及數(shù)據(jù)恢復(fù)過程.

2.1預(yù)備知識

一個由n塊磁盤組成的存儲系統(tǒng)，包括一定數(shù)量的數(shù)據(jù)磁盤和校驗磁盤，其中校驗磁盤所存數(shù)據(jù)由數(shù)據(jù)磁盤編碼計算而來，與同一次編碼計算相關(guān)的所有數(shù)據(jù)稱為條帶(stripe)，存儲系統(tǒng)也可以看作為多個條帶的組合.同一磁盤上同屬一個條帶的數(shù)據(jù)集合稱為條塊(stripchunk)，條塊又由若干扇區(qū)(sectorelementsymbolblock)組成，個數(shù)記為r，扇區(qū)為編碼基本計算單元[13].如圖1所示，條塊由r個扇區(qū)組成，條帶由n個條塊組成，條帶可以看成由扇區(qū)組成的r×n矩陣.

Fig. 1　Relationship between sector, strip and stripe.圖1　扇區(qū)、條塊、條帶三者關(guān)系

如上所述，各條帶在編碼時相互獨立，可以以條帶為單位來進(jìn)行討論.存儲系統(tǒng)面臨的威脅有磁盤錯誤和扇區(qū)錯誤，可以把磁盤錯誤映射為條帶中的條塊錯誤，即整個條塊數(shù)據(jù)丟失或損壞.本文提出的方案能抵抗條帶中同時出現(xiàn)m(m

2.1.1校驗扇區(qū)分布

本方案的目標(biāo)是能抵抗s個扇區(qū)錯誤，需添加相同分布的校驗扇區(qū)(證明見第3節(jié))，而s個扇區(qū)錯誤的分布有很多種可能，所以添加的校驗扇區(qū)應(yīng)覆蓋其所有可能分布.如s=4時，可能的分布就有(4)，(3，1)，(2，2)，(1，1，1，1)，添加的校驗扇區(qū)分布應(yīng)為(4，2，1，1).若要抵抗s個扇區(qū)錯誤，需添加的校驗扇區(qū)的分布為

(證明見第3節(jié)).為了優(yōu)化單個扇區(qū)錯誤恢復(fù)性能，本方案在每個條塊中添加一個本地校驗扇區(qū)，所以本方案校驗扇區(qū)分布為

則全局校驗扇區(qū)分布實際為

本方案總計校驗扇區(qū)個數(shù)為s′+n.

2.1.2基本定義

本方案涉及使用2種系統(tǒng)MDS碼，一種為磁盤間編碼(行編碼)，采用(n+m′,n-m)碼作為行編碼算法，記為Crow；另一種為磁盤內(nèi)編碼(列編碼)，采用(r+s-1,r-1)碼作為列編碼算法，記為Ccol.所以將本方案命名為磁盤內(nèi)和磁盤間冗余編碼.

2.1.3同態(tài)性質(zhì)

根據(jù)定義，各列進(jìn)行編碼計算有：

當(dāng)0≤j≤n-m-1時，

當(dāng)0≤k≤m-1時，

當(dāng)0≤t≤s-2時，

2.2編碼過程

2.2.1示例

首先通過實例來介紹本方案編碼過程，圖2中取值n=8，m=2，r=6，s=4，即有6個數(shù)據(jù)條塊、2個校驗條塊，每個條帶添加分布為(3，1)的全局校驗扇區(qū)，此外每個條塊添加1個扇區(qū)作為本地校驗扇區(qū).行編碼、列編碼分別需采用(10，6)碼、(9，5)碼.具體步驟如表1所述，本方案編碼思想是利用MDS碼的同態(tài)性質(zhì)，配合置0的外部全局校驗扇區(qū)完成編碼計算.

Fig. 2　Encoding algorithm.圖2　編碼算法

2.2.2一般情況

Table 1　Detailed Steps for Encoding

根據(jù)全局校驗扇區(qū)的分布，本方案編碼由以下4步組成：

1) 計算0至n-m-m′-1列各校驗扇區(qū)

根據(jù)定義，計算條帶中0至r-s-1行、0至n-m-m′-1列不包含全局校驗扇區(qū).此類行和列可以直接進(jìn)行編碼計算：

① 計算行校驗扇區(qū)(不包含全局校驗扇區(qū)的行)，

其中0≤i≤r-s-1；

② 計算本地校驗扇區(qū)及相應(yīng)的臨時列數(shù)據(jù)扇區(qū)(不包含全局校驗扇區(qū)的列)，

其中0≤j≤n-m-m′-1.

2) 計算n-m-m′至n-m-2列各校驗扇區(qū)

算法1. 編碼循環(huán)算法.

初始化:

Rr;*行中數(shù)據(jù)完好的扇區(qū)數(shù)目*

Rc;*列中數(shù)據(jù)完好的扇區(qū)數(shù)目*

Sett=2,i=0,q=0,j=0,p=0.

t=t+i;

搜索第r+s-t行;

記錄Rr;

IfRr=n-mThen

對r+s-t行進(jìn)行編碼;

Else break;

End If

Forj=qtom′-2

搜索第n-m-m′+i列;

記錄Rc;

IfRc=r-1 Then

對n-m-m′+i列進(jìn)行編碼;

p=p+1;

Else break;

End If

End For

q=j+p;

p=0;

End For

輸出：從n-m-m′到n-m-2列.

3) 計算n-m-1列各校驗扇區(qū)

經(jīng)過第2步運算，r至r+s-m′-1行都存在n-m個已知扇區(qū)，可調(diào)用行編碼算法進(jìn)行計算，

其中0≤t≤s-m′-1；

全局校驗扇區(qū)全部計算完畢.

4) 計算n-m至n-1列(磁盤校驗條塊)剩余扇區(qū)

其中0≤k≤m-1.

至此，條帶中的校驗扇區(qū)全部計算完畢.

2.3數(shù)據(jù)恢復(fù)過程

2.3.1示例

圖3為本方案數(shù)據(jù)恢復(fù)示例，其中取值n=8，m=2，r=6，s=4，圖3中黑色表示出錯扇區(qū)，即出現(xiàn)2個條塊錯誤及分布為(4，2，1，1，1，1)的扇區(qū)錯誤，即該參數(shù)下本方案能抵抗最嚴(yán)重錯誤情況，通過這個示例來闡述本方案數(shù)據(jù)恢復(fù)算法，具體操作如表2所示.

Fig. 3　Data recovery algorithm.圖3　數(shù)據(jù)恢復(fù)算法

本方案數(shù)據(jù)恢復(fù)思路是先使用本地校驗扇區(qū)修復(fù)單個扇區(qū)錯誤，再結(jié)合置0的外部全局校驗扇區(qū)計算出部分臨時行扇區(qū)，使得部分列達(dá)到列編碼條件并恢復(fù)，依次類推直到數(shù)據(jù)完全恢復(fù).

Table 2　Detailed Steps for Data Recovery

2.3.2一般情況

本方案為了能抵抗s個任意分布的扇區(qū)錯誤，添加了大于s的校驗扇區(qū)，實際容錯上限為校驗扇區(qū)相同分布的扇區(qū)錯誤(證明見第3節(jié))，即出現(xiàn)m個條塊錯誤和分布為的扇區(qū)錯誤.

1) 修復(fù)簡單錯誤

列內(nèi)只存在單個扇區(qū)錯誤或者行內(nèi)扇區(qū)錯誤數(shù)為m的情況，即恢復(fù)數(shù)據(jù)只涉及1次解碼計算，稱為簡單錯誤.首先處理列內(nèi)只存在單個扇區(qū)錯誤的情況，很顯然此類列存在r-1個完好扇區(qū)，可調(diào)用列編碼算法Ccol(r+s-1,r-1)恢復(fù)數(shù)據(jù)，如表2的Step1～4；接著處理扇區(qū)錯誤數(shù)為m的行，可知該行完好扇區(qū)個數(shù)為n-m，可調(diào)用行編碼算法Crow(n+m′,n-m)恢復(fù)數(shù)據(jù)，如表2中的Step5～6.

2) 修復(fù)連續(xù)扇區(qū)錯誤

① 修復(fù)m+1至m+m′-1 列

② 修復(fù)第m列(s個扇區(qū)錯誤)

此時，r至r+s-m′-1行都存在n-m個已知扇區(qū)，可調(diào)用行編碼算法進(jìn)行計算，

其中0≤t≤s-m′-1.

使得第m列擁有r-1個已知扇區(qū)，可調(diào)用列編碼算法Ccol(r+s-1,r-1)恢復(fù)該列剩余扇區(qū)，

3) 修復(fù)0至m-1列(條塊錯誤)

經(jīng)過步驟1，條塊錯誤所在列仍有s個扇區(qū)錯誤，經(jīng)過步驟2計算此類列存在r-1個已知扇區(qū)，可調(diào)用列編碼算法恢復(fù)所有扇區(qū)錯誤：

其中0≤j≤m-1.

至此，全部數(shù)據(jù)均被修復(fù).

上述算法為本方案能夠容忍的最嚴(yán)重錯誤情況，很顯然針對一般錯誤情況(m個磁盤錯誤，任意分布的s個扇區(qū)錯誤)本方案仍能勝任，具體正確性證明會在第3節(jié)進(jìn)行闡述.

3　正確性證明

引理1.s個扇區(qū)錯誤所有分布的疊加為

證明. 設(shè)s個扇區(qū)錯誤分布為(e0,e1,…,em′-1)，其中1≤m′≤s，且有e0+e1+…+em′-1=s，為便于討論設(shè)e0≥e1≥…≥em′-1.按照m′不同的取值來進(jìn)行討論驗證：

1)m′=1，即s個扇區(qū)錯誤分布在同一磁盤，e0=s；

2)m′=2，則分布為(e0,e1)，可知e0+e1=s且e0≥e1，則當(dāng)e0=e1=s2時e1取值最大，由于e0，e1為整數(shù)且e0≥e1，則e1的取值上限為s；

3)m′=3，則分布為(e0,e1,e2)，可知e0+e1+e2=s且e0≥e1≥e2，則當(dāng)e0=e1=e2=s3時e3取值最大，由于e0，e1，e2為整數(shù)且e0≥e1≥e2，則e2的取值上限為s.

證畢.

引理2. 本方案能抵抗與校驗扇區(qū)相同分布的扇區(qū)錯誤.

根據(jù)命題，此時存在同樣分布的扇區(qū)錯誤，其中單個扇區(qū)錯誤可以用本地校驗扇區(qū)獨立恢復(fù)，剩余需要恢復(fù)分布為(λ0+1,λ1+1,…,λm′-1+1)的錯誤扇區(qū).可知此時計算條帶中每行都存在n-m-m′個可用扇區(qū)，最后λ0行都存在m′個外部全局校驗扇區(qū)(置0)，滿足行編碼條件，調(diào)用Crow恢復(fù)最后λ0行的剩余扇區(qū)(臨時列校驗扇區(qū)).λ0+1個錯誤扇區(qū)所在列存在r-1個可用扇區(qū)(r-λ0-1個數(shù)據(jù)扇區(qū)、λ0個臨時列校驗扇區(qū))，滿足列編碼條件，調(diào)用Ccol能夠恢復(fù)該列λ0+1個錯誤扇區(qū).

此時，剩余行存在n-m-m′+1個可用扇區(qū)，配合λ1-λ0行都存在m′-1個外部全局校驗扇區(qū)，滿足行編碼條件，調(diào)用Crow恢復(fù)λ1-λ0行所有扇區(qū).計算后λ1+1個錯誤扇區(qū)所在列滿足列編碼條件，能夠恢復(fù)該列λ1+1個錯誤扇區(qū).

恢復(fù)完λi-1(1≤i≤m′-1)個錯誤扇區(qū)所在列后，配合λi-λi-1行都存在m′-i個外部全局校驗扇區(qū)，可以調(diào)用Crow計算λi-λi-1行所有扇區(qū)，由此可以調(diào)用Ccol恢復(fù)λi+1個扇區(qū)錯誤所在列的所有數(shù)據(jù).依次循環(huán)計算可以將全部錯誤扇區(qū)恢復(fù).

因此，本方案能抵抗與校驗扇區(qū)相同分布的扇區(qū)錯誤.

證畢.

定理1. 本方案若添加分布為

的校驗扇區(qū)，則能抵抗s個任意分布的扇區(qū)錯誤.

證明. 根據(jù)引理2，若想抵抗s個扇區(qū)錯誤，需添加相同分布的s個校驗扇區(qū).根據(jù)引理1可知s個扇區(qū)錯誤所有分布的疊加為

很顯然分布本方案添加的校驗扇區(qū)包含該值.

因此，本方案若添加分布為

的校驗扇區(qū)，則能抵抗s個任意分布的扇區(qū)錯誤.

證畢.

4　性能分析

如第1節(jié)所述，本文提出了一種基本磁盤間和磁盤內(nèi)冗余的混合編碼算法(IIDR).本節(jié)從磁盤利用率、計算開銷、更新性能3個方面，通過與經(jīng)典的磁盤內(nèi)冗余方案IDR及混合編碼方案SD Codes，STAIR Codes做對比，來分析本方案各方面性能的優(yōu)劣.

4.1磁盤利用率

隨著數(shù)據(jù)爆炸性的增長，磁盤利用率成為衡量編碼算法優(yōu)劣的重要指標(biāo).由于STAIR Codes，IDR及本方案在同等容錯能力下校驗磁盤數(shù)目一致，所以數(shù)據(jù)磁盤中校驗扇區(qū)的多少決定了一個方案磁盤利用率的高低，所需校驗扇區(qū)越多則磁盤利用率越低.圖4中取值n=8，r=6，分別計算了抵抗4個扇區(qū)錯誤的5種分布情況下各方案單個條帶的校驗扇區(qū)數(shù)目.

如圖4所示，抵抗特定分布的扇區(qū)錯誤，STAIR Codes只需添加對應(yīng)分布的校驗扇區(qū)，即只需4個校驗扇區(qū)，該方案所需添加的校驗扇區(qū)最少；本方案除了添加全局校驗扇區(qū)，還在每個條塊中都添加了本地校驗扇區(qū)，所以本方案校驗扇區(qū)數(shù)略大于STAIR Codes方案；IDR方案需要在每個條塊添加最大錯誤數(shù)的本地校驗扇區(qū)，即校驗扇區(qū)數(shù)目為最大錯誤數(shù)與n之積，所以隨著最大錯誤數(shù)的增大，IDR方案變化十分明顯.可以看出在抵抗特定分布扇區(qū)錯誤時，本方案磁盤利用率介于STAIR Codes與IDR方案之間.

Fig. 4　The number of parity sectors for different e.圖4　校驗扇區(qū)數(shù)目

由于STAIR Codes方案不支持任意扇區(qū)錯誤分布，只能對比IDR方案與本方案在面對任意錯誤分布時的磁盤利用率.本方案添加的校驗扇區(qū)分布為

則數(shù)目可以表示為

圖5中分別取值n=8，16，32，分析對比2種方案在s不同的取值下校驗扇區(qū)數(shù)量的變化.

Fig. 5　The number of parity sectors for different s.圖5　s不同取值下校驗扇區(qū)數(shù)目

如圖5所示，同一n取值下，2方案所需校驗扇區(qū)數(shù)量與s成正比，IDR方案所需校驗扇區(qū)更多，且增長速率也大于本方案.由于2個方案都是在每個磁盤上添加校驗扇區(qū)，在同一s取值下，2方案所需校驗扇區(qū)數(shù)量與n成正比，同樣IDR方案所需校驗扇區(qū)多于本方案，且增長速率大于本方案.綜上所述，在抵抗任意錯誤分布的情況下，本方案的磁盤利用率優(yōu)于IDR方案.

4.2計算開銷

為了量化分析編解碼算法的計算開銷，將算法分解成若干步基本操作Mult_XORs[14]，以步驟的多少來衡量一個算法計算開銷的大小 ，很顯然分解的操作越少，則計算開銷較小.基本操作Mult_XORs(R1,R2,α)定義為若干字節(jié)數(shù)據(jù)R1與常量α相乘，所得的值與R2異或求和.如：(n,k)碼的編碼過程可以分解成k×(n-k)步基本操作.

4.2.1修復(fù)混合錯誤的計算開銷

本方案在編解碼過程中，共調(diào)用了n次縱向編碼算法Ccol(r+s-1,r-1)，計算產(chǎn)生了n個本地校驗扇區(qū)、s′個全局校驗扇區(qū)、(n-m)×(s-1)-s′個臨時校驗扇區(qū)、m×(s-1)個行校驗扇區(qū).調(diào)用r-1次橫向編碼算法Crow(n+m′,n-m)，計算產(chǎn)生了m×(r-s)個行校驗扇區(qū)、m×(s-1)+s′個臨時校驗扇區(qū).分解成基本操作Mult_XORs，步驟數(shù)β為

圖6為s=4時5中不同錯誤分布情況下本方案與STAIR Codes方案計算開銷對比，其中n=8，m=2，r=8，16，24.如圖6所示，本方案總體性能與STAIR-Upstairs算法相近，由于本方案添加了本地校驗扇區(qū)，在修復(fù)單個扇區(qū)錯誤時不需要調(diào)用全局校驗扇區(qū)，只需進(jìn)行1次解碼運算，所以在抵抗單個扇區(qū)錯誤較多的分布時，本方案β值略小于STAIR-Upstairs算法.

圖7為s，n，r不同取值時β的變化情況.如圖7所示，β與s成正比，且隨著n，r的取值增大，β的增長速率變大.可以看出抵抗s個扇區(qū)錯誤，編碼條帶的規(guī)模也影響了計算性能，規(guī)模越大，開銷越大.

4.2.2恢復(fù)單個扇區(qū)錯誤的計算開銷

假設(shè)條帶中出現(xiàn)m個條塊錯誤(對應(yīng)磁盤錯誤)及單個扇區(qū)錯誤，對比分析STAIR Codes方案的Upstairs，Downstairs兩種算法與本方案恢復(fù)錯誤數(shù)據(jù)的計算開銷.各方案恢復(fù)條塊錯誤的操作基本一致，不同之處在于恢復(fù)單個扇區(qū)錯誤.本方案只需要扇區(qū)錯誤所在條塊調(diào)用1次列編碼算法即可完成扇區(qū)數(shù)據(jù)恢復(fù)，總計操作數(shù)為

Fig. 6　The number of Mult_XORs of STAIR Codes，IIDR versus different e.圖6　抵抗不同分布錯誤時STAIR Codes，IIDR方案Mult_XORs操作數(shù)

Fig. 7　The number of Mult_XORs of IIDR.圖7　IIDR方案Mult_XORs操作數(shù)變化圖

而STAIR Codes方案的Upstairs，Downstairs兩種算法都需要結(jié)合外部全局校驗扇區(qū)來恢復(fù)扇區(qū)數(shù)據(jù)，總計操作數(shù)分別為

從公式上來看，本方案計算開銷小于其他2種算法.圖8是n，r取不同值時本方案與STAIR Codes方案3種算法恢復(fù)計算操作數(shù)對比.

Fig. 8　Compute overhead of a single sector error recovery.圖8　單個扇區(qū)錯誤恢復(fù)計算開銷

如圖8所示，由于本方案添加了本地磁盤校驗，修復(fù)單個扇區(qū)錯誤時只需在本地進(jìn)行1次解碼操作，所以在不同的取值組合下本方案操作數(shù)均小于其他2種算法，特別是隨著n，r取值增大時，STAIR Codes行、列編碼矩陣增大，計算復(fù)雜度進(jìn)一步增大，本方案優(yōu)勢更加明顯.綜上所述，本方案在抵抗單個扇區(qū)錯誤時計算開銷小于STAIR Codes方案.

再考慮只發(fā)生單個扇區(qū)錯誤的情形，本方案仍通過磁盤內(nèi)冗余進(jìn)行修復(fù)，只需接入讀取1塊磁盤；而STAIR Codes則需要利用磁盤間冗余修復(fù)，需要讀取n-m塊磁盤.此種情形下，本方案IO性能也優(yōu)于STAIR Codes方案.

Fig. 9　Update cost of SD Codes, IDR, IIDR for different s.圖9　s不同取值下SD Codes，IDR，IIDR的更新開銷

4.3更新性能

當(dāng)數(shù)據(jù)扇區(qū)更新時，相應(yīng)的校驗扇區(qū)也需要更新，可以通過所需更新的校驗扇區(qū)數(shù)目來衡量方案的更新性能.更新開銷定義為在1個條帶中更新1個數(shù)據(jù)扇區(qū)時，所需更新的校驗扇區(qū)數(shù)目的平均值.

Fig. 10　Update cost of STAIR Codes, IIDR versus different e.圖10　抵抗不同分布錯誤時STAIR Codes，IIDR方案更新開銷

圖9為n=8，r=6，s，m不同的取值情況下，SD Codes，IDR，IIDR三個方案更新開銷的對比.如圖9所示，3個方案中，SD Codes方案所需更新的全局校驗扇區(qū)僅為s，行校驗扇區(qū)僅為m，所以SD Codes方案有較好的更新性能.當(dāng)s較小時，3個方案相差不大；當(dāng)s較大時，本方案全局校驗扇區(qū)數(shù)目增大，IDR方案則需要更新較多的行校驗扇區(qū)，所以SD Codes方案優(yōu)勢更為明顯，但SD Codes方案只能抵抗s≤3的任意錯誤分布.本方案開銷整體略高于IDR方案，2個方案所需更新的行校驗扇區(qū)基本一致，但隨著s，m的增大，IDR需要更新更多的本地校驗扇區(qū)，則本方案與IDR方案更新開銷差距隨即縮小.

由于STAIR Codes方案不支持任意錯誤分布，只能在抵抗特定錯誤分布的情況下分析其更新性能.圖10中設(shè)s=4，針對其5種分布及m的不同取值，分析對比STAIR Codes與本方案的更新性能.如圖10所示，2個方案性能相差不大，在不同分布下各有優(yōu)劣.其中分布為(2，2)，(4)的情況下，STAIR Codes更新性能較優(yōu)；分布為(1，1，1，1)，(1，1，2)，(1，3)的情況下，本方案更新性能較優(yōu).這是由于2個方案所需更新的磁盤校驗扇區(qū)數(shù)目基本一致，更新差距主要集中在全局校驗扇區(qū)，由于本方案校驗扇區(qū)由本地校驗扇區(qū)和全局校驗扇區(qū)組成，其中全局校驗扇區(qū)數(shù)目比STAIR Codes少，更新時本方案只需更新單個本地校驗扇區(qū)及全局校驗扇區(qū)，所以更新開銷比STAIR Codes小，特別是在單個扇區(qū)錯誤較多的分布，這種優(yōu)勢尤為明顯.

綜上所述，本方案更新性能總體優(yōu)于STAIR Codes方案，特別是在抵抗存在單個扇區(qū)錯誤分布情況下優(yōu)勢較為明顯.在抵抗任意扇區(qū)錯誤分布時，SD Codes方案更新性能最優(yōu)(s≤3)，本方案總體略差于IDR方案，但在部分參數(shù)下本方案優(yōu)于IDR方案.

5　結(jié)　　論

本文將磁盤間編碼與磁盤內(nèi)編碼相結(jié)合，提出一種能抵抗磁盤錯誤和任意分布的扇區(qū)錯誤的混合編碼方案.與傳統(tǒng)的IDR方案相比，本方案有更高的磁盤利用率；相比SD Codes方案，本方案能夠抵抗更多任意分布的扇區(qū)錯誤；相比STAIR Codes方案，本方案犧牲了一定的磁盤利用率，但能抵抗任意分布的扇區(qū)錯誤，更新性能也略優(yōu)，特別是在處理單個扇區(qū)錯誤時有更小的IO和計算開銷.

[1]Li M, Lee P P C. STAIR codes: A general family of erasure codes for tolerating device and sector failures[J]. ACM Trans on Storage, 2014, 10(4): 1-30[2]Bairavasundaram L N, Goodson G R, Pasupathy S, et al. An analysis of latent sector errors in disk drives[C]Proc of the 2007 ACM SIGMETRICS Int Conf on Measurement and Modeling of Computer Systems. New York: ACM, 2007: 289-300[3]Micron Technology, Inc. N-29-17: NAND flash design and use considerations introduction Micron[EBOL]. 2006 [2015-06-01]. https:www.micron.com～mediadocumentsproductstechnical-notenand-flashtn2917.pdf[4]Schroeder B, Damouras S, Gill P. Understanding latent sector errors and how to protect against them[J]. ACM Trans on storage, 2010, 6(3): 523-530[5]Oprea A, Juels A. A clean-slate look at disk scrubbing[C]Proc of the 8th USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2010: 57-70[6]McKusick M K, Joy W N, Leffler S J, et al. A fast file system for UNIX[J]. ACM Trans on Computer Systems, 1984, 2(3): 181-197[7]Vijayan P, Lakshmi N B, Nitin A, et al. IRON file systems[C]Proc of the 20th ACM Symp on Operating Systems Principles. New York: ACM, 2005: 206-220[8]Dholakia A, Eleftheriou E, Hu X Y, et al. A new intra-disk redundancy scheme for high-reliability RAID storage systems in the presence of unrecoverable errors[J]. ACM Trans on Storage, 2008, 4(1): 133-169[9]Iliadis I, Haas R, Hu X Y, et al. Disk scrubbing versus intra-disk redundancy for high-reliability raid storage systems[C]Proc of the 2008 ACM SIGMETRICS Int Conf on Measurement and Modeling of Computer Systems. New York: ACM, 2008: 241-252[10]Plank J S, Blaum M. Sector-disk (SD) erasure codes for mixed failure modes in RAID systems[J]. ACM Trans on Storage, 2014, 10(1): 112-128[11]Plank J S, Blaum M, Hafner J L. SD codes: Erasure codes designed for how storage systems really fail[C]Proc of the 11th USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2013: 95-104[12]Li M, Lee P P C. STAIR codes: A general family of erasure codes for tolerating device and sector failures in practical storage systems[C]Proc of the 12th USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2014: 147-162[13]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(in Chinese)(羅象宏, 舒繼武. 存儲系統(tǒng)中的糾刪碼研究綜述[J]. 計算機(jī)研究與發(fā)展, 2012, 49(1): 1-11)[14]Plank J S, Greenan K M, Miller E L. Screaming fast Galois field arithmetic using Intel SIMD instructions[C]Proc of the 11th USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2013: 299-306

Bian Jianchao, born in 1989. PhD candidate. His main research interests include information security, coding theory, storage security and reliability, disaster backup and recovery.

Zha Yaxing, born in 1985. PhD candidate. His main research interests include information security, cryptography, storage security and reliability, disaster backup and recovery (zhayaxing@safe-code.com).

Luo Shoushan, born in 1962. Professor and PhD supervisor in the School of Computer Science at Beijing University of Posts and Telecommunications. His main research interests include information security, cryptography, secure multi-party computation (luoshoushan@safe-code.com).

Li Wei, born in 1986. PhD candidate. His main research interests include information security, cryptography, network security (liwei@safe-code.com).

A Hybrid Coding Scheme Based on Intra- and Inter-Device Redundancy

Bian Jianchao, Zha Yaxing, Luo Shoushan, and Li Wei

(SchoolofComputerScience,BeijingUniversityofPostsandTelecommunications,Beijing100876)(NationalEngineeringLaboratoryforDisasterBackupandRecovery(BeijingUniversityofPostsandTelecommunications),Beijing100876)

The development and application of cloud computing set higher requirement for the fault-tolerant capability of the storage systems. Erasure code has been widely used to generate device-level redundancy to protect against device failures, while has less space efficiency when resisting the sector failures. Current optimization schemes for the sector failures only resist the failures of small amounts of the sectors or specific sectors. In this paper, we propose a hybrid coding scheme (intra- and inter-device redundancy, IIDR) combining inter-device redundancy with intra-device redundancy based on the homomorphism property of MDS (maximum distance separable) codes, which employs global parity sector against sector failures in the data disks when adding parity device against device failures, and optimizes the ability to process single-sector errors taking advantage of intra-device coding to generate local parity sectors. In the end, the correctness proof and performance analysis are shown in this paper, and the results indicate that our scheme can protect against device failures and sector failures of any distribution, and the computing cost of recovering single-sector errors is much lower, and the update performance is better. Compared with traditional intra-device coding schemes, our scheme comes with less space usage.

cloud computing; device failures; latent sector errors (LSEs); erasure code; intra-disk redundancy

2015-06-16；

2015-10-13

國家“八六三”高技術(shù)研究發(fā)展計劃基金項目(2015AA016005)

TP302.8

This work was supported by the National High Technology Research and Development Program of China (863 Program) (2015AA016005).