一種低單盤故障恢復開銷的局部修復碼

蕭 楓，唐 聃，范 迪，白寧超

1.成都信息工程大學 軟件工程學院，成都 610225

2.四川省計算機研究院，成都 610041

1 引言

近年來，隨著信息技術的快速發展，世界上的數據量正不斷增長，而存儲系統的規模也日益增大，廉價存儲設備的應用也逐漸變得廣泛。而隨著規模的增大、廉價磁盤數目的增多，存儲系統中磁盤發生故障的概率也在上升，從而導致存儲系統的穩定性所面臨更加嚴峻的挑戰。因此大多數存儲系統都會為了保障數據的可靠存儲而使用容錯技術。

常用的容錯技術有兩種：副本技術和糾刪碼技術。副本技術是指通過復制原數據并存儲其副本，來保障當發生任意小于副本數目的錯誤時，都可以通過備份的副本來保障數據的完整性和可靠性。副本技術的優點在于算法簡單，易于實現，且恢復速度極快。而副本技術最大的缺點在于存儲開銷過大，需要許多的冗余存儲才能夠保證數據的可靠。而糾刪碼技術則是通過相應的算法來生成少量的冗余數據，并與原數據一起存儲。當故障發生時，則通過對應的解碼算法對于剩余數據和冗余數據進行運算得到原數據。糾刪碼技術解決了副本技術帶來的冗余過多的問題，同時能夠在一定程度上保證數據的完整性和可靠性，因此是目前存儲系統中主流的容錯策略。

在糾刪碼技術中，陣列糾刪碼由于基于異或計算，編譯碼速度快的特點而被廣泛應用。典型的陣列碼包括 EVENODD[1]、RDP[2]、STAR[3]、RTP[4]等等，而 RDP 碼是存儲系統中較為常用的一類容兩錯的陣列碼。其原理主要是通過增加額外的兩個冗余磁盤來保證數據的完整性，因此RDP能夠在任意的兩個數據磁盤發生故障后仍正確地恢復出原始數據。

對于RDP編碼而言，其優點在于結構簡單，編譯碼過程基于異或運算，因而速度很快。但是其主要缺點之一就是單盤故障恢復所需讀取的數據過多，需要讀取所有的剩余原數據。而在存儲系統的故障失效情況中，單一磁盤故障的比例達到99.75%[5]，而糾刪碼高額的恢復讀取開銷會給數據中心原本就緊張的帶寬資源[6]帶來更大的壓力。文獻[7]則論述了降低單盤故障的恢復時間可以提高整個存儲系統的穩定性。因此為減少讀取開銷，降低單盤故障恢復時間，提出一種新的RDP單盤故障恢復算法。考慮到傳統RDP編碼中單數據盤故障的恢復是基于單個校驗盤，若增加一個只由部分數據盤計算得到的局部校驗盤，能夠使得當這些數據盤發生故障時，僅需要讀取生成局部校驗盤的數據盤就能夠恢復，從而達到減少讀取開銷的目的。

2 RDP介紹

2.1 RDP編碼過程

RDP（Row Diagonal Parity）的編碼過程是基于一個規模為(p-1)×(p-1)的原數據陣列，其中 p為素數。假設陣列中每一列代表一個磁盤，而磁盤中存儲的數據塊為ai,j,i和 j分別表示元素的行列坐標，且坐標均從0開始計。

編碼過程分為兩步，第一步是計算水平冗余列。計算方法是將 p-1個數據列橫向進行異或，其編碼過程如式（1）所示：

第二步是計算對角冗余列。方法是將由p-1列原數據以及第一步生成的水平冗余列構成的規模為(p-1)×p的新陣列中行列坐標之和模 p結果相同的數據塊進行異或構成對角冗余列。其編碼過程如式（2）所示：

最終的編碼過程如圖1所示，最終得到一個包含兩列冗余列的規模為(p-1)×(p+1)的陣列。

圖1 水平冗余和對角線冗余計算過程

2.2 RDP單盤故障恢復過程

