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

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

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

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

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

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

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

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

0 引言

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

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

1 糾刪碼

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

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

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

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

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

3.1 相對負載

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

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

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

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

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

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

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

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

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

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

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

1)當用戶提交數(shù)據(jù)存儲的請求時，計算網(wǎng)絡拓撲中與客戶端節(jié)點網(wǎng)絡距離最近的機架，并返回機架ID，記為N.標記為已選擇或不平衡的機架不在選擇之列.若沒有可用機架，則返回NULL.

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

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

4)找出機架N中相對負載最低的節(jié)點，并返回其ID.若沒有節(jié)點可選，則返回NULL.

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

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

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

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

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

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

4 實驗結(jié)果與分析

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

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

表1 編碼器模塊編解碼時間 s

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

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

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

對比圖2中的(a)與(b)可知，以相對負載為評價標準，本文提出的基于糾刪碼的數(shù)據(jù)放置策略能夠保證機架中各數(shù)據(jù)節(jié)點的負載均衡.

圖2 不同策略下集群中各節(jié)點的相對負載情況

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

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

表2 本文的策略和默認策略的時間開銷

5 結(jié)語

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

［1］王意潔，孫偉東.云計算環(huán)境下的分布存儲關(guān)鍵技術(shù)［J］.軟件學報，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］孫程，謝軍.一種基于糾刪碼的分布式存儲容災的設計與實驗［J］.中國集成電路，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］.計算機技術(shù)與發(fā)展，2013，23(5):90－96.

(責任編輯 杜利民)

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

國家自然科學基金資助項目(61272468)

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

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

10.16218/j.issn.1001－5051.2015.01.015