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

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

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

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

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