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

關(guān)鍵詞：陣列碼；存儲系統(tǒng)；局部修復(fù)；讀取開銷

中圖分類號：TP333.3"" 文獻(xiàn)標(biāo)志碼：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 引言

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

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

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

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

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

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

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

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

1 陣列碼

1.1 陣列碼概念

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

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

a）數(shù)據(jù)塊。存儲真實(shí)用戶原始數(shù)據(jù)的一塊數(shù)據(jù)串。

b）校驗(yàn)塊。利用糾刪碼算法，通過多塊數(shù)據(jù)塊計(jì)算得到的冗余信息的一塊數(shù)據(jù)串。

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

d）條塊。處于同一存儲設(shè)備上屬于同一條帶的數(shù)據(jù)集合，條塊的大小由條塊所包含的數(shù)據(jù)塊或校驗(yàn)塊個數(shù)決定。

e）橫式陣列碼。冗余獨(dú)立于數(shù)據(jù)條塊，并單獨(dú)存儲在冗余條塊中的編碼方式。

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

g）混合陣列碼。結(jié)合橫式陣列碼與縱式陣列碼的數(shù)據(jù)存儲方式，部分條塊混合存儲數(shù)據(jù)塊和校驗(yàn)塊，部分條塊集中存儲校驗(yàn)塊。

1.2 橫式陣列碼

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

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

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

1.3 縱式陣列碼

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

2 LHRC

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

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

2.1 編碼

左側(cè)局部水平校驗(yàn)列和右側(cè)局部水平校驗(yàn)列的編碼公式如式（3）（4）所示。

對角校驗(yàn)行的編碼公式如式（5）所示。

驗(yàn)集中，通過單個局部水平校驗(yàn)與對角校驗(yàn)混合修復(fù)的方式，減少數(shù)據(jù)塊的讀取，提升修復(fù)效率。

當(dāng)p=5且故障磁盤位于disk1時，對角校驗(yàn)集與左側(cè)水平校驗(yàn)集數(shù)據(jù)塊重合數(shù)為3，參與修復(fù)的右側(cè)區(qū)域中數(shù)據(jù)塊數(shù)量為1，采用對角校驗(yàn)修復(fù)數(shù)據(jù)塊q2，1后，其余丟失數(shù)據(jù)塊采用左側(cè)局部水平校驗(yàn)進(jìn)行修復(fù)，參與修復(fù)的總數(shù)據(jù)塊數(shù)為7，如圖7所示。

2.2 譯碼

3 單盤修復(fù)

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

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

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

4 雙盤修復(fù)

雙盤修復(fù)時，由于對角校驗(yàn)行只能通過相應(yīng)對角校驗(yàn)元素修復(fù)，所以修復(fù)時優(yōu)先修復(fù)故障磁盤對應(yīng)的對角校驗(yàn)元素（同單盤故障），若該校驗(yàn)鏈包含另一故障磁盤數(shù)據(jù)塊，則以該數(shù)據(jù)塊為起點(diǎn)，反向搜尋恢復(fù)起點(diǎn)，直到全部故障數(shù)據(jù)塊完成修復(fù)。

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

4.1 同側(cè)雙盤故障

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

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

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

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

b）通過左側(cè)局部水平校驗(yàn)集：d0，0、d0，1異或運(yùn)算恢復(fù)p0，2；

c）通過對角校驗(yàn)集：p0，2、d1，1、p3，5異或運(yùn)算恢復(fù)q2，0；

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

e）通過左側(cè)水平校驗(yàn)集：d1，0、d1，1異或運(yùn)算恢復(fù)p1，2；

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

g）通過左側(cè)局部水平校驗(yàn)集：d3，1、p3，2異或運(yùn)算恢復(fù)d3，0。

4.2 異側(cè)雙盤故障

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

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

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

5 三盤修復(fù)

定理5 當(dāng)三盤故障發(fā)生在同一側(cè)時，無法進(jìn)行三盤故障的恢復(fù)。

