基于HadoopMapReduce作业调度方法研究

王玉芹

摘要：信息技术飞速发展，以及如今的互联网的快速性的发展，云计算作为现在最为流行的计算模式，很好达到了传统的互联网式服务模式。关系到集群运行得很好的性能以及整个集群，能否有效利用各个的调度系统资源的关键，更好地来满足信息用户的需求。但是随着不同应用的环境变化，Hadoop 的调度算法很难充分的适应用户的应用式环境变化的多种性需求，因此改进现有的业务调度式流程算法非常的重要。本文针对在数据的区域性方面初始作业的调度算法的不足性，在引入預先提取技术的基础上，设计了一种基于资源提前取出的Hadoop MapReduce 作业调度算法。

关键词：云计算；业务调度式流程数据的区域性；资源提前取出；Hadoop MapReduce.

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2018）27-0010-02

1 概述

互联网时代，大量的用户信息数据需要得到及时迅速的处理，因此互联网系统开发和操作人员需要研究一个能够处理大数据并存储大量异构数据的数据库和能够计算不同结构的算法。Google 云计算系统的关键技术由Hadoop开源实现并得到广泛支持及应用。弹性计算云[1]（elastic compute cloud，简称 EC2）系统是由推出Amazon的，为用户提供信息存储服务是该系统主要功能 ，所以说Amazon 是云计算服务商业化的先行者。云计算最为核心部分做简单的介绍：MapReduce[2]模型、Google File System[3]简称GFS和BigTable。通过Map及Reduce两个操作分布式，计算模型MapReduce[4]， 充分利用集群的效用最后进行分布式计算从而达到简化的目的。首先，分布式的文件系统Google File System将文件分为若干相等的块，再建立多个副本。BigTable。Hadoop是一种开源框架，作为GFS以及Google MapReduce的开源实现。可靠性上有一个好的业务调度流程算法显得至关重要。

2 调度算法

本节主要讨论的是资源提前取出的业务调度流程的算法，资源提前取出是为了解决以前的问题而被引入的。第一步：预先选出将要被候选的节点；第二步：非本地的以及待提前取出的map任务被预选出。第三步：资源提前取出被实现。非本地map任务在不用等待的情况下就可以被分配到存储有输入的数据的节点，这样就大大提升了数据的区域性。对比于Hadoop原生的三种作业调度算法，本文基于 Hadoop0.2版本，又重新改进了算法，从而实现了更好的数据区域性。

提前选出节点以及预先选出任务及提前取出资源是该算法的三大步骤。

2.1 提前选出节点

一般在 Hadoop 中，不会有这一步，Pull通信模型在JobTracker 与以TaskTracker 之间得到了采用。作业在执行时间上的减少，通过该算法来实现生成的。在这个策略的范围内，通过下面的方法可以调整运行之中的任务的数据的区域性：网络状况是处在运行的过程中的、和集群的负载动态，作业的运行时间实现了减少。不要对数据的区域性进行追求，而是要对整体性能在该算法中实现通盘的考虑。不足的是：在Hadoop平台上还不能实现该算法。算法实现的是预先提出节点，能射都是的节点的提前取出。

Pull通信模型被JobTracker到TaskTracker的传输中使用。在与TaskTracker 的通信上不会主动化。轮询实现了TT的预选。正好有空闲的节点被加入预选的队伍中，这时因为有空闲计的算槽（slots）的节点，第一种情况相对于第二种更简单。另一种是轮询到的没有空闲的计算槽（slots）的节点，需要判断节点。具有下面的判断条件：此节点的计算槽（slots）被释放的快慢，即计算槽（slots）中的任务正被执行的快慢性。最大概率释放忙碌槽（slots）的是当前任务中工作快的节点。

此算法主要的运算步骤如下：

第一步：执行中的任务还需要多少时间来执行完毕，这一问题TT（TaskTracker）给出了计算结果。

progressRate（T）=progress（T）/（currentTime-dispatchTime（T）） 任务在目前为止执行的进度是progress（T），并且系统当前的时间是currentTime ，同时调度任务T的时间是dispatchTime（T）。则可以一个任务的剩余时间被估算为 timeLeft。可以通过任务的进度增长率这一途径来计算剩余的所需时间。下面所示：

timeLeft=（1-progress（T））/progressRate（T））

第二步：此步骤实现的是一个数据块经过 Hadoop 在TT（TaskTracker）之间传输时一共花费的时间。通常的情况下，Hadoop有固定的文件块大小，大多数的情况下被设置为64M，在数据块间的数据传输，需要花费的时间被记为timePerBlock，下面所示：

timePerBlock=blockSize/tranRate

blockSize在一般的情况是64M，集群网络在理论上的传输速率是tranRate，一般是100Mbps。

第三步：进行了对比，实现了节点的选取。此节点被心跳信号轮询时，判断该节点上是否有此map 任务处在正在运行的任务中，该节点则会被加入预选的队列里，因为数据提前取出是在此任务完成之前进行的。当存在这样的任务节点，满足timePerBlock 小于timeLeft，则在candidateTTs的集合中加入了此计算节点，如果不满足，此次提前取出的操作被退出。

按照相差时间的多少对此队列进行由小到大的排序，这样做的目的是实现了从预选的队列中，来进行节点的预选。每隔一个心跳时段对已经排好序的队列进行一次更新，时间的有效性得到了提前选出节点的保证。

2.2 预选作业任务

候选的计算节点集合在上面得到了讲解，作业任务的提前取出在这一节中得到了介绍。需要被预期的数据块在map任务被选择之后才能确认。提前取出工作的成功完成是因为下面的条件决定的：每一个map 任务所处理的数据块不一样，因此首先要做的是预选出待提前取出的 map 任务。

