存儲系統中的局部修復陣列碼模型

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

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

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

中圖分類號：TP333.3?? 文獻標志碼：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 引言

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

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

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

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

1 RDP碼介紹

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

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

1.1 RDP碼編碼過程

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

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

1.2 RDP碼譯碼過程

傳統的RDP碼在面對單盤故障的情況時，若故障的是數據列則利用存活的數據元素和水平校驗元素進行異或運算修復；若故障的是校驗列，則修復過程和編碼過程一致。

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

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

2 DRDP碼編碼方案

為了降低RDP碼在單雙盤故障修復時的讀取開銷，減少修復時間，本文基于局部修復碼［32］，對RDP碼進行拓展，通過將部分數據列按水平線進行異或計算生成一列新的校驗列，構造了一種具有局部修復性質的陣列碼模型。為進行區分，將RDP碼的水平校驗列稱為全局水平校驗列，新增的校驗列稱為局部水平校驗列。因為該碼具有全局和局部兩個水平校驗列，所以命名為DRDP碼（double rows diagonal parity code）。作為RDP碼的拓展碼，DRDP碼也是屬于橫式陣列碼，其條帶由一個（p-1）×（p+1）的二維陣列構成，其中p為大于3的素數，不同的是DRDP碼在RDP碼的基礎上將第（p-1）/2列數據列替換為局部水平校驗列，該校驗列由前（p-1）/2列數據列經過水平線異或計算得到，其局部水平校驗列的編碼公式為

當p=7時，DRDP碼的局部水平校驗列編碼過程如圖3所示。

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

當p=5時，DRDP碼的全局水平校驗列編碼過程如圖4所示，其中校驗元素p5，6可由數據元素d5，4和d5，5異或計算得到。

對于對角校驗列，其計算方式與RDP碼相同，已在本文第1.2節中詳細闡述。與RDP碼不同的是，DRDP碼對角校驗列的生成同時涉及到了全局和局部兩個水平校驗列。

3 DRDP碼譯碼方案

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

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

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

由定義1～3可知，當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碼的局部水平校驗集和全局水平校驗集不相交。

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

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

3.1 單盤故障修復

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

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

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

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

3.2 雙盤故障修復

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

證明 DRDP碼是對RDP碼進行拓展后產生的碼，兩者二維陣列的生成形式與規格相同，DRDP碼在任何磁盤故障的情況下都可以按照RDP碼的譯碼方案對數據進行修復，故能保證在DRDP碼在雙盤故障后能重構二維陣列，證畢。

DRDP碼在雙磁盤故障時可分為五種情況，假設丟失的兩列為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

當p=7時，以第1和5列數據列丟失為例，即u=1，v=5。首先通過全局水平校驗集使用disk4和disk6中的元素修復disk5中的元素，再使用混合修復算法通過局部水平校驗集和對角校驗集對disk1中的元素進行修復。修復過程如圖6所示，其中括號內的數字0代表使用局部水平校驗集進行修復、數字1代表使用全局水平校驗集進行修復、數字2代表使用對角校驗集進行修復。

當（p-1）/2為奇數時，雙盤故障修復讀取開銷如下：

當（p-1）/2為偶數時，雙盤故障修復讀取開銷如下：

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

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

3.3 三盤故障修復

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

定理3 3列丟失的情況下必須先利用局部水平校驗集或全局水平校驗集優先修復1列，否則會導致修復失敗。

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

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

4 理論分析

本章將DRDP碼與RDP碼、LRRDP碼和RDP（p，3）碼從單雙盤故障讀取開銷、編碼復雜度、譯碼復雜度和更新復雜度這幾個影響陣列碼性能的關鍵指標進行比較，分析DRDP碼的優點和局限性。

4.1 故障修復讀取開銷

故障讀取開銷指在修復故障磁盤的過程中需要讀取的元素數量。三盤故障在修復時需要讀取所有元素，在這里本文只討論單盤故障和雙盤故障情況下的故障修復讀取開銷。關于DRDP碼的故障修復讀取開銷已在本文第3章中詳細闡述，單雙盤故障修復平均讀取開銷如表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 編碼復雜度

4.3 更新復雜度

4.4 譯碼復雜度

5 實驗對比

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

5.1 編碼實驗

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

5.2 單盤故障修復實驗

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

5.3 雙盤故障修復實驗

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

6 結束語

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

參考文獻：

［1］Blaum M，Farrell 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］.計算機工程與應用，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］萬武南，索望，陳運，等.基于X-RDP 陣列碼的一種數據分布策略［J］.通信學報，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］.計算機應用，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，Feng 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］冼嘉倫.基于陣列碼的分布式存儲系統容錯技術研究［D］.深圳：深圳大學，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］楊松霖，張廣艷.糾刪碼存儲系統中數據修復方法綜述［J］.計算機科學與探索，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］劉文波.基于糾刪碼的單盤錯誤恢復技術研究［D］.大連：大連理工大學，2018.（Liu Wenbo.The research on single disk failure reco-very based on erasure codes［D］.Dalian：Dalian University of Technology，2018.）

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

［25］來燃，馮興杰，王晴，等.一種可行的優化降級讀性能RAID-6編碼算法［J］.中國民航大學學報，2018，36（4）：49-53.（Lai Ran，Feng 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］解崢，王子豪，唐聃，等.低編譯復雜度的雙容錯陣列碼［J］.計算機應用，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］蕭楓，唐聃，范迪，等.一種低單盤故障恢復開銷的局部修復碼［J］.計算機工程與應用，2018，54（18）：66-73.（Xiao Feng，Tang Dan，Fan Di，et al.Local repairable code with low single disk failure recovery overhead ［J］.Computer Engineering and Applications，2018，54（18）：66-73.）

［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］劉靖宇，牛秋霞，李蕭言，等.基于局部冗余混合編碼的故障快速恢復方法［J］.計算機應用，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.