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

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

1.成都信息工程大學(xué) 軟件工程學(xué)院，成都 610225

2.四川省計(jì)算機(jī)研究院，成都 610041

1 引言

近年來(lái)，隨著信息技術(shù)的快速發(fā)展，世界上的數(shù)據(jù)量正不斷增長(zhǎng)，而存儲(chǔ)系統(tǒng)的規(guī)模也日益增大，廉價(jià)存儲(chǔ)設(shè)備的應(yīng)用也逐漸變得廣泛。而隨著規(guī)模的增大、廉價(jià)磁盤數(shù)目的增多，存儲(chǔ)系統(tǒng)中磁盤發(fā)生故障的概率也在上升，從而導(dǎo)致存儲(chǔ)系統(tǒng)的穩(wěn)定性所面臨更加嚴(yán)峻的挑戰(zhàn)。因此大多數(shù)存儲(chǔ)系統(tǒng)都會(huì)為了保障數(shù)據(jù)的可靠存儲(chǔ)而使用容錯(cuò)技術(shù)。

常用的容錯(cuò)技術(shù)有兩種：副本技術(shù)和糾刪碼技術(shù)。副本技術(shù)是指通過復(fù)制原數(shù)據(jù)并存儲(chǔ)其副本，來(lái)保障當(dāng)發(fā)生任意小于副本數(shù)目的錯(cuò)誤時(shí)，都可以通過備份的副本來(lái)保障數(shù)據(jù)的完整性和可靠性。副本技術(shù)的優(yōu)點(diǎn)在于算法簡(jiǎn)單，易于實(shí)現(xiàn)，且恢復(fù)速度極快。而副本技術(shù)最大的缺點(diǎn)在于存儲(chǔ)開銷過大，需要許多的冗余存儲(chǔ)才能夠保證數(shù)據(jù)的可靠。而糾刪碼技術(shù)則是通過相應(yīng)的算法來(lái)生成少量的冗余數(shù)據(jù)，并與原數(shù)據(jù)一起存儲(chǔ)。當(dāng)故障發(fā)生時(shí)，則通過對(duì)應(yīng)的解碼算法對(duì)于剩余數(shù)據(jù)和冗余數(shù)據(jù)進(jìn)行運(yùn)算得到原數(shù)據(jù)。糾刪碼技術(shù)解決了副本技術(shù)帶來(lái)的冗余過多的問題，同時(shí)能夠在一定程度上保證數(shù)據(jù)的完整性和可靠性，因此是目前存儲(chǔ)系統(tǒng)中主流的容錯(cuò)策略。

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

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

2 RDP介紹

2.1 RDP編碼過程

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

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

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

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

圖1 水平冗余和對(duì)角線冗余計(jì)算過程

2.2 RDP單盤故障恢復(fù)過程

傳統(tǒng)的RDP單盤故障恢復(fù)方法可以根據(jù)丟失的列位置分為數(shù)據(jù)列丟失和冗余列丟失兩種類型。

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

圖2 單盤故障恢復(fù)所需讀取的數(shù)據(jù)

由圖2可知，當(dāng)數(shù)據(jù)列發(fā)生故障時(shí)，需要讀取的列數(shù)目為p-1，即原陣列中總共的數(shù)據(jù)列列數(shù)。

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

因此對(duì)于傳統(tǒng)的單盤故障恢復(fù)方法而言，無(wú)論是數(shù)據(jù)列丟失還是冗余列丟失，恢復(fù)過程所需要讀取的列數(shù)量均為p-1個(gè)。

2.3 RDP相關(guān)研究

為了對(duì)RDP進(jìn)行擴(kuò)展，文獻(xiàn)[8]提出在RDP基礎(chǔ)上再增加一個(gè)冗余列，其計(jì)算過程是將斜率為-1的斜線上的數(shù)據(jù)塊進(jìn)行異或，構(gòu)造出一種新的三容錯(cuò)RAID碼。而文獻(xiàn)[9]則同樣提出在RDP基礎(chǔ)上增加新的冗余列，其計(jì)算過程是將斜率為2的斜線上的數(shù)據(jù)塊進(jìn)行異或，得出了另一種新的三容錯(cuò)RAID碼。

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

如圖3所示，當(dāng)Disk0失效時(shí)，對(duì)于前兩個(gè)數(shù)據(jù)塊通過水平冗余列來(lái)進(jìn)行恢復(fù)，對(duì)于后兩個(gè)數(shù)據(jù)塊通過對(duì)角線冗余來(lái)進(jìn)行恢復(fù)。其中“○”表示利用水平冗余所需要讀取的數(shù)據(jù)塊，而“□”表示利用對(duì)角線冗余所需要讀取的數(shù)據(jù)塊，而兩者都有則表示重復(fù)的數(shù)據(jù)塊。

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

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

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

3 局部修復(fù)RDP編碼及相關(guān)性質(zhì)

