存儲(chǔ)系統(tǒng)中的局部修復(fù)陣列碼模型

洪鐵原 唐聃 熊攀 蔡紅亮 曾瓊 許源平

摘 要：對(duì)于單容錯(cuò)和雙容錯(cuò)的存儲(chǔ)系統(tǒng)，在磁盤(pán)修復(fù)過(guò)程中發(fā)生的任何故障都可能引起數(shù)據(jù)丟失，導(dǎo)致修復(fù)失敗，保證數(shù)據(jù)的修復(fù)效率對(duì)于存儲(chǔ)系統(tǒng)的可靠性至關(guān)重要。RDP碼在進(jìn)行單盤(pán)故障修復(fù)時(shí)使用混合恢復(fù)算法能減少25%的讀取總量，但是在進(jìn)行雙盤(pán)故障修復(fù)時(shí)需讀取所有的元素。針對(duì)目前難以同時(shí)提升單雙盤(pán)故障修復(fù)效率的問(wèn)題，對(duì)RDP碼進(jìn)行拓展，提出了一種具有局部修復(fù)性質(zhì)的陣列碼模型——DRDP碼。DRDP碼在RDP碼的基礎(chǔ)上將部分?jǐn)?shù)據(jù)列按水平線進(jìn)行異或計(jì)算生成局部水平校驗(yàn)列，并將其參與到全局校驗(yàn)列的編碼計(jì)算中，從而縮短了修復(fù)鏈，使其擁有局部修復(fù)的功能。通過(guò)理論分析，DRDP碼擁有良好的編譯碼復(fù)雜度和更新效率，大幅節(jié)省了單盤(pán)故障修復(fù)讀取開(kāi)銷(xiāo)，并對(duì)雙盤(pán)故障修復(fù)讀取開(kāi)銷(xiāo)進(jìn)行了優(yōu)化，同時(shí)能修復(fù)75%三盤(pán)故障的情況。實(shí)驗(yàn)結(jié)果表明，與RDP碼、LRRDP碼和RDP（p，3）碼相比，DRDP碼的編碼時(shí)間可節(jié)省8.23%～32.89%、單盤(pán)故障修復(fù)時(shí)間可節(jié)省7.08%～35.01%、雙盤(pán)故障修復(fù)時(shí)間可節(jié)省5.07%～29.26%。

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

中圖分類(lèi)號(hào)：TP333.3?? 文獻(xiàn)標(biāo)志碼：A?? 文章編號(hào)：1001-3695（2024）01-029-0193-07

doi：10.19734/j.issn.1001-3695.2023.05.0211

Local repairable array code model in storage systems

Abstract：For single fault tolerance and double fault tolerance systems，any failures that occurs during the disk repair process may cause data loss，leading to repair failure.Ensuring the efficiency of data repair is essential to the reliability of storage systems.RDP code（row diagonal parity code） can reduce the total number of reads by 25% when using the hybrid recovery algorithm for single disk failure repair，but all elements need to be read when repairing double disk failure.To address the current difficulties in improving the efficiency of single and double disk failure repair at the same time，this paper extended RDP code and proposed an array code model with local repair properties，namely DRDP code （double rows diagonal parity code）.Based on RDP code，DRDP code generated a local horizontal parity column by XOR calculation of some data columns according to horizontal lines and participated it in the encoding calculation of global parity columns，thus shortening the repair chain and making it have the function of local repair.Through theoretical analysis，DRDP code not only has good encoding and decoding complexity and update efficiency，but also significantly saves the single disk failure repair read overhead and optimizes the double disk failure repair read overhead.It can also repair 75% of three disk failure cases.The experimental results show that compared with RDP code，LRRDP code，and RDP （p，3） code，the encoding time of DRDP code can be saved by 8.23% to 32.89%，the repair time of single disk failure can be saved by 7.08% to 35.01%，and the repair time of double disk failure can be saved by 5.07% to 29.26%.

Key words：array code；RDP code；storage system；local repair；read overhead

0 引言

