大规模集群长时间服务型作业调度

Scheduling of Long Running Applications

Posted by JetMuffin on October 15, 2018 | times

本文是结合工业界调度现状对 Eurosys’18 的文章 《MEDEA:Scheduling of Long Running Applications in Shared Production Clusters》的解读。

集群调度

集群调度主要是在分布式环境下,将各种类型作业(下文会提到具体类型)分发到集群各个机器节点上,并保证其运行的过程,相当于一个分布式系统的内核。

如下图所示,每个作业内部会有 intra-dependency,相互之间构成一个 DAG。DAG 会被交到一个集群范围的 Resource Manager(例如 YARN/Mesos/Kubernetes),由 Resource Manager 中的调度器负责根据一定的逻辑和策略将作业下发至集群各个节点进行运行。

cluster scheduling

在这个过程中,集群调度会关注以下几个核心的 Objectives:

  • Cluster Efficiency,也就是集群的效率。一般来说,集群的效率以集群的资源利用率来体现,而集群的资源利用率则又可以细分为集群资源的分配率集群资源的实际使用率。前者主要由调度算法解决,Tetris(SIGCOMM’14) 等文章从这个方面提升了集群效率;后者则与任务的实际运行时状况有关,同样有一些文章做了相关的优化,例如 Heracles(ISCA’15),Quasar(ASPLOS’14)。

  • Job Performance,及作业的运行性能。这里的性能一般针对短作业(batch job/one-off job),这些作业集群的使用者会更希望作业执行地更快一些。因此会关注作业平均完成时间或是作业总的调度完成时间。减少作业完成时间上,内核中的一些策略例如 SJF(Shortest Job First)等是在单机上的有效的方法,而在分布式环境,结合各种特定场景也有一些工作进行提升,例如 Carbyne(OSDI’16) 在大数据任务上的一些优化。

  • Fairness,公平性是相对比较新的一个概念,主要是在多租户情况下,对各个用户资源分配要求公平。典型的工作是 DRF(NSDI’11) 为了实现在多资源维度上的公平。

这三个指标相互之间都有一些 tradeoff,很难达到各个指标均最优的状况,集群调度只能在其中找到一个折中点。此外,可能还有一些其他特殊的指标。

Bin-packing

上面提到的解决集群资源分配率的问题,抽象出来实际上是解决装箱问题的过程。

bin packing

如上图所示,在实际的集群中,任务被封装在虚拟机或者容器中,限制它的最大可用资源,则可以作为一个小的箱子。而每台机器则可以作为一个大的箱子,装箱则是要把任务放置到机器上,使得总的碎片最小(或者让使用的机器数量最少)的一个过程。

装箱问题是个线性规划问题,我们可以简单的公式化如下:

这个问题本身是各个 NP-Hard 问题,解决这个问题有一些经典的算法,这里不再赘述。

作业类型

集群常见的作类型主要分为两大种,短作业和长作业。

短作业(batch analytics jobs),这种任务一般执行时间相对较短,执行完毕后结束。在大数据的场景下又可以细分为流处理任务(stream processing jobs),对应上层提交的框架可能为 kafka/flink/storm 等,这种任务对调度实时性要求很高,要求调度延迟小。另一种则为数据密集型任务(data-intensive jobs),典型的框架为 spark/mapreduce,这种任务对数据本地性(data locality)要求较高。

长作业(Latency-sensitive online applications)。相比于短作业,长作业往往对外提供服务,一旦执行,可能运行几个月乃至几年都不会停止。同时它对资源相对敏感,一旦资源有所冲突,反映到宏观上会导致 qps,响应时间等指标的下降。

此外,近期的文章还比较关注的是机器学习/深度学习的任务(deep learning training jobs),因为它相比前两种类型的任务更为特殊。

medea cluster workloads

根据 MEDEA 的文章介绍,Microsoft 不同集群的任务类型分布不同,某些集群专门会用来跑长任务 LRA。此外,在 Alibaba,由于主要的业务为电商,大部分的集群会跑 LRA(跑在 Sigma 上),而相对较少部分会跑 batch(跑在 Fuxi 上)。而另一家公司 Baidu 则是以 batch 居多,因为主要的业务是服务于搜索。

