一種基于多層次校驗的低恢復成本糾刪碼

鄧文杰 洪鐵原 唐聃 王燮

摘 要：隨著糾刪碼在分布式存儲系統中的實際應用，糾刪碼為存儲系統提供了更加優秀的存儲效率，但當節點丟失時，相較于傳統副本技術更多的網絡傳輸帶寬開銷成為了造成系統性能瓶頸的關鍵因素。為了解決MDS編碼高帶寬開銷對系統性能的影響，一類新型編碼方案——分組碼被應用在分布式存儲系統中，相較于傳統MDS編碼能夠有效地降低節點修復時的數據傳輸量，從而減少網絡帶寬需求。在Pyramid分組碼的基礎上進行層次擴展，提出一種HLRC（hierarchical local repair codes）糾刪碼。HLRC相較于LRC引入了層次編碼模型，將原始數據塊構建為編碼矩陣，根據層次進行分別編碼，生成包含數據塊范圍不同的局部校驗塊；每個層次包含的數據塊數量不同，可以保證修復節點時的低修復成本，同時還擁有較高的存儲效率。HLRC相較于Pyramid擁有額外的校驗塊冗余，能夠降低校驗塊出錯和多節點出錯時的恢復開銷。在基于Ceph的分布式存儲系統中的實驗結果表明，HLRC與Pyramid等分組碼相比，單節點修復開銷最高可降低48.56%，多節點修復開銷最高可降低25%。

關鍵詞：糾刪碼；分組碼；層次編碼；帶寬開銷；恢復成本

中圖分類號：TP391?? 文獻標志碼：A??? 文章編號：1001-3695（2024）05-023-1441-07

doi： 10.19734/j.issn.1001-3695.2023.08.0399

Low recovery-overhead erasure codes based on multi-hierarchical check

Abstract：With the practical application of erasure codes in distributed storage systems， erasure codes provide better storage efficiency for storage systems， but when nodes are lost， more network transmission bandwidth overhead compared with traditional replica technology becomes a key factor causing system performance bottlenecks. In order to solve the impact of high bandwidth overhead of MDS coding on system performance， a new type of coding scheme， packet coding， is applied in distri-buted storage systems. Compared with traditional MDS coding， it can effectively reduce the amount of data transmission during node repairing， thus reducing the network bandwidth demand. This paper proposed a HLRC（hierarchical local repair codes） based on the hierarchical expansion of Pyramid codes. HLRC introduced a hierarchical coding model compared to LRC， which constructed the original data blocks as a coding matrix， and coded according to the hierarchical levels to generate local checksum blocks with different ranges of data blocks. Each hierarchy contained a different number of data blocks， which ensured low repair cost and high storage efficiency when repairing nodes. HLRC had additional checksum block redundancy compared to Pyramid codes， which reduced the recovery overhead in the event of checksum block errors and multi-node errors. Experimental results in a Ceph-based distributed storage system show that HLRC can reduce single-node repair overhead by up to 48.56% and multi-node repair overhead by up to 25% compared to Pyramid codes and other packet codes.

Key words：erasure code; group repair codes; hierarchical coding; bandwidth overhead; recovery overhead

0 引言

在當今數字化時代，海量數據的存儲和處理已經成為一項重要且具有挑戰性的任務。分布式存儲系統［1～3］作為一種有效的數據管理和存儲方案，被廣泛應用于云計算、大數據分析和分布式計算等領域。然而，這些系統面臨著諸多挑戰，如節點故障、網絡延遲和數據丟失等。

糾刪碼（erasure code）［4］是一種高效的冗余編碼方案，用于在分布式存儲系統中實現數據的冗余和容錯。與傳統的副本技術［5］不同，糾刪碼可以通過增加冗余數據，以較低的存儲代價提供更強的容錯能力。在分布式存儲系統中，數據通常會被劃分為多個數據塊，并分布存儲在不同的節點上，以實現數據的冗余備份和高可靠性。當某個節點發生故障或數據丟失時，糾刪碼可以通過冗余數據恢復丟失的數據塊，而無須訪問原始數據所在的節點。這種冗余和恢復的能力使得分布式存儲系統能更好地應對節點故障、數據丟失等問題。

