隨著網(wǎng)絡(luò)與信息技術(shù)的飛速發(fā)展,分布式存儲系統(tǒng)在成本、性能、可擴(kuò)展性以及存儲容量等方面已取得了快速進(jìn)步,但同時在容錯性方面也面臨著巨大的挑戰(zhàn):隨著節(jié)點規(guī)模的不斷擴(kuò)大,分布式存儲系統(tǒng)中節(jié)點出現(xiàn)失效的概率會大大增加,而節(jié)點失效導(dǎo)致的數(shù)據(jù)丟失會造成災(zāi)難性的后果。因此,如何設(shè)計高效、可靠的分布式容錯存儲技術(shù)是當(dāng)前亟需解決的關(guān)鍵問題。相比于副本技術(shù),基于糾刪碼的數(shù)據(jù)冗余技術(shù)能夠在保證相同容錯能力的基礎(chǔ)上,極大地降低存儲開銷,成為了當(dāng)前分布式存儲領(lǐng)域研究的熱點�；诩m刪碼的分布式容錯存儲技術(shù)面臨的主要挑戰(zhàn)在于:(1)現(xiàn)有的糾刪碼數(shù)據(jù)寫入方法將數(shù)據(jù)分塊、編碼與傳輸?shù)热蝿?wù)集中于同一節(jié)點,存在較為嚴(yán)重的瓶頸問題。隨著數(shù)據(jù)量的不斷增大,瓶頸問題更加突出。(2)節(jié)點規(guī)模的不斷增加使得多點失效的概率明顯增大,在多點修復(fù)過程中現(xiàn)有的糾刪碼數(shù)據(jù)修復(fù)方法修復(fù)效率較低,修復(fù)開銷較大。(3)糾刪碼更新過程中涉及較多的數(shù)據(jù)傳輸與復(fù)雜的數(shù)據(jù)計算,現(xiàn)有的糾刪碼更新方法需要消耗較大的網(wǎng)絡(luò)開銷,導(dǎo)致了較低的更新效率。為此,本文圍繞實現(xiàn)基于糾刪碼的高效低成本存儲服務(wù)這一目標(biāo),分別針對基于糾刪碼的數(shù)據(jù)寫入、數(shù)據(jù)修復(fù)和數(shù)據(jù)更新技術(shù)展開深入研究。針對已有的糾刪碼數(shù)據(jù)寫入方法因單點瓶頸而導(dǎo)致寫入效率較低的問題,本文研究提出了一種基于分組的分布式流水線數(shù)據(jù)寫入方法D2CP。D2CP采用一種基于分組的分布式框架以維護(hù)源節(jié)點、數(shù)據(jù)節(jié)點與編碼節(jié)點之間的鄰居關(guān)系。通過一種基于一致性哈希的數(shù)據(jù)放置算法,D2CP將節(jié)點位置與數(shù)據(jù)存儲位置進(jìn)行哈希計算以提高數(shù)據(jù)放置效率。為了降低寫入開銷,D2CP采用一種基于分組的數(shù)據(jù)發(fā)送調(diào)度算法以動態(tài)調(diào)度源節(jié)點的數(shù)據(jù)發(fā)送。為了提高編碼計算效率,D2CP采用一種基于協(xié)作的編碼數(shù)據(jù)生成算法以協(xié)作方式組織編碼節(jié)點之間的計算�；贖DFS-RAID平臺的測試結(jié)果表明,與目前已有的糾刪碼數(shù)據(jù)寫入方法相比,在多種不同參數(shù)設(shè)置情況下,D2CP的數(shù)據(jù)寫入時間平均減少了26%,網(wǎng)絡(luò)開銷平均降低了24.5%,顯著提升了糾刪碼數(shù)據(jù)寫入效率并降低了網(wǎng)絡(luò)開銷。在多點失效場景中,集中式修復(fù)方法存在單點瓶頸的問題,而分布式修復(fù)方法存在修復(fù)開銷大的問題。兩種方法的修復(fù)效率隨著數(shù)據(jù)量的增大而顯著下降。為此,本文研究提出了一種基于協(xié)作的自適應(yīng)數(shù)據(jù)修復(fù)方法DARS。DARS采用一種星型結(jié)構(gòu)與樹型結(jié)構(gòu)結(jié)合的自適應(yīng)數(shù)據(jù)修復(fù)模型以同時支持單點失效和多點失效的修復(fù)。通過一種帶寬感知的節(jié)點選擇算法,DARS選擇具有更高可用帶寬的節(jié)點以保證節(jié)點之間的高可用帶寬。通過一種線型結(jié)構(gòu)的數(shù)據(jù)傳輸算法,DARS有效組織提供者節(jié)點與中繼節(jié)點之間的數(shù)據(jù)傳輸。通過一種基于中心節(jié)點的數(shù)據(jù)分發(fā)算法,DARS有效組織協(xié)調(diào)者節(jié)點與新生節(jié)點之間的數(shù)據(jù)交互,進(jìn)而保證節(jié)點之間的數(shù)據(jù)傳輸效率。為了最小化網(wǎng)絡(luò)代價,DARS通過條帶內(nèi)的懶惰修復(fù)算法自適應(yīng)地調(diào)整失效數(shù)據(jù)的修復(fù)時機(jī),并動態(tài)調(diào)整提供者節(jié)點的數(shù)目從而保證負(fù)載的均衡性�；贖DFS-RAID平臺的測試結(jié)果表明,與目前已有的糾刪碼數(shù)據(jù)修復(fù)方法TSR和CORE相比,在多種不同參數(shù)設(shè)置情況下,DARS的數(shù)據(jù)修復(fù)時間平均減少了29%和55%,顯著提升了糾刪碼數(shù)據(jù)修復(fù)效率。更新過程中復(fù)雜的數(shù)據(jù)傳輸與計算使得已有的糾刪碼單點更新方法效率隨著數(shù)據(jù)規(guī)模的增長而顯著下降。為此,本文研究提出了一種基于樹型結(jié)構(gòu)的單點數(shù)據(jù)更新方法TA-Update。TA-Update采用一種編碼參數(shù)無關(guān)的更新樹結(jié)構(gòu)維護(hù)節(jié)點之間的連接關(guān)系,以支持不同參數(shù)的編碼算法。通過一種機(jī)架感知的樹型構(gòu)建算法,TA-Update構(gòu)建了一顆最優(yōu)更新樹,以保證節(jié)點之間數(shù)據(jù)傳輸?shù)母咝�。通過一種自頂向下的流水線數(shù)據(jù)處理算法,TA-Update將節(jié)點之間的數(shù)據(jù)傳輸流水線化并將更新計算任務(wù)分布在多個不同的節(jié)點中。TA-Update通過一種基于緩存的失效處理算法高效修復(fù)失效數(shù)據(jù)并恢復(fù)暫停的更新過程,以提高方法的適應(yīng)性�；贖DFS-RAID平臺的測試結(jié)果表明,與目前已有的糾刪碼數(shù)據(jù)單點更新方法相比,TA-Update在無節(jié)點失效情況下的更新時間平均減少了33%,在單點失效情況下的更新時間平均減少了44%,顯著提升了糾刪碼單點更新效率。多點更新過程中,順序更新的方式導(dǎo)致已有的更新方法更新開銷較大,更新效率隨著數(shù)據(jù)量的增大而顯著下降。為此,本文研究提出了一種基于分組結(jié)構(gòu)的多點更新方法Group-U。Group-U采用基于分組的更新框架以有效組織節(jié)點之間的鄰居關(guān)系。通過一種負(fù)載感知的分組算法,Group-U依據(jù)更新負(fù)載自適應(yīng)地為多個待更新節(jié)點選擇合理的分組方式與分組大小。通過一種混合更新算法,Group-U依據(jù)時間間隔閾值有效組織多個更新節(jié)點的更新時機(jī),從而保證數(shù)據(jù)節(jié)點的數(shù)據(jù)一致性和編碼節(jié)點的更新效率。通過一種基于緩存的失效處理算法,Group-U有效處理更新過程中出現(xiàn)的節(jié)點失效并保證更新過程的順利進(jìn)行。基于HDFS-RAID平臺的測試結(jié)果表明,與目前已有的糾刪碼數(shù)據(jù)多點更新方法相比,在多種不同參數(shù)設(shè)置情況下,Group-U的數(shù)據(jù)更新時間平均減少了44%,更新開銷平均降低了12%,顯著提升了糾刪碼多點更新效率。
【學(xué)位單位】：國防科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：博士
【學(xué)位年份】：2016
【中圖分類】：TP333
【部分圖文】：

