一種基于磁盤內和磁盤間冗余的混合編碼方案

卞建超　查雅行　羅守山　李　偉

(北京郵電大學計算機學院　北京　100876)(災備技術國家工程實驗室(北京郵電大學)　北京　100876)

?

一種基于磁盤內和磁盤間冗余的混合編碼方案

卞建超查雅行羅守山李偉

(北京郵電大學計算機學院北京100876)(災備技術國家工程實驗室(北京郵電大學)北京100876)

(bianjianchao@bupt.edu.cn)

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

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

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

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

1　相關工作

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

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

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

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

2　混合編碼方案

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

2.1預備知識

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

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

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

2.1.1校驗扇區(qū)分布

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

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

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

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

2.1.2基本定義

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

2.1.3同態(tài)性質

根據定義，各列進行編碼計算有：

當0≤j≤n-m-1時，

當0≤k≤m-1時，

當0≤t≤s-2時，

2.2編碼過程

2.2.1示例

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

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

2.2.2一般情況

Table 1　Detailed Steps for Encoding

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

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

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

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

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

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

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

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

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

初始化:

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

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

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

t=t+i;

搜索第r+s-t行;

記錄Rr;

IfRr=n-mThen

對r+s-t行進行編碼;

Else break;

End If

Forj=qtom′-2

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

記錄Rc;

IfRc=r-1 Then

對n-m-m′+i列進行編碼;

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ū)

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

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

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

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

其中0≤k≤m-1.

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

2.3數據恢復過程

2.3.1示例

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

Fig. 3　Data recovery algorithm.圖3　數據恢復算法

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

Table 2　Detailed Steps for Data Recovery

2.3.2一般情況

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

1) 修復簡單錯誤

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

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

① 修復m+1至m+m′-1 列

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

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

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

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

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

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

其中0≤j≤m-1.

至此，全部數據均被修復.

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

3　正確性證明

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

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

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

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

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

證畢.

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

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

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

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

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

證畢.

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

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

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

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

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

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

證畢.

4　性能分析

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

4.1磁盤利用率

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

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

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

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

則數目可以表示為

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

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

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

4.2計算開銷

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

4.2.1修復混合錯誤的計算開銷

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

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

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

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

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

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

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

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

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

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

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

再考慮只發(fā)生單個扇區(qū)錯誤的情形，本方案仍通過磁盤內冗余進行修復，只需接入讀取1塊磁盤；而STAIR Codes則需要利用磁盤間冗余修復，需要讀取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更新性能

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

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方案有較好的更新性能.當s較小時，3個方案相差不大；當s較大時，本方案全局校驗扇區(qū)數目增大，IDR方案則需要更新較多的行校驗扇區(qū)，所以SD Codes方案優(yōu)勢更為明顯，但SD Codes方案只能抵抗s≤3的任意錯誤分布.本方案開銷整體略高于IDR方案，2個方案所需更新的行校驗扇區(qū)基本一致，但隨著s，m的增大，IDR需要更新更多的本地校驗扇區(qū)，則本方案與IDR方案更新開銷差距隨即縮小.

由于STAIR Codes方案不支持任意錯誤分布，只能在抵抗特定錯誤分布的情況下分析其更新性能.圖10中設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ū)數目基本一致，更新差距主要集中在全局校驗扇區(qū)，由于本方案校驗扇區(qū)由本地校驗扇區(qū)和全局校驗扇區(qū)組成，其中全局校驗扇區(qū)數目比STAIR Codes少，更新時本方案只需更新單個本地校驗扇區(qū)及全局校驗扇區(qū)，所以更新開銷比STAIR Codes小，特別是在單個扇區(qū)錯誤較多的分布，這種優(yōu)勢尤為明顯.

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

5　結　　論

本文將磁盤間編碼與磁盤內編碼相結合，提出一種能抵抗磁盤錯誤和任意分布的扇區(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]. 計算機研究與發(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

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

TP302.8

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