低編譯復(fù)雜度的雙容錯(cuò)陣列碼

解 崢，王子豪，唐 聃*，張 航，蔡紅亮

（1.成都信息工程大學(xué) 軟件工程學(xué)院，成都 610225；2.四川省信息化應(yīng)用支撐軟件工程技術(shù)研究中心，成都 610225；3.中國(guó)電子科技集團(tuán)第三十研究所，成都 610041）

0 引言

隨著存儲(chǔ)需求的持續(xù)增加，為保證存儲(chǔ)系統(tǒng)的高性能和可靠性，獨(dú)立磁盤冗余陣列（Redundant Array of Independent Disks，RAID）技術(shù)［1］得到廣泛的認(rèn)可和應(yīng)用。由于技術(shù)發(fā)展趨勢(shì)［2-3］，發(fā)生并發(fā)磁盤故障的可能性隨著系統(tǒng)規(guī)模的增長(zhǎng)而增加［4-5］，RAID-6［2］在RAID 的眾多策略中脫穎而出，得到了廣泛應(yīng)用，并成為目前研究的重點(diǎn)。

RAID-6 的雙容錯(cuò)能力通過底層的糾刪碼技術(shù)實(shí)現(xiàn)，因此，RAID-6 的性能與使用的糾刪碼密不可分。由于異或（Exclusive OR，XOR）運(yùn)算的特性，陣列碼在編譯碼過程中具有較低的計(jì)算復(fù)雜度，因此也常用于RAID-6 中底層糾刪碼的實(shí)現(xiàn)。典型的陣列碼有EVENODD［6］、RDP（Row-Diagonal Parity）［3］和X-code［7］等。EVENODD 和RDP 使用兩個(gè)特定的校驗(yàn)磁盤存儲(chǔ)校驗(yàn)位，它們的缺點(diǎn)是連續(xù)的寫操作會(huì)導(dǎo)致磁盤熱點(diǎn)集中和I/O 瓶頸。雖然X-code 獨(dú)特的結(jié)構(gòu)克服了這些缺陷，但磁盤間的依賴性較強(qiáng)，導(dǎo)致擴(kuò)展性不足［8］。近年來(lái)，新的陣列碼也在不斷被提出，如N-code［9］、EaR（Enduranceaware RAID-6）［10］以及Thou Code［11］。這些陣列碼分別對(duì)復(fù)雜均衡、編譯復(fù)雜度以及容錯(cuò)能力進(jìn)行優(yōu)化，可作為RAID-6的底層編碼保障數(shù)據(jù)可靠性。

雖然糾刪碼可以容忍多個(gè)磁盤的并發(fā)故障，但在實(shí)際應(yīng)用中單磁盤故障的恢復(fù)場(chǎng)景占全部恢復(fù)場(chǎng)景的99.75%［4］。因此，單磁盤故障恢復(fù)的性能對(duì)于存儲(chǔ)系統(tǒng)也至關(guān)重要。但RIAD-6 中的經(jīng)典陣列碼EVENODD、RDP 和X-code 在單磁盤故障恢復(fù)過程中對(duì)存活磁盤的讀取次數(shù)較多，單盤恢復(fù)性能不足。為了提高單磁盤故障恢復(fù)的性能，Huang 等［12］通過增加冗余位的方式，降低了單盤修復(fù)時(shí)的數(shù)據(jù)下載量；Deng等［13］對(duì)X-code 進(jìn)行改進(jìn)，縮小了數(shù)據(jù)重建窗口；Fu 等［14］考慮到真實(shí)存儲(chǔ)系統(tǒng)中存在邏輯磁盤旋轉(zhuǎn)映射到磁盤，設(shè)計(jì)了兩種基于貪婪算法的恢復(fù)機(jī)制以減少修復(fù)過程I/O；Li 等［15］提出了具有雙層碼結(jié)構(gòu)的OI-RAID，可加快磁盤恢復(fù)；Chen等［16］對(duì)HV Code（Horizontal-Vertical Code）［17］在單磁盤故障恢復(fù)上進(jìn)行優(yōu)化，具有更少的磁盤讀取次數(shù)；Huang 等［18］改進(jìn)了Liberation 碼［19］的編譯碼算法，消除了編譯碼過程中的冗余計(jì)算，從而減少了數(shù)據(jù)恢復(fù)過程的異或次數(shù)。

針對(duì)現(xiàn)有陣列碼的不足，本文提出了一種基于異或運(yùn)算的混合陣列糾刪碼——J 碼（J-code）。J-code 結(jié)合了橫式陣列碼和縱式陣列碼的優(yōu)點(diǎn)，具有較低的編譯碼復(fù)雜度和較少的XOR 操作數(shù)，還能容許任意兩個(gè)磁盤的并發(fā)故障。J-code沿對(duì)角線和反對(duì)角線方向生成校驗(yàn)位，將部分校驗(yàn)位均勻分布在數(shù)據(jù)磁盤中，相較于橫式陣列碼中使用多個(gè)專用的校驗(yàn)磁盤，J-code 僅有一個(gè)校驗(yàn)磁盤，可以在一定程度上緩解磁盤I/O 瓶頸和失衡問題，降低了編譯碼復(fù)雜度；相較于縱式陣列碼，J-code 提高了碼率，并節(jié)省了單節(jié)點(diǎn)修復(fù)占用的I/O資源。

1 相關(guān)工作

