基于MapReduce的并行数据流调度策略

葛茂松 王永利 张立铭 赵佳彬 于占龙 张国忠

摘要：本文提出一种基于MapReduce的并行数据流调度策略，包括作业性能估计策略和任务调度策略。通过对过去作业和任务信息的统计，对任务完成时间、所需资源和优先级进行估算，并以此对作业进行调度。经实验测试，利用该策略设计的算法可达到预期调度目标。

关键词：并行数据流;调度策略;作业性能

中图分类号： TP31        文献标识码：A

文章编号：1009-3044（2019）26-0011-02

开放科学（资源服务）标识码（OSID）：

MapReduce是用于大规模数据集的一种并行运算模型，可用于分布式查询、分布式排序、机器学习、文档聚类等等[1]。MapReduce调度算法分两部分：作业性能估计算法和任务调度算法。当用户提交一项作业时，作业会被分成多个任务，一个作业的任务将由作业调度功能将其分配到某个节点上完成，作业调度算法的主要任务就是选择一个合适的作业并将其分配到合适的节点上[2]。

2 作业性能估计策略

作业性能估计策略就是，统计出当前作业中的已完成任务所用的完成时间和任务数，再根据这些数据推测当前作业中的任务平均完成时间，然后推测出当前执行任务的剩余完成时间。当我们就完成对任务剩余时间的估算后，就可以利用该数据作为判断任务性能的依据，来确定任务的优先级，再进行后期的任务调度功能了。

设某一项正在运行的作业为m，已完成任务集合为[Cm]，作业m中的任务i的完成时间为[αmi]。我们可通过作业m中的已完成任务集合[Cm]来推测作业m中的任务平均完成时间，若设任务m的平均完成时间为[μm]，我们有公式1：

可看出，对于不同的任务执行器[TTt]，将会有相应的[μtm]。并且由于存在任务执行器之间的异构，一般情况下，[μtm≠μm]。但是，在本文的调度算法策略中，我们假设[μtm=μm]。因为，位于工作节点中的作业调度器，是通过从任务节点传来的心跳函数被触发执行的，任务节点的心跳函数包括一些当前状态信息，例如，目前空闲的执行单元数目等，工作节点中的作业调度器则需要根据心跳函数传来的状态信息，来完成它的调度工作。为了实现快速响应，我们尽量保持调度算法简单。所以，当假设[μtm=μm]时，只需根据所有正在运行的作业m的平均完成时间就可以估计资源分配情况，其复杂度为O（M）。但若把所有任务执行器[TTt]以及其平均任务完成时间[μtm]都考虑在内的话，算法的复杂度将会达到指数级别，无法保证作业调度器的快速响应。

另外，任务调度动态而高速的，因此，任务调度和任务完成时间的估算也会相隔很短时间就执行一次。即使将[μtm≠μm]的情况考虑在内，并以此得到更为精确的估算调度算法，其实，对于作业资源分配的影响也是很小的。

而且，作业m的完成时间估算只与那些分配到该作业m任务的任务执行器有关，在实际情况中，某作业执行过程中，只与MapReduce集群中的部分任务执行器相关，因此，没有必要获取所有任务执行器的平均任务完成时间[μtm]。

在调度算法执行过程中，对于任意一个属于作业m的正在执行的任务[tmi]，我们用公式2表示：

其中，只有任务的已运行时间[βmi]已知，任务完成时间[αmi]和任务剩余时间[δmi]均未知。我们假设任务[tmi]的完成时间等于任务平均完成时间，即[αmi=μm]，将其带入公式，我们可以得到公式3：

当我们完成了对任务[tmi]的剩余时间[δmi]的估算后，就可以以此作为判断任务性能的依据，来确定任务的优先级并对任务进行调度了。

3 任务调度策略

任务调度策略的主要思想是计算出作业的优先级，再根据作业的优先级进行调度。调度算法的思想是在作业服务器的工作节点中进行优先队列的维护，用户存储作业的ID、状态以及优先级。

3.1 维护优先队列思路

1） 当有作业提交时，将作业进队，作业状态为NODATA。

2）当任务服务器将作业状态发送给作业服务器JobTracker时，如果作业已经超过目标完成时间，将优先队列中该作业的状态改为UNDEAD;否则更新其估计的任务执行单元数目[smreq]，作业状态设置为ADJUST。

3）当有作业完成时，将该作业从优先队列中去除。

4） 调度器从优先队列队首取出作业，根据作业的状态分为UNDEAD、NODATA、ADJUST三种状态。

5） 如果作业状态为UNDEAD，取出队首中同样为UNDEAD的作业，分别给每个作业最大数目的任务执行单元。

6） 如果作业状态为NODATA，取出队首中同样为NODATA的作业，分别给每个作业最大数目的任务执行单元。

7） 如果作业状态为ADJUST，计算估计的任务执行单元数目，并分配给作业数目的任务执行单元。

3.2初始化优先队列的算法

4 估计完成时间准确率实验

在某RFID资产管理系统中，我们利用MapReduce模型对列存储中的RFID数据建立作业。实验记录了每次工作节点进行调度时估算的作业完成时间和实际的工作结束时间。我们将这两种数据进行对比，来验证此策略下估算的工作完成时间的准确率。实验结果如图1所示：

由图1可看出，在作业运行的前30%时间里，由于准实时调度器只收集到关于该作业的少量信息，估算出的作业完成时间与实际完成时间差距比较大。但当作业运行时间超过30%后，由于调度器获得了越来越多的信息数据，估算出的作业完成時间就在实际完成时间附近上下震荡，振幅越来越小，逐渐接近实际完成时间。

5 结论

在该策略中，调度器可通过记录的作业和任务的相关数据信息，对任务完成时间进行估算，再计算出当前作业所需资源数和相应的优先级，然后根据作业优先级对作业进行调度。实验结果表明，当本调度器获得了一定数量的信息后，估算出的作业完成时间基本接近实际完成时间。该策略基本达到了MapReduce调度的预期目标。

参考文献：

[1] 朱付保，白庆春，汤萌萌，等.基于MapReduce的数据流频繁项集挖掘算法[J].华中师范大学学报 （自然科学版） ，2017，51（4）：429-434.

[2] 富春岩，葛茂松，张立铭，等.一种准实时MapReduce调度算法的改进与实现[J].电脑知识与技术，2016（12）：3-4.

【通联编辑：梁书】