余基映，张　腾

(1.湖北民族学院 科技学院，湖北 恩施 445000；

2.湖北民族学院 理学院，湖北 恩施 445000)



Hadoop平台下MapReduce模型的数据分配策略研究

余基映1，张腾2

(1.湖北民族学院 科技学院，湖北 恩施 445000；

2.湖北民族学院 理学院，湖北 恩施 445000)

摘要：针对Hadoop开源云计算平台下MapReduce并行编程模型中间数据分配不均衡的问题，提出基于抽样的改进型MapReduce模型，即SMR(Sample MapReduce)模型.SMR模型采用MapReduce作业方式对各分块数据集进行并行抽样，基于抽样结果，利用LAB(leen and balance)均衡算法对Map端输出的中间数据进行均衡分配，以改善Reduce端处理数据负载不均衡问题.实验结果表明：改进型MapReduce模型可以有效减少作业运行时间，Reduce端输入数据达到负载均衡.

关键词：云计算；MapReduce模型；Hadoop；数据分配

当前，科研、医疗、网络安全及图形图像处理等诸多领域对大规模海量数据处理的性能需求与日俱增，云计算作为一种新型的商业计算模型应运而生，并迅速成为互联网信息技术领域的研究热点[1-6].云计算系统通常采用MapReduce模型[7-9]实现大规模数据集的并行计算和处理,系统后台采用虚拟技术产生可自主配置和管理的虚拟资源池，根据实际需求为各种应用系统提供虚拟资源和计算服务.MapReduce模型是一种简化的分布式编程模型和高效的任务调度模型，该模型使得开发人员不需要感知后台复杂的并行计算和任务调度，从而降低了编程复杂度.基于MapReduce模型的Hadoop开发平台[10-11]具有较高的可用性、可扩展性和容错性，是目前主流的开源云计算编程平台.尽管如此，Hadoop平台的现有机制并不完善，其MapReduce框架中Map端输出中间数据分配不均衡，从而导致作业完成时间差较大，大大降低了系统并行作业的效率.因此，MapReduce任务负载均衡问题是限制系统并行作业效率的关键问题，优化和改进MapReduce模型以实现中间数据的均衡分配对于提高大数据处理平台的业务承载能力具有重要意义.目前，关于改进MapReduce模型的研究报道中通常采用添加Balance任务、路由策略等方法来提高并行计算效率[12-14]，但这些研究尚未成熟，且均未能取得广泛应用.

本文提出改进的MapReduce模型，为了提高数据集的抽样效率，采用MapReduce作业方式对源数据集进行并行抽样，同时采用改进的LAB分配算法取代Hadoop中默认的Hash分配算法，充分考虑数据的本地性和公平性因素，减少了数据在不同节点之间传输所带来的网络开销，优化了Reduce端任务节点的数据均衡性，充分利用计算资源，提高了并行程序运行效率.

图1　原MapReduce模型数据分配图Fig.1　Original data distribution of MapReduce mode

1　MapReduce数据分配问题

MapReduce模型把一组键值对(keyin，valuein)作为输入，输出另外的一组键值对(keyout，valueout)，由用户自定义的Map(映射)函数和Reduce(规约)函数实现上述运算.现有的处理机制首先将每个Map任务的输入数据进行分片处理，分片数据块在不同节点上并行执行，而分片大小由用户根据实际情况指定(系统默认为64M)，因此，每个Map任务处理的数据量大小确定且基本一致[15].基于计算产生的中间结果，Map任务采用系统默认的Hash分配算法对其进行分区操作，相同key值下的数据集被分配至同一Reduce节点处理，由于在完成Map阶段之后才能确定数据集的大小和分布节点，因此，每个Reduce任务的数据量具有动态不确定性[16]，表现为Map端输出的中间数据不均衡，从而导致Reduce端数据处理负载不均衡，如图1所示.

上述数据的不均衡分配是由于系统Hash分配算法仅将相同key值的数据集分配到同一个Reduce节点上，该处理方式忽略了每个key值所对应数据集大小可能不同的情况[17-18].因此，本文提出一种改进的MapReduce模型优化和改进上述数据分配不均衡问题.

