低修復成本的局部混合修復陣列碼模型

摘 要：具有局部修復性質的水平陣列碼將編碼矩陣進行分區管理，降低磁盤發生故障時需要讀取的數據總量并提升修復效率，但仍存在修復時讀寫負載集中于單個磁盤的問題。針對局部水平陣列碼磁盤讀寫不均和單雙盤修復效率有待提升的問題，結合水平陣列碼和垂直陣列碼的特點，對其進行局部冗余改造，提出一種具有局部修復性質的混合式陣列碼修復模型——LHRC。LHRC根據垂直陣列碼的思想將局部水平陣列碼的對角校驗列遷移至矩陣的中間行，加深數據塊與校驗塊之間的聯系，分散讀寫負載至其他磁盤并減少參與修復的數據總量。通過理論分析，LHRC具有良好的編譯碼復雜度，改善了磁盤修復時讀寫不均勻的問題并減少單雙盤故障時需要讀取的數據總量，提升了三盤故障的修復成功率。實驗結果表明LHRC與RDP、LRRDP、DRDP相比，LHRC可將單盤故障修復時間節省3.92%～29.91%、雙盤故障修復時間節省7.79%～30.64%。

關鍵詞：陣列碼；存儲系統；局部修復；讀取開銷

中圖分類號：TP333.3"" 文獻標志碼：A

文章編號：1001-3695（2025）01-030-0222-09

doi：10.19734/j.issn.1001-3695.2024.06.0188

Local hybrid repair array code model with low repair cost

Abstract：Horizontal array codes with local repair partition the coding matrix to reduce the total amount of data to be read when a disk fails and improve repair efficiency，but there is still the problem that the read and write loads are concentrated on a single disk during repair.To address the problems of uneven disk read/write and single/dual disk repair efficiency，this paper combined the features of horizontal and vertical array codes and local redundancy to propose a hybrid array code repair model with local repair propertie—LHRC （local hybrid repair code）.Based on the idea of vertical array code，LHRC relocated the diagonal checksum columns of local horizontal array code to the middle rows of the matrix，which deepened the connection between data blocks and checksum blocks，dispersed the read/write loads to other disks，and reduced the total amount of data involved in repair.Through theoretical analysis，LHRC has good compilation code complexity，improves the problem of uneven reading and writing during disk repair and reduces the total amount of data to be read during single and double disk failure，and improves the success rate of repairing three-disk failure.The experimental results show that compared with RDP，LRRDP and DRDP，LHRC can save 3.92% to 29.91% of single-disk failure repair time and 7.79% to 30.64% of double-disk failure repair time.

Key words：array code；storage system；local repair；read overhead load0 引言

隨著大數據和計算機存儲技術的快速發展，數據量呈爆炸式增長，存儲設備的數量和存儲容量不斷增加，對數據中心的存儲效率、安全性提出新的挑戰。數據中心不僅要保證數據的高效存儲，還要對數據的安全性提供保障。磁盤故障作為影響數據安全的主要因素，發生在磁盤工作的各個時間段，為了保障數據的可靠性，通常采用容錯技術來恢復故障磁盤。目前的容錯技術主要分為副本技術和糾刪碼技術［1］兩類。副本技術是指將元素磁盤的數據進行備份，選取一個或多個磁盤來存儲其副本，當小于等于副本數量的磁盤發生故障時，都可以通過備份的副本磁盤來恢復原始磁盤的數據。糾刪碼技術則是將多個原始數據磁盤進行編碼，將編碼后的數據存儲在新的磁盤或原始磁盤中。當磁盤發生故障時，該技術通過讀取剩余磁盤的原始數據以及編碼數據進行特定的運算來恢復丟失數據。糾刪碼技術解決了副本技術冗余過多的問題［2］，將少量的編碼數據存儲在原始磁盤或新磁盤中，為數據提供一定的安全性和可靠性。相比副本技術產生大量冗余的數據，通過糾刪碼技術的特定算法來幫助數據安全存儲，更適用于數據快速增長的發展現狀。

糾刪碼主要分為RS碼（Reed-Solomon）［3］和陣列碼［4］兩個大類。RS碼基于伽羅華域運算，可通過增加矩陣大小來決定容錯范圍，具有容錯能力強的特點，但RS碼的編解碼過程需要進行大量的有限域計算，修復過程不僅涉及殘余矩陣的求逆運算，同時涉及復雜的有限域運算。而陣列碼的編解碼過程基于異或運算，運算速度快，但容錯能力弱于RS碼。在目前存儲系統發生的故障情況中，單個磁盤發生故障的比例達到99.75%［5］。文獻［6］采用預測恢復的方式，通過RS進行編碼并提前遷移和恢復數據，可以提高數據的可靠性，但RS碼計算速度慢的缺點給數據中心本就緊缺的計算資源帶來更大的壓力。選取陣列碼作為容錯手段，更適用于數據量大、可用資源緊缺的大型存儲系統。

