一類精確修復(fù)多個(gè)節(jié)點(diǎn)的簡單再生碼

收稿日期：2015-06-25。國家自然科學(xué)基金項(xiàng)目(61325005)。，博士生，主研領(lǐng)域：分布式存儲(chǔ)，網(wǎng)絡(luò)編碼。，教授。

?

一類精確修復(fù)多個(gè)節(jié)點(diǎn)的簡單再生碼

收稿日期：2015-06-25。國家自然科學(xué)基金項(xiàng)目(61325005)。王麗莎，博士生，主研領(lǐng)域：分布式存儲(chǔ)，網(wǎng)絡(luò)編碼。唐小虎，教授。

海量數(shù)據(jù)環(huán)境下要求存儲(chǔ)系統(tǒng)具有高擴(kuò)展性、高可靠性和低成本等特點(diǎn)。大規(guī)模存儲(chǔ)系統(tǒng)的節(jié)點(diǎn)因數(shù)目巨大而易頻繁失效，為保證節(jié)點(diǎn)的可用性，系統(tǒng)會(huì)利用冗余數(shù)據(jù)對(duì)失效節(jié)點(diǎn)進(jìn)行修復(fù)。作為一種新的容錯(cuò)技術(shù)，再生碼可有效降低分布式存儲(chǔ)系統(tǒng)中失效節(jié)點(diǎn)修復(fù)時(shí)需要的下載數(shù)據(jù)量?；诤唵卧偕a，為分布式存儲(chǔ)系統(tǒng)設(shè)計(jì)一種新的編碼方式。它不僅可容忍多個(gè)節(jié)點(diǎn)同時(shí)出錯(cuò)并進(jìn)行修復(fù)，而且編碼形式簡單并具有較高的碼率。

分布式存儲(chǔ)系統(tǒng) 精確修復(fù) 多節(jié)點(diǎn)修復(fù) 簡單再生碼

0 引 言

據(jù)國際數(shù)據(jù)咨詢公司(IDC)統(tǒng)計(jì)2012年全世界產(chǎn)生的數(shù)據(jù)量已達(dá)到1.8 ZB，全球已進(jìn)入大數(shù)據(jù)時(shí)代。分布式存儲(chǔ)系統(tǒng)通過使用網(wǎng)絡(luò)中多臺(tái)機(jī)器上的存儲(chǔ)設(shè)備，把數(shù)據(jù)分散存儲(chǔ)在多個(gè)獨(dú)立的節(jié)點(diǎn)上，從而實(shí)現(xiàn)對(duì)數(shù)據(jù)的海量存儲(chǔ)。分布式存儲(chǔ)系統(tǒng)由于單個(gè)節(jié)點(diǎn)的可靠性不高，需要利用數(shù)據(jù)冗余技術(shù)保證整個(gè)系統(tǒng)的魯棒性，特別地在節(jié)點(diǎn)失效時(shí)為維持冗余度需要?jiǎng)?chuàng)建新節(jié)點(diǎn)代替失效的節(jié)點(diǎn)，我們稱其為節(jié)點(diǎn)修復(fù)問題。