2　改进型MapReduce模型

本文采用MapReduce作业方式来完成大规模数据集的并行抽样[19]，并对现有数据分配算法进行优化和改进，提出采用LAB(Leen and Balance)均衡算法[15,20]将中间结果分配至指定Reduce端，为Reduce端提供负载均衡的数据集，从而提高集群中的数据本地化率和程序运行效率.

改进的MapReduce模型分为两个MapReduce作业流程：

1)实现对源数据集进行并行抽样，利用并行平台可以高效获取抽样结果，统计源数据集的数据量分布信息.

2)基于各分块数据集不同key值下的数据量情况完成Map端输出中间数据的均衡分配.

2.1　抽样模型

通过MapReduce方式对数据集进行并行抽样，基于抽样结果的数据分配策略集合所有mapper的分布式信息，有效保证MapReduce的同步机制，避免长时间等待和阻塞.

各分块数据集随机抽样的概率为：p= 1/2N，其中取值为(0，1)，N表示抽样数据集对象key值的个数，值用于控制样本大小.每个Map任务并行完成后对相同key值的记录进行combine操作，从而得到抽样所得分块数据样本中某key值(keyi)在节点nj上的数量集，表示为s(ki)j.原分块数据中keyi在节点nj上的数量集c(ki)j，其无偏估计值如式(1)所示，无偏估计值与真实值的误差大小由值控制，值越小样本规模越大，其误差值越小.通过Reduce的规约操作可得出原整块数据中keyi在节点nj上的数量集大小为c(ki)，表示为式(2).

(1)

(2)

2.2　数据分配算法

基于上述抽样结果，采用式(3)来评估数据的本地性，其大小为本地节点的key数量与分布于各个节点上所有key数量的比值，其中c(ki)j为nj节点上keyi出现的数量，c(ki)为所有节点上keyi的数量之和.

(3)

Reduce端输入数据的均衡性表现为Reduce端处理的数据大小基本相同，在MapReduce系统中，作业的结束时间取决于最慢的子任务，因此作业效率受限于最慢的Reduce任务.在LAB算法中，均衡性的差异Doverload用过载数据来表示，其大小为Reduce端最大的输入数据量减去平均值.

(4)

其中：SumNj表示节点nj上所有key数量之和，当key分配至某节点后，采用各节点之间的标准差来评估分配的均衡性，表示为：

(5)

LAB算法对具有不同数量集的key分配至标准差最小的节点，key按照c(ki)j值的降序排列，为了提高数据分配的本地性，将key分配至原本key数量最大的节点上.完成一次key值分配后，计算各节点上新的数据量，进行下一个key的分配，采用启发式的方法将分布在M个节点上的N个key值所对应的数据集依次分配至所期望的Reduce节点，算法伪代码如下：

foreachki∈K do

j←0

j←j+1

end while

Partition (ki,ni)

for eachni∈M do

endfor

endfor

其中：K表示为key的集合，M表示为节点数量.

图2　抽样运行时间对比图Fig.2　Sampling time of parallel execution and single execution

3　实验与结果

3.1实验环境

在校园内部局域网环境下搭建Hadoop集群，该实验集群由四台计算机组成，包括1个主节点和3个工作节点，Hadoop版本是Hadoop-0.20.0，操作系统版本Ubuntu8.0.4，Java环境为JDK1.5.针对改进型Mapreduce模型，采用运行时间和负载均衡情况来评估系统性能，对三种不同的分配策略进行WordCount实验，数据分配策略分别为：Native WordCount(NWC)、Combination Optimization WordCount(COWC)和LAB WordCount(LABWC).

3.2　抽样

3.3　作业时间

不同分配策略下系统作业执行时间随数据集倾斜程度的变

图3　不同倾斜程度下的运行时间Fig.3　Execution time for different degree of data skew

图4　不同大小数据集的运行时间Fig.4　Execution time for different size of dataset