根據編碼生成的校驗數據的存放位置，陣列碼又分為橫式陣列碼和縱式陣列碼［7］，橫式陣列碼的校驗數據通常存放于單個磁盤中，在矩陣中以列的方式存放，縱式陣列碼則以行作為存放校驗數據的位置，以每個磁盤的特定位置來存放校驗數據。

目前，研究人員對橫式陣列碼的研究已較為成熟，EVENODD［8］作為最早提出的雙容錯橫式陣列碼，因計算復雜度低、編譯速度快的特點受到研究者廣泛關注。STAR［9］對EVENODD進行拓展，利用反對角線思想添加反對角校驗列，構造出一種三容錯的橫式陣列碼。RDP［10］ 的提出減少了EVENODD中校驗因子參與的計算時間，進一步提高了運算效率。X-RDP［11］的思想與STAR相似，在RDP雙容錯的基礎上添加反對角校驗鏈，利用幾何對稱關系增加RDP容錯能力，簡化譯碼過程。近年來提出的橫式陣列碼有Ear［12］、Thou［13］等。Ear的構造基于RDP，通過為每個條帶添加額外的對角校驗元素和設計新的校驗生成規則，減少了與每個數據元素相關聯的校驗元素的數量，使得Ear具有較低的編譯碼復雜度；Thou能容忍3個磁盤發生故障，并且其陣列構造使得Thou具有較低的存儲開銷和編譯碼復雜度。

常用的縱式陣列碼有X-code［14］、P-code［15］和WEAVER［16］等，X-code作為最經典的縱式陣列碼，其思想是利用對角校驗和反對角校驗來保護元素數據，其編譯碼效率高、故障恢復速度快。P-code也稱為分區碼，利用一行缺失磁盤編號的校驗塊對不同區域的數據塊進行保護，在所有能糾正雙盤故障的糾刪碼中具有最佳的存儲效率。WEAVER利用對稱特性提供較高容錯能力，適用于任何具有高容錯性和性能要求的存儲系統。相對于橫式陣列碼，縱式陣列碼的數據存放于各個磁盤中，編碼數據發生更新時，各磁盤的讀寫速率相近，具有良好的負載均衡特性，但縱式陣列碼的存儲效率低于相同容錯能力的橫式陣列碼，磁盤間密切相關的聯系限制了縱式陣列碼的擴展能力［17］，所以相對橫式陣列碼，縱式陣列碼的磁盤擴容方案較少。

混合式陣列碼結合了橫式陣列碼和縱式陣列碼的特點，以矩陣中行和列的形式分別存儲校驗信息，利用不同校驗位重疊的特點降低故障恢復開銷。目前混合式陣列碼的方案較少，得到相關研究人員的廣泛關注。N-code［18］作為混合式陣列碼的一種，其校驗塊和數據塊分散在各個磁盤，行校驗塊按階梯狀排列，對角校驗集中于第一個和最后一個磁盤，有效優化了降級讀和負載均衡方面的性能。J-code［19］的提出進一步降低了陣列碼的編譯碼效率，通過縱式編碼思想利用反對角校驗行對所有數據塊進行編碼，再通過橫式編碼思想將編碼后的二維矩陣再編碼形成對角校驗列，J-code降低了編譯碼效率的同時提升了單盤恢復效率。

單磁盤故障作為當前存儲系統的研究重點［20］，目前主要以降低讀取開銷來減少磁盤故障修復時間。文獻［21］對RDP提出混合修復算法RDOR，最大化利用水平校驗集與對角校驗集中的重疊部分，減少25%的磁盤讀取總量。添加局部校驗塊作為常用的加速修復手段，將覆蓋全局的水平校驗鏈進行切分，利用切分后的局部校驗鏈保護切分后所屬區域的數據塊，該方法縮短了原始碼鏈的長度，減少了修復單個磁盤需要讀取的其他數據塊［22］個數。LRRDP［23］作為RDP的擴展編碼，采用局部校驗的方式，在RDP陣列結構的基礎上添加一個新冗余磁盤來存儲矩陣部分的校驗信息，在單盤故障下相比RDP減少最多50%的數據讀取開銷，但是對于雙盤故障，LRRDP的修復開銷與RDP一致，沒有提出雙盤修復的優化方案。DRDP［24］進一步對LRRDP進行改進，將局部水平校驗列遷移至陣列中間位置，減少一列數據參加計算的同時，通過局部校驗縮短校驗鏈的長度，有效降低了單盤修復的讀取開銷，同時根據磁盤故障發生的位置，以水平校驗和對角校驗混合修復的方式，減少了雙盤故障的平均數據讀取量。

