原文地址：http://www.firmament.io/blog/scheduler-architectures.html
集群调度器是现代基础设施很重要的组件，尤其在最近几年有很大发展。架构从单体应用的设计进化成更灵活，分散的，分布式的设计。但是，目前很多开源能提供的还是单体应用或缺了关键特性。这些特性对于真实世界的用户很重要，因为他们需要很高的使用率。
这是我们发布的第一篇关于在大集群上进行任务调度的系列文章，那些在亚马逊，谷歌，facebook，微软或雅虎实际在使用的。调度是一个重要的话题，因为它直接影响操作集群的成本：一个差调度器会导致极低的使用率，让昂贵的机器空闲，导致浪费钱。高使用率，对于集群自己并不容易：除非仔细的决策，负载之间会互相影响。
架构进化
这篇文章主要讨论调度架构在近些年是如何进化的，以及这为什么发生。图一将这些不同的方式可视化：灰色的方块代表一个机器，圆圈代表一个任务，一个里面标着S的团员性代表一个调度器。箭头表示调度器做的决策，三种颜色代表不同类型的负载（例如，web服务，批量分析，机器学习）。
许多集群调度器 - 例如高性能计算（HPC）调度器，Borg调度器，早期Hadoop调度器和Kubernetes调度器 - 都是单体的。一个单例的调度进程泡在一个机器上（例如，Hadoop第一版的JobTracker，Kubernetes的kube-scheduler）并且给机器调度任务。所有的负载被同一个调度器来处理，所有的任务跑着相同的调度逻辑（图1a）。这样简单并统一，却导致了越来越复杂的调度器。举个例子，可以看看Paragon和Quasar调度器，使用了机器学习的方式来避免在资源上相互冲突的负载调度。
在今天很多集群运行很多不同类型的应用（在早期只有Hadoop MapReduce任务在运行）。因此维护单个的调度器实现处理混合型的负载很需要技巧，原因如下：
- 很明显我们期望一个调度器按不同的方式来处理长周期服务型任务和批量分析型任务。
- 不同的应用有不同的需求，要支持他们所有的需求需要给调度器添加许多特性，增加了逻辑和实现的复杂性。
- 调度器处理任务的顺序成了问题：队列效应（队列头部阻塞 head-of-line blocking）与积压问题需要小心地设计调度器。
综上所述，这听起来是一个工程上的噩梦 - 调度器的开发者会收到无穷无尽的特性需求。
二级调度架构 通过隔离资源获取与任务来解决这个问题。这样任务调度逻辑可以针对特定的应用，这也可以保持在集群间共享的能力。Mesos的集群管理在这方面是先驱， 同时YARN支持一部分功能。在Mesos，资源是应用级别调度器提供的（被挑选和选中），而YARN允许应用级别调度器请求资源（在返回中得到配额）。 图1b展示了基本思想：负责负载的调度器（S0-S2）与资源管理器进行交互，资源管理器为集群资源的每个负载刻画出动态分区。这种方式可以支持定制化，针对负载的调度策略。
现在，分离了关注点的两级架构带来了一些缺点：应用级调度器丢掉了一些知识，例如，他们看不到所有可能的资源点，他们基本看不到这些与资源管理器组件提供的资源获取（Mesos）或分配（YARN）相关的选项。这有一些缺点：
- 优先级抢占（高优先级任务踢掉低优先级的）的实现变得困难了：在一个基于提供的模型里，运行任务的资源对于上一级的调度器是不可见的；在一个基于请求的模型里，低级别的资源管理器必须理解抢占策略（很可能与应用相关）。
- 调度器不能从负载运行中来考虑降级资源（例如，“吵闹的邻居”抢占了IO资源），因为他们看不到他。
- 应用级调度关心下游资源的许多不同方面，但他们只有资源管理器的提供/请求接口。这个接口很容易变得很复杂。
共享状态架构 将这个问题转化成分布式模型，多个集群状态的副本会被应用级调度器独自更新，就像图1c展示的。在本地更改后，调度器发起一个乐观更新事物去更新共享的集群状态。这个事务可能会失败，很明显：一个其他的调度器可能同一时间也在做一个冲突的变动。
最知名的使用共享状态的设计就是Google的 Omega，和微软的Apollo,还有Hashicorp的Nomad容器调度器。以上豆浆共享集群状态是现在一个单点位置：Omega的“cell state”，Apollo的“resource monitor”，Nomad的“plan queue”。Apollo与其他两个不同的是它的共享状态是只读的，调度事务直接提交给集群机器。机器自己检查冲突并选择接受或拒绝变动。这让Apollo可以在共享状态暂时不可用时进行调度。
一个“逻辑”共享状态设计可以归档同时不需要实现整个的集群状态。这种方式（类似Apollo做的），每个机器维护它们自己的状态并且将更新发送给不同的agent，如调度器，机器健康监控，资源监控系统。每个机器自己的本地状态的视图现在组成了一个全局共享状态的分片。
当然，共享状态架构也有一些缺点：他们必须与状态信息一起工作（不像中心式调度器），也会遇到高层争抢时降级调度性能（尽管其他架构也会遇到）。
全分布式架构 将分化做的更彻底，调度器间没有任何协调，并且使用许多独立的调度器来处理进入的负载，就像图 1d里面展示的。每个调度器只与他们的本地数据，通常是集群的过期数据工作。任务可以提交给任何调度器，每个调度器又会将任务放置在集群的任何位置。不像两层调度器，调度器不对隔离负责。相反，全局调度器和资源分区是在统计了多样与随机性的负载造成的结果后做的决策 - 类似于共享状态调度器，只是没有中央控制。
最近的分布式调度器运动应该是起始于Sparrow(http://dl.acm.org/citation.cfm?id=2522716)的论文，虽然底层的概念（多样随机性选择）第一次出现实在1996年。Sparrow的关键前提是假设我们在集群中运行的任务会变得更短，基于一个争论(http://dl.acm.org/citation.cfm?id=2490497)，即细粒度的任务有更更多的好处。作者假设任务会变得越来越多，意味着调度器应该支持一种更高层的吞吐量。由于一个单一的调度器可能无法保持这样的吞吐（假设每秒有100W的任务！），Sparrow将负载转移到许多的调度器上。
这很有意义：中央控制的缺乏可以变成一个很好的特性 ，它对一些负载适配的很好 - 在未来更多。 由于分布式调度器不需要互相协调，他们可以做到比高级单体，2层，或者共享状态调度器的逻辑更简单。例如：
- 分布式调度器可以基于一个简单的“槽”概念，将每个机器划分成n个标准的槽，对应n个并行的任务。这样简化了任务需要的资源不是统一的。
- 在worker端也使用了队列作为简单的服务逻辑（如，Sparrow的FIFO），保证调度有弹性，调度器可以仅仅选择在哪台机器上做任务的入队操作。
- 分布式调度器很难进行一个全局调度（如：公平策略或严格的优先级控制），因为没有中央控制。
- 由于它们都被设计为在只有很少知识时进行快速决策，分布式调度器不能支持复杂或定制应用策略。避免干涉任务，例如，用一些后门手段。
混合架构 是最近出现的致力于通过组合单体或共享态的设计来解决全分布架构的缺点。一般这样做是ok的 - 比如，在Tarcil（http://dl.acm.org/citation.cfm?id=2806779 ）, Mercury（https://www.usenix.org/conference/atc15/technical-session/presentation/karanasos ）, 和Hawk（https://www.usenix.org/conference/atc15/technical-session/presentation/delgado ） - 有两种调度路径： 一个分布式的来处理负载（如，很短的的任务，或低优先级的批处理任务）， 另一个中心式的来处理其他任务。图1e展示了这种设计。每一个混合调度器的行为都与以上架构描述的部分相同。在实际的实践中，目前据我所知还没有混合调度器在生产环境中部署。
在实践中意味着什么？
以上讨论的不同的调度架构并不只是一个学术课题，尽管他们确实在研究论文出现。作为一个关于Borg，Mesos和Omega论文从工业界角度的扩展的讨论，可以看看Andrew Wang的精彩博文(http://umbrant.com/blog/2015/mesos_omega_borg_survey.html )。此外，很多系统的讨论都部署在大型企业(微软的Apollo，Google的Borg，Apple的Mesos)的生产环境设定，并且他们启发了其他可用的开源项目。
最近，许多集群开始运行容器，所以很多关注容器的“编排框架”出现了。这些跟Google和其他公司称为“集群管理器”很像。不管怎样，一些关于调度器讨论的细节已经融入了这些框架和他们的设计规范，一般他们的关注点都是在面向用户的调度API(由Armand Grillet报道 http://armand.gr/static/files/htise.pdf ，其对比了Docker Swarm，Mesos/Marathon, Kubernetes default scheduler)。此外，很多用户并不知道调度器架构之间的差异，也不知道哪一个架构适合他们的应用。
图2 展示了开源编排框架的概要，他们的调度器的架构和支持的特性。在表格底部，我们也加入了Google和微软的闭源系统。资源粒度列指出了调度器分配任务到一个固定尺寸的slot，还是会根据多个维度（CPU,内存，磁盘I/O贷款，网络带宽等）来分配资源。
一个决定合适调度架构的关键点就是你的集群是否运行了混合的负载。这种case，举例来说，就是当既有在线服务(原文：front-end services) （web负载均衡服务与memcached）和批处理数据分析（MapReduce或Spark）的情况。为了提高使用率这种类型很有意义，但不同的应用有不同的调度需求。在一个混合式的设定中，单体调度器只能得到次优解，因为单一逻辑不能以每个应用为基础进行调整，双层或共享态调度器可以提供更好的收益。
大多数面向用户的在线业务负载设计为将所有资源用来服务每个容器的峰值需求，但这样会导致他们的使用率低于分配到的资源。这样的情况下，用低优先级的负载任务（保证QoS）来优化被过度订阅的资源成为优化有效集群的关键。Mesos是目前唯一支持过度订阅的开源系统，Kubernetes有一个提案（http://kubernetes.io/v1.1/docs/proposals/resource-qos.html ）来加入这个特性。我们期望未来这块领域会有更多的活动，因为目前很多集群的使用率实际上低于Google Borg集群报道（http://dl.acm.org/citation.cfm?id=2741964 ）的60-70%。我们会继续在今后发布关于容量规划，过度订阅，高效机器使用率的内容。
最后，特定的分析和OLAP类型的应用（如，Dremel或SparkSQL查询）可以从全分布式调度器受益。但是，全分布式调度器（如Sparrow）有很严格的特性集限制，它在任务负载都是同一个类型时有很好的性能（如，所有的任务大约在同一个时间段运行），set-up times are low（如，任务被调度到长时间运行的worker， 像YARN中的MapReduce应用级别任务），任务会大量产生（如，许多调度判断会在很短时间产生）。我们会在这个系列的下一个博文更细的讨论下为何全分布式调度器- 混合调度器的分布式组件只在这些应用中有意义。现在，分布式调度器比其他调度器更简单，不支持多资源维度，过度订阅，或重新调度。
大体上，图2证明了开源框架还有一段路要走，直到它们可以支持闭源系统的以上高级特性，这是行动的召唤：由于缺失的特性，糟糕的使用率，不可靠的任务性能，吵杂的邻居导致被半夜叫醒，为一些用户需求定制的黑科技。
不过，还是有一些好消息：今天很多框架还是单体调度器，他们开始向更弹性的设计变化。 Kubernetes已经开始支持插件化调度器（kube-调度器 pod可以被另一个API兼容的调度器pod替代），很多从V1.2后的调度器(https://github.com/kubernetes/kubernetes/blob/master/docs/proposals/multiple-schedulers.md )，开始支持自定义的策略（https://github.com/kubernetes/kubernetes/blob/master/docs/design/scheduler_extender.md ）。Docker Swarm可能-按我的理解-也会增加插件化调度器的支持。
