【摘要】：近年來,隨著信息技術(shù)的飛速發(fā)展,數(shù)據(jù)海量化逐漸成為一種趨勢。如何有效可靠地存儲(chǔ)這些海量數(shù)據(jù)成為一個(gè)亟待解決的問題。針對(duì)傳統(tǒng)集中式存儲(chǔ)在可靠性、可擴(kuò)展性等方面的局限性,分布式存儲(chǔ)系統(tǒng)以其低成本和高可擴(kuò)展性等特點(diǎn),逐漸贏得廣泛關(guān)注。為保證系統(tǒng)的可靠性,分布式存儲(chǔ)系統(tǒng)常采用冗余存儲(chǔ)的方式,以犧牲一定的存儲(chǔ)開銷為代價(jià)來換取系統(tǒng)可靠性。復(fù)制與糾刪碼是分布式存儲(chǔ)系統(tǒng)中2種傳統(tǒng)的冗余存儲(chǔ)策略。為解決復(fù)制策略在存儲(chǔ)開銷方面以及糾刪碼策略在修復(fù)帶寬開銷方面的不足,網(wǎng)絡(luò)編碼技術(shù)被引入到分布式存儲(chǔ)系統(tǒng)中,稱為再生碼,用于均衡系統(tǒng)存儲(chǔ)開銷與修復(fù)帶寬開銷。本文重點(diǎn)針對(duì)基于再生碼的節(jié)點(diǎn)修復(fù)方法進(jìn)行了研究,主要工作如下:(1)基于MSR碼的分布式存儲(chǔ)系統(tǒng)單節(jié)點(diǎn)修復(fù)算法由于人為操作失誤或機(jī)器故障等原因,常常導(dǎo)致分布式存儲(chǔ)系統(tǒng)中某些節(jié)點(diǎn)不可用,無法獲取節(jié)點(diǎn)上存儲(chǔ)的數(shù)據(jù),這樣的節(jié)點(diǎn)稱為失效節(jié)點(diǎn)。為維持系統(tǒng)的可靠性,設(shè)計(jì)一個(gè)良好的節(jié)點(diǎn)修復(fù)機(jī)制對(duì)失效節(jié)點(diǎn)進(jìn)行修復(fù),對(duì)于分布式存儲(chǔ)系統(tǒng)非常重要。本文提出了一種新的基于MSR碼的分布式存儲(chǔ)系統(tǒng)節(jié)點(diǎn)修復(fù)算法,該算法可以對(duì)單節(jié)點(diǎn)進(jìn)行確定性修復(fù)。該算法首先對(duì)系統(tǒng)中的節(jié)點(diǎn)進(jìn)行分組,對(duì)原始文件進(jìn)行分組存儲(chǔ),每個(gè)節(jié)點(diǎn)都有其對(duì)應(yīng)的唯一分組,且各個(gè)分組相互獨(dú)立。其次,每個(gè)分組內(nèi),采用異或算法對(duì)原始文件數(shù)據(jù)塊進(jìn)行編碼存儲(chǔ),不涉及有限域乘法等高級(jí)運(yùn)算。最后,解碼時(shí),各分組可同時(shí)獨(dú)立進(jìn)行,同時(shí),新生節(jié)點(diǎn)對(duì)失效節(jié)點(diǎn)上數(shù)據(jù)進(jìn)行修復(fù)時(shí),只與該分組有關(guān),通過連接該分組其他存活節(jié)點(diǎn)并下載少量數(shù)據(jù)進(jìn)行異或運(yùn)算即可完成精確修復(fù),減小磁盤I/O開銷與修復(fù)復(fù)雜度。(2)基于MBR碼的多節(jié)點(diǎn)協(xié)作修復(fù)算法除了單節(jié)點(diǎn)失效外,在分布式存儲(chǔ)系統(tǒng)中,多節(jié)點(diǎn)同時(shí)失效的情況也時(shí)有發(fā)生,并且,在有些分布式存儲(chǔ)系統(tǒng)中,采用的是延遲修復(fù),即失效節(jié)點(diǎn)數(shù)目達(dá)到一定數(shù)目時(shí),才啟動(dòng)修復(fù)過程,因此,對(duì)分布式存儲(chǔ)系統(tǒng)的多節(jié)點(diǎn)修復(fù)算法進(jìn)行研究也是很有必要的。相比于將多節(jié)點(diǎn)修復(fù)分解為單個(gè)節(jié)點(diǎn)依次修復(fù),多個(gè)節(jié)點(diǎn)協(xié)作修復(fù)能減小修復(fù)帶寬開銷。本文對(duì)基于MBR碼的多節(jié)點(diǎn)協(xié)作修復(fù)方法進(jìn)行了研究,給出了一種新的基于MBR碼的多節(jié)點(diǎn)協(xié)作修復(fù)方法。理論分析表明,本文所提方法達(dá)到了其修復(fù)帶寬的理論最小值。
【圖文】：