在陣列碼被提出前，存儲(chǔ)系統(tǒng)廣泛應(yīng)用的糾刪碼為RS（Reed-Solomon）碼［20］，隨后，Plank［21］將RS 編碼算法應(yīng)用于RAID 存儲(chǔ)系統(tǒng)中。雖然RS 碼具有最大距離可分（Maximum Distance Separable，MDS）［22］性質(zhì)和理論上無(wú)限容錯(cuò)等優(yōu)點(diǎn)，但它的編譯碼過程涉及有限域上的計(jì)算，計(jì)算復(fù)雜度高［2］。為降低計(jì)算復(fù)雜度，Blaum 等［6］提出了一種陣列糾刪碼EVENODD，與RS 碼相比，EVENODD 最突出的優(yōu)點(diǎn)是計(jì)算復(fù)雜度低、編譯碼速度快。隨著研究的深入，陣列碼最終取代RS 碼，廣泛應(yīng)用于RAID 的編碼實(shí)現(xiàn)中。RAID-6中使用的陣列碼分為橫式陣列碼和縱式陣列碼。橫式陣列碼的特點(diǎn)是原始數(shù)據(jù)位和校驗(yàn)位分布在不同的列上，典型的橫式陣列碼包括EVENODD、RDP 等；縱式陣列碼的特點(diǎn)是校驗(yàn)位均勻分布在各列中，與原始數(shù)據(jù)位混合放置，典型的縱式陣列碼有X-code、P-code［23］等。

橫式陣列碼和縱式陣列碼的編碼結(jié)構(gòu)對(duì)它們的性能也造成了不同影響：橫式陣列碼有多個(gè)專用于放置校驗(yàn)塊的校驗(yàn)列，校驗(yàn)信息集中在特定校驗(yàn)盤上，造成讀寫開銷大、I/O瓶頸和I/O 不平衡等問題；縱式陣列碼數(shù)據(jù)塊和校驗(yàn)塊均勻分布在各列中，具有良好的單寫復(fù)雜度和編譯碼效率，但存儲(chǔ)效率往往不及具有相同容錯(cuò)能力的橫式陣列碼，磁盤間緊密的邏輯聯(lián)系也限制了縱式陣列碼的擴(kuò)展能力。

近年來(lái)，雙容錯(cuò)的陣列碼不斷被提出，如EaR［10］、N-code［9］等，但學(xué)術(shù)界對(duì)混合陣列碼的研究依然較少。EaR屬于橫式陣列碼，使用兩塊專用的校驗(yàn)磁盤分別保存行校驗(yàn)位和對(duì)角校驗(yàn)位，其中保存對(duì)角校驗(yàn)位的磁盤比其他磁盤多存儲(chǔ)一個(gè)數(shù)據(jù)塊，因此磁盤存儲(chǔ)的數(shù)據(jù)量并不統(tǒng)一。EaR 優(yōu)化了編譯碼復(fù)雜度，但未在單磁盤恢復(fù)性能方面進(jìn)行優(yōu)化。N-code 是一種混合陣列碼，沒有專用的校驗(yàn)磁盤，而是將校驗(yàn)塊與數(shù)據(jù)塊一同分散在所有磁盤中，其中，行校驗(yàn)塊按階梯狀分布，第一個(gè)磁盤和最后一個(gè)磁盤均使用一半的空間存儲(chǔ)對(duì)角校驗(yàn)位。N-code 在降級(jí)讀和負(fù)載均衡方面進(jìn)行了優(yōu)化，但編譯碼復(fù)雜度和單磁盤恢復(fù)性能并沒有提升。目前，縱式陣列碼除了X-code、P-code 外，受到的關(guān)注較少，在實(shí)際環(huán)境中的應(yīng)用也很少，它們的性能和特性仍需要繼續(xù)探索［24］。

綜上，現(xiàn)有研究工作提出的雙容錯(cuò)陣列碼要么屬于橫式陣列碼，要么屬于縱式陣列碼，而對(duì)混合編碼方式的陣列碼的研究涉及較少。因此，亟須設(shè)計(jì)混合編碼模型，結(jié)合橫式編碼與縱式編碼的優(yōu)點(diǎn)，有效地提升雙容錯(cuò)陣列碼的性能。

2 J碼

2.1 編碼設(shè)計(jì)

J-code 采用混合校驗(yàn)規(guī)則的陣列碼，與其他陣列碼一樣，由參數(shù)p定義，要求p必須是大于2 的素?cái)?shù)。J-code 構(gòu)造一個(gè)大小為(p-1) × (p+1)的二維陣列進(jìn)行編碼，不同于RDP 將校驗(yàn)位全部放置在兩個(gè)單獨(dú)的列中，也不同于X-code將校驗(yàn)位均勻放置在各列，J-code 采用一種折中的放置方案，即數(shù)據(jù)塊分別按照斜率為-1 的反對(duì)角線和斜率為1 的對(duì)角線異或運(yùn)算，得到反對(duì)角校驗(yàn)塊和對(duì)角校驗(yàn)塊，兩種校驗(yàn)塊分別采用橫式和縱式的方式放置。全部的校驗(yàn)塊呈“J”形排列，因此將該糾刪碼模型命名為J-code。J-code 編碼后的二維陣列可表示為：

其中：D是由原始數(shù)據(jù)構(gòu)建的(p-2) × (p+1)二維陣列；Ph是由D編碼得到的1 ×p二維陣列；Pv是由D和Ph編碼計(jì)算得到的(p-1) × 1 二維陣列，包括Pv1和Pv2。編碼計(jì)算公式如下：

其中：di，j表示J-code 二維陣列C(p) 第i行j列的元素（i∈[0，p-2]，j∈[0，p]）分別表示(j+k+2) modp和(i-k) modp。本文只存儲(chǔ)了p-1 條對(duì)角線的校驗(yàn)結(jié)果，同時(shí)選取pp-2，1所在的對(duì)角線作為“缺失的對(duì)角線”（missing diagonal）［6］，不再進(jìn)行對(duì)角校驗(yàn)計(jì)算。J-code 的編碼過程如圖1 所示。

圖1 J-code的生成過程Fig.1 Process of J-code generation

