分布式存儲系統(tǒng)中基于糾刪碼的容錯技術(shù)研究

《分布式存儲系統(tǒng)中基于糾刪碼的容錯技術(shù)研究》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、中國科學(xué)技術(shù)大學(xué)博士學(xué)位論分布式存儲系統(tǒng)中基于糾刪碼的容錯技術(shù)研究作者姓名：朱云鋒學(xué)科專業(yè)：計算機(jī)軟件與理論導(dǎo)師姓名：許胤龍教授完成時間：二O一四年五月一日乙以“矽V以11力畸∽文fIIIIIlUlIIIIIIIIIlY2589749UniversityofScienceandTechnologyofChinanversityotcienceandechnolo’．qvhInaAdissertationfordoctorSdegreeStudyonFault—ToleranceTechnologies

2、forEreCodeFrasudesinDistributedStorageSystemsAuthor’SName：YunfengZhuSpeciality：ComputerSoftwareandTheorySupervisor：Prof．YinlongXuFinishedtime：Mayl吼，2014中國科學(xué)技術(shù)大學(xué)學(xué)位論文原創(chuàng)性聲明本人聲明所呈交的學(xué)位論文，是本人在導(dǎo)師指導(dǎo)下進(jìn)行研究工作所取得的成果。除已特別加以標(biāo)注和致謝的地方外，論文中不包含任何他人已經(jīng)發(fā)表或撰寫過的研究成果。與我一同工作的同志

3、對本研究所做的貢獻(xiàn)均己在論文中作了明確的說明。作者簽名：蜱簽字日期：上生幽生垃中國科學(xué)技術(shù)大學(xué)學(xué)位論文授權(quán)使用聲明作為申請學(xué)位的條件之一，學(xué)位論文著作權(quán)擁有者授權(quán)中國科學(xué)技術(shù)大學(xué)擁有學(xué)位論文的部分使用權(quán)，即：學(xué)校有權(quán)按有關(guān)規(guī)定向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱，可以將學(xué)位論文編入《中國學(xué)位論文全文數(shù)據(jù)庫》等有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存、匯編學(xué)位論文。本人提交的電子文檔的內(nèi)容和紙質(zhì)論文的內(nèi)容相一致。保密的學(xué)位論文在解密后也遵守此規(guī)定。J回公開

4、口保密(——年)作者簽名：簽字日期：監(jiān)埠一7．o14．o()．02導(dǎo)師簽名：埠血么簽字日期：立砸二0—厶衛(wèi)摘要在當(dāng)前大型分布式存儲系統(tǒng)中，隨著存儲規(guī)模越來越大以及廉價但可靠性差的存儲設(shè)備的廣泛部署，磁盤錯誤變得益發(fā)頻繁，容錯能力成為了現(xiàn)代存儲系統(tǒng)的重要指標(biāo)。通常，存儲系統(tǒng)通過引入冗余數(shù)據(jù)來保障數(shù)據(jù)可靠性。冗余數(shù)據(jù)可以通過復(fù)制或者糾刪碼方式產(chǎn)生。其中，糾刪碼容錯存儲技術(shù)因其在相同可靠性條件下可最小化冗余存儲開銷，被廣泛地在大型分布式存儲系統(tǒng)中部署。因此，研究分布式存儲系統(tǒng)中基于糾刪碼的容錯存儲技術(shù)對海量