具備MDS性質的RS碼［6］等糾刪碼擁有理論最優的存儲效率，同時能夠提供較好的容錯能力，但缺點在于節點出錯進行數據恢復時對網絡帶寬的占用過高。在分布式存儲系統中，由于其易擴展的特性，網絡帶寬相較于存儲空間而言更為珍貴，所以此類編碼很容易造成系統性能的瓶頸［7］。

陣列碼作為糾刪碼的另外一個分支，其主要思想是將條帶內的數據塊生成一個編碼陣列，通過陣列進行編碼生成校驗塊。其優點是計算簡單，且在以節點為出錯單位時，大部分的陣列碼都為MDS編碼。現階段主流的陣列碼有EVENODD碼［8］、DRDP碼［9］等。相較于傳統MDS編碼，其編譯碼都是基于簡單的XOR操作，所以計算簡單且高效，編譯碼過程也易于實現。但是依然存在傳統MDS編碼的缺點，在節點出錯時需要讀取的數據量非常大，對網絡帶寬造成相當大的挑戰，容易引起系統的性能瓶頸。同時LDPC［10］編碼方案采用了圖結構進行編碼，修復開銷優秀，但其基于Tanner圖和概率的構造方式使其更適合在信道編碼中使用。Tu等人［11］提出的DDUC碼實現了更新和解碼的解耦，從而提高了系統的并發性能；Zhang等人［12］提出的SA-RSR算法能夠加速異或類糾刪碼單節點故障恢復。

根據現階段研究表明，分布式存儲系統中90%以上的節點丟失為單節點丟失［13］，同時為了應對節點修復時網絡帶寬占用高這一挑戰，研究人員提出了許多解決方案，其中之一就是分組碼。分組碼作為一種糾刪碼方案，具有在分布式存儲系統中提供高可靠性和高效性的潛力。分組碼的主要思想是將數據塊分成多個組，并為每個組計算冗余信息，以實現錯誤檢測和糾正。與MDS碼相比，在面臨節點故障時具備較低的修復成本。現階段主流的分組碼有LRC［14］、Pyramid碼［15］、DLRC［16］、TLRC［17］等。其中，LRC最先提出將數據塊分組，通過分組編碼的思想降低單節點修復時需要讀取的節點數目，從而大幅降低修復時的帶寬需求；Pyramid碼提供了多層次的分組編碼思想，將局部校驗塊的類別按照實際需要來進行調整，更能夠適應不同大小的存儲系統需要；DLRC提出重疊編碼的思想，讓數據塊分組時，不同的組內包含的數據塊可以有一定的重疊，使得存儲效率有較大提升；TLRC將全局校驗塊和數據塊一起納入到局部校驗塊的生成過程中，使得全局校驗塊丟失時修復成本也較低。之后又提出了多種基于交叉編碼的分組碼，例如，SHEC［18］雖然容錯能力優秀，但修復開銷較大；GRC［19］采用將條帶分組并增加局部校驗塊的思想來降低多節點修復開銷；RGRC［20］通過旋轉編碼的編碼方式將多個條帶組合成條帶集，進而減少修復成本。

分布式存儲系統相較于傳統集中式存儲系統需要進行更多的數據遷移，現階段主流的MDS糾刪碼方案在修復數據時需要較大的網絡帶寬開銷，導致網絡帶寬經常成為系統性能的瓶頸，同時在分布式存儲系統中大部分的節點丟失是單節點丟失。目前的糾刪碼方案研究僅限于修復開銷和存儲效率，對于同時提高單節點修復效率和存儲效率的研究較少。針對以上問題，本文結合陣列碼的陣列化思想提出層次局部修復碼HLRC（hierarchical local repair codes）。其主要的思想是在編碼時將數據塊和全局塊進行陣列化，通過編碼陣列生成不同層次的局部校驗塊，在保證優秀的單節點修復性能的同時，為系統提供可觀的容錯能力，在分布式存儲系統之中有良好的使用前景。

1 相關工作

1.1 RS編碼