為了結合混合式陣列碼與局部修復碼的特點，本文提出一種基于異或運算的混合式局部修復陣列碼——LHRC碼（local hybrid repair code）。LHRC受DRDP的啟發，主要思想是利用局部水平校驗和對角校驗的重疊部分來減少單盤故障和雙盤故障恢復所需的數據塊個數。LHRC的校驗元素由左右兩列水平局部校驗列和矩陣行中間位置斜率為“1”的一行傾斜校驗行組成，LHRC碼結合了橫式陣列碼和縱式陣列碼的優點，在單磁盤故障和多磁盤故障時均能一定程度上減少磁盤的讀取，降低磁盤發生故障時對其他磁盤的讀取總量，并且在丟失磁盤數達到3的情況下，也能較大概率地修復所有故障磁盤，保證存儲系統的可靠性和安全性。

1 陣列碼

1.1 陣列碼概念

陣列碼作為存儲系統中的編碼之一，其編碼過程僅基于異或運算，其運算速度快，且磁盤發生故障時參與恢復的數據塊數量相對RS碼較少。陣列碼通常用于磁盤陣列或存儲服務器上，提供硬件級別的數據保護和性能優化。

為便于理解，基于陣列碼基本性質［25］，本文給出如下一些常用的基本概念的說明和定義：

a）數據塊。存儲真實用戶原始數據的一塊數據串。

b）校驗塊。利用糾刪碼算法，通過多塊數據塊計算得到的冗余信息的一塊數據串。

c）條帶。同一糾刪碼算法計算所使用的最小信息集合，通常包含多個磁盤的同一條塊，以條塊中的多個數據塊進行計算生成校驗塊保存到對應磁盤位置。

d）條塊。處于同一存儲設備上屬于同一條帶的數據集合，條塊的大小由條塊所包含的數據塊或校驗塊個數決定。

e）橫式陣列碼。冗余獨立于數據條塊，并單獨存儲在冗余條塊中的編碼方式。

f）縱式陣列碼。冗余數據和原始數據按照一定比例均勻存放于每個條塊的編碼方式。

g）混合陣列碼。結合橫式陣列碼與縱式陣列碼的數據存儲方式，部分條塊混合存儲數據塊和校驗塊，部分條塊集中存儲校驗塊。

1.2 橫式陣列碼

橫式陣列碼具有校驗塊集中分布于單獨校驗磁盤的特點，通常能容忍校驗磁盤個數的磁盤發生故障，從而保證數據的完整性和可靠性。冗余數據通常在末尾的磁盤中單獨存放，使得磁盤陣列需要增加容量時能以最小的代價遷移盡可能少的數據，增加了陣列的可拓展性。橫式陣列碼的通用構造如圖1所示。

RDP作為經典的橫式陣列碼，其條帶由一個（p-1）×（p+1）的二維陣列構成。p=5的RDP矩陣構造如圖2所示，其中，disk4存放水平校驗位，每個校驗元素由其所在行中disk0～disk3的數據元素異或形成，disk5存放對角校驗位，其水平校驗和對角校驗的編碼公式分別如式（1）（2）所示。

其中：di，j代表二維陣列中第i行第j列的元素，i∈［0，p-2］，j∈［0，p］，〈i-j〉p表示（i-j）mod p。

1.3 縱式陣列碼

如圖3所示，縱式陣列碼的數據塊和校驗塊通常平均分布于磁盤陣列中的每個磁盤中，具有良好的讀寫效率及編譯碼復雜度。當磁盤發生故障時，多數磁盤共同參與修復，相比于橫式陣列碼集中于部分磁盤的修復方式，可以提高磁盤故障的修復效率［26］。但縱式陣列碼數據塊和校驗塊間緊密聯系的特點，限制了磁盤的擴展能力。

2 LHRC

為了降低單雙盤故障恢復的開銷，本文提出一種水平校驗列與垂直校驗行混合修復的混合陣列碼編碼模型。該模型的水平校驗列又切分為左右兩個局部水平校驗列，故命名為LHRC（local hybrid repair code）。

作為橫式陣列碼與縱式陣列碼結合的混合陣列碼，LHRC結合了橫式陣列碼和縱式陣列碼的特點，其主要設計思路是：保留局部修復碼（LRRDP、DRDP）低修復成本的優點，以水平局部校驗的方式存放兩列水平校驗列，再以縱式編碼的思想將矩陣的中部偏下一行作為對角校驗行，這樣的編碼方式能結合縱式陣列碼的優點，提高數據塊和校驗塊之間的關聯性，提升單雙盤恢復時的并行修復效率。

