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

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

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

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

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

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

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

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

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

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

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