本章是 The evolution of cluster scheduler architectures 文章的学习笔记。这篇文章讨论了这些年调度架构是如何发展的以及为什么会这样发展。
首先介绍一下这篇文章的作者：Malte Schwarzkopf，他目前在 MIT 的 PDOS实验室 作博士后，说起作者的这个名字可能有点陌生，但是提起 Google 的集群管理系统 Omega 应该很多人都知道，Omega 这篇文章，就是Malte 在谷歌实习时发表的。
在 2016 年他和 Ionel Gog 一起在 OSDI 上发表了一篇文章：《Firmament: fast, centralized cluster scheduling at scale》，这份工作也是和谷歌一起合作的，目前Kubernetes也开始拥抱这个工作。
这篇文章讨论了这些年调度架构是如何发展的以及为什么会这样发展。图一展示了集群调度的不同方法：其中灰色的方块对应一个机器，不同颜色的圆圈代表不同的任务，有“S”标志的圆角矩形代表调度器（这个图简化了一些，实际上，每台机器运行多个任务，许多调度器适合多个资源纬度的任务，而不是简单的slots），箭头代表调度器决定的作业放置位置，三种颜色代表不同的工作负载（如网站服务、批量分析和机器学习）。
3.1 中心化调度框架
许多集群调度框架，例如大量高性能计算（high-performance computing，HPC）调度器、 Borg 调度器、各种早期的Hadoop调度器和Kubernetes调度器都是中心化设计的调度框架。单一的调度进程在一台机器上运行（例如Hadoop V1的JobTracker、Kubernetes的kube-scheduler），调度器负责将任务指派给集群内的机器。在中心化调度框架下，所有的工作负载都是由一个调度器来处理，所有的作业都通过相同的调度逻辑来处理（如图）。这种架构很简单并且统一，在这个基础上发展出了许多复杂的调度器。比如Paragon调度器和Quasar调度器，它们使用机器学习的方法来避免负载之间因互相竞争资源而产生的干扰。
现在大部分的集群都运行着不同类型的应用（相反，如Hadoop MapReduce的早期作业）。然而，维护一个处理混合负载的单一调度器是一个很棘手的问题，原因如下：
- 希望调度器能区别处理长期运行的作业和批处理作业，这是一个合理的请求。
- 因为不同的应用有不同的需求，若要全部满足其需求则需要不断在调度器中增加特性，这样增加了它的逻辑复杂度和部署难度。
- 调度器处理作业的顺序变成了一个问题：队列效应（例如头阻塞：head-of-line blocking）和作业积压是一个问题，除非在设计调度器时非常小心。
总之，这些听起来是工程师的噩梦，调度器维护者会不断收到往调度器中添加特性要求的清单。
3.2 两级调度架构
两级调度框架通过将资源调度和作业调度分开的方式来解决这个问题。两级调度允许根据特定的应用来定做不同的作业调度逻辑，并同时保留了不同作业之间共享集群资源的特性。Mesos集群管理系统首先使用了两级调度的方法，Yarn则支持其有限的版本。在Mesos中，资源是主动被提供给应用层的调度器来使用的（调度器可以从下层提供的资源中进行选择），而Yarn则是由应用层来请求资源（并且接受被分配的资源）。如图所示，适用于特定负载的调度器（S0-S2）与资源管理器进行交互，资源管理器则为每个负载动态划分集群的资源。这是一个非常灵活的方式，它允许针对特定负载来自定义调度策略。
但是，两级调度框架也有一些问题。应用层调度器无法看到所有的资源，也就是说，它们没有全局视角，无法看到作业可以被放到哪些机器上执行。相反，它们只能看到资源管理器主动提供的资源（Mesos）或者资源管理器分配给应用（Yarn）的部分资源。这样的设计有几点缺点：
- 高优先级抢占（高优先级作业会踢走低优先级作业）会变得很难实现。在基于 offer 的模式下，被运行中作业所占用的资源对上层调度器是不可见的；在基于 request 的模式下，底层的资源管理器必须能理解抢占的策略（这可能与应用程序有关）。
- 调度器无法考虑到因其他运行的工作负载造成的干扰可能影响到资源的质量（比如“吵闹的邻居”占据了 I/O 带宽），因为调度器无法看到它们。
- 应用特定的调度器对底层资源的很多不同方面很关心，但是它们获得资源的唯一方法就是通过资源管理器提供的 offer/request 接口，这个接口很容易变得非常复杂。
3.3 共享状态调度架构
共享状态调度通过半分布式的模式来解决这个问题，在这种模式下应用层的每个调度器都拥有一份集群状态的副本，并且调度器会独立地对集群状态副本进行更新，如图所示。一旦本地的状态副本产生了变化，调度器会发布一个事务去更新整个集群的状态，有时候因另外一个调度器同时发布了一个冲突的事务时，事务更新有可能失败。
在共享状态调度的框架中，最著名的是Google的Omega、Microsoft的Apollo，以及Hashicorp的Nomad容器调度器。所有的这些都是使用一种方法实现共享状态调度，就是Omega中的“cell state”、Apollo的“resource monitor”以及Nomad中的“plan queue”。Apollo跟其他两个调度框架不同之处在于其共享状态是只读的，调度事务是直接提交到集群中的机器上，机器自己会检查冲突，来决定是接受还是拒绝这个变化，这使得Apollo即使在共享状态暂时不可用的情况下也可以执行。
逻辑上的共享状态调度架构也可以不通过将整个集群的状态分布在其他地方来实现，这种方式（有点像Apollo做的）中，每台机器维护其自己的状态并发送更新的请求到其他对该节点感兴趣的代理，比如调度器、设备健康监控器和资源监控系统等。每个物理设备的本地状态都成为了整个集群的共享状态的分片之一。
然而，共享状态调度架构也有一些缺点，它必须工作在有稳定信息的情况下（这点跟中心化调度器不同），在集群资源的竞争度很高的情况下有可能造成调度器的性能下降（尽管其他框架也有可能出现这种情况）。
3.4 全分布式架构
全分布式架构更加去中心化：调度器之间根本没有任何的协调，并且使用很多各自独立的调度器来处理不同的负载，如图所示。每个调度器都作用在自己本地（部分或者经常过时的）集群状态信息。在分布式调度架构下，作业可以提交给任意的调度器，并且每个调度器可以将作业发送到集群中任何的节点上执行。与两级调度调度框架不同的是，每个调度器并没有负责的分区，相反的是，全局调度和资源划分都是服从统计和随机分布的，与共享状态调度架构有些相似，但是没有中央控制。
尽管全分布式调度架构的概念（多个随机选择）是从1996年出现的，现代意义上的分布式调度应该是从Sparrow论文开始的。Sparrow论文的关键是它假设集群上任务周期都会变的越来越短，这点是以当时一个讨论作为支撑的：细粒度的任务有很多的优势。因此作者假设作业会变得越来越多，这意味着调度器必须支持更高决策的吞吐量，而单一的调度器并不能支持如此高的吞吐量（假设每秒有上百万个任务），因此Sparrow将这些负载分散到很多调度器上。
这个实现的意义重大：缺少中央控制在理论上很吸引人，并且非常合适某些负载，我们会在后面的连载中进行讨论。目前，我们注意到因为分布式调度器是不协调的，它相对于中心化调度、两级调度或共享状态调度拥有更简单的逻辑，例如：
- 分布式调度器是基于简单的“slot”概念，将每台机器分成n个标准的“slot”，并放置n个并行作业，这简化了任务的资源需求不统一的事实。
- 它使用了拥有简单服务规则的worker-side队列（例如，Sparrow中的FIFO规则），这样限制了调度器的灵活性，因为调度器只能选择将作业放置在哪台设备的队列上。
- 分布式调度器很难执行全局不变量（例如公平策略和严格的优先级优先），因为它没有中央控制。
- 因为分布式调度器是基于最少知识做出快速决策而设计，它无法支持或承担复杂或特定应用的调度策略，例如，避免任务之间的相互干扰对分布式调度来说很困难。
3.5 混合式调度架构
混合式调度架构是最近（学术界提出的）提出的解决方法，它的出现是为了解决全分布式架构的缺点，它结合了中心化调度和共享状态的设计。这种方式例如Tarcil、Mercury和Hawk一般有两条调度路径，一条是为部分负载设计的分布式调度（例如非常短的作业或者低优先级的批作业），另外一条是中心式作业调度来处理剩下的负载，如图1e所示。混合调度器的每个组成部分的行为与上述描述的部分架构相同。实际上，据我所知，目前还没有真正的混合调度器应用于生产环节当中。
3.6 小结
对不同调度器架构的相对优缺点的讨论并不只是学术探讨，尽管它自然围绕着研究论文。从工业界角度对于Borg、Mesos和Omega论文的深入讨论可以参见Andrew Wang的博文。此外，很多以上讨论的系统都已经部署到大型企业的生产系统中了（比如Microsoft的Apollo、Google的Borg、Apple的Mesos），反过来这些系统激励了其他可用于开源的项目。
如今，很多集群运行容器化的负载，因此有一系列基于容器的框架（Orchestration Frameworks）出现，它们与Google和其他称为“集群管理系统”的很相似。然而，很少有关于这些调度器的框架和设计原则的详细讨论，它们更多的是集中于面向用户调度的API（例如这篇Armand Grillet的报道，文中比较了Docker Swarm、Mesos/Marathon和Kubernetes的默认调度器），然而很多客户既不懂不同调度器的区别，也不知道哪个更适合自己的应用。
图2展示了一部分开源框架的概况，包括它们的结构和调度器所支持的功能。在图表的最底端，也包括Google和Microsoft没有开源的系统作为参考。资源粒度（Resource Granularity）这一列展示了调度器是分配作业给固定大小的slots，还是按照作业多维度的资源需求来分配的（例如CPU、内存、磁盘IO带宽、网络带宽等）。
决定使用哪个调度框架主要的一点就是看集群中是否运行一个异构（例如混合的）负载。例如一个前端服务（例如负载均衡或memcached）和批量数据分析作业（例如MapReduce或spark）相结合的生产环境，这种组合有利于提高系统的资源利用率，但是不同的应用对调度的需求有所不同。在作业混部的情况下，中心化调度可能导致任务的次优分配，因为不能基于单个应用进行逻辑的多样化处理，因此在这种情况下，两级调度和共享状态调度可能更加合适。
大多数面向用户服务的负载运行在资源能满足峰值需求的容器中，但是实际上这些资源都是过度分配的，在这种情况下，能有机会降低给低优先级负载过多分配资源（能继续保证负载的QoS）对提高集群的效率是非常关键的。尽管kubernetes拥有相对比较成熟的方案，Mesos是目前唯一支持这种过多分配资源的开源系统。我们期待未来在这个方面有更多的工作，因为根据Google的Borg集群来看很多集群的利用率依然低于60-70%。在后续的文章中，我们将关注资源预估、过度分配和有效提高机器的资源利用率。
最后，特定的分析和OLAP应用（例如Dremel或者SparkSQL Queries）会从全分布式调度器受益，然而，全分布式调度器（如Sparrow）有严格的功能设置，因此当集群的负载是同构（比如所有作业的运行时间是大概相同的）、配置时间短（也就是任务能被调度到长时间运行的worker上，例如MapReduce作业在YARN中运行）、任务通量高（大部分调度的决定必须能在短时间内做出）时非常合适。我们将在接下来的文章中讨论这些条件，并且讨论为什么全分布式调度器和混合式调度器中的分布式组件只对这些应用有效。现在，我们可以证明分布式调度比其他调度框架更加简单，但是不支持多维度的资源、过度分配和重新调度。
总之，图2中的表格表明对于开源的调度框架依旧有一段路要走，直到它们能匹配一些高级的配置。可以从以下几个方面来采取行动：功能缺失、资源利用率低、作业的性能不可测和“吵闹的邻居”降低效率，并且需要将elaborate hacks加入到调度器中来支持用户的需要。
然而，这里有一些好消息：尽管今天还有很多集群仍然使用中心化调度，但是大部分已经开始迁移到更灵活的设计中。Kubernetes今天已经可以支持调度器插件（kube-scheduler pod可以被其他兼容调度pod的API所替代），更多调度器从1.2版本开始支持“扩展器”来提供定制化策略。据我了解，Docker Swarm在未来可能也会支持调度器插件。
附录：参考资料
集群调度框架的架构演进过程
