本文關(guān)鍵詞：基于FRC碼的分布式存儲(chǔ)編碼優(yōu)化算法研究

  更多相關(guān)文章： 分布式存儲(chǔ) 糾刪編碼 分片復(fù)制碼 楊氏矩陣 禁忌搜索

【摘要】：隨著計(jì)算機(jī)技術(shù)的快速進(jìn)步,數(shù)據(jù)的爆炸性增長(zhǎng)迫使人們對(duì)計(jì)算機(jī)存儲(chǔ)系統(tǒng)提出了越來(lái)越高的要求。分布式存儲(chǔ)系統(tǒng)由于其低廉的價(jià)格和優(yōu)異的性能而被人們所青睞。由分布式存儲(chǔ)系統(tǒng)所衍生的云存儲(chǔ)技術(shù)被各大IT企業(yè)采用且全面走向商業(yè)化。然而,網(wǎng)絡(luò)存儲(chǔ)節(jié)點(diǎn)的不可靠性使得系統(tǒng)需使用大量的存儲(chǔ)空間存放冗余數(shù)據(jù),同時(shí)在節(jié)點(diǎn)失效時(shí)進(jìn)行高頻的節(jié)點(diǎn)修復(fù)。這嚴(yán)重浪費(fèi)了系統(tǒng)有限的網(wǎng)絡(luò)帶寬和存儲(chǔ)資源,降低存儲(chǔ)服務(wù)的質(zhì)量。因此,分布式存儲(chǔ)系統(tǒng)不僅需要保證容多節(jié)點(diǎn)故障,而且需要降低修復(fù)過(guò)程中的網(wǎng)絡(luò)消耗。于是,各種容錯(cuò)編碼技術(shù),尤其是再生碼,得到深入研究。文獻(xiàn)[1]提出一種Fractional Repetition(分片復(fù)制)編碼,在修復(fù)過(guò)程中不需要編碼計(jì)算,帶寬消耗最小,并且具有比最小帶寬再生(MBR)編碼更優(yōu)的存儲(chǔ)能力。已有的FRC編碼往往依賴于特定的組合構(gòu)造,僅僅適用于有限的參數(shù)情形。對(duì)于一般參數(shù)下情形,如何構(gòu)造最優(yōu)的存儲(chǔ)能力的FRC編碼被認(rèn)為是一個(gè)開(kāi)放性的問(wèn)題。本文對(duì)基于分片復(fù)制碼(FRC碼)的分布式存儲(chǔ)系統(tǒng),抽象出編碼矩陣的數(shù)學(xué)模型,提出了在任意參數(shù)下給出FRC碼數(shù)據(jù)分布策略的方法,使得用戶在取數(shù)據(jù)時(shí)需連接的存儲(chǔ)節(jié)點(diǎn)數(shù)量達(dá)到最小。本文的主要工作在以下幾個(gè)方面。(1)為了找到FRC碼的最優(yōu)編碼矩陣,本文提出了基于楊氏矩陣遍歷搜索最優(yōu)編碼矩陣的方法。首先將FRC碼抽象為布爾矩陣,然后利用楊氏矩陣和布爾矩陣間的雙射實(shí)現(xiàn)FRC碼編碼矩陣與楊氏矩陣間的對(duì)應(yīng),之后根據(jù)楊氏矩陣的特殊性質(zhì)提出了幾種剪枝優(yōu)化方法。本文提出的枚舉算法能在任意參數(shù)下完整的遍歷存在最優(yōu)FRC碼的編碼矩陣集合,且算法的剪枝優(yōu)化方法能減少95%以上的搜索項(xiàng)。通過(guò)實(shí)驗(yàn)表明算法的效果較好。(2)在FRC編碼的布爾矩陣描述的基礎(chǔ)上,本文提出了一種在基于布爾矩陣交換操作的禁忌搜索算法。根據(jù)FRC碼的性質(zhì),本文研究了其存儲(chǔ)能力與編碼矩陣中1的分布間的關(guān)系,提出并證明了FRC碼存儲(chǔ)能力與編碼矩陣中的充分條件定理。在此基礎(chǔ)上,本文提出了以C4圈計(jì)數(shù)為啟發(fā)式準(zhǔn)則的禁忌搜索算法。算法可在任意參數(shù)下給出具有最優(yōu)存儲(chǔ)能力的FRC碼編碼矩陣。同時(shí)本文針對(duì)算法的核心運(yùn)算,提出了更快速的C4圈計(jì)數(shù)矩陣法,降低了算法的時(shí)間復(fù)雜度。實(shí)驗(yàn)表明,算法以不同的編碼矩陣為初始搜索節(jié)點(diǎn)都能得到存儲(chǔ)能力基本相同的編碼矩陣,且結(jié)果編碼矩陣的存儲(chǔ)能力較為接近上界。
【學(xué)位授予單位】：天津理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類(lèi)號(hào)】：TP333

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條

1 王征;劉心松;李美安;;企業(yè)信息分布式存儲(chǔ)的熱點(diǎn)處理策略[J];計(jì)算機(jī)集成制造系統(tǒng);2006年09期