隨著大數(shù)據(jù)和計(jì)算機(jī)存儲(chǔ)技術(shù)的快速發(fā)展，各種數(shù)據(jù)的存儲(chǔ)量呈爆炸式增長(zhǎng)，對(duì)存儲(chǔ)系統(tǒng)的可靠性帶來(lái)了巨大的挑戰(zhàn)。陣列碼［1］因其計(jì)算復(fù)雜度要遠(yuǎn)低于基于有限域的編碼［2］，從而能大幅度加快數(shù)據(jù)修復(fù)速度、減少修復(fù)時(shí)間，解決了傳統(tǒng)糾刪碼窗口漏洞時(shí)間過(guò)長(zhǎng)的問(wèn)題，提高了存儲(chǔ)系統(tǒng)的可用性和可靠性，從而得到了廣泛應(yīng)用。陣列碼屬于線性分組碼的一種，早期常應(yīng)用于磁盤(pán)陣列中的容錯(cuò)，隨著存儲(chǔ)規(guī)模的不斷擴(kuò)大，分布式存儲(chǔ)系統(tǒng)應(yīng)運(yùn)而生，陣列碼也可應(yīng)用于分布式存儲(chǔ)系統(tǒng)中節(jié)點(diǎn)間的容錯(cuò)。具有MDS（maximum distance separable）性質(zhì)的陣列碼指在保證存儲(chǔ)開(kāi)銷(xiāo)一致的同時(shí)具有最佳容錯(cuò)能力的陣列碼，經(jīng)典的MDS陣列碼有EVENODD碼［4］、RDP碼［5］、X碼［6］、STAR碼［7］等。EVENODD碼和RDP碼作為RAID-6（redundant array of independent disks）［3］中最常用的容兩錯(cuò)陣列碼，其將數(shù)據(jù)元素存儲(chǔ)在一個(gè)二維陣列中并通過(guò)增加兩個(gè)冗余列存儲(chǔ)校驗(yàn)元素，編譯碼操作簡(jiǎn)單，易于實(shí)現(xiàn)，但是存在著數(shù)據(jù)修復(fù)時(shí)讀取開(kāi)銷(xiāo)過(guò)高、數(shù)據(jù)讀取不均衡導(dǎo)致磁盤(pán)熱點(diǎn)集中和容錯(cuò)能力限制等問(wèn)題。近年來(lái)提出的能容兩錯(cuò)的MDS陣列碼有Lamda碼［8］、N碼［9］等。Lamda碼在一定程度上消除了碼字的瓶頸效應(yīng)以及達(dá)到了負(fù)載均衡的效果；N碼在保證最佳存儲(chǔ)效率的同時(shí)，在正常讀取和降級(jí)讀取性能上有所提升。隨著硬盤(pán)和節(jié)點(diǎn)數(shù)量的增多，給存儲(chǔ)系統(tǒng)的容錯(cuò)能力帶來(lái)了巨大挑戰(zhàn)。文獻(xiàn)［7］對(duì)EVENODD碼進(jìn)行拓展，提出了能容三錯(cuò)的STAR碼，但其存在容易造成I/O瓶頸、小寫(xiě)性能不均衡和計(jì)算復(fù)雜度較高等問(wèn)題；萬(wàn)武南等人［10］提出RDP碼的拓展碼X-RDP碼，在保證小寫(xiě)性能均衡的前提下保證能容三錯(cuò)。MDS陣列碼在提高容錯(cuò)能力的同時(shí)需要付出很大的代價(jià)，研究人員通過(guò)犧牲部分存儲(chǔ)效率來(lái)進(jìn)一步提升容錯(cuò)能力，經(jīng)典的非MDS陣列碼包括斜率碼［11］、Weaver碼［12］、Hover碼［13］和Grid碼［14］等，此類(lèi)陣列碼雖然在存儲(chǔ)效率上達(dá)不到最優(yōu)，但是大大增加了容錯(cuò)能力。根據(jù)陣列碼校驗(yàn)元素的布局，主要可分為橫式陣列碼和縱式陣列碼。橫式陣列碼把數(shù)據(jù)元素和校驗(yàn)元素分別存儲(chǔ)在不同的存儲(chǔ)設(shè)備中，目前常用的橫式陣列碼有容兩錯(cuò)的EVENODD碼、RDP碼、容三錯(cuò)的STAR碼以及它們的拓展碼，橫式陣列碼的優(yōu)點(diǎn)是數(shù)據(jù)元素與校驗(yàn)元素相互獨(dú)立存放，縮短了碼鏈的構(gòu)造。近年來(lái)提出的橫式陣列碼有Ear碼［15］、Thou碼［16］等。Ear碼基于RDP碼，通過(guò)為每個(gè)條帶添加額外的對(duì)角校驗(yàn)元素，并設(shè)計(jì)新的校驗(yàn)生成規(guī)則，從而減少與每個(gè)數(shù)據(jù)元素相關(guān)聯(lián)的校驗(yàn)元素的數(shù)量，使得Ear碼具有較低的編譯碼復(fù)雜度；Thou碼作為MDS碼，能同時(shí)能容忍三個(gè)磁盤(pán)的故障，其具有最低的存儲(chǔ)開(kāi)銷(xiāo)、較低的編譯碼復(fù)雜度和最優(yōu)的更新效率。經(jīng)典的縱式陣列碼有X碼、P碼［17］和WEAVER碼等，其因?qū)?shù)據(jù)元素與校驗(yàn)元素均勻安放在存儲(chǔ)設(shè)備中，從而具有良好的負(fù)載均衡特性。近年來(lái)提出的縱式陣列碼有X+碼［18］，X+碼基于子條帶進(jìn)行編碼，在容錯(cuò)能力提升到3的同時(shí)具有最優(yōu)的更新效率。

為了保證存儲(chǔ)系統(tǒng)的可用性和數(shù)據(jù)可靠性，降低磁盤(pán)故障修復(fù)所需的時(shí)間尤為重要。根據(jù)對(duì)數(shù)據(jù)中心產(chǎn)生的各種數(shù)據(jù)丟失的問(wèn)題進(jìn)行統(tǒng)計(jì)分析，在存儲(chǔ)系統(tǒng)的磁盤(pán)故障失效情況中，單磁盤(pán)失效占比高達(dá)99.75%［19］。為了保證存儲(chǔ)系統(tǒng)的可靠性，如何加快陣列碼在單磁盤(pán)故障修復(fù)的修復(fù)速度、減少漏洞窗口的時(shí)間、提高存儲(chǔ)系統(tǒng)的可靠性成為了近幾年的研究熱點(diǎn)之一。在存儲(chǔ)系統(tǒng)中，降低單盤(pán)故障修復(fù)時(shí)間的方法主要有降低修復(fù)讀取總量和提高修復(fù)并行度兩種方式［20］。文獻(xiàn)［21］提出了混合修復(fù)算法RDOR（row diagonal optimal recovery），RDOR同時(shí)使用兩種不同的校驗(yàn)集進(jìn)行單盤(pán)故障修復(fù)，其中使用水平校驗(yàn)集對(duì)一半元素進(jìn)行修復(fù)，使用對(duì)角校驗(yàn)集對(duì)另一半元素進(jìn)行修復(fù)，通過(guò)最大化不同類(lèi)型的校驗(yàn)集之間的重疊元素，可以減少25%的讀取總量，且能保證磁盤(pán)間的負(fù)載均衡，緩解I/O過(guò)熱，然而由于陣列碼結(jié)構(gòu)規(guī)則的限制，混合修復(fù)算法很難推廣到其他碼；文獻(xiàn)［22］提出了一種基于X碼的單盤(pán)故障修復(fù)最優(yōu)恢復(fù)方案MDRR（minimum disk read recovery），其最大限度地減少了故障修復(fù)時(shí)磁盤(pán)讀取的次數(shù)；文獻(xiàn)［23］構(gòu)造了一種容雙錯(cuò)的陣列碼L碼，在縮短單磁盤(pán)故障修復(fù)時(shí)間的同時(shí)降低了數(shù)據(jù)更新時(shí)的代價(jià)；文獻(xiàn)［24］提出了一種橫式陣列碼W碼，在單盤(pán)故障時(shí)能讓所有磁盤(pán)的元素都參與修復(fù)，且在修復(fù)時(shí)讀取的元素更少，縮短了修復(fù)的時(shí)間；針對(duì)優(yōu)化縱式碼的恢復(fù)讀取開(kāi)銷(xiāo)，文獻(xiàn)［25］在校驗(yàn)元素不變的情況下將X碼的數(shù)據(jù)元素調(diào)整為水平分布，減少了單盤(pán)故障恢復(fù)讀取開(kāi)銷(xiāo)；文獻(xiàn)［26］構(gòu)造了一種混合陣列碼J碼，J碼將部分校驗(yàn)元素均勻放置在各磁盤(pán)中，緩解了I/O瓶頸問(wèn)題，同時(shí)提出一種算法可降低單盤(pán)故障的修復(fù)讀取開(kāi)銷(xiāo)，但相比RDP碼、EVENODD碼，J碼編碼復(fù)雜度偏低，且碼率僅高于X碼；Fu等人［27］系統(tǒng)地研究了在堆棧級(jí)的單盤(pán)故障修復(fù)的問(wèn)題，并提出了一種旋轉(zhuǎn)修復(fù)算法以降低修復(fù)過(guò)程的數(shù)據(jù)讀取；文獻(xiàn)［28］提出了一種局部修復(fù)碼LRRDP（local repairable RDP），該碼在RDP碼的基礎(chǔ)上再增加一個(gè)局部校驗(yàn)列以減少單盤(pán)故障時(shí)的修復(fù)讀取開(kāi)銷(xiāo)，但是LRRDP碼的雙盤(pán)故障修復(fù)讀取開(kāi)銷(xiāo)與原始RDP碼一致，沒(méi)有任何優(yōu)化。