第一步：执行中的任务还需要多少时间来执行完毕，这一问题TT（TaskTracker）给出了计算结果。

progressRate（T）=progress（T）/（currentTime-dispatchTime（T））

任務在目前为止执行的进度是progress（T），并且系统当前的时间是currentTime ，同时调度任务T的时间是dispatchTime（T）。则可以一个任务的剩余时间被估算为 timeLeft。可以通过任务的进度增长率这一途径来计算剩余的所需时间。下面（2）所示：

timeLeft=（1-progress（T））/progressRate（T））

第二步：此步骤实现的是一个数据块经过 Hadoop 在TT（TaskTracker）之间传输时一共花费的时间。通常的情况下，Hadoop有固定的文件块大小，大多数的情况下被设置为64M，在数据块间的数据传输，需要花费的时间被记为timePerBlock，下面所示：

timePerBlock=blockSize/tranRate blockSize在一般的情况是64M，集群网络在理论上的传输速率是tranRate，一般是100Mbps。

第三步：进行了对比，实现了节点的选取。此节点被心跳信号轮询时，判断该节点上是否有此map 任务处在正在运行的任务中，该节点则会被加入到预选的队列里，因为数据提前取出是任务完成之前进行的。当存在这样的任务节点，满足timePerBlock 小于timeLeft，则在candidateTTs的集合中加入了此计算节点提前取出的操作被退出。

第一步：提前取出候选的节点targetTT，最近得到更新的候选列表被读取到，排名靠前的TaskTracker得到了选取，任务的剩余的时间上是最小，并且在完成任务之前，计算节点的提前取出会有足够的时间来实现。

第二步：完成任务的选取。首先要选取失败的任务failedMaps，这个失败任务是从正在进行作业之中选择出来的。在作业的过程中，优先级最高的任务就是失败任务。当failedMaps 不为空时，对于失败次数最多的任务，是从列表中被选取的，相对于上一个步骤这个任务被选取出来的，筛选targetTT 的数据的区域性。整个的算法在任务为node-local时结束。此任务被加入到该任务中，是该任务不是node-local时进行的，记为toPrefetchMap。

第三步：当toPrefetchMap还处于空的状态时，任务的选择是按照选取出来的targetTT的数据的区域性实现的，整个算法的结束是在nonRunningCache存在node-local任务的条件下进行的。node-local 任务在nonRunningCache中不存在的话 ，toPrefetcheMap中加入了rack-local 的任务，是按照优先级进行选择的。完成了本次作业任务的选择，在该算法没有结束时，实现下一步的操作，即进行数据块间的资源的预选。

2.3 提前取出块间数据资源

数据块间资源的提前取出机制是这一节我们介绍的重点，从步骤一以及步骤二中分别选择出待提前取出的节点和任务，然后以待提前取出任务的元数据信息为依据把待提前取出map任务的数据块从待提前取出的节点 targetTT 上面提前取出出来。待提前取出资源所在的源节点可以根据待提前取出map任务元数据的信息以及固定的策略来确定：输入数据被分为了大小为64M的分片split，map任务和数据块是一一对应，每个数据块又和每个数据分片 split一一对应。一个数据块里面又包含了按照固定策略在机器节点上分布的3个副本。因此要提前取出资源的话首先要选取和targetTT 距离最为相近的机器上面的节点数据分片来进行提前取出。具体算法如下：

步骤1：源节点集合 sourceTTs的确定：把组成源节点集合的位置信息从 toPretchMap 中的 TaskInProgress 类之中读取出来，然后依据某些一定的策略选择某个适合源节点来进行提前取出操作。

步骤2：选择某一个源节点，这个源节点的集合中节点和targetTT之间的距离可以从Hadoop 集群中的网络拓扑的信息来获取，而这一网络拓扑信息可以从Hadoop集群中conf 目录之下的 topology.data 文件获得，之后选择和targetTT 最为相近的源节点作为sourceTT。targetTT和sourceTT这两个节点之间的距离可以有下述几种情况：两个节点位于同一节点，距离记为0；两个节点在同一机架上，距离为2；两个节点在相同的数据中心但在不同的机架上，距离记为4；最后一种是两个节点在不同数据中心之上，这种情况，距离就记为6。

步骤 3：把待提前取出map 任务的所需要数据从步骤 2 中选取的合适源节点 sourceTT上传送到targetTT 节点之上。

步骤 4：主节点元信息文件更新，map 任务中出现了空闲的计算槽（slots）时，给主节点发送“心跳”信息来要求新任务，就是toPrefetchMap。

3 总结

通过资源提前取出技术的引入很大改进了任务调度时的数据的区域性。此研究方法络资源，而且俭省经济负担，为用户提供了方便，从而在运算速度和存储功能上也得到了很好的提升。

参考文献：

[1] Amazon EC2[EB/OL].http：//aws.amazon.come/ec2， 2011.

[2] JEFFREY DEAN， SANJAY GHEMAWAT. MapReduce： simplified data processing on largec！usters[J]. Communications of the ACM， 2008，51（1）：107-113.

[3] Sanjay Ghemawat， Howard Gobioff， Shun-Tak Leung. The Google file system. In Proceedings ofthe nineteenth ACM symposium on Operating systems principles. New York： ACM， 2003：29-43.

[4] Fay Chang， Jeffrey Dean， Sanjay Ghemawat， et al. Bigtable： A Distributed Storage System forStructured Data[J]. ACM Transactions on Computer Systems， 2008，26（2）：1-26.

[5] 王凯，吴泉源，杨树强.一种多用户 MapReduce 集群的作业调度算法的设计与实现[J].计算机与现代化，2010：23-28.

[6] 罗国玮，兰瑞乐.基于云计算的高校科研实验平台构建研究[J].实验技术与管理.2012（4）. 115-117. [通联编辑： ]