來 燃 ，馮興杰 ，王 晴 ，李 杰 ，焦文歡

（1.中國民航大學(xué)信息網(wǎng)絡(luò)中心，天津 300300；2.天津市大學(xué)軟件學(xué)院信息化部，天津 300387）

進(jìn)入大數(shù)據(jù)時(shí)代[1]以來，數(shù)據(jù)規(guī)模不斷擴(kuò)大，數(shù)據(jù)價(jià)值日益增長，存儲系統(tǒng)的性能和可靠性受到了嚴(yán)重挑戰(zhàn)，特別是現(xiàn)代存儲系統(tǒng)中設(shè)備的數(shù)量及容量都在呈指數(shù)級增長，數(shù)據(jù)中心發(fā)生磁盤失效以及扇區(qū)錯(cuò)誤的概率越來越大[2]，存儲系統(tǒng)需要在磁盤失效的情況下保障數(shù)據(jù)的可用性。

目前，用于提高存儲系統(tǒng)數(shù)據(jù)可靠性的數(shù)據(jù)冗余技術(shù)主要分為多路鏡像技術(shù)和糾刪碼技術(shù)兩種。多路鏡像技術(shù)具有數(shù)據(jù)可用性高、存儲空間利用率低的特點(diǎn)，主要用于數(shù)據(jù)訪問密集型存儲系統(tǒng)[3]。糾刪碼技術(shù)在提高存儲空間利用率的同時(shí)能夠提供相同甚至高得多的數(shù)據(jù)容錯(cuò)能力[4]，RAID-6 MDS（maximum distance separable）編碼因其容忍任意2塊磁盤失效的能力以及較高的存儲空間利用率，得到了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注[5]。另一方面，存儲系統(tǒng)中磁盤出錯(cuò)已成為一種常態(tài)，當(dāng)磁盤因故障或網(wǎng)絡(luò)堵塞等原因?qū)е聰?shù)據(jù)不能訪問時(shí)，存儲系統(tǒng)進(jìn)入降級模式[6]，為了在降級模式下不影響用戶的體驗(yàn)，需研究一種可靠的適用于降級讀操作的RAID-6編碼算法。

為了提高降級讀性能，目前的研究主要針對單磁盤錯(cuò)誤進(jìn)行數(shù)據(jù)重構(gòu)效率優(yōu)化[7]。文獻(xiàn)[8]提出了RDOR（row diagonal optimal recovery）算法，RDOR同時(shí)利用水平校驗(yàn)元素和對角校驗(yàn)元素對失效元素進(jìn)行重構(gòu)，不僅在降級模式下讀取的數(shù)據(jù)元素總量最少，而且還實(shí)現(xiàn)了磁盤間的負(fù)載均衡。文獻(xiàn)[9]將RDOR基于構(gòu)造的優(yōu)化算法推廣到其它水平碼中。然而，RDOR算法的思想不能完全適用于垂直碼，文獻(xiàn)[10]在X-碼[11]的基礎(chǔ)上提出了一種用于優(yōu)化讀取數(shù)據(jù)總量的MDRR（minimum disk read recovery）算法，但無法實(shí)現(xiàn)磁盤間的負(fù)載均衡。針對基于構(gòu)造的優(yōu)化算法適用性差的缺點(diǎn)，文獻(xiàn)[12]提出一種基于深度優(yōu)先搜索原理的單磁盤錯(cuò)誤重構(gòu)方法，從而減小降級操作讀取的數(shù)據(jù)總量。文獻(xiàn)[13]在已有糾刪碼的基礎(chǔ)上，通過分組方式，將多個(gè)糾刪碼技術(shù)疊加構(gòu)建，極大提高了重構(gòu)過程的并行度，但存儲利用率不高。文獻(xiàn)[14]提出的STP算法在條帶棧的應(yīng)用場景下相比文獻(xiàn)[12]在重構(gòu)效率上有較大幅度提升。文獻(xiàn)[15]通過壓縮水平校驗(yàn)鏈的長度，有效提高了降級讀性能，但負(fù)載均衡性能不佳。充分利用RDP碼等水平碼的優(yōu)勢，提出一種優(yōu)化降級讀性能的RAID-6編碼算法。在X-碼（垂直碼）的基礎(chǔ)上將X-碼中數(shù)據(jù)元素的布局方式調(diào)整為水平方向，而校驗(yàn)元素的位置及其計(jì)算方法保持不變，有效減少了降級讀操作所需要的額外I/O開銷。