在分布式存儲(chǔ)系統(tǒng)中，主要有三種節(jié)點(diǎn)修復(fù)方式: 復(fù)制、糾刪碼和再生碼。使用復(fù)制和糾刪碼修復(fù)失效節(jié)點(diǎn)時(shí)，要在系統(tǒng)中傳送整個(gè)原始信息，才能在新加入的節(jié)點(diǎn)上重構(gòu)出失效的數(shù)據(jù)塊。為減少修復(fù)失效節(jié)點(diǎn)需要下載的數(shù)據(jù)量(即修復(fù)帶寬)，Dimakis等[1]將網(wǎng)絡(luò)編碼技術(shù)與分布式存儲(chǔ)技術(shù)結(jié)合，提出一種稱之為再生碼的新的編碼策略。對(duì)于(n;k;d)——再生碼，它需要滿足: (1) 是(n;k)——MDS 碼; (2) 當(dāng)一個(gè)節(jié)點(diǎn)失效時(shí)，新節(jié)點(diǎn)可以連接剩下的n-1個(gè)節(jié)點(diǎn)中任意d(d≥k)個(gè)恢復(fù)該節(jié)點(diǎn)的數(shù)據(jù)。文獻(xiàn)[1]中利用網(wǎng)絡(luò)信息流圖理論給出了節(jié)點(diǎn)存儲(chǔ)容量和修復(fù)帶寬之間的理論界，并基于隨機(jī)網(wǎng)絡(luò)編碼技術(shù)構(gòu)造出達(dá)到理論界的最佳再生碼。其中最小存儲(chǔ)再生碼MSR Code(Minimum Storage Regenerating Code)和最小帶寬再生碼MBR Code(Minimum Bandwidth Regenerating Code)因分別具有最小存儲(chǔ)量和最小的修復(fù)帶寬故而最為重要。再生碼修復(fù)失效節(jié)點(diǎn)時(shí)，恢復(fù)出的數(shù)據(jù)和原節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)可能不一樣，這種修復(fù)模式被稱為功能修復(fù)。而精確修復(fù)因能確切地恢復(fù)出失效節(jié)點(diǎn)的數(shù)據(jù)，更符合實(shí)際系統(tǒng)的需要，所以更具研究意義。目前為止，基于完全圖或干擾對(duì)齊技術(shù)構(gòu)造得到的精確修復(fù)的MBR和MSR碼的編碼策略日趨完善[2-4]。最一般的編碼方法是Rashmi等在文獻(xiàn)[4]中利用矩陣乘積的形式給出的, 但是它們的碼率都不高。

上面修復(fù)機(jī)制的研究都是基于單節(jié)點(diǎn)失效情形給出的編碼方案，然而在實(shí)際的分布式存儲(chǔ)系統(tǒng)中多節(jié)點(diǎn)同時(shí)失效的問題也很常見。針對(duì)多節(jié)點(diǎn)修復(fù)，目前有兩種解決方案: 第一種是將多節(jié)點(diǎn)修復(fù)過程轉(zhuǎn)換為多個(gè)獨(dú)立的串行的單次修復(fù)，此時(shí)系統(tǒng)中所使用的(n;k;d)——再生碼只要滿足n≥d+r，即可依次修復(fù)出r個(gè)失效的節(jié)點(diǎn)。事實(shí)上在實(shí)際修復(fù)機(jī)制下，修復(fù)過程中需要修復(fù)的新節(jié)點(diǎn)之間也可以進(jìn)行數(shù)據(jù)傳輸，以進(jìn)一步減少修復(fù)帶寬，這種方式被稱為多節(jié)點(diǎn)合作修復(fù)[5]。Shum等在文獻(xiàn)[6]中確定了節(jié)點(diǎn)存儲(chǔ)容量和修復(fù)帶寬的理論關(guān)系，并依此給出了對(duì)應(yīng)的最小存儲(chǔ)合作再生碼MSCR Code(Minimum Storage Cooperate Regenerating Code)和最小帶寬合作再生碼MBCR Code(Minimum Bandwidth Cooperate Regenerating Code)的參數(shù)。對(duì)此，Wang等[7]構(gòu)造出了任意參數(shù)(n,k,d,r)下的非線性MBCR碼，Chen等[8]給出了參數(shù)為(n=2k;k)的MSCR碼，但精確合作修復(fù)的再生碼構(gòu)造方法還很少。在這些已知的編碼體制的基礎(chǔ)上，近年來人們更多的關(guān)注于新的編碼形式[9-15]。

2012年，Papailiopoulos等[9]利用MDS碼構(gòu)造了一類簡單再生碼。該編碼方式把信息重建和節(jié)點(diǎn)修復(fù)這兩個(gè)問題分離，通過簡單的異或運(yùn)算來精確修復(fù)系統(tǒng)中單個(gè)失效的節(jié)點(diǎn)。此外，其節(jié)點(diǎn)存儲(chǔ)量也與再生碼要求的存儲(chǔ)最小理論值接近。而對(duì)于其它高碼率的編碼構(gòu)造方案[13-15]節(jié)點(diǎn)數(shù)據(jù)存儲(chǔ)量為(n-k)的冪指數(shù)，這極大地增加了系統(tǒng)的復(fù)雜性。本文中，基于簡單再生碼，我們提出一種新的編碼方式，可容忍多個(gè)節(jié)點(diǎn)同時(shí)失效并通過簡單的計(jì)算進(jìn)行修復(fù)。同簡單再生碼一樣，這種編碼形式有較高的碼率和較小的節(jié)點(diǎn)存儲(chǔ)。

