谷歌最近公布了他们基础设施系统王冠上的宝石之一：Borg，集群调度系统。这促使我重新阅读了Mesos和Omega论文，它们与Borg的功能类似。我觉得对比下这三个系统一定会非常有趣。Mesos两级调度的突破性理念得到了认可，Omega使用类似数据库的技术有所改进，Borg可以看作是对所有这些思想的巅峰之作。

背景

集群调度系统在大数据出现之前就存在已久。在高性能计算（HPC）的世界中，关于上千核CPU的调度有丰富的文献，但他们的问题域比数据中心调度系统要解决什么更简单，到底该用Mesos/Borg还是与他们同类的其他产品。让我们从几个维度对他们进行一次对比。

为具体位置而调度

超级计算机将存储和计算分离，并使用近似于全等分带宽的网络连接起来，其运行速度接近内存速度（GB/秒）。这意味着我们的任务可以放置在集群上的任何地方，而不必考虑具体位置，因为所有计算节点都可以同样快速地访问数据。一些超优化的应用优化了网络拓扑，但这毕竟是非常罕见的。

数据中心调度系统会关心具体位置，实际上，这是GFS和MapReduce共同设计的结果。回眸2000年初，那时的网络带宽远比磁盘带宽昂贵。所以，为了经济上极大的节约，调度算法会将计算任务保持在与数据相同的节点上。这是调度主要的约束;在我们可以把任务放到任何地方之前，需要将其放在三个数据副本之一的节点上。

硬件配置

超级计算机通常由同质节点组成的，即它们都具有相同的硬件规格。这是因为，超级计算机一般是一次性购买的：实验室获得几百万美元的采购费用，然后一次全部预支出去。一些高性能计算应用的优化是针对超级计算机中特定型号的CPU的。新技术，如图形处理器和协处理器的推出，就要作为一个新的集群。

在大数据领域，集群主要受存储限制，因此运维不断地增加新的机架，更新规格来扩展群集容量。这意味着节点可以有不同的CPU、内存容量、磁盘数量等。这样的节点还可以配入指定的附加设备，如固态硬盘、图形处理器、重叠驱动器（shingled drive）等。一个数据中心可能要支持广泛的应用，而这一切又会强加额外的调度约束。

队列管理和调度

在超级计算机上运行应用程序时，你需要指定想要多少个节点、要提交作业的队列，以及作业将运行多长时间。队列存储可以请求多少资源、作业可以运行多久等不同的限制。同时，队列也有优先级或基于系统的预留来确定排序。由于作业的持续时间都是已知的，这是一个非常简单的打包到盒子的问题。如果队列很长（通常就是这样），并有可以很好融合的小作业回填大作业（也是典型）的剩余空间，则可以实现非常高的资源利用率。我很喜欢将这一描述用以时间为X轴，以资源使用为Y轴的可视化2D图呈现出来。

如前所述，数据中心的调度是一个比较普遍的问题。资源请求的“形状”可以是相当多样，并有更多的维度。作业也没有设定持续时间，所以很难预先计划队列。因此，我们有更复杂的调度算法，从而，调度器的性能变得非常重要。

利用率作为一般的规则将变得糟糕（除非你是谷歌，以及更多的后来者），但高性能计算之上的应用有一个优势是可以使用MapReduce和类似的技术逐渐代替组调度。高性能计算，会等到请求所需的N个节点都可用后，同时运行所有任务。MapReduce可以在多次波动中运行它的任务，这意味着它仍然可以有效地利用剩余的资源。单一的MR作业也可以基于集群的需求起伏，避免了抢占或资源预留，并且还有助于实现多用户之间的公平性。

Mesos

Mesos的出现早于YARN，并且在设计时考虑了原有MapReduce的问题。当时，Hadoop集群只可以运行一种单一的应用：MapReduce。这使得它很难运行不符合先是map阶段后是reduce阶段的应用程序。这里最好的例子是Spark。在Mesos出现之前，你必须为Spark安装一套全新的worker和master，这一套设置与MapReduce的worker和master放在一起。这么做，从利用率的角度来看非常不理想，因为他们通常是静态分区的。