為了進(jìn)一步地降低RDP碼在單盤故障時(shí)的恢復(fù)讀取開銷，縮短恢復(fù)時(shí)間，本文構(gòu)造了一種LRRDP碼（Local Repairable RDP）。

3.1 編碼過程

LRRDP碼的編碼過程如圖4所示，相同形狀的白色元素生成對(duì)應(yīng)的黑色校驗(yàn)塊。

圖4 LRRDP編碼過程

3.2 編碼開銷

4 局部修復(fù)RDP解碼

4.1 單盤故障

對(duì)于傳統(tǒng)的RDP編碼，修復(fù)單盤故障（非冗余列）的方式是通過讀取剩余數(shù)據(jù)列以及水平冗余列進(jìn)行異或來(lái)恢復(fù)。對(duì)于LRRDP，修復(fù)單盤故障分為4種情況。

4.1.1數(shù)據(jù)列丟失

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

圖5 丟失數(shù)據(jù)列在前半部分時(shí)所需讀取數(shù)據(jù)

恢復(fù)所需的數(shù)據(jù)塊如圖6所示。

圖6 丟失數(shù)據(jù)列在后半部分時(shí)所需讀取數(shù)據(jù)

4.1.2 局部冗余列丟失

4.1.3 水平冗余列丟失

4.1.4對(duì)角冗余列丟失

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

對(duì)于單盤故障恢復(fù)來(lái)說，假設(shè)每個(gè)盤發(fā)生故障的概率一致，則擴(kuò)展后的RDP單盤故障恢復(fù)平均開銷如式（7）所示：

圖7 水平冗余列丟失時(shí)所需讀取數(shù)據(jù)

4.2 雙盤故障

4.2.1丟失兩列數(shù)據(jù)列

對(duì)于擴(kuò)展后的RDP，丟失兩個(gè)數(shù)據(jù)列的恢復(fù)過程與傳統(tǒng)RDP的雙盤故障恢復(fù)方法相同，數(shù)據(jù)的讀取開銷如式（8）所示：

4.2.2 丟失一列數(shù)據(jù)列和局部冗余列

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

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

圖8 雙盤故障恢復(fù)所需讀取數(shù)據(jù)

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

4.2.3丟失一列數(shù)據(jù)列和水平或?qū)蔷€冗余列

恢復(fù)過程與傳統(tǒng)RDP恢復(fù)方法一致，讀取開銷為p-1列。

4.2.4丟失兩列冗余列

恢復(fù)過程與編碼過程相同，顯然，當(dāng)丟失水平和對(duì)角冗余列時(shí)，讀取開銷為 p-1列。當(dāng)丟失水平和局部冗余列時(shí)，讀取開銷也為p-1列。而當(dāng)丟失對(duì)角和局部冗余列時(shí)，讀取開銷為p列。

綜上，對(duì)于任意的雙盤故障，LRRDP能夠保證數(shù)據(jù)的完整性和可靠性。同時(shí)，LRRDP的雙盤故障恢復(fù)讀取開銷與傳統(tǒng)RDP保持基本一致。

4.3 三盤故障

LRRDP中的三個(gè)冗余列的計(jì)算可由式（10）～（12）表示：

同時(shí)設(shè)每個(gè)磁盤發(fā)生故障的概率為γ。

在LRRDP中，三盤故障恢復(fù)的關(guān)鍵在于將三盤故障轉(zhuǎn)換為傳統(tǒng)的RDP雙盤故障情況。對(duì)于傳統(tǒng)的RDP雙盤故障恢復(fù)過程，文獻(xiàn)[2]中有具體描述，不再贅述。

4.3.1 丟失的三列均為數(shù)據(jù)列

當(dāng)丟失的均為數(shù)據(jù)列時(shí)，按照三個(gè)數(shù)據(jù)列的位置分布可以分為三種情況。

這種情況不可恢復(fù)。

對(duì)式（14）經(jīng)過變換后可得式（16）：

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

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

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

再通過傳統(tǒng)RDP解碼方法恢復(fù)剩余兩個(gè)丟失列，恢復(fù)完畢。

再通過傳統(tǒng)RDP解碼方法恢復(fù)剩余兩個(gè)丟失列，恢復(fù)完畢。

4.3.2 丟失的兩列為數(shù)據(jù)列，一列為冗余列

當(dāng)丟失三個(gè)列，其中有兩個(gè)是數(shù)據(jù)列，另外一個(gè)是冗余列，根據(jù)冗余列類型可分為三種情況。

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

恢復(fù)過程為通過傳統(tǒng)RDP解碼方法恢復(fù)丟失的兩個(gè)數(shù)據(jù)列，之后通過編碼方法重新生成局部冗余列。

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

這種情況無(wú)法恢復(fù)。

再通過傳統(tǒng)RDP解碼方法恢復(fù)丟失的數(shù)據(jù)列和水平冗余列，恢復(fù)完畢。

第三種情況是對(duì)角冗余列丟失，根據(jù)丟失的數(shù)據(jù)列的分布情況也可以分為兩類。