2.2 譯碼過程

本文構(gòu)造一個(gè)磁盤數(shù)為p+1 的磁盤陣列，并按0～p編號(hào)，p是大于2 的素?cái)?shù)。定義各個(gè)原始數(shù)據(jù)塊和校驗(yàn)塊，將J-code 的構(gòu)造形式化。將每個(gè)由J-code 構(gòu)建的二維陣列中相同位置的塊分組成一個(gè)條帶。對(duì)于一個(gè)二維陣列的原始數(shù)據(jù)，先按反對(duì)角線方向?qū)⒚縫-2 個(gè)原始數(shù)據(jù)塊分組，每組進(jìn)行異或求和，并將得到的反對(duì)角校驗(yàn)位加入該組，將這樣的一個(gè)分組稱為一個(gè)反對(duì)角校驗(yàn)集，記為ln（n∈[0，p-1]）。如圖1（a）所示。當(dāng)p=5 時(shí)，l0由d0，0、d1，1、d2，2和p3，3組成?？啥x完整的反對(duì)角校驗(yàn)集合P={ln|n∈[0，p-1]}。磁盤k上存儲(chǔ)的數(shù)據(jù)di，k所屬反對(duì)角校驗(yàn)集為（i∈[0，p-2]，k∈[0，p-1]）。對(duì)于一個(gè)二維陣列的原始數(shù)據(jù)位和橫式排列的校驗(yàn)位，沿對(duì)角線方向按p-1 進(jìn)行分組，每組進(jìn)行異或求和，并將得到的對(duì)角校驗(yàn)位加入本組，將這樣的一個(gè)分組稱為一個(gè)對(duì)角校驗(yàn)集，記為如圖1（b）所示，當(dāng)p=5 時(shí)由d0，0、d3，2、d2，3、d1，4和p0，5組成 。同理，定義完整的對(duì)角校驗(yàn)集合由于磁盤k上存儲(chǔ)的數(shù)據(jù)di，k（i∈[0，p-2]，k∈[0，p]），當(dāng)i+k=p-1 時(shí)，di，k位于“缺失的對(duì)角線”上，不進(jìn)行對(duì)角檢驗(yàn)計(jì)算，即不屬于任何對(duì)角校驗(yàn)集。di，k所屬的對(duì)角校驗(yàn)集為：

因此，前p個(gè)磁盤中存儲(chǔ)了反對(duì)角校驗(yàn)塊，第p+1 塊磁盤，即磁盤p中存儲(chǔ)對(duì)角校驗(yàn)塊，稱為對(duì)角校驗(yàn)磁盤。

定理1 J-code 中原始數(shù)據(jù)塊所屬的反對(duì)角校驗(yàn)集與對(duì)角校驗(yàn)集，除當(dāng)前數(shù)據(jù)塊本身外沒有重疊數(shù)據(jù)塊。

證明 按照編碼過程和參數(shù)p構(gòu)造J-code，設(shè)二維陣列中存在原始數(shù)據(jù)塊dx，y（0 ≤x≤p-3，0 ≤y≤p-1）。根據(jù)編碼構(gòu)造過程可知，數(shù)據(jù)塊dx，y所屬的構(gòu)造反對(duì)角校驗(yàn)位的反對(duì)角校驗(yàn)集l和構(gòu)造對(duì)角校驗(yàn)位的對(duì)角校驗(yàn)集l′分別為：

假設(shè)反對(duì)角校驗(yàn)集l和對(duì)角校驗(yàn)集l′存在dx，y之外的重疊元素，記為di，j，若存在i∈[0，p-2]，則：

當(dāng)k=0 時(shí)，i=x，對(duì)角校驗(yàn)集和反對(duì)角校驗(yàn)集在每行有且只有一個(gè)數(shù)據(jù)塊，因此，數(shù)據(jù)塊di，j與數(shù)據(jù)塊dx，y重合，與假設(shè)矛盾；當(dāng)k≠0 時(shí)，為保證i為非負(fù)整數(shù)，則必須為p的整數(shù)倍，由于0 ≤x≤p-1

當(dāng)發(fā)生單磁盤數(shù)據(jù)丟失時(shí)，若故障磁盤位于前p個(gè)磁盤中，可跨磁盤0 到p-1 取出特定原始數(shù)據(jù)塊和校驗(yàn)塊構(gòu)建反對(duì)角校驗(yàn)集進(jìn)行數(shù)據(jù)恢復(fù)；若故障磁盤是磁盤p，使用前p個(gè)磁盤內(nèi)的數(shù)據(jù)塊和校驗(yàn)塊即可構(gòu)建對(duì)角校驗(yàn)集進(jìn)行恢復(fù)。

當(dāng)雙磁盤發(fā)生數(shù)據(jù)丟失時(shí)，丟失磁盤可分為兩類：一類是包含對(duì)角校驗(yàn)磁盤p，即前p個(gè)磁盤中的某一個(gè)磁盤與磁盤p同時(shí)發(fā)生數(shù)據(jù)丟失；另一類不包含對(duì)角校驗(yàn)磁盤p，即前p個(gè)磁盤中的兩個(gè)磁盤同時(shí)發(fā)生數(shù)據(jù)丟失。

針對(duì)第一類情況，由于反對(duì)角校驗(yàn)集內(nèi)數(shù)據(jù)的存儲(chǔ)位置不涉及對(duì)角校驗(yàn)磁盤，因此可以僅通過反對(duì)角校驗(yàn)重構(gòu)前p個(gè)磁盤中的丟失數(shù)據(jù)，由此，再根據(jù)對(duì)角校驗(yàn)集的定義便可恢復(fù)對(duì)角校驗(yàn)磁盤p中數(shù)據(jù)。

