案例2: Mesos

Mesos 是和 YARN 几乎同一时间发展起来的任务和资源调度系统。这一调度系统实现了完整的资源调度功能，并使用 Linux Container 技术对资源的使用进行限制。和 YARN 一样，Mesos 系统也包括一个独立的 Mesos Master 和运行在每个节点上的 Mesos Agent，而后者会管理节点上的资源和任务并将状态同步给 Master。在 Mesos 里，任务运行在 Executor 里。下图是 Mesos 的主要架构：

Mesos Scheduler

值得注意的是，Mesos 分区的单位并不是单个节点，是可以将一个节点当中的资源划分到多个区的。也就是说，在 Mesos 里，分区是逻辑的、动态的。

把 Mesos 看作一种双层的资源调度系统设计主要基于以下几点：

与一般通过 Master 请求资源不同，Mesos提出了Framework的概念，每个 Framework 相当于一个独立的调度器，可以实现自己的调度策略；
Master 掌握对整个集群资源的的状态，通过 Offer (而不是被动请求) 的方式通知每个 Framework 可用的资源有哪些；
Framework 根据自己的需求决定要不要占有 Master Offer 的资源，如果占有了资源，这些资源接下来将完全由 Framework 管理；
Framework 通过灵活分配自己占有的资源调度任务并执行，并不需要通过 Master 完成这一任务。

同样，Mesos 也可以通过 Stand-By Master 的方法提供 Master 节点的高可用性。Mesos 已经被广泛应用于各类集群的管理，但是其 Offer-Accept 的资源申请可能不是特别容易理解。

对于想要自行编写调度策略的人，Frameworks 的抽象比较并不容易掌握。而且由于 Framework 要先占有了资源才能使用，设计不够良好的 Framework 可能会导致资源浪费和资源竞争/死锁。

案例3: Spark 和 Spark Drizzle

Spark 为了调度和执行自己基于 DAG 模型的计算，自己实现了一个集中式的调度器，这个调度器的 Master 被称为 Driver。当 Driver 运行起来的之后，会向上层的 Scheduler 申请资源调度起 Executor 进程。Executor 将会一直保持待机，等候 Driver 分配任务并执行，直到任务结束为止。

Spark 传统的调度模型

Spark 和 YARN 这样的集中式调度器放在一起可以认为是通过迂回的方式实现了双层调度器。就好像单机进程自己实现协程调度器一样，Spark Driver 预先申请的资源可以认为是在申请分区资源，申请到的资源将由 Driver 自行管理和使用。

有趣的是，在 2017 年的 SOSP 上，Spark 为了解决流处理计算当中调度延迟较大的问题，提出了一种新的调度模型 Drizzle，在原来调度模型的基础上，又再次实现了双层调度。下图是 Spark Drizzle 的设计模型：

Spark Drizzle 的调度模型

Drizzle 使得调度 Spark Streaming 任务的延迟由最低500ms降低到200ms 左右，让 Spark Streaming 在低延迟处理的问题上获得了突破性的进展。要搞清楚 Drizzle 提出的目的和解决的问题，首先要理解以下几点：

Spark Streaming 的实现方式实际上是 Micro Batch，也就是说流式输入的数据在这里仍然被切分成一个一个 Batch 进行处理；
传统的 Spark 调度器会在前序任务完成之后，根据之前任务输出的规模和分布，通过一定的算法有策略地调度新的任务，以便于获得更好的处理速度、降低资源浪费；
在这一过程中，Exector 需要在前续任务完成后通知 Scheduler，之后由 Scheduler 调度新的任务。在传统 Batch 处理模式下，这种模型效果很好，但是在 Streaming 的场景下存在很多问题；
在 Streaming 场景下，每个 Batch 的数据量较小，因此任务可能会需要频繁与 Scheduler 交互，因为存在这一交互过程的 Overhead，Streaming 处理的过程中最低的延迟也要 500ms 以上。