證明 三盤故障對應(yīng)于矩陣的三列丟失，當(dāng)數(shù)據(jù)丟失三列時，嘗試優(yōu)先保證修復(fù)一列即能將三盤修復(fù)問題轉(zhuǎn)換為雙盤修復(fù)問題。而三盤故障發(fā)生在同一側(cè)（左側(cè)/右側(cè)）時，無法通過對角校驗(yàn)集或局部水平校驗(yàn)集來修復(fù)任何一列。當(dāng)三盤故障發(fā)生在非同側(cè)時，可以通過局部水平校驗(yàn)列優(yōu)先修復(fù)故障磁盤數(shù)量為1的一側(cè)，將三盤故障轉(zhuǎn)換為同側(cè)雙盤修復(fù)問題，修復(fù)另一側(cè)的兩個磁盤；否則通過同側(cè)雙盤修復(fù)反向?qū)ふ椅词褂玫膶ο笮ｒ?yàn)鏈，結(jié)合水平局部校驗(yàn)修復(fù)指定磁盤后完成同側(cè)雙盤故障修復(fù)，證畢。

當(dāng)故障磁盤為disk0、disk3、disk4時，由于磁盤disk0單獨(dú)位于左側(cè)局部校驗(yàn)集中，可以通過左側(cè)局部水平校驗(yàn)集和disk0對應(yīng)對角校驗(yàn)集優(yōu)先修復(fù)該磁盤，當(dāng)磁盤恢復(fù)完成后，該三盤故障問題轉(zhuǎn)換為同側(cè)雙盤故障修復(fù)問題，采用第4章中的同側(cè)雙盤故障修復(fù)方法修復(fù)剩余故障磁盤disk3和disk4完成對所有故障磁盤的修復(fù)，如圖15所示。

6 理論分析

本章將LHRC與RDP、LRRDP、DRDP從單雙盤故障修復(fù)開銷、三盤修復(fù)成功率、編譯碼復(fù)雜度這幾個影響糾刪碼性能的關(guān)鍵指標(biāo)進(jìn)行對比，分析LHRC的優(yōu)缺點(diǎn)和局限性。由于LHRC的參數(shù)p并非嚴(yán)格素?cái)?shù)，為保證相同矩陣大小下進(jìn)行比較，選擇p=5、p=7和p=13作為比較參數(shù)（編譯碼復(fù)雜度添加p=37以獲取更準(zhǔn)確對比結(jié)果）。

6.1 單盤故障修復(fù)開銷

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

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

6.2 雙盤故障修復(fù)開銷

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

6.3 三盤故障修復(fù)成功率

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

6.4 編譯碼復(fù)雜度

編譯碼復(fù)雜度的高低是糾刪碼在編譯碼階段實(shí)用性和效率的體現(xiàn)，因此，編譯碼復(fù)雜度也是評價糾刪碼性能的重要指標(biāo)之一。

6.4.1 編碼復(fù)雜度

本文將編碼復(fù)雜度定義為在編碼過程中單個數(shù)據(jù)元素生成校驗(yàn)元素所需要的平均異或次數(shù)。

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

6.4.2 譯碼復(fù)雜度

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

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

7 實(shí)驗(yàn)分析與比較

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

7.1 編碼時間

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

7.2 單盤故障修復(fù)時間

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

7.3 雙盤故障修復(fù)時間

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

8 結(jié)束語

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

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

參考文獻(xiàn)：

［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，F(xiàn)arrell 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］羅象宏，舒繼武.存儲系統(tǒng)中的糾刪碼研究綜述［J］.計(jì)算機(jī)研究與發(fā)展，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］萬武南，楊威，陳運(yùn).一種新的3容錯擴(kuò)展RAID碼［J］.北京郵電大學(xué)學(xué)報，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系統(tǒng)擴(kuò)容方案研究綜述［J］.電子學(xué)報，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］解崢，王子豪，唐聃，等.低編譯復(fù)雜度的雙容錯陣列碼［J］.計(jì)算機(jī)應(yīng)用，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］蕭楓，唐聃，范迪，等.一種低單盤故障恢復(fù)開銷的局部修復(fù)碼［J］.計(jì)算機(jī)工程與應(yīng)用，2018，54（18）：66-73.（Xiao Feng，Tang Dan，F(xiàn)an Di，et al. Local repairable code with low single disk failure recovery overhead［J］.Computer Engineering and Applications，2018，54（18）：66-73.）

［24］洪鐵原，唐聃，熊攀，等.存儲系統(tǒng)中的局部修復(fù)陣列碼模型［J］.計(jì)算機(jī)應(yīng)用研究，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］楊松霖，張廣艷.糾刪碼存儲系統(tǒng)中數(shù)據(jù)修復(fù)方法綜述［J］.計(jì)算機(jī)科學(xué)與探索，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.