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

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

0 引言

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

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

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

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

1 相關(guān)工作

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

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

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

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

2 J碼

2.1 編碼設(shè)計

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

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

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

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

2.2 譯碼過程

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

因此，前p個磁盤中存儲了反對角校驗塊，第p+1 塊磁盤，即磁盤p中存儲對角校驗塊，稱為對角校驗磁盤。

定理1 J-code 中原始數(shù)據(jù)塊所屬的反對角校驗集與對角校驗集，除當(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)造反對角校驗位的反對角校驗集l和構(gòu)造對角校驗位的對角校驗集l′分別為：

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

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

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

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

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

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

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

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

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

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

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

圖2 J-code的反對角校驗集Fig.2 J-code anti-diagonal parity set

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

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

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

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

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

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

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

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

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

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

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

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

由式（9），根據(jù)磁盤d1和d2存儲的數(shù)據(jù)相關(guā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編號不為0 時，根據(jù)引理1，設(shè)磁盤d1和磁盤d2內(nèi)數(shù)據(jù)未參與構(gòu)建的對角校驗集分別為，則磁盤d1中存在一個數(shù)據(jù)塊屬于，記為xm，磁盤d2中存在一個數(shù)據(jù)塊屬于，記為xn，根據(jù)陣列結(jié)構(gòu)和對角校驗位生成方式，有m=j-1，n=2p-2 -j，于是：

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

由式（10）構(gòu)建大小為(p-1) × (2p-2)的系數(shù)矩陣的一般形式，令。構(gòu)造的矩陣如圖7 所示。根據(jù)編碼構(gòu)造原理及齊次線性方程組可知，無論是圖6 或圖7，其中任意兩行都是線性無關(guān)的。根據(jù)定理1 易知，對角校驗集和反對角校驗集構(gòu)建的次線性方程組的系數(shù)矩陣任意兩行線性無關(guān)。因此，通過拼接兩種系數(shù)矩陣可構(gòu)建非奇異矩陣來求解未知數(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ù)方案

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

3.2 混合恢復(fù)方案

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

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

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

圖8 兩種校驗集與不相交磁盤的關(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 二維陣列中的一個元素，則：

1）有且僅有一個非對角校驗列與其所屬的反對角校驗集不相交，該列編號為

2）有且僅有一個非對角校驗列與其所屬的對角校驗集不相交，該列編號為

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

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

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

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

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

4 實驗與結(jié)果分析

4.1 存儲利用率和容錯率

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

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

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

4.2 編譯碼復(fù)雜度

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

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

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

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

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

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

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

單磁盤故障修復(fù)I/O 指修復(fù)任意一個故障磁盤時對其他磁盤的讀取次數(shù)。本節(jié)僅考慮存儲原始數(shù)據(jù)的磁盤丟失的情況。第3 章詳細闡述了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 邏輯上的最后一個數(shù)據(jù)磁盤只存儲零。由圖11可知，隨著編碼參數(shù)p的增加，J-code 始終具有最少的磁盤讀取次數(shù)，說明了在單磁盤故障修復(fù)過程中，J-code 占用最少的I/O 資源。

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

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

4.4 真實應(yīng)用場景下的實驗對比

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

4.4.1 編碼用時實驗

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

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

4.4.2 單磁盤故障修復(fù)用時實驗

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

4.4.3 雙磁盤故障修復(fù)用時實驗

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

5 結(jié)語

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