MEDEA

前面提了这么多背景,下面终于开始介绍 MEDEA 这篇文章了。文章着重提到了之前所有调度器基本没有考虑的三个关键点:AffinityAnti-AffinityCardinality

亲和性

Affinity 按照字面上的意思即为亲和性。在很多情况下,我们会考虑会把多个 LRA 跑在同一个节点上,或者跑在同一组特定节点上(例如同一个机房,同一个机柜等)。考虑亲和性主要为了减少网络传输开销,例如一个 “Web+Cache+DB” 结构的应用,在分布式的环境下,实际 Web Pod 的相应延迟需要考虑各个 Pod 间的网络传输,那么很显然把他们放到同一台机器上开销最小。Affinity 包括应用内亲和性 (intra-affinity) 和应用间亲和性(inter-affinity),两者主要的区别是描述 Affinity 时的单位是 App 还是 Pod。

Anti-Affinity 反亲和性和 Affinity 相反,则是描述哪些应用尽量不能调度到一台机器上。当某些消耗资源类似的应用(例如两个 IO 密集型应用)被调度到同一台机器,很有可能出现资源抢占(例如带宽抢占),那么反亲和性则是为了减少这些冲突。和亲和性相同,反亲和性也有应用间和应用内。

如果说 Affinity 和 Anti-Affinity 是两个极端,那么 Cardinality 则是描述两个状态的中间状态,用来说明两个应用被调度到同一台机器上时,每个应用最多可以放置多少个实例。很明显 Cardinality=INF 为 Affinity,Cardinality=0 为 Anti-Affinity。

为了量化新增的三个约束对调度带来的优势,作者做了三组验证下实验,分别的设置如下:

实验 实验设置 对照组
Affinity 5 storm supervisior + 1 memcached (i) no-constraints (ii) intra-only (iii) intra-inter
Anti-Affinity 6 YCSB workloads of Hbase (1 TB dataset) (i) no-contraints (ii) anti-affinitiy (iii) with cgroup isolations
Cardinality HBase profiling + Tensorflow profiling RegionServer(Worker) from full anti-affinity to full affinity

profiling

针对 Affinity,很明显发现加上了应用间(supervisor & memcached)和应用内(supervisors)的约束后,延迟分布明显优于另外两组对照;而 Anti-Affinity 上加了约束,会明显降低资源冲突而提高吞吐量。这里值得一提的是,作者还设置了一组 cgroup 的对照。在之前的调度器中(YARN/Mesos 等),往往用 Cgroup 限制了资源使用的 Quota 限制,然后再将各种不同类型的任务部到机器上。这些调度器默认认为 Cgroup 可以做到比较好的隔离性,但是从 MEDEA 的这组结果上看,即使加了 Cgroup 限制,在任务消耗资源类似且密集的场景下,依然会出现冲突。然而如果在调度层面用 Anti-Affinity 提前预防了这种场景出现,吞吐量提升效果甚至会比加了 Cgroup 的场景更好。而 Cardinality 反映出的结果是,对于类似 HBase 的查询任务或 TensorFlow 的训练任务,可以找到一个最优的 Cardinality 使得任务完成时间最短(Cardinality-Runtime 曲线是个凸函数)。在 TensorFlow 的场景中,同样在 Eurosys’18 的文章 Optimus 里得到了验证。

调度目标

那么既然有了新的三个约束后,我们就可以重新审视一个优秀的调度器的设计原则了,按照 MEDEA 的说法,它需要满足以下几个要求:

  • 可以表达出丰富的调度约束(可以支持 inter-/intra- 的亲和性反亲和性,以及 cardinality)
  • 需要从高层 API 显式支持约束(这点主要用来攻击例如 Mesos 的调度器,可以通过设置机器属性等方法隐式指定亲和约束,虽然可行但是不易用)
  • 可以得到更优的 Global Objective,包括:
    • 违反的约束最少(这里区别于之前提到的 Hard Constraints,存在约束可以不满足的调度情况)
    • 最小化资源碎片,也就是装箱更紧实
    • 节点负载更均衡,为了更适应峰值负载
    • 最小化使用的机器(其实也是优化装箱的一个目标)
  • 最后则是为了求解最优的 Global Objective 所需要的调度延迟更低。

