Hadoop平臺下MapReduce模型的數(shù)據(jù)分配策略研究

余基映，張　騰

(1.湖北民族學(xué)院 科技學(xué)院，湖北 恩施 445000；

2.湖北民族學(xué)院 理學(xué)院，湖北 恩施 445000)

?

Hadoop平臺下MapReduce模型的數(shù)據(jù)分配策略研究

余基映1，張騰2

(1.湖北民族學(xué)院 科技學(xué)院，湖北 恩施 445000；

2.湖北民族學(xué)院 理學(xué)院，湖北 恩施 445000)

摘要：針對Hadoop開源云計算平臺下MapReduce并行編程模型中間數(shù)據(jù)分配不均衡的問題，提出基于抽樣的改進(jìn)型MapReduce模型，即SMR(Sample MapReduce)模型.SMR模型采用MapReduce作業(yè)方式對各分塊數(shù)據(jù)集進(jìn)行并行抽樣，基于抽樣結(jié)果，利用LAB(leen and balance)均衡算法對Map端輸出的中間數(shù)據(jù)進(jìn)行均衡分配，以改善Reduce端處理數(shù)據(jù)負(fù)載不均衡問題.實驗結(jié)果表明：改進(jìn)型MapReduce模型可以有效減少作業(yè)運行時間，Reduce端輸入數(shù)據(jù)達(dá)到負(fù)載均衡.

關(guān)鍵詞：云計算；MapReduce模型；Hadoop；數(shù)據(jù)分配

當(dāng)前，科研、醫(yī)療、網(wǎng)絡(luò)安全及圖形圖像處理等諸多領(lǐng)域?qū)Υ笠?guī)模海量數(shù)據(jù)處理的性能需求與日俱增，云計算作為一種新型的商業(yè)計算模型應(yīng)運而生，并迅速成為互聯(lián)網(wǎng)信息技術(shù)領(lǐng)域的研究熱點[1-6].云計算系統(tǒng)通常采用MapReduce模型[7-9]實現(xiàn)大規(guī)模數(shù)據(jù)集的并行計算和處理,系統(tǒng)后臺采用虛擬技術(shù)產(chǎn)生可自主配置和管理的虛擬資源池，根據(jù)實際需求為各種應(yīng)用系統(tǒng)提供虛擬資源和計算服務(wù).MapReduce模型是一種簡化的分布式編程模型和高效的任務(wù)調(diào)度模型，該模型使得開發(fā)人員不需要感知后臺復(fù)雜的并行計算和任務(wù)調(diào)度，從而降低了編程復(fù)雜度.基于MapReduce模型的Hadoop開發(fā)平臺[10-11]具有較高的可用性、可擴展性和容錯性，是目前主流的開源云計算編程平臺.盡管如此，Hadoop平臺的現(xiàn)有機制并不完善，其MapReduce框架中Map端輸出中間數(shù)據(jù)分配不均衡，從而導(dǎo)致作業(yè)完成時間差較大，大大降低了系統(tǒng)并行作業(yè)的效率.因此，MapReduce任務(wù)負(fù)載均衡問題是限制系統(tǒng)并行作業(yè)效率的關(guān)鍵問題，優(yōu)化和改進(jìn)MapReduce模型以實現(xiàn)中間數(shù)據(jù)的均衡分配對于提高大數(shù)據(jù)處理平臺的業(yè)務(wù)承載能力具有重要意義.目前，關(guān)于改進(jìn)MapReduce模型的研究報道中通常采用添加Balance任務(wù)、路由策略等方法來提高并行計算效率[12-14]，但這些研究尚未成熟，且均未能取得廣泛應(yīng)用.

本文提出改進(jìn)的MapReduce模型，為了提高數(shù)據(jù)集的抽樣效率，采用MapReduce作業(yè)方式對源數(shù)據(jù)集進(jìn)行并行抽樣，同時采用改進(jìn)的LAB分配算法取代Hadoop中默認(rèn)的Hash分配算法，充分考慮數(shù)據(jù)的本地性和公平性因素，減少了數(shù)據(jù)在不同節(jié)點之間傳輸所帶來的網(wǎng)絡(luò)開銷，優(yōu)化了Reduce端任務(wù)節(jié)點的數(shù)據(jù)均衡性，充分利用計算資源，提高了并行程序運行效率.

