HDFS平臺(tái)下基于糾刪碼的一種數(shù)據(jù)放置策略*

孔晨燕， 趙建民， 朱信忠， 徐慧英

(浙江師范大學(xué)數(shù)理與信息工程學(xué)院，浙江金華 321004)

HDFS平臺(tái)下基于糾刪碼的一種數(shù)據(jù)放置策略*

孔晨燕， 趙建民， 朱信忠， 徐慧英

(浙江師范大學(xué)數(shù)理與信息工程學(xué)院，浙江金華 321004)

數(shù)據(jù)的可靠性一直是云計(jì)算領(lǐng)域中的熱點(diǎn)問(wèn)題，副本備份機(jī)制作為保證數(shù)據(jù)可靠性的重要手段應(yīng)用比較廣泛.但隨著副本個(gè)數(shù)的增加，該機(jī)制浪費(fèi)存儲(chǔ)空間這一缺陷暴露無(wú)遺.為節(jié)省存儲(chǔ)空間，采用糾刪碼技術(shù)保證數(shù)據(jù)的可靠性，提出了在HDFS平臺(tái)下基于糾刪碼的一種數(shù)據(jù)放置策略.該策略以HDFS為平臺(tái)，結(jié)合HDFS的副本備份策略和糾刪碼技術(shù)，通過(guò)改進(jìn)HDFS平臺(tái)下原本的數(shù)據(jù)放置策略，使改進(jìn)后的數(shù)據(jù)放置策略能夠適用于基于糾刪碼和HDFS的云文件系統(tǒng).

云計(jì)算;HDFS;副本備份;糾刪碼;數(shù)據(jù)放置

0 引言

數(shù)據(jù)的可靠性作為云計(jì)算領(lǐng)域中的熱點(diǎn)問(wèn)題一直倍受人們的關(guān)注.為保證數(shù)據(jù)的可靠性，應(yīng)用比較廣泛的手段是副本備份機(jī)制，它簡(jiǎn)單直觀，易于實(shí)現(xiàn)和部署，但是需為每個(gè)數(shù)據(jù)對(duì)象創(chuàng)建若干相同副本，所需存儲(chǔ)空間較大.而基于糾刪碼的容錯(cuò)方式則能夠把多個(gè)數(shù)據(jù)塊的信息融合到較少的冗余信息中，因而能夠節(jié)省存儲(chǔ)空間.

目前，云計(jì)算環(huán)境下分布式存儲(chǔ)應(yīng)用中的數(shù)據(jù)放置策略都比較簡(jiǎn)單，比如機(jī)架無(wú)關(guān)(rack unware)、機(jī)架相關(guān)(rack aware)、數(shù)據(jù)中心相關(guān)(datacenter aware)等策略，或者順序放置、隨機(jī)放置等策略.這些策略大都針對(duì)基于復(fù)制的容錯(cuò)技術(shù)［1］.本文針對(duì)基于糾刪碼的數(shù)據(jù)放置策略展開研究，提出了HDFS(Hadoop Distributed File System，Hadoop分布式文件系統(tǒng))平臺(tái)下基于糾刪碼的一種數(shù)據(jù)放置策略.該策略以HDFS為平臺(tái)，結(jié)合HDFS的副本備份策略和糾刪碼技術(shù)，通過(guò)改進(jìn)HDFS平臺(tái)下原本的數(shù)據(jù)放置策略，使改進(jìn)后的數(shù)據(jù)放置策略能夠適用于基于糾刪碼和HDFS的云文件系統(tǒng).

1 糾刪碼

