曹 凱,文 捷

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

0 概述

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

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

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

表2 (k+r,k)MSR碼的校驗節(jié)點存儲結(jié)構(gòu)

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

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

Aj,i=Ai,1≤i≤k

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

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

1.2 問題描述

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

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

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

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

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

表4 C1校驗節(jié)點存儲結(jié)構(gòu)

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

表6 C2校驗節(jié)點存儲結(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個備份校驗節(jié)點,所以,這里最多只需要討論到4系統(tǒng)節(jié)點失效的情況。

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

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

γold=ka

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

γold=ka

γold=ka

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

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

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

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

這里額外分析一下這種情況的發(fā)生概率:用4位的2進制(0000～1111)來表示總共的16種分布情況,4位代表了4個失效節(jié)點,某位為0代表該失效節(jié)點在上半部分,某位為1代表該失效節(jié)點在下半部分,列出總的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個失效節(jié)點或者以上時的失效節(jié)點其他分布情況。原理和上面一樣,此時新碼也將不能修復(fù)。

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

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

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

3 實驗結(jié)果分析

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

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

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

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

4 結(jié)束語

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

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

[2] 劉宴濤,夏桂陽,徐 靜,等.一種基于子樹分解的組播線性網(wǎng)絡(luò)編碼算法[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é)報,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)用于分布式存儲系統(tǒng)的準循環(huán)再生碼構(gòu)造方案[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.