集群调度系统的演进

Kubernetes 已经成为容器编排领域的事实标准，将来所有应用都会在 Kubernetes 上开发和运行，这个系列文章的目的是深入浅出的介绍 Kubernetes 底层实现的原理。

Kubernetes 是一个集群调度系统，今天这篇文章主要是介绍 Kubernetes 之前一些集群调度系统的架构，通过梳理他们的设计思路和架构特点，我们能够学习到集群调度系统的架构的演进过程，以及在架构设计时需要考虑的主要问题，对理解 Kubernetes 的架构会非常有帮助。

基本概念

我们需要先了解集群调度系统里面的一些基本的概念，为了方便大家理解，我通过一个例子来解释这些概念，假设我们要实现一个分布式的定时任务系统（分布式的 Cron），这个系统管理了一组 Linux 主机，用户通过系统提供的的 API / UI 定义定时任务（就类似在 Linux 里面定义 Crontab） ，系统会根据任务的定义，来定时来执行相应的任务，在这个例子里面有如下基本概念：

• 集群（Cluster）：这个系统管理的 Linux 主机组成一个资源池，用来运行任务，这个资源池就是集群。
• 作业（Job）：就是定义集群如何去执行任务，在例子里面 Crontab 就是一个简单的作业，里面明确的告诉了集群需要在什么时间（时间间隔） ，做什么事情（执行的脚本）。一些作业的定义会复杂很多，比如还会定义一个作业分几个任务做完，以及任务之间的依赖关系，还包括每一个任务对资源的需求。
• 任务（Task）：作业需要被调度成具体的执行任务，如果我们定义了一个作业是每天晚上凌晨 1 点执行一个脚本，那么在每天凌晨 1点被执行的这个脚本进程就是任务。

在设计集群调度系统的时候，这个调度系统的核心任务也就是 2 个：

• 任务调度。作业提交给集群调度系统之后，需要对提交的作业拆分成具体的执行任务，并且跟踪和监控任务的执行结果。在分布式 Cron 的例子中，调度系统需要按照作业的要求定时启动进程，如果进程执行失败，需要重试等，一些复杂的场景，比如 Hadoop 的 Map Reduce ，调度系统需要把 Map Reduce 任务拆分成相应的多个 Map 和 Reduce 任务，并且最终拿到任务执行结果的数据。
• 资源调度：本质上是对任务和资源做匹配，根据集群中主机的资源使用情况，分配合适的资源来运行任务。和操作系统的进程调度算法比较类似，资源调度的主要目标是，在固定的资源供给的情况下，尽可能提高资源使用率，减少任务等待的时间（任务等待资源去执行的时间），减少任务运行的延迟或者响应时间（如果是批量任务的话，就是任务从开始执行到结束的时间，如果在线响应式任务的话，比如 Web 应用，就是每一次响应请求的时间），尽可能公平（资源公平的被分配到所有任务）的同时，还需要考虑任务的优先级。这些目标里面有一些是有冲突的，需要平衡，比如资源利用率和响应时间，公平和优先级。

Hadoop MRv1

Map Reduce 是一种并行计算模型，Hadoop 是可以运行这种并行计算的集群管理平台，其中 MRv1 是 Hadoop 平台的 Map Reduce 任务调度引擎的第一代版本，简单来说，用户定义了 一个 Map Reduce 计算，提交给 Hadoop 之后，由 MRv1 负责在集群上调度和执行这个作业，并且返回计算结果。 MRv1 的架构看起来是这样的：

架构还是比较简单的，标准的 Master/Slave 的架构，有 2 个核心组件：

• Job Tracker 是集群主要的管理组件，同时承担了资源调度和任务调度的责任。
• Task Tracker 运行在集群的每一台机器上，负责在主机上运行具体的任务，并且汇报状态。

随着 Hadoop 的流行和各种需求的增加，MRv1 有如下问题需要改进：