糾刪碼提供了一種存儲(chǔ)優(yōu)化的冗余機(jī)制來(lái)保證數(shù)據(jù)的可靠性［2］，它可以用一個(gè)四元組(n，k，b，k')來(lái)描述，其中k為編碼前的文件塊數(shù)，n為編碼后的文件塊數(shù)，b為每塊文件所含的比特?cái)?shù)，k'是大于或者等于k的正整數(shù).首先將要存儲(chǔ)的文件塊分為k份相等的數(shù)據(jù)塊，記每份數(shù)據(jù)塊的大小為b比特，則編碼前的文件可以表示為F=(F1，F(xiàn)2，…，F(xiàn)k).設(shè)糾刪碼的編碼函數(shù)是E，解碼函數(shù)是D，對(duì)原文件進(jìn)行編碼，文件編碼后生成n個(gè)數(shù)據(jù)塊，編碼后的數(shù)據(jù)塊大小仍為b比特.設(shè)E(F')是E(F)中任意k'(k'≥k)個(gè)文件組成的子文件，那么D(E(F'))=F.由糾刪碼的性質(zhì)可知，當(dāng)系統(tǒng)中部分節(jié)點(diǎn)失效，用戶依舊可以根據(jù)余下可得的文件來(lái)恢復(fù)原文件.也就是說(shuō)一定數(shù)量的節(jié)點(diǎn)失效并不會(huì)造成用戶數(shù)據(jù)的丟失.

相關(guān)研究表明，糾刪碼在存儲(chǔ)空間上和數(shù)據(jù)可用性及容錯(cuò)能力上優(yōu)于完全復(fù)制，在容侵能力上與完全復(fù)制基本差不多［3］.

2 HDFS的數(shù)據(jù)放置策略

HDFS采用主從式的結(jié)構(gòu)管理體系，集群中有一個(gè)NameNode和多個(gè)DataNode，NameNode負(fù)責(zé)數(shù)據(jù)放置節(jié)點(diǎn)的選擇和DataNode的管理，Data－Node負(fù)責(zé)數(shù)據(jù)塊的存儲(chǔ)［4－5］.其默認(rèn)情況下根據(jù)部署在集群上的默認(rèn)機(jī)架感知策略［6］進(jìn)行數(shù)據(jù)副本的放置，而數(shù)據(jù)放置策略是基于完全復(fù)制機(jī)制的.HDFS系統(tǒng)為每個(gè)數(shù)據(jù)塊保存3個(gè)副本，客戶節(jié)點(diǎn)本地機(jī)架上放置2個(gè)，第3個(gè)放置于隨機(jī)遠(yuǎn)端機(jī)架的隨機(jī)節(jié)點(diǎn)上.如果還需存放更多副本，則在整個(gè)集群中隨機(jī)選取節(jié)點(diǎn)存放.當(dāng)本地節(jié)點(diǎn)都失效時(shí)，HDFS系統(tǒng)將自動(dòng)通過(guò)遠(yuǎn)端機(jī)架上的數(shù)據(jù)副本，將數(shù)據(jù)副本的數(shù)量恢復(fù)到標(biāo)準(zhǔn)值.

3 HDFS下基于糾刪碼的數(shù)據(jù)放置策略

3.1 相對(duì)負(fù)載

目前的HDFS版本都假設(shè)集群中的節(jié)點(diǎn)是同構(gòu)的，而在實(shí)際的云存儲(chǔ)系統(tǒng)中節(jié)點(diǎn)的同構(gòu)性并不理想，部分節(jié)點(diǎn)之間還可能存在較大的性能差異.因此，給各個(gè)數(shù)據(jù)節(jié)點(diǎn)平均分配數(shù)據(jù)量的做法并不符合HDFS集群的特點(diǎn).本文提出的數(shù)據(jù)放置策略，引入相對(duì)負(fù)載作為節(jié)點(diǎn)評(píng)價(jià)標(biāo)準(zhǔn)，根據(jù)數(shù)據(jù)節(jié)點(diǎn)的存儲(chǔ)性能及已經(jīng)存儲(chǔ)的數(shù)據(jù)量進(jìn)行節(jié)點(diǎn)的選擇.

本文使用節(jié)點(diǎn)已經(jīng)存儲(chǔ)的數(shù)據(jù)量N(i)與節(jié)點(diǎn)的存儲(chǔ)性能P(i)的比值表示節(jié)點(diǎn)的相對(duì)負(fù)載L(i)，即

其中節(jié)點(diǎn)已經(jīng)存儲(chǔ)的數(shù)據(jù)量N(i)表示存儲(chǔ)的數(shù)據(jù)占用的磁盤空間大小，在HDFS啟動(dòng)時(shí)DadaN－ode通過(guò)org.apache.hadoop.fs.DF類來(lái)實(shí)現(xiàn)unix的df命令，以此獲得本地磁盤的使用情況.節(jié)點(diǎn)存儲(chǔ)性能P(i)包括節(jié)點(diǎn)CPU性能、內(nèi)存大小、存儲(chǔ)設(shè)備的存儲(chǔ)速度、系統(tǒng)結(jié)構(gòu)等［7］.為了提高數(shù)據(jù)放置效率，計(jì)算節(jié)點(diǎn)的存儲(chǔ)性能時(shí)，主要考慮CPU性能(記為C)、內(nèi)存大小(記為M)和存儲(chǔ)設(shè)備的存儲(chǔ)速度(記為V).則集群中某一節(jié)點(diǎn)i的存儲(chǔ)性能可以表示為

δ1，δ2，δ3是各性能的權(quán)重因子(δ1+δ2+δ3=1)，取值為0～1，用戶可以根據(jù)具體情況下各因素的重要程度設(shè)置權(quán)重因子.目前有很多CPU和磁盤性能的測(cè)試軟件，可通過(guò)這些軟件獲得性能參數(shù)，從而計(jì)算出集群中節(jié)點(diǎn)的存儲(chǔ)性能.

3.2 基于糾刪碼的數(shù)據(jù)放置策略的總體思路

客戶機(jī)在上傳文件時(shí)將文件分塊，對(duì)分塊后的文件進(jìn)行編碼，將編碼后的文件直接上傳到DataNode.在HDFS啟動(dòng)時(shí)，集群中的所有節(jié)點(diǎn)直接計(jì)算出與其他節(jié)點(diǎn)之間的距離，DataNode計(jì)算出本地磁盤的使用情況及本節(jié)點(diǎn)的存儲(chǔ)性能，并發(fā)送給NameNode.由節(jié)點(diǎn)已存儲(chǔ)數(shù)據(jù)占用的磁盤空間大小和其存儲(chǔ)性能可以計(jì)算出節(jié)點(diǎn)的相對(duì)負(fù)載.DataNode會(huì)在內(nèi)存中保存一個(gè)NameNode與相對(duì)負(fù)載的對(duì)照表及系統(tǒng)的平均相對(duì)負(fù)載，在存儲(chǔ)數(shù)據(jù)塊的過(guò)程中同步更新這個(gè)對(duì)照表，以及系統(tǒng)平均相對(duì)負(fù)載.在上傳編碼后的文件塊時(shí)，NameNode選擇距離上傳節(jié)點(diǎn)最近的機(jī)架，在機(jī)架中找到相對(duì)負(fù)載最小且放置數(shù)據(jù)后系統(tǒng)的負(fù)載平衡不會(huì)被打破的節(jié)點(diǎn)作為文件塊的放置節(jié)點(diǎn).

本策略通過(guò)當(dāng)前節(jié)點(diǎn)的相對(duì)負(fù)載L(i)與系統(tǒng)中的平均相對(duì)負(fù)載LA的差值是否大于閾值LR來(lái)判斷系統(tǒng)的是否平衡.若L(i)－LA＞LR，則認(rèn)為該節(jié)點(diǎn)的負(fù)載過(guò)重，系統(tǒng)的負(fù)載平衡被打破，反之則認(rèn)為系統(tǒng)的負(fù)載仍然平衡.其中平均相對(duì)負(fù)載是集群中所有節(jié)點(diǎn)的相對(duì)負(fù)載的平均值，記為

其中TN為集群中的節(jié)點(diǎn)總數(shù).

另外，根據(jù)保存的文件重要性確定HDFS集群的備份參數(shù)dfs.replication的值，將相當(dāng)重要的設(shè)置為2，這就實(shí)現(xiàn)了每個(gè)文件的編碼數(shù)據(jù)塊都有2個(gè)副本保存在HDFS集群中，應(yīng)用糾刪碼和備份雙重機(jī)制保障數(shù)據(jù)的可靠性.如果保存的是普通文件，則將值設(shè)置為1，直接用糾刪碼保證數(shù)據(jù)的可靠性，最大程度節(jié)約HDFS集群的存儲(chǔ)空間.

3.3 HDFS下基于糾刪碼的數(shù)據(jù)放置策略過(guò)程

在上傳文件時(shí)，上傳節(jié)點(diǎn)首先對(duì)文件進(jìn)行分塊，按照一定的比例對(duì)分塊所得的數(shù)據(jù)塊進(jìn)行編碼，然后將編碼后的數(shù)據(jù)塊上傳到 HDFS上.HDFS下基于糾刪碼的數(shù)據(jù)放置策略的過(guò)程如圖1所示.由圖1可知，數(shù)據(jù)放置策略的過(guò)程可以描述如下:

1)當(dāng)用戶提交數(shù)據(jù)存儲(chǔ)的請(qǐng)求時(shí)，計(jì)算網(wǎng)絡(luò)拓?fù)渲信c客戶端節(jié)點(diǎn)網(wǎng)絡(luò)距離最近的機(jī)架，并返回機(jī)架ID，記為N.標(biāo)記為已選擇或不平衡的機(jī)架不在選擇之列.若沒(méi)有可用機(jī)架，則返回NULL.