針對(duì)第二類情況，所有的數(shù)據(jù)丟失都發(fā)生在存儲(chǔ)反對(duì)角校驗(yàn)集合的磁盤。從二維陣列結(jié)構(gòu)看，對(duì)角校驗(yàn)磁盤p存儲(chǔ)的校驗(yàn)塊均屬于對(duì)角校驗(yàn)集合P′，稱對(duì)角校驗(yàn)集合P′與對(duì)角校驗(yàn)磁盤p中所有元素相交。

引理1 J-code 形式化編碼構(gòu)成的二維陣列前p個(gè)磁盤中任意兩個(gè)磁盤未參與構(gòu)造的對(duì)角校驗(yàn)集不相同。

證明假設(shè)丟失磁盤編號(hào)為d1和d2，d2=d1+j（j∈[1，p-1]），記兩個(gè)磁盤未參與構(gòu)造的對(duì)角校驗(yàn)集為l′n和，則：

假設(shè)m=n，則m=(n+ip) modp成立，i為自然數(shù)。由于j∈[1，p-1]且m，n∈[0，p-1]，可知?i∈N，均無(wú)法滿足n+j=n+ip，于 是(n+j) modp≠(n+ip) modp，即(n+j) modp≠m與假設(shè)矛盾，假設(shè)錯(cuò)誤，因此m≠n。證畢。

引理2 J-code 形式化編碼構(gòu)成的二維陣列中前p個(gè)磁盤中任意兩個(gè)磁盤分別有一個(gè)與對(duì)方存儲(chǔ)數(shù)據(jù)不相交的反對(duì)角校驗(yàn)集。

證明 根據(jù)J-code 形式化編碼構(gòu)成的二維陣列特點(diǎn)，前p列參與了反對(duì)角校驗(yàn)位的構(gòu)建，因此只提取前p列，得到一個(gè)(p-1) ×p的二維陣列。第i行依次水平循環(huán)左移i個(gè)位置，得到新的二維陣列a，p=5 時(shí)對(duì)應(yīng)的陣列如圖2 所示。

圖2 J-code的反對(duì)角校驗(yàn)集Fig.2 J-code anti-diagonal parity set

二維陣列a中每列元素屬于同一個(gè)反對(duì)角校驗(yàn)集，而位于同一條斜率為1 的對(duì)角線的元素屬于同一個(gè)磁盤。每個(gè)磁盤中存儲(chǔ)的元素所屬的反對(duì)角校驗(yàn)集構(gòu)成了一個(gè)大小為(p-1) × (p-1)的陣列。如圖3 所示，陰影標(biāo)注的數(shù)據(jù)塊存儲(chǔ)于磁盤3，陰影數(shù)據(jù)塊所屬的反對(duì)角校驗(yàn)集構(gòu)成了4 × 4的二維陣列。

圖3 反對(duì)角校驗(yàn)集與磁盤3的對(duì)應(yīng)關(guān)系Fig.3 Relationship between anti-diagonal parity set and disk3

根據(jù)結(jié)構(gòu)特點(diǎn)易知，大小為(p-1) ×p的陣列a中必然存在一個(gè)與磁盤d中元素不相關(guān)的反對(duì)角校驗(yàn)集l，同時(shí)，a中元素必然分布于其他所有非對(duì)角校驗(yàn)磁盤中。因此，a中任選兩個(gè)磁盤，則分別擁有一個(gè)與對(duì)方磁盤存儲(chǔ)數(shù)據(jù)不相交的反對(duì)角校驗(yàn)集。根據(jù)a的構(gòu)造原理，J-code 形式化編碼構(gòu)成的二維陣列同樣滿足。證畢。

假設(shè)前p個(gè)磁盤中兩個(gè)故障磁盤分別為d1和d2，所具有的與對(duì)方存儲(chǔ)數(shù)據(jù)不相交的對(duì)角校驗(yàn)集分別為lm和ln，未參與構(gòu)造的對(duì)角校驗(yàn)集分別為。根據(jù)引理1、2 知，lm和包含磁盤d1中數(shù)據(jù)塊，而不包含d2中的數(shù)據(jù)；ln和包含磁盤d2中數(shù)據(jù)塊，而不包含d1中的數(shù)據(jù)。因此，首先可以通過lm、ln嘗試恢復(fù)磁盤d1和d2中對(duì)應(yīng)丟失的塊；然后，分別探尋恢復(fù)出的數(shù)據(jù)塊所屬的反對(duì)角校驗(yàn)集和對(duì)角校驗(yàn)集；最后進(jìn)行異或求和操作，恢復(fù)出新的丟失數(shù)據(jù)。如此循環(huán)，直至恢復(fù)全部丟失符號(hào)。當(dāng)p=5 時(shí)，以磁盤1 和磁盤2 丟失為例，恢復(fù)過程如圖4 所示，括號(hào)內(nèi)數(shù)字與箭頭分別表示恢復(fù)的次序和方向。

圖4 雙磁盤故障恢復(fù)過程Fig.4 Double disk failure repair process

定理2 根據(jù)J-code 的編碼過程構(gòu)造的二維陣列可以在其任何兩個(gè)磁盤發(fā)生故障后重建。

證明 從代數(shù)的角度，可以根據(jù)式（2）、（3），構(gòu)建關(guān)于丟失磁盤內(nèi)存儲(chǔ)數(shù)據(jù)的齊次線性方程組，通過證明齊次線性方程組系數(shù)矩陣任意兩行滿足線性無(wú)關(guān)來(lái)證明該齊次線性方程組有解，繼而證出兩個(gè)磁盤內(nèi)數(shù)據(jù)可恢復(fù)。