圖1　原MapReduce模型數(shù)據(jù)分配圖Fig.1　Original data distribution of MapReduce mode

1　MapReduce數(shù)據(jù)分配問題

MapReduce模型把一組鍵值對(keyin，valuein)作為輸入，輸出另外的一組鍵值對(keyout，valueout)，由用戶自定義的Map(映射)函數(shù)和Reduce(規(guī)約)函數(shù)實現(xiàn)上述運算.現(xiàn)有的處理機制首先將每個Map任務(wù)的輸入數(shù)據(jù)進(jìn)行分片處理，分片數(shù)據(jù)塊在不同節(jié)點上并行執(zhí)行，而分片大小由用戶根據(jù)實際情況指定(系統(tǒng)默認(rèn)為64M)，因此，每個Map任務(wù)處理的數(shù)據(jù)量大小確定且基本一致[15].基于計算產(chǎn)生的中間結(jié)果，Map任務(wù)采用系統(tǒng)默認(rèn)的Hash分配算法對其進(jìn)行分區(qū)操作，相同key值下的數(shù)據(jù)集被分配至同一Reduce節(jié)點處理，由于在完成Map階段之后才能確定數(shù)據(jù)集的大小和分布節(jié)點，因此，每個Reduce任務(wù)的數(shù)據(jù)量具有動態(tài)不確定性[16]，表現(xiàn)為Map端輸出的中間數(shù)據(jù)不均衡，從而導(dǎo)致Reduce端數(shù)據(jù)處理負(fù)載不均衡，如圖1所示.

上述數(shù)據(jù)的不均衡分配是由于系統(tǒng)Hash分配算法僅將相同key值的數(shù)據(jù)集分配到同一個Reduce節(jié)點上，該處理方式忽略了每個key值所對應(yīng)數(shù)據(jù)集大小可能不同的情況[17-18].因此，本文提出一種改進(jìn)的MapReduce模型優(yōu)化和改進(jìn)上述數(shù)據(jù)分配不均衡問題.

2　改進(jìn)型MapReduce模型

本文采用MapReduce作業(yè)方式來完成大規(guī)模數(shù)據(jù)集的并行抽樣[19]，并對現(xiàn)有數(shù)據(jù)分配算法進(jìn)行優(yōu)化和改進(jìn)，提出采用LAB(Leen and Balance)均衡算法[15,20]將中間結(jié)果分配至指定Reduce端，為Reduce端提供負(fù)載均衡的數(shù)據(jù)集，從而提高集群中的數(shù)據(jù)本地化率和程序運行效率.

改進(jìn)的MapReduce模型分為兩個MapReduce作業(yè)流程：

1)實現(xiàn)對源數(shù)據(jù)集進(jìn)行并行抽樣，利用并行平臺可以高效獲取抽樣結(jié)果，統(tǒng)計源數(shù)據(jù)集的數(shù)據(jù)量分布信息.

2)基于各分塊數(shù)據(jù)集不同key值下的數(shù)據(jù)量情況完成Map端輸出中間數(shù)據(jù)的均衡分配.

2.1　抽樣模型

通過MapReduce方式對數(shù)據(jù)集進(jìn)行并行抽樣，基于抽樣結(jié)果的數(shù)據(jù)分配策略集合所有mapper的分布式信息，有效保證MapReduce的同步機制，避免長時間等待和阻塞.

各分塊數(shù)據(jù)集隨機抽樣的概率為：p= 1/2N，其中取值為(0，1)，N表示抽樣數(shù)據(jù)集對象key值的個數(shù)，值用于控制樣本大小.每個Map任務(wù)并行完成后對相同key值的記錄進(jìn)行combine操作，從而得到抽樣所得分塊數(shù)據(jù)樣本中某key值(keyi)在節(jié)點nj上的數(shù)量集，表示為s(ki)j.原分塊數(shù)據(jù)中keyi在節(jié)點nj上的數(shù)量集c(ki)j，其無偏估計值如式(1)所示，無偏估計值與真實值的誤差大小由值控制，值越小樣本規(guī)模越大，其誤差值越小.通過Reduce的規(guī)約操作可得出原整塊數(shù)據(jù)中keyi在節(jié)點nj上的數(shù)量集大小為c(ki)，表示為式(2).

