基于非均勻循環(huán)編碼的分組修復(fù)碼構(gòu)造

王 靜，雷 珂，李家儀，田松濤，王相隆

(1. 長安大學(xué)信息工程學(xué)院 西安 710064；2. 山東科技大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院 山東 青島 266590)

隨著信息技術(shù)的快速發(fā)展，海量數(shù)據(jù)存儲引起了廣泛關(guān)注。當(dāng)存儲PB 級以及更高量級數(shù)據(jù)時，傳統(tǒng)的集中式存儲系統(tǒng)在存儲容量、存儲成本和擴展性等方面存在諸多瓶頸，尤其是價格昂貴的設(shè)備開銷使其無法適應(yīng)當(dāng)前存儲需求。分布式存儲系統(tǒng)以其海量存儲能力、高可用性、高可擴展性和低成本等優(yōu)勢成為海量數(shù)據(jù)的有效存儲手段[1]。分布式存儲系統(tǒng)將大量文件存儲在多個廉價存儲設(shè)備中，隨著系統(tǒng)規(guī)模的擴大，存儲節(jié)點故障時有發(fā)生，因此需引入冗余存儲來提高節(jié)點故障時的存儲可靠性。常用的冗余存儲技術(shù)包括復(fù)制策略和糾刪碼策略[2-5]。

復(fù)制策略不需要編解碼運算，操作簡單易于實現(xiàn)，但存儲開銷過大。相比復(fù)制策略，糾刪碼策略雖然具有較低的存儲開銷和較強的容錯性能，但在修復(fù)故障節(jié)點時需要下載文件大小的數(shù)據(jù)量，修復(fù)帶寬開銷過高。針對上述兩種冗余存儲技術(shù)的不足，文獻[6]創(chuàng)造性地將網(wǎng)絡(luò)編碼技術(shù)應(yīng)用于分布式存儲，提出了再生碼的概念，降低了故障節(jié)點的修復(fù)帶寬開銷。文獻[7-9]發(fā)現(xiàn)節(jié)點存儲開銷和修復(fù)帶寬開銷之間的最優(yōu)折中曲線，以及該曲線上的兩個極值點，達到這些極值點的再生碼分別稱為最小存儲再生(minimum storage regenerating, MSR)碼和最小帶寬再生(minimum bandwidth regenerating, MBR)碼。在再生碼的修復(fù)過程中，新生節(jié)點需要從存活節(jié)點中連接d個節(jié)點完成修復(fù)，磁盤I/O 開銷過高。為此， 文獻[10-12]提出了局部修復(fù)碼(locally repairable code, LRC)，通過將原始數(shù)據(jù)塊分組生成組編碼塊，降低了磁盤I/O 開銷；文獻[13-14]進一步分別研究了局部修復(fù)碼的構(gòu)造以及協(xié)作局部修復(fù)碼。文獻[15]針對局部修復(fù)碼在修復(fù)全局校驗塊時成本過高以及組內(nèi)多節(jié)點故障時無法修復(fù)的問題，提出分組修復(fù)碼(group repairable codes, GRC)。文獻[16]在分組修復(fù)碼的基礎(chǔ)上，基于跨條帶重疊編碼的思想提出重疊分組修復(fù)碼(rotated group repairable codes, RGRC)，獲得了更好的數(shù)據(jù)修復(fù)性能。

上述編碼方式均為所有數(shù)據(jù)塊和校驗塊提供了相同等級的故障保護。而在實際的分布式存儲系統(tǒng)中，因磁盤磨損狀況和使用情況的不同，節(jié)點故障概率也會有區(qū)別?？紤]到節(jié)點間不均等的故障概率，文獻[17]在局部修復(fù)碼的基礎(chǔ)上，提出基于非均勻故障保護的局部修復(fù)碼(unequal failure protection based local reconstruction code, UFPLRC)，將數(shù)據(jù)塊劃分為大小不等的分組，分配易出錯的數(shù)據(jù)塊到較小的分組，從而使存儲系統(tǒng)的整體修復(fù)性能和可靠性得到顯著提高，但存在組內(nèi)多個數(shù)據(jù)塊失效時無法局部修復(fù)以及修復(fù)全局校驗塊成本過高的問題。

