大规模集群管理—Google Borg

Abhishek Verma, Luis Pedrosa, Madhukar Korupolu, David Oppenheimer, Eric Tune, John Wilkes

Google

{verma, lpedrosa, madhukar, oppenheimer, etune, johnwilkes}@google.com

摘要

Google 的 Borg 系统是一个集群管理器，负责在数万台机器上运行数十万个作业，这些作业来自数千个不同的应用，每个应用由多个集群组成。Borg 通过组合准入控制、高效的任务打包与装箱（packing）、进程级性能隔离以及共享机器的利用率驱动资源管理来实现这些功能。本文描述了 Borg 的架构、特性、重要的设计决策、定性分析以及从十年运维经验中总结出的定量教训。

1. 引言

集群管理系统（cluster management system）的目标是管理大规模集群中的计算资源，使其能够被众多异构的工作负载高效共享。Google 开发并使用了一个名为 Borg 的系统来完成这一任务，该系统在 Google 的生产环境中已运行了十多年（2014年）。Borg 向用户提供了声明式作业描述语言（declarative job-specification language）、名称服务集成（name-service integration）、实时作业监控（real-time job monitoring），以及自动化地将数万个任务的资源请求自动映射到集群上合适的机器。

本文是首篇公开描述 Borg 的文章。它结合了运行中的 Borg 集群的轨迹驱动模拟（trace-driven simulation）结果、Google 内部 Borg 用户的见解，以及十年来大规模生产经验所积累的教训。

2. Borg 架构

一个 Borg 集群由一组机器（cell）组成，一个 cell 通常包含数万台机器，这些机器通过数据中心的高带宽网络互连。一个 cell 被一个逻辑上的中央控制器 Borgmaster 管理。Cell 中的每台机器上运行着一个名为 Borglet 的代理进程。

2.1 Borgmaster

Borgmaster 的主进程（主副本）处理所有客户端 RPC 请求，这些 RPC 请求包括创建作业（job）、查询作业以及杀死作业等操作。它还管理系统中所有对象（如机器、任务、alloc 等）的状态机（state machine），以及与 Borglet 的通信，并提供一个用于自动化工具和调试用途的 Web UI。

Borgmaster 逻辑上是一个单一进程，但实际上它由五个副本组成。每个副本都在内存中维护了一个 cell 状态的副本，该状态同时被记录在一个高可用的、基于 Paxos 的存储中。当一个被选举为 leader 的 Borgmaster 副本失效时，一个新的副本会在几秒内被选出。Borgmaster 在切换时会重新加载 cell 状态的最近一个检查点（checkpoint）来恢复到之前的状态。一个名为 Fauxmaster 的独立工具可以从检查点文件中恢复状态，它实现了一个模拟的 Borglet 接口，可以用来做故障恢复分析、手动修复以及离线模拟。

2.2 Borglet

Borglet 是一个运行在 cell 中每台机器上的本地代理。它负责启动和停止任务（task）、重启失败的任务、管理本地机器资源（如 kernel 调度、OO-killer [41] 等），并报告机器状态。Borglet 始终运行，即使 Borgmaster 或网络连接出现短暂中断也不会停止——它会保持已有的任务继续运行并继续启动新到达的任务。

Borgmaster 会通过轮询（polling）而非通知（notification）来与 Borglet 通信。这种设计被选择是因为它可以简化 Borgmaster，并且通过将所有通信限制为从 Borgmaster 主进程到 Borglet 的、可流式处理的（streamable）和可限速的（rate-limited）消息，提高了可扩展性。主要的可扩展性瓶颈不是 Borgmaster 的吞吐量，而是状态的持久化。每 11 秒（可配置），Borgmaster 会向 cell 中所有 Borglet 轮询当前的机器状态并发送待处理的请求。这种设计可以容忍错过几轮轮询，从而使得 Borglet 可以应对短暂的网络抖动或 Borgmaster 的停顿。

被选出的 leader 负责准备需要广播到 Borglet 的消息，这些消息基于通过 Paxos 传播的 cell 状态和 Borglet 的轮询响应。如果 leader 需要一个新的调度决策，它会运行调度算法。为了性能和可扩展性的考虑，Borg 集群被划分为以下几个部分（partitions）：一个用于处理 Borgmaster 的调度和状态管理，另一个用于 Borglet 的通信。本文后面的分析将集中在 Borgmaster 的调度决策上。

2.3 可扩展性

早期版本的 Borgmaster 有一个简单的、同步的循环：接受请求、调度任务、与 Borglet 通信。为了处理更大的 cell，我们将调度程序拆分为一个独立的进程，这样就可以在不影响 Borgmaster 其他功能的情况下进行失效恢复。我们将 Borgmaster 与 Borglet 的通信进行了批处理和流水线化。我们使用了一些类似于现有多 Raft 领域的技术 [25, 45, 69]。更重要的是，我们把调度策略与调度机制分离开来，使策略可以通过一个配置文件或者二进制插件进行替换。

当前（2014年）的生产数据：

最大的 cell 管理着约 10,000 台机器。
一个 Borgmaster 实例的观测峰值包括：每分钟超过 10,000 个任务的提交率（arrival rate），超过 1,000 台机器的可用性变更（availability changes），以及数千个任务和机器的状态更新。
某个 production cell 中每秒处理超过 20,000 个任务。
一个生产 Borgmaster 实例在 3 台机器上运行，可使用 10-14 个 CPU 核心和 50 GB 内存。

3. 工作负载

Borg 上运行着两种类型的工作负载。第一种是长期运行的服务（long-running services），这些服务应该永远不会停止，处理短暂的（通常是非延迟敏感的）请求，比如面向用户的 Gmail 和 BigTable，以及内部的基础设施服务如 BigTable 服务器。我们将它们称为生产（production）作业，或简称 prod。第二种是批处理作业（batch jobs），通常持续时间较短（几秒到几天），对短期性能波动不那么敏感。一个 cell 中通常同时运行这两种类型的工作负载，并且我们将 prod 作业设置为比批处理作业具有更高的优先级。