RS（n，k）碼是一種具備MDS性質的編碼，其計算都在GF（2w）上完成，主要思想是將文件拆分成數據塊再進行條帶化，每個條帶內包含k個數據塊D=（d1，d2，…，dk），通過與生成矩陣G相乘即可得到編譯后的碼字c=（c1，c2，…，cn），其中前k位為數據位，所以其為系統MDS碼。生成矩陣的構造如式（1）所示，其中a為GF（2w）的元素。

當數據丟失時，只要丟失節點數x滿足條件1≤x≤n－k，無論丟失多少節點數都可以通過讀取所有的剩余數據塊來進行修復操作，所以容錯能力高但修復效率較為低下。

1.2 Pyramid編碼

Pyramid（n，k）最先提出層次結構編碼思想，其主要思想是將數據塊劃分為不同的層次，為每個不同的層次生成不同類型的局部校驗塊，所以可以更靈活地調整編碼方案。圖1展示了Pyramid（20，12）的編碼結構。

其中每個校驗塊的生成都是基于MDS編碼，在本文中MDS編碼一般指RS碼。圖中Pyramid編碼將數據塊劃分為三層次，第一層長度為3，第二層長度為6，第三層為全局校驗塊。用di代表當前條帶內第i個數據塊，pi表示當前條帶內第i個子局部校驗塊，p′i表示當前條帶內第i個局部校驗塊，p″i表示當前條帶內第i個全局校驗塊。pi、p′i、p″i的構造方式如式（2）～（4）所示，其中r為全局校驗塊個數，li為第i層分組的分組個數。

Pyramid碼的層次結構使其能夠在擁有優秀的單節點修復開銷的同時還兼顧一定的存儲效率，但其缺點在于所有的全局校驗塊以及高層次校驗塊都沒有添加額外的冗余手段，導致其多節容錯能力不足，同時當丟失全局校驗塊或者高層次校驗塊時修復成本依然很高。

2 HLRC的設計

2.1 HLRC基礎概念

本節對HLRC涉及使用的相關符號進行解釋，其中HLRC（k， c， m， r， s）使用的符號具體含義如表1所示。

為了更好進行描述，本文定義以下概念：

定義1 編碼陣列。將當前條帶的數據塊進行陣列化后的數據布局。

定義2 效率優先局部校驗塊。當前的編碼陣列中第一層級的局部校驗塊，與Pyramid碼類似，HLRC編碼時也會產生不同層級的局部校驗塊，其中層級越低，編碼組內的數據塊越少。

定義3 存儲優先局部校驗塊。當前的編碼陣列中第二層級的局部校驗塊，其編碼時組內數據塊相較于第一層范圍更廣，存儲效率也就更高。

定義4 校驗全局校驗塊。當前條帶中編碼范圍為所有局部校驗塊的校驗塊，其作用是為局部校驗塊提供額外的容錯，能夠為編碼方案提供更好的容錯能力和多節點修復性能。

定義5 數據全局校驗塊。編碼矩陣中編碼范圍涵蓋所有數據塊的校驗塊，其主要作用是滿足編碼的容錯性能需要。

定義6 修復成本。在本文中如沒有特別指定，修復成本通常指定為節點恢復時讀取和傳輸的總數據量。

2.2 HLRC編碼

編碼流程一般分為四個步驟，分別對應的是四個不同類型的校驗塊的生成。首先是數據全局校驗塊的生成，對條帶內k個數據塊進行編碼操作，生成r個數據全局校驗塊，其中各個參數需要滿足k+r+c≤c2。

a）進行數據全局校驗塊p=（p1，p2，…pr）的生成。定義矩陣GGlobal是一個r×k階矩陣，其構造如式（5）所示；同時在所有校驗塊的編碼中，a為GF（2w）上的元素，其構造方式如式（6）所示，其中任意兩個g互異，且后續的構造方式也與a（i， j）構造方式一致。

通過GGlobal可以計算得到對應的數據全局校驗塊p，具體的計算流程如式（7）所示。