為了對實際分布式存儲系統(tǒng)中高故障率節(jié)點提供更高等級的保護，本文提出一種基于非均勻循環(huán)編碼的分組修復(fù)碼(group repairable codes based on non-uniform cyclic coding, GRC-NCC)，通過減少高故障率節(jié)點的修復(fù)成本來改善故障節(jié)點的修復(fù)性能。具體地，根據(jù)故障率對存儲節(jié)點進行分組，高故障率節(jié)點存儲到小分組以提供更高等級保護。在此基礎(chǔ)上，使用跨條帶循環(huán)編碼的思想生成組編碼塊和全局校驗塊，故障節(jié)點修復(fù)過程中相鄰條帶的編碼可以提供部分解碼數(shù)據(jù)，獲得較低的數(shù)據(jù)傳輸量和修復(fù)成本。

1 分組修復(fù)碼和重疊分組修復(fù)碼

1.1 分組修復(fù)碼

基于(n,k)最大距離可分(maximum distance separable, MDS)碼，將文件分為大小相等的k個原始數(shù)據(jù)塊，經(jīng)過編碼生成n=k+m個編碼塊。GRC的構(gòu)造過程為：將MDS 碼的k個數(shù)據(jù)塊分為L組，記為Sl(l=1,2,···,L)，將m=m0+m1個編碼塊中的前m0個編碼塊作為GRC 的全局編碼塊，在數(shù)據(jù)塊分組Sl(l=1,2,···,L)中 生成m1個 組編碼塊；m1個組編碼塊生成方式與MDS 碼編碼塊生成方式相同，只需保持本組內(nèi)編碼系數(shù)不變，其余組編碼系數(shù)置零即可；最后將GRC 碼的m0個全局編碼塊視為一組，再生成一個組編碼塊。

具體地，(15, 8)GRC 編碼過程如圖1 所示。將8 個原始數(shù)據(jù)塊D1,D2,···,D8平均分成兩組，為每個組分別生成m1=2個 組編碼塊P1、P2和P3、P4。將(12, 8)MDS 碼 的m0=2個 編 碼 塊Q1、Q2作 為GRC 的全局編碼塊，再將其視為一組生成一個組編碼塊Q3。

圖1 (15, 8)GRC 編碼示意圖

1.2 重疊分組修復(fù)碼

(k,p,q,m)R GRC 基于跨條帶編碼的思想，k表示原始數(shù)據(jù)塊的個數(shù)，p表示組編碼塊的個數(shù)，q表示全局編碼塊的個數(shù)，m表示全局組編碼塊的個數(shù)。(k,p,q,m)RGRC 的構(gòu)造過程如下：將大小為M的文件按照指定的數(shù)據(jù)塊大小進行劃分，然后根據(jù)塊數(shù)劃分為M/k個條帶；每次讀入兩個條帶，將條帶內(nèi)數(shù)據(jù)劃分為k/p個組，為每個組生成一個組編碼塊；再將條帶數(shù)據(jù)劃分為q組，記為Gi(i=1,2,···,q)，其中第一個全局編碼塊由本條帶內(nèi)的數(shù)據(jù)塊編碼得到，第二個全局編碼塊由第二個條帶提供G1組和第一個條帶提供剩余組數(shù)據(jù)求得，依次類推。

具體地，(4, 2, 2, 1)RGRC 的編碼過程如圖2所示。首先讀取兩個條帶，將條帶內(nèi)數(shù)據(jù)劃分為D1、D2和D3、D4，為每個組生成一個組編碼塊P1和P2；再將條帶數(shù)據(jù)劃分為兩組，記為G1和G2，第一個全局編碼塊Q1由本條帶內(nèi)的數(shù)據(jù)求得，第二個全局編碼塊Q2由 第二個條帶提供G1組和第一個條帶提供G2組 數(shù)據(jù)求得；最后將Q1、Q2視為一組生成一個組編碼塊Q3。

圖2 (4, 2, 2, 1)RGRC 編碼示意圖