2 李磊;沈海斌;黃凱;嚴(yán)曉浪;Han Sangil;Ahmed A Jerraya;;分布式存儲(chǔ)管理在多核設(shè)計(jì)中的高層建模[J];電子與信息學(xué)報(bào);2008年11期

3 劉翔;汪海玲;;分布式存儲(chǔ)中的一種數(shù)據(jù)放置策略[J];計(jì)算機(jī)與數(shù)字工程;2009年05期

4 陳衛(wèi)衛(wèi);吳海佳;胥光輝;;分布式存儲(chǔ)中文件分割的最優(yōu)化模型[J];解放軍理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2010年04期

5 崔忠強(qiáng);左德承;張展;;在云間可重構(gòu)的分布式存儲(chǔ)[J];系統(tǒng)工程理論與實(shí)踐;2011年S2期

6 郝杰;逯彥博;劉鑫吉;夏樹(shù)濤;;分布式存儲(chǔ)中的再生碼綜述[J];重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年01期

7 唐京偉;;基于云計(jì)算的分布式存儲(chǔ)技術(shù)[J];中國(guó)傳媒科技;2013年15期

8 郭棟;王偉;曾國(guó)蓀;;基于一致性樹(shù)分布的數(shù)據(jù)分布式存儲(chǔ)方法[J];計(jì)算機(jī)應(yīng)用;2013年12期

9 蘇李亮;王云福;侯斌;;海量設(shè)計(jì)文檔分布式存儲(chǔ)及負(fù)載均衡的研究與實(shí)現(xiàn)[J];電信科學(xué);2013年12期

10 謝然;;敢問(wèn)存儲(chǔ)之路在何方?見(jiàn)分布式存儲(chǔ)搖曳在數(shù)據(jù)枝頭[J];互聯(lián)網(wǎng)周刊;2014年02期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前7條

1 蘇李亮;王云福;侯斌;;海量設(shè)計(jì)文檔分布式存儲(chǔ)及負(fù)載均衡的研究與實(shí)現(xiàn)[A];2013電力行業(yè)信息化年會(huì)論文集[C];2013年

2 蘇李亮;王云福;侯斌;;海量設(shè)計(jì)文檔分布式存儲(chǔ)及負(fù)載均衡的研究與實(shí)現(xiàn)[A];2013電力行業(yè)信息化年會(huì)論文集[C];2013年

3 鄭文武;李先緒;黃植勤;邱紅飛;;云存儲(chǔ)關(guān)鍵技術(shù)[A];2012全國(guó)無(wú)線及移動(dòng)通信學(xué)術(shù)大會(huì)論文集（下）[C];2012年

4 蔣軼林;郭淑琴;;分布式存儲(chǔ)在數(shù)字集群移動(dòng)通信系統(tǒng)中的應(yīng)用[A];浙江省電子學(xué)會(huì)2013學(xué)術(shù)年會(huì)論文集[C];2013年

5 姜繼忱;陳鋼;;P2P之路——締造“分布式對(duì)等”的Internet3.0[A];全面建設(shè)小康社會(huì)：中國(guó)科技工作者的歷史責(zé)任——中國(guó)科協(xié)2003年學(xué)術(shù)年會(huì)論文集（下）[C];2003年

6 付偉;肖儂;盧錫城;;QoS感知的副本放置問(wèn)題研究綜述[A];第15屆全國(guó)信息存儲(chǔ)技術(shù)學(xué)術(shù)會(huì)議論文集[C];2008年

7 張彥;劉欣然;徐慧彬;;一種基于虛擬計(jì)算環(huán)境的分布式存儲(chǔ)體系結(jié)構(gòu)[A];2009全國(guó)計(jì)算機(jī)網(wǎng)絡(luò)與通信學(xué)術(shù)會(huì)議論文集[C];2009年

中國(guó)重要報(bào)紙全文數(shù)據(jù)庫(kù) 前8條

1 京東架構(gòu)委員會(huì)主任 云平臺(tái)首席架構(gòu)師 系統(tǒng)技術(shù)部負(fù)責(zé)人 劉海鋒;京東:分布式存儲(chǔ)體系成為業(yè)務(wù)基石[N];中國(guó)信息化周報(bào);2014年

2 《網(wǎng)絡(luò)世界》記者 于翔;京東分布式存儲(chǔ)體系研發(fā)歷程[N];網(wǎng)絡(luò)世界;2014年

3 《網(wǎng)絡(luò)世界》記者 于翔;融合一體機(jī)投入大規(guī)模商用[N];網(wǎng)絡(luò)世界;2013年

4 記者 余榮華;大數(shù)據(jù)，，催生大變革[N];人民日?qǐng)?bào);2014年

5 本報(bào)記者 張佳星;新生產(chǎn)業(yè)布局如何“云”中索驥[N];科技日?qǐng)?bào);2014年

6 本報(bào)記者 甘露;物聯(lián)網(wǎng)讓管理更美妙[N];計(jì)算機(jī)世界;2013年

7 本報(bào)記者 郭濤;華為幫用戶定制HANA一體機(jī)[N];中國(guó)計(jì)算機(jī)報(bào);2013年

8 臨江;手機(jī)瀏覽器,3G時(shí)代的采礦機(jī)？[N];人民郵電;2009年

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前8條

1 胡q

本文編號(hào)：1156176