本文關(guān)鍵詞：分布式存儲(chǔ)系統(tǒng)中一種新的再生碼及其譯碼算法研究

  更多相關(guān)文章： 分布式存儲(chǔ)系統(tǒng) 再生碼 Product Matrix 移位操作 按位異或

【摘要】：近年來,“大數(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ù)塊經(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)行運(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算法,能很大程度的降低修復(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í),本文中提出了一種新的基于移位的譯碼算法,新的算法與In-place相比,譯碼時(shí)的時(shí)間消耗降低了50%。
【學(xué)位授予單位】：西南交通大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP333

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條

1 何公明;張?jiān)獫?;面向數(shù)字媒體的高性能分布式存儲(chǔ)系統(tǒng)的研究與應(yīng)用[J];廣播電視信息;2009年10期

2 范劍波,郭建康;分布式存儲(chǔ)系統(tǒng)性能模型的建立與應(yīng)用[J];計(jì)算機(jī)工程與應(yīng)用;2001年13期

3 范劍波,徐利浩;分布式存儲(chǔ)系統(tǒng)可靠性的研究[J];計(jì)算機(jī)工程;2001年06期

4 吳英;謝廣軍;劉t，

本文編號(hào)：1142799