2 基于非均勻循環(huán)編碼的分組修復(fù)碼

2.1 節(jié)點故障率

節(jié)點故障率 τ是節(jié)點發(fā)生故障的頻數(shù)，以每單位時間的節(jié)點故障數(shù)表示[17]。節(jié)點故障率與平均無故障時間(mean time to failure, MTTF)之間的關(guān)系為：

式中，MTTF 表示系統(tǒng)無故障運行的平均時間，為取所有從系統(tǒng)開始正常運行到發(fā)生故障之間的時間段的平均值。實際分布式存儲系統(tǒng)中節(jié)點故障率并不相同，呈現(xiàn)非均勻分布的特征。

2.2 基于非均勻循環(huán)編碼的分組修復(fù)碼構(gòu)造

基于非均勻循環(huán)編碼的分組修復(fù)碼構(gòu)造算法具體步驟如下。

1) 根據(jù)節(jié)點故障率對存儲節(jié)點進行非均勻分組，記為Gj(j=1,2,···,l)。

3) 將多個條帶組合成條帶集，MDS 碼編碼塊個數(shù)為m=m0+m1。

4) 為 λ個高故障率分組生成m1個組編碼塊，其中第一個組編碼塊由本條帶內(nèi)數(shù)據(jù)塊計算得到，剩余組編碼塊由本條帶與相鄰條帶各提供一部分數(shù)據(jù)塊計算得到；同時，m1個組編碼塊生成方式與MDS碼編碼塊生成方式相同，只需保持本組內(nèi)編碼系數(shù)不變，其余組編碼系數(shù)置為零即可。

5)對于l?λ個低故障率分組，分別異或組內(nèi)數(shù)據(jù)生成一個組編碼塊。

6) 對MDS 碼的前m0個編碼塊，保持第一個全局編碼塊不變，依舊由本條帶內(nèi)的數(shù)據(jù)求得，剩余的全局編碼塊則由上一條帶提供G1組和本條帶提供剩余組數(shù)據(jù)求得，依次類推，最后再將全局編碼塊視為一組生成一個組編碼塊。

(k,λm1,l?λ,m0+1)G RC-NCC 由l個大小不等分組內(nèi)的個數(shù)據(jù)塊、λm1+(l?λ)+1個局部校驗塊、m0個全局校驗塊組成，編碼后共生成n=k+λm1+(l?λ)+m0+1個編碼塊。具體地，(6, 2,1, 3)GRC-NCC 編碼過程如圖3 所示。

圖3 (6, 2, 1, 3)GRC-NCC 編碼示意圖

根據(jù)節(jié)點故障率將存儲節(jié)點劃分為大小不等的l=2 個 分組，記為G1和G2。將MDS 碼中k0=2個數(shù)據(jù)塊存入第1 個分組G1，剩余k0+2=4個數(shù)據(jù)塊存入第2 個分組G2。再將4 個條帶組合成條帶集，為λ=1個 高故障率分組生成m1=2個 組編碼塊p1和p2，其中p1由 組內(nèi)數(shù)據(jù)計算得到，p2由組內(nèi)前半段數(shù)據(jù)與上一條帶中后半段數(shù)據(jù)計算得到。對由D3、D4、D5、D6組 成的l?λ=1個低故障率分組，異或組內(nèi)數(shù)據(jù)生成一個組編碼塊p3。對 MDS 碼的前m0=2個 編碼塊，保持第一個全局編碼塊q1不變，由本條帶內(nèi)的數(shù)據(jù)求得。剩余的全局編碼塊q2由 上一條帶提供G1組 和本條帶提供G2組數(shù)據(jù)求得。再將全局編碼塊q1和q2視為一個分組，生成一個組編碼塊q3。

2.3 故障節(jié)點修復(fù)

2.3.1 單節(jié)點故障

在GRC-NCC 編碼方案中，單節(jié)點故障均可進行組內(nèi)修復(fù)。下面分別以圖3 中高故障率分組節(jié)點D1、低故障率分組節(jié)點D3以 及全局校驗節(jié)點q1故障為例，對采用GRC-NCC 編碼的單節(jié)點故障修復(fù)進行說明。