假設(shè)通過參數(shù)p構(gòu)建的二維陣列故障磁盤編號(hào)為d1和d2，其中，d2=d1+j，d1∈[0，p-1]，j∈[1，p-1]。磁盤d1和d2存儲(chǔ)的數(shù)據(jù)分別記為 {x0，x1，…，xp-2} 和{xp-1，xp，…，x2p-3}。由反對(duì)角校驗(yàn)集的構(gòu)建過程，可以一般化構(gòu)造方程：

其中，ci表示當(dāng)前反對(duì)角校驗(yàn)集的其他元素的異或求和的結(jié)果。由引理2 可知，磁盤d1和d2分別存儲(chǔ)一個(gè)特殊的元素，該元素所屬的反對(duì)角校驗(yàn)集中沒有對(duì)方磁盤中的元素，標(biāo)記這兩個(gè)元素分別為xm和xn，其中m=p-j-1，n=p+j-2。由式（6），根據(jù)磁盤d1和d2存儲(chǔ)的數(shù)據(jù)所屬的反對(duì)角校驗(yàn)集構(gòu)建齊次線性方程組

由齊次線性方程組（7）構(gòu)建大小為p×(2p-2)的系數(shù)矩陣的一般形式，令diag[ 1，1，…，1 ]m×m。構(gòu)造的矩陣如圖5所示。

根據(jù)編碼構(gòu)造原理及齊次線性方程組可知，系數(shù)矩陣任意兩行是線性無(wú)關(guān)的，同理，根據(jù)對(duì)角校驗(yàn)集的構(gòu)建過程，同樣可以一般化構(gòu)造方程：

當(dāng)磁盤d1編號(hào)為0 時(shí)，即位于第一個(gè)磁盤位置，則磁盤d1中存儲(chǔ)的元素均參與了對(duì)角校驗(yàn)集的構(gòu)建。根據(jù)結(jié)構(gòu)特點(diǎn)，假設(shè)磁盤d1中元素xk參與的反對(duì)角校驗(yàn)集不包含磁盤d2中數(shù)據(jù)塊，則k=j-1，因此：

由式（9），根據(jù)磁盤d1和d2存儲(chǔ)的數(shù)據(jù)相關(guān)的對(duì)角校驗(yàn)集構(gòu)建齊次線性方程組：

由式（9）構(gòu)建大小為(p-1) × (2p-2)的系數(shù)矩陣的一般形式，令C=diagdiag[ 1，1，…，1]k×k。構(gòu)造的矩陣如圖6所示。

圖6 由式（9）構(gòu)造的矩陣的一般形式Fig.6 General form of matrix constructed by equation（9）

當(dāng)磁盤d1編號(hào)不為0 時(shí)，根據(jù)引理1，設(shè)磁盤d1和磁盤d2內(nèi)數(shù)據(jù)未參與構(gòu)建的對(duì)角校驗(yàn)集分別為，則磁盤d1中存在一個(gè)數(shù)據(jù)塊屬于，記為xm，磁盤d2中存在一個(gè)數(shù)據(jù)塊屬于，記為xn，根據(jù)陣列結(jié)構(gòu)和對(duì)角校驗(yàn)位生成方式，有m=j-1，n=2p-2 -j，于是：

由式（8），根據(jù)磁盤d1和d2存儲(chǔ)的數(shù)據(jù)相關(guān)的對(duì)角校驗(yàn)集構(gòu)建齊次線性方程組

由式（10）構(gòu)建大小為(p-1) × (2p-2)的系數(shù)矩陣的一般形式，令。構(gòu)造的矩陣如圖7 所示。根據(jù)編碼構(gòu)造原理及齊次線性方程組可知，無(wú)論是圖6 或圖7，其中任意兩行都是線性無(wú)關(guān)的。根據(jù)定理1 易知，對(duì)角校驗(yàn)集和反對(duì)角校驗(yàn)集構(gòu)建的次線性方程組的系數(shù)矩陣任意兩行線性無(wú)關(guān)。因此，通過拼接兩種系數(shù)矩陣可構(gòu)建非奇異矩陣來(lái)求解未知數(shù){x0，x1，…，x2p-3}的值，即磁盤丟失的數(shù)據(jù)。證畢。

圖7 由式（10）構(gòu)造的矩陣的一般形式Fig.7 General form of matrix constructed by equation（10）

3 單磁盤故障恢復(fù)方案

3.1 常規(guī)恢復(fù)方案

對(duì)于J-code，如果故障磁盤不是對(duì)角校驗(yàn)盤，常規(guī)恢復(fù)方案是使用反對(duì)角校驗(yàn)集來(lái)恢復(fù)每一個(gè)丟失數(shù)據(jù)。例如當(dāng)p=5 時(shí)，磁盤0 出現(xiàn)錯(cuò)誤，可以通過反對(duì)角校驗(yàn)集{l0，l2，l3，l4}恢 復(fù)，其 中l(wèi)0={d0，0，d1，1，d2，2，p3，3}，l2、l3和l4同理。如果故障磁盤是對(duì)角校驗(yàn)盤，恢復(fù)方案就是使用原始數(shù)據(jù)和反對(duì)角校驗(yàn)位重新編碼。

3.2 混合恢復(fù)方案

J-code 單磁盤故障的常規(guī)恢復(fù)方案只使用了反對(duì)角校驗(yàn)集，但每個(gè)數(shù)據(jù)位都受兩個(gè)不同校驗(yàn)塊的保護(hù)。本節(jié)將介紹p>3 的J-code 同時(shí)使用兩個(gè)校驗(yàn)集的混合恢復(fù)方案，把兩個(gè)校驗(yàn)集的重疊元素存儲(chǔ)在內(nèi)存中，以減少恢復(fù)過程中磁盤的讀取次數(shù)，節(jié)省恢復(fù)時(shí)間。