5、數(shù)據(jù)背景下的數(shù)據(jù)存儲有著重要意義。本文主要研究了基于糾刪碼的分布式存儲系統(tǒng)中，發(fā)生節(jié)點(diǎn)故障時的數(shù)據(jù)修復(fù)問題，主要研究內(nèi)容與貢獻(xiàn)如下：(1)單節(jié)點(diǎn)故障修復(fù)問題研究當(dāng)前很多存儲系統(tǒng)具有可容忍多個節(jié)點(diǎn)同時發(fā)生故障的能力，但實(shí)際中發(fā)生單節(jié)點(diǎn)故障的頻率要遠(yuǎn)遠(yuǎn)高于多節(jié)點(diǎn)并發(fā)故障發(fā)生的頻率。當(dāng)存儲系統(tǒng)發(fā)生節(jié)點(diǎn)故障時，系統(tǒng)需要及時重構(gòu)出故障數(shù)據(jù)以維持系統(tǒng)可靠性及服務(wù)性能。而修復(fù)操作從剩余節(jié)點(diǎn)讀取的數(shù)據(jù)量直接影響著修復(fù)性能。本文研究了糾刪碼的單節(jié)點(diǎn)故障修復(fù)問題，通過引入由單校驗(yàn)塊以及編碼產(chǎn)生該校驗(yàn)塊的數(shù)據(jù)塊組成的校驗(yàn)集

6、的概念，構(gòu)建了基于校驗(yàn)集組的糾刪碼單節(jié)點(diǎn)故障修復(fù)分析模型，繼而設(shè)計了一種替換修復(fù)算法ReplaceRecovery。該算法利用啟發(fā)式搜索策略，在糾刪碼各校驗(yàn)節(jié)點(diǎn)的校驗(yàn)集中尋找最小化修復(fù)過程數(shù)據(jù)讀取量的校驗(yàn)集組。理論分析表明，ReplaceRecovery為各類糾刪碼的單節(jié)點(diǎn)故障修復(fù)提供了數(shù)據(jù)讀取量最優(yōu)／近似最優(yōu)的修復(fù)方案。通過在實(shí)際分布式存儲系統(tǒng)中部署該替換修復(fù)算法，并開展相對傳統(tǒng)修復(fù)算法的廣泛對比實(shí)驗(yàn)，本文證實(shí)了ReplaceRecovery可明顯減少糾刪碼的單節(jié)點(diǎn)故障修復(fù)時間。(2)異構(gòu)存儲環(huán)境修

7、復(fù)問題研究由于設(shè)備更新?lián)Q代以及數(shù)據(jù)訪問熱點(diǎn)分布不均等原因，實(shí)際部署的分布式存儲系統(tǒng)往往面臨著異構(gòu)的存儲環(huán)境，存儲節(jié)點(diǎn)的計算能力各不相同，鏈路的傳輸帶寬也不盡相同。因此，現(xiàn)有最小化修復(fù)過程數(shù)據(jù)讀取量的修復(fù)算法可能無法在異構(gòu)存儲環(huán)境中提供有效修復(fù)性能。本文通過引入衡量異構(gòu)存儲環(huán)境中各節(jié)點(diǎn)單位數(shù)據(jù)下載成本的指標(biāo)，為RAID．6碼異構(gòu)修復(fù)問題建立了旨在最小化修復(fù)代價的優(yōu)化模型?；谠撃Ｐ停疚慕o出相應(yīng)縮減策略大大縮小異構(gòu)修復(fù)模型的搜索空間，繼而為RAID．6碼設(shè)計了一種基于成本的單節(jié)點(diǎn)故障異構(gòu)恢復(fù)算法CHR(

8、Cost．basedHeterogeneousRecovery)，該算法保證故障節(jié)點(diǎn)恢復(fù)過程數(shù)據(jù)傳輸量最優(yōu)并且恢復(fù)成本也最少。進(jìn)一步地，本文將異構(gòu)修復(fù)優(yōu)化模型推廣至一般性糾刪碼，同時給出了通用的異構(gòu)替換修復(fù)算法HeRR摘要(HeterogeneousReplaceRecovery)，有效減少了故障修復(fù)過程的恢復(fù)成本。通過在實(shí)際的異構(gòu)存儲系統(tǒng)中開展廣泛對比實(shí)驗(yàn)，本文證實(shí)了糾刪碼的異構(gòu)修復(fù)算法可以有效地加快單節(jié)點(diǎn)故障修復(fù)時間。(3)加速退化讀問題研究當(dāng)存儲系