基于網(wǎng)絡(luò)編碼的分布式存儲(chǔ)容錯(cuò)及擴(kuò)容問題研究.pdf

1、當(dāng)前，信息技術(shù)飛速發(fā)展，已從以計(jì)算設(shè)備為核心的時(shí)代進(jìn)入到以存儲(chǔ)設(shè)備為核心的時(shí)代，數(shù)據(jù)海量化成為一種趨勢。分布式存儲(chǔ)以其廉價(jià)和高擴(kuò)展性等特點(diǎn)適用于數(shù)據(jù)的海量存儲(chǔ)，得到越來越廣泛的應(yīng)用。分布式存儲(chǔ)系統(tǒng)依靠冗余存儲(chǔ)來維持整個(gè)系統(tǒng)的可靠性，并且需要一個(gè)良好的節(jié)點(diǎn)修復(fù)機(jī)制在發(fā)生節(jié)點(diǎn)故障時(shí)能快速有效的進(jìn)行修復(fù)，維持系統(tǒng)的冗余度。基于網(wǎng)絡(luò)編碼的分布式存儲(chǔ)系統(tǒng)編碼冗余方式(再生碼)相比于傳統(tǒng)的冗余策略(復(fù)制、糾刪碼)，降低了維持系統(tǒng)可靠性所需的存儲(chǔ)開銷

2、和節(jié)點(diǎn)修復(fù)所需的帶寬開銷，因此有著良好的應(yīng)用前景。我們希望對(duì)基于再生碼的各種具體的編碼方式及節(jié)點(diǎn)修復(fù)方式進(jìn)行研究。分布式存儲(chǔ)系統(tǒng)的另一個(gè)關(guān)鍵問題是系統(tǒng)擴(kuò)容。對(duì)于相對(duì)較為復(fù)雜的基于再生碼的分布式存儲(chǔ)系統(tǒng)而言，如何高效的進(jìn)行系統(tǒng)擴(kuò)容，也是我們需要解決的問題。
　　 本文主要研究了基于網(wǎng)絡(luò)編碼的分布式存儲(chǔ)系統(tǒng)中的節(jié)點(diǎn)修復(fù)問題和擴(kuò)容問題，主要研究內(nèi)容如下:
　　 (1)基于MSR(最小存儲(chǔ)再生碼)的單節(jié)點(diǎn)修復(fù)確定性算法
　

3、　 良好的節(jié)點(diǎn)修復(fù)機(jī)制對(duì)分布式存儲(chǔ)系統(tǒng)至關(guān)重要。本文研究了基于MSR編碼的分布式存儲(chǔ)系統(tǒng)的單節(jié)點(diǎn)修復(fù)問題。我們通過對(duì)節(jié)點(diǎn)修復(fù)過程中的兩個(gè)編碼步驟進(jìn)行分析，給出了每個(gè)編碼步驟所需滿足的條件。并參考多播問題中中間節(jié)點(diǎn)進(jìn)行數(shù)據(jù)編碼的確定性算法，給出了一種實(shí)際的MSR編碼單節(jié)點(diǎn)修復(fù)問題的確定性算法滿足上述條件。與傳統(tǒng)的隨機(jī)性方法相比，我們的確定性算法能夠百分之百保證修復(fù)性質(zhì)，使得系統(tǒng)擁有更高的可靠性。同時(shí)只需要一個(gè)相對(duì)小得多的有限域，從而大大

4、減少了編解碼過程中的計(jì)算開銷和內(nèi)存開銷。
　　 (2)多節(jié)點(diǎn)合作修復(fù)的E-MBR(確定性修復(fù)的最小帶寬再生碼)編碼方法
　　 實(shí)際系統(tǒng)中，常常會(huì)遇到多個(gè)節(jié)點(diǎn)同時(shí)發(fā)生故障的情況?，F(xiàn)有的E-MBCR編碼方法僅基于r=n-k個(gè)節(jié)點(diǎn)修復(fù)的情況。對(duì)于r'＜n-k個(gè)節(jié)點(diǎn)故障盡管也能修復(fù)，但帶寬開銷和存儲(chǔ)開銷都較高。本文中，我們證明了任意(n，k)系統(tǒng)中的任意r(2≤r≤n-k)個(gè)節(jié)點(diǎn)故障情況下達(dá)到節(jié)點(diǎn)修復(fù)帶寬開銷下界的E-MBCR編

5、碼的存在性，并給出了一種實(shí)際的編碼方式以及相應(yīng)的節(jié)點(diǎn)修復(fù)和還原原始文件的方法。我們的方法通過多節(jié)點(diǎn)合作修復(fù)降低了修復(fù)帶寬開銷。并通過確定性修復(fù)維持了系統(tǒng)中未編碼的原始文件塊的存在，從而提高了訪問性能。同時(shí)，比起現(xiàn)有的基于r=n-k個(gè)節(jié)點(diǎn)故障的E-MBCR編碼方法，我們的方法降低了系統(tǒng)存儲(chǔ)開銷和節(jié)點(diǎn)修復(fù)帶寬開銷。
　　 (3)基于E-MSR(確定性修復(fù)的最小存儲(chǔ)再生碼)的分布式存儲(chǔ)系統(tǒng)的存儲(chǔ)容量擴(kuò)容問題
　　 分布式存儲(chǔ)系

6、統(tǒng)常常會(huì)遇到存儲(chǔ)容量或訪問性能不足的情況，從而產(chǎn)生系統(tǒng)擴(kuò)容的需求。本文率先提出了基于再生碼的分布式存儲(chǔ)系統(tǒng)擴(kuò)容問題，并研究了基于E-MSR編碼的分布式存儲(chǔ)系統(tǒng)的存儲(chǔ)容量擴(kuò)容問題。我們對(duì)該問題進(jìn)行了建模分析，給出了其限制條件及優(yōu)化目標(biāo)，并主要針對(duì)擴(kuò)容過程的帶寬開銷這一優(yōu)化目標(biāo)對(duì)問題進(jìn)行了研究，指出減少帶寬開銷的關(guān)鍵點(diǎn)在于擴(kuò)容前后系統(tǒng)的編碼塊部分有較大相關(guān)性。我們采用了利用較大規(guī)模系統(tǒng)的編碼矩陣構(gòu)造較小規(guī)模系統(tǒng)的編碼矩陣的方法，使得系統(tǒng)在擴(kuò)