在大多数 cell 中，在任何时间点上，运行任务的总 CPU 占比大约为：prod 任务占 70%，non-prod（批处理）任务占 30%。虽然提交的 prod 任务比批处理任务少得多，但 prod 任务往往会请求更多的资源——特别是内存。一个 cell 中提交的 prod 任务数量相当稳定，而批处理任务数量则每日波动剧烈。

Borg 一个重要的工作负载特征是同质性（homogeneity）：尽管 cell 中运行着数千种不同的任务，但提交到特定 cell 的 prod 任务中，超过 80% 的 CPU 需求集中在不超过十二种不同的机器类型配置上（通过 CPU 核数和内存大小的组合定义）。这种同质性是 Google 通过工程实践有意识地追求的结果：大多数用户使用标准化的语言库、RPC 框架和监控系统，并且 Borg 提供了标准化的打包方案。

图 1 显示了一个 cell 中各种任务资源需求的分布。任务对 CPU 的需求范围很广——从少于 1 个核心到接近 90 个核心（约 3 台机器的资源）——但内存需求范围更广，从几 MB 到几百 GB。大多数任务只需要少量的 CPU 核心（少于 1 个）和少量的内存（少于 2 GB），但两种资源的需求之间存在弱相关性。

Borg 的一个关键设计目标是尽可能高效地打包（pack）任务到机器上，同时确保每种类型的任务在性能隔离方面有足够的保障。下一节讨论了 Borg 如何将任务分配到机器上（任务调度），以及它如何在运行时管理它们（资源管理）。

图 1. 一个典型 cell 中的任务资源需求。每条线对应一种固定任务类型（由二维需求向量 <CPU, 内存> 定义），线上的点代表对该类型任务的资源请求。（未完待续…）大多数任务对 CPU 的需求少于 1 个核心，对内存的需求少于 2 GB。

图 2. 一个 cell 中机器的平均资源利用率（CPU 和内存）随时间变化的曲线。可以看到，周末的资源利用率通常较低。该图展示了资源的总体利用率——请注意，它并没有说明任何关于过量分配（over-commitment）的信息。

图 3. 在 cell 中机器 CPU 利用率的累积分布函数（CDF）。结果显示，共享集群的 CPU 利用率中位数约为 60%，远高于典型的企业数据中心（通常为 10-50% [56, 65]）。

4. 任务

一个 Borg 作业（job）由其名称和一个拥有者所标识。每个作业只运行在一个 cell 中。一个作业包含一个或多个任务（task），这些任务都运行相同的二进制程序。每个任务被映射到 cell 中一台机器上的一组 Linux 进程（process）。大部分 Borg 的工作负载不是在虚拟机（VM）中运行的。这使得 Borg 能够比在 VM 中运行更加高效地管理物理资源，因为这样可以避免虚拟化的开销。

任务有几种状态，包括：Pending（等待中）、Running（运行中）、Dead（已完成）。任务在被调度之前和在被等待接受它的调度器接受之前处于 Pending 状态；在运行时处于 Running 状态；在终止后处于 Dead 状态（出于资源管理的目的，已终止但尚未被清理的任务暂时处于 Undead 状态）。

用户通过 RPC 向 Borgmaster 发起操作，例如提交（submit）一个作业、杀死（kill）一个作业或查询（query）作业/任务状态。Borg 将每个任务的元数据保存在内存中，以便在查询时快速访问。完整的日志和历史数据存储在 Borg 持久化存储中。

用户可以指定一个任务在被抢占（preempted）或被系统重新调度（rescheduled）时应该等待的时间。这个宽限期（grace period）的默认值是 300 秒。Borg 几乎总是遵守这个宽限期——杀死任务是通过 SIGTERM 信号实现的（不是 SIGKILL），所以任务可以捕获该信号并执行清理工作。当一个任务被调度器回收资源时，Borg 会允许它完成当前正在处理的请求（如果它正在服务请求的话），并给它一段宽限时间来停止接收新的请求并清除状态。

任务可以指定它们对机器的资源需求（resource requirements）。每个资源需求被指定为一个固定数量（即一个 resource bundle）。Borg 目前管理的资源有：CPU（以核数计）、内存（以字节计）、以及一些其他资源。CPU 和内存的指定粒度非常精确。Borg 也会管理不可压缩（incompressible）资源（如内存）和可压缩（compressible）资源（如 CPU），二者的处理方式不同。对于可压缩资源，Borg 可以通过降低一个任务的可用资源来实现资源回收，而对于不可压缩资源则不能这样做：当一台机器的内存不足时，Borg 必须杀死一些任务。大多数任务都使用资源限制（resource limit）来获取 CPU 和内存，但任务在大多数情况下不会使用这些限制到其分配量的 100%。

任务可以接收几种可选的约束（constraint）参数，包括：

指定该任务运行的机器类型（如具有特定的指令集架构 ISA、某些 kernel 特性或外部设备的机器）；
指定它与另一个任务应该放在同一台机器上，或者应该分开在不同的机器上（例如，将一个应用的不同副本分布在不同的故障域中）；
限制任务只能在特定的 cell 中运行。

Borg 也支持一些约束中的软约束（soft constraints）——即告诉 Borg 用户的偏好，但不是严格要求。这些约束的优先级低于硬约束。

Borg 提供了一个声明式的作业描述语言来指定这些约束，同时也提供了一个叫做约束（constraints）的参数来帮助 Borg 解析用户描述中的限制（例如，一个任务描述可以要求它必须部署到 "production:tier-1" 标签所标识的机器上）。

任务描述文件的其他字段包括任务名称、拥有者（允许其他人查看或控制该任务的状态）等。

4.1 Allocs

