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

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

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

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

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

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

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