隨著存儲(chǔ)系統(tǒng)規(guī)模的不斷擴(kuò)大，保證在多磁盤(pán)故障時(shí)的數(shù)據(jù)修復(fù)效率變得越來(lái)越重要。Wan等人［29］提出了條帶單元組的概念，并構(gòu)建了一種雙盤(pán)故障快速修復(fù)編碼Code-M，Code-M通過(guò)將條帶分組的方式將組內(nèi)和組外的數(shù)據(jù)元素進(jìn)行混合編碼，使不同元素的修復(fù)鏈間存在重疊區(qū)域，很大程度上減少了雙盤(pán)故障修復(fù)時(shí)讀取的數(shù)據(jù)量，但是Code-M在進(jìn)行故障修復(fù)時(shí)需要從其他條帶單元組讀取大量數(shù)據(jù)；文獻(xiàn)［30］對(duì)Code-M進(jìn)行拓展，提出了一種基于局部冗余混合編碼Code-LM，Code-LM犧牲了一部分存儲(chǔ)效率，通過(guò)在每個(gè)條帶組中增加局部校驗(yàn)元素來(lái)縮短修復(fù)鏈，在故障修復(fù)時(shí)大量減少了從其他條帶單元組讀取的數(shù)據(jù)，進(jìn)一步節(jié)省了磁盤(pán)故障的修復(fù)時(shí)間；此外Chen等人［31］提出了一種RDP碼的拓展碼RDP（p，3）碼，RDP（p，3）碼是在RDP碼的基礎(chǔ)上增加一列斜率為“-1”的校驗(yàn)列構(gòu)成，在雙盤(pán)故障修復(fù)時(shí)通過(guò)增加修復(fù)并行度來(lái)縮短修復(fù)鏈，從而加速修復(fù)過(guò)程，但是其雙盤(pán)故障修復(fù)讀取開(kāi)銷(xiāo)與RDP碼一致。

目前學(xué)術(shù)屆對(duì)磁盤(pán)故障的快速修復(fù)方案的研究?jī)H限于單盤(pán)或雙盤(pán)，對(duì)于同時(shí)提升單雙盤(pán)故障修復(fù)效率的研究較少。針對(duì)以上問(wèn)題，本文在RDP碼的基礎(chǔ)上，提出了一種具有局部修復(fù)性質(zhì)的陣列碼模型——DRDP碼。DRDP碼在保證編譯碼復(fù)雜度和更新效率的同時(shí)，有效降低了單雙盤(pán)故障修復(fù)讀取開(kāi)銷(xiāo)，降低了故障修復(fù)的時(shí)間，容錯(cuò)能力也有所提升，在目前的存儲(chǔ)系統(tǒng)中擁有良好的應(yīng)用前景。

1 RDP碼介紹

RDP碼作為存儲(chǔ)系統(tǒng)中常用的陣列碼之一，編譯碼過(guò)程只需要進(jìn)行XOR操作，大幅度降低了計(jì)算復(fù)雜度，且在磁盤(pán)故障時(shí)修復(fù)需要下載的數(shù)據(jù)量相比經(jīng)典的RS碼（Reed-Solomon code）［2］要少得多，從而節(jié)省了磁盤(pán)故障的修復(fù)時(shí)間。

為了方便理解與研究，首先給出一些陣列碼的常用術(shù)語(yǔ)。a）數(shù)據(jù)元素：用戶(hù)上傳至存儲(chǔ)系統(tǒng)中被等量劃分的原始數(shù)據(jù)；b）校驗(yàn)元素：數(shù)據(jù)元素通過(guò)特定的糾刪碼編碼算法生成得到的冗余元素；c）條帶：一組由數(shù)據(jù)元素和校驗(yàn)元素組成的二維陣列，編譯碼操作的基本單位；d）數(shù)據(jù)列：一列可以代表一個(gè)存儲(chǔ)數(shù)據(jù)元素的磁盤(pán)；e）校驗(yàn)列：一列可以代表一個(gè)存儲(chǔ)校驗(yàn)元素的磁盤(pán)；f）編碼：將數(shù)據(jù)元素通過(guò)相應(yīng)糾刪碼算法計(jì)算出校驗(yàn)元素的過(guò)程；g）更新：當(dāng)數(shù)據(jù)元素發(fā)生改變時(shí)，重新計(jì)算相應(yīng)校驗(yàn)元素的過(guò)程；h）修復(fù)：存活元素采用特定的修復(fù)算法恢復(fù)丟失的元素的過(guò)程；i）容錯(cuò)能力：陣列碼能容忍出錯(cuò)的列數(shù)。

1.1 RDP碼編碼過(guò)程

RDP碼作為最經(jīng)典的容兩錯(cuò)MDS陣列碼之一，其條帶由一個(gè)（p-1）×（p+1）的二維陣列構(gòu)成，為保證其MDS性質(zhì)，其參數(shù)p為素?cái)?shù)。和EVENODD碼相同，RDP碼對(duì)數(shù)據(jù)元素采用水平線（斜率為“0”）和對(duì)角線（斜率為“1”）的方式進(jìn)行異或計(jì)算編碼。假設(shè)二維陣列中的每一列代表一個(gè)磁盤(pán)，首先將原始數(shù)據(jù)按條帶進(jìn)行等量分塊存放在二維陣列的前p-1列，經(jīng)過(guò)水平校驗(yàn)生成的校驗(yàn)元素存放在第p列中，而經(jīng)過(guò)對(duì)角校驗(yàn)生成的校驗(yàn)元素放在第p+1列。水平校驗(yàn)列和對(duì)角校驗(yàn)列的編碼公式分別如式（1）（2）所示。

