曹 凱,文 捷

(復(fù)旦大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院,上海 200433)

0 概述

最大距離可分碼(Maximum Distance Separable Code,MDS)是一種常見的糾錯(cuò)碼。假設(shè)M大小的文件被均分成了k個(gè)分片,將它們存儲(chǔ)在具有n個(gè)節(jié)點(diǎn)的分布式存儲(chǔ)系統(tǒng)中(這里n>k)。存儲(chǔ)原始數(shù)據(jù)的前k個(gè)節(jié)點(diǎn)一般稱為系統(tǒng)節(jié)點(diǎn),其余n-k個(gè)節(jié)點(diǎn)稱為奇偶校驗(yàn)節(jié)點(diǎn)。如果一個(gè)編碼滿足在n個(gè)節(jié)點(diǎn)中任意選k個(gè)節(jié)點(diǎn)都可以重建原始數(shù)據(jù),那么就說此碼擁有MDS屬性?；贛DS碼的編碼方案與傳統(tǒng)的基于拷貝的方案相比具有更低的存儲(chǔ)開銷和更高的可靠性,但是與此同時(shí)它的修復(fù)帶寬也隨之提升(修復(fù)帶寬是指修復(fù)失效節(jié)點(diǎn)需要從其他節(jié)點(diǎn)連接下載的總的數(shù)據(jù)量),文獻(xiàn)[1-2]分別提出了新的網(wǎng)絡(luò)編碼的編碼算法來探索這一問題。

為了解決MDS碼高修復(fù)帶寬的問題,最小存儲(chǔ)再生碼(Minimum Storage Regeneration Code,MSR)應(yīng)運(yùn)而生。MSR碼是擁有最優(yōu)修復(fù)屬性的MDS碼[3]。在一個(gè)(n,k)MDS碼中(例如Reed-Solomon碼[4]),當(dāng)某個(gè)系統(tǒng)節(jié)點(diǎn)失效時(shí)需要下載其余幸存節(jié)點(diǎn)的所有數(shù)據(jù),而在MSR碼的修復(fù)過程中卻只需要從每個(gè)幸存節(jié)點(diǎn)下載部分內(nèi)容。文獻(xiàn)[5]探索了顯示的最小存儲(chǔ)再生碼,文獻(xiàn)[6]為降低分布式存儲(chǔ)系統(tǒng)中節(jié)點(diǎn)的存儲(chǔ)量,構(gòu)造了一類新(k+2,k) Hadamard MSR碼,文獻(xiàn)[7]對(duì)MSR碼提出了一種新的Piggybacking架構(gòu)設(shè)計(jì),文獻(xiàn)[8]提出了一種最優(yōu)本地修復(fù)碼的方案,文獻(xiàn)[9]提出了應(yīng)用于分布式存儲(chǔ)系統(tǒng)的準(zhǔn)循環(huán)再生碼構(gòu)造方案,文獻(xiàn)[10]提出一種具有獨(dú)立奇偶符號(hào)的MDS碼,此外,文獻(xiàn)[11]構(gòu)造了擁有最優(yōu)訪問屬性和最優(yōu)更新屬性的MSR碼的框架,文獻(xiàn)[12-14]提出了構(gòu)造高碼率的再生碼方案。以上述研究為基礎(chǔ),本文提出一種基于(k+2,k)MSR碼的高容錯(cuò)低修復(fù)帶寬的編碼方案。

1 傳統(tǒng)MSR碼的修復(fù)方案與問題描述

1.1 傳統(tǒng)(k+r,k)MSR碼的修復(fù)方案

fk+j=Aj,1f1+Aj,2f2+…+Aj,kfk

其中,矩陣Aj,i(1≤i≤k)是一個(gè)a×a的滿秩矩陣,將其稱為第j個(gè)校驗(yàn)節(jié)點(diǎn)對(duì)第i個(gè)系統(tǒng)節(jié)點(diǎn)的編碼矩陣。表1和表2給出了一般(k+r,k)MSR碼的節(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)。

表1 (k+r,k)MSR碼的系統(tǒng)節(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)

表2 (k+r,k)MSR碼的校驗(yàn)節(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)