高故障率分組節(jié)點D1發(fā)生故障時，可通過節(jié)點D2與p1完成修復(fù)，總共傳輸8 個數(shù)據(jù)塊。進一步地，節(jié)點D1也 可通過節(jié)點D2與 兩個組編碼節(jié)點p1、p2混合修復(fù)，如圖4 所示，只需傳輸6 個數(shù)據(jù)塊，且混合修復(fù)算法的優(yōu)勢隨著條帶數(shù)的增多更為明顯。當(dāng)?shù)凸收下史纸M節(jié)點D3故障時，可通過節(jié)點D4、D5、D6和組編碼節(jié)點p3完成修復(fù)。當(dāng)全局校驗節(jié)點q1故 障時，可通過剩余的全局校驗節(jié)點q2和組編碼節(jié)點q3進行局部修復(fù)，從而減少修復(fù)成本。

圖4 (6, 2, 1, 3)GRC-NCC 單節(jié)點故障修復(fù)

2.3.2 多節(jié)點故障

在GRC-NCC 編碼方案中，多節(jié)點故障修復(fù)可分為組內(nèi)修復(fù)與全局修復(fù)兩種，修復(fù)原則是先組內(nèi)修復(fù)，組內(nèi)不可修復(fù)時再全局修復(fù)。下面分情況進行討論：

1) 多個故障節(jié)點分別位于不同修復(fù)組內(nèi)時，可分別在不同修復(fù)組內(nèi)進行單節(jié)點修復(fù)。

2) 多個故障節(jié)點均位于高故障率分組內(nèi)時，若故障節(jié)點數(shù)目不大于組編碼節(jié)點數(shù)目m1，則可在組內(nèi)完成修復(fù)；否則，將使用全局修復(fù)。全局修復(fù)中，若故障節(jié)點數(shù)目不大于編碼節(jié)點(包括組編碼節(jié)點與全局編碼節(jié)點)數(shù)目，使用全局完成修復(fù)，否則無法成功修復(fù)。

3) 多個故障節(jié)點均位于低故障率分組內(nèi)時，此時故障節(jié)點數(shù)目大于組編碼節(jié)點數(shù)目，則在該故障情況下無法進行組內(nèi)修復(fù)，只能采用全局修復(fù)。若故障節(jié)點數(shù)目不大于編碼節(jié)點數(shù)目，使用全局修復(fù)，否則無法成功修復(fù)。

4) 其他多節(jié)點故障修復(fù)情況。對可使用組內(nèi)完成修復(fù)的修復(fù)組先使用組內(nèi)修復(fù)，再使用全局修復(fù)。全局修復(fù)完成后，修復(fù)條件可能會發(fā)生變化，此時若還可使用組內(nèi)修復(fù)則繼續(xù)進行組內(nèi)修復(fù)，組內(nèi)修復(fù)不可進行時再使用全局修復(fù)。重復(fù)以上過程，直至所有故障節(jié)點均修復(fù)成功。

以圖3 中高故障率分組節(jié)點D1、D2、p1、p2全部故障以及全局編碼節(jié)點q1、q2發(fā)生故障為例，說明采用GRC-NCC 編碼方案無法成功修復(fù)故障節(jié)點的情況。首先在高故障率分組中，節(jié)點D1、D2以及組編碼節(jié)點p1、p2全部故障，無法進行組內(nèi)修復(fù)；其次全局校驗分組中的全局編碼節(jié)點q1、q2故障，故障節(jié)點數(shù)目大于未故障組編碼節(jié)點數(shù)目，也不能進行組內(nèi)修復(fù)；最后考慮全局修復(fù)，由于全局編碼節(jié)點q1、q2故 障，則節(jié)點D1、D2不能被修復(fù)，故在該故障情況下無法成功修復(fù)。