其中：ai，j代表二維陣列中第i行第j列的元素，i∈［0，p-2］、j∈［0，p］；〈i-j〉p表示（i-j） mod p，mod為取模運(yùn)算，其結(jié)果永遠(yuǎn)為大于等于0且小于p的一個(gè)整數(shù)。圖1展示了在p=5時(shí)RDP碼的編碼過(guò)程，其中白色背景圖案代表該元素是原始數(shù)據(jù)元素，灰色背景圖案代表該元素是校驗(yàn)元素。

1.2 RDP碼譯碼過(guò)程

傳統(tǒng)的RDP碼在面對(duì)單盤(pán)故障的情況時(shí)，若故障的是數(shù)據(jù)列則利用存活的數(shù)據(jù)元素和水平校驗(yàn)元素進(jìn)行異或運(yùn)算修復(fù)；若故障的是校驗(yàn)列，則修復(fù)過(guò)程和編碼過(guò)程一致。

文獻(xiàn)［5］詳細(xì)闡述了關(guān)于RDP碼單雙盤(pán)故障時(shí)的修復(fù)過(guò)程，在此不再贅述。RDP碼在p=5時(shí)，假設(shè)磁盤(pán)disk0故障，則需要讀取disk1～disk4中的所有元素（共16個(gè)）進(jìn)行修復(fù)。

傳統(tǒng)的單盤(pán)譯碼方式造成了很多不必要的數(shù)據(jù)讀取開(kāi)銷(xiāo)。Xiang等人［21］提出了混合修復(fù)算法，其主要思想是最大化重疊元素的數(shù)量，該算法同時(shí)使用水平和對(duì)角兩種不同的校驗(yàn)組進(jìn)行單故障修復(fù)以最優(yōu)化磁盤(pán)讀取和平衡磁盤(pán)讀取。由于內(nèi)存的讀取速度遠(yuǎn)快于磁盤(pán)的讀取速度，可以將修復(fù)過(guò)程中重疊的元素在第一次讀取時(shí)存入內(nèi)存中，在后續(xù)修復(fù)過(guò)程中直接從內(nèi)存中讀取重疊元素以修復(fù)其他元素，加快了磁盤(pán)修復(fù)過(guò)程的同時(shí)降低了存儲(chǔ)系統(tǒng)的通信負(fù)載。圖2展示了當(dāng)p=5時(shí)的RDP碼的混合修復(fù)方案，其中條紋背景圖案代表修復(fù)過(guò)程中需要讀取的元素。在故障磁盤(pán)disk0中，數(shù)據(jù)元素d0，0和d2，0采用水平校驗(yàn)進(jìn)行進(jìn)行修復(fù)，而數(shù)據(jù)塊d1，0和d3，0采用對(duì)角校驗(yàn)進(jìn)行修復(fù)，只需讀取12個(gè)元素，相較于原始修復(fù)方式讀取的16個(gè)元素最多可減少25%的修復(fù)讀取開(kāi)銷(xiāo)。雖然混合修復(fù)算法降低了單盤(pán)故障修復(fù)時(shí)的讀取開(kāi)銷(xiāo)，但是對(duì)于雙盤(pán)故障在修復(fù)時(shí)沒(méi)有任何優(yōu)化，依然需要讀取所有存活磁盤(pán)中的所有元素。

2 DRDP碼編碼方案

為了降低RDP碼在單雙盤(pán)故障修復(fù)時(shí)的讀取開(kāi)銷(xiāo)，減少修復(fù)時(shí)間，本文基于局部修復(fù)碼［32］，對(duì)RDP碼進(jìn)行拓展，通過(guò)將部分?jǐn)?shù)據(jù)列按水平線進(jìn)行異或計(jì)算生成一列新的校驗(yàn)列，構(gòu)造了一種具有局部修復(fù)性質(zhì)的陣列碼模型。為進(jìn)行區(qū)分，將RDP碼的水平校驗(yàn)列稱(chēng)為全局水平校驗(yàn)列，新增的校驗(yàn)列稱(chēng)為局部水平校驗(yàn)列。因?yàn)樵摯a具有全局和局部?jī)蓚€(gè)水平校驗(yàn)列，所以命名為DRDP碼（double rows diagonal parity code）。作為RDP碼的拓展碼，DRDP碼也是屬于橫式陣列碼，其條帶由一個(gè)（p-1）×（p+1）的二維陣列構(gòu)成，其中p為大于3的素?cái)?shù)，不同的是DRDP碼在RDP碼的基礎(chǔ)上將第（p-1）/2列數(shù)據(jù)列替換為局部水平校驗(yàn)列，該校驗(yàn)列由前（p-1）/2列數(shù)據(jù)列經(jīng)過(guò)水平線異或計(jì)算得到，其局部水平校驗(yàn)列的編碼公式為

當(dāng)p=7時(shí)，DRDP碼的局部水平校驗(yàn)列編碼過(guò)程如圖3所示。

對(duì)于全局水平校驗(yàn)列，其計(jì)算方式與RDP碼相同，由所有數(shù)據(jù)列和局部水平校驗(yàn)列沿水平線進(jìn)行異或計(jì)算得到，但為了減少異或次數(shù)以降低編碼復(fù)雜度，全局水平校驗(yàn)列可由后（p-3）/2列數(shù)據(jù)列經(jīng)過(guò)水平線異或計(jì)算得到，在后文利用全局水平校驗(yàn)列進(jìn)行修復(fù)時(shí)同上。全局水平校驗(yàn)列的編碼公式為

當(dāng)p=5時(shí)，DRDP碼的全局水平校驗(yàn)列編碼過(guò)程如圖4所示，其中校驗(yàn)元素p5，6可由數(shù)據(jù)元素d5，4和d5，5異或計(jì)算得到。