b）進行效率優先局部校驗塊p′=（p′1，p′2，…，p′c）的生成。定義矩陣GEF是一個c×m階矩陣，構造如式（8）所示。數據矩陣DEF是一個m×c階矩陣，其中di， j代表編碼陣列中位于第i行第j列的數據塊，構造如式（9）（10）所示。

通過GEF計算可以得到包含c個效率優先局部校驗塊p′的矩陣，取對角線元素即可得到c個效率優先局部校驗塊，計算流程如式（11）所示。

c）進行存儲優先局部校驗塊p″=（p″1，p″2，…，p″m）的生成。定義矩陣GSF是一個m×c階矩陣，數據矩陣DSF是一個c×m階的矩陣，如式（12）～（14）所示。

通過GPGlobal計算可以得到m個存儲優先局部校驗塊p″。

d）對于校驗全局校驗塊p可以通過式（15）計算。

2.3 HLRC解碼

HLRC的解碼方式主要與丟失節點的數量與參與解碼的校驗塊有關，可以根據丟失節點的數量將錯誤分為兩類丟失錯誤：單節點丟失和丟失節點數大于1的多節點丟失。其中單節點修復擁有三種解碼方法：效率優先解碼、容錯優先解碼和校驗塊解碼，其分別對應著三類不同校驗塊參與解碼的方式。

2.3.1 單節點修復

對于單節點出錯，若出錯節點derrorp″，derrorp，設出錯節點位于原編碼陣列中第n行第j列，且不屬于存儲優先局部校驗塊。則可使用其對應的效率優先局部校驗塊分組內的數據進行解碼，可以以最優的解碼效率盡可能快速高效地修復錯誤。這類解碼方式稱為效率優先解碼，如圖2所示，具體修復步驟如下：

a）確定丟失節點所對應的效率優先局部校驗塊p′j。

b）得到p′j的編碼方程，如式（16）所示。

c）通過p′j的編碼方程以及組內的數據塊，通過式（17）進行解碼，得到丟失節點derror。

a）確定丟失節點在原編碼陣列中對應的局部校驗塊p″n。

b）按照式（18）確定p″n的原編碼方程。

c）通過p″j的編碼方程以及組內的數據塊，通過式（19）進行解碼，得到丟失節點derror。

若出錯節點為derror∈（p′∪p″∪p），即出錯節點為任意一個局部校驗塊，則可使用其對應的校驗全局校驗塊分組內的數據進行解碼。這一流程被稱為校驗塊解碼，如圖4所示，具體步驟如下：

a）確定丟失節點在原編碼陣列中對應的第x個校驗全局校驗塊px。

b）按照式（20）確定px的原編碼方程。

c）通過px的編碼方程以及組內的數據塊，通過式（21）（22）進行解碼，得到丟失節點derror。

表2為LRC（k，l，r）、DLRC（k，m，n，l）、HLRC（k，c，m，r，s）以及TLRC（k，m，s，x，r）的理論單節點修復開銷。

2.3.2 多節點修復

定理1 設丟失節點個數為x，當擁有x個與丟失的數據塊有關聯的校驗塊時則能夠修復該錯誤。

證明 當擁有x個校驗塊，意味著能夠生成x個帶有未知塊數據的校驗方程。在2.2節編碼時，每一個校驗塊生成時的生成矩陣內的gi都是兩兩互異的，且每一組方程的構成都按照RS碼編碼流程。所以在足夠大的GF（2w）中，條帶內每一個校驗方程之間都是線性無關的。將x個校驗方程組成校驗方程組可以得到線性方程組Ax=b，由于每一個校驗方程線性兩兩無關，可以推出系數矩陣A為滿秩，則Ax=b的秩滿足以下條件：r（A）=r（A，b）=x，線性方程組能夠得到一個唯一解，則該錯誤可以修復。

本文提出一種效率最優的多節點修復算法，其基本思想就是首先使用修復開銷最低的效率優先單節點修復算法來修復丟失節點中可以直接被修復的節點；再添加剩余節點的效率優先局部校驗塊編碼方程至解碼方程組；然后添加其他相關編碼方程直至滿足定理1中的解碼條件r（A）=r（A，b）=x；最后聯立方程組進行解碼，即可實現修復開銷最低的多節點修復。具體流程如圖5所示。

