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

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

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

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

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

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

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

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

1 RDP碼介紹

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

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

1.1 RDP碼編碼過程

RDP碼作為最經(jīng)典的容兩錯MDS陣列碼之一，其條帶由一個（p-1）×（p+1）的二維陣列構(gòu)成，為保證其MDS性質(zhì)，其參數(shù)p為素?cái)?shù)。和EVENODD碼相同，RDP碼對數(shù)據(jù)元素采用水平線（斜率為“0”）和對角線（斜率為“1”）的方式進(jìn)行異或計(jì)算編碼。假設(shè)二維陣列中的每一列代表一個磁盤，首先將原始數(shù)據(jù)按條帶進(jìn)行等量分塊存放在二維陣列的前p-1列，經(jīng)過水平校驗(yàn)生成的校驗(yàn)元素存放在第p列中，而經(jīng)過對角校驗(yàn)生成的校驗(yàn)元素放在第p+1列。水平校驗(yàn)列和對角校驗(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的一個整數(shù)。圖1展示了在p=5時RDP碼的編碼過程，其中白色背景圖案代表該元素是原始數(shù)據(jù)元素，灰色背景圖案代表該元素是校驗(yàn)元素。

1.2 RDP碼譯碼過程

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

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

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

2 DRDP碼編碼方案

為了降低RDP碼在單雙盤故障修復(fù)時的讀取開銷，減少修復(fù)時間，本文基于局部修復(fù)碼［32］，對RDP碼進(jìn)行拓展，通過將部分?jǐn)?shù)據(jù)列按水平線進(jìn)行異或計(jì)算生成一列新的校驗(yàn)列，構(gòu)造了一種具有局部修復(fù)性質(zhì)的陣列碼模型。為進(jìn)行區(qū)分，將RDP碼的水平校驗(yàn)列稱為全局水平校驗(yàn)列，新增的校驗(yàn)列稱為局部水平校驗(yàn)列。因?yàn)樵摯a具有全局和局部兩個水平校驗(yàn)列，所以命名為DRDP碼（double rows diagonal parity code）。作為RDP碼的拓展碼，DRDP碼也是屬于橫式陣列碼，其條帶由一個（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)過水平線異或計(jì)算得到，其局部水平校驗(yàn)列的編碼公式為

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

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

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

對于對角校驗(yàn)列，其計(jì)算方式與RDP碼相同，已在本文第1.2節(jié)中詳細(xì)闡述。與RDP碼不同的是，DRDP碼對角校驗(yàn)列的生成同時涉及到了全局和局部兩個水平校驗(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 對角校驗(yàn)集gj，j∈［0，p-2］，gi為DRDP碼二維陣列的中所有的元素按斜率為“1”的對角線進(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時，如圖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ù)元素通過異或計(jì)算得出，而全局水平校驗(yàn)元素又是由局部水平校驗(yàn)元素與l′i中的數(shù)據(jù)元素通過異或計(jì)算得出，故全局水平校驗(yàn)集可表示為l′i={ai，j|（p+1）/2≤j≤p-1}，i∈［0，p-2］，l′i中的元素與局部水平校驗(yàn)集li不相交，證畢。

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

3.1 單盤故障修復(fù)

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

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

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

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

3.2 雙盤故障修復(fù)

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

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

DRDP碼在雙磁盤故障時可分為五種情況，假設(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時，以第1和5列數(shù)據(jù)列丟失為例，即u=1，v=5。首先通過全局水平校驗(yàn)集使用disk4和disk6中的元素修復(fù)disk5中的元素，再使用混合修復(fù)算法通過局部水平校驗(yàn)集和對角校驗(yàn)集對disk1中的元素進(jìn)行修復(fù)。修復(fù)過程如圖6所示，其中括號內(nèi)的數(shù)字0代表使用局部水平校驗(yàn)集進(jìn)行修復(fù)、數(shù)字1代表使用全局水平校驗(yàn)集進(jìn)行修復(fù)、數(shù)字2代表使用對角校驗(yàn)集進(jìn)行修復(fù)。

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

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

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

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

3.3 三盤故障修復(fù)

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

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

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

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

4 理論分析

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

4.1 故障修復(fù)讀取開銷

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

4.2 編碼復(fù)雜度

4.3 更新復(fù)雜度

4.4 譯碼復(fù)雜度

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

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

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

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

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

圖14為單盤故障修復(fù)時間對比。RDP碼在進(jìn)行單盤故障修復(fù)時采用混合修復(fù)算法可降低25%的數(shù)據(jù)讀取量；LRRDP碼通過構(gòu)造局部校驗(yàn)列縮短了修復(fù)鏈，在對絕大部分單盤故障情況進(jìn)行修復(fù)時只需讀取局部數(shù)據(jù)元素；RDP（p，3）碼在單盤故障修復(fù)時通過正反兩個對角校驗(yàn)集間存在重疊的元素來降低數(shù)據(jù)讀取量；DRDP碼通過構(gòu)造局部水平校驗(yàn)列并將局部水平校驗(yàn)列參與到全局水平校驗(yàn)列的計(jì)算中，進(jìn)一步縮短了修復(fù)鏈，很大程度上降低了單盤故障修復(fù)時間。具體的分析比較過程已在第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%的單盤故障修復(fù)時間。

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

圖15為雙盤故障修復(fù)時間對比圖。RDP碼在雙盤故障修復(fù)時必須要讀取所有的存活元素；LRRDP碼在雙盤故障修復(fù)時修復(fù)讀取開銷與RDP碼一致，但是異或計(jì)算次數(shù)比RDP碼要少；RDP（p，3）碼在雙盤故障修復(fù)時雖然讀取開銷和譯碼復(fù)雜度均為最高，但其存在多個修復(fù)起始點(diǎn)，可以并行修復(fù)丟失的元素；在3.2節(jié)詳細(xì)分析了DRDP碼雙盤故障的所有情況，并相應(yīng)給出了最優(yōu)的修復(fù)方案，DRDP碼在雙盤故障修復(fù)時同時利用了局部水平校驗(yàn)集和混合修復(fù)算法，降低了雙盤故障修復(fù)的修復(fù)讀取開銷。具體的分析比較過程已在第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%的雙盤故障修復(fù)時間。

6 結(jié)束語

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

參考文獻(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］萬武南，索望，陳運(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］冼嘉倫.基于陣列碼的分布式存儲系統(tǒng)容錯技術(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］楊松霖，張廣艷.糾刪碼存儲系統(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］劉文波.基于糾刪碼的單盤錯誤恢復(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］朱希康.基于陣列碼的單盤故障修復(fù)及優(yōu)化問題研究 ［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］來燃，馮興杰，王晴，等.一種可行的優(yōu)化降級讀性能RAID-6編碼算法［J］.中國民航大學(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ù)雜度的雙容錯陣列碼［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］蕭楓，唐聃，范迪，等.一種低單盤故障恢復(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.）

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