本站原创基于数据局部性的推测式Hadoop任务调度算法研究
刘奎1,,,
(1.东北大学秦皇岛分校计算机与通信学院,河北省省,2.市)
摘 要:
关 键 词:Hadoop
中图分类号:TP31文献标志码:A文章编号:
AspeculativetaskschedulingalgorithmbasedonlocalityofdatainHadoop
LIUKui1,LIUXiang-dong1,MABao-lai2,WANGCui-rong1
(1.CollegeofComputerandCommunication,NortheasternUniversityatQinHuangdao,QinHuangdaoHebei066004,China,2.CollegeUniversity,Shenyang110000,China)
Abstract:ForthereasonthattheexistingalgorithmonHadoopdoesn'theahighlevelofoptimization,thispaperpresentsanoveltaskschedulingalgorithmbasedondatalocalityspeculation.BycalculatingthetimedurationratioofMapandReducetaskoneachnodebinedwiththelocalcharacteristicsoftasksanddataondifferentnodes,thealgorithmintroducesamoreaccuratetaskdetectionmechani,andthenlaunchesbackuptasksofslowtasksonfastnodes.Forusingputingmigrationinsteadofdatamigration,thealgorithmcanobtainhigherefficiency.ExperimentalresultsinHadoopshowthatparedwiththeexistingschedulingalgorithm,thealgorithmproposedinthispapercanshortenthetaskerageoperationtimeandreducetheworkcongestioncausedbydataexchangebetweenclusterracks.Italsocanspeedupthetaskexecutionefficiency.
Keywords:Hadoop,jobscheduling,heterogeneousenvironments,localityofdata
0引言
Amazon,Yahoo！等IT公司都推出了自己的云计算怎么写作平台,并把云计算作为未来的重要战略之一[2].云[3].这个项目得到了雅虎公司的大力支持,进而使得Hadoop成为一个更适合并行处理大规模数据的开源分布式计算平台,并且已经在很多大型网站上得到了广泛的应用.Hadoop平台最大的优点就是在并行化技术方面对应用开发者实现了透明处理,开发人员在开发云计算的应用程序时,可以像开发普通程序一样编写代码,而不需要理解那些由Hadoop底层自动实现完成的复杂的并行化技术[4].但是,Hadoop毕竟还是一个比较年轻的平台,在很多技术细节问题还有待进一步改进,特别是在实际使用过程中暴露出的MapReduce调度器的低效性和对异构系统适应能力差的问题,任务调度技术是Hadoop平台的核心技术之一,其主要功能是对任务执行的顺序以及系统的计算资源进行合理的控制与分配.调度技术的优劣直接影响到Hadoop平台的整体执行性能和系统资源利用效率的高低,这一技术在现阶段仍然处于不完善的状态,现有的任务调度算法都存在着一些不足,限制了云计算技术在应用领域的作为.目前常见的调度算法有Hadoop的默认调度算法FIFO,这种算法不考虑作业的优先级或者大小,选取最老的作业先调度.公平调度[5]是Facebook公司贡献的,它会随着时间的推移公平分配资源.Yahoo公司开发了容量调度器[6],保证作业最小资源的同时共享多余的资源.伯克利大学提出的late[7]算法是推测式算法的一种,它会根据作业中任务的进度重新分配资源,运行效率明显优于其它调度算法,但是在数据局部性方面存在缺陷.本文对Hadoop原有的任务调度算法和late调度算法不足基础上,提出一种基于数据局部性的推测式任务调度算法,并与其它算法进行了比较研究.
1相关工作
,任务阶段性地完成,所以进度值比较小的任务被判定为慢任务.上述理想情况下的检测设在异构的集群环境中都是不成立的.这使得原有的Hadoop调度算法在探测落后任务并为落后任务启动推测式备份任务的算法中显得不够精确.
Hadoop目前原有的调度算法都是检测定了大部分的Map任务都是在本地数据节点中执行,没有考虑Reduce任务是否在本地读取数据执行任务的问题.根据FaceBook使用Hadoop平台的情况统计分析,拥有1至25个Map任务的小工作只有5%的任务能够在存储数据的本地节点上执行(数据局部性),如图1所示.有59%的任务在存储数据的本地机架上执行,如图2所示.因此,需要对传统的Hadoop调度算法在数据局部性上进行优化,来进一步提高算法的性能,提高整个集群资源的利用率.
图1Map任务数与本地节点Map任务数的关系
图2Map任务数与本机架上Map任务数的关系
本文对Hadoop原有的推测式任务调度做出了进一步的改进,结合Yahoo公司提出的保证作业最小资源的同时共享多余的资源的原则,考虑数据局部性和推测式算法的优势,实现了一种基于数据局部性的推测式任务调度算法LOL,通过统计执行任务节点上已经记录的数据,使得调度器能够随时收集到节点中的任务处理的有效信息,从而自主地调整任务调度队列,来提高Hadoop平台的运行效率,尤其适合在异构环境下的集群环境.
2落后任务判定算法
在快节点上为落后任务启动备份任务是减小整个工作响应时间的核心,准确判定真正的落后任务,对于减少任务响应时间至关重要.在异构环境的云计算系统中,任务的完成时间不同,落后任务完成的时间决定整个作业的运行时间,只有减小落后任务的完成时间,才能缩短整个作业完成的总时间.判定落后任务的算法是Hadoop平台的任务调度器能否高效运行的关键所在.
2.1慢任务判定算法的改进
本文将原有Hadoop调度算法中的慢任务进一步细分为Map慢任务和Reduce慢任务,正确地判断出Map慢任务和Reduce慢任务是找到落后任务的前提.
本文将Map任务又细分为两个阶段,两阶段所占Map任务总时间的比例设为MapHisFirst(MHF),MapHisSecond(MHS).对于Reduce任务继续沿用现有的Hadoop调度算法中的设定,分为三个阶段,所占时间比例设为ReduceHisFirst,ReduceHisSecond,ReduceHisThird,分别简记为RHF,RHS,RHT,并满足:
MHF+MHS等于1(1)
RHF+RHS+RHT等于1(2)
在异构环境的Hadoop集群中,由于不同的节点所具备的资源不同,磁盘读写速度,网络传输速率,CPU速度都不尽相同,所以不能保证每个节点执行任务的时间相同.但是在一个节点上的这些资源是基本保持长期不变的,在某一个节点上执行相同类型的任务所需的时间相差无几[8].在本设计中,TaskTracker上的每个任务执行完成后,将该任务执行过程中,各个阶段所耗用的时间比例记录在节点的本地磁盘上.其他任务在执行时从所属的TaskTracker所在的节点的磁盘上读取已经存储的相关的时间比例数据,记录并调整时间比例.
图3获得Map和Reduce任务时间比例算法流程图
在节点的本地磁盘上,利用已经运行过的Map任务和Reduce任务各阶段所占时间比例分别计算出各阶段耗费时间比例的平均值:AvgMapFirst(AMF),AvgMapSecond(AMS),AvgReduceFirst(ARF),AvgReduceSecond(ARS),AvgReduceThird(ART).当TaskTracker启动一个新任务时,如果该任务为Map任务,则将AMF和AMS作为Map任务两阶段耗用时间比例的数据,如果该任务为Reduce型任务,则将ARF,ARS,ART作为Reduce任务三个阶段耗用时间比例的数据.获得Map任务和Reduce任务各阶段时间比例的流程如图3所示.
在计算任务的当前进度时,设任务总数为J,任务当前所处阶段为第I阶段,任务当前阶段所需处理的数据条数为M,已经处理完成的数据条数为N.任务的进度为Progress,当前阶段已经完成的进度为SProgress,J个任务的平均进度为AvgProgress.则阶段内进度如公式(3)所示:
(3)
Map任务的两阶段计算进度方法如公式(4),(5)所示.
当I等于0时,则
Progress等于AMF*SProgress(4)
当I等于1时,则
Progress等于AMF+AMS*SProgress(5)
Reduce任务的三阶段计算进度方法如公式(6),(7),(8)所示.
当I等于0时,则
Progress等于ARF*SProgress(6)
当I等于1时,则
Progress等于ARF+ARS*SProgress(7)
当I等于2时,则
Progress等于ARF+ARS+ART*SProgress(8)
J个任务的平均进度为:
(9)
这里仍然Hadoop原有的LATE算法计算任务执行速率的方式,且Map任务和Reduce任务的执行速率相同,即:
PRM等于PRR等于progress/T(10)
在式(11)中,ProgressRateMap(PRM)为单位时间内Map任务的进度增长,ProgressRateReduce(PRR)为单位时间内Reduce任务的进度增长,T为从任务开始执行到当前时间所耗用的时间.AvgProgressRate(APR)是同类任务执行的平均速率,将APR分为Map任务的AvgProgressRateMap(APRM)和Reduce任务的AvgProgressRateReduce(APRR),Map和Reduce任务的数量分别记作CountMap(CM)和CountReduce(CR).这样,可以得到Map任务的平均速率如式(11)所示:
(11)
Reduce任务的平均速率如式(12)所示:
(12)
定义一个常数SlowTaskThreshold(STT)作为判定一个任务是否为慢任务的阈值,在本文中,若Map任务的速率满足:
PRM<,(1-STT)*APRM(13)
则判定该Map任务为Map慢的任务,若Reduce任务的速率满足:
PRR<,(1-STT)*APRR(14)
则判定该Reduce任务为Reduce慢的任务.
2.2任务的剩余时间估计算法
判定一个任务是否为落后任务并且为之启动备份任务需要满足以下几个条件:(1)系统中正在运行的备份任务数量小于阈值SpeculativeCap,(2)该任务已经执行超过60s,(3)该任务被判定为Map慢任务或者Reduce慢任务,(4)该任务在所属的Map慢任务或者Reduce慢任务中,是剩余时间最长的.由于Map慢的任务和Reduce慢的任务是不同类型的,所以落后任务也需被区分为Map落后任务和Reduce落后任务.寻找出Map落后任务和Reduce落后任务之后,将这些落后任务分别在执行Map任务快的TaskTracker和执行Reduce任务快的TaskTracker上启动备份任务,只要原任务和副本中的某一个完成,则该任务即为"成功"状态,并"杀死"另一个任务.
通过式(15)计算任务的剩余时间TimeToEnd(TTE).
(15)
图4落后任务判定算法
TaskTracker在执行任务的过程中,通过周期性的向JobTracker发送心跳通信,将当前任务的Progress,ProgressRate和任务名称以及经计算得到的TimeToEnd发送给JobTracker.由JobTracker按照剩余时间排序,对Map任务和Reduce任务分别维护一个队列:QueueSlowMap,QueueSlowReduce,这两个队列中的任务都是正在运行的任务.每次有TaskTracker请求新任务时,如果该TaskTracker请求的是Map任务,同时不存在未执行的Map任务,并且系统当前的已经启动且正在运行的备份任务数量小于SpeculativeCap,那么就在队列QueueSlowMap中选取剩余时间最长的Map任务,并判断其是否为慢任务,如果是,就为之启动备份任务,否则即忽略这个TaskTracker的请求.如果该TaskTracker请求的是Reduce任务,同时不存在未执行的Reduce任务,并且系统当前的已经启动且正在运行的备份任务数量小于SpeculativeCap,那么就在队列QueueSlowReduce中选取剩余时间最长的Reduce任务,并判断其是否为慢任务,如果是,就为之启动备份任务,否则即忽略这个TaskTracker的请求,落后任务判定流程如图4所示.
3慢节点判定算法
在本文中,将TaskTracker分为四类,Map任务和Reduce任务都慢的TaskTracker,Map任务慢Reduce任务快的TaskTracker,Map任务快Reduce任务慢的TaskTracker,Map任务和Reduce任务都快的TaskTracker.由于每一个TaskTracker仅存在于一个节点上,所以找到慢的TaskTracker也即找到了执行Map任务慢或者执行Reduce任务慢的节点.由于在实际系统中存在着异构性,所以每个节点所掌握的资源质量和数量都是不同的,因此不同节点执行Map任务和Reduce任务的速率也不同,那么可能存在某个节点执行Map任务很慢但执行Reduce任务却很快,也可能存在相对的情况,某个节点执行Reduce任务很慢但是执行Map任务很快[9,10].所以,设计中将LATE算法中的慢TaskTracker区分为执行Map任务慢的TaskTracker和执行Reduce任务慢的TaskTracker这种思想是很有必要的.
本文检测设系统中的TaskTracker总数为N,执行Map任务慢的TaskTracker和Reduce任务慢的TaskTracker的判定参数为STT.系统中的TaskTracker总数量为N,某个TaskTracker上正在运行的Map任务数量为CM,Reduce任务的数量为CR,在每个TaskTracker上计算得出该TaskTracker上的Map任务执行速率TTProgrseeRateMap(TTPRM)和Reduce任务执行速率TTProgrseeRateReduce(TTPRR),则该TaskTracker上的Map任务的平均执行速率为:
(16)
该TaskTracker上的Reduce任务的平均执行速率为:
(17)
系统中所有TaskTracker上的Map任务执行平均速率为:
(18)
系统中TaskTracker上的Reduce任务执行平均速率为:
(19)
判断系统中某个TaskTracker是否为执行Map任务慢的TaskTracker时,如若满足如下条件:
TTPRM<,(1-STT)*AvgTTPRM(20)
则判定此TaskTracker为执行Map任务慢的TaskTracker.
判断系统中某个TaskTracker是否为执行Reduce任务慢的TaskTracker时,如若满足如下条件:
TTPRR<,(1-STT)*AvgTTPRR(21)
则判定此TaskTracker为执行Reduce任务慢的TaskTracker.
4基于数据局部性推测任务调度算法
本节给出了基于数据局部性的推测式任务调度算法LOL的基本思路.当系统中有一个节点请求新的任务时,先判断该节点是执行Map任务快的节点还是执行Reduce任务快的节点.如果此节点为执行Map任务快节点,并且当前整个集群中的备份任务数量小于一个阈值SpeculativeCap,那么在请求任务的节点所在的机架上,计算该机架上所有正在执行的Map任务的剩余时间,由JobTracker维护一个名为QueueSlowMapRack的队列.该队列中按照剩余时间对正在执行的Map任务进行排序,选择QueueSlowMapRack中剩余时间最长且满足慢任务阈值SlowTaskThreshold的Map任务,并为这个Map慢任务启动备份任务.
如果请求新任务的节点被判定为执行Reduce任务快的节点,并且当前整个集群中的备份任务数量小于SpeculativeCap,那么在请求任务的节点所在的机架上,计算该机架上所有正在执行的Reduce任务的剩余时间.由JobTracker维护一个名为QueueSlowReduceRack的队列,该队列中按照剩余时间对正在执行的Reduce任务进行排序,选择QueueSlowReduceRack中剩余时间最长且满足慢任务阈值SlowTaskThreshold的Reduce任务,并为这个Reduce慢任务启动备份任务.如果QueueSlowReduceRack队列中没有满足慢任务阈值SlowTaskThreshold的Reduce任务,则计算在请求任务的节点所在机架之外的其他机架上所有正在执行的Reduce任务的剩余时间,由JobTracker维护一个名为QueueSlowReduceRackoff的队列,该队列中同样按照剩余时间对正在执行的Reduce任务进行排序,选择QueueSlowReduceRackoff中剩余时间最长且满足慢任务阈值SlowTaskThreshold的Map任务,并为这个Reduce慢任务启动备份任务.LOL调度算法流程如图5所示.
图5基于数据局部性的推测式任务调度算法流程
5实验设计及结果分析
本文的实验环境是在实验室搭建了由5台异构PC怎么写作器构成的Hadoop集群,在集群中的节点的内存容量方面以及CPU处理速度等方面都存在着很大差异,用来模仿异构环境.为了测试算法的数据局部性对性能的影响,使得节点之间能够跨机架读取数据,设定了3个机架,一个机架设置1台物理机,另外2个机架分别由2台物理机组成.在每台机器上设置2个或者3个虚拟机,增加实验的节点数量,每台虚拟机的内存设置为1GB或2GB,对应的硬盘设置为20GB或40GB.虚拟机操作系统都为Ubuntu11.10,在所有的Ubuntu系统中安装的JDK版本为1.7,在各个节点之上使用的Hadoop的版本号为1.0.2.
本文利用Hadoop的自带的作业实例WordCount来评估各种调度器的性能,WordCount是一种用来计算输入文件里每个词汇出现的频率的作业.数据来源是维基百科(Wikipedia)的数据库,在Wikipedia的数据库中下载了一个1.4G的文本格式的搜索记录,利用WordCount作业来统计这个文件之中显示的用户搜索过的关键字的出现频率.执行WordCount时,在每个TaskTracker上开启两个Map任务槽和Reduce任务槽,这样,每个TaskTracker上可同时执行两个Map任务和两个Reduce任务.通过统计每种调度算法执行WordCount作业处理该文件所耗用的运行时间来对各个调度算法进行对比评估.
5.1LOL调度器的性能评估
用调度器LOL替换Hadoop1.0.2原有的LATE调度器源,在LOL调度器中已经具有了本文给出的落后任务判定和慢节点判定等算法.将未启动推测式任务的Hadoop调度器,Hadoop原有的推测式任务调度器,LATE调度器,以及LOL调度器分别运行10次,记录出其最短执行时间,最长执行时间和平均执行时间,来对比评估LOL调度器的性能.
图6存在慢节点的运行时间
在图6中利用Hadoop原有的推测式任务调度器的运行时间作为参照.可以看出,未启动推测式任务调度算法的调度器的效率很低,平均运行时间是Hadoop原有的推测式任务调度器的1.87倍,这是因为系统设置了两个明显的慢节点,这两个节点上所执行的任务的速度很低,导致系统中产生了落后任务,而这种调度器不为落后任务启动备份任务,整个作业必须要等到慢节点上的落后任务执行完成,所以极大的延长了整个作业的运行时间,导致整个系统的响应时间下降很多.LATE调度器的平均响应时间是Hadoop原有的推测式任务调度器的响应时间的87%.LOL调度器针对LATE调度器的不足做出了改进,不依赖传统的同构集群的不合理的检测设,对异构系统的适应能力更强,剩余时间估计更加准确,能较为合理的判定落后任务与慢节点,并且考虑到数据局部性问题,从图6中可以看出,LOL调度器的平均响应时间是Hadoop原有的推测式任务调度器的70%.
图7存在慢节点的运行时间变化趋势
图7为四种调度器运行10次相同任务的时间走势图,可以看出,在异构环境下存在明显慢节点时,未启动推测式任务的调度器很不稳定,调度算法的折线图波动较大.而另外三种调度都启动了备份任务,能较好的适应异构环境中出现明显慢节点的情况,LOL调度器明显要比其他几种调度器适应性更强,更为稳定.
若不在系统中设置明显的慢节点,所有节点都正常运行,选择四种调度方式进行调度实验,结果如图8,9所示.
图8不存在慢节点的运行时间
与存在明显慢节点的异构系统对比,在不存在明显慢节点的系统中各个调度器运行时间对比图有着很大的变化,四种调度器都很大程度的缩短了运行时间,最为显着的是未启动备份任务的调度器,LOL调度器的效率仍然是最优的,因为系统中虽然不存在明显慢的节点,但也会有某个任务成为落后任务的可能.
图9不存在慢节点的运行时间变化趋势
5.2LOL调度器中各参数对性能的影响
LOL调度器中的各个参数对整个调度器的性能有着很大的影响,设置合理的参数,能够有效提高系统效率.本节对LOL调度器中的几个主要的参数与Hadoop系统性能的关系进行了评估,包括SpeculativeCap,SlowTaskThreshold,SlowTrackerThreshold,利用已有的推荐值,固定其它的参数不变,只逐步改动需要评估的参数的数值,记录每次实验的运行时间,分析各个数值对运行时间的映像,从而确定合理高效的参数配置.测试参数对性能影响的实验是在设置了明显慢的节点的环境中进行的,因为在存在明显慢节点的环境中能更好的发挥推测式任务调度的作用,这样能充分检验到LOL调度器的性能.
让LOL调度器的其它参数不变,仅改变SpeculativeCap的大小,从10%开始,以10%的增量渐增直到100%,SpeculativeCap数值每一次变动时都运行相同的任务10次,取响应时间的平均值,将运行时间走势曲线绘制如图10所示.
从图10可以看出,系统的响应时间随着SpeculativeCap值的增加先减小然增大,当SpeculativeCap处于20%的位置时,系统响应时间最小,当SpeculativeCap值小于20%时,响应时间随SpeculativeCap的增大而减小,当SpeculativeCap值大于20%时,响应时间并未继续减小而是缓慢的增加.这是因为调度器启动备份任务也会消耗一些系统资源,占用其他节点上的空闲任务槽,执行备份任务也会占用集群的网络带宽,节点上的CPU与磁盘等资源,最差的情况是系统启动备份任务后执行作业的时间甚至多于不启动备份任务所消耗的时间.
图10SpeculativeCap对运行时间的影响
SlowTaskThreshold是一个用来判定正在执行的任务是否是慢任务的阈值.如果SlowTaskThreshold设置过小,调度器可能会将某些非慢的任务错误的判别为慢任务,从而使系统为这些非慢任务不必要的启动备份任务,浪费系统资源.如果SlowTaskThreshold设置过大,调度器可能会将某些慢任务认为是非慢的任务,忽略这些可能成为落后任务的慢任务,未能及时的为之启动备份任务,导致整个作业延迟完成.控制LOL调度器的其它参数不变,仅改变SlowTaskThreshold的大小,从10%开始,以10%的增量渐增直到100%,SlowTaskThreshold数值每一次变动时都运行相同任务10次,取响应时间的平均值,将运行时间走势曲线绘制如图11所示.
图11SlowTaskThreshold对运行时间的影响
可以图11看出,系统响应时间随着SlowTaskThreshold值的增加先减小然增大,当SlowTaskThreshold处于30%的位置时,系统响应时间最小,当SlowTaskThreshold值小于30%时,响应时间随SlowTaskThreshold的增大而减小,这是因为当SlowTaskThreshold较小时,系统中只要存在运行速度稍低于平均速度的任务时,但是这样的任务可能并不是慢任务,只是由于SlowTaskThreshold过小,被判别为慢任务,空闲的任务槽会为这样的任务启动备份任务,甚至大量的启动不必要的备份任务,与其他任务竞争使用系统资源,导致其他任务执行的速度下降,延长了整个系统的响应时间.当SlowTaskThreshold值大于30%时,响应时间并未继续减小而是缓慢的增加.这是因为随着SlowTaskThreshold增大,调度器判定出的慢任务逐渐减少,甚至会把慢任务误判为非慢任务,系统不会为真正的慢任务启动备份任务,调度器失去了推测执行任务的意义,落后任务的完成时间决定了整个作业的完成时间,导致整个系统的响应时间变大.
SlowTrackerThreshold是一个用来判定系统中的TaskTracker是否属于执Map任务慢的TaskTracker,或者执行Reduce任务慢的TaskTracker的阈值.如果SlowTrackerThreshold设置过大,调度器可能不能探测到执行Map任务慢的TaskTracker和Reduce任务慢的TaskTracker,也即有可能在慢TaskTracker上启动备份任务,白白浪费了系统资源,甚至降低了整个系统的速度.如果SlowTrackerThreshold设置过小,可能会将部分执行任务快的TaskTracker判定为慢的TaskTracker,使系统中没有可用的节点来为落后任务启动备份任务,延长了整个系统的响应时间.控制LOL调度器的其它参数不变,仅改变SlowTrackerThreshold的大小,从10%开始,以10%的增量渐增直到100%,SlowTrackerThreshold数值每一次变动时都运行相同任务10次,取响应时间的平均值,将运行时间走势曲线绘制如图12所示.
从图12可以看出,当SlowTaskThreshold处于20%的位置时,系统响应时间最小,当SlowTaskThreshold值小于20%时,响应时间随SlowTaskThreshold的增大而减小,这是因为当SlowTaskThreshold较小时,某个空闲TaskTracker的速度稍低于平均速度,则可能判定此TaskTracker为慢的TaskTracker,从而不能在其上启动备份任务,在实验环境中节点较少时尤为明显,所以此时随SlowTaskThreshold的增大,响应时间越来越理想.当SlowTaskThreshold值大于32%之后,响应时间并未继续减小而是缓慢的增加.这是因为随着SlowTaskThreshold增大,调度器把更多TaskTracker错误地判定为非慢的节点,可能会在慢的TaskTracker上执行备份任务,作无用的备份任务,这样的启动备份任务是徒劳的,甚至会占用很多系统资源,导致其他任务的执行速率下降,影响整个系统的吞吐率.当SlowTaskThreshold增加到50%时,响应时间达到峰值,任务槽的数量不能为所有的落后任务启动备份任务,备份任务与非备份任务争夺系统内的资源,使得系统的响应时间达到最大.SlowTaskThreshold继续增大,响应时间有所下降,这是由于随着SlowTaskThreshold的继续增大,被判定为慢的TaskTracker数量逐渐减少,就会有更多节点启动备份任务,在为慢任务中的落后任务启动备份任务之后,系统的响应时间会有所回落.
图12SlowTrackerThreshold对运行时间的影响
5结束语
本文给出的LOL调度算法参考了LATE调度算法的优点,即采用为完成当前任务所需剩余时间最长的落后任务启动备份任务的方式,来达到推测执行任务的目的,降低整个作业的运行时间,提高系统资源的利用率.同时,采用了更精确的任务进度探测方式,解决了Hadoop自带调度算法对任务剩余时间估计不够准确的缺陷,能够比较准确的估计出任务的剩余时间,从而正确的找出落后任务.给出区分快节点和慢节点的方法,进一步将节点细分为执行Map任务慢和执行Reduce任务慢的节点,使得为落后任务启动备份任务的效率增加,提高了系统资源的利用率.LOL调度器由于是基于数据局部性的推测式任务调度算法,更合理的利用了大规模计算集群的机架之间读取数据会占有系统较多的稀缺资源—网络带宽,从而满足移动计算比移动数据更经济这一条件,降低了网络拥塞的可能性,加快任务的执行效率,提高了系统的吞吐率.
ation,2016[C].SanDiego:Usenix,2016:29-42.,[8]BERNARDINJandLEEPandLEWISJ.UsingexecutionstatisticstoselecttaskorredundantassignmentinadistributedputingplatformGooglePatents:US,093004[P].2006.08.15.
[9]WARNEKED,KAOO.Exploitingdynamicresourceallocationforefficientparalleldataprocessinginthecloud[J].IEEETransactionsonParallelandDistributedSystems,2016,22(6):985-997.
[10]CALHEIROSRN,RENJANR.BeloglazovA,ete1.Cloudaim:Atoolkitformodelingandsimulationofcloudputingenvironmentsandevaluationofresourceprovisioningalgorithms[J].Soflwan:PracticeandExperience(SPE),2016,41(1):23-50.
修改说明:
按照模板修改了论文格式,
压缩了摘 要,
重新画了图3,4,5,6,8,将彩重新画成黑白图.
双页码计算机应用研究2006年
页码计算机应用研究第28卷
第卷第期计算机应用研究Vol.No.
201年期ApplicationResearchofComputersJan.201
———————————————
收稿日期:2016-04-00,修回日期:基金项目:国家自然科学基金(61070162,71071028)
作者简介:刘奎1973年10月生,男,河北唐山人,讲师,主要研究方向为数据处理(wangcr@mail.neuq.edu.),刘向东,1966年9月生,男,讲师,研究方向并行计算,马宝来1988年11月生,男,硕士,研究方向并行计算,王翠荣,1963年5月生,女,教授,主要研究方向为计算机网络
结束
在本地磁盘上写入任务各阶段时间比例
Task
是否关闭
更新TaskTracker任务各阶段时间比例
Task与TaskTracker交互获得各阶段时间比例
是
是
计算落后任务
任务运行时间>,60s
备份任务数>,上限量>,shangxian
执行Task,计算各阶段时间比例,进度,剩余时间
结束
启动备份任务
系统有新任务否
从落后任务队列中删除该任务
Task从TaskTracker获取信息
TaskTracker读本地任务信息
该任务是慢任务
开始
TaskTracker从本地磁盘读取各阶段时间比例
Task
是否完成
启动TaskTracker
是
是
创建QueueSlowMapRack队列,按剩余时间任务排序
计算节点所在机架上其它节点上任务剩余时间
结束
是否还有落后任务
创建QueueSlowMapRakcoff队列,按剩余时间任务排序
计算其它机架上节点上任务的剩余时间
是否有落后任务
开始
否
否
否
否
是
是
否
是
否
是
是
执行该落后任务的备份任务,从落后队列中删除该任务
否
该节点是慢节点
否
否