2.1 編碼

左側局部水平校驗列和右側局部水平校驗列的編碼公式如式（3）（4）所示。

對角校驗行的編碼公式如式（5）所示。

驗集中，通過單個局部水平校驗與對角校驗混合修復的方式，減少數據塊的讀取，提升修復效率。

當p=5且故障磁盤位于disk1時，對角校驗集與左側水平校驗集數據塊重合數為3，參與修復的右側區域中數據塊數量為1，采用對角校驗修復數據塊q2，1后，其余丟失數據塊采用左側局部水平校驗進行修復，參與修復的總數據塊數為7，如圖7所示。

2.2 譯碼

3 單盤修復

LHRC在單盤故障主要分為故障磁盤位于局部水平校驗列或位于非局部水平校驗列兩種情況。

定理3 單盤故障時，采用橫式和縱式混合編碼的LHRC相比橫式局部修復陣列碼（LRRDP、DRDP等）修復效率更優。

證明 LRRDP、DRDP等橫式局部修復碼改善了RDP在單盤故障時需要讀取的數據塊數量較多的問題，但并未改善對單個磁盤數據塊全部讀取的問題，當每個磁盤的讀取速度相近時，單個磁盤的最大數據量成為影響單盤修復的瓶頸。DRDP在單盤故障時（p=5）的修復過程如圖9所示，當磁盤disk2發生故障時，需要從disk0和disk2分別讀取4個數據塊，LRRDP單盤故障時與DRDP相似，需要讀取單個磁盤全部數據進行修復。而如圖8所示，LHRC在disk2發生故障時，從disk0、disk1分別讀取3個數據塊，從disk3、disk4分別讀取1個數據塊，這樣混合讀取的方式能分擔單個磁盤I/O壓力過大的情況，并且在磁盤并行讀寫時發揮更好的讀寫效率，證畢。

4 雙盤修復

雙盤修復時，由于對角校驗行只能通過相應對角校驗元素修復，所以修復時優先修復故障磁盤對應的對角校驗元素（同單盤故障），若該校驗鏈包含另一故障磁盤數據塊，則以該數據塊為起點，反向搜尋恢復起點，直到全部故障數據塊完成修復。

雙盤修復分為同側磁盤丟失和異側磁盤丟失兩種情況，設丟失磁盤編號分別為u、v，0≤ult;v≤p，其中同側丟失與兩側丟失的情況如下。

4.1 同側雙盤故障

定理4 雙盤故障中，丟失磁盤位于同一側的最小修復開銷為p2-3p+1。

其修復開銷為（p-1）×（p-2）-1=p2-3p+1。

同側雙盤故障（故障磁盤不相鄰）的修復流程如圖10所示，故障磁盤位于disk0和disk2時，首先以對角校驗集進行反向搜尋，位于第2行的對角校驗塊q2，2由d3，1、d1，3、d0，4通過異或運算恢復，而對角校驗塊q2，0在恢復時需要d1，1、p3，5和p0，2，p0，2可由d0，0、d0，1通過異或運算恢復，而d0，0可由d3，3、q2，4、p1，5異或運算恢復。反向搜尋結束后，其余的丟失數據塊根據最小代價進行恢復，修復開銷為11，具體的恢復流程如下：

a）通過對角校驗集：d3，1、d1，3、d0，4異或運算恢復q2，2，同時通過對角校驗集：d3，3、q2，4、p1，5異或運算恢復d0，0；

b）通過左側局部水平校驗集：d0，0、d0，1異或運算恢復p0，2；

c）通過對角校驗集：p0，2、d1，1、p3，5異或運算恢復q2，0；

d）通過對角校驗集：d3，4、q2，5、d0，1異或運算恢復d1，0，其中d3，4無須從磁盤讀取，可由已有數據塊d3，3，和d3，5異或獲取；

e）通過左側水平校驗集：d1，0、d1，1異或運算恢復p1，2；

f）通過對角校驗集p0，5、d1，4、q2，3異或運算恢復p3，2，其中d1，4和q2，3無須從磁盤讀取，可由右側已有數據塊通過右側局部水平校驗集獲?。?/p>

g）通過左側局部水平校驗集：d3，1、p3，2異或運算恢復d3，0。

4.2 異側雙盤故障

圖11、12為異側故障修復開銷的最小情況，此時故障磁盤間距離為1或p，根據定理1可知，圖（a）（b）中的陣列具有相同的性質，其中參與修復的局部水平校驗集個數為4，參與修復的對角校驗集個數為4，修復開銷達到該情況下最小值，為C=10。