觀察二維陣列的前p列，由于列數(shù)比行數(shù)多1，兩個(gè)校驗(yàn)集分別沿著斜率為1 的對(duì)角線方向和斜率為-1 的反對(duì)角線方向構(gòu)造，且在每一行分別只包含一個(gè)元素。因此，任意一對(duì)反對(duì)角校驗(yàn)集與對(duì)角校驗(yàn)集至多存在一個(gè)重疊元素。

對(duì)反對(duì)角校驗(yàn)塊的生成過程分析可知，該過程僅涉及前p個(gè)磁盤，與對(duì)角校驗(yàn)磁盤無(wú)關(guān)，每個(gè)反對(duì)角校驗(yàn)集包含p-1 個(gè)元素，其中每一個(gè)元素分布在陣列中不同且連續(xù)的列，同時(shí)位于不同行中，因此，對(duì)于每一個(gè)反對(duì)角校驗(yàn)集而言，存在一個(gè)非對(duì)角校驗(yàn)盤，它存儲(chǔ)的數(shù)據(jù)塊不屬當(dāng)前校驗(yàn)集，即存在一個(gè)不相交的非對(duì)角校驗(yàn)盤。同理，對(duì)對(duì)角校驗(yàn)塊的生成過程進(jìn)行分析，每一個(gè)對(duì)角校驗(yàn)集包含p個(gè)元素，每一個(gè)元素分布在陣列中不同行和不同列，因此，對(duì)于每一個(gè)對(duì)角校驗(yàn)集而言，也存在一個(gè)列與之不相交。圖8 展示了p=5時(shí)校驗(yàn)集l0和l′0及與其不相交的列。引理3 指出了兩種校驗(yàn)集與各自不相交的列的對(duì)應(yīng)關(guān)系。

圖8 兩種校驗(yàn)集與不相交磁盤的關(guān)系Fig.8 Relationships between tow parity sets and disjoint disks

引理3 設(shè)di，j（i∈[0，p-2]，j∈[0，p]）為J-code 二維陣列中的一個(gè)元素，則：

1）有且僅有一個(gè)非對(duì)角校驗(yàn)列與其所屬的反對(duì)角校驗(yàn)集不相交，該列編號(hào)為

2）有且僅有一個(gè)非對(duì)角校驗(yàn)列與其所屬的對(duì)角校驗(yàn)集不相交，該列編號(hào)為

對(duì)于任意一個(gè)反對(duì)角校驗(yàn)集與對(duì)角校驗(yàn)集，若二者不相交的列相同，設(shè)為j。根據(jù)結(jié)構(gòu)特點(diǎn)，若兩個(gè)校驗(yàn)集分別按照各自斜率延伸，則會(huì)相交于dp-1，j或d-1，j，由于二維陣列只有p-1 行，因此兩個(gè)數(shù)據(jù)塊實(shí)際并不存在，故兩個(gè)校驗(yàn)集不相交。

由引理3，設(shè)兩個(gè)位于同一個(gè)丟失磁盤c中的元素分別為di，c和dj，c，假設(shè)di，c使用對(duì)角校驗(yàn)集恢復(fù)，dj，c使用反對(duì)角校驗(yàn)集恢復(fù)。若兩個(gè)校驗(yàn)集不相交的列相同，則

因此，i+1+c=c-j-1+kp，其中k為整數(shù)，化簡(jiǎn)得j=kp-i-2。由于i，j∈[0，p-2]，k只能取1，即j=p-i-2。由此可得出引理4。

引理4 設(shè)di，c和dj，c為J-code 二維陣列中同一個(gè)磁盤c中的兩個(gè)元素，其中i，j∈[0，p-2]，c∈[0，p-1]，當(dāng)j=p-i-2 時(shí)，di，c所屬的對(duì)角校驗(yàn)集和dj，c所屬的反對(duì)角校驗(yàn)集的交集為空。

證明 為減少磁盤的讀取次數(shù)，應(yīng)讓恢復(fù)過程中用到的校驗(yàn)集存在盡可能多的重疊數(shù)據(jù)。由引理4 易知，當(dāng)故障列中使用不同校驗(yàn)集進(jìn)行恢復(fù)的兩個(gè)元素的行編號(hào)之和不等于p-2 時(shí)，使用的兩個(gè)校驗(yàn)集之間沒有重疊數(shù)據(jù)。設(shè)丟失列中t個(gè)元素使用對(duì)角校驗(yàn)集恢復(fù)，剩下的p-1 -t個(gè)元素使用反對(duì)角校驗(yàn)集恢復(fù)，其中有k對(duì)校驗(yàn)集不相交，則重疊元素的個(gè)數(shù)為

4 實(shí)驗(yàn)與結(jié)果分析

4.1 存儲(chǔ)利用率和容錯(cuò)率

存儲(chǔ)利用率是指存儲(chǔ)的原始數(shù)據(jù)量與全部編碼信息量的比值。J-code 編碼構(gòu)建的二維陣列中，(p-2) ×p的陣列用于存儲(chǔ)源數(shù)據(jù)，剩余空間存儲(chǔ)冗余數(shù)據(jù)，存儲(chǔ)利用率為，可容忍任意兩列數(shù)據(jù)丟失。而同樣能容忍兩列數(shù)據(jù)丟失的EVENODD、RDP、X-code、N-code 和EaR的存儲(chǔ)利用率對(duì)比如表1、圖9 所示，其中RDP 與N-code 在同一參數(shù)p下具有相同的存儲(chǔ)利用率。根據(jù)理論分析對(duì)比，雖然J-code 在存儲(chǔ)利用率方面僅優(yōu)于X-code，但相較于下文中J-code 降低的編譯碼復(fù)雜度和單磁盤故障修復(fù)I/O，J-code 所增加的存儲(chǔ)開銷仍在可接受范圍內(nèi)。

