基于網(wǎng)絡(luò)編碼的分布式存儲(chǔ)容錯(cuò)中修復(fù)機(jī)制研究.pdf

1、當(dāng)前，信息技術(shù)產(chǎn)業(yè)已從以計(jì)算設(shè)備為核心的計(jì)算時(shí)代進(jìn)入到以存儲(chǔ)設(shè)備為核心的存儲(chǔ)時(shí)代，數(shù)據(jù)海量化成為了一種趨勢(shì)。分布式存儲(chǔ)以網(wǎng)絡(luò)技術(shù)為基礎(chǔ)，利用小型服務(wù)器甚至PC機(jī)來(lái)搭建存儲(chǔ)池，從而以其廉價(jià)性和高擴(kuò)展性等特點(diǎn)而適用于對(duì)數(shù)據(jù)的海量存儲(chǔ)。但是由于分布式存儲(chǔ)節(jié)點(diǎn)可用性并不高，因此如何保證高數(shù)據(jù)可靠性就成為亟待解決的問(wèn)題。在存儲(chǔ)系統(tǒng)中，保證數(shù)據(jù)可靠性主要依賴于數(shù)據(jù)容錯(cuò)技術(shù)，而數(shù)據(jù)容錯(cuò)的關(guān)鍵性問(wèn)題是如何進(jìn)行有效的數(shù)據(jù)修復(fù)，即存活節(jié)點(diǎn)盡可能少地消耗系統(tǒng)

2、資源來(lái)修復(fù)失效節(jié)點(diǎn)的問(wèn)題。本文就分布式存儲(chǔ)容錯(cuò)中的修復(fù)機(jī)制進(jìn)行了研究，主要研究成果如下：
　　 (1)分布式存儲(chǔ)容錯(cuò)中修復(fù)問(wèn)題的建模
　　 在現(xiàn)階段，較少工作采用網(wǎng)絡(luò)流圖這個(gè)數(shù)據(jù)工具來(lái)對(duì)分布式存儲(chǔ)容錯(cuò)中修復(fù)過(guò)程進(jìn)行建模，而且少數(shù)幾個(gè)相關(guān)工作的模型都是針對(duì)分布式存儲(chǔ)容錯(cuò)中較特殊的修復(fù)情形，缺乏普適性。因此，本文利用網(wǎng)絡(luò)流圖工具，提出了一個(gè)能夠適用絕大多數(shù)容錯(cuò)修復(fù)情況下的數(shù)學(xué)模型。同時(shí)，本文引入了虛擬信源節(jié)點(diǎn)的思想，簡(jiǎn)化了

3、流圖分析。另外，本文還針對(duì)分布式存儲(chǔ)修復(fù)機(jī)制的特點(diǎn)，專門(mén)在網(wǎng)絡(luò)流圖中引入了三段節(jié)點(diǎn)，精確刻畫(huà)了分布式存儲(chǔ)節(jié)點(diǎn)在修復(fù)過(guò)程中的特性。最后，本文利用該數(shù)學(xué)模型，證明了分布式存儲(chǔ)容錯(cuò)中修復(fù)過(guò)程并不需要有存活節(jié)點(diǎn)之間的數(shù)據(jù)傳輸過(guò)程，從而為后面的修復(fù)機(jī)制的設(shè)計(jì)提供了一定的理論基礎(chǔ)。
　　 (2)一種基于彈性的節(jié)點(diǎn)修復(fù)機(jī)制
　　 在分布式存儲(chǔ)容錯(cuò)修復(fù)問(wèn)題上，已有的修復(fù)機(jī)制限制所有的待修復(fù)節(jié)點(diǎn)必須連接同樣多的d個(gè)存活節(jié)點(diǎn)來(lái)完成修復(fù)，但