假設(shè)第i個(gè)(1≤i≤k)系統(tǒng)節(jié)點(diǎn)發(fā)生故障,對(duì)于(k+r,k)MSR碼,需要從其他所有幸存節(jié)點(diǎn)下載Si,jfj(j≠i)。其中,矩陣Si,j是一個(gè)(a/r×a)的矩陣(秩為a/r),稱為第j個(gè)節(jié)點(diǎn)對(duì)第i個(gè)系統(tǒng)節(jié)點(diǎn)的修復(fù)矩陣。然后就可以恢復(fù)原始數(shù)據(jù)fi。假設(shè)r=2,為了更加簡(jiǎn)單直觀地表示,設(shè)定:

Si,j=Si,1≤i≤k,1≤j≠i≤k+2

Aj,i=Ai,1≤i≤k

在修復(fù)節(jié)點(diǎn)i的過程中,可以得到以下的線性方程:

通過以上分析可以看到,為了修復(fù)單個(gè)失效的系統(tǒng)節(jié)點(diǎn)i(1≤i≤k),只需要從其他k+r-1個(gè)幸存節(jié)點(diǎn)中分別下載1/r比例的數(shù)據(jù),總的修復(fù)帶寬就為(k+r-1)a/r,所以,對(duì)于修復(fù)單個(gè)失效的系統(tǒng)節(jié)點(diǎn)(現(xiàn)已有對(duì)所有節(jié)點(diǎn)修復(fù)均符合最優(yōu)屬性的碼,如文獻(xiàn)[15]),MSR碼擁有最優(yōu)修復(fù)屬性。

1.2 問題描述

在1.1節(jié)中本文已經(jīng)詳細(xì)地描述了當(dāng)單個(gè)系統(tǒng)節(jié)點(diǎn)失效時(shí),傳統(tǒng)MSR碼的修復(fù)過程,但是當(dāng)有多個(gè)節(jié)點(diǎn)失效(比如r個(gè)),此時(shí),MSR碼并沒有最優(yōu)修復(fù)屬性了。以最常見且應(yīng)用廣泛的(k+2,k)MSR碼為例,當(dāng)有2個(gè)系統(tǒng)節(jié)點(diǎn)失效時(shí),此時(shí)總的修復(fù)帶寬就是M=ka。而本文提出的方案正是為了解決此問題。

本文提出一種基于(k+2,k)MSR碼的高容錯(cuò)低修復(fù)帶寬的編碼方案。在新編碼方案中,當(dāng)有2個(gè)系統(tǒng)節(jié)點(diǎn)失效時(shí),新碼修復(fù)帶寬幾乎為原來的一半。

2 新碼的構(gòu)造與修復(fù)帶寬分析

2.1 新編碼的具體構(gòu)造

表3 C1系統(tǒng)節(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)

表4 C1校驗(yàn)節(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)

表5 C2系統(tǒng)節(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)

表6 C2校驗(yàn)節(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)

2.2 新編碼的修復(fù)帶寬分析

在本文編碼方案中,由于新碼上下半部C1、C2是MSR碼,因此局部修復(fù)滿足最優(yōu)修復(fù)屬性。依托于此性質(zhì),接下來具體分析下新碼的修復(fù)帶寬,這里γold代表了傳統(tǒng)(k+2,k)MSR碼的修復(fù)帶寬,γnew代表新碼的修復(fù)帶寬。由于MSR碼也是MDS碼,因此滿足MDS屬性,在原來編碼上添加了4個(gè)備份校驗(yàn)節(jié)點(diǎn),所以,這里最多只需要討論到4系統(tǒng)節(jié)點(diǎn)失效的情況。

情況1當(dāng)單個(gè)系統(tǒng)節(jié)點(diǎn)失效。很明顯,此時(shí)新碼的修復(fù)帶帶寬與(k+2,k)MSR碼是一樣的,均為(k+1)α/2。即:

情況2當(dāng)有2個(gè)系統(tǒng)節(jié)點(diǎn)失效并且都分布在了C1上(發(fā)生概率:1/2×1/2=25%)。首先和之前分析的一樣,γold=ka,并且需要連接k個(gè)節(jié)點(diǎn)進(jìn)行下載,在新碼中,只需要連接上面一半的幸存節(jié)點(diǎn),但是每個(gè)幸存節(jié)點(diǎn)所需要傳輸?shù)臄?shù)據(jù)量都是a,即:

γold=ka

情況3當(dāng)有2個(gè)系統(tǒng)節(jié)點(diǎn)失效并且都分布在了C2上(發(fā)生概率:1/2×1/2=25%)。這種情況實(shí)際與情況2是一致的,即:

γold=ka

γold=ka

γnew=(k+2)×a/2=(k+2)a/2

情況5當(dāng)有3個(gè)系統(tǒng)節(jié)點(diǎn)失效并且都分布在了C1上(發(fā)生概率:(1/2)×(1/2)×(1/2)=12.5%)。由于C1只有2個(gè)校驗(yàn)節(jié)點(diǎn),通過MDS屬性得知,此時(shí)新碼也不能修復(fù)。

情況6當(dāng)有3個(gè)系統(tǒng)節(jié)點(diǎn)失效并且都分布在了C2上(發(fā)生概率:(1/2)×(1/2)×(1/2)=12.5%)。結(jié)論同情況5。

情況9當(dāng)有4個(gè)系統(tǒng)節(jié)點(diǎn)失效并且2個(gè)分布在了C1上,2個(gè)分布在了C2上(發(fā)生概率為37.5%)。

這里額外分析一下這種情況的發(fā)生概率:用4位的2進(jìn)制(0000～1111)來表示總共的16種分布情況,4位代表了4個(gè)失效節(jié)點(diǎn),某位為0代表該失效節(jié)點(diǎn)在上半部分,某位為1代表該失效節(jié)點(diǎn)在下半部分,列出總的16種情況:

0000 0001 0010 0011 0100 0101 0110 0111

1000 1001 1010 1011 1100 1101 1110 1111

其中,只有0011 0101 0110 1001 1010 1111的情況下滿足2-2分布,所以,事件發(fā)生概率為37.5%。

情況104個(gè)失效節(jié)點(diǎn)或者以上時(shí)的失效節(jié)點(diǎn)其他分布情況。原理和上面一樣,此時(shí)新碼也將不能修復(fù)。

表7為(k+2,k)MSR碼與本文方案總的修復(fù)帶寬的對(duì)比情況,其中,表中的比數(shù)分布指的是失效節(jié)點(diǎn)在C1、C2上的分布情況,失效節(jié)點(diǎn)只包含系統(tǒng)節(jié)點(diǎn)。

表7 (k+2,k)MSR碼與新碼的修復(fù)帶寬對(duì)比

綜上,本文的編碼方案在一定程度上對(duì)比傳統(tǒng)的(k+2,k)MSR碼有一定的寬帶修復(fù)優(yōu)勢(shì)。尤其是當(dāng)k?r時(shí),新的編碼仍然符合高碼率的要求,本文的編碼方案試用于所有的(k+2,k)MSR碼,如文獻(xiàn)[3]中所提到的。

3 實(shí)驗(yàn)結(jié)果分析

表8中給出當(dāng)k取值固定時(shí)(k取4),隨著p的變化初始(k+2,k)MSR碼和新編碼的實(shí)際修復(fù)帶寬的變化。為了方便分析,這里只列出單節(jié)點(diǎn)失效和雙節(jié)點(diǎn)失效的情況,其中γold和γnew的單位均為α。

表8 k固定時(shí)的修復(fù)帶寬對(duì)比

根據(jù)表8給出的實(shí)驗(yàn)數(shù)據(jù),可以很容易看出,模擬實(shí)驗(yàn)結(jié)果基本和理論分析的結(jié)果相符合。并且從表8的對(duì)比數(shù)據(jù)可以看出,隨著p的增大,本文方案的修復(fù)帶寬與初始方案相比優(yōu)勢(shì)越來越大:γold隨著p的增大而增大而γnew卻始終在分析的理論期望值2.500周圍徘徊。為了進(jìn)一步地研究新碼的修復(fù)帶寬,接下來再來模擬當(dāng)p取固定值而k變化時(shí)的情景,如表9所示。在此次模擬實(shí)驗(yàn)中,設(shè)定節(jié)點(diǎn)失效概率p取0.1保持不變,并且設(shè)定節(jié)點(diǎn)之間的失效是相互獨(dú)立無相關(guān)的,其中γold和γnew的單位均為α。從表9給出的實(shí)驗(yàn)數(shù)據(jù)可以看到,隨著k取值變大,本文方案的修復(fù)帶寬與初始方案相比優(yōu)勢(shì)也穩(wěn)定提升。從理論來分析,不管是p還是k的增大,都會(huì)導(dǎo)致雙節(jié)點(diǎn)失效事件發(fā)生的概率相比較而提升,所以,本文方案的優(yōu)勢(shì)也會(huì)得以體現(xiàn)。

