Page 131 - 《软件学报》2020年第10期

王康瑾 等:在离线混部作业调度与资源管理技术研究综述 3107

作业性能干扰最小的节点.本文总结了筛选节点的两种常用方法.
(1) 基于性能模型筛选节点.该方法首先对在线作业建立性能模型,进而使用性能干扰模型来预测混部后
作业所能达到的性能指标,通过搜索的方法寻找产生干扰较小的节点.例如:文献[14,34]在使用性能干
扰模型预测不同作业混部运行时的性能,以预测数据为依据判断该混部作业组合是否“安全”(“安全”
的混部组合是指混部组合中的每个作业都能达到其要求的性能指标);文献[28,39,40,45]使用协同过
滤模型预测一个作业与其他作业混部时所能达到的性能,进而使用贪心算法搜索作业的最佳运行位
置.使用预训练的性能干扰模型作为调度的依据取得了较好的效果,例如文献[14]在保证在线作业
QoS(quality of service)的情况下提升了 50%~90%的集群整体资源利用率;文献[39]可以保持 52%的作
业的 QoS 不被影响,而另外 33%的作业的 QoS 波动低于 10%.虽然可以有效地避免作业之间的性能干
扰,但是该方法依赖了预构建的性能模型,而获取性能干扰数据和构建性能模型所带来的开销是不可
忽略的问题;
(2) 基于空闲资源筛选节点.由于干扰和资源的相关性,空闲资源多的节点意味着该节点目前负载较少,因
而有可能承受更多的资源竞争.文献[46,47]通过预测未来一段时间集群的空闲资源数据,进而用于作
业调度;文献[48]提出一种作业偷取机制,当在线作业集群位于较低负载时可从待运行离线作业队列
中调度一部分作业至在线集群运行;文献[49]在调度时首先对作业的 CPU 和 I/O 资源需求进行聚类,
然后在作业间进行资源的匹配,进而完成调度.根据作业资源调度简单实用,因此适合在大规模混部系
统中使用 [9,50] .本文在第 2.2 节中指出,作业间的性能干扰还与作业本身资源的使用特征相关,因此仅考
虑将作业调度至空闲资源多的节点并不能完全保证该节点上在线作业的 QoS,因此仍存在一定的
风险.
在离线混部调度不仅要减少作业间的性能干扰,还要满足传统作业调度中存在的资源公平性、作业资源需
求、集群负载均衡、集群吞吐率等多个优化目标,为解决在离线混部作业调度面临的多目标优化问题,相关工
作中使用了 3 类算法.
(1) 启发式算法.基于专家直观经验构造算法用于寻找最优调度结果,启发式算法由于其简单直观,易于理
解和修改,被多种在离线混部作业调度算法所采用,如文献[34,39,40,48,49];文献[14]通过性能干扰模
型预测作业在每个机器上运行时产生的干扰,然后寻找干扰最小的节点作为作业的部署节点.文献
[52]将博弈论应用于在离线混部作业调度,使用 Shapley 算法寻找作业和节点之间稳定的婚姻匹配组
合(如果 A 喜欢 b 的程度比喜欢自己的配偶更高,并且 b 同样对 A 的喜好程度比自己的配偶更高,则他
们很可能组成新的家庭,这样的组合是不稳定婚姻,不存在不稳定婚姻的组合被称为稳定婚姻组合),
在保证作业性能的同时保证资源分配的公平性.启发式算法的局限性在于:(a) 当需要优化的目标较
多时,调度问题的复杂度上升,设计兼顾多个目标的启发式算法具有一定的难度;(b) 启发式算法难以
保证算法给出的解是全局最优解;
(2) 打分规则,当调度优化目标较多时,对每个目标设定量化规则,并使用这些规则对每个节点进行打分,将
最终的加权分数作为节点最终得分,最后将作业调度至得分最高的节点.常见的打分规则有:根据负载
打分,负载最低时节点得分为 10,满负载时得分为 0 等.节点的最终得分是所有规则的得分加权和,调度
算法选择得分最高的节点作为调度决策,基于打分规则的调度算法有文献[47,52].该方法的优点是易
于扩展(如果有新的优化目标只需添加新的打分规则即可),计算开销低,但其局限性在于:(a) 每个规
则的权重作为调度算法的超参数,对调度结果影响较大,寻找最佳的超参数设置需要经过不断的调
试;(b) 基于打分规则的调度算法同样难以保证算法给出的解是全局最优解;
(3) 整数线性规划.作业调度问题可以抽象为组合优化问题,而整数线性规划问题(integer linear program,
简称 ILP)作为组合优化的一种解决方法,可用于解决作业调度问题.文献[18]通过对减少亲和性违反、
最大化成功调度的作业数量、最小化资源碎片、集群负载均衡、最大化资源利用率等多种目标进行
量化后,并使用加权的方式将多个优化目标统一在一个全局目标函数中,使用 CPLEX 优化器求解.基