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

1、在當(dāng)前大型分布式存儲系統(tǒng)中，隨著存儲規(guī)模越來越大以及廉價(jià)但可靠性差的存儲設(shè)備的廣泛部署，磁盤錯(cuò)誤變得益發(fā)頻繁，容錯(cuò)能力成為了現(xiàn)代存儲系統(tǒng)的重要指標(biāo)。通常，存儲系統(tǒng)通過引入冗余數(shù)據(jù)來保障數(shù)據(jù)可靠性。冗余數(shù)據(jù)可以通過復(fù)制或者糾刪碼方式產(chǎn)生。其中，糾刪碼容錯(cuò)存儲技術(shù)因其在相同可靠性條件下可最小化冗余存儲開銷，被廣泛地在大型分布式存儲系統(tǒng)中部署。因此，研究分布式存儲系統(tǒng)中基于糾刪碼的容錯(cuò)存儲技術(shù)對海量數(shù)據(jù)背景下的數(shù)據(jù)存儲有著重要意義。本文主要研

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

3、校驗(yàn)塊以及編碼產(chǎn)生該校驗(yàn)塊的數(shù)據(jù)塊組成的校驗(yàn)集的概念，構(gòu)建了基于校驗(yàn)集組的糾刪碼單節(jié)點(diǎn)故障修復(fù)分析模型，繼而設(shè)計(jì)了一種替換修復(fù)算法Replace Recovery。該算法利用啟發(fā)式搜索策略，在糾刪碼各校驗(yàn)節(jié)點(diǎn)的校驗(yàn)集中尋找最小化修復(fù)過程數(shù)據(jù)讀取量的校驗(yàn)集組。理論分析表明，Replace Recovery為各類糾刪碼的單節(jié)點(diǎn)故障修復(fù)提供了數(shù)據(jù)讀取量最優(yōu)/近似最優(yōu)的修復(fù)方案。通過在實(shí)際分布式存儲系統(tǒng)中部署該替換修復(fù)算法，并開展相對傳統(tǒng)修復(fù)算

4、法的廣泛對比實(shí)驗(yàn)，本文證實(shí)了Replace Recovery可明顯減少糾刪碼的單節(jié)點(diǎn)故障修復(fù)時(shí)間。
　　(2)異構(gòu)存儲環(huán)境修復(fù)問題研究
　　由于設(shè)備更新?lián)Q代以及數(shù)據(jù)訪問熱點(diǎn)分布不均等原因，實(shí)際部署的分布式存儲系統(tǒng)往往面臨著異構(gòu)的存儲環(huán)境，存儲節(jié)點(diǎn)的計(jì)算能力各不相同，鏈路的傳輸帶寬也不盡相同。因此，現(xiàn)有最小化修復(fù)過程數(shù)據(jù)讀取量的修復(fù)算法可能無法在異構(gòu)存儲環(huán)境中提供有效修復(fù)性能。本文通過引入衡量異構(gòu)存儲環(huán)境中各節(jié)點(diǎn)單位數(shù)據(jù)下載成

