一種快速重構的raid-6編碼及重構方法
2023-06-28 11:06:01
專利名稱：一種快速重構的raid-6編碼及重構方法
技術領域：
本發明屬於計算機存儲領域，具體涉及一種可以容忍雙盤失效，且滿足RAID-6 特性的新型編碼方法。
背景技術：
磁碟冗餘陣列RAID (Redundant Array of Independent Disk)是一種在較低的成本
下，能夠提供高可靠性、高性能服務的常用方案。在前期的RAID方案中，從RAID-O到 RAID-5,都只能容忍單盤失效。但是最近幾年來，RAID系統的基本單位——磁碟，在 容量上有了顯著的提升。同時，隨著存儲的數據量的增加，大型磁碟陣列的使用越來越 普遍。然而，大型磁碟陣列有更大的可能性造成雙盤失效，這使得RAID-5無法滿足人 們的需求。RAID-6是一種能夠容忍雙盤同時失效的編碼規範，並且越來越受到人們歡迎。 根據網絡存儲工業協會(SNIA)的定義，RAID-6是「在任何形式下，兩個磁碟同時失效 的情況下，仍可以繼續執行讀寫請求的RAID編碼」。目前，已經有很多基於RAID-6 的糾刪碼技術，如 Reed-Solomon 編碼，Cauchy Reed-Solomon 編碼，EVEN0DD 編碼， RDP編碼等等。這些都是極大距離可分MDS (Maximum Distance Separable)編碼。其 中，X-編碼和P-編碼是垂直編碼，其它的都是水平編碼。當然也有非MDSRAID-6編 碼,例如WEAVER編碼，HoVer編碼和Pyramid編碼。然而，上面提到的所有編碼都存在著一定的缺陷。圖1是一種典型的水平MDS RAID-6編碼的結構。它由K+2個磁碟組成，前K個磁碟用來存儲數據，最後兩個盤是 校驗盤，分別叫做P盤和Q盤。水平MDSRAID-6編碼存在一個共同的局限性生成校 驗元素時需要大量數據元素的參與。這一缺陷約束了單盤失效或者雙盤失效情況下的重 構性能。χ-編碼，循環編碼和P-編碼是垂直編碼，但是它們存在著同樣的局限性。磁碟的讀寫性能和重構性能是糾刪碼設計者最關心的問題，在這個問題上已經 有了很多的研究。許多研究者關心如何通過改變結構來提高RAID的重構性能，而非 MDS編碼正是另一種能夠打破重構性能瓶頸的方法。這種編碼方式把校驗信息部署到更 多的校驗元素中，大大降低了構建一個校驗元素的元素數量。例如，WEAVER編碼的設 計核心是如何容忍多個磁碟並發失效。然而，這些方法的缺陷都是存儲效率很低，它的 存儲效率低至50%。這是WEAVER編碼一個很大的缺陷。在某些單盤失效和雙盤失效 的情況下，HoVer編碼有著很高的重構性能，但是，在其它的情況下，它的重構性能甚至 比傳統的MDS編碼還低。而且，HoVer編碼存在空閒的元素，空間利用率低。
發明內容
為了彌補目前各種RAID-6編碼方法存在的局限性，本發明提供了一種快速重構 的RAID-6編碼方法，利用該方法所得到編碼能夠容忍雙盤失效，並且具有高可靠性、高 擴展性、低計算量和低I/O複雜度，以及快速恢復丟失數據的功能；本發明還提供了該編碼的重構方法。本發明提供的一種快速重構的RAID-6編碼方法，設Code_M (N，K)表示 一種RAID-6編碼，其中，N為大於等於2的正整數，K+1為大於等於3的素數，在 Code-M(N, K)中，一個條帶有N個條帶單元集，每個條帶單元集由位於相鄰磁碟上的 K個條帶單元組成，每個條帶單元由同一磁碟上連續K個的元素組成；一個Code-M(N，K)的條帶由N個獨立的K行K列的條帶單元集組成，每一個 條帶單元集擁有同樣的結構，主對角線上的元素被設計為校驗元素，其它的都是數據元 素；SN表示s-1對N求模，對於Code-M (N，K)中的任意一個校驗元素(s， r，c)，它在Code-M(N，K)編碼中是由同一條帶單元集中的一組水平數據元素和序號為 N的條帶單元集中的一組對角線元素通過異或運算得到，一個條帶中所有校驗元素 (s，r, c)的形式化編碼規則，如下
K—l&J^cK—1紐 c(W)= 2 (W+)+ X (N,K+」r^
/=0 /=0式ι中，符號「+」和「Σ」均表示異或運算，&表示邏輯與，i表示該元素 所在列在該條帶單元集中的列號，K+1表示Κ-2-r-i對K+1求模，其中，r+c = K-I,即所有校驗元素(s，r, c)都在條帶單元集的對角線上。上所述RAID-6編碼的重構方法，其特徵在於，根據不同的失效情況分別採用相 應的過程進行重構；情況一、單盤失效假設失效的條帶單元為(S，C)，其重構過程為(1.1)遍歷條帶單元(s，C)中的每一個元素，如果該元素(s，r, C)滿足r+c = K-I,轉入步驟1.2;否則，轉入步驟1.3;所有元素遍歷完後結束此過程；(1.2)使用式I重構該元素，轉入步驟1.1 ；(1.3)使用式II重構該元素，轉入步驟1.1 ；(s, r,c)= YjJ (化+」/·)式 π
/=0 /=0式II中，符號「+」和「Σ」均表示異或運算，&表示邏輯與，i表示該元素 所在列在該條帶單元集中的列號，N表示S-I對N求模，同理，K+1表示 K-2-r-i 對 K+1 求模；情況二、雙盤失效，失效的兩個條帶單元在同一條帶單元集上假設失效的條帶單元為(Sl，C1)、(Sl, C2),其重構過程為(2.1)設r的初值為1 ；(2.2)把 K+1 的值賦予 r ；(2.3) (Sl, r, C1) 一定是數據元素，使用式III進行重構；
K-\K-\&i^c&i^K+1(s,r,c) = Y4(N,K+l,i)+^ (s,K+l,i)
i=0i=0
式III式III中，符號「 + 」和「Σ」均表示異或運算，&表示邏輯與，i表示該元素所在列在該條帶單元集中的列號，N表示S-I對N求模，同理，K+1表示 K-2-r-i 對 K+1 求模，K+1 表示 r+c_i 對 K+1 求模(2.4)如果r+c2^K_l，(Sl，r, C2) —定是數據元素，使用式II進行重構，否 則，(Sl，r，C2) —定是校驗元素，使用式I進行重構；(2.5)如果r+c2 Φ K_l，那麼轉入步驟2.1，否則，轉入步驟2.6 ；(2.6)設r的初值為1 ；(2.7)把 K+1 的值賦予 r ；(2.8) (Sl, r, C2) —定是數據元素，使用式III進行重構；(2.9)如果r+Cl ^K-l，(Sl，r, C1) 一定是數據元素，使用式II進行重構，否 則，(S1, r, C1) 一定是校驗元素，使用式I進行重構；(2.10)如果r+c2 ^K-I，那麼轉入步驟2.6，否則，結束此過程；情況三、雙盤 失效，失效的兩個條帶單元在相鄰的兩個條帶單元集上假設失效的兩條失效的條帶單元分別為(Sl，C1)、(s2, C2),其中N = S2, 其重構過程為(3.1)遍歷條帶單元(Sl，C1)上的所有元素(Sl，r，C1),如果r+Cl=K_l，那麼 轉入步驟3.2，否則，轉入步驟3.3;(3.2) (Sl, r，C1)是校驗元素，使用式I重構該元素，轉入步驟3.4 ；(3.3) (Sl, r, C1)是數據元素，使用式II重構該元素，轉入步驟3.4 ；(3.4)如果遍歷結束，轉入步驟3.5，否則，轉入步驟3.1 ；(3.5)遍歷條帶單元(N，C2)上的所有元素(N，r，c2)，如果 r+c2 = K-I,那麼轉入步驟3.6，否則，轉入步驟3.7;(3.6) (N, r，C2)是校驗元素，使用式I重構該元素，轉入步驟3.8 ；(3.7) (N，r, C2)是數據元素，使用式II重構該元素，轉入步驟3.8 ；(3.8)如果遍歷結束，結束此過程，否則，轉入步驟3.5;情況四、雙盤失效，失效的兩個條帶單元所在的條帶之間的條帶單元集間距為 2 假設失效的兩條失效的條帶單元分別為(Sl，C1)、(s2, C2),其中N = s2， 其重構過程為(4.1)遍歷條帶單元(Sl，C1)上的所有元素(Sl，r，C1),如果r+Cl=K_l，那麼 轉入步驟4.2，否則，轉入步驟4.3;(4.2) (Sl, r, C1)是校驗元素，使用式I重構該元素，轉入步驟4.4 ；(4.3) (Sl, r, C1)是數據元素，使用式III重構該元素，轉入步驟4.4 ；(4.4)如果遍歷結束，轉入步驟4.5，否則，轉入步驟4.1;(4.5)遍歷條帶單元(N，c2)上的所有元素(n，r，c2)，如果 r+c2 = K-I,那麼轉入步驟4.6，否則，轉入步驟4.7;(4.6) (N, r, C2)是校驗元素，使用式I重構該元素，轉入步驟4.8 ；(4.7) (N, r, C2)是數據元素，使用式II重構該元素，轉入步驟4.8 ；(4.8)如果遍歷結束，結束此過程，否則，轉入步驟4.5;情況五、雙盤失效，失效的兩個條帶單元所在的條帶之間的條帶單元集間距大於或等於3 假設失效的兩條失效的條帶單元分別為(Sl，C1)、(s2, C2)，其中N> = 3，其重構過程為(5.1)遍歷條帶單元(Sl，C1)上的所有元素(Sl，r，C1),如果r+Cl=K_l，那麼 轉入步驟5.2，否則，轉入步驟5.3;(5.2) (Sl, r，C1)是校驗元素，使用式I重構該元素，轉入步驟5.4 ；(5.3) (Sl, r, C1)是數據元素，使用式II重構該元素，轉入步驟5.4 ；(5.4)如果遍歷結束，轉入步驟5.5，否則，轉入步驟5.1 ；(5.5)遍歷條帶單元(s2, C2)上的所有元素(s2, r，c2)，如果r+c2 = K-I,那麼 轉入步驟5.6，否則，轉入步驟5.7;(5.6) (s2, r，C2)是校驗元素，使用式I重構該元素，轉入步驟5.8 ；(5.7) (s2, r, C2)是數據元素，使用式II重構該元素，轉入步驟5.8 ；如果遍歷 結束，結束此過程，否則，轉入步驟5.5。同時考慮到RAID-6系統大部分時間工作在正常模式下，單盤失效情況是次要 的，而雙盤失效的概率更低這一實際情況，本發明設計了上述新的方案來構建RAID-6 編碼，稱之為Code-M。為了能夠容忍雙盤失效，並且希望各方面的性能都有所提高， Code-M將校驗信息部署到更多的校驗元素中。具體而言，Code-M有以下幾個主要特佔.(I)Code-M是一種新的基於集合的RAID-6編碼方案。同時，我們提出了一種 新的概念——條帶單元集，來構建編碼方案。這樣的RAID-6編碼能夠在較低的成本下 獲得較高的性能。(2)Code-M極大地降低了單盤失效模式下重構的I/O量和計算複雜度。(3)在大部分情況下，Code-M降低了雙盤失效情況下的I/O量和計算複雜度。
圖1是一種典型的水平MDS RAID-6編碼；圖2是一種典型的Code-M (N，K)編碼的結構，其中N = 3，K = 4;圖3是Code-M(N，K)構建的流程圖；圖4是Code-M (N，K)重構的總體流程圖；圖5是在重構的第一種情況下，單個條帶重構流程；圖6是在重構的第二種情況下，單個條帶重構流程；圖7是在重構的第三種和第五種情況下，單個條帶重構流程；圖8是在重構的第四種情況下，單個條帶重構流程。
具體實施例方式首先，定義一下與Code-M相關的一些概念· n n表示M模η的值，值的範圍是O到η_1。 元素編碼時的基本單位。一個元素可以是磁碟上的IBit，也可以是一個連 續的數據塊。有兩種形式的元素，分別是數據元素和校驗元素。
條帶在糾刪碼中，條帶是可以獨立的恢復丟失的數據元素或校驗元素的元
素集合。 條帶單元一個條帶中，同一磁碟上的所有連續數據叫做條帶單元。 條帶單元集一個條帶中，相鄰磁碟上的若干條帶單元組成的集合。 條帶單元間距兩個條帶單元集之間的最小距離。如果有兩個條帶單元集， 它們的編號分別為Sl和s2，那麼這兩個條帶單元集之間的距離就是min(N， N)。 校驗鏈一條校驗鏈包括校驗元素和所有創建校驗元素的數據元素。 校驗鏈長度一條校驗鏈上，所有元素的數量。 水平編碼一種糾刪碼，所有數據元素和校驗元素在同一條帶單元上。 垂直編碼一種糾刪碼，所有數據元素在一個條帶單元中，或者所有校驗元 素在一個條帶單元中。一、Code-M(N, K)的構建本發明使用Code-M(N，K)來表示某一特定的Code-M結構，其中，N為大於 等於2的正整數，K+1為大於等於3的素數。在這樣結構的Code-M中，一個條帶有N 個條帶單元集，每個條帶單元集由位於相鄰磁碟上的K個條帶單元組成，每個條帶單元 由同一磁碟上連續K個的元素組成。Code-M(N，K)表示一個K行、K*N列模型的編 碼，共有K*N個條帶單元。I.數據/校驗元素標記一個Code_M(N，K)的條帶由N個獨立的K行K列的條帶單元集組成。每一 個條帶單元集擁有同樣的結構，主對角線上的元素，即圖2中標記著ρ的元素，被設計為 校驗元素，其它的都是數據元素。我們用二元組(X，Z)來表示在一個條帶中的某一條 帶單元。X表示條帶單元集的序號，0=<X<=N_1。Z表示該列在這一條帶中的列 號，0=<Ζ<=Κ_1。我們使用三元組(X，Y，Ζ)表示每一個元素。X表示該元素 所在的條帶單元集的序號，0=<X< = N-1。Y表示該元素所在的行號，0=<Υ< = K-l。Z表示該元素所在列在該條帶單元集中的列號，O =< Z <=Κ_1。圖2是一種 典型的Code-M(N，K)編碼的結構，其中N = 3，K = 4。II Code-M 的構建設<8_1、表示s-1對N求模，對於任意一個校驗元素(s，r，c)，它在 Code-M(N, K)編碼中是由同一條帶單元集中的一組水平數據元素和序號為N的條 帶單元集中的一組對角線元素通過異或運算得到。一個條帶中所有校驗元素(s，r, c)的 形式化編碼規則，如下
權利要求
1. 一種快速重構的RAID-6編碼方法，設Code-M(N，K)表示一種RAID-6編碼， 其中，N為大於等於2的正整數，K+1為大於等於3的素數，在Code_M(N，K)中，一 個條帶有N個條帶單元集，每個條帶單元集由位於相鄰磁碟上的K個條帶單元組成，每 個條帶單元由同一磁碟上連續K個的元素組成；一個Code_M(N，K)的條帶由N個獨立的K行K列的條帶單元集組成，每一個條帶 單元集擁有同樣的結構，主對角線上的元素被設計為校驗元素，其它的都是數據元素；SN表示S-I對N求模，對於Code_M(N，K)中的任意一個校驗元素(s，r， c)，它在Code_M(N，K)編碼中是由同一條帶單元集中的一組水平數據元素和序號為 N的條帶單元集中的一組對角線元素通過異或運算得到，一個條帶中所有校驗元素 (s，r, c)的形式化編碼規則，如下K—l&J^cK—1紐 c(s,r,c)= ^ Cw')+ Σ (N,K+l,i)^ii=0 i=0式ι中，符號「+」和「Σ」均表示異或運算，&表示邏輯與，i表示該元素所在列 在該條帶單元集中的列號，K+1表示Κ-2-r-i對K+1求模，其中，r+c = K_l， 即所有校驗元素(s，r，c)都在條帶單元集的對角線上。
2.—種權利要求1所述RAID-6編碼的重構方法，其特徵在於，根據不同的失效情況 分別採用相應的過程進行重構；情況一、單盤失效假設失效的條帶單元為(s，c)，其重構過程為(1.1)遍歷條帶單元(s，C)中的每一個元素，如果該元素(s，r，c)滿足r+c= K_l， 轉入步驟1.2;否則，轉入步驟1.3;所有元素遍歷完後結束此過程；(1.2)使用式I重構該元素，轉入步驟1.1；(1.3)使用式II重構該元素，轉入步驟1.1；(W)= Yj Cw+)+ Yj (N,K+lJ)^ II/=0 /=0式II中，符號「+」和「Σ」均表示異或運算，&表示邏輯與，i表示該元素所在列 在該條帶單元集中的列號，N表示S-I對N求模，同理，K+1表示K-2-r-i 對K+1求模；情況二、雙盤失效，失效的兩個條帶單元在同一條帶單元集上假設失效的條帶單元為(Sl，C1)、(Sl, C2),其重構過程為(2.1)設r的初值為1；(2.2)把〈r+cfcpm的值賦予r；(2.3)(Sl，r, C1) 一定是數據元素，使用式III進行重構；^-lK-\&i^c&i^K+1(s,r,c) = Yj(N,K+lJ)^ ^ 0,< r + c-ζ.、+1,/)式 IIIi=0 i=0式III中，符號「+」和「Σ」均表示異或運算，&表示邏輯與，i表示該元素所在列 在該條帶單元集中的列號，N表示S-I對N求模，同理，K+1表示K-2-r-i 對K+1求模，K+1表示r+c-i對K+1求模(2.4)如果r+c2^K_l，(Sl,r, C2) —定是數據元素，使用式II進行重構，否則，(S1, r, C2) —定是校驗元素，使用式I進行重構；(2.5)如果r+c2^K-I,那麼轉入步驟2.1，否則，轉入步驟2.6 ；(2.6)設r的初值為1；(2.7)把K+1 的值賦予 r ；(2.8)(Sl，r, C2) —定是數據元素，使用式III進行重構；(2.9)如果r+Cl^K_l，(Sl,r, C1) 一定是數據元素，使用式II進行重構，否則， (Sl, r, C1) 一定是校驗元素，使用式I進行重構；(2.10)如果r+c2^K-I，那麼轉入步驟2.6，否則，結束此過程；情況三、雙盤失效，失效的兩個條帶單元在相鄰的兩個條帶單元集上假設失效的兩條失效的條帶單元分別為(Sl，C1)、(s2, C2),其中N = S2，其重 構過程為(3.1)遍歷條帶單元(Sl，C1)上的所有元素(Sl，r,C1),如果r+Cl=K_l，那麼轉入 步驟3.2，否則，轉入步驟3.3;(3.2)(Sl, r, C1)是校驗元素，使用式I重構該元素，轉入步驟3.4;(3.3)(Sl, r, C1)是數據元素，使用式II重構該元素，轉入步驟3.4;(3.4)如果遍歷結束，轉入步驟3.5，否則，轉入步驟3.1;(3.5)遍歷條帶單元(N，c2)上的所有元素(N，r，c2),如果r+c2= K-I,那麼轉入步驟3.6，否則，轉入步驟3.7;(3.6)(N，r, C2)是校驗元素，使用式I重構該元素，轉入步驟3.8;(3.7)(N，r, C2)是數據元素，使用式II重構該元素，轉入步驟3.8;(3.8)如果遍歷結束，結束此過程，否則，轉入步驟3.5;情況四、雙盤失效，失效的兩個條帶單元所在的條帶之間的條帶單元集間距為2:假設失效的兩條失效的條帶單元分別為(Sl，C1)、(s2, C2),其中N = S2，其重 構過程為(4.1)遍歷條帶單元(Sl，C1)上的所有元素(Sl，r,C1),如果r+Cl=K_l，那麼轉入 步驟4.2，否則，轉入步驟4.3;(4.2)(Sl, r, C1)是校驗元素，使用式I重構該元素，轉入步驟4.4;(4.3)(Sl，r, C1)是數據元素，使用式III重構該元素，轉入步驟4.4 ；(4.4)如果遍歷結束，轉入步驟4.5，否則，轉入步驟4.1;(4.5)遍歷條帶單元(N，c2)上的所有元素(n，r，c2)，如果r+c2= K-I,那麼轉入步驟4.6，否則，轉入步驟4.7;(4.6)(N, r, C2)是校驗元素，使用式I重構該元素，轉入步驟4.8;(4.7)(N, r, C2)是數據元素，使用式II重構該元素，轉入步驟4.8 ；(4.8)如果遍歷結束，結束此過程，否則，轉入步驟4.5;情況五、雙盤失效，失效的兩個條帶單元所在的條帶之間的條帶單元集間距大於或 等於3:假設失效的兩條失效的條帶單元分別為(S1, C1)、(s2, C2),其中N>=3，其 重構過程為(5.1)遍歷條帶單元(Sl，C1)上的所有元素(Sl，r, C1),如果r+Cl=K_l，那麼轉入步驟5.2，否則，轉入步驟5.3;(5.2)(Sl, r, C1)是校驗元素，使用式I重構該元素，轉入步驟5.4;(5.3)(Sl, r, C1)是數據元素，使用式II重構該元素，轉入步驟5.4;(5.4)如果遍歷結束，轉入步驟5.5，否則，轉入步驟5.1;(5.5)遍歷條帶單元(s2，c2)上的所有元素(s2，r，c2),如果r+c2=Κ_1，那麼轉入 步驟5.6，否則，轉入步驟5.7;(5.6)(s2, r, C2)是校驗元素，使用式I重構該元素，轉入步驟5.8;(5.7)(s2, r, C2)是數據元素，使用式II重構該元素，轉入步驟5.8; 如果遍歷結束，結束此過程，否則，轉入步驟5.5。
全文摘要
本發明公開了一種快速重構的RAID-6編碼及重構方法，可以容忍雙盤失效，且滿足RAID-6特性。這種編碼方法是一種具有最優化恢復時間的非MDS RAID-6型編碼。磁碟的讀寫性能和重構性能是糾刪碼設計者最關心的問題，現有的RAID-6編碼存在著一定的局限性。有的RAID-6編碼生成校驗元素時需要大量數據元素的參與，約束了單盤失效或者雙盤失效情況下的重構性能，有的編碼存儲效率或者空間利用率低，進而影響了讀寫性能。本發明不但在重構性能有很大的提高，而且有著很好的讀寫性能，與目前主流的RAID-6型編碼相比較，在許多方面都有著明顯的優勢。本發明具有高可靠性、高擴展性、低計算量和低I/O複雜度，以及快速恢復丟失數據的功能，這些優勢使它有著實用性和推廣潛力。
文檔編號G06F11/20GK102012792SQ20101052903
公開日2011年4月13日 申請日期2010年11月2日 優先權日2010年11月2日
發明者萬勝剛, 曹強, 詹盛輝, 謝長生, 黃建忠 申請人:華中科技大學