李 玲,付 園,麻曉珍,張海蓉

(吉林大學(xué) 通信工程學(xué)院,長(zhǎng)春 130012)

0 引 言

云存儲(chǔ)系統(tǒng)作為云計(jì)算的一個(gè)分支受到廣大學(xué)者的重視[1-3],存儲(chǔ)系統(tǒng)數(shù)據(jù)的有效性和完整性是最受關(guān)注的性能指標(biāo),為此,云存儲(chǔ)系統(tǒng)紛紛引入了冗余機(jī)制[4-6]。絕大多數(shù)系統(tǒng)采用簡(jiǎn)單的完全備份[7,8],每個(gè)數(shù)據(jù)塊增加幾個(gè)固定的備份副本并隨機(jī)地存放在不同節(jié)點(diǎn)上,這給系統(tǒng)帶來(lái)了挑戰(zhàn)：

1)引入過(guò)多的副本雖然能滿足數(shù)據(jù)有效性要求,但也帶來(lái)存儲(chǔ)成本的增加；

2)副本在云計(jì)算集群中放置的不均衡將導(dǎo)致訪問(wèn)扭曲甚至網(wǎng)絡(luò)擁塞；

3)當(dāng)所有副本都失效時(shí),數(shù)據(jù)無(wú)法恢復(fù)。

針對(duì)云存儲(chǔ)系統(tǒng)冗余機(jī)制的上述前兩個(gè)問(wèn)題,文獻(xiàn)[9-11]都提出了改進(jìn)策略,分別給出了各自副本數(shù)確定和副本放置的模型,在滿足有效性要求的基礎(chǔ)上節(jié)省了存儲(chǔ)空間并實(shí)現(xiàn)了負(fù)載均衡,但都沒(méi)有解決數(shù)據(jù)可恢復(fù)性問(wèn)題。

文獻(xiàn)[12,13]提出采用糾刪碼的方法,以增強(qiáng)云存儲(chǔ)系統(tǒng)中數(shù)據(jù)的可靠性,但當(dāng)數(shù)據(jù)更新頻繁時(shí),糾刪碼的編解碼過(guò)程將帶來(lái)大量的系統(tǒng)時(shí)延。

文獻(xiàn)[14]對(duì)糾刪碼和完全備份的優(yōu)劣勢(shì)進(jìn)行對(duì)比分析,分別得出了各自的優(yōu)勢(shì)。為結(jié)合二者的優(yōu)勢(shì),文獻(xiàn)[15]提出了將完全備份和RS(Rood-Solomon)糾刪碼結(jié)合的分布式架構(gòu)REPERA,但并沒(méi)有給出副本數(shù)確定和副本放置以及參數(shù)調(diào)整的依據(jù),而且REPERA采用的RS編碼方法編解碼速度慢,增加了系統(tǒng)時(shí)延。

因此,筆者提出一種將完全備份與改進(jìn)的RS糾刪碼結(jié)合的自適應(yīng)數(shù)據(jù)冗余策略RIRS,可根據(jù)具體應(yīng)用環(huán)境設(shè)置RIRS的參數(shù)。RIRS在需要隨時(shí)更新數(shù)據(jù)的場(chǎng)合下退化為純粹的完全備份模式時(shí),筆者又給出一個(gè)動(dòng)態(tài)副本管理優(yōu)化模型DRMO,以動(dòng)態(tài)調(diào)節(jié)副本數(shù)和副本位置,節(jié)省存儲(chǔ)空間和實(shí)現(xiàn)負(fù)載均衡。

1 完全備份與改進(jìn)后RS糾刪碼結(jié)合的冗余策略RIRS

Hadoop是目前廣泛用于學(xué)術(shù)研究的典型開(kāi)源云平臺(tái),筆者提出的完全備份與改進(jìn)后RS糾刪碼結(jié)合的冗余策略也是基于Hadoop的分布式文件系統(tǒng)HDFS(Hadoop Distributed File System)的,下面詳細(xì)介紹RIRS的實(shí)現(xiàn)過(guò)程。