對(duì)于對(duì)角校驗(yàn)列，其計(jì)算方式與RDP碼相同，已在本文第1.2節(jié)中詳細(xì)闡述。與RDP碼不同的是，DRDP碼對(duì)角校驗(yàn)列的生成同時(shí)涉及到了全局和局部?jī)蓚€(gè)水平校驗(yàn)列。

3 DRDP碼譯碼方案

定義1 局部水平校驗(yàn)集li，i∈［0，p-2］，li為DRDP碼二維陣列的前（p+1）/2列中的元素按水平線進(jìn)行分組得到，li={ai，j|0≤j≤（p-1）/2}。

定義2 全局水平校驗(yàn)集l′i，i∈［0，p-2］，l′i為DRDP碼二維陣列的（p+1）/2～p-1列中的元素按水平線進(jìn)行分組得到的集合，l′i={ai，j|（p+1）/2≤j≤p-1}。

定義3 對(duì)角校驗(yàn)集gj，j∈［0，p-2］，gi為DRDP碼二維陣列的中所有的元素按斜率為“1”的對(duì)角線進(jìn)行分組得到的集合，gj={ai，p∪{ai，r|（i+r） mod p=j，0≤i≤p-2，0≤r≤p-1}}。

由定義1～3可知，當(dāng)p=7時(shí)，如圖3所示，l1由d1，0、d1，1、d1，2和p1，3組成。同理如圖4所示，l′1由d1，4、d1，5和p1，6組成，而g1由d1，0、d0，1、p5，3、d4，4、d3，5、p2，6和p1，7組成。

定理1 DRDP碼的局部水平校驗(yàn)集和全局水平校驗(yàn)集不相交。

證明 按DRDP碼的編碼方式以及參數(shù)p構(gòu)造二維陣列，已知DRDP碼的全局水平校驗(yàn)集在形式上與RDP碼的水平校驗(yàn)集相同，可表示為l′i={ai，j|0≤j≤p-1}，i∈［0，p-2］，因其包含了局部水平校驗(yàn)集li，也可表示為l′i={li∪{ai，j|（p+1）/2≤j≤p-1}}。局部水平校驗(yàn)元素是由li中的數(shù)據(jù)元素通過(guò)異或計(jì)算得出，而全局水平校驗(yàn)元素又是由局部水平校驗(yàn)元素與l′i中的數(shù)據(jù)元素通過(guò)異或計(jì)算得出，故全局水平校驗(yàn)集可表示為l′i={ai，j|（p+1）/2≤j≤p-1}，i∈［0，p-2］，l′i中的元素與局部水平校驗(yàn)集li不相交，證畢。

存儲(chǔ)系統(tǒng)可以預(yù)先知道二維陣列中丟失列的位置和列數(shù)，為保證最佳的修復(fù)效率，需要根據(jù)列出錯(cuò)的數(shù)量和位置，按照不同的方案進(jìn)行修復(fù)。

3.1 單盤(pán)故障修復(fù)

DRDP碼在單磁盤(pán)故障時(shí)可分為三種情況，假設(shè)丟失的列為k，譯碼過(guò)程如下：

a）丟失的列位于前（p-1）/2列，即0≤k≤（p-1）/2。此時(shí)k包含數(shù)據(jù)列與局部水平校驗(yàn)列，其修復(fù)過(guò)程為利用存活的局部水平校驗(yàn)列（第（p-1）/2列）和前（p-1）/2數(shù)據(jù)列通過(guò)水平校驗(yàn)集li修復(fù)所有丟失的元素。單盤(pán)故障修復(fù)讀取開(kāi)銷(xiāo)為（p-1）2/2。修復(fù)公式如下：

b）丟失的列位于（p+1）/2～p-1列，即（p+1）/2≤k≤p-1。此時(shí)k包含數(shù)據(jù)列與全局水平校驗(yàn)列，其修復(fù)過(guò)程為利用存活的全局水平校驗(yàn)列（第p-1列）和后（p-3）/2列數(shù)據(jù)列通過(guò)全局水平校驗(yàn)集l′i修復(fù)所有丟失的元素。單盤(pán)故障修復(fù)讀取開(kāi)銷(xiāo)為[（p-3）（p-1）]/2。修復(fù)公式如下：

c）丟失的列為對(duì)角校驗(yàn)列，即k=p。此時(shí)修復(fù)原理與RDP碼相同，即按式（2）通過(guò)對(duì)角校驗(yàn)列重新編碼來(lái)修復(fù)所有丟失的校驗(yàn)元素。圖5展示了當(dāng)p=7時(shí)DRDP碼在修復(fù)全局校驗(yàn)列時(shí)的讀取開(kāi)銷(xiāo)情況，其中條紋背景圖案代表修復(fù)過(guò)程中需要讀取的元素。與RDP不同的是，該碼具有局部校驗(yàn)列，在修復(fù)過(guò)程中，將部分讀取的元素存入內(nèi)存中，在后續(xù)修復(fù)過(guò)程中需要的元素可由內(nèi)存中已有的元素進(jìn)行異或計(jì)算得到，進(jìn)而減少修復(fù)讀取開(kāi)銷(xiāo)。例如在p=7時(shí)，p3，6可由預(yù)先存儲(chǔ)在內(nèi)存中的d3，4和d3，5異或計(jì)算得到，從而參與全局校驗(yàn)元素p2，7的修復(fù)。單盤(pán)故障修復(fù)讀取開(kāi)銷(xiāo)為（p-2）（p-1）。

3.2 雙盤(pán)故障修復(fù)

定理2 DRDP碼能在雙磁盤(pán)故障后重構(gòu)二維陣列。

證明 DRDP碼是對(duì)RDP碼進(jìn)行拓展后產(chǎn)生的碼，兩者二維陣列的生成形式與規(guī)格相同，DRDP碼在任何磁盤(pán)故障的情況下都可以按照RDP碼的譯碼方案對(duì)數(shù)據(jù)進(jìn)行修復(fù)，故能保證在DRDP碼在雙盤(pán)故障后能重構(gòu)二維陣列，證畢。

DRDP碼在雙磁盤(pán)故障時(shí)可分為五種情況，假設(shè)丟失的兩列為u和v，其中0≤u

a）丟失的兩列均位于前（p-1）/2列，即0≤u

b）丟失的兩列均位于（p+1）/2～p-1列，即（p+1）/2≤u

c）丟失的兩列其中一列位于前（p-1）/2列，另一列位于（p+1）/2～p-1列，即0≤u≤（p-1）/2