圖3 中高故障率分組發(fā)生兩節(jié)點故障時，仍可進行組內(nèi)修復(fù)，減少修復(fù)成本；當(dāng)高故障率分組節(jié)點全部故障時，可使用全局修復(fù)完成所有故障節(jié)點的修復(fù)，為高故障率節(jié)點提供了更高等級的保護。低故障率分組發(fā)生兩節(jié)點故障，修復(fù)過程中相鄰條帶的編碼可為對方提供一部分解碼數(shù)據(jù)，減少數(shù)據(jù)的傳輸量。如圖5 所示低故障率分組節(jié)點D3和p3故障時，首先通過剩余數(shù)據(jù)節(jié)點與全局校驗節(jié)點q2修復(fù)第一條帶與第三條帶中對應(yīng)節(jié)點D3的數(shù)據(jù)塊，所用數(shù)據(jù)塊以 Δ表示；再通過剩余數(shù)據(jù)節(jié)點與全局校驗節(jié)點q1修 復(fù)第0 條帶與第2 條帶中對應(yīng)節(jié)點D3的數(shù)據(jù)塊，所用數(shù)據(jù)塊以 ○表示；最后通過已修復(fù)的節(jié)點D3和 節(jié)點D4、D5、D6實現(xiàn)組編碼節(jié)點p3的修復(fù)?？梢?，GRC-NCC 編碼方案為高故障率節(jié)點提供更有效保護的同時，也考慮了使用跨條帶循環(huán)編碼的思想以減少低故障率節(jié)點的修復(fù)成本。

圖5 (6, 2, 1, 3)GRC-NCC 中低故障率分組兩節(jié)點故障修復(fù)

3 性能分析

本節(jié)主要分析GRC-NCC 的存儲開銷、修復(fù)局部性、修復(fù)帶寬開銷和容錯能力，并與RS 碼和RGRC 進行比較。由于修復(fù)帶寬開銷和修復(fù)局部性依賴于節(jié)點故障，故分別討論了單節(jié)點故障和多節(jié)點故障的情況。

3.1 存儲開銷

本文采用文獻[18]中定義的存儲開銷，存儲編碼數(shù)據(jù)塊需要的存儲空間與存儲原始數(shù)據(jù)塊存儲空間的比值。依據(jù)上述存儲開銷的定義，(n,k)RS碼和(k,λm1,l?λ,m0+1)GRC-NCC 的存儲開銷分別為：

根據(jù) (k,λm1,l?λ,m0+1)GRC-NCC 構(gòu)造過程得m0+m1=n?k，則可直接比較RS 碼和GRC-NCC的存儲開銷。對于 (k,λm1,l?λ,m0+1)GRC-NCC，其存儲開銷為：

因λ ≥1，m1≥1且l≥2，可推斷出：

因此，相比于RS 碼，GRC-NCC 沒有達到最優(yōu)的存儲開銷。

3.2 修復(fù)單故障節(jié)點

修復(fù)單故障節(jié)點時，RS 碼的修復(fù)局部性和修復(fù)帶寬開銷分別為k和n。

除RS 碼外，RGRC 和GRC-NCC 的構(gòu)造使得故障節(jié)點可能位于局部組或全局校驗組，因此綜合考慮兩種情況，討論RGRC 和GRC-NCC 在單節(jié)點故障情況下的修復(fù)局部性和修復(fù)帶寬開銷。首先分析RGRC 和GRC-NCC 在單節(jié)點故障情況下的修復(fù)局部性。修復(fù)局部性是指故障節(jié)點修復(fù)過程中連接的存活節(jié)點數(shù)目。

在(k,λm1,l?λ,m0+1)GRC-NCC 中，故障節(jié)點可以位于局部組，包括高故障率分組和低故障率分組，也可以位于全局校驗組。當(dāng)故障節(jié)點位于第i(i=0,1,···,l?1)個局部組時，修復(fù)單故障節(jié)點需要連接k0+2i個 存活節(jié)點，其中；當(dāng)故障節(jié)點位于全局校驗組時，該故障節(jié)點的修復(fù)局部性為m0，則GRC-NCC 的修復(fù)局部性為：

對于 (k,p,q,m)RGRC，當(dāng)單故障節(jié)點位于局部組時，修復(fù)局部性為k/p；當(dāng)單故障節(jié)點位于全局校驗組時，修復(fù)局部性為q/m，所以RGRC 的修復(fù)局部性為：

