基于Hadoop MapReduce的组合服务性能优化研究
2016-02-24秦军，翟钊
秦 军，翟 钊
(1.南京邮电大学 教育科学与技术学院，江苏 南京 210003；2.南京邮电大学 计算机学院，江苏 南京 210003)
基于Hadoop MapReduce的组合服务性能优化研究
秦 军1，翟 钊2
(1.南京邮电大学 教育科学与技术学院，江苏 南京 210003；2.南京邮电大学 计算机学院，江苏 南京 210003)
对Hadoop中的任务调度进行了研究，在分析Hadoop作业调度算法的需求的基础上，文中提出了调度算法在线性意义上的解空间。针对Hadoop的编程模型框架，提出了一种结合禁忌搜索思想的改进人工鱼群算法。在该算法中，以任务总执行时间作为寻优函数，采用线性编码方式，每一个N维向量代表一种具体调度方案；利用将解向量直接作为人工鱼的方法，使人工鱼群算法可以直接在解空间内运行。结合禁忌搜索思想，既保留了人工鱼群算法计算基数大仍能快速收敛的优点，又充分利用禁忌搜索不会陷入局部最优解的优势。通过仿真实验将该算法和Fair算法进行比较，结果表明：改进的人工鱼群作业调度算法可以提高系统性能，降低任务运行时间，是一种Hadoop环境下有效的任务调度程序。
Hadoop；人工鱼群算法；作业调度算法；组合优化
1 概 述
在Hadoop系统中，作业调度的策略一直都是重点优化目标之一，其目标是实现高可用性服务、网络吞吐量和集群负载的动态均衡[1-2]。其实质是寻求资源和能力之间进行匹配的最佳解决方案，即寻取一个作业执行时间最短的全局最优解[3]。对于云服务大多采用租赁形式向用户提供服务的现行模式来说，快速的任务响应无疑是云服务的服务质量(Quality of Service，QoS)的一个重要因素。在Hadoop系统[4]中，Master节点作为Hadoop集群的控制中枢，作业调度是其功能的重要组成之一，这就要求调度算法不能过于复杂。如果调度算法采用复杂设计，全局最优解固然可以得到，但快速的任务响应却很难做到，尤其是如果调度算法复杂度过高，随着节点数目的增加，Master的管理负担会呈现几何级数的增长，进而使得Master计算压力增加，不利于集群的实时调度需求，最终影响服务的QoS。Hadoop自带了三种资源调度策略，分别是先进先出调度算法[5](First In First Out，FIFO)、公平调度算法—Fair算法[6]、计算能力调度算法—Capacity算法[7]。但是这几种调度策略设计过于简单，存在资源浪费、作业响应时间长等不足，并且算法具有容易陷入局部最优解、不能高效使用资源等问题。
目前，主流的集群调度算法主要是针对同构环境下的作业调度，在调度过程中研究的主要热点包括作业执行顺序、计算资源分配以及调度性能优化等多个方面。国内外学者针对MapReduce集群，先后提出了许多调度算法。Matei等提出一种竞争性调度算法[8]；Polo等提出基于时间阈值来决定作业调度和执行以及资源自适应策略[9]；Zaharia等提出了作业延时等待的策略[10]；国内有人提出异构环境下的自适应算法、公平队列调度算法[11]……
上述算法绝大部分都是讨论在同构的环境中进行的优化。然而，在实际的运行环境中，集群往往是由不同制造商生产的计算机、网络设备和系统组成的高度差异化系统，一般实现方式为跨协议集成以实现表层接口统一。上述调度算法在这样的集群中运行时，往往随着集群PC数量的增长和作业量的增大而变得效率越来越低下；而蚁群算法、人工鱼群算法等群智能算法，具有效率对基数不敏感、对海量作业适应性高等优点，将群智能算法作为调度算法可以获得效率的极大提升。
人工鱼群算法(Artificial Fish Swarm Algorithm,AFSA)[12-15]是一种新的启发式生物智能算法，具有计算基数大仍能快速收敛和不需要问题的精确描述等优点。AFSA主要适用于连续变量型问题的优化[16]，另外AFSA擅长的是寻取一个最优解域，再则由于觅食行为中随机行为，使得算法中有迂回搜索的缺点。
针对上述问题，文中在AFSA基础上，结合禁忌搜索算法[17](Tabu Search，TS)，提出了一种改进的人工鱼群算法(Improved Artificial Fish Swarm Algorithm，IAFSA)。仿真结果表明,IAFSA不仅保留了AFSA的优点，而且以较快的速度收敛，并且相比于Hadoop自带的Fair调度算法在作业执行速度上有较大提升。
2 Hadoop作业调度策略的解空间
假设用户向Hadoop提交了一个批次的任务，系统将这个批次的任务划分为m个Mapper节点和r个Reducer节点，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)所示：
(1)
式中,ai表示第i个中间结果分配到第ai个Reducer节点。
每一个n维向量都是一个分配方案,也即是master节点可选择的一个调度策略。任意一个n维向量作为调度策略的选择时，最终耗费的Reduce作业时间见式(2)。
F(X)=max{cost(1),cost(2),…,cost(r)}
(2)
式中,cost(i)表示分配到第i个Reducer节点上的任务的执行时间花费。
3 人工鱼群算法及禁忌搜索
AFSA主要的特点是对问题的优劣性进行比较，然后由个体人工鱼在局部区域进行搜索，最终给出一个最佳解决方案。
TS是Glover在1986年提出的一种算法，它延伸了本地搜索的概念，是一种全局性的渐进的优化算法，是仿真人类智能的过程。
3.1 人工鱼群算法
AFSA的主要思想是，一片水域中富含营养物质最多的地方生存的鱼类数目也就最多。通过这一特点，李晓磊等提出利用单条鱼的行为及鱼和鱼之间互相作用的行为进行全局寻优。以下对鱼的这几种行为进行简要描述。
(1)觅食行为。
设人工鱼当前状态为Xi，在其感知范围内随机选择一个状态Xj，如果在求极大问题中，Yi
(2)聚群行为。
(3)追尾行为。
3.2 禁忌搜索算法
TS算法采用模拟人类智力的标记模式，采用禁忌表的形式来避免搜索过程陷入本地最优解导致的反复搜索，进而保证有效且多样的搜索并最终实现全局优化。禁忌搜索核心思想是，对已得到的本地最优解进行记录，并在之后的迭代搜索中对此类解进行无视操作，从而保证能实现对所有有效搜索路径的覆盖。禁忌搜索提出了邻域、禁忌表、禁忌长度、候选解、特赦准则等概念。文中仅对在IAFSA中用到的几个概念进行说明。
(1)邻域点。
定义网格点A的邻域点为在Rm维解空间中和网格点A相邻的网格点，易得在m维空间中除边界点外每个网格点都有2*m个邻域点。图1是二维解空间中的网格点A的邻域点显示。邻域点概念在IAFSA中使用时，相当于AFSA中的觅食行为中的随机状态Xj。
图1 二维解空间的邻域点显示
(2)特赦准则。
TS算法在IAFSA中使用时，定义其特赦准则为式(3)。
FoodDensity(X)=bestDensity
(3)
式中：X为要赦免的禁忌点；bestDensity为禁忌表中记录的历史候选解。
特赦的标准是，当前搜索到的解是搜索过程中找到的全局最优解。
特赦准则能够实现高效的全局优化搜索的特点，可以确保人工鱼进行全局范围的搜索，最终搜索到全局最优值，同时可以避免重复搜索。
4 N维空间的改进人工鱼群算法描述
文中提出的IAFSA算法可以直接在解空间中运行。以下对人工鱼模型的建立，单条鱼的觅食、追尾和聚群行为进行说明。
4.1 人工鱼模型
文中取前文中描述的解向量为人工鱼模型，以使IAFSA算法可以直接在解空间内运行。在网格化的解空间里，AFSA中的移动步长Step与网格单位长度意义重合，所以直接采用网格长度作为移动步长。人工鱼移动时采用的网格长度计算见式(1)。
4.2 人工鱼行为描述
人工鱼行为描述是在原行为的基础上在解空间内做这些行为时的适配描述。
(1)觅食行为。
假设人工鱼当前位置为Xi。首先替代AFSA中随机选择一种行为为遍历邻域点寻找食物浓度最高的点，定义为Xj，然后判断Xj是否在禁忌表中。如果在禁忌表中，就判断其是否符合特赦准则，如果符合就移动至Xj，觅食结束。如果不符合特赦准则，就把该人工鱼重新初始化，以使其重新寻优，相当于在人工鱼实际数目不变的基础上增大了寻优的人工鱼个数。如果Xj不在禁忌表中，则移动至Xj并把该点加入到禁忌表，然后将该点的食物浓度与公告板的信息相比较，选较优者为公告板信息并更新公告板维持不变的次数。
觅食行为的流程图如图2所示。
图2 人工鱼觅食行为流程
(2)聚群行为。
设人工鱼当前位置为Xi，在其视野范围内的伙伴(其他鱼)的中心位置为Xj，定义伙伴中心网格点的位置：
(4)
式中，dij为视野内其他网格点到Xi的距离。
如果中心网格点具有较高的食物浓度，且拥挤度小于阈值，则人工鱼从当前位置向中心网格点移动一步；否则执行觅食行为。
(3)追尾行为。
IAFSA中的追尾行为与AFSA中的追尾行为动作相同，但把移动时的移动步长Step更改为网格长度。
4.3 最优解的获取
AFSA可以获取待求解问题的近似解，但不擅长获取组合优化类问题需要的精确解。在网格化的解空间里，每一个位置都是一个精确解，这就解决了AFSA的弊端。同时通过在IAFSA中引入禁忌搜索的思想，避免了大量的迂回搜索，提高了求解问题的速度，强制把陷入局部最优的人工鱼重新初始化，能够在全局范围内进行更广泛的搜索，同时充分利用了历史最优解起到的禁忌作用。在迭代过程中，如果公告板维持一定的次数没有更新，则可认为获得了最优解。
5 算法实现步骤
(1)给定m和r，设定公告板连续不更新次数上限Numuc和初始人工鱼数量fish_num。
(2)初始化各条人工鱼的位置，Xi=X0+Random()。其中，X0为m维坐标系的原点，Random()为分量取值范围为1至r的随机向量。如该点代表的解决方案在禁忌表中，则重新进行Random()操作；否则将此点插入禁忌表。
(3)遍历人工鱼，各人工鱼依次按规则游动一次，更新禁忌表，然后与公告板信息进行比较。如当前点的解决方案优于公告板信息，则公告板进行更新操作，同时公告板信息连续不更新次数Nuc=0；否则Nuc=Nuc+1。
(4)如当前公告板信息连续不更新次数Nuc小于Numuc，则跳转至第3步；否则算法结束，获得最优解。
通过上述算法建立的人工鱼群模型将算法展开，没有高层的指挥者且对寻找方向完全不做限制，每条人工鱼就按照自己的规则游动，运用人工鱼的自主行为来寻优。运用IAFSA动态地寻找解向量的最优解，不断更新公告板，最后公告板记录的最优值，即为分配任务的最终策略。
6 仿真实现
文中采用云计算环境仿真平台CloudSim 3.0[18]进行仿真实验。通过CloudSim中的Datacenter、Cloudlet和CloudCoordinator及一些辅助类模拟云计算的计算节点和网络资源、创建人物和虚拟机，计算节点的计算能力和网络传输能力设置不同值以尽量贴近真实环境，并重写DataCenterBroker类和Cloudlet类，构造IAFSA，与Fair算法[6]进行性能比较。实验PC配置为Core i5处理器，6 G内存，操作系统为Windows 7。
算法实现中，IAFSA相关参数为：人工鱼数量fish_num=50，公告板连续不更新次数上限Numuc=30，人工鱼视野Visual=16，拥挤度因子δ=0.618。
仿真中，在由虚拟机组成的Hadoop集群上执行了三种类型的作业：Grep、WordCount和Sort。分别测试了在不同大小的输入数据下的作业完成时间，IAFSA与Fair算法相比较测试结果如图3～5所示。
图3 Grep作业仿真结果
图4 WordCount作业仿真结果
图5 Sort作业仿真结果
仿真结果显示，使用IAFSA比Fair算法具有更高的作业执行速度，可以提高集群整体作业执行效率。从图3～5中还可以看出，不同作业下，IAFSA都比Fair算法效率高，说明IAFSA具有较高的稳定性。另外，随着作业量的增长及运行时间曲线可以看出，IAFSA的效率比Fair算法的效率差异幅度更大，说明Fair算法随着作业量的增长，效率出现了一定的下降，而IAFSA更适应海量作业的处理，效率并未降低而且增长幅度有小幅上升。IAFSA通过将解向量作为人工鱼，使得计算资源和计算能力节点达到很好的匹配，有效减少了节点的闲置时间，提高了计算节点的利用率，以此大幅降低了任务的执行时间。
7 结束语
HadoopMapReduce是当前最成功的、应用最广泛的并行计算框架和模型之一。其作业调度算法效率对整个集群的性能有着显著影响。文中采用IAFSA对作业调度算法进行优化，利用AFSA的收敛速度，通过优化算法减少重复搜索，获取精确解。仿真结果表明，通过IAFSA来改进Hadoop作业调度算法的方案是可行的，该算法有利于提高集群整体执行效率，降低了任务的执行时间。
[1]DeanJ,GhemawatS.MapReduce:simplifieddataprocessingonlargeclusters[J].CommunicationsoftheACM,2008,51(1):107-113.
[2]BhandarkarM.MapReduceprogrammingwithapacheHadoop[C]//ProcofIEEEinternationalsymposiumonparallel&distributedprocessing.[s.l.]:IEEE,2010.
[3] 李春艳,何一舟,戴 彬.Hadoop平台的多队列作业调度优化方法研究[J].计算机应用研究,2014,31(3):705-707.
[4]ApacheHadoop[EB/OL].2012-04-16.http://hadoop.apache.org.
[5] 李建锋,彭 舰.云计算环境下基于改进遗传算法的任务调度算法[J].计算机应用,2011,31(1):184-186.
[6]Hadoop公平调度算法[EB/OL].2010-02-19.http://hadoop.apache.org/docs/r0.20.2/fair_scheduler.html.
[7] 罗军舟,金嘉晖,宋爱波,等.云计算:体系架构与关键技术[J].通信学报,2011,32(7):3-21.
[8]RajuR,AmudhavelJ,PavithraM,etal.AheuristicfaulttolerantMapReduceframeworkforminimizingmakespaninhybridcloudenvironment[C]//Procofinternationalconferenceongreencomputingcommunicationandelectricalengineering.[s.l.]:IEEE,2014:1-4.
[9]BerkovichVG.Spectraltheoryandanalyticgeometryovernon-Archimedeanfields[M].American:AmericanMathematicalSoc.,2012.
[10]RenZ,WanJ,ShiW,etal.Workloadanalysis,implications,andoptimizationonaproductionHadoopcluster:acasestudyonTaobao[J].IEEETransactionsonServicesComputing,2014,7(2):307-321.
[11] 张 雨,李 芳,周 涛.云计算环境下基于遗传蚁群算法的任务调度研究[J].计算机工程与应用,2014,50(6):51-55.
[12] 李晓磊.一种新型的智能优化方法-人工鱼群算法[D].杭州:浙江大学,2003.
[13] 王联国,洪 毅,赵付青,等.一种改进的人工鱼群算法[J].计算机工程,2008,34(19):192-194.
[14] 易新兵，杨凯. 复合混沌-人工鱼群混合算法的改进及性能研究[J]．计算机工程与科学 2013, 35(8) 89-95.
[15] 姚丽莎，王占凤，程家兴．基于人工鱼群遗传算法的异构多核系统任务调度研究[J]．计算机工程与科学，2014, 36(10) 1866-1871.
[16] 李晓磊,路 飞,田国会,等.组合优化问题的人工鱼群算法应用[J].山东大学学报:工学版,2004,34(5):64-67.
[18]CalheirosRN,RanjanR,BeloglazovA,etal.CloudSim:atoolkitformodelingandsimulationofcloudcomputingenvironmentsandevaluationofresourceprovisioningalgorithms[J].Software:PracticeandExperience,2011,41(1):23-50.
Research on Composite Service Performance Optimization Based on Hadoop MapReduce
QIN Jun1,ZHAI Zhao2
(1.College of Education Science & Technology,Nanjing University of Posts and Telecommunications,Nanjing 210003,China;2.College of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)
Research of job scheduling in Hadoop,based on analysis of requirement for Hadoop job scheduling algorithm,the solution space in linear meaning of scheduling algorithm is proposed.Aiming at the procedure model for Hadoop,an improved Artificial Fish Swarm Algorithm (AFSA) combines tabu search is put forward.It uses total execution time as the optimized functions,and with linear coding,eachN-dimensionalvectorrepresentsaspecialschedulingscheme.ThemethodwhichtakessolutionvectorasartificialfishdirectlyisappliedtomakeAFSAcanberundirectlyinthesolutionspace.IAFSAnotonlyretainstheadvantagesofrapidconvergenceofAFSAatalargecomputingbase,alsomakesfulluseoftheadvantagesoftabusearchdoesnotfallintolocaloptima.ThroughcomparisonbetweenthealgorithmwiththeFairalgorithm,theexperimentshowsthattheimprovedAFSAinheterogeneousenvironmentscanimprovesystemperformanceandreducethecomputingtime.ItiseffectiveintheHadoopenvironment.
Hadoop;AFSA;job scheduling algorithm;combinatorial optimization
2015-08-12
2015-11-17
时间：2016-05-05
江苏省自然科学基金项目(BK20130882)
秦 军(1955-)，女，教授，研究方向为计算机网络技术、多媒体技术、数据库技术；翟 钊(1990-)，男，硕士研究生，研究方向为分布式计算机技术与应用。
http://www.cnki.net/kcms/detail/61.1450.TP.20160505.0828.074.html
TP
A
1673-629X(2016)05-0061-05
10.3969/j.issn.1673-629X.2016.05.013