1 預(yù)備知識(shí)

本文首先給出簡單再生碼[9]的具體構(gòu)造: 設(shè)文件W大小為M=kf，將其分成f部分:W=[W(1)…W(f)]，這里W(i)∈F1×k，i∈{1,…,f}，F(xiàn)是一充分大的素域。此時(shí)W(i)可以看成是一個(gè)長為k的向量，利用一個(gè)(n;k)——MDS 碼G∈Fk×n分別對(duì)其編碼，形成f個(gè)長為n的編碼向量x(i)= (x0(i),…,xn-1(i)) =W(i)G，其中i∈{1,…,f}。于是根據(jù)MDS碼的性質(zhì)可知，x(i)中的任意k個(gè)數(shù)據(jù)組可以恢復(fù)W(i)，i∈{1,…,f}。接著利用：

(1)

生成n個(gè)校驗(yàn)數(shù)據(jù)，最后將這(f+1)n組數(shù)據(jù)放入表1所示的n個(gè)節(jié)點(diǎn)中，注意本文涉及節(jié)點(diǎn)序號(hào)的運(yùn)算是模n的。

表1 節(jié)點(diǎn)數(shù)據(jù)存儲(chǔ)方式

上述簡單再生碼可以容忍任意n-k個(gè)節(jié)點(diǎn)的錯(cuò)誤，并且能夠使用簡單的異或運(yùn)算進(jìn)行節(jié)點(diǎn)的修復(fù)，詳見文獻(xiàn)[9]。此外，在修復(fù)任意失效節(jié)點(diǎn)時(shí)需要連接的剩余節(jié)點(diǎn)數(shù)為min(2f,n-1)。但是，這種簡單再生碼僅能每次修復(fù)一個(gè)失效的節(jié)點(diǎn)。本文接下來的部分，針對(duì)能精確修復(fù)多個(gè)失效節(jié)點(diǎn)的簡單再生碼進(jìn)行研究。

2 能夠精確修復(fù)r=2的錯(cuò)誤再生碼

本節(jié)中，我們改進(jìn)簡單再生碼使其可以修復(fù)r=2的錯(cuò)誤。

2.1 編碼構(gòu)造

我們保持其他數(shù)據(jù)不變，僅修改式(1)中的n個(gè)校驗(yàn)數(shù)據(jù)：

(2)

這里j=0,1,2,…,n-1，要求n≥3f+1且n-(f+1)≥d≥f。由于僅改變校驗(yàn)數(shù)據(jù)，所以任意選取的k個(gè)節(jié)點(diǎn)中，每行包含的k個(gè)編碼數(shù)據(jù)可恢復(fù)W(i)，i∈{1,…,f}，f行即可重構(gòu)出原始文件。

2.2 修復(fù)方式

我們具體地給出一般的f，d=f時(shí)修復(fù)r=2的錯(cuò)誤方案，對(duì)于其他的d，其修復(fù)方法與過程類似。

引理1若如下形式的編碼數(shù)據(jù)同時(shí)失效：

則只需下載3f個(gè)數(shù)據(jù)即可完成修復(fù)。

(3)

利用引理1，接下來我們根據(jù)修復(fù)類型詳細(xì)分析編碼方式(2)下r=2的錯(cuò)誤修復(fù)過程：

表2 情形(Ⅰ)需修復(fù)的數(shù)據(jù)

表3 情形(Ⅱ)需修復(fù)的數(shù)據(jù)

表4 情形(III)需修復(fù)的數(shù)據(jù)

通過上面對(duì)修復(fù)類型的分析，我們將可以修復(fù)的節(jié)點(diǎn)對(duì)情形總結(jié)如表5所示。

表5 各修復(fù)情形所對(duì)應(yīng)的節(jié)點(diǎn)對(duì)