表1 不同糾刪碼的存儲(chǔ)利用率計(jì)算公式Tab.1 Formulas for calculating storage utilization of different erasure codes

圖9 不同糾刪碼的存儲(chǔ)利用率對(duì)比Fig.9 Comparison of storage utilization of different erasure codes

4.2 編譯碼復(fù)雜度

編譯碼復(fù)雜度的高低是糾刪碼在編譯碼階段的實(shí)用性和效率的體現(xiàn)，因此，編譯碼復(fù)雜度也是評(píng)價(jià)糾刪碼性能的重要指標(biāo)之一。J-code 作為陣列碼的一種，基于XOR 運(yùn)算的編譯碼計(jì)算方式使其計(jì)算復(fù)雜度遠(yuǎn)低于基于Galois 域GF(2w)運(yùn)算的糾刪碼，如RS 類糾刪碼與再生碼。

下面以每種陣列碼的數(shù)據(jù)位構(gòu)造校驗(yàn)位所需的異或操作平均次數(shù)作為衡量編碼復(fù)雜度的指標(biāo)，對(duì)EVENODD、RDP、X-code、N-code、EaR 和J-code 進(jìn)行對(duì)比。根據(jù)J-code 的編碼過程可知，J-code 的每個(gè)信息位都參與了反對(duì)角校驗(yàn)位的構(gòu)建，斜率為1 的部分對(duì)角線上的信息位與反對(duì)角校驗(yàn)位參與了對(duì)角校驗(yàn)位的構(gòu)建，因此一個(gè)J-code 碼字的編碼過程總異或次數(shù)為 2(p2-3p+1)，編碼復(fù)雜度為。EVENODD、RDP、X-code、N-code 和EaR 的編碼復(fù)雜度對(duì)比如表2、圖10（a）所示。其中，EVENODD 的原始構(gòu)建方式要求p+2 個(gè)磁盤，除了X-code 外的其他糾刪碼的構(gòu)建都要求使用p+1 個(gè)磁盤，假設(shè)這些糾刪碼都應(yīng)用于具有p+1 個(gè)磁盤的存儲(chǔ)系統(tǒng)中，為保持統(tǒng)一，令EVENODD 邏輯上的最后一個(gè)數(shù)據(jù)磁盤只存儲(chǔ)零。而RDP 與N-code 在同一參數(shù)p下具有相同的編碼復(fù)雜度。

表2 不同糾刪碼的編碼和譯碼復(fù)雜度計(jì)算公式Tab.2 Calculation formulas of encoding and decoding complexity of different erasure codes

圖10 編碼復(fù)雜度和譯碼復(fù)雜度對(duì)比Fig.10 Comparison of encoding complexity and decoding complexity

類似地，以每種陣列碼恢復(fù)兩列數(shù)據(jù)位過程中異或計(jì)算次數(shù)與原始數(shù)據(jù)塊之比作為衡量譯碼復(fù)雜度的指標(biāo)。在此，假設(shè)數(shù)據(jù)丟失都發(fā)生在存儲(chǔ)原始信息的列中。由第二章Jcode 的譯碼過程可知，J-code 恢復(fù)兩列丟失數(shù)據(jù)XOR 操作次數(shù) 為2p2-7p+4。因此，J-code 的譯碼復(fù)雜度為。EVENODD、RDP、X-code、N-code 和EaR 的譯碼復(fù)雜度對(duì)比如表2、圖10（b）所示，其中，RDP 與N-code 在相同參數(shù)p下具有相同的譯碼復(fù)雜度。

如圖10 所示，當(dāng)p=3 時(shí)，J-code 具有最低的編碼復(fù)雜度；隨著p的增加，J-code 的編碼復(fù)雜度僅高于X-code 并逐漸趨于一致，而J-code 的譯碼復(fù)雜度始終保持最低，說明J-code具有優(yōu)秀的編譯碼性能，在理論上能提高存儲(chǔ)系統(tǒng)的編譯碼速度。

4.3 單磁盤故障修復(fù)I/O

單磁盤故障修復(fù)I/O 指修復(fù)任意一個(gè)故障磁盤時(shí)對(duì)其他磁盤的讀取次數(shù)。本節(jié)僅考慮存儲(chǔ)原始數(shù)據(jù)的磁盤丟失的情況。第3 章詳細(xì)闡述了J-code 的混合恢復(fù)方案，在此不再贅述。EVENODD、RDP、X-code、N-code 和EaR 的單磁盤修復(fù)硬盤讀取次數(shù)如表3、圖11 所示，其中EVENODD、RDP、Xcode 同樣采用單磁盤故障最優(yōu)恢復(fù)方案［25］。與4.2 節(jié)一樣，EVENODD 邏輯上的最后一個(gè)數(shù)據(jù)磁盤只存儲(chǔ)零。由圖11可知，隨著編碼參數(shù)p的增加，J-code 始終具有最少的磁盤讀取次數(shù)，說明了在單磁盤故障修復(fù)過程中，J-code 占用最少的I/O 資源。

表3 不同糾刪碼的單磁盤故障修復(fù)硬盤讀取次數(shù)計(jì)算公式Tab.3 Calculation formulas of read times for single disk failure repair of different erasure codes

圖11 不同糾刪碼的單磁盤故障修復(fù)磁盤讀取次數(shù)對(duì)比Fig.11 Comparison of read times among different erasure codes for single disk failure repair

4.4 真實(shí)應(yīng)用場(chǎng)景下的實(shí)驗(yàn)對(duì)比

