大数据处理集群面向效用最大化的动态资源分配技术研究

王松云 李叶飞 陈国琳

摘 要：文章引入时间—效用函数表述任务完成时间与收益的关系，从而准确刻画不同类型大数据处理任务的需求。为最大化系统效用，设计了优先关系调度机制，确定资源分配。模拟实验表明，提出的优先关系调度机制比公平调度机制的效用提升超过50%。

关键词：大数据处理;时间-效用函数;资源分配

大数据处理已被广泛应用于各个领域，人们已为此开发多个框架来加速不同类型的数据处理应用。由于一个大数据处理集群往往运行多个不同类型数据处理任务，公平资源共享是大部分平台所采用的资源配置策略[1]。然而，不同类型任务对服务质量的需求是不同的，绝对公平并不总是终端用户和服务提供商的最佳选择。例如，实时数据流分析，需要快速完成任务;而综合决策系统，则主要关注系统吞吐量。

为了刻画不同类型任务对服务质量的不同要求，本文提出时间—效用函数（Time-Utility Function，TUF）[2]，每个任务均对应特定TUF，以表述不同完成时间对该任务效用的影响，由此区分不同类型作业的服务质量需求。同一类型的作业TUF走势类似，而不同类型作业会有较大不同。基于给定的TUF，集群资源分配的目标是使提交的作业的总收益最大化，从而总体上满足更多任务的服务质量要求。此前基于TUF的解决方案主要是针对具有相同作业优先级的单个调度序列而设计的，而实际在一个数据分析集群中会有多种任务，其TUF有显著区别。本文针对这一复杂任务调度问题，提出了一种基于优先关系的在线启发式算法来有效地实现任务调度。

1 问题描述

从数据处理的角度来看，大数据处理作业可以分为3类，即交互式、流式和批处理式。交互式作业通常有一个严格的截止时间，以保证用户体验，如果交互式作业的响应时间超过了截止时间，则用户体验会迅速下降。流式作业是实时作业，每一个时间窗口都有数据到达，若未在当前时间间隔结束前完成当前任务，可能会妨碍后续到来的工作。一般的大数据处理作业是批处理作业，通常需要相对长的时间（如数小时或数天）来获得最终结果，不设置硬截止时间。为了能够体现不同作业需求，本文设计了TUF。效用是指当作业完成时系统可以获得的收益或利润，其值Utility根据作业完成时间的不同而发生变化，是一个自变量为作业完成时间t的函数值。对于一个作业i，使用ti表示该作业的完成时间，该作业在ti时刻完成产生的效用是TUFi（ti），其中TUFi（·）表示作业i的时间效用函数。即：

2 基于优先关系的资源调度算法

我们的目的是得到一个多处理器的作业调度序列使得产生的总效用最大化，但这个问题是NP-hard问题[3]，因此，我们考虑能否找到一个具有最优解的某些性质的解。首先考虑只有一个处理节点的简单情况，我们将作业集合划分为若干子集，使得算法得到的调度序列最优解形式上均为依次调度T1T2…Tm这m个子集中的作业。因此，我们要设计一个产生某个序列的调度算法，满足以下目标：（1）算法序列应产生接近最佳值的值;（2）如果存在上述划分，算法序列应该与之相兼容。此时，算法序列在子集层面上与最优调度序列保持一致。

本文将提出一个实现了这两个目标的算法。算法的基本思想是，在每个选择步骤中，在所有剩余任务中选择在当前调度时刻是一个评估函数G（t，i）的值最大的任务。当评估函数G（t，i）满足特定条件时，算法序列也会有符合需求的特定性质。对于某个作业调度序列，若交换其中某两个相邻作业i和j的调度顺序后，产生的总效用降低，那么称i优先于j。将在时刻t作业i优先于的作业数记为P（t，i），当G（t，i）=P（t，i）时，算法序列σ将会是T1T2…Tm的顺序，即，算法序列σ将与最优分解相一致。

将上面的基于单处理器的算法思想拓展为支持多处理器的算法，即可得到求解原问题的优先关系调度算法（PR）：

算法：优先关系算法（PR）

While数据处理集群正在运行do：

if当前存在空闲处理器f且当前未被处理的作业的集合Tr不为空集do：

t=当前时间

s为当前时刻使函数P（t，s）取值最大，即优先于的作业数最多的作业

从未被调度的作业集合Tr中删掉作业s

将选中的作业s分配给空闲处理器f

if有新作业jn到达do：

将新到达的作业jn加入未被执行的作业集Tr中

3 性能评估

使用逻辑回归任务对交互式作业进行仿真，使用wordcount任务作为流式任务的仿真，使用pagerank任务对批处理任务进行仿真，分别采用本算法PR、先进先出算法（First Input First Output，FIFO）和最早截止时间优先算法（Earliest Deadline First，EDF）进行调度，比较仿真实验的结果。第一组实验比较的是这3种算法在不同的工作负载下的表现，实验结果如图2所示。在不同的工作负载条件下对3种算法的表现进行对比，结果显示，随着工作负载的提高，EDF算法和FIFO算法的性能显著下降，而PR算法产生的效用明显高于另外两个算法。在高工作负载下，PR算法产生的总效用比FIFO算法产生的总效用超出50%以上。

在高负载的工作条件下，大数据处理集群理应将更多的资源分配给交互式任务。第二组实验对比的是在高工作负载的条件下，3种算法对交互式作业的调度效果，实验按照1.4的平均负载提交交互式作业，分析比较3种算法在不同时刻对作业的完成率，实验结果如图3所示。该组实验结果表明，在3 s内，FIFO表现最差，EDF其次，PR表现相对最佳。3种算法都在大约1.2～2 s的时间段内完成大部分作业，而由于调度机制的原因，FIFO和EDF算法在此阶段丢失的作业更多，在3 s钟时，PR算法完成的作业数更高。

4 结语

由于大数据处理集群中的多租户和多框架，具有不同的QoS需求的多個类型的大数据处理任务同时运行。本文介绍了时间效用函数捕捉不同的作业类型的特征，并认为最大化活跃作业产生的总效用可以提高用户体验以及系统性能。不幸的是，这个最大化资源分配问题是NP-hard问题。然后，本文提出了一个在线启发式算法PR来实现它。PR基于时间效用函数，计算出任务之间的优先关系，生成的调度序列接近最优调度序列。仿真结果表明，我们的机制比FIFO公平调度有超出50%的改进，在产生较接近最优解的同时保持一定的效率，有效地弥补了现有调度机制在不同工作负载条件下无法灵活调度的弊端。

[参考文献]

[1]ZAHARIA M，BORTHAKUR D，SEN S J，et al.Delay scheduling： a simple technique for achieving locality and fairness in cluster scheduling[C].Paris：the 5th European Conference on Computer Systems，2010：265-278.

[2]LI P，WU H，RAVINDRAN B，et al.A utility accrual scheduling algorithm for real-time activities with mutual exclusion resource constraints[J].IEEE Transactions on Computers，2006（4）：454-469.

[3]CLARK R K.Scheduling dependent real-time activities[D].Pittsburgh：Carnegie Mellon University，1990.