為避免重復(fù)，我們對(duì)節(jié)點(diǎn)個(gè)數(shù)n的不同進(jìn)行如下討論。注意到如下主要針對(duì)n的取值不同來分類，與上述情形I-III分類不同，主要目的是為避免重復(fù)修復(fù)節(jié)點(diǎn)對(duì)。

2.2.1 n=3f+1時(shí)的修復(fù)

當(dāng)n=3f+1時(shí)，依據(jù)表5容易驗(yàn)證，只需討論上述三種修復(fù)情況，即可修復(fù)出節(jié)點(diǎn)對(duì)(1,j),j=2,3,…,n。

2.2.2 3f+1

當(dāng)3f+1

(IV) 設(shè)N=3f+1+j，j=1,2,…,f-1。節(jié)點(diǎn)對(duì)(1,f+1+t)，t=1,2,…,j失效，我們需要修復(fù)數(shù)據(jù)如表6所示。

表6 情形(IV)需修復(fù)的數(shù)據(jù)

此時(shí)根據(jù)上面的討論，我們得到如下節(jié)點(diǎn)對(duì)的修復(fù)情形(見表7)。

表7 修復(fù)情形(IV)對(duì)應(yīng)的節(jié)點(diǎn)對(duì)

2.2.3 n≥4f+1時(shí)的修復(fù)

當(dāng)n≥4f+1時(shí)，對(duì)于修復(fù)情形(IV) ，取j=f-1，可以修復(fù)節(jié)點(diǎn)對(duì)(1,f+2)，…，(1,2f)。再結(jié)合表2，那么只需考慮節(jié)點(diǎn)對(duì)(1,2f+2)，… ，(1,n-2f)的修復(fù)即可。

(V) 節(jié)點(diǎn)對(duì)(1,j),2f+2≤j≤n-2f失效。

此時(shí)，我們得到如下節(jié)點(diǎn)對(duì)的修復(fù)情形(見表8)。

表8 修復(fù)情形(V)對(duì)應(yīng)的節(jié)點(diǎn)對(duì)

通過上面的分類可知，最多通過上述五種情況的討論即可修復(fù)節(jié)點(diǎn)對(duì)(1,j),2≤j≤n。根據(jù)節(jié)點(diǎn)數(shù)據(jù)放置的對(duì)稱性，可類似的修復(fù)任意的節(jié)點(diǎn)對(duì)，從而式(2)的編碼方式可容忍r=2的節(jié)點(diǎn)失效。

實(shí)例：當(dāng)參數(shù)f=3時(shí)，取n=10,12,15，上述五種修復(fù)情形可修復(fù)的節(jié)點(diǎn)對(duì)分別如表9所示。

表9 各修復(fù)情形及所修復(fù)節(jié)點(diǎn)對(duì)實(shí)例

2.3 修復(fù)帶寬

修復(fù)r=2的失效節(jié)點(diǎn)，需要修復(fù)2f個(gè)編碼數(shù)據(jù)和2個(gè)校驗(yàn)數(shù)據(jù)。根據(jù)上節(jié)的討論，我們得到修復(fù)2f個(gè)編碼數(shù)據(jù)需要的下載量如表10所示。

表10 各修復(fù)情形所需下載量

修復(fù)校驗(yàn)數(shù)據(jù)時(shí)，可以重復(fù)利用下載的數(shù)據(jù)，或是利用已修復(fù)的編碼數(shù)據(jù)，所以需要再下載的數(shù)據(jù)量最多為2f。因此結(jié)合表10可知，修復(fù)r=2的失效節(jié)點(diǎn)需要的帶寬最多為4f2+2f=2f(2f+1)，那么相應(yīng)的修復(fù)一個(gè)節(jié)點(diǎn)的修復(fù)帶寬為f×(2f+1)。