图5　不同倾斜程度reduce端负载均衡情况Fig.5　Reduce output for different degree of data skew

图6　不同大小数据集负载均衡情况Fig.6　Load bananling for different size of dataset

化关系曲线如图3所示，数据集大小为1G，其中内嵌为LABWC作业变化曲线的放大图.可以看出，对于相同大小的数据集，运行时间随倾斜程度增加而增加，并且时间差有增大的趋势.这是由于倾斜程度增大，NWC方式下需要花更多的时间等待数据量较大的Reduce端完成作业，COWC 方式需要合并更多的数据集，LABWC方式需要对更多的倾斜数据进行均衡操作.同时，LABWC作业方式的整体运行时间小于NWC和COWC作业方式，不同倾斜程度运行的时间差变化较小，且时间差表现出减小的趋势.

针对倾斜程度为1.5的数据集进行WordCount实验，系统运行时间随数据集大小的变化关系如图4所示，可以看出，对于相同倾斜程度而大小不同的数据集，运行时间都随数据集增大而增加.LABWC作业方式与NWC 和COWC作业方式的运行时间差距随处理数据集的增大明显增大，从2G数据集实验可以看出LABWC运行时间约为NWC运行时间的一半，比COWC减少了约三分之一，说明改进的LAB算法可以有效的提高并行作业效率.

3.4负载均衡

采用式(3-6)定义的标准差来评估负载均衡情况，纵坐标Stdev表示标准偏差，横坐标为数据集倾斜程度，Stdev值越小表明处理数据负载均衡性越好.采用数据集大小为1G，倾斜程度在0.1～1.5之间的数据集进行WordCount实验，实验所得负载均衡结果如图5所示，从图中可以看出，stdev的变化趋势与执行时间的变化趋势基本吻合，同时反映出倾斜程度较小时，负载均衡情况差异较小.随着倾斜程度的增大，LABWC作业方式下Reduce端负载均衡的优势显现，说明基于抽样结果的LAB分配策略可有效改善Map端输出中间数据的均衡分配，使Reduce端处理数据大小均衡.

倾斜程度为1.5时不同大小数据集处理的负载均衡情况如图6所示，从图中可以看出不同大小数据集下LABWC作业方式的Stdev值均小于其它作业方式，随着数据集的增大，不同作业方式下的Stdev值均表现增大趋势，但NWC和COWC作业方式增加幅度明显大于LABWC作业方式，因此，LABWC作业方式具有明显的负载均衡优势.

4　结语

基于Hadoop平台研究了MapReduce模型下的任务分配机制，提出了改进的MapReduce模型，其中利用MapReduce作业方式实现数据集的并行抽样，同时采用LAB算法优化中间数据分配不均衡的问题，改进的LAB算法兼顾数据的本地性和Reduce端输入的均衡性，大大提高了并行作业效率.在Hadoop开源平台上通过实验集群进行性能验证，结果表明：改进的SMR模型减少了作业运行时间，且能够为Reduce端分配负载均衡的数据量，可解决Reduce端输入数据不均衡的性能瓶颈.

参考文献:

[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].软件学报，2011,22(1):71-83.

[3]张建勋,古志民,郑超.云计算研究进展综述[J].计算机应用研究,2010,27(2):429-433.

[4]陈全,邓倩妮.云计算及其关键技术[J].计算机应用,2009,29(9):2562-2565.

[5]陈康,郑纬民.云计算：系统实例与研究现状[J].软件学报,2009,20(5):1337-1348.

[6]李乔,郑啸.云计算研究现状综述[J].计算机科学，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].沈阳师范大学学报：自然科学版,2013,31(1):85-89.

[12]李玉林,董晶.基于Hadoop的MapReduce模型的研究与改进[J].计算机工程与设计,2012,33(8)：3111-3115.

[13]周锋,李旭伟.一种改进的MapReduce并行编程模型[J].科协论坛,2009,2(下):65-66.

[14]黄山,王波涛,王国仁,等.MapReduce优化技术综述[J].计算机科学与探索,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.

责任编辑：时凌

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

文献标志码：A