當(dāng)p=7時(shí)，以第1和5列數(shù)據(jù)列丟失為例，即u=1，v=5。首先通過(guò)全局水平校驗(yàn)集使用disk4和disk6中的元素修復(fù)disk5中的元素，再使用混合修復(fù)算法通過(guò)局部水平校驗(yàn)集和對(duì)角校驗(yàn)集對(duì)disk1中的元素進(jìn)行修復(fù)。修復(fù)過(guò)程如圖6所示，其中括號(hào)內(nèi)的數(shù)字0代表使用局部水平校驗(yàn)集進(jìn)行修復(fù)、數(shù)字1代表使用全局水平校驗(yàn)集進(jìn)行修復(fù)、數(shù)字2代表使用對(duì)角校驗(yàn)集進(jìn)行修復(fù)。

當(dāng)（p-1）/2為奇數(shù)時(shí)，雙盤(pán)故障修復(fù)讀取開(kāi)銷(xiāo)如下：

當(dāng)（p-1）/2為偶數(shù)時(shí)，雙盤(pán)故障修復(fù)讀取開(kāi)銷(xiāo)如下：

d）丟失的兩列其中一列位于前（p-1）/2列，另一列為對(duì)角校驗(yàn)列，即0≤u≤（p-1）/2，v=p。此時(shí)u包含數(shù)據(jù)列和局部水平校驗(yàn)列，v為對(duì)角校驗(yàn)列，修復(fù)方法如下：首先通過(guò)局部水平校驗(yàn)集li修復(fù)第u列，其修復(fù)過(guò)程與單盤(pán)修復(fù)過(guò)程相同，已在本文第3.1節(jié)中詳細(xì)闡述，對(duì)于對(duì)角校驗(yàn)列v則采用重新編碼的方式來(lái)修復(fù)所有丟失的校驗(yàn)元素。雙盤(pán)故障修復(fù)讀取開(kāi)銷(xiāo)為（p-2）（p-1）。

e）丟失的兩列其中一列位于（p+1）/2～p-1列，另一列為對(duì)角校驗(yàn)列，即（p+1）/2≤u≤p-1，v=p。 此時(shí)u包含數(shù)據(jù)列和全局水平校驗(yàn)列，v為對(duì)角校驗(yàn)列，修復(fù)方法與上一種情況類(lèi)似，不同的是通過(guò)全局水平校驗(yàn)集l′i修復(fù)第u列，其修復(fù)過(guò)程已在本文第3.1節(jié)中詳細(xì)闡述。雙盤(pán)故障修復(fù)讀取開(kāi)銷(xiāo)為（p-2）（p-1）。

3.3 三盤(pán)故障修復(fù)

傳統(tǒng)的RDP碼譯碼方案無(wú)法修復(fù)三盤(pán)故障，DRDP碼三盤(pán)故障修復(fù)的主要思想是利用局部水平校驗(yàn)集或全局水平校驗(yàn)集先修復(fù)1列，將其轉(zhuǎn)換為雙盤(pán)修復(fù)問(wèn)題，雙盤(pán)修復(fù)過(guò)程已在本文第3.2節(jié)中詳細(xì)闡述，在此不再贅述。

定理3 3列丟失的情況下必須先利用局部水平校驗(yàn)集或全局水平校驗(yàn)集優(yōu)先修復(fù)1列，否則會(huì)導(dǎo)致修復(fù)失敗。

證明 當(dāng)丟失3列時(shí)，只要優(yōu)先保證修復(fù)1列即能將三盤(pán)修復(fù)問(wèn)題轉(zhuǎn)換為雙盤(pán)修復(fù)問(wèn)題。由定義1～3可知，對(duì)角校驗(yàn)集中的元素涉及到了二維陣列中的所有列，故在多磁盤(pán)故障時(shí)無(wú)法通過(guò)對(duì)角校驗(yàn)集優(yōu)先修復(fù)1列；而局部水平校驗(yàn)集和全局水平校驗(yàn)集中的元素分別只涉及到了二維陣列中的（p+1）/2列以及（p-1）/2列，故當(dāng)丟失的3列中只有1列涉及到局部水平校驗(yàn)集或全局水平校驗(yàn)集時(shí)，可以通過(guò)式（5）或（6）優(yōu)先修復(fù)1列，將三盤(pán)修復(fù)問(wèn)題轉(zhuǎn)換為雙盤(pán)修復(fù)問(wèn)題，證畢。

假設(shè)丟失的三列分別為u、v和m，其中0≤u

4 理論分析

本章將DRDP碼與RDP碼、LRRDP碼和RDP（p，3）碼從單雙盤(pán)故障讀取開(kāi)銷(xiāo)、編碼復(fù)雜度、譯碼復(fù)雜度和更新復(fù)雜度這幾個(gè)影響陣列碼性能的關(guān)鍵指標(biāo)進(jìn)行比較，分析DRDP碼的優(yōu)點(diǎn)和局限性。

4.1 故障修復(fù)讀取開(kāi)銷(xiāo)

故障讀取開(kāi)銷(xiāo)指在修復(fù)故障磁盤(pán)的過(guò)程中需要讀取的元素?cái)?shù)量。三盤(pán)故障在修復(fù)時(shí)需要讀取所有元素，在這里本文只討論單盤(pán)故障和雙盤(pán)故障情況下的故障修復(fù)讀取開(kāi)銷(xiāo)。關(guān)于DRDP碼的故障修復(fù)讀取開(kāi)銷(xiāo)已在本文第3章中詳細(xì)闡述，單雙盤(pán)故障修復(fù)平均讀取開(kāi)銷(xiāo)如表1和圖7、8所示，相比RDP碼、LRRDP碼和RDP（p，3）碼，DRDP碼在單盤(pán)故障讀取開(kāi)銷(xiāo)分別減少了34.79%～42.11%、9.64%～32.46%、25.42%～33.34%；在雙盤(pán)故障讀取開(kāi)銷(xiāo)減少了11.11%～22.83%。

4.2 編碼復(fù)雜度

4.3 更新復(fù)雜度

4.4 譯碼復(fù)雜度

5 實(shí)驗(yàn)對(duì)比