為方便比較，設(shè)定RGRC 和GRC-NCC 中分組數(shù)目及全局校驗節(jié)點個數(shù)均為2。圖6 為單節(jié)點故障時，RS 碼、RGRC 和GRC-NCC 的修復(fù)局部性曲線。從圖6 可以看出，隨著存儲節(jié)點數(shù)目k的增加，RS 碼、RGRC 和GRC-NCC 的修復(fù)局部性也隨之線性增加，且提出的GRC-NCC 的修復(fù)局部性最小，RS 碼的修復(fù)局部性最大。

圖6 單節(jié)點故障情況下的修復(fù)局部性

進一步分析修復(fù)單節(jié)點故障的帶寬開銷。修復(fù)帶寬開銷是修復(fù)故障節(jié)點時需要下載的數(shù)據(jù)量的大小。當(dāng)GRC-NCC 的單故障節(jié)點位于局部組時，修復(fù)帶寬開銷為w1=(k0+2i)n/k；當(dāng)單故障節(jié)點位于GRC-NCC 的全局校驗組時，修復(fù)帶寬開銷為w2=m0n/k；考慮到k=，n=k+λm1+l?λ+m0+1，則GRC-NCC 的修復(fù)帶寬開銷為：

下面討論RGRC 的修復(fù)帶寬開銷。當(dāng)RGRC的單故障節(jié)點位于局部組時，修復(fù)帶寬開銷為=(k+p+q+m)/p；當(dāng)單故障節(jié)點位于全局校驗組時，修復(fù)帶寬開銷為=q(k+p+q+m)/km。因此，RGRC的修復(fù)帶寬開銷為：

取n=k+4，假定RGRC 和GRC-NCC 中分組數(shù)目及全局校驗節(jié)點個數(shù)均為2，RS 碼、RGRC和GRC-NCC 的修復(fù)帶寬開銷的性能如圖7 所示。由圖可知，GRC-NCC 的修復(fù)帶寬開銷最小，RGRC次之，RS 碼的修復(fù)帶寬開銷最大。

圖7 單節(jié)點故障情況下的修復(fù)帶寬開銷

3.3 修復(fù)多故障節(jié)點

修復(fù)多故障節(jié)點時，RS 碼的修復(fù)局部性和修復(fù)帶寬開銷仍分別為k和n。對于RGRC 和GRCNCC，當(dāng)多個故障節(jié)點分別位于不同分組時，均可通過組內(nèi)完成修復(fù)，因此主要討論同組發(fā)生多節(jié)點故障的情況。

RGRC 無論是修復(fù)局部組還是全局校驗組的多故障節(jié)點，都必須采用全局修復(fù)，因此RGRC 的修復(fù)局部性為k，修復(fù)帶寬開銷為k+p+q+m。

對于GRC-NCC，當(dāng)高故障率分組發(fā)生多節(jié)點故障，且假設(shè)故障節(jié)點個數(shù)不大于m1時，仍可進行組內(nèi)修復(fù)，修復(fù)局部性為k0+2i(i=0,1,···,λ?1)；當(dāng)?shù)凸收下史纸M或全局校驗組發(fā)生多節(jié)點故障時，此時需采用全局修復(fù)，修復(fù)局部性為k。所以GRC-NCC 的修復(fù)局部性為：

取RGRC 和GRC-NCC 中分組數(shù)目及全局校驗節(jié)點個數(shù)為2 時，得到圖8 所示的多節(jié)點故障時的修復(fù)局部性和存儲節(jié)點數(shù)k的關(guān)系。從圖中得知，GRC-NCC 修復(fù)多節(jié)點故障時的修復(fù)局部性最小。

圖8 多節(jié)點故障情況下的修復(fù)局部性

當(dāng)高故障率分組發(fā)生多節(jié)點故障時，GRC-NCC的修復(fù)帶寬開銷為w1=(k0+2i)n/k；當(dāng) 低故障率分組或全局校驗組發(fā)生多節(jié)點故障時，其修復(fù)帶寬開銷為w2=n。所以GRC-NCC 的修復(fù)帶寬開銷為：