這種情況無(wú)法恢復(fù)。

其中對(duì)式（27）經(jīng)過變換后可得式（29）：

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

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

4.3.3 丟失一個(gè)數(shù)據(jù)列，兩個(gè)冗余列

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

第一種情況是剩余的冗余列是水平冗余列或?qū)侨哂嗔校l(fā)生的概率如式（32）：

恢復(fù)過程為通過傳統(tǒng)的RDP雙盤恢復(fù)方式恢復(fù)兩個(gè)丟失的數(shù)據(jù)列，再通過編碼的方式重新生成局部冗余列，恢復(fù)完畢。

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

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

這種情況無(wú)法恢復(fù)。

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

4.3.4 丟失三列冗余列

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

恢復(fù)過程為通過編碼再次生成三個(gè)冗余列。

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

而出現(xiàn)三盤故障的概率如式（37）：

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

5 性能測(cè)試

本章通過在集群環(huán)境下測(cè)試比較RDP與LRRDP的單盤故障恢復(fù)性能。實(shí)驗(yàn)環(huán)境集群中的機(jī)器參數(shù)為：CPU Intel Core i7-3632、內(nèi)存8 GB、磁盤500 GB、測(cè)試文件大小10 MB。

5.1 編碼測(cè)試

圖9給出了當(dāng)確定文件塊大小時(shí)，素?cái)?shù)p取不同值時(shí)所需的編碼時(shí)間。

圖9 編碼時(shí)間比較

由圖9可知，LRRDP編碼時(shí)間僅比傳統(tǒng)RDP編碼時(shí)間略多。

5.2 單盤故障恢復(fù)測(cè)試

圖10為 p取不同值時(shí)RDP與改進(jìn)后的RDP的單盤故障恢復(fù)開銷在理論上的對(duì)比。

圖10 理論上單盤故障恢復(fù)讀取開銷對(duì)比

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

圖11 單盤故障恢復(fù)讀取開銷對(duì)比

通過圖11可知，LRRDP在單盤故障恢復(fù)中所需的數(shù)據(jù)塊個(gè)數(shù)接近于RDP的50%。

圖12給出了當(dāng)確定素?cái)?shù) p時(shí)，塊文件大小不同時(shí)的單盤故障恢復(fù)時(shí)間，而圖13則給出了當(dāng)素?cái)?shù) p取不同值時(shí)的單盤故障恢復(fù)時(shí)間。

圖12 p不同時(shí)單盤故障恢復(fù)時(shí)間對(duì)比

圖13 塊大小不同時(shí)單盤故障恢復(fù)時(shí)間對(duì)比

通過測(cè)試結(jié)果可得，當(dāng) p取值增大，塊文件大小增大時(shí)，單盤故障恢復(fù)讀取開銷降低的越多。當(dāng) p=17、塊文件大小取5 000 Byte時(shí)，開銷降低達(dá)到了45%。

5.3 雙盤故障恢復(fù)測(cè)試

圖14給出了當(dāng)確定文件塊大小時(shí)，素?cái)?shù) p取不同值時(shí)所需的雙盤故障恢復(fù)時(shí)間。

圖14 雙盤故障恢復(fù)時(shí)間對(duì)比

5.4 三盤故障恢復(fù)測(cè)試

圖15 給出了當(dāng)發(fā)生10 000次三盤故障，素?cái)?shù) p取不同值時(shí)的不可恢復(fù)情況發(fā)生的次數(shù)。

圖15 不可恢復(fù)的三盤故障次數(shù)

由圖15可知，當(dāng) p逐漸增大，不可恢復(fù)的次數(shù)逐漸穩(wěn)定接近于2 500次，即三盤故障總次數(shù)的25%。

圖16給出了當(dāng)確定文件塊大小時(shí)，素?cái)?shù) p取不同值時(shí)所需的三盤故障平均恢復(fù)時(shí)間。

圖16 三盤故障平均恢復(fù)時(shí)間

6 結(jié)束語(yǔ)

本文針對(duì)RDP編碼存在的單盤故障恢復(fù)讀取開銷比較大的問題，對(duì)其進(jìn)行了改造。結(jié)合LRC對(duì)于RS碼的改造，構(gòu)造了一種局部修復(fù)碼LRRDP。LRRDP碼通過加入一列新的冗余列來(lái)減少單盤故障時(shí)的讀取開銷。實(shí)驗(yàn)結(jié)果顯示LRRDP碼可以有效降低單盤故障恢復(fù)的讀取開銷，同時(shí)可以恢復(fù)75%的三盤故障情況，能夠提升海量數(shù)據(jù)存儲(chǔ)系統(tǒng)的穩(wěn)定性和可靠性。實(shí)際上，對(duì)于EVENODD、STAR以及RTP碼等斜率碼，都可以采用類似改進(jìn)方法進(jìn)行改造，相關(guān)證明和測(cè)試等工作還有待進(jìn)一步完成。