通过为所有集群应用提供一个通用调度器，Mesos解决了这一问题。MapReduce和Spark被简单地作为不同的应用程序，他们可以使用相同的基础资源，共享Mesos的Framework。最简单的实现方法是写一个集中式的调度器，但具有如下一些缺点：

• API的复杂性：我们需要一个单一的API，它是所有已知Framework调度器API的超集。这本身就是一个难题。资源请求也会变得非常复杂。
• 性能：成千上万个节点和数百万的任务实在太多，特别是当调度问题很复杂的时候。
• 代码的灵活性：要为新的需求，持续编写新的调度器和新的Framework。

相反，Mesos引入了两级调度的理念。Mesos将每个应用程序的调度工作委派给应用程序本身，同时，Mesos仍然负责应用和执行整体公平性之间的资源分配。因此，Mesos可以做得相当薄，只有10K行代码。

两级调度通过一个名为资源邀约的新API发起，Mesos会周期地为应用程序调度器提供一些资源。这咋听起来很落后（请求要从master到应用程序？），但其实这一点都不奇怪。在MR1中，TaskTracker worker是实际的运行节点。当TT心跳报告任务完成后，JobTracker会选择别的任务让TaskTracker运行。调度决策本质上是由worker上的资源邀约触发的。在Mesos中，资源邀约来自Mesos master，而不是slave，因为Mesos在管理集群。没有什么不同。

资源邀约扮演着对资源有时间限制的租约。基于优先级或公平份额策略​​，Mesos向应用程序提供资源。然后，应用程序会计算如何使用他们，并且告诉Mesos资源邀约中它想要的那部分资源。这给了应用程序很大的灵活性，因为它可以选择现在运行任务的一部分、等待后面更大的分配（组调度），或者调整任务的大小以适应可用的资源。由于邀约是有时间限制的，这也激励了应用程序去实现快速地调度。

一些问题及解决办法：

• 长任务占用资源：Mesos允许为短任务预留一些资源，时间期限一到便杀死他们。这也激励了用户使用短任务，它具有很好的公平性。
• 性能隔离：使用Linux容器（cgroups）。
• 大型任务饥饿：很难得到一个节点的唯一访问权，因为一些具有较小任务的其他应用程序会蚕食它。可以通过设定请求资源的最小规模来修复这一问题。

尚未解决的/未知的决定：

• 组调度：我认为，无法预知任务长度或者抢占不可能做到高利用率。可以使用低利用率来增量囤积资源，但这可能会导致死锁。
• 跨应用程序抢占很也难：资源邀约API没有办法说“这里有一些低优先级的任务，如果你想要，我可以杀掉他们。”Mesos实现公平性取决于任务必须是短期的。

Omega

Omega是Mesos的继任者，事实上，是同一作者。由于论文采用模拟结果做评估，所以我怀疑它永远不会进入谷歌的生产，而其中的想法会进入下一代Borg中。改写API可能是太侵入性的变化，即使是谷歌。

Omega让资源邀约更进一步。在Mesos中，资源邀约是悲观的或独占的。如果资源已经提供给一个应用程序，同样的资源将不能提供给另一个应用程序，直到邀约超时。在Omega中，资源邀约是乐观的。每个应用程序可以请求群集上的所有可用资源，冲突在提交时解决。Omega的资源管理器基本上只是一个记录每个节点状态的关系数据库，使用不同类型的乐观并发控制解决冲突。这样的好处是大大增加了调度器的性能（完全并行）和更好的利用率。