1.1 RIRS的數(shù)據(jù)存儲(chǔ)及恢復(fù)策略

RIRS對(duì)系統(tǒng)中的數(shù)據(jù)進(jìn)行存儲(chǔ)時(shí)采用{r,m,n}策略,先用改進(jìn)的RS糾刪碼算法對(duì)每n塊數(shù)據(jù)塊進(jìn)行編碼,產(chǎn)生(m-n)塊冗余碼并將其編為一個(gè)編碼組,然后將每個(gè)編碼組備份r份,分散地存儲(chǔ)在不同的數(shù)據(jù)節(jié)點(diǎn)和機(jī)架上。在NameNode上維護(hù)一個(gè)記錄編碼任務(wù)的數(shù)據(jù)結(jié)構(gòu),包括源數(shù)據(jù)節(jié)點(diǎn)的位置,進(jìn)行冗余塊計(jì)算的節(jié)點(diǎn)位置和存放冗余塊的節(jié)點(diǎn)位置等信息。RIRS系統(tǒng)中{r,m,n}參數(shù)的調(diào)整能使該冗余策略滿足不同環(huán)境的需求,在某些應(yīng)用場(chǎng)景下完全可以退化成純粹的完全備份或糾刪碼方法。

HDFS采用完全備份的方法將每個(gè)數(shù)據(jù)塊復(fù)制3份,因此其占用的空間為3×n,而RIRS占用的空間為r×m,采用RIRS節(jié)省存儲(chǔ)空間情況如表1所示。

表1 HDFS與RIRS占用空間

RIRS的數(shù)據(jù)恢復(fù)策略采用備份優(yōu)先策略[15],只有當(dāng)所有副本都失效時(shí)才采用解碼操作恢復(fù)數(shù)據(jù)。

1.2 RIRS中糾刪碼的選擇

糾刪碼發(fā)展至今,已有數(shù)十種類型,其中適合分布式存儲(chǔ)系統(tǒng)的主要是RS糾刪碼和LDPC糾刪碼,下面將通過(guò)試驗(yàn)比較得出糾刪碼選擇的依據(jù)。

1)RS糾刪碼。RS糾刪碼用范德蒙矩陣F與數(shù)據(jù)矩陣D相乘得到校驗(yàn)矩陣C,編碼過(guò)程如下

(1)

觀察如上矩陣可得,刪除矩陣A和矩陣E的對(duì)應(yīng)行,等式依然成立。刪除相應(yīng)行后的矩陣分別用A′,E′表示,得到

A′D=E′

(2)

根據(jù)矩陣的性質(zhì),可得

D=(A′)-1E′

(3)

根據(jù)范德蒙矩陣的性質(zhì),可得A中任取p(p≥n)行一定線性獨(dú)立,則矩陣A一定可逆。故只要數(shù)據(jù)損壞少于等于m-n個(gè),就一定能恢復(fù)原來(lái)的n個(gè)數(shù)據(jù),即容錯(cuò)能力為m-n。

使用Matlab編程實(shí)現(xiàn)n=10,m=15的編碼結(jié)果如圖1所示。

圖1 RS糾刪碼編碼過(guò)程

圖2中A0和encode0t分別為A和encode刪除對(duì)應(yīng)5行后的結(jié)果,Inv為A0在伽羅華域范圍上的逆矩陣,可見(jiàn)只要損失的數(shù)據(jù)不大于5即可成功解碼,說(shuō)明RS編碼的容錯(cuò)能力為m-n。

圖2 RS糾刪碼解碼過(guò)程

2)LDPC糾刪碼。LDPC糾刪碼是用稀疏矩陣H與數(shù)據(jù)矩陣D相乘得校驗(yàn)矩陣C,其中H中只有0,1兩個(gè)元素,而且1的個(gè)數(shù)小于0的個(gè)數(shù)。該矩陣表示信息位到冗余校驗(yàn)位的具體映射關(guān)系,所以,校驗(yàn)位只需對(duì)數(shù)據(jù)位進(jìn)行簡(jiǎn)單的異或運(yùn)算就可得到,從而簡(jiǎn)化了編解碼運(yùn)算的復(fù)雜度。