傳統的RDP單盤故障恢復方法可以根據丟失的列位置分為數據列丟失和冗余列丟失兩種類型。

數據列丟失的恢復過程為讀取出其他全部的數據列的數據塊以及水平冗余列的數據塊進行異或運算，得到丟失的數據列。恢復所需要讀取的數據盤如圖2所示，其中“×”表示丟失的數據塊，“○”表示恢復所需要讀取的數據塊。

圖2 單盤故障恢復所需讀取的數據

由圖2可知，當數據列發生故障時，需要讀取的列數目為p-1，即原陣列中總共的數據列列數。

冗余列丟失的恢復過程同編碼過程一致，即通過編碼算法再次生成冗余列即可恢復。顯然當冗余列發生故障時，需要讀取的列數目依然為p-1。

因此對于傳統的單盤故障恢復方法而言，無論是數據列丟失還是冗余列丟失，恢復過程所需要讀取的列數量均為p-1個。

2.3 RDP相關研究

為了對RDP進行擴展，文獻[8]提出在RDP基礎上再增加一個冗余列，其計算過程是將斜率為-1的斜線上的數據塊進行異或，構造出一種新的三容錯RAID碼。而文獻[9]則同樣提出在RDP基礎上增加新的冗余列，其計算過程是將斜率為2的斜線上的數據塊進行異或，得出了另一種新的三容錯RAID碼。

而為了降低單盤恢復開銷，文獻[10]提出，對于RDP編碼，當某一個數據盤發生故障時，可以同時使用兩個冗余列，即水平冗余與對角線冗余來進行恢復。由于使用不同方法恢復會產生重復讀取的數據塊，因此可通過緩存這些塊來降低讀取開銷。該文獻同時對于理論上的讀取下限進行了推導和證明，發現最小的恢復開銷是對于一半數據使用水平冗余進行恢復，對另一半數據使用對角線冗余進行恢復。最終計算得到該混合恢復算法理論上恢復開銷的下限是總數據量的3/4，即能夠節省25%的讀取開銷。

如圖3所示，當Disk0失效時，對于前兩個數據塊通過水平冗余列來進行恢復，對于后兩個數據塊通過對角線冗余來進行恢復。其中“○”表示利用水平冗余所需要讀取的數據塊，而“□”表示利用對角線冗余所需要讀取的數據塊，而兩者都有則表示重復的數據塊。

圖3 混合恢復算法的單盤故障恢復讀取開銷

文獻[11]則提出了一種針對RDP單盤故障恢復的不同方案。該方法通過將水平上的部分不參與對角冗余計算的數據塊進行異或產生額外的冗余塊，并使用產生的冗余塊來代替原來的多個數據塊，從而達到降低數據讀取開銷的目的。而針對于容三錯的陣列碼而言，文獻[12]同樣提出了混合使用三列冗余列來進行單盤故障恢復的方法。其具體方法是通過對于丟失的p-1數據元素選取p-1個合適的校驗元素將其恢復，并平均使用3中校驗元素，使得校驗方程中需要的數據塊盡可能多的重合，以此來達到降低數據讀取量的目的。

然而混合恢復算法也帶來了磁盤隨機訪問的問題，文獻[13]在保證數據讀取量最少的前提下，為RDP設計出一種新型的、支持連續讀的單磁盤故障修復策略，最大程度上維持了磁盤訪問的連續性，加快了單磁盤故障的修復效率。

3 局部修復RDP編碼及相關性質

為了進一步地降低RDP碼在單盤故障時的恢復讀取開銷，縮短恢復時間，本文構造了一種LRRDP碼（Local Repairable RDP）。

3.1 編碼過程

LRRDP碼的編碼過程如圖4所示，相同形狀的白色元素生成對應的黑色校驗塊。

圖4 LRRDP編碼過程

3.2 編碼開銷

4 局部修復RDP解碼

4.1 單盤故障

對于傳統的RDP編碼，修復單盤故障（非冗余列）的方式是通過讀取剩余數據列以及水平冗余列進行異或來恢復。對于LRRDP，修復單盤故障分為4種情況。

4.1.1數據列丟失