圖13為異側故障修復開銷的最大情況，其中p=7，故障磁盤為disk0和disk4，其中深色區域表示由對角校驗集進行修復，淺色部分表示由局部水平校驗集進行修復，修復時優先修復位于對角校驗行的q3，0和q3，4，然后優先選擇對角校驗鏈減少修復開銷，通過q3，3，和q3，7所在的對角校驗鏈修復d2，4和d2，0后，其余丟失數據塊采用局部水平校驗進行修復，此時修復開銷達到該情況下最小值，C=28。

圖14為異側故障的一般情況，其中disk2和disk4發生故障，故障磁盤間距離D=1，該情況下最小修復開銷為C=27。

5 三盤修復

定理5 當三盤故障發生在同一側時，無法進行三盤故障的恢復。

證明 三盤故障對應于矩陣的三列丟失，當數據丟失三列時，嘗試優先保證修復一列即能將三盤修復問題轉換為雙盤修復問題。而三盤故障發生在同一側（左側/右側）時，無法通過對角校驗集或局部水平校驗集來修復任何一列。當三盤故障發生在非同側時，可以通過局部水平校驗列優先修復故障磁盤數量為1的一側，將三盤故障轉換為同側雙盤修復問題，修復另一側的兩個磁盤；否則通過同側雙盤修復反向尋找未使用的對象校驗鏈，結合水平局部校驗修復指定磁盤后完成同側雙盤故障修復，證畢。

當故障磁盤為disk0、disk3、disk4時，由于磁盤disk0單獨位于左側局部校驗集中，可以通過左側局部水平校驗集和disk0對應對角校驗集優先修復該磁盤，當磁盤恢復完成后，該三盤故障問題轉換為同側雙盤故障修復問題，采用第4章中的同側雙盤故障修復方法修復剩余故障磁盤disk3和disk4完成對所有故障磁盤的修復，如圖15所示。

6 理論分析

本章將LHRC與RDP、LRRDP、DRDP從單雙盤故障修復開銷、三盤修復成功率、編譯碼復雜度這幾個影響糾刪碼性能的關鍵指標進行對比，分析LHRC的優缺點和局限性。由于LHRC的參數p并非嚴格素數，為保證相同矩陣大小下進行比較，選擇p=5、p=7和p=13作為比較參數（編譯碼復雜度添加p=37以獲取更準確對比結果）。

6.1 單盤故障修復開銷

根據定理3提出的單盤混合修復模式，LHRC在單盤故障時采用混合修復方式，改善了局部修復碼（LRRDP、DRDP）單盤修復時將數據讀取量集中于局部水平校驗集的修復模式，利用縱式陣列碼并行修復的特點，提升了單盤修復效率。如圖16所示，LHRC相比LRDP、RDP（混合修復）、RDP在平均單盤修復的讀取開銷上減少了13.66%～54.17%，與DRDP的單盤修復讀取開銷相等，但LHRC在讀取數據時采用并行讀取，讀取同樣數量數據塊時讀取的磁盤數大于DRDP，單盤修復效率優于DRDP。

DRDP單盤故障修復時會集中讀取一個或多個磁盤，這樣的讀取方式導致單個或多個磁盤負載過大，而LHRC通過混合修復的方式，在平均讀取開銷相同的情況下將部分讀取壓力轉移至空閑磁盤，減輕了單個磁盤的負載和讀取量，提升了單盤恢復效率。如圖17所示，相比DRDP，LHRC減少了8.33%～33.33%單盤平均最大讀取量。

6.2 雙盤故障修復開銷

雙盤發生故障時，RDP碼需要讀取所有其他磁盤的信息來恢復兩個故障磁盤，LRRDP雖然采用增加1個校驗磁盤的方式來提高單盤故障修復效率并能修復三盤故障，但在雙盤故障時依舊需要讀取所有非故障磁盤來修復雙盤故障，對比RDP在雙盤故障時沒有提升。DRDP雙盤故障時，優先修復全局水平校驗集，再通過局部水平校驗集與對角校驗集混合修復的方式，最大程度減少雙盤修復的讀取開銷。如圖18所示，LHRC相比RDP、LRRDP、DRDP，將平均雙盤故障修復的讀取開銷減少了1.01%～17.74%，在參數p越大時，LHRC在雙盤修復時左/右側局部水平校驗集與對角校驗集重合度越高，LHRC的雙盤修復開銷越小。

6.3 三盤故障修復成功率

三盤修復成功率是指三個磁盤同時發生故障時能夠修復所有故障磁盤的情況，LRRDP、DRDP和LHRC結構相似，并都屬于局部修復碼，容忍三磁盤發生故障，但由于其構造差異，對修復成功率有一定影響。如圖19所示，DRDP三盤修復成功率固定為75%，LHRC相較于LRRDP、DRDP提高了4.07%～15%的修復成功率，在參數p趨近于無窮時，LHRC和LRRDP的修復成功率都趨近于75%。