用Matlab實(shí)現(xiàn)n=10,m=15的編碼結(jié)果如圖3所示。

圖3 LDPC碼編碼的運(yùn)行結(jié)果

圖1和圖3,圖2和圖4比較可得,LDPC碼的編解碼時(shí)延遠(yuǎn)小于RS碼,但由圖2和圖5可知,LDPC碼不能保證解碼成功,經(jīng)過(guò)多次運(yùn)行得到,在損失3個(gè)數(shù)據(jù)的情況下成功解碼的概率很高,能達(dá)到90%,而在損失4個(gè)數(shù)據(jù)的情況下,則只有50%,所以LDPC碼的容錯(cuò)性能較差。

圖4 LDPC碼損失3個(gè)數(shù)據(jù)時(shí)的解碼運(yùn)行結(jié)果 圖5 LDPC碼損失4個(gè)數(shù)據(jù)的解碼運(yùn)行結(jié)果

3)改進(jìn)的RS糾刪碼。為降低RS碼的編解碼時(shí)延,使用一種新的乘法運(yùn)算代替伽羅華域中乘法的計(jì)算,這種乘法只需用到異或和二進(jìn)制數(shù)的左移右移操作,運(yùn)算簡(jiǎn)單。

圖6 RS碼與其改進(jìn)算法的解碼時(shí)間對(duì)比

兩個(gè)整數(shù)相乘時(shí),將左邊的乘數(shù)除以2(右移),右邊的乘數(shù)乘以2(左移),得到的結(jié)果繼續(xù)重復(fù)這種運(yùn)算,直到左邊的乘數(shù)變?yōu)?。之后將左側(cè)結(jié)果為偶數(shù)的行刪掉,為奇數(shù)的行保留,將保留的右側(cè)結(jié)果全部相加,得到的即為兩數(shù)相乘的結(jié)果。

改進(jìn)后的RS編碼與原RS碼性能比較如圖6所示。圖6中K為信息位長(zhǎng),N為編碼后的數(shù)據(jù)位長(zhǎng),即碼長(zhǎng)。

圖6表明,改進(jìn)后的RS碼降低了RS碼的編解碼時(shí)延。

4)總結(jié)。由上面的實(shí)驗(yàn)結(jié)果可得,RS碼的容錯(cuò)能力,存儲(chǔ)空間使用效率都能達(dá)到最佳,但編解碼時(shí)延長(zhǎng)； LDPC碼有很快的編解碼速度,但其隨機(jī)的特性使其容錯(cuò)能力有限,且存儲(chǔ)空間使用效率較低。由于筆者提出的冗余策略是完全備份與糾刪碼結(jié)合的策略,而且數(shù)據(jù)丟失時(shí)采用備份優(yōu)先的原則恢復(fù)數(shù)據(jù),只有當(dāng)所有備份全丟失時(shí)才使用解碼恢復(fù),所以用到糾刪碼解碼的情況較少,解碼時(shí)延并不會(huì)影響整個(gè)系統(tǒng)的性能,而采用該種方法時(shí)必然沒(méi)有數(shù)據(jù)副本,如果解碼失敗,丟失的數(shù)據(jù)將不可恢復(fù)。因此選擇容錯(cuò)能力最佳的RS糾刪碼,并對(duì)其進(jìn)行上述改進(jìn),以降低解碼時(shí)延。

1.3 分析小結(jié)