scheduler

作者提出这些指标以后,就拿出现在最流行的几个开源/闭源的调度器来做比较了(这点有点像 Firmament 的作者的做法)。在亲和性上,以上调度器只有 Kubernetes 支持了,然而 Kubernetes 并不支持 Cardinality。而反观 MEDEA 支持了全部要求(日常吹自己的东西)。

约束描述

那么 MEDEA 是怎么在它的调度器上做亲和性约束描述的呢?MEDEA 首先允许上层对容器进行打标签(Container Tags:$\tau_n$):

上述标签表示 appID 为 0023 的应用的第 4 个实例,它是个 HBase 应用,且 role 为 HBase Master,并且这是个 Memory Critical 的应用。简单的讲就是用一组 Label 来描述容器的特点。

同时定义节点的标签(Node Tags:set of $\tau_n$)为节点上所有容器的 Container Tags 的并集,节点标签会随着容器启停动态变化。同时定义了每个标签 $\tau_n$ 的 Cardinality $\gamma_n:\tau_n \rightarrow N$,表示有某个标签的容器,在节点上最多放多少实例。例如一个节点 $n$ 上部署了一个 HBase Master 和一个 HBase RegionServer 实例,分别标签为 ${hb,hb_m}$ 和 ${hb,hb_rs}$,那么节点标签为 $\tau_n={hb,hb_m,hb_rs}$,同时定义 Cardinality $\gamma_n(hb_m)=\gamma_n(hb_rs)=1,\gamma(hb)=2$,表示该节点最多放 2 个 HBase 实例,且 Master 和 RegionServer 最多各一个。

此外,对于节点的集合(例如机柜,集群)的标签则同理由节点向上做并集。

有了标签的描述,MEDEA 用以下形式描述调度约束:

$\text{subject_tag}$ 是用于描述一个容器的标签集合,$\text{node_group}$ 是需要加约束的节点集合,而三元组 ${\text{c_tag},c_{min},c_{max}}$ 则表示 Cardinality 为 $c_{min} \leq \gamma_n(\text{c_tag}) \leq c_{max} $。给一个实际的例子:

上式表示 storm 的容器必须调度到一个至少有 HBase,且是 Memory Critical 的容器的节点上。如果我们要更严格的指定约束到一个实例,那么可以加上一些逻辑运算符例如合取($appId:0023 \land storm$)。同理更多复杂的约束可以用析取范式表示(这点当时介绍文章的时候被老板吐槽在软工方向用滥了的方法)。

既然把所有约束都形式化的表示出来了,那么我们就可以把最开始调到的装箱问题的优化式子更详细地写出来了:

其中第 2 行表示是否调度到节点上,第 3 行表示每个节点资源用量不超过资源上限,第 4 行表示总调度的实例数等于一个应用的实例数,第 5 行表示节点剩余资源约束,之后则表示新增的基于 tag 的亲和性约束描述。很明显这又是一个 NP-Hard 问题,文中提到 MEDEA 使用整数线性规划求解器进行求解。

实现与实验

implementation

MEDEA 实现在了 YARN 上,增加了 contraint manager(CM) 和 LRA scheduler 到 YARN 的 Resource Manager 上,CM 负责存储容器的 tag 以及约束的描述。而 LRA scheduler 在收到应用提交请求以后,会去调用求解器去求出一个最优防止,再将结果返回给 YARN 的 Application Master。

文章对比了 4 种调度器的性能:

  • MEDEA:使用文章中方法实现的调度器
  • J-KUBE:为了比较和 Kubernetes 的区别,作者实现了 Kubernetes 的调度机制(具体逻辑没提,应该是节点过滤及节点打分的一套方法,支持 (Anti-)Affinity)
  • J-KUBE++:在 J-KUBE 的基础上加入了 Cardinality 机制
  • YARN:纯 YARN 调度器