下面以HLRC（11，4，3，1，1）為例來展示其編碼過程，單節點修復過程以及效率最優多節點修復算法的執行過程。HLRC（11，4，3，1，1）的布局如圖6所示。

通過本章的HLRC編碼算法可以計算得到所有校驗塊，總體的生成矩陣G如式（23）所示。

通過圖6可以看出，對于每一部分的校驗塊而言，其計算復雜度以及需要的數據塊都不同。效率優先局部校驗塊擁有最優秀的計算性能，其計算只需要三個數據塊，在保證少數節點可靠性的同時擁有優秀的修復性能。對于存儲優先校驗塊而言，其擁有較效率優先校驗塊更優秀的容錯性能，僅需四個額外的冗余空間即可為所有數據塊提供容錯，所以它能在效率優先校驗塊無法恢復錯誤時提供額外的輔助。全局校驗塊和校驗全局校驗塊分別為所有數據塊和所有局部校驗塊提供最基礎的容錯能力。

對于單節點出錯，若出錯節點derrorp″，derrorp，例如此處出錯節點為d1，1，則優先使用效率優先修復，通過局部校驗塊p′1的修復方程，只需讀取d2，1、d3，1、p′1三個節點數據即可恢復丟失節點d1，1。此類型錯誤修復代價最小，且占總單節點錯誤概率的80%。若出錯節點derror∈p″，例如此處假設出錯節點為p″1，則優先使用存儲優先解碼，通過存儲優先局部校驗塊p″1的修復方程，只需讀取d1，1、d1，2、d1，3、d1，4節點數據即可恢復丟失節點p″1。此類型錯誤修復代價更大，但只占總單節點錯誤概率的15%。若出錯節點為derror∈p，則需要通過所有局部校驗塊聯立進行解碼，是修復代價最高的單節點錯誤。但由于其個數較少，只占總概率的5%，所以其高代價可以被忽略。

對于多節點出錯，則按照效率最優的多節點修復算法的流程對其進行修復。設出錯節點為d1，1、d1，2、d1，3、d2，1、d2，2、d2，3，則算法開始尋找每一個節點修復性能最高的效率優先校驗塊p′1、p′2、p′3。再尋找每個節點對應的存儲優先校驗塊p″1、p″2，最后使用數據全局校驗塊p1。一共可以得到六個線性無關的編碼方程，通過定理1判定后即可修復該多節點錯誤。

3 實驗結果

本文實驗主要在基于Ceph的分布式糾刪碼測試平臺上對HLRC以及其他糾刪碼進行部署并進行相關的性能比較，以便能夠得到最真實的實驗結果。

3.1 實驗環境

Ceph是一個大型可靠的分布式存儲系統，本糾刪碼測試實驗平臺基于Ceph的Pacific（16.2.13）版本搭建，其主要構件有Monitor和OSD。OSD為數據節點，負責存放數據以及數據的管理，其中分為Primary OSD主數據節點和OSD普通數據節點，系統基于其現有框架進行擴展糾刪碼OSD來添加不同的糾刪碼方案。Monitor負責管理數據節點以及與客戶端交互，具體結構如圖7所示。

在圖7所示的分布式實驗平臺上，對HLRC（k， c， m， r， s）算法進行了實現與應用，其具體的實現流程如下：a）在分布式存儲系統之中將目標文件拆分為若干個條帶，每個條帶內包含k個數據塊，通過2.2節的編碼算法得到（c+m+r+s）個校驗塊；b）將條帶內每個數據塊依次放置在節點之中，具體的數據布局如圖8所示；c）循環步驟a）b）直到目標文件編碼完畢；d）當系統出現節點失效時，通過2.3節的解碼算法得到最優的解碼方案，通過條帶內其他校驗塊的輔助，計算得到丟失數據塊，循環步驟d）直到丟失節點恢復完畢。

Ceph的OSD往往采用三副本技術進行數據冗余，本實驗平臺在原生Ceph中添加HLRC OSD和其他對比糾刪碼OSD，以便更方便快捷地得到準確實驗數據。

3.2 容錯能力

