本文關(guān)鍵詞：容錯(cuò)存儲(chǔ)系統(tǒng)中的MDS陣列碼研究

  更多相關(guān)文章： 陣列碼 糾刪碼 存儲(chǔ)系統(tǒng) 磁盤陣列 容錯(cuò)

【摘要】：隨著現(xiàn)代存儲(chǔ)系統(tǒng)在規(guī)模和復(fù)雜性上的不斷增長(zhǎng),硬盤(節(jié)點(diǎn))故障已經(jīng)成為系統(tǒng)運(yùn)行中的一個(gè)日常事件。為了防止各類硬件故障造成數(shù)據(jù)丟失,存儲(chǔ)系統(tǒng)一般使用兩種方式對(duì)數(shù)據(jù)進(jìn)行保護(hù),即多路鏡像和糾刪編碼。多路鏡像雖然實(shí)現(xiàn)簡(jiǎn)單,但這種方式的存儲(chǔ)效率通常較低;而糾刪碼技術(shù)由于可以靈活地調(diào)節(jié)存儲(chǔ)效率而被越來(lái)越多的存儲(chǔ)系統(tǒng)采用。最大距離可分的(MDS)陣列碼是一類主要面向存儲(chǔ)系統(tǒng)的糾刪碼,這類碼可以使用最少的冗余來(lái)提供特定的容錯(cuò)能力,并且其編解碼過(guò)程只需要用到簡(jiǎn)單的異或和循環(huán)移位運(yùn)算,因此在近幾年受到了越來(lái)越多的關(guān)注。本文主要針對(duì)糾雙刪和糾三刪的MDS陣列碼進(jìn)行了深入的研究,并取得了以下幾點(diǎn)成果:1、RAID-6正在逐步取代RAID-5成為RAID的主流形式,因?yàn)樗梢栽趦蓚€(gè)磁盤同時(shí)故障的情況下也能夠恢復(fù)數(shù)據(jù)。有許多糾雙刪的MDS陣列碼是專為實(shí)現(xiàn)RAID-6設(shè)計(jì)的,但是這些碼都有它們各自的局限性。本文研究了其中一種有代表性的碼(Blaum-Roth碼),分析其優(yōu)勢(shì)及局限性,并對(duì)其編解碼算法進(jìn)行改進(jìn)。改進(jìn)后的Blaum-Roth碼具有以下優(yōu)秀特性:1)編碼復(fù)雜度達(dá)到理論下界;2)解碼復(fù)雜度接近理論下界;3)可以在幾乎沒(méi)有性能損失的前提下實(shí)現(xiàn)RAID-6的可擴(kuò)展性。與其它最常用于RAID-6的MDS陣列碼相比,改進(jìn)后的Blaum-Roth碼更適于構(gòu)建高性能并且可伸縮的RAID-6磁盤陣列。2、糾雙刪的最低密度MDS陣列碼是一類結(jié)構(gòu)優(yōu)美的糾刪碼,具有最優(yōu)的編碼、解碼和更新復(fù)雜度。然而,現(xiàn)有的這類碼或者對(duì)碼長(zhǎng)的限制過(guò)于嚴(yán)格,或者編碼規(guī)則沒(méi)有明顯的幾何規(guī)律,這使得它們的實(shí)用性較差。為此,本文構(gòu)造了一種新的糾雙刪最低密度MDS陣列碼,稱為對(duì)稱碼。對(duì)稱碼的編碼、解碼和更新復(fù)雜度均達(dá)到最優(yōu),而且碼長(zhǎng)可以是素?cái)?shù)或者素?cái)?shù)減1。此外,對(duì)稱碼在恢復(fù)單個(gè)刪除列時(shí)所需的I/O開銷比大多數(shù)最低密度MDS陣列碼要少,并且在碼長(zhǎng)較短時(shí)這個(gè)開銷可以接近理論下界。3、最低密度MDS陣列碼由于其編碼和更新復(fù)雜度的最優(yōu)性而廣受歡迎。然而,目前已知的絕大多數(shù)最低密度MDS陣列碼都只能糾兩個(gè)刪除列,雖然有少部分例外,但是它們對(duì)碼長(zhǎng)的限制非常嚴(yán)格。例如,現(xiàn)有的糾三刪的最低密度MDS陣列碼通常要求碼長(zhǎng)為p(或p-1),其中p必須是滿足以下條件的素?cái)?shù):2為GF(p)的一個(gè)本原元且p-1能夠被3整除。如此嚴(yán)格的碼長(zhǎng)限制使得這些碼幾乎無(wú)法被實(shí)際存儲(chǔ)系統(tǒng)采用。為此,本文構(gòu)造了一種實(shí)用的糾三刪的最低密度MDS陣列碼,能夠糾正碼字中的任意三個(gè)刪除列或者一個(gè)刪除列連同一個(gè)差錯(cuò)列。這類碼的解碼復(fù)雜度可以達(dá)到或接近理論下界(取決于刪除模式),并且碼長(zhǎng)可以是p或p+1,其中p是一個(gè)奇素?cái)?shù)。這是目前已知最具實(shí)用價(jià)值的糾三刪的最低密度MDS陣列碼。4、廣義RDP碼被認(rèn)為是目前最實(shí)用和最高效的強(qiáng)系統(tǒng)的MDS碼,因?yàn)槠渚幋a復(fù)雜度達(dá)到了理論下界,并且可以支持任意碼長(zhǎng)。然而,廣義RDP碼的現(xiàn)有解碼算法的解碼復(fù)雜度離理論下界有點(diǎn)遠(yuǎn),還有一定的改進(jìn)空間。本文對(duì)糾三刪的廣義RDP碼的解碼算法進(jìn)行了研究,并提出了一種針對(duì)三個(gè)刪除列的改進(jìn)的解碼算法。與原有的解碼算法相比,本文提出的算法具有明顯更低的解碼復(fù)雜度,且當(dāng)碼長(zhǎng)不等于10或11時(shí)這個(gè)復(fù)雜度最多只比理論下界高出8個(gè)百分點(diǎn)。
【學(xué)位授予單位】：華中科技大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP333