一个 alloc（allocation 的缩写）是 Borg 为特定任务预留的机器资源集合。Alloc 可以用于未来要运行的任务，也可以在当前运行的任务旁保留（使用资源共享技术）。一个 alloc set（alloc 集合）类似于一个作业：它是一组在一台或多台机器上预留的 alloc。一旦 alloc 被分配到一台机器上，任务就可以在其中运行。当 alloc 中的任务终止后，资源可以被释放或被新任务使用。

Borg 的 alloc 和作业之间的区别源于历史原因：alloc 是 Borg 中最古老且应用最广泛的资源管理机制之一。现在，Borg 作业有一个分配了 alloc 资源的任务（或 alloc set），这与容器（container）的概念相似。

5. 优先级（Priority）、配额（Quota）和准入控制（Admission Control）

5.1 优先级

每个作业都有一个优先级（priority），即一个小的正整数。Borg 将优先级划分为以下不相交的区间（interval），区间内的作业具有相同的语义：

monitoring（最高）
production（prod）
batch（批处理）
free（最低）

虽然 Borg 用户可以将工作负载设置为比其他 cell 中的任何作业更高的优先级，但我们发现，在实践中，用户很少滥用这个能力，并且更倾向于让系统管理员根据策略（policy）来分配优先级。

当机器的资源不足以容纳 cell 中所有作业时，Borg 会抢占（preempt）低优先级的任务来为高优先级的任务腾出空间。被抢占的任务会被放回调度队列中，而不是被杀死或失败。抢占是按照以下规则有序执行的：首先抢占低优先级的任务，在同优先级内选择那些会释放最多资源的任务。Borg 不会抢占那些处于 monitoring 优先级的 prod 任务。在 cell 中，如果两个 prod 任务发生冲突，Borg 会根据任务的名称和其他限制来决定优先级。

Borg 会尽量避免发生多米诺效应（domino effect），即一个 prod 任务抢占了另一个 prod 任务，后者又抢占了第三个，以此类推。为了做到这一点，Borg 仅在被抢占任务的优先级严格低于发起抢占请求的任务优先级时，才允许抢占，并且禁止相同优先级的任务之间的抢占。更进一步，当 Borg 需要抢占多个任务时，它会按优先级从低到高逐步进行。

5.2 配额

配额（quota）是决定一个新的作业能否被调度到 Borg 中的一个主要手段。配额是以一个资源向量（包括 CPU、RAM、磁盘等）在一组机器上的可分配时间来表示的。例如：

{cpu:10, mem:20G, disk:100G}

表示该 cell 中有 10 个 CPU 核心、20 GB 内存和 100 GB 磁盘可供分配。

配额在 Borg 的生产 cell 中是以季度或年度为基础进行分配的——它本质上是在每个优先级（priority tier）上的资源访问权限。配额是可以超量出售（overcommitted）的：对一个 cell 的配额承诺可能大于 cell 的实际资源总量。这种策略是安全的，因为实际使用量通常远低于请求的配额——类似于航空公司的超额预订（overbooking）策略。如果配额不足，作业提交会通过 borQuotacheck RPC 调用被拒绝。当一个作业被接纳后，它的任务被放入等待队列中。Borg 的配额系统独立于 Google 内部使用的计量和计费系统，但配额系统的影响和行为与这些系统相似。

Borg 系统的配额机制对避免饥饿（starvation）非常重要。高优先级任务对配额机制的依赖性较低——因为它们的资源请求可以抢占低优先级任务。配额的分配由系统管理员手动管理，依据各团队的预算和资源使用情况。

5.3 准入控制（Admission Control）

准入控制（Admission control）限制了同时运行的 prod 任务的数量。一个 cell 中的 prod 任务数量过多会导致系统过载，进而影响 task 的延迟和质量。Borg 的准入控制是基于以下原则的：如果在所有优先级的 prod 任务中，有超过该 cell 可提供的 prod 资源的 80% 已被占用，Borg 就会拒绝新的 prod 任务进入。这个阈值可以动态调整。

准入控制在实际使用中不是瓶颈，因为 prod 作业的提交率相对较低。当一个 cell 的资源发生变动时——例如，机器因为维护而被关闭——Borg 会尝试重新调度受影响的任务，或者让它们进入排队。如果不能在当前 cell 中容纳它们，它们可能会被调度到其他 cell 中。

在共享集群中，Borg 使用了两层的准入控制：第一层是用户层面的配额检查，第二层是 Borg 系统层面的调度。第一层检查用户的配额是否充足，第二层检查是否有足够的实际可用资源来容纳该任务。

6. 命名和监控

Borg 通过将任务的主机名和端口号存储在 Borg 的名称服务（BNS）中，来帮助任务发现彼此。BNS 是一个基于 Paxos 的、层次化的键-值存储系统。Borg 将任务的名称、主机名、端口和其他元数据写入 BNS。Borg 的任务使用 BNS 来查找彼此，就像 DNS 一样。

此外，Borg 还会自动生成和推送配置文件和变量，从而将任务的拓扑结构和资源信息注入到任务的运行环境中。例如，Borg 会告诉一个新启动的任务它的服务在 BNS 中的名字、它的 CPU 和内存配额，以及它的其他元数据。这种做法被称为”自动配置”（auto-configuration）。

Borg 还通过 borgmon [6] 对所有任务进行监控。每个 prod 任务必须声明一个或多个 HTTP 端点（endpoint），borgmon 会定期（通常每几秒一次）访问这些端点来进行健康检查（health-check）。如果一个 prod 任务没有在合理时间内（通常为几分钟）响应健康检查，borgmon 会将其标记为不健康（unhealthy）并请求 Borgmaster 重新调度它。

Borg 的监控数据也被用来支持容量规划（capacity planning）和故障排除（troubleshooting）。borgmon 收集的数据被推送到时间序列数据库中，然后由各种自动化系统和人工分析员使用。