5、本的指標(biāo)，為RAID-6碼異構(gòu)修復(fù)問題建立了旨在最小化修復(fù)代價(jià)的優(yōu)化模型?；谠撃Ｐ?，本文給出相應(yīng)縮減策略大大縮小異構(gòu)修復(fù)模型的搜索空間，繼而為RAID-6碼設(shè)計(jì)了一種基于成本的單節(jié)點(diǎn)故障異構(gòu)恢復(fù)算法CHR(Cost-based Heterogeneous Recovery)，該算法保證故障節(jié)點(diǎn)恢復(fù)過程數(shù)據(jù)傳輸量最優(yōu)并且恢復(fù)成本也最少。進(jìn)一步地，本文將異構(gòu)修復(fù)優(yōu)化模型推廣至一般性糾刪碼，同時(shí)給出了通用的異構(gòu)替換修復(fù)算法HeRR(Hete

6、rogeneous Replace Recovery)，有效減少了故障修復(fù)過程的恢復(fù)成本。通過在實(shí)際的異構(gòu)存儲系統(tǒng)中開展廣泛對比實(shí)驗(yàn)，本文證實(shí)了糾刪碼的異構(gòu)修復(fù)算法可以有效地加快單節(jié)點(diǎn)故障修復(fù)時(shí)間。
　　(3)加速退化讀問題研究
　　當(dāng)存儲系統(tǒng)中發(fā)生節(jié)點(diǎn)故障時(shí)，系統(tǒng)需要能夠執(zhí)行兩類操作:故障節(jié)點(diǎn)修復(fù)，以保障數(shù)據(jù)可靠性;退化讀，以滿足用戶對故障節(jié)點(diǎn)上數(shù)據(jù)的訪問請求。事實(shí)上，數(shù)據(jù)中心絕大部分節(jié)點(diǎn)故障是暫時(shí)性的，即故障節(jié)點(diǎn)上數(shù)據(jù)并

7、沒有丟失。當(dāng)發(fā)生暫時(shí)性節(jié)點(diǎn)故障時(shí)，存儲系統(tǒng)往往僅需執(zhí)行退化讀操作以滿足用戶的訪問請求。因此，相較于故障節(jié)點(diǎn)修復(fù)，退化讀操作的性能優(yōu)化對于基于糾刪碼的分布式存儲系統(tǒng)更加關(guān)鍵。
　　為了加速糾刪碼退化讀操作，本文考慮了實(shí)際系統(tǒng)中存儲設(shè)備性能異構(gòu)性以及數(shù)據(jù)訪問并發(fā)性等特點(diǎn)，設(shè)計(jì)了糾刪碼退化讀性能評估指標(biāo)。由于退化讀優(yōu)化問題求解空間過大且實(shí)際存儲系統(tǒng)需要能夠即時(shí)決定退化讀策略，本文設(shè)計(jì)了一種啟發(fā)式的EG(Enumerated Greedy

8、)退化讀算法。該算法可以根據(jù)存儲系統(tǒng)中各節(jié)點(diǎn)的實(shí)時(shí)下載成本信息，迅速給出高效退化讀方案?；贖DFS(Hadoop Distributed File System)文件系統(tǒng)，本文設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)支持高效退化讀的FastDR原型系統(tǒng)。通過在由12個(gè)節(jié)點(diǎn)組成的存儲集群中開展性能對比實(shí)驗(yàn)，本文證實(shí)了FastDR相較于傳統(tǒng)退化讀算法可以提供高效退化讀性能。
　　(4)重復(fù)數(shù)據(jù)刪除技術(shù)部署研究
　　隨著數(shù)據(jù)爆炸式增長，存儲開銷已經(jīng)成為

9、當(dāng)前存儲系統(tǒng)首要關(guān)注的問題。重復(fù)數(shù)據(jù)刪除技術(shù)，因其可以有效地去除存儲數(shù)據(jù)中冗余部分，已經(jīng)被越來越多地部署在了實(shí)際存儲系統(tǒng)中。當(dāng)文件存入分布式存儲系統(tǒng)中時(shí)，組成文件的數(shù)據(jù)塊通常會被分散存儲在不同節(jié)點(diǎn)中，以提高文件并發(fā)訪問性能。而在部署了重復(fù)數(shù)據(jù)刪除技術(shù)的分布式存儲系統(tǒng)中，組成文件的數(shù)據(jù)塊可能會出現(xiàn)聚集在某些存儲節(jié)點(diǎn)的情況，從而影響文件的并發(fā)訪問性能以及文件可靠性。
　　本文研究了基于糾刪碼的重復(fù)數(shù)據(jù)刪除技術(shù)部署問題，并設(shè)計(jì)了一種數(shù)據(jù)