一類精確修復多個節點的簡單再生碼

收稿日期：2015-06-25。國家自然科學基金項目(61325005)。，博士生，主研領域：分布式存儲，網絡編碼。，教授。

?

一類精確修復多個節點的簡單再生碼

收稿日期：2015-06-25。國家自然科學基金項目(61325005)。王麗莎，博士生，主研領域：分布式存儲，網絡編碼。唐小虎，教授。

海量數據環境下要求存儲系統具有高擴展性、高可靠性和低成本等特點。大規模存儲系統的節點因數目巨大而易頻繁失效，為保證節點的可用性，系統會利用冗余數據對失效節點進行修復。作為一種新的容錯技術，再生碼可有效降低分布式存儲系統中失效節點修復時需要的下載數據量。基于簡單再生碼，為分布式存儲系統設計一種新的編碼方式。它不僅可容忍多個節點同時出錯并進行修復，而且編碼形式簡單并具有較高的碼率。

分布式存儲系統 精確修復 多節點修復 簡單再生碼

0 引 言

據國際數據咨詢公司(IDC)統計2012年全世界產生的數據量已達到1.8 ZB，全球已進入大數據時代。分布式存儲系統通過使用網絡中多臺機器上的存儲設備，把數據分散存儲在多個獨立的節點上，從而實現對數據的海量存儲。分布式存儲系統由于單個節點的可靠性不高，需要利用數據冗余技術保證整個系統的魯棒性，特別地在節點失效時為維持冗余度需要創建新節點代替失效的節點，我們稱其為節點修復問題。

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

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

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

1 預備知識

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

(1)

生成n個校驗數據，最后將這(f+1)n組數據放入表1所示的n個節點中，注意本文涉及節點序號的運算是模n的。

表1 節點數據存儲方式

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

2 能夠精確修復r=2的錯誤再生碼

本節中，我們改進簡單再生碼使其可以修復r=2的錯誤。

2.1 編碼構造

我們保持其他數據不變，僅修改式(1)中的n個校驗數據：

(2)

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

2.2 修復方式

我們具體地給出一般的f，d=f時修復r=2的錯誤方案，對于其他的d，其修復方法與過程類似。

引理1若如下形式的編碼數據同時失效：

則只需下載3f個數據即可完成修復。

(3)

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

表2 情形(Ⅰ)需修復的數據

表3 情形(Ⅱ)需修復的數據

表4 情形(III)需修復的數據

通過上面對修復類型的分析，我們將可以修復的節點對情形總結如表5所示。

表5 各修復情形所對應的節點對

為避免重復，我們對節點個數n的不同進行如下討論。注意到如下主要針對n的取值不同來分類，與上述情形I-III分類不同，主要目的是為避免重復修復節點對。

2.2.1 n=3f+1時的修復

當n=3f+1時，依據表5容易驗證，只需討論上述三種修復情況，即可修復出節點對(1,j),j=2,3,…,n。

2.2.2 3f+1

當3f+1

(IV) 設N=3f+1+j，j=1,2,…,f-1。節點對(1,f+1+t)，t=1,2,…,j失效，我們需要修復數據如表6所示。

表6 情形(IV)需修復的數據

此時根據上面的討論，我們得到如下節點對的修復情形(見表7)。

表7 修復情形(IV)對應的節點對

2.2.3 n≥4f+1時的修復

當n≥4f+1時，對于修復情形(IV) ，取j=f-1，可以修復節點對(1,f+2)，…，(1,2f)。再結合表2，那么只需考慮節點對(1,2f+2)，… ，(1,n-2f)的修復即可。

(V) 節點對(1,j),2f+2≤j≤n-2f失效。

此時，我們得到如下節點對的修復情形(見表8)。

表8 修復情形(V)對應的節點對

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

實例：當參數f=3時，取n=10,12,15，上述五種修復情形可修復的節點對分別如表9所示。

表9 各修復情形及所修復節點對實例

2.3 修復帶寬

修復r=2的失效節點，需要修復2f個編碼數據和2個校驗數據。根據上節的討論，我們得到修復2f個編碼數據需要的下載量如表10所示。

表10 各修復情形所需下載量

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

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

3 能夠精確修復r個錯誤的的再生碼

3.1 編碼構造和相關性能

基于r=2的編碼構造方式，我們把它擴展成可容忍任意r個節點同時失效的編碼形式。此時數據應當進行r次校驗，具體的校驗數據的形式為：

(4)

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

當f無限增大時，可達到任意高的碼率：

3.2 存儲代價及相關性能的比較

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

表11 與MSCR、MBCR碼的參數比較

4 結 語

本文基于文獻[9]中單節點失效的情形，通過對校驗節點的數據進行適當的修改，使其可以對多個節點同時失效進行精確修復。本文具體給出了r=2的失效節點的詳細修復過程，并討論了其修復帶寬。通過對本文所生成的簡單再生碼在存儲代價和相關性能上的分析，可知簡單再生碼具有Repair-by-transfer性質，即可以直接從剩余節點下載數據進行修復，碼率較高，并且簡單再生碼的編碼方式簡單，因此具有一定的優越性。

[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再生碼:一類適用于云存儲的準確修復編碼[J]. 計算機應用與軟件, 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.

王麗莎 唐小虎

(西南交通大學信息科學與技術學院 四川 成都 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