為評(píng)估J-code 在真實(shí)應(yīng)用場(chǎng)景下的性能，在編碼用時(shí)、單磁盤故障恢復(fù)時(shí)間和雙磁盤故障恢復(fù)時(shí)間方面進(jìn)行了實(shí)驗(yàn)對(duì)比。該實(shí)驗(yàn)橫向?qū)Ρ鹊募m刪碼分別是J-code、EVENODD、RDP、X-code、N-code 和EaR。編碼參數(shù)p的取值為3、5 和7。與上文一致，EVENODD 邏輯上的最后一個(gè)數(shù)據(jù)磁盤只存儲(chǔ)零。用于測(cè)試的文件的大小為5 MB，為實(shí)現(xiàn)各個(gè)陣列碼條帶數(shù)統(tǒng)一，設(shè)置當(dāng)編碼參數(shù)p=3 時(shí)，數(shù)據(jù)塊分塊大小設(shè)為600 KB；當(dāng)p=5 時(shí)，數(shù)據(jù)塊分塊大小設(shè)為100 KB；當(dāng)p=7 時(shí)，數(shù)據(jù)塊分塊大小設(shè)為50 KB。實(shí)驗(yàn)的軟件運(yùn)行環(huán)境是CentOS7 64 位操作系統(tǒng)，硬件環(huán)境為CPU Intel Core i5-10400、內(nèi)存8 GB、機(jī)械硬盤1 TB*8。

4.4.1 編碼用時(shí)實(shí)驗(yàn)

從表4 編碼過程的用時(shí)可看出：由于J-code 在生成反對(duì)角校驗(yàn)位過程中，XOR 計(jì)算次數(shù)少于EVENODD、RDP、Ncode，因此編碼速度得以提升。由于EaR 每個(gè)條帶多存儲(chǔ)一個(gè)校驗(yàn)塊，導(dǎo)致編碼時(shí)間比J-code 長(zhǎng)。而X-code 的特殊構(gòu)造方式使它具有最低的編碼復(fù)雜度，從而具有最快編碼速度。相較于EVENODD、RDP、N-code 和EaR，J-code 的編碼時(shí)間分別減少了6.96%～28.70%、0.30%～20.20%、0.60%～23.60%、7.00%～22.80%。隨著p的擴(kuò)大，編碼時(shí)間趨于穩(wěn)定，各個(gè)陣列碼的用時(shí)相差不大。

表4 不同編碼參數(shù)p下的用時(shí)對(duì)比Tab.4 Comparison of time consumption under different encoding parameter p

4.4.2 單磁盤故障修復(fù)用時(shí)實(shí)驗(yàn)

從表4 單磁盤故障的平均修復(fù)用時(shí)可看出：當(dāng)p=3 時(shí)，在單個(gè)條帶內(nèi)，相較于其他陣列碼，J-code 采用常規(guī)恢復(fù)方案時(shí)具有最小的磁盤讀取次數(shù)，因此修復(fù)速度最快。而Xcode 由于需寫入數(shù)據(jù)塊最多，因此耗時(shí)最長(zhǎng)。當(dāng)p>3 時(shí)，Jcode 采用混合恢復(fù)方案仍能實(shí)現(xiàn)最少的磁盤讀取次數(shù)。綜合三種編碼參數(shù)，在單磁盤故障修復(fù)過程中，J-code 相較于EVENODD、RDP、X-code、N-code 和EaR，故障修復(fù)時(shí)間分別減少了7.20%～17.46%、5.40%～14.68%、10.61%～31.62%、6.81%～16.22%、2.23%～10.58%。

4.4.3 雙磁盤故障修復(fù)用時(shí)實(shí)驗(yàn)

從表4 雙磁盤故障的平均修復(fù)用時(shí)可看出：在雙磁盤損壞場(chǎng)景下，J-code 的修復(fù)過程需要讀取的數(shù)據(jù)塊個(gè)數(shù)比EVENODD、RDP、N-code 和EaR 少，同時(shí)需要寫入的數(shù)據(jù)塊個(gè)數(shù)比X-code 少，因此J-code 的修復(fù)時(shí)間最短。實(shí)驗(yàn)結(jié)果表明，相較于EVENODD、RDP、X-code、N-code 和EaR，J-code 的譯碼時(shí)間分別減少了9.43%～29.10%、6.05%～16.23%、15.58%～36.00%、5.88%～15.67%、0.39%～12.41%。

5 結(jié)語(yǔ)

在磁盤陣列中，由磁盤故障導(dǎo)致的數(shù)據(jù)丟失對(duì)企業(yè)及用戶造成巨大損失。目前已有多種陣列碼被用于實(shí)現(xiàn)RAID-6的容錯(cuò)機(jī)制，但編譯碼復(fù)雜度較高，單盤、雙盤恢復(fù)速度較慢。為此，對(duì)橫式陣列碼與縱式陣列碼進(jìn)行分析，提出了一種結(jié)合二者編碼特點(diǎn)的混合陣列碼J-code，闡述了編譯碼過程以及單磁盤快速修復(fù)方案，并證明其正確性。通過理論分析，J-code 在滿足RAID-6 雙容錯(cuò)能力的同時(shí)，具有較低的編譯碼復(fù)雜度和單磁盤故障修復(fù)I/O。實(shí)驗(yàn)結(jié)果表明，相較于EVENODD、RDP、N-code 和EaR，J-code 能夠減少編譯碼時(shí)間和單磁盤故障修復(fù)時(shí)間，而在存儲(chǔ)利用率方面稍有不足；相較于X-code，J-code 優(yōu)化了存儲(chǔ)開銷，節(jié)省了譯碼時(shí)間和單磁盤故障修復(fù)時(shí)間，而在編碼時(shí)間方面稍有不足。此外，J-code的校驗(yàn)生成規(guī)則也在一定程度上緩解了數(shù)據(jù)修復(fù)過程中磁盤I/O 失衡的問題，因此J-code 適合用于磁盤陣列的底層編碼實(shí)現(xiàn)，具有應(yīng)用前景。