表9 p固定時(shí)的修復(fù)帶寬對(duì)比

4 結(jié)束語

基于傳統(tǒng)的(k+2,k)MSR碼,本文提出一種改進(jìn)的低修復(fù)帶寬的編碼方案。仿真結(jié)果表明,無論隨著單節(jié)點(diǎn)失效概率的變化還是隨著系統(tǒng)節(jié)點(diǎn)數(shù)的變化,該方案均能取得較好的修復(fù)帶寬。由于考慮到了計(jì)算的復(fù)雜性,后期需將其擴(kuò)展至(k+r,k)MSR碼中,此外需考慮再增加一層甚至多層的MSR碼結(jié)構(gòu),以獲得更好的實(shí)驗(yàn)結(jié)果。

[1] 徐光憲,徐山強(qiáng),許春艷,等.基于漢明重量網(wǎng)絡(luò)編碼的廣播重傳算法[J].計(jì)算機(jī)工程,2016,42(9):38-42.

[2] 劉宴濤,夏桂陽,徐 靜,等.一種基于子樹分解的組播線性網(wǎng)絡(luò)編碼算法[J].計(jì)算機(jī)工程,2015,41(11):152-159.

[3] RASHMI K V,SHAH N B,KUMAR P V.Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points Via a Product-matrix Construction[J].IEEE Transactions on Information Theory,2011,57(8):5227-5239.

[4] 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.

[5] WANG Z,TAMO I,BRUCK J.Explicit Minimum Storage Regenerating Codes[J].IEEE Transactions on Information Theory,2016,62(8):4466-4480.

[6] 張司娜,唐小虎,李 杰.一類新的(k+2,k)Hadamard MSR碼[J].西南交通大學(xué)報(bào),2016,51(1):234-237.

[7] YANG Bin,TANG Xiaohu,LI Jie.A Systematic Piggybacking Design for Minimum Storage Regenerating Codes[J].IEEE Transactions on Information Theory,2015,61(11):5779-5786.

[8] TAMO I,BARG A.A Family of Optimal Locally Recoverable Codes[J].IEEE Transactions on Infor-mation Theory,2013,60(8):4661-4676.

[9] 李晨卉.應(yīng)用于分布式存儲(chǔ)系統(tǒng)的準(zhǔn)循環(huán)再生碼構(gòu)造方案[J].計(jì)算機(jī)工程,2015,41(3):81-87.

[10] BLAUM M,BRUCK J,VARDY E.MDS Array Codes with Independent Parity Symbols[J].IEEE Transactions on Information Theory,1995,42(2):529-542.

[11] LI Jie,TANG Xiaohu,PARAMPALLI U.A Framework of Constructions of Minimal Storage Regenerating Codes with the Optimal Access,Update Property[J].IEEE Transactions on Information Theory,2015,61(4):1920-1932.

[12] PAPAILIOPOULOS D S,DIMAKIS A G,CADAMBEM V R.Repair Optimal Erasure Codes Through Hadamard Designs[J].IEEE Transactions on Information Theory,2013,59(5):3021-3037.

[13] TAMO I,WANG Z,BRUCK J.ZigZag Codes:MDS Array Codes with Optimal Rebuilding[J].IEEE Tran-sactions on Information Theory,2013,59(3):1597-1616.

[14] GOPARAJU S,TAMO I,CALDERBANK R.An Improved Sub-packetization Bound for Minimum Storage Regenerating Codes[J].IEEE Transactions on Information Theory,2014,60(5):2770-2779.

[15] GOPARAJU S,FAZELI A,VARDY A.Minimum Storage Regenerating Codes for All Parameters[J].IEEE Transactions on Information Theory,2016,99(1):1-10.