2)若返回值為NULL，即已沒(méi)有可用機(jī)架，則過(guò)程結(jié)束，否則繼續(xù)下一步.

3)判斷機(jī)架N中文件F的數(shù)據(jù)塊總數(shù)是否大于或等于n－k－1，若滿足條件則將該機(jī)架標(biāo)記為已選擇，在后續(xù)的機(jī)架選擇中不再列入考慮范圍.如果不滿足條件，就繼續(xù)下一步.

4)找出機(jī)架N中相對(duì)負(fù)載最低的節(jié)點(diǎn)，并返回其ID.若沒(méi)有節(jié)點(diǎn)可選，則返回NULL.

5)若返回值為NULL，即已沒(méi)有節(jié)點(diǎn)可選擇，則將機(jī)架N標(biāo)記為不平衡，在后續(xù)的機(jī)架選擇中不再列入考慮范圍，返回第一步.否則繼續(xù)下一步.

6)若加入提交的數(shù)據(jù)塊后系統(tǒng)的平衡被打破，則將此節(jié)點(diǎn)標(biāo)記為不平衡，在后續(xù)的節(jié)點(diǎn)選擇中不再列入考慮范圍，返回步驟4.否則此節(jié)點(diǎn)即為用戶提交數(shù)據(jù)塊的存儲(chǔ)節(jié)點(diǎn)，記為DW，繼續(xù)下一步.