6.4 編譯碼復雜度

編譯碼復雜度的高低是糾刪碼在編譯碼階段實用性和效率的體現，因此，編譯碼復雜度也是評價糾刪碼性能的重要指標之一。

6.4.1 編碼復雜度

本文將編碼復雜度定義為在編碼過程中單個數據元素生成校驗元素所需要的平均異或次數。

LHRC的設計思路是將DRDP中位于單獨磁盤的對角校驗位遷移至各個磁盤中相同位置，并同樣以對角校驗的方式保護其他磁盤的數據，這樣的編碼方式較小地增加了整體校驗鏈的長度，如圖20所示，在編碼復雜度方面，LHRC與RDP、DRDP相近，相比DRDP，增加了1.37%～11.11%的編碼復雜度，相比于編碼復雜度的較小增加，LHRC在單雙盤修復效率、三盤修復成功率上皆有提升，LHRC利用較少的計算量換取了整體性能的提升。

6.4.2 譯碼復雜度

譯碼復雜度定義為恢復指定個數的故障磁盤需要每個數據元素進行平均異或的次數，由于LHRC在雙盤修復時根據最小恢復代價進行修復，本文只針對單盤故障下的譯碼復雜度進行討論。

LHRC在譯碼時利用局部水平校驗和對角校驗來減少讀取的數據塊數，同時減少了譯碼時進行的異或次數。如圖21所示，LHRC相比RDP，降低了44.00%～48.65%的譯碼復雜度。p=5時，LHRC相比LRRDP降低27.08%的譯碼復雜度，相比DRDP增加了20.00%的譯碼復雜度，隨著參數p增加，譯碼復雜度與LRRDP、DRDP相近。在磁盤陣列中磁盤個數較多的現狀下，LHRC的譯碼復雜度與LRRDP、DRDP相差甚微。

7 實驗分析與比較

本章通過第6章中理論分析結果，以單盤故障修復時間、雙盤故障修復時間作實驗對比。該實驗對比的糾刪碼分別是RDP、LRRDP、DRDP。與上文理論分析一致，編碼參數p分別取5、7、13。實驗環境和參數為：CPU Intel Core i3-12100、內存32 GB、固態硬盤256 GB×14、CentOS7 64位操作系統。文件分塊大小設置為100 KB，為保證不同參數下單個磁盤存放的文件大小一致，分別將文件大小設置為60 MB（p=5）、80 MB（p=7）、140 MB（p=13）。

7.1 編碼時間

LRRDP在RDP的基礎上增加了局部水平校驗列，其思想是通過局部水平校驗減少單盤故障需要讀取的數據塊個數，但LRRDP將全局水平校驗鏈拆分的同時，水平校驗參與的異或次數也變為一半，總的異或次數與RDP相近。DRDP則是將局部水平校驗列替代數據列，拆分全局水平校驗的同時減少了水平校驗時的異或次數。LHRC保留了DRDP局部水平校驗的思想，將對角校驗列改造為對角校驗行，對角校驗行的數據塊個數略多于列中的數據塊個數，其異或次數對比RDP、LRRDP有些許增長，在陣列規模較大時趨于相等，但其混合式編碼結構在磁盤恢復和數據傳輸上相較前者更有優勢。如圖22所示，LHRC在不同參數p的情況下相較RDP、LRRDP、DRDP增加了0.93%～2.30%、2.10%～3.09%、2.98%～12.32%的平均編碼時間。

7.2 單盤故障修復時間

RDP在單盤修復時采用混合修復算法可降低至多25%的數據讀取量，LRRDP在RDP的基礎上添加了冗余磁盤來存儲陣列前半部分數據的冗余數據，單盤故障時僅需讀取部分磁盤來恢復單盤故障。DRDP進一步對LRRDP陣列進行優化，將冗余磁盤遷移至陣列中間位置，縮短了修復鏈的長度，降低了單盤故障的修復時間。本文提出的LHRC碼對DRDP的陣列進行改造，結合橫式陣列碼和縱式陣列碼的優點，將對角校驗列遷移至各個磁盤，形成對角校驗行。單盤故障時，LHRC相比DRDP將數據讀取分散至其他磁盤，降低單個磁盤的總讀取量，提升了單盤修復時磁盤并行讀取效率，加快了單盤故障修復效率。具體分析結果已在第6.1節中詳細敘述。如圖23所示，相比RDP、RDP（混合修復）、LRRDP、DRDP，LHRC分別減少25.02%～29.91%、18.26%～25.97%、10.44%～22.34%、3.92%～12.79%的單盤故障修復總時間。

7.3 雙盤故障修復時間