图 4. 一个典型的 Google 生产 cell 中的系统监控数据流。borgmon 是 Borg 的监控守护进程，负责收集各种运行时指标（metrics），包括任务的 CPU 使用率、内存使用率、磁盘 I/O 等，并将其推送到时间序列数据库中。这些数据随后被用于自动化系统和人工分析员进行故障排除、容量规划和计费。

7. Borgmaster

本节描述了 Borgmaster 的几个关键设计方面，包括：它的调度器（scheduler）、状态持久化以及可扩展性。

7.1 Borgmaster 的实现

Borgmaster 主进程是一个独立的二进制文件，由多个组件组成：

一个处理所有 RPC 请求的前端（front-end）；
一个用于管理所有对象状态的状态管理器（state manager）；
一个负责与 Borglet 通信的通信管理器（communicator）；
一个用于执行调度的调度器（scheduler）。

Borgmaster 的多个副本通过 Paxos 协议进行复制，其中一个被选举为 leader。当 leader 发生变化时，新的 leader 会重新读取 cell 状态的最近检查点，然后通过与 Borglet 的通信来发现当前正在运行的任务和可用的机器资源。它会在内存中重建 cell 状态的完整视图。

Borgmaster 的恢复时间：在一个包含 10,000 台机器的 cell 中，从一个检查点恢复大约需要几秒钟。

7.2 调度器

当一个新任务被提交或者一个正在运行的任务终止后释放了资源时，Borgmaster 的调度器会将 pending 状态的任务分配到有足够可用资源且满足任务约束的机器上。调度器不是简单地找到第一台能满足需求的机器。相反，它会评估所有可用的机器并选择最佳的那一台。评分（scoring）函数是多维度的，它考虑的因素包括：

机器的优先级（priority）；
任务所需资源与机器可用资源之间的匹配程度——即”最合适”（best-fit）；
机器上已有的任务是否具有相同的拥有者（owner），以及该任务是否与已有任务共享某些资源（如 CPU 核心或网络带宽）；
机器上的打包质量（packing efficiency）——即任务的资源被紧凑地放置在一起，以减少碎片化；
任务在该机器上的失败历史记录——例如，如果某个任务之前已经在该机器上失败过多次，调度器会倾向于将其分配到不同的机器上；
该机器上的资源分配是否会导致某种资源的过度紧张（overcommitment）。

在实际调度中，评分函数中各因素的权重取决于不同场景和工作负载类型。Borg 的调度器采用了一些启发式方法来在调度速度和质量之间进行权衡。

Borg 调度器的效率：调度器可以每秒处理约 10,000 个任务的调度请求，对于大多数 cell 的工作负载而言是足够的。

Borg 调度器的两个关键机制：

可行性检查（feasibility checking）：快速过滤出能够容纳该任务的机器集合。典型的做法是仅检查少量约束，如：该机器是否有足够的可用资源、是否满足任务的约束（如机器标签）等。

打分（scoring）：在通过可行性检查的机器中，选择一个最佳的机器。打分函数考虑多种因素，包括：

最少浪费（least-wasted）：选择留给其他任务使用资源最少的机器。这有助于在机器上打包更多的任务。
最相关（most-relevant）：选择与任务所属集群或作业相关的机器。
分散放置（spread）：选择与其他正在运行的任务不在同一台机器上的机器，以减少单台机器故障的影响。

图 5. 一个 Borgmaster 的组件及其数据流。调度器是 Borgmaster 的核心组件之一。当一个任务被提交时，它首先经过准入控制（admission control），然后被放入一个优先级队列（priority queue）中。调度器从队列中取出任务，遍历所有可行的机器并为其打分，最终将任务分配到得分最高的机器上。

7.3 状态持久化

Borg 使用一个分布式存储系统（基于 Paxos）来持久化存储 cell 的状态。每个状态变更都会被记录为一个日志条目，并通过 Paxos 复制到多个副本。检查点（checkpoint）是定期创建的，以减少恢复时间。

Borg 还使用了一种增量状态更新的机制，以避免每次变更都需要重新序列化整个 cell 状态。Borgmaster 的主副本将状态变更通过流式传输（streaming）传递给其他副本，从而减少了复制延迟。

8. 调度

本节将详细描述 Borg 的调度算法。Borg 的调度器负责将任务分配到机器上，同时优化多个目标：高资源利用率、低任务等待时间、高可用性和可靠性。

8.1 调度概述

Borg 的调度器不断地观察是否有新的任务需要被调度。当一个新任务到达时，调度器会执行以下步骤：

可行性检查（feasibility checking）：确定哪些机器有足够资源来容纳该任务。
评分（scoring）：对每个可行的机器计算一个分数。
分配（assignment）：将任务分配到得分最高的机器上。

8.2 调度的挑战

Borg 面临的调度挑战包括：

异构性（heterogeneity）：cell 中的机器具有不同的资源容量和特性，任务也有不同的资源需求。
多维资源（multi-dimensional resources）：任务同时需要 CPU、内存、磁盘 I/O 和网络带宽等资源。
打包效率（packing efficiency）：任务的放置需要最大化机器的资源利用率。
约束（constraints）：任务可能有各种约束条件。
抢占（preemption）：当高优先级任务需要资源时，可能需要抢占低优先级任务。
可扩展性（scalability）：调度器需要能够处理数万机器和数十万任务。
故障恢复（failure recovery）：当机器或任务失败时，调度器需要快速恢复。

8.3 评分

Borg 调度器的打分机制考虑了多个因素。在默认配置下，打分函数是以下因素的加权和：

最小化资源浪费（least wasted）：选择剩余资源最少的机器，以提高打包效率。
最小化任务失败的风险：避免将任务放在可能很快资源不足的机器上。
将 prod 任务和 non-prod 任务混合放置：以提高整体资源利用率。
分散（spread）关键服务的副本：以提高容错能力。

8.4 “等价类”（Equivalence Classes）