1. 性能有一定瓶颈：支持管理的最大节点数是 5千个节点，支持运行的任务最大数量 4万，还有一定的提高空间。
2. 不够灵活，无法扩展支持其他任务类型。Hadoop 生态里面除了 Map Reduce 类型任务，还有其他很多任务类型需要调度，比如 Spark，Hive，HBase，Storm，Oozie 等，所以需要一个更加通用的调度系统，能够支持和扩展更多的任务类型。
3. 资源利用率比较低。MRv1 给每个节点静态配置了固定数目的 Slot ，每个 Slot 也只能够运行的特定的任务的类型（Map or Reduce），这就导致资源利用率的问题，比如大量 Map 任务在排队等待空闲资源，但实际上机器有大量 Reduce 的 Slot 被闲置。
4. 多租户和多版本的问题。比如不同部门在同一个集群里面运行任务，但是彼此是逻辑上隔离的，或者在同一个集群里面运行不同版本的 Hadoop。

YARN

YARN（Yet Another Resource Negotiator）是 Hadoop 的第二代调度系统，主要目的就是为了解决 MRv1 中的各种问题。YARN 的架构看起来是这样的：

YARN 简单的理解就是，相对于 MRv1 的主要改进就是，把原来的 JobTrack 的职责，拆分给两个不同的组件来完成：Resource Manager 和 Application Master：

• Resource Manager：承担资源调度的职责，管理所有资源，将资源分配给不同类型的任务，并且通过“可插拔”的架构来很容易的扩展资源调度算法。
• Application Master：承担任务调度的职责，每一个作业（在 YARN 里面叫做 Application）都会启动一个对应的 Application Master，它来负责把作业拆分成具体的任务、向 Resource Manager 申请资源、启动任务、跟踪任务的状态并且汇报结果。

我们看看这种架构改变是如何解决 MRv1 的各种问题的：

• 将原来的 Job Tracker 的任务调度职责拆分出来，大幅度提高了性能。原来的 Job Tracker 的任务调度的职责拆分出来由 Application Master 承担，并且 Application Master 是分布式的，每一个实例只处理一个作业的请求，将原来能够支撑的集群节点最大数量，从原来的5千节点提升到1万节点。
• 任务调度的组件，Application Master，和资源调度解耦，而且是根据作业的请求而动态创建的，一个 Application Master 实例只负责一个作业的调度，也就更加容易支持不同类型的作业。
• 引入了容器隔离技术，每一个任务都是在一个隔离的容器里面运行，根据任务对资源的需求来动态分配资源，大幅提高了资源利用率。不过有一个缺点是，YARN 的资源管理和分配，只有内存一个维度。

Mesos 的架构

YARN 的设计目标依然是服务于 Hadoop 生态的调度，Mesos 的目标更近一步，被设计成一个通用的调度系统，能够管理整个数据中心的作业，看的出来 Mesos 的架构设计很多借鉴了 YARN，将作业调度和资源调度分别由不同的模块承担，不过 Mesos 和 YARN 很大不同的地方是对资源的调度方式，设计了一个叫非常独特的 Resource Offer 的机制，进一步释放了资源调度的压力，增加了作业调度的扩展性。

Mesos 的主要组件是：

• Mesos Master ，单纯是承担资源分配和管理的组件，的对应到 YARN 里面就是那个 Resource Manager，不过工作方式会稍微有些不太一样，后面会讲到。
• Framework，承担作业调度，不同的作业类型都会有一个对应的 Framework，比如负责 Spark 作业的 Spark Framework。

Mesos 的 Resource Offer

看起来 Mesos 和 YARN 架构非常类似，不过实际上在资源管理的方面， Mesos 的 Master 有非常独特（甚至有些奇怪）的 Resource Offer 机制：

• YARN 中 Resource Manager 提供资源的方式是被动的，当资源的消费者（Application Master) 需要资源的时候，会调用 Resource Manager 的接口来获取到资源，Resource Manager 只是被动的响应 Application Master 的需求。
• Mesos 的 Master 提供资源的方式是主动的。Mesos 中的 Master 会定期的主动推送当前的所有可用的资源（就是所谓的 Resource Offer，后面统一都叫 Offer）给 Framework，Framework 如果有任务需要被执行，不能主动申请资源，只有当接收到 Offer 的时候，从 Offer 里面挑选满足要求的资源来接受（在 Mesos 里面这个动作叫做 Accept），剩余的 Offer 就都拒绝掉（这个动作叫做 Reject），如果这一轮 Offer 里面没有足够能够满足要求的资源，只能等待下一轮 Master 提供 Offer。

相信大家看到这个主动的 Offer 机制的时候，会和我有同样的感觉，就是效率比较低，会产生如下问题：