第二章 分布式存儲(chǔ)系統(tǒng)概述17圖2.7 存儲(chǔ)-帶寬開銷權(quán)衡曲線上圖，橫軸表示修復(fù)單個(gè)節(jié)點(diǎn)的帶寬開銷，縱軸表示每個(gè)存儲(chǔ)節(jié)點(diǎn)的存儲(chǔ)開銷。由圖，當(dāng)節(jié)點(diǎn)存儲(chǔ)開銷不斷增加時(shí)，修復(fù)帶寬開銷會(huì)不斷減小，達(dá)到某一點(diǎn)時(shí)，不再減小，該點(diǎn)對(duì)應(yīng)該再生碼系統(tǒng)的修復(fù)帶寬下界；同理，當(dāng)修復(fù)帶寬不斷增加時(shí)，，節(jié)點(diǎn)存儲(chǔ)開銷不斷減小，到達(dá)某一點(diǎn)時(shí)，存儲(chǔ)開銷不在減小，該點(diǎn)對(duì)應(yīng)該再生碼系統(tǒng)的存儲(chǔ)開銷下界。這兩個(gè)下界點(diǎn)，分別對(duì)應(yīng)最小修復(fù)帶寬再生(Minimum BandwidthRegeneration, MBR )碼和最小存儲(chǔ)再生(Minimum Storage Regeneration, MSR)碼。由前面存儲(chǔ)開銷閾值函數(shù)，可得到 MSR 點(diǎn)的存儲(chǔ)開銷為和修復(fù)帶寬開銷分別為： , ,( 1)MSR MSRM Mdk k d k (2-12)同理，MBR 點(diǎn)的存儲(chǔ)開銷與修復(fù)帶寬開銷分別為： 2 22 2, ,2 2MBR MBRMd Mdkd k k kd k k (2-13)圖 2.7 對(duì)再生碼存儲(chǔ)開銷與修復(fù)帶寬開銷進(jìn)行分析時(shí)
【學(xué)位授予單位】：西安電子科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類號(hào)】：TP333

【參考文獻(xiàn)】

相關(guān)期刊論文 前1條

1 孫韶輝,王新梅;互聯(lián)網(wǎng)數(shù)據(jù)可靠傳輸中前向糾錯(cuò)技術(shù)[J];長安大學(xué)學(xué)報(bào)(自然科學(xué)版);2002年02期

相關(guān)博士學(xué)位論文 前3條

1 趙浩天;基于網(wǎng)絡(luò)編碼的分布式存儲(chǔ)容錯(cuò)及擴(kuò)容問題研究[D];中國科學(xué)技術(shù)大學(xué);2013年

2 王禹;分布式存儲(chǔ)系統(tǒng)中的數(shù)據(jù)冗余與維護(hù)技術(shù)研究[D];華南理工大學(xué);2011年

3 胡q

本文編號(hào)：2658141