容錯能力是指糾刪碼能夠糾正的錯誤數量，在分布式存儲系統中代表其可以糾正的最大丟失節點數。糾刪碼的容錯能力是存儲系統非常重要的一項參數。圖9主要展示了RGRC（24，11）、HLRC（13，7，2，1，1）、HLRC（13，5，3，2，1）和HLRC（13，5，3，3，1）四種不同編碼方案的多節點容錯能力。其橫坐標表示當前丟失的節點個數，縱坐標表示當前丟失節點數情況下的修復概率。

對于四個不同參數的HLRC其各自的額外存儲空間分別為11、11、11、13。同時對比HLRC（13，7，2，1，1）、HLRC（13，5，3，2，1）可以看出，在相同開銷的情況下不同的參數以及不同的編碼布局其修復效率也會不同。雖然兩個編碼方案都使用了11個額外存儲空間，但是編碼陣列有所不同，后者編碼布局更為接近正方形，擁有更加優秀的修復效率，所以HLRC能夠提供更為靈活的編碼方式，可以滿足更多的差異化需求。HLRC（13，5，3，3，1）可以通過增加少量冗余節點的方式達到相比之下最優秀的修復效率。但總體來看，不同HLRC的多節點容錯能力都非常優秀，都能達到95%以上的修復率。

3.3 單節點修復開銷

當存活節點越多時，系統出現節點故障發生數據丟失的概率最高，所以單節點出錯是存儲系統中面臨的最為常見的錯誤。單節點修復性能就能很大程度地決定分布式存儲系統的總體穩定性和可靠性，也是對于糾刪碼方案而言最為關鍵的性能指標之一。本節對RS（24，12）、Pyramid（24，12）、LRC（12，6，6）、DLRC（12，6，3，6）以及HLRC（12，7，2，2，1）（圖中用H1標注）、HLRC（12，5，3，2，1）（圖中用H2標注）、RGRC（24，12）進行了單節點平均修復開銷的比較，結果如圖10所示。

在相同的存儲開銷下，HLRC兩個不同參數的編碼方案提供了最優秀的平均單節點修復開銷。其中HLRC（12，7，2，2，1）平均每一個單節點修復僅僅只需要額外的2.7個輔助節點即可完成；HLRC（12，5，3，2，1）也只需要3.458個輔助節點，相較于其他編碼方案都有一定的優勢。

在存儲系統中，本節使用RS（24，12）、Pyramid（24，12）、

LRC（12，6，6）、DLRC（12，6，3，6）、HLRC（12，7，2，2，1）（圖中用H1標注）、HLRC（12，5，3，2，1）（圖中用H2標注）、RGRC（24，12）七種不同的編碼方案分別對七個大小不同的文件進行編碼，文件的大小對應為圖11中的橫坐標。最后統計出七種不同的編碼方案中每一次的單節點修復開銷，具體的實驗結果如圖11所示。

由圖11可以看出，使用HLRC進行編碼的兩種方案對各個大小的文件都擁有較低的單節點修復開銷，對比LRC、DLRC和Pyramid碼都擁有更加優秀的單節點修復性能。其中HLRC（12，7，2，2，1）相較于RGRC的修復開銷降低了11.66%，相較于Pyramid碼的修復開銷降低了39.23%，相較于LRC的修復開銷降低了40%，相較于DLRC降低了48.56%，相較于RS降低了77.5%。

3.4 多節點修復開銷

分布式存儲系統中，多節點出錯的可能雖然遠小于單節點出錯的可能，但依然是系統不穩定的因素之一。HLRC使用效率最優多節點修復算法來實現對多節點出錯的恢復，使其在多節點恢復效率上依然擁有不錯的能力，能夠保證系統的可靠性。本節對Pyramid（24，12）、LRC（12，6，6）、DLRC（12，6，3，6）、

RGRC（24，12）以及HLRC（12，7，2，2，1）進行了部署和對比，具體結果如圖12所示。

