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

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

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

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

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

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

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

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

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

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