为了得到更低的延迟性且保留 Micro Batch 容错性强且易于执行 Checkpoint 的优点，Drizzle 在原来的模型上做了一些优化：

在每个节点运行一个 LocalScheduler；
中央调度器 Driver 在执行 Streaming 处理任务时，根据计算的 DAG 图模型，预先调度某一个 Job 的后序 Job，后序 Job 会被放置在 LocalScheduler 上；
后序 Job 默认在 LocalScheduler 上是沉睡状态，但是前面的 Job 可以知道后序 Job 在哪个节点上，因此当前面的任务完成后，可以直接激活后序任务；
当后序任务被激活之后，前序任务和后序任务可以直接通过网络请求串流结果。

可以看到 Drizzle 的主要思路就是根据用户程序生成的图模型，预先 Schedule 一些任务，使得前序任务知道后序任务的位置，在调度时避免再请求中央调度器 Driver。同时 Drizzle 也采取了其他一些方法：比如将多个 Micro Batch 打包在一起，借由 LocalScheduler 自行本地调度等方式减少延迟。

Drizzle 模型可以说是双层模型的又一种另类体现。然而这种模型主要的缺点是必须要预先知道计算任务的图模型和依赖关系，否则就无法发挥作用。

3、共享状态调度器

通过前面两种模型的介绍，可以发现集群中需要管理的状态主要包括以下两种：

系统中资源分配和使用的状态
系统中任务调度和执行的状态

在集中式调度器里，这两个状态都由中心调度器管理，并且一并集成了调度等功能；双层调度器模式里，这两个状态分别由中央调度器和次级调度器管理。

集中式调度器可以容易地保证全局状态的一致性，但是可扩展性不够；双层调度器对共享状态的管理较难达到好的一致性保证，也不容易检测资源竞争和死锁。

为了解决这些问题，一种新的调度器架构被设计出来。这种架构基本上沿袭了集中式调度器的模式，通过将中央调度器肢解为多个服务以提供更好的伸缩性。这种调度器的核心是共享的集群状态，因此可以被称为共享状态调度器。

共享状态调度器

共享状态调度架构为了提供高可用性和可扩展性，将除共享状态之外的功能剥离出来成为独立的服务。这种设计可以类比为单机操作系统的微内核设计。

在这种设计中，内核只负责提供最核心的资源管理接口，其他的内核功能都被实现为独立的服务，通过调用内核提供的 API 完成工作。

共享状态调度器的设计近些年来越来越受欢迎，这两年炙手可热的 Kubernetes 和它的原型 Borg 都是采用这种架构。最近由加州大学伯克利分校知名实验室 RISELab 提出的、号称要取代 Spark 分布式计算系统 Ray 也是如此。

下面将对这些案例进行介绍：

案例1: Borg / Kubernetes

根据相关论文，Borg 在初期开发的时候使用的是集中式调度器的设计，所有功能都被集中在 BorgMaster 当中，之后随着对灵活性和可扩展性的要求，逐步切换到共享状态模型或者说微内核模型上面去。Google 的工程师们总结了 Borg 的经验教训，将这些概念集合在 Kubernetes 当中开源出来，成为了近些年来最炙手可热的资源管理框架。

在这里我们依然以 Borg 为例进行介绍，Kubernetes 在具体的设计上是与 Borg 基本一致的。下图是 Borg 设计架构示意图：

Borg 资源调度架构

Borg 资源调度架构的设计可以总结为以下几点：

一个数据中心的集群可以被组织成一个 Borg 当中的 Cell；
在一个 Borg 的 Cell 当中，资源的管理类似于集中式调度器的设计——集群资源由 BorgMaster 统一管理，每一个节点上运行着Borglet定时将本机器的状态与 BorgMaster 同步；
为了增加可用性，BorgMaster 使用了Stand-By Master的模式。也就是说同时运行着 BorgMaster 的多个热备份，当 Active 的 BorgMaster 出现失败，新的 Master 会被选取出来；
为了增加可扩展性和灵活性，BorgMaster 的大部分功能被剥离出来成为独立的服务。最终，BorgMaster 只剩下维护集群资源和任务状态这唯一一个功能，包括 Scheduler 在内的所有其他服务都独立运行；
独立运行的每个 Scheduler 可以运行自己的调度策略，它们定时从 BorgMaster 同步集群资源状态，根据自己的需要做出修改，然后通过 API 同步回 BorgMaster，从而实现调度功能。

