低編譯復雜度的雙容錯陣列碼

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

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

0 引言

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

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

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

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

1 相關工作

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

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

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

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

2 J碼

2.1 編碼設計

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

其中：D是由原始數據構建的(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 條對角線的校驗結果，同時選取pp-2，1所在的對角線作為“缺失的對角線”（missing diagonal）［6］，不再進行對角校驗計算。J-code 的編碼過程如圖1 所示。

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

2.2 譯碼過程

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

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

定理1 J-code 中原始數據塊所屬的反對角校驗集與對角校驗集，除當前數據塊本身外沒有重疊數據塊。

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

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

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

當發生單磁盤數據丟失時，若故障磁盤位于前p個磁盤中，可跨磁盤0 到p-1 取出特定原始數據塊和校驗塊構建反對角校驗集進行數據恢復；若故障磁盤是磁盤p，使用前p個磁盤內的數據塊和校驗塊即可構建對角校驗集進行恢復。

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

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

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

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

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

假設m=n，則m=(n+ip) modp成立，i為自然數。由于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與假設矛盾，假設錯誤，因此m≠n。證畢。

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

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

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

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

圖3 反對角校驗集與磁盤3的對應關系Fig.3 Relationship between anti-diagonal parity set and disk3

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

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

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

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

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

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

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

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

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

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

由式（9），根據磁盤d1和d2存儲的數據相關的對角校驗集構建齊次線性方程組：

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

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

當磁盤d1編號不為0 時，根據引理1，設磁盤d1和磁盤d2內數據未參與構建的對角校驗集分別為，則磁盤d1中存在一個數據塊屬于，記為xm，磁盤d2中存在一個數據塊屬于，記為xn，根據陣列結構和對角校驗位生成方式，有m=j-1，n=2p-2 -j，于是：

由式（8），根據磁盤d1和d2存儲的數據相關的對角校驗集構建齊次線性方程組

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

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

3 單磁盤故障恢復方案

3.1 常規恢復方案

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

3.2 混合恢復方案

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

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

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

圖8 兩種校驗集與不相交磁盤的關系Fig.8 Relationships between tow parity sets and disjoint disks

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

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

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

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

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

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

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

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

4 實驗與結果分析

4.1 存儲利用率和容錯率

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

表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 編譯碼復雜度

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

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

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

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

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

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

4.3 單磁盤故障修復I/O

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

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

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

4.4 真實應用場景下的實驗對比

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

4.4.1 編碼用時實驗

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

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

4.4.2 單磁盤故障修復用時實驗

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

4.4.3 雙磁盤故障修復用時實驗

從表4 雙磁盤故障的平均修復用時可看出：在雙磁盤損壞場景下，J-code 的修復過程需要讀取的數據塊個數比EVENODD、RDP、N-code 和EaR 少，同時需要寫入的數據塊個數比X-code 少，因此J-code 的修復時間最短。實驗結果表明，相較于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 結語

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