节点ubuntu14.04

异构环境下MapReduce动态任务调度技术研究作者范宇,郭会明机构北京航天长峰科技工业集团有限公司;中国航天科工二院;北京航天长峰股份有限公司发表期刊《计算机应用研究》预排期卷2018年第35卷第5期访问地址http://www.
arocmag.
com/article/02-2018-05-063.
html发布日期2017-05-2509:24:17引用格式范宇,郭会明.
异构环境下MapReduce动态任务调度技术研究[J/OL].
[2017-05-25].
http://www.
arocmag.
com/article/02-2018-05-063.
html.
摘要针对MapReduce在异构环境下各节点性能不均衡,导致整体计算效率低下的问题进行了研究.
为此,从节点与任务两方面入手,提出了一种将节点性能量化并排序与将任务按相似度划分相结合的算法.
该方法首先根据历史日志以及实时回传的日志信息将节点按照性能高低排序;然后根据任务执行完成的信息,将其与新任务进行比对得到相似度,从而推测出新任务的执行时间,执行时间长的认为是复杂的任务;最后进行动态调度,使高性能节点处理更复杂的任务.
在随机生成数据集上的实验结果表明,所提出的动态调度算法与默认调度算法相比,数据集为…关键词异构,MapReduce,任务调度,节点排序,任务划分中图分类号TP399基金项目优先出版计算机应用研究第35卷作者简介:范宇(1991-),男,黑龙江齐齐哈尔人,硕士研究生,主要研究方向为计算机应用、大数据与云计算(alex3936@163.
com);郭会明(1966-),男,湖北天门人,研究员,硕导,主要研究方向为计算机信息系统集成与应用.
异构环境下MapReduce动态任务调度技术研究范宇1,2,郭会明3(1.
北京航天长峰科技工业集团有限公司,北京100039;2.
中国航天科工二院,北京100039;3.
北京航天长峰股份有限公司,北京100039)摘要:针对MapReduce在异构环境下各节点性能不均衡,导致整体计算效率低下的问题进行了研究.
为此,从节点与任务两方面入手,提出了一种将节点性能量化并排序与将任务按相似度划分相结合的算法.
该方法首先根据历史日志以及实时回传的日志信息将节点按照性能高低排序;然后根据任务执行完成的信息,将其与新任务进行比对得到相似度,从而推测出新任务的执行时间,执行时间长的认为是复杂的任务;最后进行动态调度,使高性能节点处理更复杂的任务.
在随机生成数据集上的实验结果表明,所提出的动态调度算法与默认调度算法相比,数据集为20G大小时执行速度提高27.
4%,数据集为100G大小时执行速度提高了74.
1%.
关键词:异构;MapReduce;任务调度;节点排序;任务划分中图分类号:TP399ResearchonMapReducedynamictaskschedulingtechnologyinheterogeneousenvironmentFanYu1,2,GuoHuiming3(1.
ChangfengScienceTechnologyIndustryGroupCorp,Beijing100039,China;2.
The2ndInstituteofChinaAerospaceScience&IndustryCorp,Beijing100039,China;3.
BeijingAerospaceChangfengCo.
Ltd,Beijing100039,China)Abstract:Theperformanceofeachnodeinheterogeneousenvironmentisnotbalanced,socomputationalefficiencyofMapReduceisinefficiency.
Tosolvethisproblem,frombothaspectsofnodeandtask,proposinganewalgorithmwhichcombinesquantificatingnode'sperformanceanddividingtask.
Firstlysortedthenodesbytheirperformanceaccordingtoboththehistorylogsandtheinformationfedbackreal-time.
Thencomparedwithnewtaskaccordingtotaskexecutioninformation.
Finallydynamicallyscheduledthosetasks,makingsurehighperformancenodesdealingwithcomplextasks.
Theexperimentalresultsshowedthatcomparedwiththedefaultschedulingalgorithm,thedynamicschedulingalgorithmcanimprove27.
4%ofexecutionspeedfor20Gdatasetand74.
1%for100Gdataset.
KeyWords:heterogeneous;MapReduce;taskscheduling;sortingnodes;dividingtasks0引言近年来,随着互联网技术的迅猛发展,以及办公自动化的普及,尤其又随着Facebook、微博、微信等为代表的自媒体信息发布方式的不断涌现.
社会运行中很大一部分的活动都与数据的创造、采集、处理、分析等息息相关,大数据的应用范围不断扩大,影响力也日渐增长.
有专家指出近两年所产生的数据量相当于人类有史以来所产生的所有数据量的总和[1,2].
全世界最知名的咨询公司McKinsey曾在2011年发布了一份关于大数据未来发展的详细报告,并称大数据是下一代创新、竞争和生产力的前沿阵地[3].
在所有大数据技术中,以MapReduce为代表的并行计算框架由于其出色的表现一直受到人们的关注.
由于可以将作业划分为多个任务并行执行,MapReduce对基础硬件要求不高,可以将多台配置较低的计算机并联到一起组成计算集群,对其计算能力进行统一调配,达到对大数据处理较快的计算速度.
但是在现实使用中,由于部分机器老化等原因需要更换这部分机器,会使得原有集群中计算机的性能千差万别,从而产生异构性.
在异构环境下集群中不同计算节点的计算能力则大不一样,因此按照原有的平均分配任务方式将会造成部分性能较高的节点处于饥饿状态,而性能差的节点始终处于饱和状态[4].
又由于MapReduce具有显著的木桶效应,只有当最后一个任务完成整个任务才算完成,所以被分配了同样多任务的性能较差的节点会严重拖慢执行时间,从而影响整体性能.
优先出版计算机应用研究第35卷1相关工作针对MapReduce在异构环境下的任务调度问题,最早的研究当属Zaharia等人在加州大学伯克利分校AMP实验室中提出的Straggler问题[5].
即MapReduce中最慢的任务被称之为Straggler,它的执行时间直接影响着整个任务的时间.
应对该问题Zaharia等人提出了LATE算法,其思想是通过系统观察找出是否存在某一任务的执行进度慢于某一设定的阈值,如果存在则选择某一节点执行该任务的备份任务,以确保该任务不会由于节点问题而拖慢整个任务.
但该方法存在着明显的不足之处.
其一是对于Straggler任务的判断.
其二是该方法需要预留一部分节点做备份,这样不能够达到最大化利用现有计算资源,与大数据的思想相悖.
其三是对于备份节点的选择,如果执行备份的节点相较原节点性能没有明显的提高,那么执行备份的过程就纯粹是浪费资源,而如果备份节点全是高性能节点,又明显会拖慢原有任务执行速度.
除Zaharia之外,还有很多学者在这方面做了很多的工作,比如Snavely等人[6]提出了在HPC中使用性能模型预测任务执行时间的方法.
比如YongM[7]提出让每个任务节点收集自身资源消耗的信息并汇总统计后分配之后的任务.
XieJ[8]设计了一种新型数据分布策略使MapReduce获得了更高的数据局部性.
Sun[9]提出一种更全面更精确的估计任务剩余时间的方法.
Rasooli[10]提出了将FIFO、公平选择、分类及优化等多种策略相结合的方法.
上述方法都在原有调度策略基础上对性能进行了优化和提升.
本文在对上述几种算法的分析研究的基础之上,从节点与任务两方面入手,提出一种基于性能监测的节点动态排序算法与基于相似度的任务划分算法相结合的办法,用于提高MapReduce的执行效率.
核心思想是首先依照性能检测的排序算法将节点按照性能高低排序并不断更新排序顺序,同时依照任务相似度划分算法将相似度高的任务归并;在执行过程中遵循两个原则,其一是将复杂任务交给高性能节点处理,其二是将归并相似的任务交给相同节点处理.
并在最后实验本方法与默认的任务调度算法相比较,得出本方法在作业完成时间、作业对于系统性能的利用率,包括CPU和内存的利用率上均有显著提升.
2算法设计2.
1基于性能检测的节点动态排序算法本算法的核心指导思想是:首先在任务执行过程前,依据最近一段时间各节点执行任务的日志,通过本算法将节点按照性能高低排序;然后在任务执行过程中通过实时回传的执行日志不断将该排序结果进行更新,做到动态排序.
在异构环境下,某一节点的性能决定因素有很多.
比如主机的CUP性能、IO速率、内存大小等等,针对不同的硬件设备,其决定因素的权重也不尽相同.
假设系统中共有v个节点,可以用X1,X2…Xv表示这些节点,p为影响节点性能因素的个数,则可以使用表示第v个节点的第p个影响因子.
则具体算法过程如下:首先获取最近一段时间内节点i在执行计算任务时的历史记录日志.
若第一条用Xi1表示,则n条记录可以用如下所示的矩阵列表示[11]:将得到记录数据整理完毕后,计算节点i中n条记录的影响因子的均值U:(1)接下来分别计算节点i中n条记录的影响因子的方差σ2:(2)最后可以利用上述计算得到的结果,推测计算出当前节点i的性能分数:(3)对于全部节点进行如上计算,将节点按照上述计算结果得到的性能得分从高到低进行排列,得到一组节点数组L=[Xa,Xb…Xn].
由于是使用的历史记录,所以上述计算工作可以在节点非工作状态下进行,即他们并不占用任务执行时间.
接下来在任务计算过程中,根据任务大小不同,采用不同时间间隔对节点日志进行采集,并重新计算节点性能,采用实时数据对所得的节点数组L进行更新.
这样可以得到一个最接近的能够表明节点性能高低的数组,然后跟据本文后续算法内容,将复杂、推测会长时间执行的任务交给高性能节点,并将任务依次分配;将数据结构单一、数据量小等被推测出耗时较短的任务交给性能较低的节点执行.
2.
2基于相似度的任务划分算法本算法的核心指导思想是:根据相似度影响因子等一系列计算手段,将待执行的任务按照相似的程度划分成若干份.
尽量使用相同的节点处理相似任务,然后根据先执行的任务的执优先出版计算机应用研究第35卷行时间可以推测出相似任务所需要的大致执行时间,据此决定是否需要调整执行这一类相似任务的执行节点.
本算法的实现依据是相似的任务在同一环境下执行时间同样具有相似性.
为此进行了如下实验:采用最为基础的WordCount算法,在同一台机器上,采用伪分布式的方式,分别执行数据量大小相等(均为3GB左右),但分别由阿拉伯数字、英文小写字母和简体中文组成的若干组任务,比较各组任务执行时间长短.
其中a-c组的内容都是由阿拉伯数字组成,d-f组的内容由英文小写字母组成,g-i组的内容由简体中文组成.
所有数据均没有明显规律且随机生成.
9组数据完全执行所需时间如表1所示(单位为秒):表19组不同数据执行WordCount算法时间阿拉伯数字英文小写字母简体中文abcdefghi38.
640.
736.
442.
139.
845.
352.
057.
754.
6显然相同种类文字组成的任务执行时间更为接近.
由此可以推测出,结构相似的任务在同一环境下执行时间同样相似的结论是正确的.
接下来要考虑到的关键问题是如何量化不同任务的影响因子.
同样的是,对于异构环境下的任务,应该根据硬件环境的不同,从而采取不同的影响因子权重策略.
比如对于一个内存丰富,但CPU运算速度较慢的节点,CPU影响整个速率的权重显然应当比内存更大.
而对于拥有强悍CPU但内存不足的节点,内存的重要性便尤为显著.
在此本文采用已经成熟运用于权重设置方面的二次规划算法[12].
二次规划是非线性规划的一种特殊类型,它的一般形式为[13](4)其中Q是Hessian矩阵,T是有限指标集,D是Rn中的一个多面体,cRn.
采用的具体量化两个不同任务X,Y的相似度的公式如下:(5)其中,xi和yi为它们的影响因子,wi为影响因子的权重,n为影响因子的个数.
在这里假设当前的一个工作节点中,一共有n条任务执行的日志文件,其中每一个任务都有p个影响因子[14].
则所得到的计算方法如下:(6)(7)其中Rxy是任务执行后通过公式计算出的真实相似度,t表示真实的执行时间,tavg表示预测执行时间的平均值.
Sxyk代表的是任务x和y在第k个属性上的相似度.
是两个任务通过公式(5)计算得到的相似度结果.
Lxy表示真实相似度和计算相似度之间的差别.
通过以上计算,可以得到通过二次规划得到的异构环境下,任意两个任务X和Y的相似度计算结果如下:(8)由此便可以通过设置不同的阈值,将全部任务划分为若干不同的小组任务.
这样可以认为相同小组中的任务为相似任务,它们在同一环境同一节点上的执行时间也是相似的.
因此每一小组中在某一节点上执行一个任务的时间可以作为该小组中后续任务执行时间的参考.
2.
3基于性能排序和任务划分的动态任务调度算法经过以上两种算法,可以分别得到一组表示各节点性能由高到低降序排列的数组L=[Xa,Xb…Xn],以及根据相似度划分所得到的若干相似任务小组.
动态调度算法基于如下思想:根据每一个执行完毕的任务在某节点上执行所需时间,可以推测认为该组任务在该节点上执行时间基本相同,再根据具体执行时间长短,判断是否需要将该组任务动态调度到其他节点执行.
以及应该调度到哪个节点去执行.
算法1动态任务调度算法.
算法输入:L=[Xa,Xb…Xn]:节点性能排序数组TaskGroupT1,T2…:相似任务小组其中Tn=[tna,tnb…],tnm为第n组第m个任务1.
foreachtnpproceedinginXi2.
computetimen=proceedingtime3.
MeanTime=(time1+time2+…+timen+…+timemax)/max4.
foreachtimendo:5.
Iftimen>MeanTime6.
tnqproceedinginXj(q>p,jp,j>i)9.
end3实验结果及分析本章采用实验验证的方式,在一个由21台规格不尽相同的台式机组成的异构环境集群中,通过WordCount程序多次执行任务量不同的数据集,验证本方法与默认的调度策略执行效果优先出版计算机应用研究第35卷优劣.
实验采用Ganglia[15]来检测集群状态,对实验结果进行分析比对.
具体节点的配置信息如表2所示.
表2硬件配置信息节点数量硬件信息Master1四核,2.
8GHz,8G内存,1T机械硬盘Slave2四核,2.
8GHz,4G内存,512G机械硬盘Slave4双核,2.
8GHz,4G内存,512G机械硬盘Slave2双核,2.
8GHz,4G内存,256G固态硬盘Slave4双核,2.
2GHz,4G内存,512G机械硬盘Slave8单核,2.
2GHz,2G内存,512G机械硬盘所有机器的操作系统均采用Ubuntu14.
04版本,Hadoop版本均为2.
6.
0,JDK版本均为1.
7.
实验数据为随机生成的由小写英文字母组成的10个不同大小的数据集,并将其分为两组,第一组的数据量较小,分别是1G,2G,3G,4G,5G;第二组的数据量则较大,分别是20G,40G,60G,80G,100G.
分别使用默认调度策略与上述动态任务调度策略进行不同实验,得到的结果如下所示:图1数据集较小一组作业运行时间图2数据集较大一组作业运行时间通过实验结果可明显看出,动态调度算法相比默认调度算法有很大优势.
由于动态调度算法需要在节点计算过程中进行额外的排序和划分,所以在数据量较小时算法优化所带来的时间精简与这部分计算时间相抵消,导致优化幅度有限.
但当数据量增大到10G为单位的程度时,动态调度策略所带来的时间收益极为明显.
因此,本调度算法实现了在异构环境下减少任务执行时间的目的,尤其对于10G级别以上大数据处理,更具有现实意义.
同时在执行20G数据集的过程中,采集了150s-200s之间两种调度策略的CPU利用率和内存利用率.
采集结果如图3、4所示.
图3执行20G数据集任务过程中CPU利用率图4执行20G数据集任务过程中内存利用率从图中可以看出,在使用默认调度策略执行时,CPU利用率和内存利用率均居高不下,长时间维持在95%甚至更高.
长时间过高的负载势必会导致性能的损耗,既会降低接下来任务的执行能力,而且还会加快硬件的损耗.
而使用动态调度策略则可以使CPU利用率和内存利用率更多得维持在90%以下,这表明该方法可以更加合理地使用系统资源.
由此可以看出,动态调度策略在资源利用率方面也体现了它的优势.
4结束语在本文中,为了应对异构环境下由于木桶效应导致的任务执行时间过长,提出了一种将执行节点排序与任务划分相结合的动态算法.
使得最高性能节点执行最复杂任务,次高性能节优先出版计算机应用研究第35卷点执行次复杂任务并以此类推.
在评价节点性能高低与任务相似程度的过程中都充分考虑到了不同条件下影响因子的权重不同所导致的影响.
最后经过实验验证,发现本算法确实在减少任务执行时间、合理化资源利用率方面有着明显的提升效果.
下一步的工作可以将本算法在处理大量数据方面的优势更加深化,并针对云平台的特点进行优化与改进,将其部署到云平台上,从而最大化地发挥本算法的特点与优势.
参考文献:[1]程学旗,靳小龙,杨婧,等.
大数据技术进展与发展趋势[J].
科技导报,2016,(14):49-59.
[2]李国杰.
大数据研究的科学价值[J].
中国计算机界学会通信,2012,8(9):8-15.
[3]ManyikaJ,ChuiM,etal.
Bigdata:Thenextfrontierforinnovation,competition,andproductivity[R/OL].
(2012-10-02)[2016-12-25].
http://www.
mckinsey.
com/Insights/MGI/Research/Techonlogy_and_Innovation/Big_data_The_next_frontier_for_innovation.
[4]刘朵,曾锋,陈志刚,等.
Hadoop平台中一种Reduce负载均衡贪心算法[J].
计算机应用研究,2016,(9):2656-2659.
[5]ZahariaM,KonwinskiA,JosephA,etal.
Improvingmapreduceperformanceinheterogeneousenvironments[C]//ProcofUSENIXSymposiumonOperatingSystemsDesign&Implementation.
2008:29-42.
[6]SnavelyA,WolterN,CarringtonL.
Modelingapplicationperformancebyconvolvingmachinesignatureswithapplicationprofiles[C]//ProcofIEEEInternationalWorkshoponWorkloadCharacterization.
2001:149-156.
[7]YongM,GaregratN,MohanS.
TowardsaresourceawareschedulerinHadoop[C]//Procofthe7thIEEEInternationalConferenceonWebServices.
LosAngeles:IEEEComputerSociety,2009:102-109.
[8]XieJ,YinS,RuanX,etal.
ImprovingMapReduceperformancethroughdataplacementinheterogeneoushadoopclusters[C]//ProcofParallel&DistributedProcessingWorkshopsandPhdForum.
2010:1-9.
[9]SunX,HeC,LuY.
ESAMR:anenhancedself-adaptiveMapReduceschedulingalgorithm[C]//Procofthe18thInternationalConferenceonParallelandDistributedSystems.
Piscataway:IEEEPress,2012:148-155.
[10]RasooliA,DownD.
AhybridschedulingapproachforscalableheterogeneousHadoopsystems[C]//HighPerformanceComputing,NetworkingStorageandAnalysis.
WashingtonDC:IEEEComputerSociety,2012:1284-1291.
[11]侯佳林,王佳君,聂洪玉.
基于异常检测模型的异构环境下MapReduce性能优化[J].
计算机应用.
2015,35(9):2476-2481.
[12]FrankM,WolfeP.
Analgorithmforquadraticprogramming[J].
Navalresearchlogisticsquarterly,2006,3(1-2):95-110.
[13]唐冲.
基于Matlab的非线性规划问题的求解[J].
计算机与数字工程.
2013,(7):1100-1102.
[14]郑思.
大规模数据处理系统中MapReduce任务划分与调度关键技术研究[D].
长沙:国防科学技术大学,2014.
[15]MassieM,LiB,NickolesB,etal.
MonitoringwithGanglia[M].
Sebastopol:O'ReillyMedia,2012:20-63.