(1)

(2)

2.2　數(shù)據(jù)分配算法

基于上述抽樣結(jié)果，采用式(3)來評估數(shù)據(jù)的本地性，其大小為本地節(jié)點的key數(shù)量與分布于各個節(jié)點上所有key數(shù)量的比值，其中c(ki)j為nj節(jié)點上keyi出現(xiàn)的數(shù)量，c(ki)為所有節(jié)點上keyi的數(shù)量之和.

(3)

Reduce端輸入數(shù)據(jù)的均衡性表現(xiàn)為Reduce端處理的數(shù)據(jù)大小基本相同，在MapReduce系統(tǒng)中，作業(yè)的結(jié)束時間取決于最慢的子任務(wù)，因此作業(yè)效率受限于最慢的Reduce任務(wù).在LAB算法中，均衡性的差異Doverload用過載數(shù)據(jù)來表示，其大小為Reduce端最大的輸入數(shù)據(jù)量減去平均值.

(4)

其中：SumNj表示節(jié)點nj上所有key數(shù)量之和，當(dāng)key分配至某節(jié)點后，采用各節(jié)點之間的標(biāo)準(zhǔn)差來評估分配的均衡性，表示為：

(5)

LAB算法對具有不同數(shù)量集的key分配至標(biāo)準(zhǔn)差最小的節(jié)點，key按照c(ki)j值的降序排列，為了提高數(shù)據(jù)分配的本地性，將key分配至原本key數(shù)量最大的節(jié)點上.完成一次key值分配后，計算各節(jié)點上新的數(shù)據(jù)量，進(jìn)行下一個key的分配，采用啟發(fā)式的方法將分布在M個節(jié)點上的N個key值所對應(yīng)的數(shù)據(jù)集依次分配至所期望的Reduce節(jié)點，算法偽代碼如下：

foreachki∈K do

j←0

j←j+1

end while

Partition (ki,ni)

for eachni∈M do

endfor

endfor

其中：K表示為key的集合，M表示為節(jié)點數(shù)量.

圖2　抽樣運行時間對比圖Fig.2　Sampling time of parallel execution and single execution

3　實驗與結(jié)果

3.1實驗環(huán)境

在校園內(nèi)部局域網(wǎng)環(huán)境下搭建Hadoop集群，該實驗集群由四臺計算機組成，包括1個主節(jié)點和3個工作節(jié)點，Hadoop版本是Hadoop-0.20.0，操作系統(tǒng)版本Ubuntu8.0.4，Java環(huán)境為JDK1.5.針對改進(jìn)型Mapreduce模型，采用運行時間和負(fù)載均衡情況來評估系統(tǒng)性能，對三種不同的分配策略進(jìn)行WordCount實驗，數(shù)據(jù)分配策略分別為：Native WordCount(NWC)、Combination Optimization WordCount(COWC)和LAB WordCount(LABWC).

3.2　抽樣

3.3　作業(yè)時間

不同分配策略下系統(tǒng)作業(yè)執(zhí)行時間隨數(shù)據(jù)集傾斜程度的變

圖3　不同傾斜程度下的運行時間Fig.3　Execution time for different degree of data skew

圖4　不同大小數(shù)據(jù)集的運行時間Fig.4　Execution time for different size of dataset

圖5　不同傾斜程度reduce端負(fù)載均衡情況Fig.5　Reduce output for different degree of data skew

圖6　不同大小數(shù)據(jù)集負(fù)載均衡情況Fig.6　Load bananling for different size of dataset

