您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 销售管理 > 基于Hadoop+MapReduce的组合服务性能优化研究
计算机技术与发展COMPUTERTECHNOLOGYANDDEVELOPMENT第26卷第5期2016年5月Vol.26No.5May2016基于HadoopMapReduce的组合服务性能优化研究秦军1,翟钊2(1.南京邮电大学教育科学与技术学院,江苏南京210003;2.南京邮电大学计算机学院,江苏南京210003)摘要:对Hadoop中的任务调度进行了研究,在分析Hadoop作业调度算法的需求的基础上,文中提出了调度算法在线性意义上的解空间。针对Hadoop的编程模型框架,提出了一种结合禁忌搜索思想的改进人工鱼群算法。在该算法中,以任务总执行时间作为寻优函数,采用线性编码方式,每一个N维向量代表一种具体调度方案;利用将解向量直接作为人工鱼的方法,使人工鱼群算法可以直接在解空间内运行。结合禁忌搜索思想,既保留了人工鱼群算法计算基数大仍能快速收敛的优点,又充分利用禁忌搜索不会陷入局部最优解的优势。通过仿真实验将该算法和Fair算法进行比较,结果表明:改进的人工鱼群作业调度算法可以提高系统性能,降低任务运行时间,是一种Hadoop环境下有效的任务调度程序。关键词:Hadoop;人工鱼群算法;作业调度算法;组合优化中图分类号:TP301.6文献标识码:A文章编号:1673-629X(2016)05-0061-05doi:10.3969/j.issn.1673-629X.2016.05.013ResearchonCompositeServicePerformanceOptimizationBasedonHadoopMapReduceQINJun1,ZHAIZhao2(1.CollegeofEducationScience&Technology,NanjingUniversityofPostsandTelecommunications,Nanjing210003,China;2.CollegeofComputer,NanjingUniversityofPostsandTelecommunications,Nanjing210003,China)Abstract:ResearchofjobschedulinginHadoop,basedonanalysisofrequirementforHadoopjobschedulingalgorithm,thesolutionspaceinlinearmeaningofschedulingalgorithmisproposed.AimingattheproceduremodelforHadoop,animprovedArtificialFishSwarmAlgorithm(AFSA)combinestabusearchisputforward.Itusestotalexecutiontimeastheoptimizedfunctions,andwithlinearcoding,eachN-dimensionalvectorrepresentsaspecialschedulingscheme.Themethodwhichtakessolutionvectorasartificialfishdi-rectlyisappliedtomakeAFSAcanberundirectlyinthesolutionspace.IAFSAnotonlyretainstheadvantagesofrapidconvergenceofAFSAatalargecomputingbase,alsomakesfulluseoftheadvantagesoftabusearchdoesnotfallintolocaloptima.ThroughcomparisonbetweenthealgorithmwiththeFairalgorithm,theexperimentshowsthattheimprovedAFSAinheterogeneousenvironmentscanimprovesystemperformanceandreducethecomputingtime.ItiseffectiveintheHadoopenvironment.Keywords:Hadoop;AFSA;jobschedulingalgorithm;combinatorialoptimization1概述在Hadoop系统中,作业调度的策略一直都是重点优化目标之一,其目标是实现高可用性服务、网络吞吐量和集群负载的动态均衡[1-2]。其实质是寻求资源和能力之间进行匹配的最佳解决方案,即寻取一个作业执行时间最短的全局最优解[3]。对于云服务大多采用租赁形式向用户提供服务的现行模式来说,快速的任务响应无疑是云服务的服务质量(QualityofServ-ice,QoS)的一个重要因素。在Hadoop系统[4]中,Master节点作为Hadoop集群的控制中枢,作业调度是其功能的重要组成之一,这就要求调度算法不能过于复杂。如果调度算法采用复杂设计,全局最优解固然收稿日期:2015-08-12修回日期:2015-11-17网络出版时间:2016-05-05基金项目:江苏省自然科学基金项目(BK20130882)作者简介:秦军(1955-),女,教授,研究方向为计算机网络技术、多媒体技术、数据库技术;翟钊(1990-),男,硕士研究生,研究方向为分布式计算机技术与应用。网络出版地址:计算机技术与发展第26卷·62·可以得到,但快速的任务响应却很难做到,尤其是如果调度算法复杂度过高,随着节点数目的增加,Master的管理负担会呈现几何级数的增长,进而使得Master计算压力增加,不利于集群的实时调度需求,最终影响服务的QoS。Hadoop自带了三种资源调度策略,分别是先进先出调度算法[5](FirstInFirstOut,FIFO)、公平调度算法—Fair算法[6]、计算能力调度算法—Capacity算法[7]。但是这几种调度策略设计过于简单,存在资源浪费、作业响应时间长等不足,并且算法具有容易陷入局部最优解、不能高效使用资源等问题。目前,主流的集群调度算法主要是针对同构环境下的作业调度,在调度过程中研究的主要热点包括作业执行顺序、计算资源分配以及调度性能优化等多个方面。国内外学者针对MapReduce集群,先后提出了许多调度算法。Matei等提出一种竞争性调度算法[8];Polo等提出基于时间阈值来决定作业调度和执行以及资源自适应策略[9];Zaharia等提出了作业延时等待的策略[10];国内有人提出异构环境下的自适应算法、公平队列调度算法[11]……上述算法绝大部分都是讨论在同构的环境中进行的优化。然而,在实际的运行环境中,集群往往是由不同制造商生产的计算机、网络设备和系统组成的高度差异化系统,一般实现方式为跨协议集成以实现表层接口统一。上述调度算法在这样的集群中运行时,往往随着集群PC数量的增长和作业量的增大而变得效率越来越低下;而蚁群算法、人工鱼群算法等群智能算法,具有效率对基数不敏感、对海量作业适应性高等优点,将群智能算法作为调度算法可以获得效率的极大提升。人工鱼群算法(ArtificialFishSwarmAlgorithm,AFSA)[12-15]是一种新的启发式生物智能算法,具有计算基数大仍能快速收敛和不需要问题的精确描述等优点。AFSA主要适用于连续变量型问题的优化[16],另外AFSA擅长的是寻取一个最优解域,再则由于觅食行为中随机行为,使得算法中有迂回搜索的缺点。针对上述问题,文中在AFSA基础上,结合禁忌搜索算法[17](TabuSearch,TS),提出了一种改进的人工鱼群算法(ImprovedArtificialFishSwarmAlgorithm,IAFSA)。仿真结果表明,IAFSA不仅保留了AFSA的优点,而且以较快的速度收敛,并且相比于Hadoop自带的Fair调度算法在作业执行速度上有较大提升。2Hadoop作业调度策略的解空间假设用户向Hadoop提交了一个批次的任务,系统将这个批次的任务划分为m个Mapper节点和r个Re-ducer节点,master节点决定m个Mapper节点产生的中间结果如何在r个Reducer节点上进行Reduce操作。m个Mapper节点产生的m个中间结果以1至m编号,r个Reducer节点以1至r编号。master分配方案的解空间的构成为:m个中间结果互相独立,每一个中间结果都可以在r个Reducer节点中随意选择。这意味着一共有rm个选择方案,这rm个解决方案形成了一个m维的、分量取值范围为1至r的解空间,在这个解空间中的每一个点都是一个n维向量,如式(1)所示:X=(a1,a2,…,am)1≤i≤m,1≤ai≤r(1)式中,ai表示第i个中间结果分配到第ai个Re-ducer节点。每一个n维向量都是一个分配方案,也即是mas-ter节点可选择的一个调度策略。任意一个n维向量作为调度策略的选择时,最终耗费的Reduce作业时间见式(2)。F(X)=max{cost(1),cost(2),…,cost(r)}(2)式中,cost(i)表示分配到第i个Reducer节点上的任务的执行时间花费。算法所需求解的是如何使F(X)最小化。为便于C理解,后文把F(X)作为AFSA的寻优函数。3人工鱼群算法及禁忌搜索AFSA主要的特点是对问题的优劣性进行比较,然后由个体人工鱼在局部区域进行搜索,最终给出一个最佳解决方案。TS是Glover在1986年提出的一种算法,它延伸了本地搜索的概念,是一种全局性的渐进的优化算法,是仿真人类智能的过程。3.1人工鱼群算法AFSA的主要思想是,一片水域中富含营养物质最多的地方生存的鱼类数目也就最多。通过这一特点,李晓磊等提出利用单条鱼的行为及鱼和鱼之间互相作用的行为进行全局寻优。以下对鱼的这几种行为进行简要描述。(1)觅食行为。设人工鱼当前状态为Xi,在其感知范围内随机选择一个状态Xj,如果在求极大问题中,YiYj(或在求极小问题中,YiYj,因极大和极小问题可以互相转换,所以以下均以求极大问题讨论),则向该方向前进一步;反之,再重新随机选择状态Xj,判断是否满足前进条件;这样反复尝试trynumber次后,如果仍不满足前进条件,则随机移动一步。(2)聚群行为。设人工鱼当前状态为Xi,探索当前邻域内(即dij第5期秦军等:基于HadoopMapReduce的组合服务性能优化研究·63·YncnVisual)的伙伴数目nf及中心位置Xc,如果f啄Yi,表明伙伴中心有较多的食物并且不太拥挤,则朝伙伴的中心位置方向前进一步;否则执行觅食行为。(3)追尾行为。设人工鱼当前状态为Xi,探索当前邻域内(即dijYjVisual)的伙伴中Yj为最大的伙伴Xj,如果f啄Yi,表明伙伴Xj的状态具有较高的食物浓度并且其周围不太拥挤,则朝伙伴Xj的方向前进一步;否则执行觅食行为。3.2禁忌搜索算法TS算法采用模拟人类智力的标记模式,采用禁忌表的形式来避免搜索过程陷入本地最优解导致的反复搜索,进而保证有效且多样的搜索并最终实现全局优化。禁忌搜索核心思想是,对已得到的本地最优解进局最优值,同时可以避免重复搜索。4N维空间的改进人工鱼群算法描述文中提出的IAFSA算法可以直接在解空间中运行。以下对人工鱼模型的建立,单条鱼的觅食、追尾和聚群行为进行说明。4.1人工鱼模型文中取前文中描述的解向量为人工鱼模型,以使IAFSA算法可以直接在解空间内运行。在网格化的解空间里,AFSA中的移动步长Step与网格单位长度意义重合,所以直接采用网格长度作为移动步长。人工鱼移动时采用的网格长度计算见式(1)。4.2人工鱼行为描述人工鱼行为描述是在原行为的基础上在解空间内做这些行为时的适配描述。(1)觅食行为。行记录,并在之后的迭代搜索中对此类解进行无视操假
本文标题:基于Hadoop+MapReduce的组合服务性能优化研究
链接地址:https://www.777doc.com/doc-4308882 .html