恢復所需的數據塊如圖5所示，“×”表示丟失的數據塊，“○”表示恢復所需要讀取的數據塊。

圖5 丟失數據列在前半部分時所需讀取數據

恢復所需的數據塊如圖6所示。

圖6 丟失數據列在后半部分時所需讀取數據

4.1.2 局部冗余列丟失

4.1.3 水平冗余列丟失

4.1.4對角冗余列丟失

對角冗余列丟失的恢復過程與編碼過程相同，恢復的讀取開銷為 p。同樣當 p不斷增大時，這種故障在所有單盤故障中所占的比例將不斷降低。

對于單盤故障恢復來說，假設每個盤發生故障的概率一致，則擴展后的RDP單盤故障恢復平均開銷如式（7）所示：

圖7 水平冗余列丟失時所需讀取數據

4.2 雙盤故障

4.2.1丟失兩列數據列

對于擴展后的RDP，丟失兩個數據列的恢復過程與傳統RDP的雙盤故障恢復方法相同，數據的讀取開銷如式（8）所示：

4.2.2 丟失一列數據列和局部冗余列

設丟失的數據列為y，恢復過程為讀取剩余數據列和水平冗余列進行異或恢復出丟失數據列，恢復公式如（9）所示：

再通過編碼方式恢復局部冗余列，恢復完畢。Disk1與局部冗余列列丟失時所需讀取的數據塊如圖8所示。

圖8 雙盤故障恢復所需讀取數據

由式（8）可知，故障恢復數據讀取開銷為 p-1列。

4.2.3丟失一列數據列和水平或對角線冗余列

恢復過程與傳統RDP恢復方法一致，讀取開銷為p-1列。

4.2.4丟失兩列冗余列

恢復過程與編碼過程相同，顯然，當丟失水平和對角冗余列時，讀取開銷為 p-1列。當丟失水平和局部冗余列時，讀取開銷也為p-1列。而當丟失對角和局部冗余列時，讀取開銷為p列。

綜上，對于任意的雙盤故障，LRRDP能夠保證數據的完整性和可靠性。同時，LRRDP的雙盤故障恢復讀取開銷與傳統RDP保持基本一致。

4.3 三盤故障

LRRDP中的三個冗余列的計算可由式（10）～（12）表示：

同時設每個磁盤發生故障的概率為γ。

在LRRDP中，三盤故障恢復的關鍵在于將三盤故障轉換為傳統的RDP雙盤故障情況。對于傳統的RDP雙盤故障恢復過程，文獻[2]中有具體描述，不再贅述。

4.3.1 丟失的三列均為數據列

當丟失的均為數據列時，按照三個數據列的位置分布可以分為三種情況。

這種情況不可恢復。

對式（14）經過變換后可得式（16）：

將式（16）代入式（15）得式（17）：

顯然式（17）為恒等式，即ai,u、ai,v和ai,w有無窮多解，所以不可恢復。

恢復過程為通過局部冗余列恢復丟失列y，恢復公式如式（19）：

再通過傳統RDP解碼方法恢復剩余兩個丟失列，恢復完畢。

再通過傳統RDP解碼方法恢復剩余兩個丟失列，恢復完畢。

4.3.2 丟失的兩列為數據列，一列為冗余列

當丟失三個列，其中有兩個是數據列，另外一個是冗余列，根據冗余列類型可分為三種情況。

第一種情況是局部冗余列丟失，發生的概率如式（22）：

恢復過程為通過傳統RDP解碼方法恢復丟失的兩個數據列，之后通過編碼方法重新生成局部冗余列。

第二種情況是水平冗余列丟失，根據丟失的兩個列的位置可分為兩類。

這種情況無法恢復。

再通過傳統RDP解碼方法恢復丟失的數據列和水平冗余列，恢復完畢。

第三種情況是對角冗余列丟失，根據丟失的數據列的分布情況也可以分為兩類。

這種情況無法恢復。

其中對式（27）經過變換后可得式（29）：

將式（29）代入式（28）得式（30）：

