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

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

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

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

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

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

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