基于網(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ù)海量化成為了一種趨勢。分布式存儲(chǔ)以網(wǎng)絡(luò)技術(shù)為基礎(chǔ)，利用小型服務(wù)器甚至PC機(jī)來搭建存儲(chǔ)池，從而以其廉價(jià)性和高擴(kuò)展性等特點(diǎn)而適用于對數(shù)據(jù)的海量存儲(chǔ)。但是由于分布式存儲(chǔ)節(jié)點(diǎn)可用性并不高，因此如何保證高數(shù)據(jù)可靠性就成為亟待解決的問題。在存儲(chǔ)系統(tǒng)中，保證數(shù)據(jù)可靠性主要依賴于數(shù)據(jù)容錯(cuò)技術(shù)，而數(shù)據(jù)容錯(cuò)的關(guān)鍵性問題是如何進(jìn)行有效的數(shù)據(jù)修復(fù)，即存活節(jié)點(diǎn)盡可能少地消耗系統(tǒng)

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

3、流圖分析。另外，本文還針對分布式存儲(chǔ)修復(fù)機(jī)制的特點(diǎn)，專門在網(wǎng)絡(luò)流圖中引入了三段節(jié)點(diǎn)，精確刻畫了分布式存儲(chǔ)節(jié)點(diǎn)在修復(fù)過程中的特性。最后，本文利用該數(shù)學(xué)模型，證明了分布式存儲(chǔ)容錯(cuò)中修復(fù)過程并不需要有存活節(jié)點(diǎn)之間的數(shù)據(jù)傳輸過程，從而為后面的修復(fù)機(jī)制的設(shè)計(jì)提供了一定的理論基礎(chǔ)。
　　 (2)一種基于彈性的節(jié)點(diǎn)修復(fù)機(jī)制
　　 在分布式存儲(chǔ)容錯(cuò)修復(fù)問題上，已有的修復(fù)機(jī)制限制所有的待修復(fù)節(jié)點(diǎn)必須連接同樣多的d個(gè)存活節(jié)點(diǎn)來完成修復(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)來完成修復(fù)過程，不同的新節(jié)點(diǎn)Yi和Yj所對應(yīng)的di和dj無需相等。這樣可以使得新節(jié)點(diǎn)的修復(fù)過程更加靈活，從而適應(yīng)不同的網(wǎng)絡(luò)狀況。同時(shí)，本文還針對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ī)制都是針對于單節(jié)點(diǎn)修復(fù)問題的，沒有專門針對多節(jié)點(diǎn)同時(shí)修復(fù)的問題進(jìn)行研究，然而多節(jié)點(diǎn)的同時(shí)修復(fù)問題在實(shí)際分布式存儲(chǔ)系統(tǒng)中非常常見。本文針對多節(jié)點(diǎn)同時(shí)修復(fù)的問題，提出了一種基于相互協(xié)作的多節(jié)點(diǎn)修復(fù)機(jī)制MCR，該機(jī)制能夠讓一個(gè)待修復(fù)節(jié)點(diǎn)不再是獨(dú)立地進(jìn)行修復(fù)過程

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

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