1 問題描述

當(dāng)存儲系統(tǒng)中的一塊磁盤出現(xiàn)錯(cuò)誤時(shí)，存儲系統(tǒng)進(jìn)入降級模式，此時(shí)前端用戶的讀請求操作有可能落在錯(cuò)誤磁盤上，系統(tǒng)通過讀取其他磁盤上存儲的額外元素對用戶請求中的失效數(shù)據(jù)元素進(jìn)行重構(gòu)，然后將所有請求的數(shù)據(jù)（包括可用數(shù)據(jù)元素和重構(gòu)數(shù)據(jù)元素）返回給用戶，以完成用戶發(fā)出的讀操作請求。在降級模式下，用戶體驗(yàn)是存儲系統(tǒng)的重要性能指標(biāo)。

如圖1所示，假設(shè)第2塊磁盤出現(xiàn)錯(cuò)誤（Ci，j表示第i行、第j列的數(shù)據(jù)元素），用戶請求讀取10個(gè)連續(xù)數(shù)據(jù)元素（從 C0，0開始），RDP 碼[16]共需取回 12 個(gè)元素，而X-碼共需取回16個(gè)元素。上述例子說明，由于連續(xù)數(shù)據(jù)元素更有可能共享相同的水平校驗(yàn)鏈，水平碼在降級讀操作時(shí)某些請求的數(shù)據(jù)元素會參與到失效元素的重構(gòu)中，因而減小了降級讀操作所造成的額外I/O開銷。相比于垂直碼，水平碼在降級讀操作時(shí)通常需要讀取較少的元素。另一方面，校驗(yàn)鏈的長度也會影響到降級讀性能，校驗(yàn)鏈的長度越長，當(dāng)請求讀取相同的數(shù)據(jù)元素時(shí)，需要取回的元素總量就越多。因此，如果能縮短水平碼的校驗(yàn)鏈長度，將會進(jìn)一步提高水平碼的降級讀性能。

圖1 RDP碼和X-碼在降級讀操作方面存在的問題（m=7）Fig.1 Problems of RDP code and X-code in degraded read operations（m=7）

2 研究方法

2.1 構(gòu)建方法

圖2為X-碼和優(yōu)化X-碼的布局比較圖，其中（X，Y）表示第X條對角校驗(yàn)鏈、第Y條反對角校驗(yàn)鏈上的數(shù)據(jù)元素。圖中涉及的7條校驗(yàn)鏈分別用A～F表示。由圖2（a）可以看出，X-碼中相同對角校驗(yàn)鏈上的數(shù)據(jù)元素和校驗(yàn)元素分布在條帶內(nèi)的不同行上。首先，將X-碼的反對角校驗(yàn)行和對角校驗(yàn)行調(diào)換位置。然后，在每個(gè)條塊內(nèi)部交換數(shù)據(jù)元素的位置，使得相同對角校驗(yàn)鏈上的數(shù)據(jù)元素共享同一水平校驗(yàn)鏈，進(jìn)而得到如圖2（b）所示的優(yōu)化X-碼布局圖。

在優(yōu)化X-碼的構(gòu)建過程中，每個(gè)條塊內(nèi)數(shù)據(jù)元素的位置相比X-碼發(fā)生了移動，并且數(shù)據(jù)元素和校驗(yàn)元素的位置移動只發(fā)生在條塊內(nèi)部，這就保證了優(yōu)化X-碼的容錯(cuò)能力不變。優(yōu)化X-碼的構(gòu)建布局可通過如下遞歸算法得到，偽代碼如下所示。

圖2 X-碼、優(yōu)化X-碼布局比較Fig.2 Layout comparison between X-code and optimized X-code

輸入：

對角校驗(yàn)鏈序列 M={0，1，2，3，4，5，6，7}

對角校驗(yàn)鏈個(gè)數(shù)p

輸入數(shù)值X-碼的所有數(shù)據(jù)元素組成的序列輸出：

輸出數(shù)值優(yōu)化X-碼的所有數(shù)據(jù)元素組成的序列

獲取列（i*（p-2）+j）%p 中所有數(shù)據(jù)元素所在的對角校驗(yàn)鏈序號，進(jìn)而找到對角校驗(yàn)鏈序列中不包含的元素m；

