基于網(wǎng)絡編碼的分布式存儲容錯中修復機制研究.pdf

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

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

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

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

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

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

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