所有这一切的缺点是，应用程序是在一个绝对自由的环境中，他们可以以最快的速度吞噬他们想要的资源，甚至抢占其他用户的资源。对谷歌来说这没问题，因为他们使用基于优先级的系统，并且可以向他们的内部用户咆哮。他们的应用大致只分为两种优先级：高优先级的服务性作业（如HBase、web服务器、长住服务等）和低优先级的批处理作业（MapReduce和类似技术）。应用程序可以抢占低优先级的作业，并且在协作执行限制的范围＃内授信，以提交作业、计算资源分配等。我认为雅虎没法冲着用户大叫（当然是不可扩展的），但这在谷歌某种方式上是可行的。

论文的大部分在谈论这种乐观的分配方案如何与冲突一起工作的，这永远是个问题。有一些高级的注意事项：

• 服务性作业都较大，对（跨机架的）容错有更严格的配置需求。
• 由于在分配完全群集状态上的开销，Omega大概可以将调度器扩展到十倍，但是无法达到百倍。
• 秒级的调度时间是典型的。他们还比较了十秒级和百秒级的调度，这是两级调度的好处真正发挥作用的地方。无法确定这样的场景有多普遍，也许是由服务性作业来决定？
• 典型的集群利用率约为60％。
• 在OCC实践中，冲突非常罕见。在调度器崩溃之前，他们能够将正常批处理作业上升6倍。
• 增量调度是非常重要的。组调度明显更昂贵，因为要增加冲突处理的实现。显然，大多数的应用程序可以做好增量，通过实现部分资源分配进而达到他们所需的全额资源。
• 即使执行复杂的调度器（每作业十余秒的费），Omega仍然可以在合理的等待时间内调度一个混合的作业。
• 用一个新的MapReduce调度器进行实验，从经验上说，在Omega中会非常容易。

开放式问题

• 在某些时候，因为高冲突率和重试导致的重复工作，乐观并发控制会崩溃。在实践中他们好像没有碰到这种问题，但我不知道是否有奇形怪状的任务致使出现最坏的场景。这是受服务和批处理作业联合影响的吗？在实践中他们做过什么调优吗？
• 是否缺乏真正可以接受的全局策略？如公平性、抢占等。
• 不同类型的作业调度的时间是多少？有人已经写出非常复杂的调度器吗？

Borg

这是一个具备生产经验的论文。与Omega有相同的负载作业量，因为它也出自谷歌，所以很多元点都是一样的。

高级功能

• 谷歌的一切都在Borg中运行，包括像CFS和BigTable这样的存储系统。
• 平均集群大小为10K个节点，虽然还有更大集群。
• 节点可以是异构的。
• Borg使用了Linux进程隔离技术（基本上就是容器技术），因为Borg的出现早于现代虚拟机基础架构。效率和启动时间是很重要的。
• 所有作业都是静态链接的二进制文件。
• 有非常复杂、非常丰富的资源规范语言。
• 可以滚动更新运行的作业，更新可以是配置和二进制文件。有时这需要任务重新启动，所以容错很重要。
• 通过SIGTERM支持“正常停止”，否则通过SIGKILL最终杀掉进程。软杀进程是可选的，但从正确性上说是不可靠的。

Alloc

• 资源分配从进程活跃度中分离。Alloc可以用于为任务组资源分配，或者为重新启动的任务保留资源。
• Alloc集合是一组在多台机器上的Alloc。多个作业可以在一个单一的Alloc中运行。
• Alloc实际上是一种很常见的模式！对于分离问题与实现，多进程是有用的。

优先级和配额

• 两级优先级：服务性的高优先级和批处理的低优先级。
• 更高的优先级作业可以抢占低优先级的。
• 高优先级的作业不能彼此抢占（在防止级联活锁的情况下）。
• 配额用于接入控制。用户支付更多的配额获得更高的优先级。
• 运行在最低优先级还提供了“自由”层，以鼓励高利用率和回填工作。
• 这是一个简单易懂的系统！

调度