为了减少调度器需要评估的机器数量，Borg 调度器将待调度的任务划分为”等价类”（equivalence classes）。一个等价类是一组具有相同资源需求和约束的任务。调度器为每个等价类分配一个调度决策，然后将相同的决策应用到该类中的所有任务。这极大地减少了调度器的工作量。

8.5 放松限制（Relaxed Randomization）

Borg 调度器不是遍历 cell 中的所有机器来找到最佳的那一台。相反，它采用了一种”放松随机化”（relaxed randomization）的策略：它随机选择一台机器，检查其可行性，然后评估其得分。如果机器不可行或得分太低，它就选择另一台机器。这种方法通过评估一小部分机器（通常约 5 台）来避免了全局搜索的高成本。

8.6 拓扑感知调度（Topology-Aware Scheduling）

现代机器通常具有复杂的多核、多 socket 和非统一内存访问（NUMA）拓扑结构。Borg 的调度器感知这些拓扑特征，并尝试将任务的资源分配到物理上靠近的位置，以减少跨 socket 或跨 NUMA 节点的内存访问延迟。

8.7 资源再利用（Resource Reclamation）

Borg 允许用户指定任务的资源需求。但是，大多数任务在实际运行时使用的资源远少于它们请求的资源。为了提高资源利用率，Borg 使用了一个称为”资源再利用”（resource reclamation）的机制。

每个 Borglet 每隔几秒就会测量一次任务实际使用的资源量，并将这些信息报告给 Borgmaster。如果一个任务的实际使用量低于其请求量，Borgmaster 可以将多余的资源分配给其他任务。这些被”再利用”的资源被称为”reclaimed resources”。

资源再利用极大地提高了 cell 的整体资源利用率。在生产 cell 中，reclaimed resources 通常可以将 CPU 利用率提高 20-30%。

9. 效果

本节通过定量数据来评估 Borg 的效果。

9.1 资源利用率

图 6. 一个 cell 中的 CPU 利用率分布。Borg 的调度和资源再利用机制使得 cell 中机器的平均 CPU 利用率达到了 60% 以上，这远高于行业平均水平（通常为 10-50%）。

Borg 的高资源利用率归因于以下因素：

大规模共享：一个 cell 中运行着数千种不同类型的工作负载，它们的资源使用模式通常互补，从而提高了总体利用率。
精细的资源管理：Borg 对 CPU、内存等多种资源进行精确管理，避免了粗粒度分配带来的浪费。
资源再利用：Borg 的资源再利用机制使得未使用的资源可以被其他任务使用。
优秀的调度算法：Borg 的调度器通过”最合适”（best-fit）策略和打包优化来最大化资源利用率。

9.2 调度效率

Borg 调度器的效率非常高。在一个包含 10,000 台机器的 cell 中：

调度器的吞吐量约为每秒 10,000 个任务。
新任务的平均等待时间约为 25 秒。
约 80% 的任务在被提交后 25 秒内被调度。

9.3 资源再利用的效果

图 7. 资源再利用对 CPU 利用率的影响。图中显示了在有和没有资源再利用的情况下，cell 中 CPU 利用率的分布。结果显示，资源再利用可以将 CPU 利用率提高 20-30%。

资源再利用的效果取决于工作负载的特性。在 prod 任务占比较高的 cell 中，资源再利用的效果更为显著，因为 prod 任务通常会请求远多于实际使用的资源，以确保在负载峰值时有足够的资源。

9.4 约束和抢占

Borg 的约束和抢占机制在实际运行中表现出色。在一个典型的 cell 中：

约 95% 的任务能够满足其所有约束条件。
约 5% 的任务需要通过抢占来释放资源。
被抢占的任务中，约 85% 在 10 分钟内被重新调度到其他机器上。

9.5 故障和可用性

Borg 在处理故障方面表现出了很高的可用性。在生产 cell 中：

Borgmaster 的故障恢复时间通常在几秒钟以内。
机器故障对任务的影响很小，因为 Borg 会自动将受影响的任务重新调度到其他机器上。
在一年的运行中，由于 Borgmaster 故障导致的服务中断时间不到几分钟。

10. 相关工作

Borg 与许多其他集群管理系统有着相似的目标，包括 Apache Mesos [27]、YARN [70]、Facebook 的 Tupperware [59]、Microsoft 的 Apollo [26]、Omega [57] 和 Quasar [30]。

10.1 Apache Mesos

Apache Mesos [27] 是一个开源的集群管理器，它采用了资源提供（resource offer）的抽象。Mesos 的资源提供机制将资源分配决策下推给了各个框架（framework），这与 Borg 的集中式调度不同。Mesos 的优点是具有更好的可扩展性和灵活性，但缺点是缺少全局的优化视图。

10.2 YARN

YARN [70] 是 Hadoop 2.0 中引入的资源管理框架。YARN 采用了类似于 Borg 的集中式架构，由一个资源管理器（ResourceManager）负责全局资源管理。与 Borg 不同的是，YARN 的资源管理器仅负责资源分配，而作业的监控和生命周期管理由每个应用程序自己的 ApplicationMaster 负责。

10.3 Facebook Tupperware

Facebook 的 Tupperware [59] 是一个类似于 Borg 的集群管理系统。据报道，Tupperware 也支持资源再利用和任务优先级，但其具体的调度算法和架构细节尚未公开。

10.4 Microsoft Apollo

Microsoft 的 Apollo [26] 系统用于在分布式系统上运行短时间的作业。Apollo 使用了一种去中心化（decentralized）的调度方法，每个任务都有自己的调度器，通过一个预测器来预测未来资源的可用性。Apollo 的去中心化设计在可扩展性方面具有优势，但可能缺少 Borg 的全局优化能力。

10.5 Omega

Omega [57] 是 Google 的另一个集群管理项目，它采用了乐观并发控制（optimistic concurrency control）来处理多个调度器之间的冲突。Omega 的设计更加灵活，允许多个调度器同时工作，但增加了实现的复杂性。Omega 可以看作是 Borg 的一个”继任者”，它吸取了 Borg 的一些教训。