RIRS充分發(fā)揮了完全備份和糾刪碼二者的優(yōu)勢(shì),由表1分析可知RIRS能節(jié)省系統(tǒng)的存儲(chǔ)空間,此外,由于多個(gè)副本分散地存儲(chǔ)在不同的節(jié)點(diǎn)上,用戶在訪問(wèn)數(shù)據(jù)時(shí)可以根據(jù)自己的地理位置就近訪問(wèn)數(shù)據(jù),降低了系統(tǒng)的訪問(wèn)時(shí)延。同時(shí),當(dāng)系統(tǒng)中所有備份都失效時(shí),RISR還可以采用解碼操作恢復(fù)數(shù)據(jù),所以,提高了系統(tǒng)的可靠性和穩(wěn)定性。

2 動(dòng)態(tài)副本管理優(yōu)化模型DRMO

DRMO是針對(duì)RIRS系統(tǒng)退化為純粹的完全備份時(shí)設(shè)計(jì)的一個(gè)動(dòng)態(tài)副本管理優(yōu)化模型,該模型通過(guò)動(dòng)態(tài)地調(diào)節(jié)副本數(shù)和副本位置改善系統(tǒng)的訪問(wèn)時(shí)延和負(fù)載均衡,主要包括副本數(shù)確定模塊、副本位置選擇模塊和動(dòng)態(tài)副本管理模塊。

2.1 副本數(shù)確定模塊

HDFS中將一個(gè)文件分成m個(gè)數(shù)據(jù)塊,每個(gè)數(shù)據(jù)塊復(fù)制rj份,分散地存儲(chǔ)在不同的數(shù)據(jù)節(jié)點(diǎn)上,一個(gè)數(shù)據(jù)塊只有在所有的副本全失效的情況下才失效,所以數(shù)據(jù)塊的失效率為

(4)

其中fi是數(shù)據(jù)節(jié)點(diǎn)i的故障概率,而一個(gè)文件只有在m個(gè)數(shù)據(jù)塊都有效的情況下才有效,所以有

(5)

假設(shè)用戶定義文件F的預(yù)期有效性為Aexpect,為滿足給定文件有效性的要求,有

(6)

該模型中名字節(jié)點(diǎn)將使用式(6)計(jì)算最小副本數(shù)rmin,以滿足平均數(shù)據(jù)節(jié)點(diǎn)故障概率下預(yù)期有效性的要求。在數(shù)據(jù)節(jié)點(diǎn)故障和當(dāng)前數(shù)據(jù)塊的副本數(shù)小于rmin的情況下,系統(tǒng)就會(huì)增加副本,并將其存入機(jī)架內(nèi)的數(shù)據(jù)節(jié)點(diǎn)上。

2.2 副本位置選擇模塊

為減少數(shù)據(jù)節(jié)點(diǎn)間訪問(wèn)扭曲現(xiàn)象的發(fā)生,進(jìn)而改善負(fù)載均衡和并行度,該模型使用如下數(shù)據(jù)節(jié)點(diǎn)的阻塞率[9]

(7)

作為副本放置的依據(jù)。該模型為實(shí)現(xiàn)負(fù)載均衡將選擇阻塞率最小的數(shù)據(jù)節(jié)點(diǎn)存放副本,同時(shí)為降低分類和查找數(shù)據(jù)節(jié)點(diǎn)的時(shí)延,該模型還采用B+樹(shù)對(duì)數(shù)據(jù)節(jié)點(diǎn)進(jìn)行排序[9]。筆者對(duì)文獻(xiàn)[9]進(jìn)行了改進(jìn),考慮了HDFS的機(jī)架感知策略。將副本分為主副本,缺省副本和其他副本,HDFS中缺省的副本數(shù)為3,包括1個(gè)主副本和2個(gè)缺省副本,其他副本是指HDFS系統(tǒng)中對(duì)熱點(diǎn)數(shù)據(jù)塊增加的副本。機(jī)架感知策略將主副本和第1個(gè)缺省副本存放在同一機(jī)架上,第2個(gè)缺省副本存放在另一遠(yuǎn)程機(jī)架上； 由于其他副本的創(chuàng)建具有動(dòng)態(tài)性,所以放置其他副本時(shí),應(yīng)根據(jù)文件在各機(jī)架中的訪問(wèn)量變化選擇訪問(wèn)次數(shù)最多的機(jī)架作為最佳機(jī)架。因此,放置副本時(shí)應(yīng)先判斷副本的類別再調(diào)用相應(yīng)算法選擇相應(yīng)機(jī)架中的最佳節(jié)點(diǎn)進(jìn)行存放。主副本和缺省副本放置算法實(shí)現(xiàn)如圖7所示,而其他副本放置時(shí)先調(diào)用如圖8所示的算法選擇最佳機(jī)架,再調(diào)用如圖9所示的算法選擇機(jī)架內(nèi)最佳節(jié)點(diǎn)存放。