傳統陣列碼RDP應對雙盤故障需要讀取所有非故障磁盤數據來恢復兩個故障磁盤，大量的讀取開銷給磁盤陣列帶來了巨大的讀寫壓力。LRRDP雖然提高了RDP的單盤故障修復效率，但并沒有改善橫式陣列碼雙盤故障時需要讀取所有正常磁盤的缺點。DRDP改善單盤故障修復效率的同時，采用優先修復全局水平校驗，再利用局部水平校驗與對角校驗混合修復的方式，減少了雙盤故障修復時需要讀取的數據總量，減少了雙盤故障修復時間。LHRC結合橫式陣列碼和縱式陣列碼的校驗分布，構造水平對角校驗集，加深了水平校驗、對角校驗的聯系，增加了局部水平校驗與對角校驗的重疊概率，提升了雙盤故障的修復效率。如圖24所示，相比RDP、LRRDP、DRDP，LHRC碼分別減少13.31%～30.64%、10.85%～28.83%、7.79%～11.04%的雙盤故障修復總時間。

8 結束語

本文針對傳統橫式陣列碼中單、雙盤修復效率低和數據讀取量大的問題，基于局部修復碼和混合陣列碼提出一種局部混合式修復碼——LHRC。LHRC首先以局部修復碼的思想將橫式陣列碼的水平校驗列拆分成兩個局部水平校驗列，再利用縱式陣列碼的思想將對角校驗列遷移至各個磁盤中形成對角校驗行。LHRC縮短了全局水平校驗鏈的長度，并以對角校驗行的形式，增加了水平校驗與對角校驗集的重疊數量，減少了單雙盤修復時所需的數據塊數量，提升了修復效率。并且，LHRC在三盤故障時能夠進行修復，相比同類型可修復三盤故障的編碼（LRRDP、DRDP）具有更高的修復成功率。

通過理論分析，LHRC擁有良好的編譯碼復雜度，相比DRDP，以較小編譯碼復雜度的代價同時換取單雙盤修復效率以及三盤修復成功率的提升。為了評估LHRC在真實環境下的性能，根據計算機運算能力、帶寬波動和磁盤讀寫等差異，本文在同一文件及相同的環境下設置不同的參數p來測試不同編碼的性能差異。實驗結果表明，相比與RDP碼、LRRDP、DRDP，LHRC節省了磁盤故障時單雙盤故障修復時間，并在參數p增大時提升的效率更為明顯，適用于當今節點數量較多的分布式系統和磁盤數量較多的磁盤陣列，擁有良好的應用前景。但LHRC碼在陣列構造時并非嚴格按照素數進行構造，對構造磁盤陣列時的特定磁盤數量具有一定的要求。

參考文獻：

［1］Plank J S.T1：erasure codes for storage applications［C］//Proc of the 4th USENIX Conference on File and Storage Technologies.Berkeley，CA：USENIX Association，2005：1-74.

［2］Weatherspoon H，Kubiatowicz J D.Erasure coding vs.replication：a quantitative comparison［C］//Proc of International Workshop on Peer-to-Peer Systems.Berlin：Springer，2002：328-337.

［3］Reed I S，Solomon G.Polynomial codes over certain finite fields［J］.Journal of The Society for Industrial and Applied Mathematics，1960，8（2）：300-304.

［4］Blaum M，Farrell P G，Van Tilborg H C A，et al.Array codes［J］.Handbook of Coding Theory，1998，2：1855-1909.

［5］Schroeder B，Gibson G A.Understanding disk failure rates：what does an MTTF of 1，000，000 hours mean to you？［J］.ACM Trans on Storage（TOS），2007，3（3）：8-es.

［6］Song Ying，Yang Mingjie，Wang Bo.LEC-PR：proactive recovery method in erasure-coded storage［C］//Proc of the 5th IEEE/ACM Annual Workshop on Emerging Parallel and Distributed Runtime Systems and Middleware.Piscataway，NJ：IEEE Press，2022：9-16.

［7］羅象宏，舒繼武.存儲系統中的糾刪碼研究綜述［J］.計算機研究與發展，2012，49（1）：1-11.（Luo Xianghong，Shu Jiwu.A review of research on corrective censoring codes in storage systems［J］.Journal of Computer Research and Development，2012，49（1）：1-11.）

［8］Blaum M，Brady J，Bruck J，et al.EVENODD：an efficient scheme for tolerating double disk failures in RAID architectures［J］.IEEE Trans on Computers，1995，44（2）：192-202.

［9］Huang Cheng，Xu Lihao.STAR：an efficient coding scheme for correcting triple storage node failures［J］.IEEE Trans on Computers，2008，57（7）：889-901.