【相似文獻(xiàn)】

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

1 李紅;藍(lán)光存儲(chǔ)系統(tǒng) 光盤容量高達(dá)23G[J];信息記錄材料;2004年01期

2 ;存儲(chǔ)系統(tǒng) 金融行業(yè)應(yīng)用卓越獎(jiǎng) 醫(yī)療行業(yè)應(yīng)用卓越獎(jiǎng)[J];每周電腦報(bào);2004年20期

3 諾拉;EMC Symmetrix DMX-3存儲(chǔ)系統(tǒng) 超大容量 高速存取[J];中國(guó)計(jì)算機(jī)用戶;2005年31期

4 謝世誠(chéng);;浪潮推出4Gb光纖存儲(chǔ)系統(tǒng)[J];微型機(jī)與應(yīng)用;2006年07期

5 ;昆騰分級(jí)存儲(chǔ)系統(tǒng)[J];軟件世界;2009年11期

6 ;超低功耗云存儲(chǔ)系統(tǒng)或被地方政府看好[J];中國(guó)有線電視;2013年08期

7 湯赫男;;云存儲(chǔ)系統(tǒng)的分析與應(yīng)用研究[J];計(jì)算機(jī)光盤軟件與應(yīng)用;2013年24期

8 諶偉;;云存儲(chǔ)系統(tǒng)的分析與應(yīng)用探討[J];數(shù)字技術(shù)與應(yīng)用;2013年10期

9 雅君;跟上企業(yè)的匆匆腳步——利用HP SureStoreEXP256構(gòu)筑企業(yè)存儲(chǔ)系統(tǒng)[J];中國(guó)計(jì)算機(jī)用戶;2000年08期

10 賈莉;;Symmetrix8000實(shí)現(xiàn)19TB存儲(chǔ)[J];每周電腦報(bào);2000年18期

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