4、在較為不穩(wěn)定的網(wǎng)絡(luò)環(huán)境中，待修復(fù)節(jié)點(diǎn)并不能保證總是能連接到d個(gè)存活節(jié)點(diǎn)。因此，本文提出了一種基于彈性的節(jié)點(diǎn)修復(fù)機(jī)制MFR，該機(jī)制能夠讓一個(gè)待修復(fù)節(jié)點(diǎn)Yj任意連接dj個(gè)節(jié)點(diǎn)來(lái)完成修復(fù)過(guò)程，不同的新節(jié)點(diǎn)Yi和Yj所對(duì)應(yīng)的di和dj無(wú)需相等。這樣可以使得新節(jié)點(diǎn)的修復(fù)過(guò)程更加靈活，從而適應(yīng)不同的網(wǎng)絡(luò)狀況。同時(shí)，本文還針對(duì)MFR機(jī)制，利用網(wǎng)絡(luò)流圖模型計(jì)算出完成修復(fù)所消耗的修復(fù)帶寬下界。最后本文為MFR設(shè)計(jì)了相應(yīng)的隨機(jī)線性編碼算法，并保證該算法正確

5、性的前提下，達(dá)到已知的修復(fù)帶寬下界，因此該下界是緊致的，并且該算法是基于MFR機(jī)制的最優(yōu)算法。
　　 (3)一種基于相互協(xié)作的多節(jié)修復(fù)機(jī)制
　　 現(xiàn)有的一些較好的修復(fù)機(jī)制都是針對(duì)于單節(jié)點(diǎn)修復(fù)問(wèn)題的，沒(méi)有專門(mén)針對(duì)多節(jié)點(diǎn)同時(shí)修復(fù)的問(wèn)題進(jìn)行研究，然而多節(jié)點(diǎn)的同時(shí)修復(fù)問(wèn)題在實(shí)際分布式存儲(chǔ)系統(tǒng)中非常常見(jiàn)。本文針對(duì)多節(jié)點(diǎn)同時(shí)修復(fù)的問(wèn)題，提出了一種基于相互協(xié)作的多節(jié)點(diǎn)修復(fù)機(jī)制MCR，該機(jī)制能夠讓一個(gè)待修復(fù)節(jié)點(diǎn)不再是獨(dú)立地進(jìn)行修復(fù)過(guò)程

6、，而是所有待修復(fù)節(jié)點(diǎn)一起相互協(xié)助完成修復(fù)過(guò)程。本文還針對(duì)MCR機(jī)制，利用網(wǎng)絡(luò)流圖模型計(jì)算出完成修復(fù)所消耗的修復(fù)帶寬下界，經(jīng)過(guò)數(shù)值分析可以得知，MCR所耗費(fèi)的修復(fù)帶寬下界比起現(xiàn)有最好的修復(fù)算法減少10％，同時(shí)存儲(chǔ)量亦減少20％。然后本文為MFR設(shè)計(jì)了相應(yīng)的傳輸算法，并引入強(qiáng)MDS性質(zhì)來(lái)構(gòu)造出隨機(jī)線性編碼算法。最后本文證明了該算法正確性，且達(dá)到已知的修復(fù)帶寬下界，因此該下界是緊致下界，并且該算法是基于MCR機(jī)制的最優(yōu)算法。
　　 (

7、4)非對(duì)稱的多節(jié)點(diǎn)修復(fù)問(wèn)題
　　 已提出的MCR方案假設(shè)所有的恢復(fù)鏈路帶寬消耗都是同樣的，即對(duì)稱修復(fù)。這個(gè)對(duì)稱假設(shè)可能過(guò)強(qiáng)，因?yàn)榉菍?duì)稱的情況不僅在實(shí)際情況中經(jīng)常出現(xiàn)，而且更關(guān)鍵的是，多節(jié)點(diǎn)存儲(chǔ)容錯(cuò)修復(fù)問(wèn)題的最優(yōu)解可能出現(xiàn)在非對(duì)稱狀況下。本文研究了非對(duì)稱的多節(jié)點(diǎn)修復(fù)問(wèn)題，通過(guò)考察該狀況下的網(wǎng)絡(luò)流圖，并利用最大流-最小截定理，給出非對(duì)稱的多節(jié)點(diǎn)修復(fù)時(shí)修復(fù)總帶寬的下界。在發(fā)現(xiàn)該下界等于基于MCR的修復(fù)帶寬下界后，我們得出結(jié)論：多節(jié)點(diǎn)