由圖12可以看出，HLRC擁有較為優秀的多節點修復能力，在丟失節點數較少時，修復開銷相較于其他方案更加優秀。在丟失3節點時，HLRC的多節點修復開銷相較于RGRC、Pyra-mid碼、DLRC和LRC分別減少了15.07%、18.9%、25.1%和22.4%。在丟失4節點時，HLRC的多節點修復開銷相較于RGRC、Pyramid碼、DLRC和LRC分別減少了5.90%、11.7%、16.9%和15.1%。即使在丟失5個節點時相較于三個其他編碼方案也平均提升了6.61%。

在實際的測試環境中，本節使用RGRC（24，12）、（24，12）Pyramid、LRC（12，6，6）、DLRC（12，6，3，6）、HLRC（12，7，2，2，1）五種編碼方案：分別對四個大小不同的文件進行了編碼。最后統計在五種不同的編碼方案中每一次的4節點平均修復開銷，具體的實驗結果如圖13所示。

由圖13可以看出，在實際的分布式環境之下，HLRC在不同的文件大小下，都擁有優秀的多節點修復開銷。同時隨著編碼文件的變大，修復開銷優勢更大。

3.5 存儲效率

存儲效率是糾刪碼方案中較為關鍵的指標之一，其決定了編碼方案實際存儲的數據占用空間占總使用空間的比例，其比例越大，代表存儲效率越高。圖14反映了HLRC（14，5，3，1，1）、RGRC（12，7）、（12，10）Pyramid、LRC（16，8，2）、DLRC（14，2，4，8）以及RS（14，10）六種不同編碼方案的存儲效率。

根據圖14可以看出，HLRC相較于RS和LRC犧牲了少許的存儲效率，其中與LRC的存儲效率相差約3.2%，但HLRC提供了更加優秀的節點修復性能和更低的節點修復開銷。所以這些少許額外開銷是可忽略不計的。相較于Pyramid碼和DLRC、HLRC、RGRC擁有相近的容錯能力，更加優秀的單節點修復性能，同時還相較于Pyramid碼提高了3.79%的存儲效率。總體來看，HLRC的存儲效率處在可接受的范圍內。

3.6 實驗數據分析

HLRC的優勢主要集中在單節點修復成本上，在少量節點丟失時修復成本依然優秀。在單節點修復開銷上，HLRC相較于Pyramid碼的修復開銷降低了39.23%，相較于LRC的修復開銷降低了40%，相較于DLRC降低了48.56%，相較于RS降低了77.5%，都擁有相當大的優勢。同時在多節點修復開銷上也有一定的優勢，根據實驗數據表明，HLRC在少量節點時丟失擁有較好的修復開銷，隨著丟失節點的增多，修復開銷優勢隨之降低。這一特性和分布式存儲系統的故障規律非常契合，所以其應用在分布式存儲系統中用于降低修復開銷具有一定的優勢。

4 結束語

根據研究表明存儲系統中約90%的數據丟失是單節點丟失［13］，。本文提出的針對少量節點丟失進行優化的層次編碼方案HLRC可以更好地保證分布式存儲系統中數據的可靠性。HLRC擁有靈活的編碼方式，在保證容錯能力和存儲效率的同時，提供更加高效低開銷的少數節點出錯修復能力。HLRC能夠通過調整編碼參數來改變編碼時的布局，從而能夠讓HLRC在相同的存儲開銷情況下擁有不同的容錯能力和修復開銷，這樣便能更好地適應分布式存儲系統中不同的存儲需求。但如何權衡編碼參數來自適應地讓分布式存儲系統中容錯能力和修復開銷達到理論上最平衡的狀態，還需后續的進一步研究。

參考文獻：

［1］Shvachko K，Kuang H，Radia S，et al. The Hadoop distributed file system ［C］// Proc of the 26th Symposium on Mass Storage Systems and Technologies. Piscataway，NJ： IEEE Press，2010： 1-10.

［2］Weil S A，Brandt S A，Miller E L，et al. Ceph： a scalable，high-performance distributed file system ［C］// Proc of the 7th Symposium on Operating Systems Design and Implementation. Berkeley，CA： USENIX Association，2006： 307-320.

［3］Ghemawat S，Gobioff H，Leung S T. The Google file system ［J］. ACM SIGOPS Operating Systems Review，2003，37（5）：29-43.