1 趙志剛;;存儲(chǔ)系統(tǒng)在企業(yè)信息化中的應(yīng)用[A];2005年安徽通信論文集[C];2006年

2 黃曉峰;張杰;;礦井信息中心存儲(chǔ)系統(tǒng)設(shè)計(jì)[A];安全高效礦井機(jī)電裝備及信息化技術(shù)——陜西省煤炭學(xué)會(huì)學(xué)術(shù)年會(huì)論文集（2011）[C];2011年

3 孫哲;李昌銀;;構(gòu)建核電高可用云存儲(chǔ)系統(tǒng)[A];2012電力行業(yè)信息化年會(huì)優(yōu)秀論文專輯[C];2012年

4 焦超;周天彤;李祥學(xué);李建華;;面向?yàn)?zāi)備的高性能可信存儲(chǔ)系統(tǒng)設(shè)計(jì)[A];第十一屆保密通信與信息安全現(xiàn)狀研討會(huì)論文集[C];2009年

5 汪位龍;;設(shè)計(jì)院存儲(chǔ)系統(tǒng)建設(shè)初探[A];中國(guó)公路學(xué)會(huì)計(jì)算機(jī)應(yīng)用分會(huì)2004年年會(huì)學(xué)術(shù)論文集[C];2004年

6 梅松竹;李宗伯;;Storage 7000系列混合存儲(chǔ)系統(tǒng)分析[A];2009年中國(guó)高校通信類院系學(xué)術(shù)研討會(huì)論文集[C];2009年

7 王克敏;張璽;胡江凱;王毅濤;;NWP資料歸檔方法及其存儲(chǔ)系統(tǒng)的應(yīng)用[A];中國(guó)氣象學(xué)會(huì)2006年年會(huì)“中尺度天氣動(dòng)力學(xué)、數(shù)值模擬和預(yù)測(cè)”分會(huì)場(chǎng)論文集[C];2006年

8 孫哲;李昌銀;;DeDu:基于云計(jì)算的冗余刪除存儲(chǔ)系統(tǒng)[A];電力行業(yè)新一代信息技術(shù)研討會(huì)論文集[C];2011年

9 高小伍;黨齊民;林晨;;校園網(wǎng)存儲(chǔ)系統(tǒng)的研究與實(shí)現(xiàn)[A];中國(guó)高等教育學(xué)會(huì)教育信息化分會(huì)第十次學(xué)術(shù)年會(huì)論文集[C];2010年

10 宮海林;郭長(zhǎng)國(guó);苑洪亮;王懷民;;支持事務(wù)的非結(jié)構(gòu)化數(shù)據(jù)聚合存儲(chǔ)系統(tǒng)GSL[A];2006年全國(guó)開放式分布與并行計(jì)算機(jī)學(xué)術(shù)會(huì)議論文集（三）[C];2006年

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

1 ;第三季度中國(guó)存儲(chǔ)系統(tǒng)市場(chǎng)達(dá)19.1億元[N];中國(guó)高新技術(shù)產(chǎn)業(yè)導(dǎo)報(bào);2005年

2 本報(bào)記者 薛斐;服務(wù)：存儲(chǔ)系統(tǒng)的靈魂[N];計(jì)算機(jī)世界;2002年

3 單群一;惠普推出全新一體化存儲(chǔ)系統(tǒng)[N];中國(guó)稅務(wù)報(bào);2007年

4 ;浪潮推出4Gb光纖存儲(chǔ)系統(tǒng)[N];人民郵電;2006年

5 ;今年第二季度 存儲(chǔ)系統(tǒng)市場(chǎng)價(jià)值達(dá)12.6億元[N];人民郵電;2006年

6 郭;日立推出普及型存儲(chǔ)系統(tǒng)[N];計(jì)算機(jī)世界;2007年

7 陳耀光;朗登 扛起存儲(chǔ)系統(tǒng)設(shè)計(jì)院的大旗[N];中國(guó)企業(yè)報(bào);2001年

