Page 318 - 《软件学报》2020年第12期

3984 Journal of Software 软件学报 Vol.31, No.12, December 2020

[8]
与实际使用量之间存在差异,这一定程度上限制了集群资源利用率 .
Mesos [24] 是由加州大学伯克利分校提出的支持多种应用的资源管理平台,它采用基于资源邀约的机制,允
许应用框架决定自身的资源使用量.然而通常情况下,应用编程框架很难清楚地知道每个任务的资源需求情况.
因此,资源邀约机制与资源请求的机制有着相似的问题.本文提出的方法分阶段精细匹配资源需求与分配量,该
方法可以在上述任意平台中实现,用于改变资源调度粒度,减少资源碎片,避免过度分配等问题.
[3]
云计算资源管理和作业调度算法相关的研究有很多,但是各研究的侧重点有很大差异.Capacity 由 Yahoo
公司开发的调度器,它以队列为单位划分资源,以实现多用户高效共享集群计算资源.Tetris [13] 针对负载多维需
求引发的资源碎片和过度分配问题,分析历史执行信息获取作业资源需求,将调度问题抽象为多维背包问题,以
提高集群的资源利用率.Tetris 假定任务的资源需求是恒定的,而细粒度匹配方法分阶段匹配,且在匹配过程中
考虑了资源特性,因此可以进一步提高集群资源利用率.
[5]
Delay 提出将任务调度到数据所在服务器进行计算,以避免数据网络传输消耗的时间并提高性能.
Quincy [25] 是微软公司提出的高效灵活的分布式作业调度框架,它将调度问题映射为有向无环图,将数据本地
性、公平性等信息编码成边的权值,并在调度中使用最小流选择代价最小的任务进行调度.当集群规模巨大
时,Quincy 的调度延迟会大幅增加.Firmament [26] 采用近似、增量流等多种方式对 Quincy 进行了最小流优化,解
决了 Quincy 调度的扩展性问题.Delay,Quincy 和 Firmament 非常关注数据本地性,本文细粒度调度中使用了与
Delay 相同数据本地性机制.但是,上述调度器在资源分配时并没有改变资源分配的粒度,而本文关注资源分配
的粒度,细粒度匹配方法也可以应用在上述调度器的资源匹配中,以提高资源分配的粒度.
[6]
LATE 与 Mantri [27] 通过重新启动任务等方式解决个别落后任务阻碍作业完成的问题.本文调度器中并没
有集中式的推测执行机制,而将推测执行策略交由各应用负责.
Apollo [11] 是微软公司提出的高度可扩展的协同调度框架,它根据相似任务推测任务的完成时间,并以此为
依据构建资源可用性表,最终使用资源可用性表分布式的做出调度决策.Omega [12] 是谷歌公司提出的基于乐观
锁 [28] 的共享状态调度器,它可以大幅提高调度决策的并发度.Apollo 和 Omega 可以提高决策质量和调度的可扩
展性,但是分布式调度决策对公平性保证是一个挑战.
[4]
Fair 公平调度算法解决了多用户集群中计算资源共享的公平性问题,它通过限定用户或作业队列的最小
份额和公平份额,避免作业饥饿.DRF [21] 提出了多种类型资源下的公平策略,进一步提高了用户间的公平性.
Choosy [29] 扩展了最大最小公平算法,在具有调度约束条件的情况下实现公平性.Carbyne [22] 放弃了瞬时公平性
而只保持长时间总体公平,它将资源碎片优先分配给快完成的作业,提高资源使用效率及性能.细粒度调度器与
Carbyne 的目的相似,均是为了提高集群资源利用率和整体性能.但是本文中没有提出新的公平策略,仅使用
DRF 作为默认公平策略.它仅通过提高资源分配粒度,并在分配中考虑资源特征压缩资源需求等方式提高资源
利用率.此外,细粒度调度器为各种资源公平行策略的实现和应用提供了扩展支持,放弃瞬时公平性的策略可以
在 FGM 中实现,达到共同优化.
本文研究侧重于以更细的粒度匹配资源的供应与需求,并在必要时,根据资源特性压缩资源需求,以提高资
源利用率和负载性能.因此,本文提出的方法与上述很多方法无互斥关系,多种方式可以协同工作,做出更优异
的资源管理和作业调度决策.例如,文献[30]提出一种具有启动时间感知的虚拟机分配策略及一种粗粒度资源
调度算法,在任务时效性和节能之间进行权衡.如果该文献采用本文的细粒度资源匹配方式,则可以提高资源供
需匹配程度并增加虚拟机并行数量,进一步提高资源使用效率和任务时效性.
任务资源需求及其他信息的量化主要有两种思路:使用历史信息推测 [13,31−36] 和利用相似任务推测 [11,37−39] .
两种方式均可以达到推测资源需求的目的,本文采用相似任务推测相关信息.相比已有的研究工作,本文使用的
推测方法有以下不同:首先,本文推测时使用迭代更新的方式,减轻数据抖动的影响,使推测曲线平滑;第二,细粒
度匹配中,通过压缩资源需求进一步提升资源利用率,这造成了运行时信息的准确性发生改变,本文推测中,根
据资源需求压缩情况动态调整迭代更新的权重,保证推测准确性.