7)將用戶提交的數(shù)據(jù)塊寫入節(jié)點(diǎn)DW.

8)將HDFS集群的備份參數(shù)dfs.replication的值賦給X，若X≠1，則將X的值減1，參照完成復(fù)制的冗余機(jī)制，隨機(jī)選擇除機(jī)架N外的其他機(jī)架N'，記N'為N，返回步驟4.若X=1，則繼續(xù)下一步.

9)若數(shù)據(jù)上傳完成，則整個(gè)過(guò)程結(jié)束.若數(shù)據(jù)上傳未完成，則取消機(jī)架和節(jié)點(diǎn)的不平衡標(biāo)記，返回步驟1，重新上傳新的數(shù)據(jù)塊.

圖1 HDFS下基于糾刪碼的數(shù)據(jù)放置策略過(guò)程圖

4 實(shí)驗(yàn)結(jié)果與分析

本文選用Reed－Solomon碼作為糾刪碼，使用Java編寫Reed Solomon編解碼器模塊，它包括編碼和解碼2個(gè)模塊，應(yīng)用范德萌矩陣方法實(shí)現(xiàn)對(duì)數(shù)據(jù)塊的編碼和解碼操作.

為了測(cè)試系統(tǒng)中編解碼器模塊的效率，分別選取大小為64，120，250，500，1 000，1 500 MB的文件進(jìn)行編碼和解碼，每個(gè)文件分別編碼、解碼5次取平均值作為結(jié)果.實(shí)驗(yàn)中k與n的比例為5∶8.所得編解碼時(shí)間如表1所示，編解碼的時(shí)間單位為s.

表1 編碼器模塊編解碼時(shí)間 s

由表1可看出，編解碼速度隨著文件的增大有所下降，但是下降到一定程度即趨于穩(wěn)定.當(dāng)文件大小為64～1 500 MB時(shí)，系統(tǒng)的編碼和解碼速度是174～78 MB/s，能夠滿足系統(tǒng)的性能要求.

