低修復(fù)成本的局部混合修復(fù)陣列碼模型

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

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

中圖分類號(hào)：TP333.3"" 文獻(xiàn)標(biāo)志碼：A

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

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

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

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

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

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

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

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

1 陣列碼

1.1 陣列碼概念

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

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

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

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

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

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

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

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

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

1.2 橫式陣列碼

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

RDP作為經(jīng)典的橫式陣列碼，其條帶由一個(gè)（p-1）×（p+1）的二維陣列構(gòu)成。p=5的RDP矩陣構(gòu)造如圖2所示，其中，disk4存放水平校驗(yàn)位，每個(gè)校驗(yàn)元素由其所在行中disk0～disk3的數(shù)據(jù)元素異或形成，disk5存放對(duì)角校驗(yàn)位，其水平校驗(yàn)和對(duì)角校驗(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)塊通常平均分布于磁盤(pán)陣列中的每個(gè)磁盤(pán)中，具有良好的讀寫(xiě)效率及編譯碼復(fù)雜度。當(dāng)磁盤(pán)發(fā)生故障時(shí)，多數(shù)磁盤(pán)共同參與修復(fù)，相比于橫式陣列碼集中于部分磁盤(pán)的修復(fù)方式，可以提高磁盤(pán)故障的修復(fù)效率［26］。但縱式陣列碼數(shù)據(jù)塊和校驗(yàn)塊間緊密聯(lián)系的特點(diǎn)，限制了磁盤(pán)的擴(kuò)展能力。

2 LHRC

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

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

2.1 編碼

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

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

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

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

2.2 譯碼

3 單盤(pán)修復(fù)

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

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

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

4 雙盤(pán)修復(fù)

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

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

4.1 同側(cè)雙盤(pán)故障

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

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

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

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

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

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

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

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

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

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

4.2 異側(cè)雙盤(pán)故障

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

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

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

5 三盤(pán)修復(fù)

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

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

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

6 理論分析

本章將LHRC與RDP、LRRDP、DRDP從單雙盤(pán)故障修復(fù)開(kāi)銷、三盤(pán)修復(fù)成功率、編譯碼復(fù)雜度這幾個(gè)影響糾刪碼性能的關(guān)鍵指標(biāo)進(jìn)行對(duì)比，分析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)確對(duì)比結(jié)果）。

6.1 單盤(pán)故障修復(fù)開(kāi)銷

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

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

6.2 雙盤(pán)故障修復(fù)開(kāi)銷

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

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

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

6.4 編譯碼復(fù)雜度

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

6.4.1 編碼復(fù)雜度

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

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

6.4.2 譯碼復(fù)雜度

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

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

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

本章通過(guò)第6章中理論分析結(jié)果，以單盤(pán)故障修復(fù)時(shí)間、雙盤(pán)故障修復(fù)時(shí)間作實(shí)驗(yàn)對(duì)比。該實(shí)驗(yàn)對(duì)比的糾刪碼分別是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)硬盤(pán)256 GB×14、CentOS7 64位操作系統(tǒng)。文件分塊大小設(shè)置為100 KB，為保證不同參數(shù)下單個(gè)磁盤(pán)存放的文件大小一致，分別將文件大小設(shè)置為60 MB（p=5）、80 MB（p=7）、140 MB（p=13）。

7.1 編碼時(shí)間

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

7.2 單盤(pán)故障修復(fù)時(shí)間

RDP在單盤(pán)修復(fù)時(shí)采用混合修復(fù)算法可降低至多25%的數(shù)據(jù)讀取量，LRRDP在RDP的基礎(chǔ)上添加了冗余磁盤(pán)來(lái)存儲(chǔ)陣列前半部分?jǐn)?shù)據(jù)的冗余數(shù)據(jù)，單盤(pán)故障時(shí)僅需讀取部分磁盤(pán)來(lái)恢復(fù)單盤(pán)故障。DRDP進(jìn)一步對(duì)LRRDP陣列進(jìn)行優(yōu)化，將冗余磁盤(pán)遷移至陣列中間位置，縮短了修復(fù)鏈的長(zhǎng)度，降低了單盤(pán)故障的修復(fù)時(shí)間。本文提出的LHRC碼對(duì)DRDP的陣列進(jìn)行改造，結(jié)合橫式陣列碼和縱式陣列碼的優(yōu)點(diǎn)，將對(duì)角校驗(yàn)列遷移至各個(gè)磁盤(pán)，形成對(duì)角校驗(yàn)行。單盤(pán)故障時(shí)，LHRC相比DRDP將數(shù)據(jù)讀取分散至其他磁盤(pán)，降低單個(gè)磁盤(pán)的總讀取量，提升了單盤(pán)修復(fù)時(shí)磁盤(pán)并行讀取效率，加快了單盤(pán)故障修復(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%的單盤(pán)故障修復(fù)總時(shí)間。

7.3 雙盤(pán)故障修復(fù)時(shí)間

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

8 結(jié)束語(yǔ)

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

通過(guò)理論分析，LHRC擁有良好的編譯碼復(fù)雜度，相比DRDP，以較小編譯碼復(fù)雜度的代價(jià)同時(shí)換取單雙盤(pán)修復(fù)效率以及三盤(pán)修復(fù)成功率的提升。為了評(píng)估LHRC在真實(shí)環(huán)境下的性能，根據(jù)計(jì)算機(jī)運(yùn)算能力、帶寬波動(dòng)和磁盤(pán)讀寫(xiě)等差異，本文在同一文件及相同的環(huán)境下設(shè)置不同的參數(shù)p來(lái)測(cè)試不同編碼的性能差異。實(shí)驗(yàn)結(jié)果表明，相比與RDP碼、LRRDP、DRDP，LHRC節(jié)省了磁盤(pán)故障時(shí)單雙盤(pán)故障修復(fù)時(shí)間，并在參數(shù)p增大時(shí)提升的效率更為明顯，適用于當(dāng)今節(jié)點(diǎn)數(shù)量較多的分布式系統(tǒng)和磁盤(pán)數(shù)量較多的磁盤(pán)陣列，擁有良好的應(yīng)用前景。但LHRC碼在陣列構(gòu)造時(shí)并非嚴(yán)格按照素?cái)?shù)進(jìn)行構(gòu)造，對(duì)構(gòu)造磁盤(pán)陣列時(shí)的特定磁盤(pán)數(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］羅象宏，舒繼武.存儲(chǔ)系統(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］萬(wàn)武南，楊威，陳運(yùn).一種新的3容錯(cuò)擴(kuò)展RAID碼［J］.北京郵電大學(xué)學(xué)報(bào)，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é)報(bào)，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ù)雜度的雙容錯(cuò)陣列碼［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］蕭楓，唐聃，范迪，等.一種低單盤(pán)故障恢復(fù)開(kāi)銷的局部修復(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］洪鐵原，唐聃，熊攀，等.存儲(chǔ)系統(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］楊松霖，張廣艷.糾刪碼存儲(chǔ)系統(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.