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

1、隨著計算機和網(wǎng)絡技術的發(fā)展，云計算正處在迅猛的發(fā)展階段，并會在未來若干年主導著信息產(chǎn)業(yè)的市場空間。云存儲作為云計算中最核心的基礎組件，它通過集群、網(wǎng)格計算和分布式文件系統(tǒng)等技術，將網(wǎng)絡中大量異構的存儲設備集合起來協(xié)同工作，對外提供統(tǒng)一的數(shù)據(jù)存儲、管理和訪問等在線服務。由于云存儲具有存儲成本低、容量大、可擴展性好的特點，所以自從推出后就倍受廣大用戶的青睞。
　　然而，由于云存儲環(huán)境的復雜性和開放性，系統(tǒng)會遇到各種各樣的問題。應用程序

2、的故障、操作系統(tǒng)的故障、人為操作失誤、網(wǎng)絡攻擊等現(xiàn)象，都有可能造成數(shù)據(jù)隨時失效。在云存儲系統(tǒng)中，節(jié)點失效被認為是常態(tài)事件而不是意外事件，在任何給定時間內(nèi)都有可能發(fā)生某些節(jié)點無法工作。為此，容錯機制是云存儲系統(tǒng)首要考慮的工作任務。
　　現(xiàn)在的云存儲容錯方案大部分采用了副本復制技術，但隨著數(shù)據(jù)量以超過摩爾定律的速度增長，會給云存儲系統(tǒng)帶來巨大的存儲壓力。目前，專家學者們一致認為:為了緩解存儲壓力，云存儲容錯方案會逐漸由副本復制向糾刪碼

3、轉(zhuǎn)變。然而，糾刪碼是一種典型的以時間換空間的算法，它雖然數(shù)據(jù)冗余量小，但計算復雜度高，重構效率低，會消耗過多的網(wǎng)絡帶寬資源。本文從計算性能優(yōu)化、存儲效率優(yōu)化、故障修復優(yōu)化、混合冗余優(yōu)化四個方面出發(fā)，對容錯糾刪碼展開研究，主要工作及創(chuàng)新點如下:
　　1.針對傳統(tǒng)RS編碼在有限域上乘法計算復雜度高的問題，提出了一種自帶加速器的RS(Reed-Solomon)編碼。
　　RS編碼是在伽羅瓦域(Galois Field)GF(2ω)

4、進行運算，加法計算簡單，但乘法計算復雜度高。本工作對基于RS編碼的存儲容錯原理進行了詳細介紹，并通過實例分析了RS編碼進行乘法運算的復雜性，在此基礎上，提出了一種自帶加速器的RS編碼---RSWA(Reed-Solomon Codes with Accelerator)編碼，并從理論上將RS編碼、柯西RS編碼、RSWA編碼的復雜度進行了對比。最后，通過實驗對RS編碼、柯西RS編碼、RSWA編碼的性能進行了評估。實驗結(jié)果表明:RSWA編碼

5、在單條帶編碼、整體編碼、重構效率方面要優(yōu)于另外兩種編碼。
　　2.針對云存儲容錯系統(tǒng)中數(shù)據(jù)存儲量迅速增長的問題，在基于糾刪碼的云存儲容錯系統(tǒng)中提出了一種基于全局布魯姆過濾器陣列的去重方法。
　　云存儲系統(tǒng)中數(shù)據(jù)量以超過摩爾定律的速度增長，并有超過60％的數(shù)據(jù)是重復的。在基于糾刪碼的容錯系統(tǒng)中，數(shù)據(jù)對象分塊存儲，存儲粒度更小，存在的重復數(shù)據(jù)會更多。在云存儲系統(tǒng)的存儲空間和網(wǎng)絡帶寬越來越緊張的情況下，如何提高系統(tǒng)的存儲效率成了一

6、個亟待解決的問題。本工作對去重技術的研究現(xiàn)狀、布魯姆過濾器的研究現(xiàn)狀、基于布魯姆過濾器的去重現(xiàn)狀進行了介紹，對去重技術、布魯姆過濾器的基礎理論進行了分析。由于布魯姆過濾器是一種空間高效的隨機化數(shù)據(jù)結(jié)構，非常適合于有限空間內(nèi)的查詢比對，所以提出了一種基于全局布魯姆過濾器陣列的高效去重方法。通過對標準布魯姆過濾器進行動態(tài)的擴容，組建了一個全局動態(tài)布魯姆過濾器陣列(Public Dynamic Bloom Filter Array，PDBFA

7、)，從而有效地控制了系統(tǒng)的誤判率。最后，在自組建的Openstack云平臺上進行了性能評估，實驗結(jié)果表明:PDBFA具有去重率高、誤判率低、對容錯性能影響較小的特性。
　　3.針對RS編碼糾錯能力強而修復復雜度高的特點，提出了一種面向云存儲容錯系統(tǒng)的RS再生糾刪碼。
　　RS編碼雖然糾錯能力強，但由乘法計算復雜并需要求逆矩陣，所以編譯碼效率低，不能滿足云存儲容錯系統(tǒng)的特性要求。陣列碼雖然計算簡單，但一般只能容雙錯，同樣不能滿

8、足云存儲容錯系統(tǒng)的特性要求。本工作在分析了現(xiàn)有的RS編碼和RDP陣列碼的優(yōu)缺點后，面向云存儲容錯系統(tǒng)提出了一種RS再生糾刪碼。該編碼繼承了RS編碼容多錯的可靠性，又能實現(xiàn)擴展RDP編碼容三錯的高效性。對RS再生碼中單節(jié)點故障混合修復方法進行了介紹，并求出了混合修復時磁盤讀取數(shù)的理論下界。從理論上對RS再生碼的存儲開銷、譯碼效率、修復帶寬進行了性能評估。最后，在開源分布式存儲系統(tǒng)NCFS中對RS再生碼的性能進行了評估實驗結(jié)果表明:RS再生

9、糾刪碼比同類糾刪碼的修復性能有較大的提升，特別是采用混合修復算法以后，系統(tǒng)單故障恢復時間下降20.8％～28.2％。
　　4.針對副本復制技術修復快、占用存儲空間多的特點，在云存儲容錯系統(tǒng)中提出了一種基于復制和糾刪碼自適應切換的容錯策略。
　　基于副本復制技術容錯操作簡單、故障修復快，但會過多地消耗存儲空間，而基于糾刪碼技術容錯可有效節(jié)約存儲空間，但故障修復時會消耗過多的網(wǎng)絡帶寬。單一的數(shù)據(jù)冗余策略無法很好地滿足云存儲容錯系

10、統(tǒng)的特性要求。本工作對副本復制和糾刪碼兩種常用的容錯方法進行了對比分析，根據(jù)云端文件的訪問規(guī)律提出一種基于復制和糾刪碼自適應切換的云存儲容錯算法，構建了一個相應的云存儲容錯框架。容錯算法根據(jù)文件的訪問頻率和存儲大小，自適應地選擇容錯策略，一方面降低了低訪問量文件的存儲開銷，另一方面提高了高訪問量文件的訪問時效。實驗結(jié)果表明:該算法較完全復制節(jié)約存儲空間40％，而較糾刪碼的訪問時效提升48％，并在這兩方面優(yōu)于同類混合數(shù)據(jù)冗余算法。