云存儲系統(tǒng)中數(shù)據(jù)冗余策略優(yōu)化問題

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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 HDFS與RIRS占用空間

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

1.2 RIRS中糾刪碼的選擇

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

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

(1)

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

A′D=E′

(2)

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

D=(A′)-1E′

(3)

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

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

圖1 RS糾刪碼編碼過程

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

圖2 RS糾刪碼解碼過程

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

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

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

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

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

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

圖6 RS碼與其改進算法的解碼時間對比

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

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

圖6表明,改進后的RS碼降低了RS碼的編解碼時延。

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

1.3 分析小結(jié)

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

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

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

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

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

(4)

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

(5)

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

(6)

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

2.2 副本位置選擇模塊

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

(7)

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

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

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

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

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

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

2.4 分析小結(jié)

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

3 結(jié) 語

筆者為改善云存儲系統(tǒng)現(xiàn)有冗余策略的不足,通過實驗比較選出了適合云存儲系統(tǒng)的最佳糾刪碼,提出將其與完全備份結(jié)合的冗余策略。分析表明,該冗余策略能降低系統(tǒng)存儲空間,降低訪問時延并增強系統(tǒng)的可靠性和穩(wěn)定性。同時,筆者提出的動態(tài)副本管理優(yōu)化模型能在該冗余策略退化為完全備份時實現(xiàn)負載均衡。筆者將在今后的研究工作中用該冗余策略具體實現(xiàn)對HDFS的改進,對分析結(jié)果進行驗證,并通過實驗測試給出應(yīng)用環(huá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].長春：吉林大學(xué)計算機科學(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的云存儲服務(wù)系統(tǒng)研究----分布式架構(gòu)REPEA設(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.