8 ;富士通存儲(chǔ)系統(tǒng)全面升級(jí)[N];網(wǎng)絡(luò)世界;2009年

9 ;EMC亞洲生產(chǎn)制造中心落戶深圳[N];網(wǎng)絡(luò)世界;2009年

10 臨履;存儲(chǔ)系統(tǒng)有了“設(shè)計(jì)院”[N];網(wǎng)絡(luò)世界;2001年

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

1 趙雨虹;云存儲(chǔ)系統(tǒng)資源調(diào)度技術(shù)研究[D];華中科技大學(xué);2015年

2 王福偉;列存儲(chǔ)系統(tǒng)的數(shù)據(jù)安全與網(wǎng)絡(luò)性能優(yōu)化模型研究[D];燕山大學(xué);2016年

3 張菁;大規(guī)模分布式糾刪碼存儲(chǔ)系統(tǒng)中的高效數(shù)據(jù)傳輸技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2015年

4 沈志榮;糾刪碼存儲(chǔ)系統(tǒng)性能優(yōu)化研究[D];清華大學(xué);2015年

5 黃志杰;容錯(cuò)存儲(chǔ)系統(tǒng)中的MDS陣列碼研究[D];華中科技大學(xué);2016年

6 陸承濤;存儲(chǔ)系統(tǒng)性能管理問(wèn)題的研究[D];華中科技大學(xué);2010年

7 聶雪軍;內(nèi)容感知存儲(chǔ)系統(tǒng)中信息信息生命周期管理關(guān)鍵技術(shù)研究[D];華中科技大學(xué);2011年

8 羅東健;大規(guī)模存儲(chǔ)系統(tǒng)高可靠性關(guān)鍵技術(shù)研究[D];華中科技大學(xué);2011年

9 聶雪軍;內(nèi)容感知存儲(chǔ)系統(tǒng)中信息生命周期管理關(guān)鍵技術(shù)研究[D];華中科技大學(xué);2010年

10 王鵬;低密度奇偶校驗(yàn)碼應(yīng)用于存儲(chǔ)系統(tǒng)的關(guān)鍵技術(shù)研究[D];華中科技大學(xué);2013年

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

1 馮漢超;基于Hadoop的分布式副本策略研究[D];河北工程大學(xué);2015年

2 張明;IaaS中基于熱點(diǎn)數(shù)據(jù)的存儲(chǔ)系統(tǒng)研究與實(shí)現(xiàn)[D];哈爾濱工業(yè)大學(xué);2015年

3 蔣靜遠(yuǎn);基于數(shù)據(jù)通道的非結(jié)構(gòu)化數(shù)據(jù)多存儲(chǔ)系統(tǒng)[D];浙江大學(xué);2015年

4 郭暉;面向高清視頻監(jiān)控的流存儲(chǔ)系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D];電子科技大學(xué);2015年

5 許孟杰;嵌入式快速存儲(chǔ)模塊的研究與實(shí)現(xiàn)[D];中國(guó)艦船研究院;2015年

6 何潔和;面向POI的分布式結(jié)構(gòu)化存儲(chǔ)系統(tǒng)存儲(chǔ)引擎設(shè)計(jì)與實(shí)現(xiàn)[D];電子科技大學(xué);2014年

7 王曉;混合存儲(chǔ)系統(tǒng)高效快照技術(shù)研究[D];北京理工大學(xué);2015年

8 邱登峰;基于Hadoop可公共審計(jì)云存儲(chǔ)的設(shè)計(jì)與實(shí)現(xiàn)[D];大連理工大學(xué);2015年

9 張致元;電子商品存儲(chǔ)系統(tǒng)設(shè)計(jì)與研究[D];復(fù)旦大學(xué);2014年

10 劉秉煦;云存儲(chǔ)環(huán)境下的混合存儲(chǔ)算法研究與實(shí)現(xiàn)[D];上海交通大學(xué);2015年

，

本文編號(hào)：1257563