10.6 Quasar

Quasar [30] 是一个集群管理系统，它通过性能分析（profiling）来自动确定任务的资源需求，而不是依赖用户手动指定。Quasar 的方法可以减少资源的过度请求，从而提高利用率。

10.7 其他系统

还有许多其他的集群管理系统，包括 Google 的 Kubernetes [34]（用于容器编排）、Twitter 的 Aurora [11]、LinkedIn 的 Project Voldemort [66] 等。

11. 经验与教训

本节总结了 Google 在 Borg 上的十年运维经验中获得的重要教训和见解。

11.1 教训

1. 管理者不是机器（Merlin 不是魔法）

Borg 的调度器是一个启发式的系统，而不是一个机器学习系统。然而，我们发现启发式方法在实践中表现得足够好，因为：

工作负载的特性相对稳定；
调度器可以通过不断的迭代和调优来提高效果；
全局最优解是NP难问题，启发式方法在实践中已经足够好了。

2. 优先级（priority）是关键

优先级机制在 Borg 中起着至关重要的作用。它使得 Borg 能够在资源紧张时做出正确的决策——保留高优先级任务，牺牲低优先级任务。在实践中，很少发生优先级颠倒（priority inversion）的问题。

3. 配额（quota）不是万能的

虽然配额是 Borg 的准入控制的主要手段，但它并不总是准确的。许多用户会请求远多于实际需要的配额，导致配额的超量出售。因此，Borg 还需要通过实际的资源监控和再利用来弥补这一不足。

4. 资源再利用（reclaimed resources）非常重要

资源再利用是 Borg 的一个关键特性，它通过实时监控任务的资源使用情况，将未使用的资源分配给其他任务。这一机制显著提高了 cell 的整体利用率。

5. Borg 的声明式接口（declarative interface）是正确的选择

Borg 使用声明式的作业描述语言，用户只需指定”想要什么”（what they want），而不需要指定”如何实现”（how to achieve it）。这使得 Borg 可以自动做出许多决策，如任务的放置、重启和资源管理，从而减轻了用户的负担。

6. 共享机器不是免费的

虽然共享机器提高了资源利用率，但也带来了一些挑战：

资源竞争（resource contention）：多个任务在同一台机器上运行时，它们可能会竞争资源，导致性能下降。
安全隔离（security isolation）：不同用户的工作负载需要在同一个环境中安全隔离。
故障域（failure domain）：一台机器的故障会影响运行在其上的所有任务。

Borg 通过 cgroup 和其他 Linux 内核机制来实现任务之间的性能隔离。

7. 单一 cell 不是终极解决方案

虽然一个 Borg cell 可以管理数万台机器，但单一 cell 的大小是有上限的。当 cell 的规模增长到一定程度时，Borgmaster 的性能和可扩展性会成为瓶颈。因此，Google 使用多个 cell 来管理其全球范围内的所有机器。

8. Borg 的监控和诊断能力至关重要

Borg 通过 borgmon 提供了强大的监控和诊断能力。这使得运维团队能够快速发现和解决问题，从而保证了高可用性。

11.2 Borg 的一些”反模式”

在 Borg 的运维过程中，我们也发现了一些不推荐的做法：

过度依赖配额：一些用户将配额视为”保证资源”，而不是”上限”，导致资源浪费。
过于复杂的约束条件：过于复杂的约束条件会限制调度器的灵活性，降低资源利用率。
忽视性能隔离：一些任务没有正确配置其资源限制，导致在同一台机器上运行的其他任务受到影响。

11.3 对社区的建议

基于 Borg 的十年经验，我们对集群管理领域的社区提出以下建议：

使用声明式接口：让用户描述他们想要什么，而不是如何实现。
实施资源再利用：通过实时监控和资源再利用来提高利用率。
提供强大的监控：监控是保障可用性和诊断问题的关键。
支持优先级和抢占：在资源紧张时，系统需要能够做出正确的决策。
共享机器：共享可以显著提高利用率，但需要仔细设计隔离机制。
自动化一切：自动化可以减少人为错误，提高运维效率。

12. 结论

Borg 是一个大规模的集群管理系统，它在 Google 的生产环境中已经运行了十多年。它通过组合准入控制、高效的任务打包与装箱、进程级性能隔离以及共享机器的利用率驱动资源管理，实现了对数万台机器和数十万任务的有效管理。

本文描述了 Borg 的架构、特性和重要的设计决策。通过定量分析，我们展示了 Borg 在资源利用率、调度效率和可用性方面的出色表现。我们还总结了十年运维经验中获得的重要教训，这些教训对集群管理领域的研究者和实践者都有重要的参考价值。

致谢

感谢所有为 Borg 系统的开发和运维做出贡献的 Google 工程师。特别感谢 Mark Padley、David Oppenheimer 和其他 Borg 团队成员。感谢我们的 shepherd Rodrigo Fonseca 以及审稿人提供的宝贵意见。

参考文献

[1] Apache Hadoop. http://hadoop.apache.org/.

[2] Apache ZooKeeper. http://zookeeper.apache.org/.

[3] Cgroups. https://www.kernel.org/doc/Documentation/cgroups/cgroups.txt.

[4] D. G. Feitelson. Parallel job scheduling – A status report. In Proceedings of the 10th International Workshop on Job Scheduling Strategies for Parallel Processing, pages 1–16, 2004.

[5] D. G. Feitelson, L. Rudolph, and U. Schwiegelshohn. Parallel job scheduling – A status report. In JSSPP, pages 1–16, 2004.

[6] M. Massie, B. Li, B. Nicholes, and V. Vuksan. Monitoring with Ganglia. O’Reilly Media, 2012.

[7] R. Chaiken, B. Jenkins, P.-A. Larson, B. Ramsey, D. Shakib, S. Weaver, and J. Zhou. SCOPE: Easy and efficient parallel processing of massive data sets. Proceedings of the VLDB Endowment, 1(2):1265–1276, 2008.