設(shè)定n=k+4，RGRC 和GRC-NCC 中分組數(shù)目及全局校驗節(jié)點個數(shù)為2，多節(jié)點故障時幾種碼的修復(fù)帶寬開銷和存儲節(jié)點數(shù)k的關(guān)系如圖9 所示，其中GRC-NCC 修復(fù)多節(jié)點故障時的修復(fù)帶寬開銷最小。

圖9 多節(jié)點故障情況下的修復(fù)帶寬開銷

實際分布式存儲系統(tǒng)中，多節(jié)點故障導(dǎo)致數(shù)據(jù)不可用占據(jù)了較少數(shù)情況。而對于GRC-NCC 而言，多個故障節(jié)點同時位于低故障率分組的可能性更小，因此若只考慮高故障率分組發(fā)生多節(jié)點故障的情況，則GRC-NCC 的修復(fù)局部性為k0+2i(i=0,1,···,λ?1)，修復(fù)帶寬開銷為 (k0+2i)n/k。圖10和圖11 分別給出了此種情況下各種碼的修復(fù)局部性和修復(fù)帶寬開銷隨存儲節(jié)點數(shù)k的變化曲線。從圖中可以得知，GRC-NCC 具有更優(yōu)的修復(fù)局部性和修復(fù)帶寬開銷。

圖10 高故障率分組多節(jié)點故障情況下的修復(fù)局部性

圖11 高故障率分組多節(jié)點故障情況下的修復(fù)帶寬開銷

3.4 容錯能力

容錯能力是指分布式存儲系統(tǒng)可以容忍節(jié)點故障且保證數(shù)據(jù)不丟失的能力，是分布式存儲系統(tǒng)的一個重要因素[19]。具體地，一個(10, 6)RS 碼可以容忍任意4 個節(jié)點故障。對于(6, 2, 2, 1)RGRC 和(6, 2, 1, 3)GRC-NCC 來說，兩種編碼均能恢復(fù)任意3 錯，因此下面主要討論故障節(jié)點數(shù)大于3 時，兩種編碼方式的容錯能力。

當(dāng)故障節(jié)點數(shù)為4 時，統(tǒng)計(6, 2, 2, 1)RGRC不可修復(fù)情況的數(shù)目為，計算其容4錯能力為：

(6, 2, 1, 3)GRC-NCC 容4 錯能力為：

當(dāng)故障節(jié)點數(shù)為5 時，(6, 2, 2, 1)RGRC 和(6,2, 1, 3)GRC-NCC 容5 錯能力分別為：

(6, 2, 2, 1)RGRC 最多能容忍5 個節(jié)點故障，其容6 錯能力為0；而(6, 2, 1, 3)GRC-NCC 容6 錯能力為：

圖12 給出了(10, 6)RS 碼、(6, 2, 2, 1)RGRC和(6, 2, 1, 3)GRC-NCC 在不同故障節(jié)點數(shù)目情況下的容錯能力，其他k和故障節(jié)點數(shù)目情況下同理。通過上述分析對比可得，相比于其他兩種編碼方式，GRC-NCC 的容錯能力更好，同時可以容忍更多的節(jié)點故障。

圖12 容錯能力對比

4 結(jié)束語

實際分布式存儲系統(tǒng)中節(jié)點故障率不同，而現(xiàn)有的糾刪碼大多都是為節(jié)點提供相同等級的保護，這使得高故障率節(jié)點沒有得到更高等級的保護。針對該問題，本文提出一種基于非均勻循環(huán)編碼的分組修復(fù)碼GRC-NCC，根據(jù)節(jié)點故障率對存儲節(jié)點進行非均勻分組，同時使用跨條帶循環(huán)編碼的思想，減少故障修復(fù)過程的數(shù)據(jù)傳輸量。與RS 碼和RGRC 相比，GRC-NCC 具有更好的修復(fù)局部性和修復(fù)帶寬開銷性能，且在多節(jié)點故障修復(fù)過程中性能更優(yōu)，同時容錯性能也更好。