化關(guān)系曲線如圖3所示，數(shù)據(jù)集大小為1G，其中內(nèi)嵌為LABWC作業(yè)變化曲線的放大圖.可以看出，對于相同大小的數(shù)據(jù)集，運行時間隨傾斜程度增加而增加，并且時間差有增大的趨勢.這是由于傾斜程度增大，NWC方式下需要花更多的時間等待數(shù)據(jù)量較大的Reduce端完成作業(yè)，COWC 方式需要合并更多的數(shù)據(jù)集，LABWC方式需要對更多的傾斜數(shù)據(jù)進(jìn)行均衡操作.同時，LABWC作業(yè)方式的整體運行時間小于NWC和COWC作業(yè)方式，不同傾斜程度運行的時間差變化較小，且時間差表現(xiàn)出減小的趨勢.

針對傾斜程度為1.5的數(shù)據(jù)集進(jìn)行WordCount實驗，系統(tǒng)運行時間隨數(shù)據(jù)集大小的變化關(guān)系如圖4所示，可以看出，對于相同傾斜程度而大小不同的數(shù)據(jù)集，運行時間都隨數(shù)據(jù)集增大而增加.LABWC作業(yè)方式與NWC 和COWC作業(yè)方式的運行時間差距隨處理數(shù)據(jù)集的增大明顯增大，從2G數(shù)據(jù)集實驗可以看出LABWC運行時間約為NWC運行時間的一半，比COWC減少了約三分之一，說明改進(jìn)的LAB算法可以有效的提高并行作業(yè)效率.

3.4負(fù)載均衡

采用式(3-6)定義的標(biāo)準(zhǔn)差來評估負(fù)載均衡情況，縱坐標(biāo)Stdev表示標(biāo)準(zhǔn)偏差，橫坐標(biāo)為數(shù)據(jù)集傾斜程度，Stdev值越小表明處理數(shù)據(jù)負(fù)載均衡性越好.采用數(shù)據(jù)集大小為1G，傾斜程度在0.1～1.5之間的數(shù)據(jù)集進(jìn)行WordCount實驗，實驗所得負(fù)載均衡結(jié)果如圖5所示，從圖中可以看出，stdev的變化趨勢與執(zhí)行時間的變化趨勢基本吻合，同時反映出傾斜程度較小時，負(fù)載均衡情況差異較小.隨著傾斜程度的增大，LABWC作業(yè)方式下Reduce端負(fù)載均衡的優(yōu)勢顯現(xiàn)，說明基于抽樣結(jié)果的LAB分配策略可有效改善Map端輸出中間數(shù)據(jù)的均衡分配，使Reduce端處理數(shù)據(jù)大小均衡.

傾斜程度為1.5時不同大小數(shù)據(jù)集處理的負(fù)載均衡情況如圖6所示，從圖中可以看出不同大小數(shù)據(jù)集下LABWC作業(yè)方式的Stdev值均小于其它作業(yè)方式，隨著數(shù)據(jù)集的增大，不同作業(yè)方式下的Stdev值均表現(xiàn)增大趨勢，但NWC和COWC作業(yè)方式增加幅度明顯大于LABWC作業(yè)方式，因此，LABWC作業(yè)方式具有明顯的負(fù)載均衡優(yōu)勢.

4　結(jié)語

基于Hadoop平臺研究了MapReduce模型下的任務(wù)分配機制，提出了改進(jìn)的MapReduce模型，其中利用MapReduce作業(yè)方式實現(xiàn)數(shù)據(jù)集的并行抽樣，同時采用LAB算法優(yōu)化中間數(shù)據(jù)分配不均衡的問題，改進(jìn)的LAB算法兼顧數(shù)據(jù)的本地性和Reduce端輸入的均衡性，大大提高了并行作業(yè)效率.在Hadoop開源平臺上通過實驗集群進(jìn)行性能驗證，結(jié)果表明：改進(jìn)的SMR模型減少了作業(yè)運行時間，且能夠為Reduce端分配負(fù)載均衡的數(shù)據(jù)量，可解決Reduce端輸入數(shù)據(jù)不均衡的性能瓶頸.

參考文獻(xiàn):

[1]Armbrust M,Fox A,Griffith R,et al.A View of Cloud Computing[J].Communications of the ACM,2010,53(4):50-58.

[2]馮登國,張敏,張妍,等.云計算安全研究[J].軟件學(xué)報，2011,22(1):71-83.

[3]張建勛,古志民,鄭超.云計算研究進(jìn)展綜述[J].計算機應(yīng)用研究,2010,27(2):429-433.