刪除對角校驗(yàn)鏈序列中的元素m；

獲取數(shù)據(jù)元素（（p-2）*（i-1）+k）所在的行 r和列c；

if數(shù)據(jù)元素（q*p+c）所在的對角校驗(yàn)鏈為m且數(shù)

據(jù)元素（r*p+c）所在的對角校驗(yàn)鏈不為m；

then

交換數(shù)據(jù)元素（q*p+c）和（r*p+c）的位置；

2.2 雙盤失效恢復(fù)

從優(yōu)化X-碼的構(gòu)建過程可以看出，優(yōu)化X-碼是在X-碼的基礎(chǔ)上，通過調(diào)整X-碼中每個(gè)邏輯磁盤上元素的位置，使連續(xù)數(shù)據(jù)元素共享相同水平校驗(yàn)鏈而得到的。和X-碼一樣，優(yōu)化X-碼的容錯(cuò)能力仍為2，即在任意2塊磁盤并發(fā)失效的情況下，優(yōu)化X-碼都可以重構(gòu)出所有失效的數(shù)據(jù)元素。不失一般性，假設(shè)磁盤2和磁盤3出現(xiàn)故障，磁盤2和磁盤3上的數(shù)據(jù)元素和校驗(yàn)元素可通過如圖3所示方法恢復(fù)。

圖3 雙盤失效重構(gòu)示例（m=6）Fig.3 Donble disk concurrent failures recovery intance（m=6）

圖3是優(yōu)化X-碼雙盤失效重構(gòu)的例子，首先通過水平校驗(yàn)鏈或?qū)切ｒ?yàn)鏈分別計(jì)算出兩個(gè)起始數(shù)據(jù)元素A和G，然后根據(jù)與數(shù)據(jù)元素A處于相同對角校驗(yàn)鏈上的其它元素的異或和計(jì)算出數(shù)據(jù)元素B，由于數(shù)據(jù)元素B和數(shù)據(jù)元素C處在相同的水平校驗(yàn)鏈上，因此數(shù)據(jù)元素C也可以恢復(fù)出來。按照此方法可以恢復(fù)所有失效元素，元素的恢復(fù)序列為A→B→C→D→E→F，G→H→I→J→K→L，元素M和N分別通過對應(yīng)的水平校驗(yàn)鏈或?qū)切ｒ?yàn)鏈恢復(fù)出來。

2.3 特性分析

1）存儲效率 優(yōu)化X-碼由（m-2）×m個(gè)數(shù)據(jù)元素和2m個(gè)校驗(yàn)元素構(gòu)成，其存儲效率為（m-2）×m/（m × m）=（m-2）/m，滿足RAID-6 MDS的最優(yōu)存儲效率。

2）編碼計(jì)算復(fù)雜度 優(yōu)化X-碼的每個(gè)校驗(yàn)元素由m-2個(gè)數(shù)據(jù)元素計(jì)算得到，于是編碼所有的校驗(yàn)元素所需的異或操作次數(shù)為2m×（m-3），平均每個(gè)數(shù)據(jù)元素的異或操作次數(shù)為2m×（m-3）/（（m-2）×m）=2-2/（m-2），滿足RAID-6 MDS的最優(yōu)編碼計(jì)算復(fù)雜度。

3）解碼計(jì)算復(fù)雜度 優(yōu)化X-碼的每個(gè)條塊包含m個(gè)元素，當(dāng)2塊磁盤并發(fā)故障時(shí)，失效元素的總數(shù)為2m，而恢復(fù)一個(gè)失效數(shù)據(jù)元素需對應(yīng)校驗(yàn)鏈上m-2個(gè)存活元素的（m-3）次異或操作次數(shù)，于是優(yōu)化X-碼的解碼計(jì)算復(fù)雜度為2m×（m-3）/2m=m-3，滿足RAID-6 MDS的最優(yōu)解碼計(jì)算復(fù)雜度。

4）更新計(jì)算復(fù)雜度 優(yōu)化X-碼中每個(gè)數(shù)據(jù)元素只屬于一個(gè)水平校驗(yàn)鏈和一個(gè)對角校驗(yàn)鏈，并且校驗(yàn)元素之間彼此獨(dú)立，對于每個(gè)數(shù)據(jù)元素的更新，優(yōu)化X-碼只需更新兩個(gè)校驗(yàn)元素，滿足RAID-6 MDS的最優(yōu)更新計(jì)算復(fù)雜度。