可以看到，Borg 的共享状态调度架构其实是集中式调度的改进。由于承载调度逻辑的调度器都运行在独立的服务里，对于 BorgMaster 的请求压力得到了某种程度的缓解。使用微内核设计模式，BorgMaster 自己包含的逻辑就比较简单了，系统的鲁棒性、灵活性和可扩展性得到了增强。

在 Borg 中，任务的隔离和资源限制使用了 Linux 的 cgroup 机制。在 Kubernetes 当中，这一机制被 Container 技术替代，实际上的功能是等价的。

Borg 的共享状态设计看似简单，其实具体实现仍然比较复杂。事实上，集中式的状态管理仍然会成为瓶颈。随着集群规模的扩展和状态的规模扩大，State Storage 必须使用分布式数据储存机制来保证可用性和低延迟。

一些文章认为 Borg 属于集中式调度器，但笔者认为，随着时间的推移，Borg / Kubernetes 已经将诸多调度器的功能剥离为独立的服务，因此更接近共享状态调度器。

共享状态架构的设计和双层设计的最大区别是，共享状态被抽取出来由一个统一的组件管理。从其他的各种服务的角度来看，共享状态提供的调用接口和集中式调度的状态管理是一样的。这种设计通过封装内部细节的方式，降低了外部服务编写的复杂度，体现了系统设计里封装复杂模块的思想。

案例2: Omega

上面介绍的 Borg 是共享状态最典型的一个示例。尽管 BorgMaster 已经为其他服务的编程提供了简单的接口，但是仍然没有降低状态一致性同步的难度——BorgMaster 和服务的编写仍然需要考虑很多并发控制的方法，防止对共享状态的修改出现 Race Condition 或死锁的现象。

如何为其他服务和调度策略提供一层简单的抽象，使得任务的调度能兼顾吞吐量、延迟和并发安全呢？

Omega 使用事务（Transaction）解决共享状态一致性管理的问题。这一思路非常直观——如果将数据库储存的数据看作共享状态，那么数据库就是是共享状态管理的最成熟、最通用的解决方案！事务更是早已被开发者们熟悉且证明了的非常成熟、好用的并发抽象。

事务调度策略

Omega 将集群中资源的使用和任务的调度看作数据库中的条目，在一个应用执行的过程当中，调度器可以分步请求多种资源，当所有资源依次被占用并使任务执行完成，这个 Transaction 就会被成功 Commit 。

Omega 的设计借鉴了很多数据库设计的思路，比如：

Transaction设计保留了一般事务的诸多特性：如嵌套Transaction或者 Checkpoint。当资源无法获取或任务执行失败，事务将会被回滚到上一个 Checkpoint 那里；
Omega 可以实现传统数据库的死锁检测机制，如果检测到死锁，可以安全地撤销一个任务或其中的一些步骤；
Omega 使用了乐观锁，也就是说申请的资源不会立刻被加上排他锁，只有需要真正分配资源或进行事务提交的时候，才会检查锁的状态，如果发现出现了 Race Condition 或其他错误，相关事务可以被回滚；
Omega 可以像主流数据库一样定义 Procedure ，这些 Procedure 可以实现一些简单的逻辑，用于对用户的资源请求进行合法性的验证（如优先级保证、一致性校验、资源请求权限管理等）。

Omega 使用事务管理状态的想法非常新颖，这一设计随着分布式数据库以及分布式事务的逐渐发展、成熟而逐渐变得可行，它一度被认为将成为 Google 的下一代调度系统。