圖7 主副本和缺省副本的位置選擇算法流程圖 圖8 最佳機(jī)架選擇算法流程圖

圖9 機(jī)架內(nèi)最佳節(jié)點(diǎn)選擇算法流程圖

2.3 動(dòng)態(tài)副本管理模塊

首先根據(jù)上述模型式(7)中參數(shù)的動(dòng)態(tài)變化更新最小副本數(shù)和阻塞率,然后根據(jù)數(shù)據(jù)塊的歷史訪問(wèn)記錄總結(jié)副本訪問(wèn)頻率ai的規(guī)律進(jìn)而得出增加、刪除和遷移副本的訪問(wèn)閾值tmig,tadd和tdel,以動(dòng)態(tài)調(diào)節(jié)系統(tǒng)中的副本數(shù)和副本位置,其流程圖分別如圖10和圖11所示。

圖10 動(dòng)態(tài)副本數(shù)調(diào)整流程圖 圖11 動(dòng)態(tài)副本位置調(diào)整流程圖

2.4 分析小結(jié)

DRMO首先將系統(tǒng)中的副本數(shù)控制在滿足數(shù)據(jù)有效性要求的最小值,然后根據(jù)數(shù)據(jù)訪問(wèn)熱點(diǎn)進(jìn)行調(diào)整,這樣保證了系統(tǒng)中的副本數(shù)既滿足系統(tǒng)要求又避免了因副本數(shù)過(guò)多而造成的存儲(chǔ)空間的浪費(fèi)。此外,DRMO將副本存放到阻塞率最小的數(shù)據(jù)節(jié)點(diǎn)上并根據(jù)訪問(wèn)熱點(diǎn)進(jìn)行遷移調(diào)整,實(shí)現(xiàn)了負(fù)載均衡,降低了訪問(wèn)時(shí)延。

3 結(jié) 語(yǔ)

筆者為改善云存儲(chǔ)系統(tǒng)現(xiàn)有冗余策略的不足,通過(guò)實(shí)驗(yàn)比較選出了適合云存儲(chǔ)系統(tǒng)的最佳糾刪碼,提出將其與完全備份結(jié)合的冗余策略。分析表明,該冗余策略能降低系統(tǒng)存儲(chǔ)空間,降低訪問(wèn)時(shí)延并增強(qiáng)系統(tǒng)的可靠性和穩(wěn)定性。同時(shí),筆者提出的動(dòng)態(tài)副本管理優(yōu)化模型能在該冗余策略退化為完全備份時(shí)實(shí)現(xiàn)負(fù)載均衡。筆者將在今后的研究工作中用該冗余策略具體實(shí)現(xiàn)對(duì)HDFS的改進(jìn),對(duì)分析結(jié)果進(jìn)行驗(yàn)證,并通過(guò)實(shí)驗(yàn)測(cè)試給出應(yīng)用環(huán)境的劃分閾值。

參考文獻(xiàn)：

[1] WU Tin-yu,WEI-TSONG LEE,LIN Yu-san,et al.Dynamic Load Balancing Mechanism Based on Cloud Storage[C]∥Computing,Communications and Applications Conference (ComComAp).Hong Kong:IEEE,2012:102-106.

[2]HWAYOUNG JEONG,JONGHYUK PARK.An Efficient Cloud Storage Model for Cloud Computing Environment[J].Grid and Pervasive Computing Lecture Notes in Computer Science,2012,7296(32):370-376.

