基于局部性編碼的分布式存儲(chǔ)容錯(cuò)機(jī)制研究.pdf

1、當(dāng)前社會(huì)產(chǎn)生的大量數(shù)據(jù)需要更好的存儲(chǔ)解決方案。近年來，基于網(wǎng)絡(luò)技術(shù)的分布式存儲(chǔ)，將數(shù)據(jù)存儲(chǔ)在多個(gè)廉價(jià)設(shè)備上，已經(jīng)得到了廣泛的應(yīng)用。但是考慮到系統(tǒng)的規(guī)模，系統(tǒng)中的構(gòu)成節(jié)點(diǎn)以及其它網(wǎng)絡(luò)組件故障已經(jīng)是常見的情況。為了保證數(shù)據(jù)的可用性，就需要引進(jìn)一定的冗余，而數(shù)據(jù)長期的可靠性，則依賴于對(duì)丟失冗余的修復(fù)。分布式存儲(chǔ)系統(tǒng)一般采用復(fù)制策略產(chǎn)生冗余。最近，能夠提供更好存儲(chǔ)效率的糾刪碼已經(jīng)被用來減少三副本系統(tǒng)中的大量存儲(chǔ)開銷。然而在修復(fù)過程中，糾刪碼要從

2、多個(gè)節(jié)點(diǎn)中下載大量的數(shù)據(jù)，并不是修復(fù)丟失冗余的高效方案。為了解決這個(gè)問題，本文提供兩種局部性編碼技術(shù)，以減少修復(fù)過程中所需的修復(fù)帶寬和修復(fù)局部性(稱修復(fù)過程中需要連接的節(jié)點(diǎn)數(shù)為修復(fù)局部性)。
　　 1.通過將(n，k)RS編碼和X編碼結(jié)合，為分布式存儲(chǔ)系統(tǒng)設(shè)計(jì)了一類新的準(zhǔn)確修復(fù)編碼—(n，k,f)X再生碼(XRC)，其中RS編碼用于提供容忍n-k個(gè)節(jié)點(diǎn)故障的可靠性，X編碼則用在RS編碼之上，提供對(duì)單個(gè)或者兩個(gè)節(jié)點(diǎn)故障的高效準(zhǔn)確修

3、復(fù)。一個(gè)顯著的優(yōu)勢是在修復(fù)過程中，需要連接的節(jié)點(diǎn)數(shù)可以設(shè)置成與n，k獨(dú)立的較小常數(shù)。文中對(duì)X再生碼的存儲(chǔ)代價(jià)、修復(fù)帶寬、修復(fù)局部性和編碼率進(jìn)行了分析，并與RS編碼、復(fù)制以及SRC進(jìn)行了對(duì)比。結(jié)果顯示，X再生碼在修復(fù)一個(gè)或者兩個(gè)節(jié)點(diǎn)故障時(shí)，在修復(fù)局部性以及修復(fù)帶寬上都具有顯著的優(yōu)勢，并能達(dá)到任意高的編碼率。我們提供了使用馬爾科夫模型估計(jì)平均數(shù)據(jù)丟失時(shí)間的可靠性分析，對(duì)XRC，RS編碼，復(fù)制的可靠性進(jìn)行了對(duì)比。X再生碼的可靠性與RS編碼相比

4、有了顯著的提升。
　　 2.介紹了另一類新的準(zhǔn)確修復(fù)編碼，由RS編碼和復(fù)制兩部分結(jié)合而成，RS編碼用于保證分布式系統(tǒng)的(n，k)性質(zhì)，復(fù)制用于保證高效的無編碼修復(fù)，我們稱這種新編碼為R再生碼。文中主要介紹了兩種:基于兩副本的(n，k，2)-R再生碼，以及基于三副本的(n，k，3)-R再生碼。(n，k,2)-R再生碼可以對(duì)一個(gè)節(jié)點(diǎn)故障進(jìn)行無編碼的修復(fù)，修復(fù)局部性為2，編碼率為k/2n。(n，k，3)-R再生碼可以對(duì)兩個(gè)節(jié)點(diǎn)同時(shí)出現(xiàn)