基于局部性編碼的分布式存儲容錯機制研究.pdf

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

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

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

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