分布式存儲系統(tǒng)中糾刪碼的數(shù)據(jù)修復技術(shù)研究.pdf

1、在“大數(shù)據(jù)”時代背景下，信息技術(shù)產(chǎn)業(yè)已從以計算為核心的時代進入到了以存儲為核心的時代，數(shù)據(jù)海量化成為了一種趨勢。構(gòu)建于普通服務器集群之上的分布式存儲系統(tǒng)，因其成本低廉和擴展性高等優(yōu)點被廣泛應用于海量數(shù)據(jù)的存儲。但是分布式存儲系統(tǒng)節(jié)點規(guī)模龐大且單個節(jié)點可靠性不高，致使系統(tǒng)發(fā)生節(jié)點失效的概率大為提高。為了保證數(shù)據(jù)可靠性，系統(tǒng)必須采用一定的數(shù)據(jù)容錯技術(shù)。糾刪碼作為一種可靠性高且存儲空間消耗少的容錯技術(shù)，對提高分布式存儲系統(tǒng)的數(shù)據(jù)可靠性并降低其

2、經(jīng)濟成本具有重大意義。但是糾刪碼數(shù)據(jù)修復網(wǎng)絡負載高、數(shù)據(jù)修復速度低等問題嚴重阻礙了其在分布式存儲系統(tǒng)中的廣泛應用。針對以上問題，本文對糾刪碼的低網(wǎng)絡負載數(shù)據(jù)修復技術(shù)和快速數(shù)據(jù)修復技術(shù)進行了深入研究，主要研究內(nèi)容與貢獻如下：
　　數(shù)據(jù)修復網(wǎng)絡負載的傳統(tǒng)度量指標是傳輸?shù)臄?shù)據(jù)量，這一指標忽略了數(shù)據(jù)傳輸距離的不同，不能精確衡量修復過程中數(shù)據(jù)傳輸對網(wǎng)絡性能產(chǎn)生的影響。針對此問題，本文提出了基于網(wǎng)絡拓撲的網(wǎng)絡負載度量指標：網(wǎng)絡代價。網(wǎng)絡代價將

3、數(shù)據(jù)傳輸?shù)木W(wǎng)絡負載定義為數(shù)據(jù)傳輸量與傳輸距離的乘積，更精確地描述了數(shù)據(jù)傳輸所占用的網(wǎng)絡資源，從而更好地刻畫了數(shù)據(jù)傳輸對網(wǎng)絡性能造成的影響。實驗結(jié)果表明，網(wǎng)絡代價能夠比數(shù)據(jù)傳輸量更加精確地反映數(shù)據(jù)傳輸對網(wǎng)絡性能造成的影響，是更好的網(wǎng)絡負載度量指標。
　　針對糾刪碼數(shù)據(jù)修復網(wǎng)絡代價過高的不足，本文提出了一種基于網(wǎng)絡拓撲的樹型數(shù)據(jù)修復技術(shù)NTree。NTree根據(jù)網(wǎng)絡拓撲將參與修復的節(jié)點組織成總網(wǎng)絡距離最小的樹型修復結(jié)構(gòu)(修復樹)，以最

4、小化修復時數(shù)據(jù)的傳輸距離，從而使修復的網(wǎng)絡代價達到最低。在此基礎上，提出了提供節(jié)點組合的選擇算法OpTree。OpTree能夠在從所有可用節(jié)點中快速選取最優(yōu)提供節(jié)點組合的同時構(gòu)建出最優(yōu)的修復樹，進一步降低NTree的網(wǎng)絡代價。大量的模擬實驗結(jié)果表明，NTree相比于現(xiàn)有的星型修復方法，可將糾刪碼數(shù)據(jù)修復的網(wǎng)絡代價降低20％-45%。
　　針對糾刪碼數(shù)據(jù)修復速度慢導致退化讀性能差的問題，提出了一種基于網(wǎng)絡拓撲的線型數(shù)據(jù)修復技術(shù)NLi

5、ne。對NTree修復過程的深入分析表明，修復速度與修復樹的最大入度成反比。NLine根據(jù)網(wǎng)絡拓撲將參與修復的節(jié)點組織成最大入度為1的線型修復結(jié)構(gòu)(修復路徑)，從而達到了最快的修復速度。同時，為了盡量降低NLine的網(wǎng)絡代價，提出了近似最優(yōu)的修復路徑規(guī)劃算法OpLine。大量模擬實驗結(jié)果表明，NLine能夠以接近于NTree網(wǎng)絡代價獲得至少比星型修復方法高400%，比NTree高100%的修復速度。
　　基于上述理論研究成果，設計

6、實現(xiàn)了一個糾刪碼數(shù)據(jù)修復原型系統(tǒng)ECRepair。ECRepair完全遵循機制與策略分離的設計原則，不僅支持基于網(wǎng)絡拓撲的樹型數(shù)據(jù)修復技術(shù)NTree和基于網(wǎng)絡拓撲的線型數(shù)據(jù)修復技術(shù)NLine，也可以方便地添加對其它樹型修復技術(shù)的支持，并且適用于任何線性糾刪碼。大量真實環(huán)境下的實驗結(jié)果表明，在星型修復方法、基于網(wǎng)絡拓撲的樹型數(shù)據(jù)修復技術(shù) NTree和基于網(wǎng)絡拓撲的線型數(shù)據(jù)修復技術(shù)NLine中，NTree具有最低的網(wǎng)絡代價和最高的并行修復速