• 两个阶段调度：找到可行的节点，然后为最终放置对这些节点评分。
• 可行性在很大程度上由任务约束决定。
• 评分主要由系统属性决定，比如最适合与最不适合、作业组成、故障域、具体位置等。
• 一旦最终节点被选择，Borg将抢占该节点的资源以适应需求。
• 典型的调度时间是25秒左右，这依赖于具体节点的本地化。下载二进制占这个时长的80％。这个具体位置很重要。 Torrent和树协议用于分发二进制文件。

伸缩性

• 集中化一直是潜在的性能瓶颈。
• 针对成千上万个节点，每分钟调度的速率为10K任务。
• 典型的Borgmaster使用10-14个内核和50GB内存。
• 随着时间推移，参照Omega和两级调度，Borg架构已经变成更多的多进程。
• Borgmaster是独立的主节点，但有些责任依然共享：worker状态的更新、只读的RPC。
• 一些明显的优化：缓存的机器分数、每种任务类型计算一次的可行性，在做调度决策时，不要试图全局最优。
• 对较大单元的主要争论是隔离操作错误和失败的传播。架构保持良好的伸缩性。

利用率

• 他们的主要的度量指标是单元压缩，或者说还有空间容纳一组任务的最小集群。从本质上讲是打包装箱。
• 主要收益来自以下几点：不分隔作业或用户、有很大的共享集群、细粒度的资源请求。
• 基于Borglet的乐观过量使用。 Borglets做资源估算，然后回填非prod工作。如果估计不正确，杀掉非prod工作。内存是无弹性的资源。
• 共享不会显着影响CPI（CPU干扰），但我不知道对存储是否有影响。

经验教训

这里列出的问题多数在他们的公开的、开放源码的容器调度系统Kubernetes中已经修复。

缺点：

• 对于跟踪和管理来说，调度多作业的工作流程要比调度单一的作业更好。关于工作流组件，还需要更灵活的方式。解决办法是可以将任意的键值对附加到每个任务上，并允许用户对其进行查询。
• 每台机器一个IP。这会导致一台机器上的端口冲突，以及复杂的绑定和服务发现。可以通过Linux的命名空间、IPv6和SDN来解决。
• 复杂的规范语言。知识点太多，作为一个普通用户很难上手。自动化确定资源请求需要一些工作。

优点：

Alloc非常牛！辅助服务可以很容易置入下一个主任务。后台服务，如负载均衡服务和命名服务是非常有用的。度量、调试、网页界面都很重要，用户能通过他们解决自己的问题。集中化的可扩展性很好，但需要将其拆分到多个进程中。为此，Kubernetes从新开始，为不同调度器组件提供一套干净的API。

结束语

YARN看上去借鉴了Mesos和Omega，使伸缩规模到达10K节点。与Mesos和Omega相比，YARN仍然是一个集中式的调度系统。Borg特别强调要分片伸缩。

为了实现高利用率而不损害服务水平目标（SLO），隔离是非常重要的。这可以在应用程序层面来实现，而应用服务本身需要设计为延迟容忍的。想想在BigTable中，为避免请求延迟（tail-at-scale）采用的向副本发起请求。最终，问题归结为是要硬件来做隔离还是软件来做。保持运行于利用率较低的状态可以回避这一问题。或者，你可以直接通过OS的隔离机制、资源评估和调整你的作业和调度器来解决。在谷歌的规模下，有足够的硬件、可以招一批内核开发工程师来实现。幸运的是，他们为我们做足了工作 :)

我也想知道，是否谷歌的假设作业更具备普遍性。谷歌能很好地使用优先级分类、资源预留，以及抢占，但是我们的客户几乎全部使用公平共享调度器。雅虎使用容量调度器。 Twitter使用的公平调度器。我没有听说过的关于优先级+资源预留调度器的任何需求或使用。

最后，很少有客户会运行在谷歌预想的大共享集群上。我们的客户在使用千级的节点，但是这被分为百级的pod节点上。为单独的用户或者应用程序独立部署集群也是常见的。集群在硬件方面通常还是同构的。我认为这将开始改变，并且会很快。