注4對(duì)于n=3f+1,d=f按照上述的方式進(jìn)行編碼，經(jīng)驗(yàn)證可以同時(shí)修復(fù)r=2的失效節(jié)點(diǎn)的數(shù)據(jù)。選取N=(3f+1)m個(gè)節(jié)點(diǎn)，并平均分成m份，每份含有3f+1個(gè)節(jié)點(diǎn)。對(duì)n=3f+1,d=f的編碼形式復(fù)制到這m份中，那么我們就得到了一個(gè)新的再生碼。這種新的再生碼同樣可以同時(shí)修復(fù)r=2的失效節(jié)點(diǎn)的數(shù)據(jù)， 并且修復(fù)數(shù)據(jù)需要連接的節(jié)點(diǎn)數(shù)(Repair Locality)可以只有3f+1個(gè)。

3 能夠精確修復(fù)r個(gè)錯(cuò)誤的的再生碼

3.1 編碼構(gòu)造和相關(guān)性能

基于r=2的編碼構(gòu)造方式，我們把它擴(kuò)展成可容忍任意r個(gè)節(jié)點(diǎn)同時(shí)失效的編碼形式。此時(shí)數(shù)據(jù)應(yīng)當(dāng)進(jìn)行r次校驗(yàn)，具體的校驗(yàn)數(shù)據(jù)的形式為：

(4)

這里要求節(jié)點(diǎn)個(gè)數(shù)n≥(2r-1)f+1，才能從剩余可用的節(jié)點(diǎn)上下載的數(shù)據(jù)，修復(fù)出失效的數(shù)據(jù)。因此關(guān)于任意r個(gè)節(jié)點(diǎn)錯(cuò)誤的修復(fù)過程雖然更復(fù)雜，需要討論的情況更多，但是總能夠找到相應(yīng)存活的數(shù)據(jù)進(jìn)行修復(fù)，在此我們省略其具體過程。

當(dāng)f無限增大時(shí)，可達(dá)到任意高的碼率：

3.2 存儲(chǔ)代價(jià)及相關(guān)性能的比較

在表11中，給出了可以修復(fù)多個(gè)失效節(jié)點(diǎn)的編碼：MSCR碼，MBCR碼和改造的簡單再生碼之間的比較。主要涉及以下四個(gè)參數(shù)：每個(gè)節(jié)點(diǎn)的存儲(chǔ)代價(jià)；修復(fù)任意r個(gè)失效節(jié)點(diǎn)時(shí)，每個(gè)節(jié)點(diǎn)需要的帶寬；編碼率；Repair-by-transfer性質(zhì)，即可以直接從剩余節(jié)點(diǎn)下載數(shù)據(jù)進(jìn)行修復(fù)。由表11可知，改造的簡單再生碼的存儲(chǔ)和修復(fù)帶寬只與f有關(guān)，并且當(dāng)f越大時(shí)，與MSCR碼的存儲(chǔ)最小理論值和碼率越接近。而現(xiàn)有的MSCR碼的編碼策略中，要求節(jié)點(diǎn)數(shù)據(jù)存儲(chǔ)量為(n-k)的冪指數(shù)，這極大地增加了系統(tǒng)的復(fù)雜性，改造的簡單再生碼卻可以存儲(chǔ)多項(xiàng)式函數(shù)。對(duì)于修復(fù)帶寬，相比于利用拉格朗日插值法需運(yùn)算而構(gòu)造的MBCR碼，改造的簡單再生碼在修復(fù)數(shù)據(jù)時(shí)，可以直接從剩余節(jié)點(diǎn)下載數(shù)據(jù)，運(yùn)算簡單并且可靠型強(qiáng)。所以，改造的簡單再生碼與其他可以修復(fù)多個(gè)失效節(jié)點(diǎn)的編碼相比，花費(fèi)較小的存儲(chǔ)代價(jià)，且達(dá)到簡單的修復(fù)運(yùn)算性能，可適用于分布式存儲(chǔ)系統(tǒng)中。

表11 與MSCR、MBCR碼的參數(shù)比較

4 結(jié) 語