实验跑的任务包括 YCSB 的 Benchmark,TensorFlow 训练任务以及 Tez 的任务。下图为一些任务的运行时间情况,可以看出 MEDEA 的亲和性约束很好地减少了一部分的冲突,使任务 runtime 更短。

runtime

而在约束违反情况上,MEDEA 也是大幅领先。其中 MEDEA-ILP 是用求解器求的结果, MEDEA-NC 和 MEDEA-PT 分别是用两种启发式方法求的结果(NC 是先计算每个容器 可以调度的节点 Candidates 数量,优先调度可选 Candidates 少的容器;PT 则是对不同 tag 加了优先级)。

violate

文章的最后作者提了一下调度延迟问题,MEDEA-ILP 的调度延迟会随着节点数量规模增大而大幅度上涨,这也是因为 ILP 为了求一个最优解复杂度相对比较高。

总结与后话

MEDEA 的文章主要分析了实际生产环境所需要用到的亲和性约束(Affinity,Anti-Affinity,Cardinality),并做了 Profiling 实验确定了这些调度约束的影响大小。同时给出了增加亲和性约束后的线性规划公式,并在 YARN 上进行了拓展实现,相比 Kubernetes、YARN 等目前流行的调度器在解决任务冲突,提高任务运行速度上效果好了很多。

另外需要补充的是,笔者在 Sigma 团队实习的时候,这篇文章收到很多同时的推荐和认可。主要的原因是,在阿里这种体量的业务场景下,Sigma 内部的调度也特别看重亲和性这个问题,尤其在 Sigma 调度器上百分之九十以上跑的都是 LRA 的情况下,如何求解带亲和性的 LRA 调度也是 Sigma 一直在着力解决的点。

但是和 MEDEA 不同的是,MEDEA 对 Cardinality 的描述三元组 ${\text{c_tag},c_{min},c_{max}}$ 是容器相对节点可以允许的数量限制,而在阿里内部这个描述会更加复杂。首先会有类似 Cardinality 的 P,M,MP 资源定义应用的重要性,且它是相对节点的描述,即一个带 P tag 的容器最多在某个节点部署多少实例。同时还有应用之间的亲和性描述,可以用一个三元组 ${app_a,app_b,c}$ 表示应用 a 在部署有应用 b 的机器上,最多可以部署 c 个实例,而这个约束又是非对称的,${app_b,app_a,c’}$ 中 $c’ \neq c$。具体的描述可以参考 Sigma 举办的全球调度算法大赛(GSAC),使用的数据均为实际生产环境的 trace 经过脱敏处理得到的。

由此可见,工业界为了避免应用在运行时出现的资源冲突,考虑在调度层面进行先决避免,但这对调度增加了更多的复杂性。同时也在 GSAC 的比赛中看出,在阿里这种百万级 LRA 的场景下,如果使用求解器去求解这个优化问题,时间复杂度是爆炸的。因此从一个比较好的切入点去贪心,并求一个局部最优解才是最好的方法。

另外亲和性约束是开发者或集群管理者在任务上线时手动指定的,常常基于经验进行设置。而更准确的亲和性约束指定,需要对任务,程序,或是应用框架进行更深入的白盒分析,这应该也是近几年调度方向的研究工作主要侧重在特定领域任务调度上的优化的原因。

参考文献

  • Garefalakis P, Karanasos K, Pietzuch P R, et al. Medea: scheduling of long running applications in shared production clusters[C]//EuroSys. 2018: 4:1-4:13.
  • Peng Y, Bao Y, Chen Y, et al. Optimus: an efficient dynamic resource scheduler for deep learning clusters[C]//Proceedings of the Thirteenth EuroSys Conference. ACM, 2018: 3.
  • Grandl R, Chowdhury M, Akella A, et al. Altruistic Scheduling in Multi-Resource Clusters[C]//OSDI. 2016: 65-80.
  • Delimitrou C, Kozyrakis C. Quasar: resource-efficient and QoS-aware cluster management[J]. ACM SIGPLAN Notices, 2014, 49(4): 127-144.
  • Lo D, Cheng L, Govindaraju R, et al. Heracles: Improving resource efficiency at scale[C]//ACM SIGARCH Computer Architecture News. ACM, 2015, 43(3): 450-462.