使用Hadoop－0.20.1進(jìn)行實(shí)驗(yàn)環(huán)境的搭建，對(duì)所提出的策略進(jìn)行了試驗(yàn).試驗(yàn)集群中有3個(gè)機(jī)架(機(jī)架A、機(jī)架B、機(jī)架C)，每個(gè)機(jī)架5個(gè)節(jié)點(diǎn)，分別記為D1，D2，D3，D4，D5.在實(shí)驗(yàn)中，機(jī)架A上的D1作為提交文件的節(jié)點(diǎn)，不考慮存儲(chǔ)性能，該節(jié)點(diǎn)一共上傳1 000個(gè)數(shù)據(jù)塊到集群，假設(shè)系統(tǒng)啟動(dòng)時(shí)所有的節(jié)點(diǎn)都處于空載狀態(tài).實(shí)驗(yàn)中P(i)各權(quán)重都設(shè)為1/3，閾值LR設(shè)置為20.機(jī)架A中D2到D5存儲(chǔ)性能分別為13.9，14.7，15.3， 12.1.機(jī)架B中D1到D5存儲(chǔ)性能分別為11.4，15.3，12.9，12.5，13.5.機(jī)架C中D1到D5存儲(chǔ)性能分別為12.6，13.2，14.3，12.3，13.7.

首先采用HDFS默認(rèn)的數(shù)據(jù)放置策略，使用相對(duì)負(fù)載的概念對(duì)集群中各數(shù)據(jù)節(jié)點(diǎn)的負(fù)載情況進(jìn)行了統(tǒng)計(jì)，結(jié)果如圖2(a)所示.接著采用本文的基于糾刪碼的數(shù)據(jù)放置策略，取k與n的比例為5∶8，實(shí)驗(yàn)中一共有1 000個(gè)數(shù)據(jù)塊，則經(jīng)過(guò)編碼后有1 600個(gè)數(shù)據(jù)塊，將數(shù)據(jù)塊上傳到HDFS后各節(jié)點(diǎn)的負(fù)載情況如圖2(b)所示.

對(duì)比圖2中的(a)與(b)可知，以相對(duì)負(fù)載為評(píng)價(jià)標(biāo)準(zhǔn)，本文提出的基于糾刪碼的數(shù)據(jù)放置策略能夠保證機(jī)架中各數(shù)據(jù)節(jié)點(diǎn)的負(fù)載均衡.

圖2 不同策略下集群中各節(jié)點(diǎn)的相對(duì)負(fù)載情況

為了檢驗(yàn)本文提出的數(shù)據(jù)放置策略所帶來(lái)的時(shí)間開銷，在相同的環(huán)境下，分別使用本文提出的方法與默認(rèn)放置策略向HDFS內(nèi)的同一個(gè)數(shù)據(jù)節(jié)點(diǎn)提交同樣大小的文件，記錄從發(fā)出文件提交請(qǐng)求到文件存儲(chǔ)完成所用的時(shí)間.由于HDFS存儲(chǔ)的數(shù)據(jù)塊默認(rèn)為64 MB.因此，在實(shí)驗(yàn)中，分別在采用默認(rèn)策略與改進(jìn)策略的情況下，提交一個(gè)320 MB的文件，每個(gè)文件被分為5個(gè)大小為64 MB的數(shù)據(jù)塊，統(tǒng)計(jì)其從NameNode接到請(qǐng)求到數(shù)據(jù)存儲(chǔ)完成所需要的時(shí)間，在測(cè)試過(guò)程中進(jìn)行4次相同操作，操作結(jié)果如表2所示.

