算法梭子鱼负载均衡

优先出版计算机应用研究第33卷基金项目:国家自然科学基金资助项目(61103202);国家教育部博士点基金资助项目(20110162120046);中南大学教师研究基金资助项目(2014JSJJ019)作者简介:刘朵(1991-),男,湖南隆回人,硕士研究生,主要研究方向为大数据;曾锋(1977-),男(通信作者),副教授,硕导,博士,主要研究方向为无线网络、数据挖掘、云计算、软件工程;陈志刚(1964-),男,教授,博导,主要研究方向为是计算机网络与分布式系统;姚亦韬(1992-).
男,硕士研究生;主要研究方向为大数据.
Hadoop平台中一种Reduce负载均衡贪心算法*刘朵,曾锋*,陈志刚,姚亦韬(中南大学软件学院,长沙410075)摘要:MapReduce是目前广泛应用的并行计算框架,是Hadoop平台的重要组成部分.
主要包括Map函数和Reduce函数.
Map函数输出key-value键值对作为Reduce的输入,由于输入的动态性,不同主机上的Reduce处理的输入量存在不均衡性.
如何解决Reduce的负载均衡是优化MapReduce的一个重要研究方向.
本文首先对整体数据进行抽样,通过适量的样本分析数据,达到较小的代价获得可靠的key分布;然后,提出贪心算法代替Hadoop平台默认的hash算法来划分数据,实现Reduce负载均衡.
本文所提贪心算法主要思想是根据抽样数据,求取所有key频次的和对于Reduce节点数量的平均值,然后依次为每一个Reduce分配一个接近平均值的负载,从而达到整体的负载均衡.
模拟实验表明,本文所提算法与默认的hash分区算法相比,运行时间节约10.
6%,达到更好的负载均衡.
关键词:MapReduce;贪心算法;reduce负载均衡;抽样中图分类号:TP311GreedyalgorithmforReduceloadbalancingonHadoopplatformLiuDuo,ZengFeng*,ChenZhigang,YaoYitao(SchoolofSoftware,CentralSouthUniversity,Changsha410075)AbStract:MapReduceisusedwildlyasaparallelcomputingframework.
mainlyincludingtheMapfunctionandReducefunction.
Mapfunctionhastheoutputofthekey-valuepairs.
whicharetheinputoftheReducefunction.
Asaresult.
theinputofReduceisdynamic.
TheloadbalancingofReducehostshasanimportantimpactontheefficiencyofMapReduce.
Inthispaper.
firstly.
theoveralldataaresampled.
Theaimistoobtainreliablekeydistributionatacheapprice.
Then.
agreedyalgorithmisproposedtodividedatatoachieveReduceloadbalancing.
takingtheplaceofhashalgorithm.
ThemainideaofthegreedyalgorithmproposedinthispaperistoassigntherightjobtoaReducehostforthebestloadbalancingineachstep.
Simulationresultsshowthatproposedalgorithmhasbetterperformancethantheothertwoalgorithms.
Comparedwiththedefaulthashpartitioningalgorithm.
theproposedalgorithmhastherunningCPUtimedecreasedby10.
6%.
andachievesbetterloadbalancing.
KeyWords:MapReduce;Greedyalgorithm;loadbalancingofReduce;sampling0引言大数据的处理目前被广泛的应用和研究,MapReduce框架是目前应用最为广泛的并行计算框架[1].
Hadoop是目前应用最为广泛的一个MapReduce实现[2].
MapReduce包括Map函数和Reduce函数.
Map函数处理输入的key/value键值对,输出中间值的key/value键值对,作为Reduce的输出.
Map处理的数据是静态的,每一个Map处理的数据大小是相同的.
而每一个Reduce处理的数据是动态的,数据量可能不相同,因此,Reduce负载存在不均衡性.
在每个节点的数据处理能力一致的条件下,任务的执行时间由处理数据量最大的Reduce节点确定.
因此Reduce的负载均衡影响MapReduce的运行效率.
目前Hadoop平台中MapReduce默认使用hash算法对数据进行划分.
该算法并没有考虑到数据中key值的分布,以及每个key产生的hash值冲突情况.
例如,具有相同hash值的key会被分配到同一Reduce节点,从而导致Reduce负载的不均衡.
可见,hash算法存在一定的局限性,没有考虑Reduce的负载均衡.
本文首先通过抽样获取key的频次分布,然后针对抽样数据提出贪心算法实现Reduce节点的负载均衡.
1相关工作由于MapReduce默认的hash算法没有考虑MapReduce中间数据的,从而影响整个MapReduce的运行效率.
为解决这个问题,国内外学者对MapReduce的数据划分的均衡性进行了研究.
文献[3]提出了基于虚拟分区的负载均衡算法.
该算法把整优先出版计算机应用研究第33卷个数据虚拟划分为n个区,在map后,统计每一个区的key的数量,然后考虑Reduce负载均衡为这些区分配一个Reduce节点.
文献[4]假设节点存在不一样的执行能力,根据节点的执行能力分配Reduce负载,实现Reduce的负载均衡.
文献[5]通过抽样后,寻找分位数的方法来确定数据划分.
文献[6]通过数据抽样后,将key划分为大负载key,中负载key和小负载key,针对不同的key分别做不同的处理,大负载key划分成多个子key,然后分配到不同的Reduce节点上,将中负载key打包后直接分配到Reduce节点,小负载key直接使用hash划分.
文献[7]提出了LAB算法来划分数据,用一种启发式的方法把特定的key对应的数据集分配到最适合的Reduce节点上,然后为下一个key寻找分配的Reduce节点,以此类推,把每个key分适合的节点上.
文献[8]提出了Cluster组合、Cluster分割两种算法来对数据进行划分.
Cluster组合应用倾斜度小的中小负载key,将key按频次排序然后依次划分到Reduce上,Cluster分割应用于倾斜度大的大负载key,将大负载key切分成多个子key,然后依次划分.
文献[3,4,7]提出的算法都需要在MapReduce程序运行过程中进行调整,针对不同的MapReduce程序往往需要有不同的调度处理,操作复杂性高.
文献[5]分位点的key通常需要划分到多个Reduce上,处理起来比较复杂,并且误差较大.
文献[6]对于大中小负载的确认与计算比较复杂.
文献[8]没有考虑由于抽样误差导致未抽取的key没有分配的情况.
基于上述研究工作,本文尝试完善样本抽样和Reduce负载均衡机制.
首先通过抽样获取key的分布,分析抽样的样本规模和准确度之间的关系,其次理论分析hash算法的不足,提出贪心算法实现Reduce负载均衡,并通过大规模的数据实验验证算法的有效性.
2算法分析与设计2.
1问题分析Hadoop平台中MapReduce默认的划分数据方法是hash算法,根据处理对象的key分配Reduce主机,如式(1)所示.
其中num是Reduce编号,nReduceTsk是Reduce的数量.
key.
hashCode为哈希码,使用的是BKDR算法.
字符串str的hash码计算如式(2)所示.
从公式(1)和公式(2)可以看出使用默认的hash算法将key划分到Reduce节点上,完全取决于key的hash值,没有考虑该key的其他信息,这样会存在以下两种情况而使数据产生倾斜.
a)使用hash算法时,多个key的hash码对Reduce节点数量取模之后可能具有相同的值,从而使数据划分集中于某一个Reduce节点,造成数据不均衡.
b)hash算法没有考虑key的频次,可能存在一些频次大的key被划分到同一个Reduce节点,从而造成数据不均衡.
如图1所示,有3个数据节点,Map端输入数据有6个key值,每个key值的数据量不相等,但每个数据节点的数据总量是相等的.
图中Node1的key值K1的数据量为15,表示为K1:15.
计算可得Node1的数据总量为75.
假设K1-K6的hash码分别与1-6对应,则由公式(1)hash算法分区之后,Reduce端输入的数据量将不相等,出现了较大的数据倾斜,三个Reduce节点的数据量分别为75,111和39.
图1中间数据不平衡示例基于上述分析,Reduce数据划分需要考虑key的聚集和频次问题.
本文拟对数据进行抽样,获取每个key的频次,求取频次对于Reduce节点数量的平均值,然后依次为每一个Reduce分配一个接近平均值的负载,从而达到整体的负载均衡.
本文优先出版计算机应用研究第33卷改进后的Hadoop作业运行流程图如图2所示:图2改进后的Hadoop作业运行流程图图中的阴影部分是新增加的内容,partioner方法是采用自定义的方法代替系统默认的方法.
2.
2抽样抽样[9]是从目标数据中抽取一部分样品单位,基本要求是保证所抽取的样品单位对全部样品具有充分的代表性.
本文算法是针对海量的数据进行分析,如果对所有的数据进行统计,花费代价非常大,因此采用抽样技术,获取key的频次.
本文采用系统抽样来对总体进行抽样.
系统抽样根据样本容量,首先确定抽选间隔,然后随机确定起点,每隔一定的间隔抽取一个单位的一种抽样方式,是纯随机抽样的变种.
在系统抽样中,将总体从1~N连续编号,抽样距离K=N/n.
式中N为总体单位总数,n为样本容量.
然后,在1~K中抽一随机数k1,作为样本的第一个单位,接着取k1+K,k1+2K,……,直至抽够n个样本为止.
系统抽样单位在总体中是均匀分布的,且抽取样本可少于纯随机抽样特点,能够很好的反映总体情况.
从统计学原理[10],我们可以发现随着样本的增大,抽样的准确度越高.
设事件A发生的概率为p,在n次重复实验中事件A发生次数为m,当n充分大时(称之为大样本),近似有取置信区间为100%,则有可知误差为可见,随着n的增大,m的误差减少,抽样的准确度越高.
2.
3贪心算法分析贪心算法[11]每一步使所做的选择都是当前最佳的,期望通过局部最优选择来产生出一个全局最优解.
本文所提贪心算法主要思想是根据抽样数据,求取所有key频次对于Reduce节点数量的平均值,然后依次为每一个Reduce分配一个接近平均值的负载,从而达到整体的负载均衡.
具体算法如下:Step1:将key按频次,从小到大排序.
Step2:计算所有key的频次和对于Reduce数量的均值avg.
Step3:将频次大于均值avg的key拆分.
分配到1个负载为0的reduce节点上,记录key和Reduce分配的对应关系,将key的频次减去avg.
重复处理,直到key的频次小于avg.
若key的频次不为0,则将key重新按序插入队列.
Step4:重复Step3,将所有的频次大于均值avg的key处理完毕.
Step5:选择Step3没有涉及的Reduce节点.
从后至前遍历队列,求取key的频次与该节点当前负载的和,如果该和不超过avg,则将该和作为Reduce节点的当前负载,记录key和分配的Reduce的对应信息,删除队列该key的信息.
重复上述操作,直到遍历完整个队列.
Step6:重复步骤5,均衡余下Reduce节点的负载,记录优先出版计算机应用研究第33卷key和分配的Reduce的对应信息.
Step7:对输入的每一个key,通过步骤3、4、5、6产生的记录,返回该key分配的Reduce的编号.
图2的例子通过贪心分区算法进行数据划分之后的结果如图3所示.
可以看出本文所提贪心分区算法获得较好的Reduce负载均衡,优于默认分区算法.
图3中间数据平衡后示例2.
4基于贪心算法的数据划分算法实现通过抽样统计获得所有key频次,对于在抽样过程中,没有抽取出的key,认为是小概率数据.
不影响Reduce的负载均衡.
没有抽取到的key,使用hash分区算法,划分到对应的Reduce上.
定义全局变量KeyReduce,KeyReduce存储的是Key和应该划分的Reduce编号的对应关系.
当key.
Freq>avg时记key为大负载key.
本文设计的一种贪心数据分区算法的的伪代码如下:1keyReduceGreadyPart()2{3读取PartionFile文件中的key的频次,记录到键值对序列KFreq中;4SortByFreq(KFreq);.
//将KFreq按照频次从小到大排序5avgValue=sum/m;//求每个reduce平均处理的key频次综合6reduce=0;7//将大于key平均频次的所有key的拆分8for(inti=0;iavg)11{12while(KFreq.
Value>avg)13{14KeyReduce.
Add(key,reduce);15KFreq[i].
Value-=avgValue16}17KFreq.
Sort();//将改变后的元素,调整到合适的位置18}19else20{21break;22}23}24for(inti=0;i=0;j--)28{29intvalue=KFreq[j].
value;30if(avgValue>=reduceSum+value)31{32reduceSum+=value;33KeyReduce.
add(KFreq[j].
key,i);优先出版计算机应用研究第33卷34KFreq.
remove(j);35}36}37}38returnKeyReduce;39}40publicintgetPartition(Textkey,Textvalue,intnumPartions)41{42if(KyeReduce==null)43{44GreadyPart();45}46if(KeyReduce[key]!
=null)47{48returnKeyReduce[key].
Reduce;49}50return(key.
hashCode()&Integer.
MAX_VALUE)%numReduceTasks;51}算法描述:按照key的频次从小到大排序,求出所有key的频次之和,计算划分到m个Reduce上的平均值avg.
如果某key的频次大于avg,则需要将其划分到多个Reduce上,该key称作大负载key.
代码8-23行是将大负载key划分到不同的Reduce上,并将key-reduce的对应关系加入KeyReduce中.
承载了大负载key的Reduce不再划分数据.
代码24-37行是为没有承载大负载key的Reduce节点均衡负载.
依次为每一个Reduce节点分配key.
对于第i个Reduce节点,选择当前队列中频次最大的key,如果满足分配该key后,第i个Reduce节点的负载不大于avg,则将key分配到第i个Reduce节点上.
直至遍历完整个队列.
代码40-51行是getPartition(),通过该方法返回对应key划分的Reduce的编号.
代码46-49行,如果key在KeyReduce中有对应的Reduce的编号,直接返回该编号,否则认为key在抽样过程中没有抽到,是小数据,不影响负载均衡,使用默认的分区算法划分到对应的Reduce节点上.
如果key为大负载,在KeyReduce中能够找到多个值,可将该key按照比例分配到各个Reduce节点上.
3实验结果及分析3.
1硬件平台及部署本文的实验集群由7台计算机组成,每台计算机有2G内存,300G磁盘空间.
包括1个主节点:master.
csu和6个工作节点:slave1.
cus-slave6.
csu,节点的部署信息如表1所示.
网络环境:校园内部局域网,操作系统:Centos6.
6,Java环境:JDK1.
6,Hadoop版本:Hadoop-1.
2.
1,开发工具:MyEclipse8.
6.
3.
2实验结果及分析以WordCount为实例,进行实验.
分别比较默认的hash分区算法,分位数分区算法和贪心分区算法.
从运行时间和Reduce的负载均衡两个角度比较三种算法的优劣.
数据从网上随机下载,分别比较数据集在432M,4.
32G,8.
64G,20G情况下的运行时间以及在数据集在4.
32G时各个节点的负载均衡.
在数据量比较小的情况下,如在数据量为400M左右时,两种算法的执行时间相当.
但随着数据量的增大,使用贪心分区算法的效率会越来越高,在数据达到20G的时候,与默认的hash分区算法相比,贪心分区算法降低执行时间约10.
6%,实验数据如图4所示.
在实验数据量为4.
32G时,每个Reduce节点的负载情况如图5所示,贪心分区算法的每个Reduce负载基本相同,而使用默认的hash分区算法的每个Reduce的负载有较大的数据起伏.
分位数数分区算法的均衡度好于hash分区算法,但比贪心算法差.
与hash分区算法和分位数数分区算法相比,贪心算法的负载均衡度提高分别为44.
4%和9.
2%.
由此可见,在均衡衡负载和时间效率这两个方面,贪心分区算法要优于hash分区算法.
表1节点部署情况服务器IP服务器主机名功能192.
168.
1.
120master.
csu主节点(namenode和jobTracker)192.
168.
1.
121slave1.
csu从节点1(DataNode和TaskTracker)192.
168.
1.
122slave2.
csu从节点2(DataNode和TaskTracker)192.
168.
1.
123slave3.
csu从节点3(DataNode和TaskTracker)192.
168.
1.
124slave4.
csu从节点4(DataNode和TaskTracker)192.
168.
1.
125slave5.
csu从节点5(DataNode和TaskTracker)192.
168.
1.
126slave6.
csu从节点6(DataNode和TaskTracker)优先出版计算机应用研究第33卷图4大小不同的数据集的执行时间比较图5同一数据集(4.
32G)不同节点上的负载比较4结束语本文主要是对MapReduce的中间数据平衡进行研究.
Reduce函数使用Map函数产生的中间结果作为输入数据,是动态的数据.
MapReduce默认使用hash算法来进行数据划分,每个Reduce节点的负载不平衡.
本文通过抽样获取key的频次,使用贪心算法代替hash算法,均衡Reduce的负载.
无论是理论分析还是实验验证,均表明贪心分区算法是一个良好的数据分区算法.
参考文献:[1]DeanJ,GhemawatS.
MapReduce:simplifieddataprocessingonlargeclusters[J].
CommunicationsoftheACM,2008,51(1):107-113.
[2]WhiteT.
Hadoop:thedefinitiveguide:thedefinitiveguide[M].
[S.
l.
]:O'ReillyMedia,Inc.
",2009.
[3]FanY,WuW,CaoH,etal.
LBVP:AloadbalancealgorithmbasedonVirtualPartitioninHadoopcluster[C]//ProcofIEEEAsiaPacificConferenceonCloudComputingCongress.
2012:37-41.
[4]GaoZ,LiuD,YangY,etal.
AloadbalancealgorithmbasedonnodesperformanceinHadoopcluster[C]//Procofthe16thAsia-PacificNetworkOperationsandManagementSymposium.
2014:1-4.
[5]韩蕾,孙徐湛,吴志川,等.
MapReduce上基于抽样的数据划分最优化研究[J].
计算机研究与发展,2013,S2:77-84.
[6]RamakrishnanSR,SwartGt,UrmanovA.
BalancingreducerskewinMapReduceworkloadsusingprogressivesampling[C]//Procofthe3rdACMSymponCloudComputing.
NewYork:ACM,2012[7]余基映.
MapReduce模型的数据分配策略研究[D].
武汉:华中科技大学,2013.
[8]耿玉娇.
MapReduce中基于抽样技术的倾斜问题研究[D].
大连:大连海事大学,2013.
[9]宛婉,周国祥.
Hadoop平台的海量数据并行随机抽样[J].
计算机工程与应用,2014,40(20):115-118.
[10]于寅,等.
高等工程数学[M].
武汉:华中科技大学出版社,2012:340-355[11]CormenTH,LeiserSonCE,etal.
算法导论[M].
北京:机械工业出版社,2006:222-239