本文基于文獻(xiàn)[9]中單節(jié)點(diǎn)失效的情形，通過對(duì)校驗(yàn)節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行適當(dāng)?shù)男薷?，使其可以?duì)多個(gè)節(jié)點(diǎn)同時(shí)失效進(jìn)行精確修復(fù)。本文具體給出了r=2的失效節(jié)點(diǎn)的詳細(xì)修復(fù)過程，并討論了其修復(fù)帶寬。通過對(duì)本文所生成的簡單再生碼在存儲(chǔ)代價(jià)和相關(guān)性能上的分析，可知簡單再生碼具有Repair-by-transfer性質(zhì)，即可以直接從剩余節(jié)點(diǎn)下載數(shù)據(jù)進(jìn)行修復(fù)，碼率較高，并且簡單再生碼的編碼方式簡單，因此具有一定的優(yōu)越性。

[1] Dimakis A G, Godfrey P B, Wu Y, et al. Network coding for distributed storage systems[J].IEEE Transactions on Information Theory, 2010, 56(9):4539-4551.

[2] Suh C, Ramchandran K. Exact-repair MDS codes for distributed storage using interference alignment[C]//IEEE International Symposium on Information Theory, ISIT 2010, Austin, Texas, USA,2010:161-165.

[3] Shah N B, Rashmi K V, Kumar P V, et al. Interference alignment in regenerating codes for distributed storage: Necessity and code constructions[J]. IEEE Transactions on Information Theory,2012,58(4):2134-2158.

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

[5] Hu Y, Xu Y, Wang X, et al. Cooperative recovery of distributed storage systems from multiple losses with network coding[J].IEEE Journal on Selected Areas in Communications, 2010,28(2):268-276.

[6] Shum K W, Hu Y. Cooperative regenerating codes[J].IEEE Transactions on Information Theory, 2013,59(11):7229-7258.

[7] Wang A, Zhang Z. Exact cooperative regenerating codes with minimum-repair-bandwidth for distributed storage[C]//Proceedings of IEEE INFOCOM,2013:400-404.

[8] Chen J, Shum K W. Repairing multiple failures in the Suh-Ramchandran regenerating codes[C]//IEEE International Symposium on Information Theory,2013:1441-1445.

[9] Papailiopoulos D S, Luo J, Dimakis A G, et al. Simple regenerating codes: Network coding for cloud storage[C]//Proceedings of the IEEE INFOCOM 2012, Orlando, FL, USA, 2012:2801-2805.

[10] 李小兵, 許胤龍, 林一施,等. X再生碼:一類適用于云存儲(chǔ)的準(zhǔn)確修復(fù)編碼[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2014,31(8)：241-244,248.

[11] Shah N B. On Minimizing Data-Read and Download for Storage-Node Recovery[J].IEEE Communications Letters, 2013,17(5):964-967.

[12] Ernvall T. Codes between MBR and MSR points with exact repair property[J].IEEE Transactions on Information Theory,2014,60(11):6993-7005.

[13] Papailiopoulos D S, Dimakis A G, Cadambe V R. Repair Optimal Erasure Codes through Hadamard Designs[J].Information Theory IEEE Transactions on,2013,59(5):3021-3037.

[14] Tamo I, Wang Z, Bruck J. Zigzag Codes: MDS Array Codes with Optimal Rebuilding[J].IEEE Transactions on Information Theory, 2013,59(3):1597-1616.

[15] Li J, Tang X, 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.

王麗莎 唐小虎

(西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院 四川 成都 611756)

A CLASS OF SIMPLE REGENERATING CODES CAPABLE OF EXACT MULTI-NODE REPAIR

Wang Lisha Tang Xiaohu

(SchoolofInformationScienceandTechnology,SouthwestJiaotongUniversity,Chengdu611756,Sichuan,China)

Massive data environment requires the storage system with the characteristics such as high scalability, high reliability and low price, etc. However, the nodes in large-scale storage system will frequently failure due to too huge in number. In order to ensure the usability of nodes, the system will use redundancy data to repair the failure nodes. As a new fault-tolerant technology, regenerating code can effectively reduce the amount of the download data required when repairing the failure nodes in distributed storage system. In this paper, we design a new encoding mode for distributed storage system based on simple regenerating codes. This mode can not only tolerates the simultaneous errors of multiple nodes and repairs them, but also has simple encoding form and achieves higher code rate.

Distributed storage system Exact repair Multi-node repair Simple regenerating codes

TP302.8

A

10.3969/j.issn.1000-386x.2016.11.003