然而近期的一些消息表明，为了达到设计目标，Omega 的实现逻辑变得越来越复杂。在原有的 Borg 共享状态模型已经能满足绝大部分需要的情况下，Omega 的前景似乎没有那么乐观。

四、总结

这篇文章介绍了多种调度器结构设计的模型，并讨论了在相关模型下进行任务调度的一些特点。通过这些模型的对比，我想提出自己对调度系统设计的几点看法：

在小规模的应用和需要自己设计调度器的场景，我们应该尽量采取中心化的调度模型。这是因为这种模型设计和使用都比较简单，调度器容易对整个系统的状态有全面的把握，状态同步的困难也不高；
在机群和应用规模继续扩大或者对调度算法有定制要求的情况下，可以考虑使用双层调度器设计。双层调度器调度策略的编写较为复杂，随着新一代共享状态调度器的发展，在未来可能会慢慢退出主流；
共享状态调度器因为其较为简单的编程接口以及适应多种需要的特点，正随着 Kubernetes 的流行而渐渐变成主流。如果应用规模比较大或需要在一个集群上运行多种定制调度策略，这种调度器架构设计是最有前景的。

最后，通过学习和亲自设计一套调度系统，我深刻地领会到一些个人在编程的时候非常重要的经验：

Keep things simple. 在实现任何程序的时候，简单的设计往往比复杂的设计更好。比如说尽量减少系统中相互独立的各种模块，尽量统一编程语言，尽量减少相互隔离的系统状态。这样的设计可以减少 Bug 出现的概率，降低维护状态同步的难度；
Move fast. 在设计复杂系统的时候很容易陷入对细节的不必要追究上，从而导致需要管理的细节越来越多，增加了很多心智压力，最后系统完成的进度也是难上加难。更好的办法是先从宏观上进行大概设计，在进行实现的时候忽略具体的细节（比如代码如何组织、函数如何相互调用、代码如何写得好看等），快速迭代并实现功能。当然，在这个过程中也仍然要把握好功能和质量的平衡；
技术发展的循环上升轨迹。 回忆起当初 Linux 和 Minix 在宏内核和微内核之间的世纪论战，尽管以 Linux 这种 Monolithic 内核设计的胜出而告终，但是 Minix 的作者在其著述的《Modern Operating System》教科书上指出了这种循环上升的轨迹，预言了微内核设计的归来。看一看共享状态调度系统的设计就会发现，这一预言已经应验在了分布式系统上。

五、展望

在本文中，并没有特别涉及到任务调度的具体算法，比如如何准确地定时激发任务、如何更高效地分配资源等等。调度算法所要解决的问题本质上只有两个：

全面掌握当前系统的状态
准确预测未来的任务需求

很多调度器模型在设计上已经对这两方面有所考量，但调度器算法本身可以说又是一个巨大的主题，笔者本身对其了解也非常有限，因此不敢在这篇文章中继续展开。从直觉上讲，上述需求二可能是一个和 AI 技术相结合很好的切入点，在未来可能会有很多研究。

在前文还提到了很多调度器也会附带管理本地文件资源的分发，比如像 Kubernetes 启动任务的时候需要将 Docker 镜像分发到各个宿主机上。

作为其原型，Borg 在这一过程中甚至利用了 P2P 技术加快分发速度和充分利用带宽。在开源世界中似乎还没有类似的解决方案。当然，这一需求也只有在机群规模非常大的时候才有价值，但未来仍可能成为一个不错的发展方向。

作者介绍：
张晨，Strikingly数据平台工程师，算法、分布式系统和函数式编程爱好者。Shanghai Linux User Group Co-Op，上海交大技术社群SJTUG创始人。

本文转载自公众号360云计算（ID：hulktalk）。

原文链接：

https://mp.weixin.qq.com/s/3cN63AMQicEi_dquWquNjA

创作场景

7 种主流案例，告诉你调度器架构设计通用法则（下）