分布式存儲系統(tǒng)中一種新的再生碼及其譯碼算法研究.pdf

1、近年來，“大數(shù)據(jù)”受到互聯(lián)網(wǎng)行業(yè)及學術(shù)界越來越多的重視，如何存儲及處理“大數(shù)據(jù)”是我們的當務之急。分布式存儲系統(tǒng)在過去30多年里，在數(shù)據(jù)存儲及處理方面發(fā)揮了很大的作用，它很好的平衡了數(shù)據(jù)的可靠性，存儲成本及修復失效節(jié)點的計算復雜度等性能。糾刪碼（Erasure Codes，也翻譯為擦除碼）及復制碼(Replication Codes)是在分布式存儲中使用最為廣泛的編碼。一個系統(tǒng)參數(shù)為（n，k)的Erasure Code，原始的k個數(shù)據(jù)塊

2、經(jīng)過編碼后，生成n個編碼后的數(shù)據(jù)塊，當某個存儲節(jié)點失效時，新加入的節(jié)點會從剩下未失效的數(shù)據(jù)節(jié)點中任意的鏈接k個，并下載節(jié)點中全部的數(shù)據(jù)進行運算，修復失效的節(jié)點。糾刪碼具有存儲消耗小，可靠性高等優(yōu)點，但運算的復雜度較高，下載帶寬大。與糾刪碼相比，復制碼在修復帶寬及計算開銷等方面的性能更優(yōu)。
　　在網(wǎng)絡編碼理論引入分布式存儲系統(tǒng)之后，Dimakis等提出了再生碼的概念。在再生碼理論中，單個的存儲結(jié)點不僅具有存儲和轉(zhuǎn)發(fā)功能，而且還能進行

3、運算。自2010年起，學者們提出了性能各異的MBR(Minimum Bandwidth Regenerating)碼，MSR(Minimum Storage Regenerating)碼和LRC(Locally Repairable Codes)。而Rashmi等人提出的Product Matrix構(gòu)造法，由于不受構(gòu)造參數(shù)的限制，被廣泛的研究。另外，針對基于移位操作的再生碼，Yang等提出一種基于Xor的In-place算法，能很大程度

4、的降低修復時的運算復雜度。
　　前面提到的Product Matrix MBR碼及BASIC碼雖然下載帶寬已達到最優(yōu)，但修復時的數(shù)據(jù)讀取量(Data I/O)卻依然不理想。本文在基于移位操作的Product Matrix MBR碼的基礎(chǔ)上，做出了改進，改進后的編碼具有原始Product Matrix碼的所有優(yōu)點，并且還具有最佳I/O性質(zhì)，使得修復時，總的數(shù)據(jù)讀取量達到理論最優(yōu)。同時，本文中提出了一種新的基于移位的譯碼算法，新的算法