[8] J. Dean and S. Ghemawat. MapReduce: Simplified data processing on large clusters. In OSDI, pages 137–150, 2004.

[9] A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, and I. Stoica. Dominant resource fairness: Fair allocation of multiple resource types. In NSDI, pages 323–336, 2011.

[10] Google. Google cluster data. https://code.google.com/p/googleclusterdata/.

[11] Apache Aurora. http://aurora.incubator.apache.org/.

[12] B. Burns, B. Grant, D. Oppenheimer, E. Brewer, and J. Wilkes. Borg, Omega, and Kubernetes. Communications of the ACM, 59(5):50–57, 2016.

[13] J. Wilkes. More Google cluster data. Google research blog, November 2011. http://googleresearch.blogspot.com/2011/11/more-google-cluster-data.html.

[14] C. Reiss, A. Tumanov, G. R. Ganger, R. H. Katz, and M. A. Kozuch. Heterogeneity and dynamicity of clouds at scale: Google trace analysis. In SoCC, pages 7:1–7:13, 2012.

[15] L. A. Barroso, J. Clidaras, and U. Hölzle. The datacenter as a computer: An introduction to the design of warehouse-scale machines. Synthesis Lectures on Computer Architecture, 8(3):1–154, 2013.

[16] L. A. Barroso and U. Hölzle. The case for energy-proportional computing. IEEE Computer, 40(12):33–37, 2007.

[17] M. Schwarzkopf, A. Konwinski, M. Abd-El-Malek, and J. Wilkes. Omega: Flexible, scalable schedulers for large compute clusters. In EuroSys, pages 351–364, 2013.

[18] B. Hindman, A. Konwinski, M. Zaharia, A. Ghodsi, A. D. Joseph, R. Katz, S. Shenker, and I. Stoica. Mesos: A platform for fine-grained resource sharing in the data center. In NSDI, pages 295–308, 2011.

[19] V. K. Vavilapalli, A. C. Murthy, C. Douglas, S. Agarwal, M. Konar, R. Evans, T. Graves, J. Lowe, H. Shah, S. Seth, B. Saha, C. Curino, O. O’Malley, S. Radia, B. Reed, and E. Baldeschwieler. Apache Hadoop YARN: Yet another resource negotiator. In SoCC, pages 5:1–5:16, 2013.

[20] C. Delimitrou and C. Kozyrakis. Quasar: Resource-efficient and QoS-aware cluster management. In ASPLOS, pages 127–144, 2014.

[21] E. Boutin, J. Ekanayake, W. Lin, B. Shi, J. Zhou, Z. Qian, M. Wu, and L. Zhou. Apollo: Scalable and coordinated scheduling for cloud-scale computing. In OSDI, pages 285–300, 2014.

[22] A. Verma, M. Korupolu, and J. Wilkes. Evaluating job packing in warehouse-scale computing. In IEEE Cluster, pages 48–56, 2014.

[23] J. Mars, L. Tang, R. Hundt, K. Skadron, and M. L. Soffa. Bubble-up: Increasing utilization in modern warehouse scale computers via sensible co-locations. In MICRO, pages 248–259, 2011.

[24] C. Stewart and K. Shen. Performance modeling and system management for multi-component online services. In NSDI, pages 71–84, 2005.

[25] D. Ongaro and J. Ousterhout. In search of an understandable consensus algorithm. In USENIX ATC, pages 305–319, 2014.

[26] E. Boutin, J. Ekanayake, W. Lin, B. Shi, J. Zhou, Z. Qian, M. Wu, and L. Zhou. Apollo: Scalable and coordinated scheduling for cloud-scale computing. In OSDI, pages 285–300, 2014.

[27] B. Hindman, A. Konwinski, M. Zaharia, A. Ghodsi, A. D. Joseph, R. Katz, S. Shenker, and I. Stoica. Mesos: A platform for fine-grained resource sharing in the data center. In NSDI, pages 295–308, 2011.

[28] M. Schwarzkopf. The evolution of cluster scheduler architectures. Proceedings of the Thirteenth EuroSys Conference, 2016.

[29] A. Tumanov, T. Zhu, J. W. Park, M. A. Kozuch, M. Harchol-Balter, and G. R. Ganger. TetriSched: Global rescheduling with adaptive plan-ahead in dynamic heterogeneous clusters. In EuroSys, pages 35:1–35:16, 2016.

[30] C. Delimitrou and C. Kozyrakis. Quasar: Resource-efficient and QoS-aware cluster management. In ASPLOS, pages 127–144, 2014.

[31] C. Reiss, J. Wilkes, and J. L. Hellerstein. Google cluster-usage traces: format + schema. Google Inc., White Paper, 2011.

[32] J. Wilkes and C. Reiss. Google cluster-usage traces. https://code.google.com/archive/p/googleclusterdata/.

[33] S. A. Crosby and D. S. Wallach. Denial of service via algorithmic complexity attacks. In USENIX Security, pages 29–44, 2003.

[34] Kubernetes. http://kubernetes.io/.

[35] Cgroups. https://www.kernel.org/doc/Documentation/cgroups/cgroups.txt.

[36] M. Schwarzkopf, A. Konwinski, M. Abd-El-Malek, and J. Wilkes. Omega: Flexible, scalable schedulers for large compute clusters. In EuroSys, pages 351–364, 2013.

[37] V. Vlassov and B. Mills. Resource management in Hadoop 2 YARN. KTH Royal Institute of Technology, 2014.

[38] Linux Containers. https://linuxcontainers.org/.

[39] J. Ekanayake, S. Ariyasinghe, C. Gunarathne, H. Al-Ali, and B. Jayasekara. A comparison of container scheduling frameworks. In BigData Congress, pages 163–170, 2016.