[3]YASHASWI SINGH,FARAH KANDAH,ZHANG Wei-yi.A Secured Cost-Effective Multi-Cloud Storage in Cloud Computing[C]∥IEEE Infocom 2011 Workshop on Cloud Computing.Shanghai:IEEE,2011:619-624.

[4]LLUIS PAMIES-JUAREZ,PEDRO GARCIA-LOPEZ,MARC SANCHEZ-ARTIGAS,et al.Towards the Design of Optimal Data Redundancy Schemes for Heterogeneous Cloud Storage Infrastructures[J].Computer Networks,2011,55(5):1100-1113.

[5]HUANG Zhen,YUAN Yuan,PENG Yu-xing.Storage Allocation for Redundancy Scheme in Reliability-Aware Cloud Systems[C]∥Communication Software and Networks (ICCSN),2011 IEEE 3rd International Conference.Xi’an:IEEE,2011:275-279.

[6]MOHAMMED A.ALZAIN,BEN SOH,ERIC PARDEDE.A New Approach Using Redundancy Technique to Improve Security in Cloud Computing[C]∥Cyber Security,Cyber Warfare and Digital Forensic (CyberSec),2012 International Conference.Kuala Lumpur:IEEE,2012:230-235.

[7]SANJAY GHEMAWAT,HOWARD GOBIOFF,SHUNTAK LEUNG.The Google File System[J].ACM SIGOPS Operating Systems Review-SOSP’03 Homepage,2003,37(5):29-43.

[8]KONSTANTIN SHVACHKO,HAIRONG KUANG,SANJAY RADIA,et al.The Hadoop Distributed File System[C]∥2010 IEEE 26th Mass Storage Systems and Technologies (MSST).[S.l.]:IEEE,2012:1-10.

[9]ZENG Ling-fang,FENG Dan,WEI Qing-song,et al.CDRM:A Cost-Effective Dynamic Replication Management Scheme for Cloud Storage Cluster[C]∥IEEE International Conference on Cluster Computing.Heraklion,Crtee:IEEE,2010:188-196.

[10]黑繼偉.基于分布式并行文件系統(tǒng)HDFS的副本管理模型[D].長(zhǎng)春：吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,2010.

HEI Ji-wei.The Replication Management Model Based on Distributed Parallel File System HDFS[D].Changchun:College of Computer Science and Technology,Jilin University,2010.

[11]LI Wen-hao,YANG Yun,CHEN Jin-jun,et al.A Cost-Effective Mechanism for Cloud Data Reliability Management Based on Proactive Replica Checking[C]∥12th IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing.Ottawa,ON:IEEE,2012:564-571.

[12]CAO Ning,YU Shu-cheng,YANG Zhen-yu,et al.LT Codes-Based Secure and Reliable Cloud Storage Service[C]∥Proceedings IEEE Infocom Orlando.FL:IEEE,2012:693-701.

[13]HSIAO-YING LIN,WEN-GUEY TZENG.A Secure Erasure Code-Based Cloud Storage System with Secure Data Forwarding[J].IEEE Transactions on Parallel and Distributed Systems,2012,23(6):995-1003.

[14]WEATHERSPOON H,KUBIATOWICZ J D.Erasure Coding vs Replication:A Quantitative Comparison[C]∥IPTPS’01 Revised Papers from the First International Workshop on Peer-to-Peer Systems.London:Springer-Verlag,2002:328-338.

[15]黃曉云.基于HDFS的云存儲(chǔ)服務(wù)系統(tǒng)研究----分布式架構(gòu)REPEA設(shè)計(jì)與實(shí)現(xiàn)[D].上海：上海交通大學(xué)電子信息與電氣工程學(xué)院,2010.

HUANG Xiao-yun.Research of Cloud Storage Service System Based on HDFS ---- The Design and Implementation of the Distributed Architec ture REPEA[D].Shanghai:College of Electronic Information and Electrical Engineering,Shanghai Jiaotong University,2010.