多點更新方法更新的方式導(dǎo)致已有的更著下降。為此，本文研究roup-U 采用基于分組的更感知的分組算法，Group-的分組方式與分組大小。有效組織多個更新節(jié)點的點的更新效率。通過一種中出現(xiàn)的節(jié)點失效并保證果表明，與目前已有的況下，Group-U 顯著提升1.4 論文結(jié)構(gòu)織結(jié)構(gòu)如圖 1.4 所示。

采用的隨機(jī)放置方法。完成編碼任務(wù)，數(shù)據(jù)以編碼的形式寫入系寫入方式，直接編碼方式無需同時維護(hù)副寫入系統(tǒng)時完成編碼即可。直接編碼主要數(shù)據(jù)上傳。其中，數(shù)據(jù)分塊是指數(shù)據(jù)對象；數(shù)據(jù)編碼是指編碼節(jié)點將分割的數(shù)據(jù)塊上傳是指編碼節(jié)點將完成編碼的數(shù)據(jù)塊和過程中原始數(shù)據(jù)對象被分割為 k 個數(shù)據(jù)算產(chǎn)生 r 個編碼塊。最后，k 個數(shù)據(jù)塊和依據(jù)數(shù)據(jù)寫入過程中三個步驟的執(zhí)行情式和分布式數(shù)據(jù)寫入方法。12分布式存儲系統(tǒng)

我們通過一個條帶中的編碼過程來了解整個數(shù)據(jù)對般性，我們將 k 個數(shù)據(jù)塊表示為1{ , , }ko o。在一個分組碼點參與：存儲原始數(shù)據(jù)塊的存儲節(jié)點，存儲局部編碼塊的局編碼塊的全局編碼節(jié)點。其中，局部編碼塊是由一組數(shù)編碼塊則由所有的數(shù)據(jù)塊編碼生成。我們可以用參數(shù)(k,g,l其中，k 表示原始數(shù)據(jù)塊的總數(shù)目，g 表示組數(shù)，l 表示局示全局編碼塊數(shù)目。在編碼過程中，k 個數(shù)據(jù)塊1{ , , }ko o被1, / ,1 , /, ), ,( , , ))k g g g k g o o o。 其 中 ， 第 i 組 的 局 部 編 碼 /)l g，o 個全局編碼塊表示為1( , , )op p。第 i 組的第 j 個局部3.1 生成，全局編碼塊ip 通過公式 3.2 生成。/, , , ,1* ,1 ,1 /k gi j i j x i xx o i g j l g (3.1)/*, , , , ,1 1 1* * ,1g k g gj j i x j x i j i ji x i o p j o (3.2)

本文編號：2853126