3 仿真結(jié)果及分析

為了評估優(yōu)化X-碼在降級讀操作下的性能，主要關(guān)注降級讀操作下的平均I/O懲罰因子p，假設(shè)L表示前端用戶需要讀取數(shù)據(jù)元素的個(gè)數(shù)，L′表示實(shí)際讀取元素的個(gè)數(shù)，則I/O懲罰因子p=L′/L。為此進(jìn)行如下實(shí)驗(yàn)：由于RAID-6編碼包含k（k表示數(shù)據(jù)磁盤的個(gè)數(shù)）種不同的故障情況，對于每種故障情況，產(chǎn)生一組隨機(jī)數(shù)（S，B，F(xiàn)），如表1所示。其中S為讀操作的起始數(shù)據(jù)元素，B為讀取數(shù)據(jù)元素的長度，F(xiàn)為執(zhí)行F次起始于數(shù)據(jù)元素S且讀取長度為B的降級讀操作次數(shù)，計(jì)算所有故障情況下降級讀操作的平均I/O懲罰因子。

表1 隨機(jī)讀模式(S,B,F)Tab.1 Random read mode(S,B,F)

按照上述實(shí)驗(yàn)方法，分別計(jì)算X-碼、RDP碼和優(yōu)化X-碼在不同磁盤數(shù)目下的平均I/O懲罰因子，如圖4所示。可以看出，使用優(yōu)化X-碼計(jì)算出的平均I/O懲罰因子比X-碼、RDP碼都要小，而X-碼的平均I/O懲罰因子最大，進(jìn)一步說明水平碼在降級讀操作中的優(yōu)勢。同時(shí)，優(yōu)化X-碼的水平校驗(yàn)鏈長度比RDP碼小，讀取相同長度的數(shù)據(jù)元素需要較少的額外I/O開銷，因此計(jì)算出的平均I/O懲罰因子比RDP碼小。

圖4 降級讀操作下的平均I/O懲罰因子與磁盤數(shù)量的關(guān)系圖Fig.4 Relationship between average I/O penalty factor and disks number under degraded reads

為分析降級讀操作下不同讀取長度對平均I/O懲罰因子的影響，分別計(jì)算不同讀取長度下的平均I/O懲罰因子，如圖5所示。當(dāng)讀取長度恰好為整個(gè)條帶時(shí)，降級讀操作不會帶來任何懲罰（p=1）。當(dāng)讀取長度小于整個(gè)條帶時(shí)，隨著讀取長度的增大，平均I/O懲罰因子會逐漸減小并趨近于1。相比于X-碼、RDP碼，優(yōu)化X-碼在相同讀取長度下的平均I/O懲罰因子最小，特別地，當(dāng)B=10時(shí)，優(yōu)化X-碼相對于X-碼和RDP碼分別減少了約30%和10%的元素讀取。

圖5 降級讀操作下的平均I/O懲罰因子隨讀取長度變化曲線圖（k=7）Fig.5 Changing trend of average I/O penalty factor with various reading length under degraded reads（k=7）

4 結(jié)語

針對傳統(tǒng)RAID-6糾刪碼存儲系統(tǒng)在降級模式下讀操作性能不足的問題，提出一種優(yōu)化降級讀性能的RAID-6編碼算法。充分利用水平碼中連續(xù)數(shù)據(jù)元素更有可能共享相同水平校驗(yàn)鏈的優(yōu)點(diǎn)，將X-碼中對角校驗(yàn)鏈上的數(shù)據(jù)元素布局方式調(diào)整為水平方向，保持校驗(yàn)元素的位置及其計(jì)算方法不變，有效減小了降級讀操作的額外I/O開銷。優(yōu)化X-碼不僅具有最佳存儲效率，而且在編解碼計(jì)算復(fù)雜度以及更新效率上都達(dá)到了理論最優(yōu)。仿真結(jié)果表明，該方法在磁盤數(shù)量相同的情況下降級讀性能優(yōu)于RDP碼和X-碼。然而，以上研究只針對單磁盤錯(cuò)誤下的降級讀性能進(jìn)行了優(yōu)化，隨著存儲規(guī)模不斷擴(kuò)大，多磁盤錯(cuò)誤的概率會越來越大，下一步將重點(diǎn)研究多磁盤并發(fā)失效下的降級讀性能優(yōu)化技術(shù)。