［10］Corbett P，English B，Goel A，et al.Row-diagonal parity for double disk failure correction［C］//Proc of the 3rd USENIX Conference on File and Storage Technologies.Berkeley，CA：USENIX Association，2004：1-14.

［11］萬武南，楊威，陳運.一種新的3容錯擴展RAID碼［J］.北京郵電大學學報，2014，37（5）：75-79.（Wan Wunan，Yang Wei，Chen Yun.A new 3-fault tolerant extended RAID code［J］.Journal of Beijing University of Posts and Telecommunications，2014，37（5）：75-79.）

［12］Liang Ningjing，Zhang Xingjun，Wu Xurui，et al.An endurance-aware RAID-6 code with low computational complexity and write overhead［C］//Proc of IEEE International Conference on Parallel amp; Distributed Processing with Applications，Big Data amp; Cloud Computing，Sustainable Computing amp; Communications，Social Computing amp; Networking.Piscataway，NJ：IEEE Press，2021：939-946.

［13］Liang Ningjing，Zhang Xingjun，Chen Heng，et al. Thou code：a triple-erasure-correcting horizontal code with optimal update complexity［J］.The Journal of Supercomputing，2022，78（7）：10088-10117.

［14］Xu Lihao，Bruck J.X-code：MDS array codes with optimal encoding［J］.IEEE Trans on Information Theory，1999，45（1）：272-276.

［15］Chao Jin，Hong Jiang，Dan Feng，et al. P-Code：a new RAID-6 code with optimal properties［C］//Proc of the 23rd International Confe-rence on Supercomputing.New York：ACM Press，2009：360-369.

［16］Hafner J L.WEAVER codes：highly fault tolerant erasure codes for storage systems［C］//Proc of USENIX Conference on File and Storage Technologies.Berkeley，CA：USENIX Association，2005，5：16-16.

［17］元鑄，謝平，耿生玲.RAID系統擴容方案研究綜述［J］.電子學報，2019，47（11）：2420-2431.（Yuan Zhu，Xie Ping，Geng Shengling.A review of research on RAID system expansion schemes［J］.Chinese Journal of Electronics，2019，47（11）：2420-2431.）

［18］Xie Ping，Yuan Zhu，Huang Jianzhong，et al.N-code：an optimal RAID-6 MDS array code for load balancing and high I/O performance［C］//Proc of the 48th International Conference on Parallel Proces-sing.New York：ACM Press，2019：1-10.

［19］解崢，王子豪，唐聃，等.低編譯復雜度的雙容錯陣列碼［J］.計算機應用，2023，43（9）：2766-2774.（Xie Zheng，Wang Zihao，Tang Dan，et al. Dual fault-tolerant array codes with low compilation complexity［J］.Journal of Computer Applications，2023，43（9）：2766-2774.）

［20］Fu Yingxun，Shu Jiwu，Shen Zhirong，et al. Reconsidering single disk failure recovery for erasure coded storage systems：optimizing load ba-lancing in stack-level［J］.IEEE Trans on Parallel and Distributed Systems，2015，27（5）：1457-1469.

［21］Xiang Liping，Xu Yinlong，Lui J C S，et al. Optimal recovery of single disk failure in RDP code storage systems［J］.ACM SIGMETRICS Performance Evaluation Review，2010，38（1）：119-130.

［22］Dimakis A G，Godfrey P B，Wu Yunnan，et al. Network coding for distributed storage systems［J］.IEEE Trans on Information Theory，2010，56（9）：4539-4551.

［23］蕭楓，唐聃，范迪，等.一種低單盤故障恢復開銷的局部修復碼［J］.計算機工程與應用，2018，54（18）：66-73.（Xiao Feng，Tang Dan，Fan Di，et al. Local repairable code with low single disk failure recovery overhead［J］.Computer Engineering and Applications，2018，54（18）：66-73.）

［24］洪鐵原，唐聃，熊攀，等.存儲系統中的局部修復陣列碼模型［J］.計算機應用研究，2024，41（1）：193-199.（Hong Tieyuan，Tang Dan，Xiong Pan et al. Local repair array code model in storage systems［J］.Application Research of Computers，2024，41（1）：193-199.）

［25］楊松霖，張廣艷.糾刪碼存儲系統中數據修復方法綜述［J］.計算機科學與探索，2017，11（10）：1531-1544.（Yang Songlin，Zhang Guangyan.A review of data repair methods in corrective deletion code storage systems［J］.Journal of Frontiers of Computer Science and Technology，2017，11（10）：1531-1544.）

［26］Chao Jin，Dan Feng，Hong Jiang，et al.A comprehensive study on RAID-6 codes：horizontal vs.vertical［C］//Proc of the 6th IEEE International Conference on Networking，Architecture，and Storage.Piscataway，NJ：IEEE Press，2011：102-111.