[4]陳全,鄧倩妮.云計算及其關(guān)鍵技術(shù)[J].計算機應(yīng)用,2009,29(9):2562-2565.

[5]陳康,鄭緯民.云計算：系統(tǒng)實例與研究現(xiàn)狀[J].軟件學(xué)報,2009,20(5):1337-1348.

[6]李喬,鄭嘯.云計算研究現(xiàn)狀綜述[J].計算機科學(xué)，2011,38(4):32-37.

[7]Dean J,Ghernawat S.MapReduce:Simplified data processing on large clusters[J].Operating Systems Design and Implementation,2008,55(1)：107-113.

[8]Srirama S N,Jakovits P,Vainikko E.Adapting scientific computing problems to clouds using MapReduce[J].Future Generation Computer Systems,2012,28(1):184-192.

[9]Dean J,Ghernawat S.MapReduce:A Flexible Data Processing Tool[J].Communications of the ACM,2010,53(1)：72-77.

[10]Xie G L,Luo S X.Study on application of MapReduce model based on Hadoop[J].Microcomputer & Its Applications,2010,29(8):4-7.

[11]張巖,郭松,趙國海.基于Hadoop的云計算試驗平臺搭建研究[J].沈陽師范大學(xué)學(xué)報：自然科學(xué)版,2013,31(1):85-89.

[12]李玉林,董晶.基于Hadoop的MapReduce模型的研究與改進(jìn)[J].計算機工程與設(shè)計,2012,33(8)：3111-3115.

[13]周鋒,李旭偉.一種改進(jìn)的MapReduce并行編程模型[J].科協(xié)論壇,2009,2(下):65-66.

[14]黃山,王波濤,王國仁,等.MapReduce優(yōu)化技術(shù)綜述[J].計算機科學(xué)與探索,2013(10):865-880.

[15]Kwon Y C,Balazinska M,Howe B,et al.SkewTune: Mitigating Skew in MapReduce Applications[C]//Proceeding of SIGMOD'12 Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data,New York,USA,2012:25-36.

[16]Condie T,Conway N,Alvaro P,et al.MapReduce Online[C]//Proceedings of the NSDL.San Jose,California,USA,2010:33-48.

[17]DeWitt D.MapReduce:A Major Step Backwards[EB/OL].(2008-01-17)[2015-04-23].http://homes.cs.washington.edu/～billhowe/mapreduce_a_major_step_backwards.html.

[18]DeWitt D,Gary J.Parallel Database System:The Future of High Performance Database Systems[J].(2008-01-17).[2015-04-23]Communications of ACM,1992,35(6):85-98.

[19]Xu Y J,Zou P,Qu W Y,et al.Sampling-based Partitioning in MapReduce for Skewed Data[C]//Seventh ChinaGrid Annual Conference,Dalian,China,2012:1-8.

[20]Ibrahim S,Jin H,Lu L,et al.LEEN: Locality/Fairness-Aware Key Partitioning for MapReduce in the Cloud[C]//2nd IEEE International Conference on Cloud Computing Technology and Science,Wuhan,China,2010:17-24.

責(zé)任編輯：時凌

Study on Data Allocation Strategy of MapReduce

Model on Hadoop Platform

YU Jiying，ZHANG Teng

(1.School of Information Engineering,Hubei University for Nationalities, Enshi 445000,China;

2.School of Science,Hubei University for Nationalities, Enshi 445000,China)

Abstract：The existing intermediate data allocation strategy of MapReduce parallel programming model on Hadoop open source computing platform was investigated, to consider the problem of partitioning imbalance.The improved MapReduce model,SMR (Sample-MapReduce) was proposed. In order to provide a load-balanced partition scheme,the MapReduce method was adopted to parallelly sample the data block,and LAB (leen and balance) balancing allocation strategy was used to distribute the output intermediate data of Map task.The results show that the improved MapReduces model significantly reduces the running time of the MapReduce job,and the input data of reduce task achieve load balance.

Key words：cloud computing；Hadoop； MapReduce；data distribution

中圖分類號：TP303

文獻(xiàn)標(biāo)志碼：A