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

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

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

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

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

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

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