［4］王意潔，許方亮，裴曉強. 分布式存儲中的糾刪碼容錯技術研究 ［J］. 計算機學報，2017，40（1）：236-255. （Wang Yijie，Xu Fang-liang，Pei Xiaoqiang. Research on erasure code-based fault-tolerant technology for distributed storage ［J］. Chinese Journal of Computers， 2017，40（1）： 236-255.）

［5］羅象宏，舒繼武. 存儲系統中的糾刪碼研究綜述 ［J］. 計算機研究與發展，2012，49（1）： 1-11. （Luo Xianghong，Shu Jiwu. Summary of research for erasure code in storage system ［J］. Journal of Computer Research and Development，2012，49（1）： 1-11.）

［6］唐聃，蔡紅亮，耿微. RS類糾刪碼的譯碼方法 ［J］. 計算機研究與發展，2022，59（3）： 582-596. （Tang Dan，Cai Hongliang，Geng Wei. Decoding method of Reed-Solomon erasure codes ［J］. Journal of Computer Research and Development，2022，59（3）： 582-596.）

［7］楊松霖，張廣艷. 糾刪碼存儲系統中數據修復方法綜述 ［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 & Technology，2017，11（10）： 1531-1544.）

［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］洪鐵原，唐聃，熊攀，等. 存儲系統中的局部修復陣列碼模型 ［J］. 計算機應用研究，2024，41（1）： 193-199. （Hong Tieyuan，Tang Dan，Xiong Pan，et al. Local repairable array code model in storage systems ［J］. Application Research of Computers，2024，41（1）： 193-199.）

［10］Bhuvaneshwari P V，Tharini C. Review on LDPC codes for big data storage ［J］. Wireless Personal Communications，2021，117（3）： 1601-1625.

［11］Tu Yaofeng，Xiao Rong，Han Yinjun，et al. DDUC： an erasure-coded system with decoupled data updating and coding ［J］. Frontiers of Information Technology & Electronic Engineering，2023，24（5）： 716-731.

［12］Zhang Xingjun，Liang Ningjin，Liu Yunfei，et al. SA-RSR： a read-optimal data recovery strategy for XOR-coded distributed storage systems ［J］. Frontiers of Information Technology & Electronic Engineering，2022，23（6）： 858-876.

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

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

［15］Huang Cheng，Chen Minghua，Li Jin. Pyramid codes： flexible schemes to trade space for access efficiency in reliable data storage systems ［J］. ACM Trans on Storage，2013，9（1）： article No 3.

［16］Meng Yulong，Zhang Lingling，Xu Dong，et al. A dynamic erasure code based on block code ［C］// Proc of International Conference on Embedded Wireless Systems and Networks. ［S.l.］： Junction Publishing，2019： 379-383.

［17］Wang Zihao，Xie Zheng，Tang Dan. An erasure code with low recovery-overhead based on a particular three-hierarchical redundancy structure ［J］. International Journal of Network Security，2022，24（5）： 965-974.

［18］Miyamae T，Nakao T，Shiozawa K. Erasure code with shingled local parity groups for efficient recovery from multiple disk failures ［C］// Proc of the 10th USENIX Conference on Hot Topics in System Dependability. Berkeley，CA： USENIX Association，2014：.

［19］林軒，王意潔，裴曉強，等. GRC： 一種適用于多節點失效的高容錯低修復成本糾刪碼 ［J］. 計算機研究與發展，2014，51（S2）： 172-181. （Lin Xuan，Wang Yijie，Pei Xiaoqiang，et al. GRC： a high fault-tolerance and low recovery-overhead erasure code for multiple losses ［J］. Journal of Computer Research and Development，2014，51 （S2）： 172-181.）

［20］張航，劉善政，唐聃，等. 分布式存儲系統中的低修復成本糾刪碼 ［J］. 計算機應用，2020，40（10）： 2942-2950. （Zhang Hang，Liu Shanzheng，Tang Dan，et al. Erasure code with low recovery-overhead in distributed storage systems ［J］. Journal of Computer Applications，2020，40（10）： 2942-2950.）