一种优化的并行数据流调度算法

葛茂松 富春岩 支援 李微娜 周虹

摘要：很多需要对数据流进行实时处理、快速响应。本文对已有的MapReduce调度器进行了分析，结合它们的优缺点，对MapReduce调度算法进行了优化。实验表明，该优化算法可进行精准的估算，运行效率较高。

关键词：数据流;调度算法;优化查询

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

文章编号：1009-3044（2019）22-0003-02

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

1 引言

目前，在电力、电信、金融、网络安全等很多领域，都需要对数据流进行在线实时处理。数据流无须存储，而需要通过数据流查询被及时、快速地处理。为了应对不断增大的数据流规模，出现了分布式数据流处理技术，根据数据流速率的变化可动态调整数据流查询所需的计算资源。

MapReduce是一个用于大规模数据集的并行运算模型，广泛地应用在分布式查询、分布式排序、web访问日志分析、机器学习等方面。它有FIFO、Capacity Scheduler和Fair Scheduler三种调度器，这三种调度器它们有各自的优点。但是，共同的缺点是：在作业提交前，要求对系统的参数进行预设。也就是说，一旦作业提交预先设定完成，MapReduce系统给每一个任务的资源分配策略就已经确定，再无法根据实际情况进行动态的调整，更不要说自适应的调整。因此，本文对MapReduce调度算法进行了优化，改进后的算法能够基于正在进行的任务的进度对任务完成的时间进行预估，这样就可以根据每个任务进行的情况，自适应地动态的分配资源，从而提高系统资源的利用率。

2 相关定义

为了准确描述优化的MapReduce调度算法，本文有如下定义，见表1。

其中，作业m中第i项任务的任务完成时间由任务已运行时间和任务剩余时间两部分组成，因此有，[αmi=βmi+δmi]，作业集合[tmi]由[Cm]、[Um]和[Rm]三部分组成。

3 任务调度策略

任务调度策略就是要根据作业性能估算后得到的任务平均完成时间，通过相应的公式推导出当前作业所需的任务执行单元的数量，通过这个数量来确定当前作业的优先级。调度器将根据所确定的优先级分配相适应的合理资源。该任务调度策略由给作业分配合适的优先级和分配算法两部分组成。

3.1 作业的优先级

在MapReudce中，正在运行的某作业，需要进行调度时，调度器会根据任务调度策略给其分配合适数量的任务执行单元。

因为要根据在规定时间内完成作业所需要分配的执行单元数而算出来的作业的优先级，因此，需要估算出某项作业m中，正在执行的任务数和尚未执行的任务数。如果，每个任务执行单元需要花费[μm]时间，我们可对作业m当前所需任务执行单元数[smreq]进行估算，见如下公式：

其中，[Tmgoal]为目标完成时间，[Tcurr]为当前时间。

计算后，调度器将依据得到的[smreq]值作为作业m的权重，将当前作业集合放于优先队列中。

但是，由于任务调度策略是依据以往的任务运行情况对任务完成时间进行估算的，因此，在一些特殊情况下，任务调度策略无法准确地进行估算。例如，一些已超过目标完成时间的作业，优先级会被赋予的较高，使其尽快得到资源完成任务。另外，作业刚提交的时，调度器还未收集到信息，无法估算作业最终完成时间，也就无法计算出所需任务执行单元数[smreq]。这种情况下的作业将获得较高的优先级，以方便调度器尽快调度该任务。

因此，调度器要通过以下几个因素对任务的优先级进行整体的评估计算：第一，判断作业是否已超过目标完成时间;第二，看调度器是否收集了作业的状态信息;第三，估算出的任务执行单元数目。

任务调度策略中规定调度器分配资源的顺序为：已经超过目标完成时间的作业、未被调度器收集到信息的作业、所需任务执行单元数较大的作业。

3.2 优化的调度算法

确定了优先级之后就要确定基于作业的优先级的分配算法。调度算法主要完成在作业服务器中维护优先队列的功能。优化后的调度算法定义了三个函数，分别是初始化函数、添加作业到优先队列函数和调度优先队列已有作业函数。

初始化作业优先队列函数的主要功能是创建一个优先队列。其中队列的元素为Job类型，包含作业的Id、作业的状态和当前任务执行单元数等。作业又包括UDEAD、NODATA、ADJUST这3种状态。

用户在提交新的作业时，开始调用添加作业到优先队列函数，这个函数的功能是将新作业加入到优先队列中去。输入参数为Job类型，Job类型参数的初始状态为NODATA，伪代码如下：

当工作服务器收到来自作业服务器的信息时，将执行调度优先队列中已有作业函数。在函数中，先遍历作业服务器中返回的任务列表，如果该任务已在优先队列中，就更新作业优先队列中相关信息。若该任务不在优先队列中，就将该任务所属作业加入优先队列中。然后，再按照作业的优先级依次地取出作业，进行相应操作。若该作业状态是UNDEAD状态或NODATA状态，那么，说明该作业已超出了作业的目标完成时间;或者此作業处于刚刚提交状态，无信息可循，那么，将给该作业分配最大任务执行器数目maxSlot;若作业当前处于ADJUST状态，就依据公式1进行计算，得出作业所需任务执行单元数，并进行分配。

4 结论

本文对MapReduce调度算法中的任务调度策略进行了优化。调度器可根据记录的作业及任务信息数据，估算出任务完成时间。优化后的算法可计算出当前作业所需资源，并给出当前作业对应的优先级，形成优先队列。

通过模拟真实场景下多个作业提交的情况，对算法进行了实验验证，作业运行的前30%时间里，因为收集到的关于该作业的信息数据少，所以估算的完成时间与实际作业的完成时间差距较大。但在作业运行了30%的时间以后，由于调度器收集到了足够的关于该作业的信息数据，估算的完成时间与实际完成时间基本相符。

在实验过程中，初始的几次实验运行时间较长，但实验次数增加后，调度器收集到的信息数据量足够大之后，就可以对作业的完成时间做出比较精准的估算，分配给作业的任务执行单元数也更为合适，运行效率较高。

参考文献：

[1] Bonnet P， Gehrke JE， Seshadri P. Towards sensor database systems[C]//Tan K-L， Franklin MJ， Lui JCS， eds. Proceedings of the 2nd International Conference on Mobile Data Management. Hong Kong： Springer-Verlag， 2010. 3-14.

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

【通联编辑：梁书】