基于(k+2,k)MSR的多容錯低修復帶寬編碼

曹 凱,文 捷

(復旦大學 計算機科學技術學院,上海 200433)

0 概述

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

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

1 傳統MSR碼的修復方案與問題描述

1.1 傳統(k+r,k)MSR碼的修復方案

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

其中,矩陣Aj,i(1≤i≤k)是一個a×a的滿秩矩陣,將其稱為第j個校驗節(jié)點對第i個系統節(jié)點的編碼矩陣。表1和表2給出了一般(k+r,k)MSR碼的節(jié)點存儲結構。

表1 (k+r,k)MSR碼的系統節(jié)點存儲結構

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

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

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

Aj,i=Ai,1≤i≤k

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

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

1.2 問題描述

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

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

2 新碼的構造與修復帶寬分析

2.1 新編碼的具體構造

表3 C1系統節(jié)點存儲結構

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

表5 C2系統節(jié)點存儲結構

表6 C2校驗節(jié)點存儲結構

2.2 新編碼的修復帶寬分析

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

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

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

γold=ka

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

γold=ka

γold=ka

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

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

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

情況9當有4個系統節(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é)點其他分布情況。原理和上面一樣,此時新碼也將不能修復。

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

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

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

3 實驗結果分析

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

表8 k固定時的修復帶寬對比

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

表9 p固定時的修復帶寬對比

4 結束語

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

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

[2] 劉宴濤,夏桂陽,徐 靜,等.一種基于子樹分解的組播線性網絡編碼算法[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].西南交通大學報,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] 李晨卉.應用于分布式存儲系統的準循環(huán)再生碼構造方案[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.