顯然式（30）為恒等式，即 ai,y、ai,z有無窮多解，所以不可恢復。

4.3.3 丟失一個數據列，兩個冗余列

根據剩余的冗余列類型可以分為兩種情況。

第一種情況是剩余的冗余列是水平冗余列或對角冗余列，發生的概率如式（32）：

恢復過程為通過傳統的RDP雙盤恢復方式恢復兩個丟失的數據列，再通過編碼的方式重新生成局部冗余列，恢復完畢。

第二種情況是剩余的冗余列為局部冗余列，根據丟失的數據列位置可以分為兩類。

恢復過程為利用局部冗余盤來將丟失的數據列恢復，恢復公式如式（25）所示。再通過編碼方式恢復其他的冗余盤，恢復完畢。

這種情況無法恢復。

證明設丟失的數據列為y，顯然，在構成局部冗余列的方程式（12）中，并不包含元素ai,y，因此不可恢復。

4.3.4 丟失三列冗余列

丟失的三列均為冗余列，發生的概率如式（35）：

恢復過程為通過編碼再次生成三個冗余列。

由以上的討論可得，不可恢復的情況概率之和如式（36）：

而出現三盤故障的概率如式（37）：

因此不可恢復的情況占所有三盤故障情況的比例如式（38）：

5 性能測試

本章通過在集群環境下測試比較RDP與LRRDP的單盤故障恢復性能。實驗環境集群中的機器參數為：CPU Intel Core i7-3632、內存8 GB、磁盤500 GB、測試文件大小10 MB。

5.1 編碼測試

圖9給出了當確定文件塊大小時，素數p取不同值時所需的編碼時間。

圖9 編碼時間比較

由圖9可知，LRRDP編碼時間僅比傳統RDP編碼時間略多。

5.2 單盤故障恢復測試

圖10為 p取不同值時RDP與改進后的RDP的單盤故障恢復開銷在理論上的對比。

圖10 理論上單盤故障恢復讀取開銷對比

而圖11則給出了實際測試過程中，單盤故障恢復時RDP和LRRDP所需要讀取的文件塊數的比較。

圖11 單盤故障恢復讀取開銷對比

通過圖11可知，LRRDP在單盤故障恢復中所需的數據塊個數接近于RDP的50%。

圖12給出了當確定素數 p時，塊文件大小不同時的單盤故障恢復時間，而圖13則給出了當素數 p取不同值時的單盤故障恢復時間。

圖12 p不同時單盤故障恢復時間對比

圖13 塊大小不同時單盤故障恢復時間對比

通過測試結果可得，當 p取值增大，塊文件大小增大時，單盤故障恢復讀取開銷降低的越多。當 p=17、塊文件大小取5 000 Byte時，開銷降低達到了45%。

5.3 雙盤故障恢復測試

圖14給出了當確定文件塊大小時，素數 p取不同值時所需的雙盤故障恢復時間。

圖14 雙盤故障恢復時間對比

5.4 三盤故障恢復測試

圖15 給出了當發生10 000次三盤故障，素數 p取不同值時的不可恢復情況發生的次數。

圖15 不可恢復的三盤故障次數

由圖15可知，當 p逐漸增大，不可恢復的次數逐漸穩定接近于2 500次，即三盤故障總次數的25%。

圖16給出了當確定文件塊大小時，素數 p取不同值時所需的三盤故障平均恢復時間。

圖16 三盤故障平均恢復時間

6 結束語

本文針對RDP編碼存在的單盤故障恢復讀取開銷比較大的問題，對其進行了改造。結合LRC對于RS碼的改造，構造了一種局部修復碼LRRDP。LRRDP碼通過加入一列新的冗余列來減少單盤故障時的讀取開銷。實驗結果顯示LRRDP碼可以有效降低單盤故障恢復的讀取開銷，同時可以恢復75%的三盤故障情況，能夠提升海量數據存儲系統的穩定性和可靠性。實際上，對于EVENODD、STAR以及RTP碼等斜率碼，都可以采用類似改進方法進行改造，相關證明和測試等工作還有待進一步完成。