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

鄧文杰 洪鐵原 唐聃 王燮

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

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

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

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

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

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

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

1 相關工作

1.1 RS編碼

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

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

1.2 Pyramid編碼

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

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

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

2 HLRC的設計

2.1 HLRC基礎概念

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

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

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

定義2 效率優(yōu)先局部校驗塊。當前的編碼陣列中第一層級的局部校驗塊，與Pyramid碼類似，HLRC編碼時也會產(chǎn)生不同層級的局部校驗塊，其中層級越低，編碼組內(nèi)的數(shù)據(jù)塊越少。

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

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

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

定義6 修復成本。在本文中如沒有特別指定，修復成本通常指定為節(jié)點恢復時讀取和傳輸?shù)目倲?shù)據(jù)量。

2.2 HLRC編碼

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

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

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

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

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

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

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

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

2.3 HLRC解碼

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

2.3.1 單節(jié)點修復

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

a）確定丟失節(jié)點所對應的效率優(yōu)先局部校驗塊p′j。

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

c）通過p′j的編碼方程以及組內(nèi)的數(shù)據(jù)塊，通過式（17）進行解碼，得到丟失節(jié)點derror。

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

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

c）通過p″j的編碼方程以及組內(nèi)的數(shù)據(jù)塊，通過式（19）進行解碼，得到丟失節(jié)點derror。

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

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

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

c）通過px的編碼方程以及組內(nèi)的數(shù)據(jù)塊，通過式（21）（22）進行解碼，得到丟失節(jié)點derror。

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

2.3.2 多節(jié)點修復

定理1 設丟失節(jié)點個數(shù)為x，當擁有x個與丟失的數(shù)據(jù)塊有關聯(lián)的校驗塊時則能夠修復該錯誤。

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

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

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

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

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

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

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

3 實驗結(jié)果

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

3.1 實驗環(huán)境

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

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

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

3.2 容錯能力

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

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

3.3 單節(jié)點修復開銷

當存活節(jié)點越多時，系統(tǒng)出現(xiàn)節(jié)點故障發(fā)生數(shù)據(jù)丟失的概率最高，所以單節(jié)點出錯是存儲系統(tǒng)中面臨的最為常見的錯誤。單節(jié)點修復性能就能很大程度地決定分布式存儲系統(tǒng)的總體穩(wěn)定性和可靠性，也是對于糾刪碼方案而言最為關鍵的性能指標之一。本節(jié)對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）進行了單節(jié)點平均修復開銷的比較，結(jié)果如圖10所示。

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

在存儲系統(tǒng)中，本節(jié)使用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中的橫坐標。最后統(tǒng)計出七種不同的編碼方案中每一次的單節(jié)點修復開銷，具體的實驗結(jié)果如圖11所示。

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

3.4 多節(jié)點修復開銷

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

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

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

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

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

3.5 存儲效率

存儲效率是糾刪碼方案中較為關鍵的指標之一，其決定了編碼方案實際存儲的數(shù)據(jù)占用空間占總使用空間的比例，其比例越大，代表存儲效率越高。圖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）六種不同編碼方案的存儲效率。

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

3.6 實驗數(shù)據(jù)分析

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

4 結(jié)束語

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

參考文獻：

［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］羅象宏，舒繼武. 存儲系統(tǒng)中的糾刪碼研究綜述 ［J］. 計算機研究與發(fā)展，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］. 計算機研究與發(fā)展，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］楊松霖，張廣艷. 糾刪碼存儲系統(tǒng)中數(shù)據(jù)修復方法綜述 ［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］洪鐵原，唐聃，熊攀，等. 存儲系統(tǒng)中的局部修復陣列碼模型 ［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： 一種適用于多節(jié)點失效的高容錯低修復成本糾刪碼 ［J］. 計算機研究與發(fā)展，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］張航，劉善政，唐聃，等. 分布式存儲系統(tǒng)中的低修復成本糾刪碼 ［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.）