一种准实时MapReduce调度算法的改进与实现.docVIP

一种准实时MapReduce调度算法的改进与实现 　　摘要：该文通对MapReduce调度器中准实时调度算法的研究， 实现了在MapReduce调度器上能够依据正在进行的任务的进度，对任务的完成时间进行估计，在运行时给每个任务动态的分配资源。实验表明，本算法提高了MapReduce系统的资源利用率，达到了准实时MapReduce调度的预期目标。 　　关键词：MapReduce；调度策略；调度算法 　　中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）15-0003-02 　　1 引言 　　MapReduce是一个用于大规模数据集的并行运算模型. 广泛应用于分布式查询、分布式排序、Web访问日志分析、机器学习以及基于统计的机器翻译等领域[1]。MapReduce系统中现有的三种调度器：FIFO调度器、Capacity Scheduler调度器以及Fair Scheduler调度器[2]。目前这三种调度算法，在作业提交前，必须对系统的参数进行预先设定。而且，一旦作业提交，MapReduce系统给每一个任务的资源分配策略就已经确定下来，不能根据任务执行的实际情况进行动态的调整[3]。本文提出的算法使MapReduce调度器能够对正在进行的任务的进度及任务的完成时间进行估计，并在运行时给每个任务动态的分配资源，从而提高了MapReduce系统的资源利用率。 　　2 算法思想 　　准实时MapReduce调度算法主要由作业性能估计及任务调度策略两部分组成。 　　1）作业性能估计的主要思想是：通过作业m中，已完成任务集合的完成时间和任务数量的统计，推测作业m中的任务平均完成时间，并且以此推测正在执行任务的剩余完成时间。然后，准实时调度算法就可以以此作为判断任务性能的依据，确定任务的优先级并对任务进行调度。 　　2）任务调度策略的主要思想是：根据作业性能估计中得到的任务平均完成时间，通过公式推导，得出作业还需要的任务执行单元的数量，以此确定作业的优先级，调度器再根据作业的优先级，给不同的作业分配相应的资源。任务调度策略包括两部分：一是将合适的优先级赋给作业；二是基于作业优先级的分配算法。 　　3 准实时MapReduce调度器的核心类及主要功能 　　准实时MapReduce调度器的核心类由SoftRealTimeConfiguration类、Soft Real Time Operation In Progress Listener类、Soft Real Time Task Scheduler类、Soft Real Time Operation类、Operation Tracker类和Operation In Progress类等组成。准实时MapReduce调度器的核心类图如图1所示，核心类及主要功能如下： 　　1）SoftRealTimeConfiguration类继承自org.apache.hadoop.conf.Configuration类，功能是进行配置文件管理。在Hadoop MapReduce启动加载时，SoftRealTimeConfiguration会读取配置文件中的参数，并保存至相应的数据结构中。 　　2）Soft Real Time Operation In Progress Listener类该类继承自org. apache. hadoop. Map red. Operation In Progress Listener类，功能是当作业添加或者删除时，通知调度器。该类包含三个主要函数：operation Added、operation Removed以及operation Updated，功能是当有作业添加到作业队列，从作业队列删除；作业的状态有更新时，该类侦听到这些事件并且执行对应的函数。 　　3）Soft Real Time Task Scheduler类继承自org. apache. hadoop.mapreduce. server. operationtracker. Task Tracker类，实现核心调度算法。Soft Real Time Task Scheduler类除了包含init Schedule Queue，priority Op及add Operation To Queue三个主要函数以外，还包括assign Tasks和getOperations函数。assign Tasks函数的功能是用于返回正在某个Task Tracker上执行的任务集合；getOperations函数的功能是通过作业队列的名称返回该队列中的作业。 　　4）Soft Real Time Operation类记录作业的状态和估计作业完成时间，并以此为依据比较正