隨機(jī)化數(shù)據(jù)冗余方法及其在存儲系統(tǒng)中的應(yīng)用.pdf

《隨機(jī)化數(shù)據(jù)冗余方法及其在存儲系統(tǒng)中的應(yīng)用.pdf》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、電子科技大學(xué)UNIVERSITYOFELECTRONICSCIENCEANDTECHNOLOGYOFCHINA博士學(xué)位論文DOCTORALDISSERTATION論文題目隨機(jī)化數(shù)據(jù)冗余方法及其在存儲系統(tǒng)中的應(yīng)用學(xué)科專業(yè)計(jì)算機(jī)軟件與理論學(xué)號200911060152作者姓名肖宜龍指導(dǎo)教師王曉京研究員萬方數(shù)據(jù)萬方數(shù)據(jù)分類號密級注1UDC學(xué)位論文隨機(jī)化數(shù)據(jù)冗余方法及其在存儲系統(tǒng)中的應(yīng)用（題名和副題名）肖宜龍（作者姓名）指導(dǎo)教師王曉京研究員中國科學(xué)院成都計(jì)算機(jī)應(yīng)用研究所（姓名、職稱、單位名稱）申請學(xué)位級別博士學(xué)科專業(yè)計(jì)算機(jī)軟件與理論提交論文日期2013.3.15論文答辯日期2013.5.28學(xué)位授予單位

2、和日期電子科技大學(xué)2013年6月23日答辯委員會主席周明天評閱人唐常杰張小松岳麗華鐘勇汪心宣注1：注明《國際十進(jìn)分類法UDC》的類號。萬方數(shù)據(jù)萬方數(shù)據(jù)RANDOMDATAREDUNDANCYMETHODANDITSAPPLICATIONINDISTRIBUTEDSTORAGESYSTEMSADoctorDissertationSubmittedtoUniversityofElectronicScienceandTechnologyofChinaMajor:ComputerSoftwareandTheoryAuthor:XiaoYi-longAdvisor:WangXiao-jingSchool

3、:SchoolofComputerScienceandEngineering萬方數(shù)據(jù)萬方數(shù)據(jù)獨(dú)創(chuàng)性聲明本人聲明所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。據(jù)我所知，除了文中特別加以標(biāo)注和致謝的地方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果，也不包含為獲得電子科技大學(xué)或其它教育機(jī)構(gòu)的學(xué)位或證書而使用過的材料。與我一同工作的同志對本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說明并表示謝意。作者簽名：日期：年月日論文使用授權(quán)本學(xué)位論文作者完全了解電子科技大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，有權(quán)保留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和磁盤，允許論文被查閱和借閱。本人授權(quán)電子

4、科技大學(xué)可以將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存、匯編學(xué)位論文。（保密的學(xué)位論文在解密后應(yīng)遵守此規(guī)定）作者簽名：導(dǎo)師簽名：日期：年月日萬方數(shù)據(jù)萬方數(shù)據(jù)摘要摘要利用網(wǎng)絡(luò)分布式存儲系統(tǒng)存儲大數(shù)據(jù)已成為數(shù)據(jù)存儲技術(shù)的發(fā)展趨勢。網(wǎng)絡(luò)分布式存儲系統(tǒng)通常由數(shù)量眾多的存儲節(jié)點(diǎn)構(gòu)成，由于人為或自然災(zāi)難的不可避免性，或是存儲節(jié)點(diǎn)本身的低可靠性，常常會發(fā)生部分存儲節(jié)點(diǎn)損壞或是無法及時使用的情況。而這一旦發(fā)生，存儲其中的重要數(shù)據(jù)就會丟失或是不可用，造成極大的損失。因此，為了保證存儲數(shù)據(jù)的安全性和可靠性，將數(shù)據(jù)冗余方法引入網(wǎng)絡(luò)分布式存儲系統(tǒng)成為一種必然。已有的數(shù)據(jù)冗

5、余方法，如基于復(fù)制的數(shù)據(jù)冗余方法，基于陣列碼的數(shù)據(jù)冗余方法等均存在種種不足，或者是存儲冗余度過高，或者是容錯能力有限，無法滿足網(wǎng)絡(luò)環(huán)境下分布式存儲系統(tǒng)的需求。針對這一問題，本文首次以隨機(jī)矩陣?yán)碚摓榛A(chǔ)，提出了一類新的數(shù)據(jù)冗余方法，稱之為隨機(jī)化數(shù)據(jù)冗余方法，并研究了其在兩類具體的網(wǎng)絡(luò)分布式存儲環(huán)境——分布式數(shù)據(jù)容災(zāi)存儲和傳感器網(wǎng)絡(luò)數(shù)據(jù)存儲環(huán)境下的應(yīng)用。本文的主要研究成果包括以下幾個方面：1．提出了性能優(yōu)異的隨機(jī)化數(shù)據(jù)冗余方法。容錯能力高、存儲冗余度低、運(yùn)算速度快、修復(fù)帶寬低是網(wǎng)絡(luò)環(huán)境下的分布式存儲系統(tǒng)對數(shù)據(jù)冗余方法的需求?，F(xiàn)有的數(shù)據(jù)冗余方法往往無法同時滿足這些需求。本文以二元域上的隨機(jī)矩陣為基礎(chǔ)

6、，提出了一類新的能滿足上述需求的隨機(jī)化數(shù)據(jù)冗余方法，給出了詳細(xì)的文件存儲、讀取、以及修復(fù)算法。在本文提出的隨機(jī)化數(shù)據(jù)冗余方法中：由源文件得到冗余文件、由冗余文件恢復(fù)出源文件均基于構(gòu)造好的隨機(jī)矩陣完成；隨機(jī)矩陣滿秩的高概率性質(zhì)保證了冗余方法的高容錯能力和低存儲冗余度；同時，源文件和冗余文件之間的轉(zhuǎn)換只依靠異或運(yùn)算進(jìn)行，降低了計(jì)算復(fù)雜度，提高了文件的處理速度；另外，隨機(jī)矩陣的稀疏性也使得修復(fù)丟失的部分冗余文件數(shù)據(jù)所需的修復(fù)帶寬有效降低；2．提出了基于隨機(jī)化數(shù)據(jù)冗余方法的低冗余度數(shù)據(jù)容災(zāi)方案。數(shù)據(jù)容災(zāi)方案是網(wǎng)絡(luò)分布式數(shù)據(jù)容災(zāi)存儲系統(tǒng)抵御大規(guī)模存儲節(jié)點(diǎn)損毀，保證數(shù)據(jù)生存能力的有效手段。傳統(tǒng)的容災(zāi)方案通

7、常以復(fù)制冗余方法為基礎(chǔ)，以高存儲空間代價換取一定的容災(zāi)能力。本文在隨機(jī)化數(shù)據(jù)冗余方法的基礎(chǔ)上，提出了一類具有低存儲冗余度的數(shù)據(jù)容災(zāi)方案。與復(fù)制容災(zāi)方案相比，本文方案在提供相同容災(zāi)能力的前提下，可將系統(tǒng)的存儲空間代價降到近似的理論最小值。本I萬方數(shù)據(jù)摘要文方案的可行性和有效性在相關(guān)實(shí)驗(yàn)中得到了驗(yàn)證。3．以隨機(jī)化數(shù)據(jù)冗余方法為基礎(chǔ)，提出了適用于無人值守傳感器網(wǎng)絡(luò)的具有低通信成本和低訪問成本的分布式存儲