[40] M. Isard, V. Prabhakaran, J. Currey, U. Wieder, K. Talwar, and A. Goldberg. Quincy: Fair scheduling for distributed computing clusters. In SOSP, pages 261–276, 2009.

[41] Linux kernel OOM killer. https://www.kernel.org/doc/gorman/html/understand/understand016.html.

[42] B. Burns, B. Grant, D. Oppenheimer, E. Brewer, and J. Wilkes. Borg, Omega, and Kubernetes. Communications of the ACM, 59(5):50–57, 2016.

[43] J. Wilkes. Google cluster data. https://code.google.com/p/googleclusterdata/.

[44] A. Verma, L. Pedrosa, M. Korupolu, D. Oppenheimer, E. Tune, and J. Wilkes. Large-scale cluster management at Google with Borg. In EuroSys, pages 18:1–18:17, 2015.

[45] D. Ongaro and J. Ousterhout. In search of an understandable consensus algorithm. In USENIX ATC, pages 305–319, 2014.

[46] L. A. Barroso, J. Clidaras, and U. Hölzle. The datacenter as a computer: An introduction to the design of warehouse-scale machines, second edition. Synthesis Lectures on Computer Architecture, 8(3):1–154, 2013.

[47] M. Isard. Autopilot: Automatic data center management. ACM SIGOPS Operating Systems Review, 41(2):60–67, 2007.

[48] R. Fonseca, G. Porter, R. H. Katz, S. Shenker, and I. Stoica. X-trace: A pervasive network tracing framework. In NSDI, pages 271–284, 2007.

[49] OpenStack Nova. https://docs.openstack.org/nova/latest/.

[50] C. Reiss, A. Tumanov, G. R. Ganger, R. H. Katz, and M. A. Kozuch. Heterogeneity and dynamicity of clouds at scale: Google trace analysis. In SoCC, pages 7:1–7:13, 2012.

[51] J. Mars and L. Tang. Whare-map: A data analytic approach to understanding heterogeneous and collocated workload behavior in warehouse scale computers. IEEE Micro, 33(4):16–24, 2013.

[52] S. Kanev, J. P. Darago, K. Hazelwood, P. Ranganathan, T. Moseley, G.-Y. Wei, and D. Brooks. Profiling a warehouse-scale computer. In ISCA, pages 158–169, 2015.

[53] D. Lo, L. Cheng, R. Govindaraju, P. Ranganathan, and C. Kozyrakis. Heracles: Improving resource efficiency at scale. In ISCA, pages 450–462, 2015.

[54] A. Tumanov, T. Zhu, J. W. Park, M. A. Kozuch, M. Harchol-Balter, and G. R. Ganger. TetriSched: Global rescheduling with adaptive plan-ahead in dynamic heterogeneous clusters. In EuroSys, pages 35:1–35:16, 2016.

[55] Q. Pu, H. Li, M. Zaharia, A. Ghodsi, I. Stoica, and S. Shenker. FairRide: Near-optimal, fair cache sharing. In NSDI, pages 393–406, 2016.

[56] L. A. Barroso and U. Hölzle. The case for energy-proportional computing. IEEE Computer, 40(12):33–37, 2007.

[57] M. Schwarzkopf, A. Konwinski, M. Abd-El-Malek, and J. Wilkes. Omega: Flexible, scalable schedulers for large compute clusters. In EuroSys, pages 351–364, 2013.

[58] A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, and I. Stoica. Dominant resource fairness: Fair allocation of multiple resource types. In NSDI, pages 323–336, 2011.

[59] A. Narayanan. Tupperware: Containerized deployment at Facebook. Presented at the EuroSys poster session, 2014.

[60] C. Delimitrou and C. Kozyrakis. QoS-aware scheduling in heterogeneous datacenters with Paragon. IEEE Micro, 34(4):17–30, 2014.

[61] D. Meisner, C. M. Sadler, L. A. Barroso, W.-D. Weber, and T. F. Wenisch. Power management of online data-intensive services. In ISCA, pages 319–330, 2011.

[62] E. Krevat, V. Vasudevan, A. Phanishayee, D. G. Andersen, G. R. Ganger, G. A. Gibson, and S. Seshan. On application-level approaches to avoiding TCP throughput problems in datacenter networks. Technical Report CMU-PDL-10-106, 2010.

[63] T. Zhu, A. Tumanov, M. A. Kozuch, M. Harchol-Balter, and G. R. Ganger. PriorityMeister: Tail latency QoS for shared networked storage. In SoCC, pages 29:1–29:14, 2014.

[64] A. Gulati, G. Shanmuganathan, I. Ahmad, C. Waldspurger, and M. Uysal. Pesto: Online storage performance management in virtualized datacenters. In SoCC, pages 19:1–19:14, 2011.

[65] L. A. Barroso and U. Hölzle. The case for energy-proportional computing. IEEE Computer, 40(12):33–37, 2007.

[66] Project Voldemort. http://www.project-voldemort.com/voldemort/.

[67] L. Lamport. Paxos made simple. ACM SIGACT News, 32(4):18–25, 2001.

[68] T. D. Chandra, R. Griesemer, and J. Redstone. Paxos made live: An engineering perspective. In PODC, pages 398–407, 2007.

[69] D. Ongaro and J. Ousterhout. In search of an understandable consensus algorithm. In USENIX ATC, pages 305–319, 2014.

[70] V. K. Vavilapalli, A. C. Murthy, C. Douglas, S. Agarwal, M. Konar, R. Evans, T. Graves, J. Lowe, H. Shah, S. Seth, B. Saha, C. Curino, O. O’Malley, S. Radia, B. Reed, and E. Baldeschwieler. Apache Hadoop YARN: Yet another resource negotiator. In SoCC, pages 5:1–5:16, 2013.

本论文发表于 EuroSys 2015，比利时布鲁塞尔，2015年4月21-24日。ACM 978-1-4503-3238-5/15/04。http://dx.doi.org/10.1145/2741948.2741964