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

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

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

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

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

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

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

1.1 分組修復(fù)碼

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

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

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

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

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

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

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

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

2.1 節(jié)點(diǎn)故障率

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3.1 單節(jié)點(diǎn)故障

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

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

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

2.3.2 多節(jié)點(diǎn)故障

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

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

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

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

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

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

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

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

3 性能分析

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

3.1 存儲(chǔ)開銷

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.4 容錯(cuò)能力

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

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

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

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

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

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

圖12 容錯(cuò)能力對(duì)比

4 結(jié)束語

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