本章通過(guò)與RDP碼、LRRDP碼和RDP（p，3）碼進(jìn)行對(duì)比實(shí)驗(yàn)來(lái)測(cè)試DRDP碼在真實(shí)應(yīng)用場(chǎng)景下的性能。對(duì)比實(shí)驗(yàn)包括編碼實(shí)驗(yàn)、單盤(pán)故障修復(fù)實(shí)驗(yàn)和雙盤(pán)故障修復(fù)實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境和參數(shù)為：CPU Intel Core i7-13700、內(nèi)存32 GB、固態(tài)硬盤(pán)256 GB×12、CentOS7 64位操作系統(tǒng)、測(cè)試文件大小10 MB、文件分塊大小100 KB。

5.1 編碼實(shí)驗(yàn)

圖13為編碼時(shí)間對(duì)比圖。RDP碼在生成全局校驗(yàn)列和對(duì)角校驗(yàn)列時(shí)均涉及了p-1列元素；LRRDP碼在生成局部水平校驗(yàn)列和全局水平校驗(yàn)列時(shí)分別涉及了（p-1）/2列和（p+1）/2列元素，但是編碼時(shí)異或計(jì)算的次數(shù)與RDP碼相同；RDP（p，3）碼在生成3列校驗(yàn)列時(shí)均需涉及p-1列元素；而DRDP碼在生成局部水平校驗(yàn)列和全局水平校驗(yàn)列時(shí)分別只涉及了（p-1）/2列和（p-3）/2列元素。綜上所述，DRDP碼編碼時(shí)的異或計(jì)算次數(shù)要少于RDP碼、LRRDP碼和RDP（p，3）碼，具體的分析比較過(guò)程已在4.2節(jié)詳細(xì)闡述，從而DRDP碼擁有較低的編碼復(fù)雜度，在一定程度上節(jié)省了編碼時(shí)間，當(dāng)p值偏小時(shí)尤為明顯。相比RDP碼、LRRDP碼和RDP（p，3）碼，DRDP碼分別可減少10.74%～21.75%、8.23%～19.79%、24.89%～32.89%的編碼時(shí)間。

5.2 單盤(pán)故障修復(fù)實(shí)驗(yàn)

圖14為單盤(pán)故障修復(fù)時(shí)間對(duì)比。RDP碼在進(jìn)行單盤(pán)故障修復(fù)時(shí)采用混合修復(fù)算法可降低25%的數(shù)據(jù)讀取量；LRRDP碼通過(guò)構(gòu)造局部校驗(yàn)列縮短了修復(fù)鏈，在對(duì)絕大部分單盤(pán)故障情況進(jìn)行修復(fù)時(shí)只需讀取局部數(shù)據(jù)元素；RDP（p，3）碼在單盤(pán)故障修復(fù)時(shí)通過(guò)正反兩個(gè)對(duì)角校驗(yàn)集間存在重疊的元素來(lái)降低數(shù)據(jù)讀取量；DRDP碼通過(guò)構(gòu)造局部水平校驗(yàn)列并將局部水平校驗(yàn)列參與到全局水平校驗(yàn)列的計(jì)算中，進(jìn)一步縮短了修復(fù)鏈，很大程度上降低了單盤(pán)故障修復(fù)時(shí)間。具體的分析比較過(guò)程已在第4.1節(jié)和4.4節(jié)詳細(xì)闡述。相比RDP碼、LRRDP碼和RDP（p，3）碼，DRDP碼分別可減少25.26%～35.01%、5.45%～7.39%、26.19%～33.06%的單盤(pán)故障修復(fù)時(shí)間。

5.3 雙盤(pán)故障修復(fù)實(shí)驗(yàn)

圖15為雙盤(pán)故障修復(fù)時(shí)間對(duì)比圖。RDP碼在雙盤(pán)故障修復(fù)時(shí)必須要讀取所有的存活元素；LRRDP碼在雙盤(pán)故障修復(fù)時(shí)修復(fù)讀取開(kāi)銷(xiāo)與RDP碼一致，但是異或計(jì)算次數(shù)比RDP碼要少；RDP（p，3）碼在雙盤(pán)故障修復(fù)時(shí)雖然讀取開(kāi)銷(xiāo)和譯碼復(fù)雜度均為最高，但其存在多個(gè)修復(fù)起始點(diǎn)，可以并行修復(fù)丟失的元素；在3.2節(jié)詳細(xì)分析了DRDP碼雙盤(pán)故障的所有情況，并相應(yīng)給出了最優(yōu)的修復(fù)方案，DRDP碼在雙盤(pán)故障修復(fù)時(shí)同時(shí)利用了局部水平校驗(yàn)集和混合修復(fù)算法，降低了雙盤(pán)故障修復(fù)的修復(fù)讀取開(kāi)銷(xiāo)。具體的分析比較過(guò)程已在第4.1節(jié)和4.4節(jié)詳細(xì)闡述。相比RDP碼、LRRDP碼和RDP（p，3）碼，DRDP碼分別可減少18.93%～26.26%、16.04%～29.64%、5.07%～18.76%的雙盤(pán)故障修復(fù)時(shí)間。

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

為了解決當(dāng)前陣列碼難以同時(shí)提升單雙盤(pán)故障修復(fù)效率的問(wèn)題，基于局部修復(fù)碼對(duì)RDP碼進(jìn)行拓展，本文提出了一種局部修復(fù)陣列碼模型——DRDP碼。DRDP碼將部分?jǐn)?shù)據(jù)列進(jìn)行編碼生成局部校驗(yàn)列，再將局部校驗(yàn)列參與到全局校驗(yàn)列的編碼計(jì)算中，從而縮短了修復(fù)鏈的長(zhǎng)度，節(jié)省了故障修復(fù)時(shí)間。針對(duì)不同的故障情況，本文提出了相應(yīng)的修復(fù)方案進(jìn)行修復(fù)，保證了最佳的修復(fù)效率。通過(guò)理論分析得出DRDP碼在具有低編譯碼復(fù)雜度和良好更新效率的同時(shí)，降低了單雙盤(pán)故障修復(fù)讀取開(kāi)銷(xiāo)，并能修復(fù)75%三盤(pán)故障情況。實(shí)驗(yàn)結(jié)果表明相比RDP碼、LRRDP碼和RDP（p，3）碼，DRDP碼節(jié)省了編碼時(shí)間和單雙盤(pán)故障修復(fù)時(shí)間，適用于磁盤(pán)陣列系統(tǒng)以及分布式存儲(chǔ)系統(tǒng)，擁有良好的應(yīng)用前景。但是在存儲(chǔ)利用率上DRDP碼稍顯不足，所以接下來(lái)的工作是在保證陣列碼修復(fù)效率的前提下提高其存儲(chǔ)利用率。