• 任何一个 Framework 的决策效率会影响整体的效率。为了一致性，Master 一次只能给一个 Framework 提供 Offer，等待这个 Framework 挑选完 Offer 之后，再把剩余的提供给下一个 Framework，这样的话，任何一个 Framework 做决策的效率就会影响整体的效率；
• “浪费”很多时间在不需要资源的 Framework 上。 Mesos 并不知道哪个 Framework 需要资源，所以会出现有资源需求的 Framework 在排队等待 Offer，但是没有资源需求的 Framework 却频繁收到 Offer 的情况。

针对上面的问题，Mesos 提供了一些机制来做一定程度的缓解，比如给 Framework 设置一个做决策的超时时间，或者允许 Framework 可以通过设置成 Suppress 状态来表示不需要接受 Offer等，因为不是本次讨论的重点，所以细节就不展开了。

实际上，Mesos 采用这种主动 Offer 的机制，也是有一些明显的优点的：

• 性能明显提高。根据模拟测试一个集群最大可以支撑 10 万个节点，Twitter 的生产环境最大集群支撑 8 万个节点，主要原因是 Mesos Master主动 Offer 的机制，进一步简化了 Mesos Master 的工作职责，Mesos 中将资源调度的过程（资源 —> 任务的匹配）分成了 2 个阶段：资源 —> Offer —> 任务 。Mesos Master 只负责完成第一个阶段，第二个阶段的匹配交给 Framework 来完成。
• 更加灵活，能够满足更加负责的任务调度的策略。举个例子，All Or Nothings 的资源使用策略。

Mesos 的调度算法 DRF（Dominant Resource Fairness)

关于 DRF 算法，其实对我们理解 Mesos 架构并没有什么关系，但是在 Mesos 中却非常核心和重要，所以多啰嗦几句。

上面说了，Mesos 是轮流给 Framework 提供 Offer 的，那么每次该挑选哪个 Framework 提供 Offer 呢？这就是 DRF 算法要解决核心的问题， 基本原则就是要兼顾公平和效率，在经量满足所有 Framework 对资源需求的同时，也要应该尽可能公平，避免某一个 Framework 占用太多资源而把其他 Framework 给“饿死”。

DRF 是 min-max fairness 算法的一个变形，简单来说就是每次都挑选支配资源占用率（Dominant Resource Usage）最低的那个 Framework 提供 Offer。如何计算 Framework 的“支配资源占用率”呢？就是从 Framework 占用的所有资源类型里面，挑选资源占用率最小的那个资源类型最为支配资源（Dominant Resource），它的资源占用率就是这个 Framework 的支配资源占用率（ Dominant Resource Usage），举个例子，一个 Framework X 的 CPU 占用了整体资源的 20%，内存是 30%，磁盘是 10%，那么这个 Framework 的支配资源占用率就是 10%，官方术语把磁盘叫做支配资源， 这个 10% 叫做支配资源占用率。

DRF 的最终目的是把资源平均的分配给所有 Framework，如果一个 Framework X 在这一轮 Offer 中接受（Accept Offer）了过多的资源，那么就要等更长的时间才能获得下一轮 Offer 的机会。不过仔细的读者会发现，这个算法里面有一个假设，就是 Framework 接受了资源之后，会很快释放掉，否则就会有 2 个后果：

1. 其他 Framework 被“饿死“。某个 Framework A 一次性的接受了集群中大部分资源，并且任务一直运行不退出，这样大部分资源就被 Framework A 一直霸占了，其他 Framework 就没法获得资源了。
2. 自己被饿死。因为这个 Framework 的支配资源占用率一直很高，所以长期无法获得 Offer 的机会，也就没法运行更多的任务。

所以实际上，Mesos 只适合调度短任务，Mesos 在设计之初就是为数据中心中的段任务而设计的。

总结一下

从大的架构上，所有调度系统的架构都是 Master / Slave 的架构，Slave 端安装在每一台需要管理的机器上，用来收集主机信息，在主机上执行任务。Master 主要负责做资源调度和任务调度，资源调度对性能要求比较高，任务调度对可扩展性要求较高，总体趋势是讲这两类职责解耦，分别由不同的组件来完成。

原文链接： 集群调度系统的演进 （作者：邵明岐）