由表2可知，在本試驗(yàn)中，本文提出的策略使用的時(shí)間少于HDFS默認(rèn)策略.綜上所述，本文提出的數(shù)據(jù)放置策略通過(guò)使用基于糾刪碼的冗余機(jī)制替換原有的基于完全復(fù)制的冗余機(jī)制，結(jié)合機(jī)架之間的網(wǎng)絡(luò)距離和節(jié)點(diǎn)相對(duì)負(fù)載，選擇離本地機(jī)架最近且相對(duì)負(fù)載最低的節(jié)點(diǎn)作為數(shù)據(jù)放置節(jié)點(diǎn).此策略減少了數(shù)據(jù)副本存放的數(shù)量，不但能夠減少存儲(chǔ)空間的浪費(fèi)，還能減少存放數(shù)據(jù)副本的時(shí)間開銷.另一方面也可以降低數(shù)據(jù)節(jié)點(diǎn)之間存儲(chǔ)負(fù)載的不平衡，特別是能夠在一個(gè)機(jī)架內(nèi)實(shí)現(xiàn)各個(gè)數(shù)據(jù)節(jié)點(diǎn)較為平均的數(shù)據(jù)塊存儲(chǔ).

表2 本文的策略和默認(rèn)策略的時(shí)間開銷

5 結(jié)語(yǔ)

本文討論了HDFS系統(tǒng)中關(guān)于數(shù)據(jù)放置策略的相關(guān)問(wèn)題，提出了HDFS平臺(tái)下基于糾刪碼的一種數(shù)據(jù)放置策略，從仿真實(shí)驗(yàn)看來(lái)，其在存儲(chǔ)空間及時(shí)間開銷方面都優(yōu)于HDFS默認(rèn)的數(shù)據(jù)放置策略，而且該策略降低了數(shù)據(jù)節(jié)點(diǎn)之間存儲(chǔ)負(fù)載的不平衡.

［1］王意潔，孫偉東.云計(jì)算環(huán)境下的分布存儲(chǔ)關(guān)鍵技術(shù)［J］.軟件學(xué)報(bào)，2012，23(4):962－986.

［2］Rizzo L.Effective erasure codes for reliable computer communication protocols［J］.ACM SIGCOMM Computer Communication Review，1997，27(2):24－36.

［3］孫程，謝軍.一種基于糾刪碼的分布式存儲(chǔ)容災(zāi)的設(shè)計(jì)與實(shí)驗(yàn)［J］.中國(guó)集成電路，2009(10):38－42.

［4］Theapache software foundation.HDFS architecture Guide，2014［EB/OL］.［2014－08－10］.http://hadoop.apache.org/docs/current/hadoopproject－dist/hadoop－h(huán)dfs/HdfsDesign.html.

［5］Shvachko K，Kuang H，Radia S.The hadoop distributed file system［C］//IEEE Conference Publications.Proc.of the IEEE 26th Symp.on Mass storage Systems and Technologies(MSST).Lake Tahoe:IEEE，2010:1－10.

［6］BorthakurD.Hadoop［EB/OL］.［2011－06－15］.http://lucene.apache.org/hadoop.

［7］王永洲，茅蘇.HDFS中的一種數(shù)據(jù)放置策略［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2013，23(5):90－96.

(責(zé)任編輯 杜利民)

A data placement strategy based on erasure code in the platform of HDFS

KONG Chenyan， ZHAO Jianmin， ZHU Xinzhong， XU Huiying

(College of Mathematics，Physics and Information Engineering，Zhejiang Normal University，Jinhua Zhejiang 321004，China)

Reliability of data was a hot topic in the field of cloud computing.The mechanism of backup as an important mean to ensure the reliability of data had been used widely，but with the increase of the number of copies，the defect of storage space wasting in this mechanism had been exposed.To save storage space，the technology of erasure codes was used to ensure the reliability of data.It was proposed a data placement strategy in the platform of HDFS.This strategy used HDFS as the platform，combining backup strategy of HDFS and technology of erasure code.The improved data placement strategy proposed could be applied to the cloud file system based on erasure code and HDFS by improving the original data storage strategy in the HDFS platform.

cloud computing;HDFS;copy backup;erasure code;dataplacement

TP393

A

1001－5051(2015)01－0089－06

?:2014－10－27;

2014－11－19

國(guó)家自然科學(xué)基金資助項(xiàng)目(61272468)

孔晨燕(1991－)，女，江蘇鎮(zhèn)江人，碩士研究生.研究方向:大數(shù)據(jù)和云計(jì)算.

趙建民.E－mail:zjm@zjnu.cn

10.16218/j.issn.1001－5051.2015.01.015