參考文獻(xiàn)：

［1］Blaum M，F(xiàn)arrell P G，Tilborg H C A V.Array codes［J］.IEEE Trans on Information Theory，1998，34（5）：1061-1066.

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

［3］Patterson D A，Giberson G，Katz R H.A case for redundant arrays of inexpensive disks （RAID）［C］//Proc of ACM SIGMOD International Conference on Management of Data.New York：ACM Press，1988：109-116.

［4］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.

［5］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 Press，2004：1-14.

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

［7］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.

［8］羅迅.Lamda碼：一種新的糾雙刪陣列碼［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45（24）：11-13.（Luo Xun.Lamda code：MDS double-erasure correcting array code［J］.Computer Engineering and Applications，2009，45（24）：11-13.）

［9］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.

［10］萬(wàn)武南，索望，陳運(yùn)，等.基于X-RDP 陣列碼的一種數(shù)據(jù)分布策略［J］.通信學(xué)報(bào)，2013，34（S1）：67-75.（Wan Wunan，Suo Wang，ChenYun，et al.Data distribution strategy based on the X-RDP array codes［J］.Journal on Communications，2013，34（S1）：67-75.）

［11］唐聃，楊昊澎，王福超.基于多斜率碼鏈的陣列糾刪碼［J］.計(jì)算機(jī)應(yīng)用，2017，37（4）：936-940.（Tang Dan，Yang Haopeng，Wang Fuchao.Array erasure codes based on coding chains with multiple slopes［J］.Journal of Computer Applications，2017，37（4）：936-940.）

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

［13］Hafner J L.HoVer erasure codes for disk arrays［C］//Proc of International Conference on Dependable Systems and Networks.Piscataway，NJ：IEEE Press，2006：217-226.

［14］Li Mingqiang，Shu Jiwu，Zheng Weimin.GRID codes：strip-based erasure codes with high fault tolerance for storage systems［J］.ACM Trans on Storage，2009，4（4）：1-22.

［15］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 & Distributed Processing with Applications，Big Data & Cloud Computing，Sustainable Computing & Communications，Social Computing & Networking.Piscataway，NJ：IEEE Press，2021：939-946.

［16］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.

［17］Jin Chao，Jiang Hong，F(xiàn)eng Dan，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.

［18］冼嘉倫.基于陣列碼的分布式存儲(chǔ)系統(tǒng)容錯(cuò)技術(shù)研究［D］.深圳：深圳大學(xué)，2020.（Xian Jialun.Research on fault tolerance technology of distributed storage system based on array code［D］.Shenzhen：Shenzhen University，2020.）

［19］Schroseder 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，2007，3（3）：8-es.

［20］楊松霖，張廣艷.糾刪碼存儲(chǔ)系統(tǒng)中數(shù)據(jù)修復(fù)方法綜述［J］.計(jì)算機(jī)科學(xué)與探索，2017，11（10）：1531-1544.（Yang Songlin，Zhang Guangyan.Review of data recovery in storage systems based on erasure codes［J］.Journal of Frontiers of Computer Science and Technology，2017，11（10）：1531-1544.）

［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］Xu Silei，Li Runhui，Lee P P C，et al.Single disk failure recovery for X-code-based parallel storage systems［J］.IEEE Trans on Compu-ters，2013，63（4）：995-1007.

［23］劉文波.基于糾刪碼的單盤(pán)錯(cuò)誤恢復(fù)技術(shù)研究［D］.大連：大連理工大學(xué)，2018.（Liu Wenbo.The research on single disk failure reco-very based on erasure codes［D］.Dalian：Dalian University of Technology，2018.）

［24］朱希康.基于陣列碼的單盤(pán)故障修復(fù)及優(yōu)化問(wèn)題研究 ［D］.天津：河北工業(yè)大學(xué)，2021.（Zhu Xikang.Research on single disk fault repair and optimization based under array coding［D］.Tianjin：Hebei University of Technology，2021.）

［25］來(lái)燃，馮興杰，王晴，等.一種可行的優(yōu)化降級(jí)讀性能RAID-6編碼算法［J］.中國(guó)民航大學(xué)學(xué)報(bào)，2018，36（4）：49-53.（Lai Ran，F(xiàn)eng Xingjie，Wang Qing，et al.Efficient RAID-6 MDS code for degraded reads optimization［J］.Journal of Civil Aviation University of China，2018，36（4）：49-53.）

［26］解崢，王子豪，唐聃，等.低編譯復(fù)雜度的雙容錯(cuò)陣列碼［J］.計(jì)算機(jī)應(yīng)用，2023，43（9）：2766-2774.（Xie Zheng，Wang Zihao，Tang Dan，et al.Double fault tolerant array code with low compilation complexity［J］.Journal of Computer Applications，2023，43（9）：2766-2774.）

［27］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.

［28］蕭楓，唐聃，范迪，等.一種低單盤(pán)故障恢復(fù)開(kāi)銷(xiāo)的局部修復(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.）

［29］Wan Shenggang，Cao Qiang，Xie Changsheng，et al.Code-M：a non-MDS erasure code scheme to support fast recovery from up to two-disk failures in storage systems ［C］//Proc of IEEE/IFIP International Conference on Dependable Systems & Networks.Piscataway，NJ：IEEE Press，2010：51-60.

［30］劉靖宇，牛秋霞，李蕭言，等.基于局部冗余混合編碼的故障快速恢復(fù)方法［J］.計(jì)算機(jī)應(yīng)用，2022，42（4）：1244-1252.（Liu Jingyu，Niu Qiuxia，Li Xiaoyan，et al.Fast failure recovery method based on local redundant hybrid code［J］.Journal of Computer Applications，2022，42（4）：1244-1252.）

［31］Chen Xin，Ma Xiao.Optimized recovery algorithms for RDP（p，3） code ［J］.IEEE Communications Letters，2018，22（12）：2443-2446.

［32］Huang Cheng，Simitci H，Xu Yikang，et al.Erasure coding in windows azure storage［C］//Proc of USENIX Conference on Annual Technical Conference.Berkeley，CA：USENIX Press，2012：15-26.