一種可行的優(yōu)化降級讀性能RAID-6編碼算法

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

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

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

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

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

1 問題描述

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

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

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

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

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

輸入：

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

對角校驗鏈個數(shù)p

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

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

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

刪除對角校驗鏈序列中的元素m；

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

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

據(jù)元素（r*p+c）所在的對角校驗鏈不為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-碼中每個邏輯磁盤上元素的位置，使連續(xù)數(shù)據(jù)元素共享相同水平校驗鏈而得到的。和X-碼一樣，優(yōu)化X-碼的容錯能力仍為2，即在任意2塊磁盤并發(fā)失效的情況下，優(yōu)化X-碼都可以重構(gòu)出所有失效的數(shù)據(jù)元素。不失一般性，假設(shè)磁盤2和磁盤3出現(xiàn)故障，磁盤2和磁盤3上的數(shù)據(jù)元素和校驗元素可通過如圖3所示方法恢復(fù)。

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

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

2.3 特性分析

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

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

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

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

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

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

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

按照上述實驗方法，分別計算X-碼、RDP碼和優(yōu)化X-碼在不同磁盤數(shù)目下的平均I/O懲罰因子，如圖4所示。可以看出，使用優(yōu)化X-碼計算出的平均I/O懲罰因子比X-碼、RDP碼都要小，而X-碼的平均I/O懲罰因子最大，進一步說明水平碼在降級讀操作中的優(yōu)勢。同時，優(yōu)化X-碼的水平校驗鏈長度比RDP碼小，讀取相同長度的數(shù)據(jù)元素需要較少的額外I/O開銷，因此計算出的平均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懲罰因子的影響，分別計算不同讀取長度下的平均I/O懲罰因子，如圖5所示。當(dāng)讀取長度恰好為整個條帶時，降級讀操作不會帶來任何懲罰（p=1）。當(dāng)讀取長度小于整個條帶時，隨著讀取長度的增大，平均I/O懲罰因子會逐漸減小并趨近于1。相比于X-碼、RDP碼，優(yōu)化X-碼在相同讀取長度下的平均I/O懲罰因子最小，特別地，當(dāng)B=10時，優(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ōu)點，將X-碼中對角校驗鏈上的數(shù)據(jù)元素布局方式調(diào)整為水平方向，保持校驗元素的位置及其計算方法不變，有效減小了降級讀操作的額外I/O開銷。優(yōu)化X-碼不僅具有最佳存儲效率，而且在編解碼計算復(fù)雜度以及更新效率上都達到了理論最優(yōu)。仿真結(jié)果表明，該方法在磁盤數(shù)量相同的情況下降級讀性能優(yōu)于RDP碼和X-碼。然而，以上研究只針對單磁盤錯誤下的降級讀性能進行了優(yōu)化，隨著存儲規(guī)模不斷擴大，多磁盤錯誤的概率會越來越大，下一步將重點研究多磁盤并發(fā)失效下的降級讀性能優(yōu)化技術(shù)。