Google 大规模集群管理器 Borg

Borg cells 运行异构的 workload，主要包括两部分。第一种是那些长时间运行、理论上“永不宕机”的服务，它们处理短生命周期且延迟敏感的请求（几微秒到几百毫秒之间）。这类服务一般用于直接面向终端用户的产品，如 Gmail、Google Docs 和 Web 搜索，以及内部基础设施服务（如 BigTable）。另外一种是运行几秒到几天即可完成的批处理作业，这类服务对短期性能波动不太敏感。

一个典型的 cell，一般分配 70% CPU 资源，实际使用为 60%，分配 55% 的内存资源，实际使用为 85%。

一个 cell 的机器都归属于单个集群，通过高性能的数据中心级别的光纤网络连接。一个集群部署在一个独立的数据中心建筑中，多个数据中心建筑构成一个 site 。一个集群通常包括一个大规模的 cell 和许多小规模的测试或者特殊目的的 cells。尽量避免单点故障。

排除测试 cells，一个中等规模的 cell 一般由 10k 机器组成。一个 cell 中的机器规格是不同的，诸如配置（CPU、RAM、磁盘、网络），处理器型号，性能等方面。用户无需关心这些差异，Borg 确定在哪个 cell 上运行任务，分配资源，安装程序和依赖项，并监控应用运行状况以及在运行失败时重启。

一个 Borg job 的属性包括名字、属主以及 tasks 数量。通过一些约束，可以强制 job 的 tasks 在具有特定属性的机器上运行，例如处理器架构、操作系统版本，或者外部 IP 地址。约束可以是硬约束，也可以是软约束；软约束更像偏好而不是强制要求。可以推迟一个 job 的启动时间，如在另一个 job 完成之后再启动。一个 job 只能运行在一个 cell 上。

每个 task 映射为一组运行在某台机器容器中的 Linux 进程。绝大多数 Borg workload 都不运行在虚拟机中，一方面是因为我们不想支付虚拟化成本，另一方面是 Borg 设计之初，Google 已经大量投入没有硬件虚拟化支持的处理器。task 也有属性，例如资源需求以及它在 job 中的索引。大多数 task 属性同它们的 job 一样，不过也可以被覆盖，例如提供 task 专用的命令行参数。每个资源维度（CPU 核、内存、磁盘空间、磁盘访问速率、TCP 端口等）都可以独立细粒度指定。Borg 程序会静态链接以减少对运行时环境的依赖，并组织成由二进制和数据文件构成的软件包，软件包安装由 Borg 编排。用户通过 RPC 与 Borg 交互来操作 job，最常见的是通过命令行工具、其它 Borg jobs 或监控系统。大部分 job 描述文件是用声明式配置语言 BCL 编写的；BCL 是 GCL 的变体，会生成 protobuf 文件，并扩展了一些 Borg 专用关键字。

用户可以修改一个运行中的 job 属性值并发布到 Borg，然后 Borg 按照新的 job 配置来更新 tasks。更新通常是以滚动方式完成，并且可以对更新导致的任务中断（重新调度或者抢占）的数量进行限制，任何导致更多中断的更改都会被跳过。

tasks 可以请求在被 SIGKILL 抢占之前，先通过 Unix SIGTERM 信号获得通知，以便有时间进行清理、保存状态、完成当前正在执行的请求并拒绝新的请求。如果抢占方设置了延迟上限，实际通知时间可能会更短。在实践中，大约 80% 的情况下可以送达通知。

Borg alloc （allocation 的缩写）是一台机器上的一组预留资源，可以在其中运行一个或多个 tasks；无论是否使用，这些资源都会保持分配。Allocs 可以用于为未来的 tasks 预留资源，在停止和再次启动 task 之间保留资源，也可以将不同 jobs 的 tasks 聚集到同一台机器上，例如一个 Web server 实例及其关联的 logsaver task，后者会把 server 的 URL 日志从本地磁盘复制到分布式文件系统。一个 alloc 的资源和机器资源类似，运行在同一个 alloc 中的多个 tasks 会共享这些资源。如果一个 alloc 必须迁移到另一台机器，它的 tasks 也会随之重新调度。

一个 alloc 集合和 job 很像，它是一组分配在多台机器上的预留资源。一旦创建一个 alloc 集合，就可以提交一个或多个 jobs 运行在其中。为简洁起见，通常使用 "task" 引用 alloc 或者一个顶级的 task(alloc 之外的 task) 和 "job" 来引用一个 job 或者 alloc 集合。

当到来的工作超过系统可容纳的规模时，Borg 通过优先级和配额来处理。每个 job 都有一个 priority 优先级，一个小的正整数。高优先级的 task 可以以牺牲较低优先级 task 为代价来获取资源，甚至通过抢占（杀死）后者实现。Borg 为不同用途定义了互不重叠的优先级区间，按优先级从高到低包括：监控、生产、批处理和 best effort（也称 testing 或 free）。

被抢占的 task 通常会在 cell 的其它地方重新调度，但如果高优先级 task 挤掉稍低优先级 task，后者又挤掉更低优先级 task，就可能产生抢占级联。为了消除大部分这种情况，Borg 禁止生产优先级区间内的 tasks 互相抢占。优先级表达的是在 cell 中正在运行或等待运行的 jobs 的相对重要性。 Quota 配额用于决定哪些 jobs 可以被准入调度。配额表示为一段时间内（通常为几个月）给定优先级的一组资源量向量（CPU、RAM、磁盘等）。这些值指定了用户的 job 请求在同一时间可以申请的最大资源量。配额检查是准入控制的一部分，而不是调度的一部分；配额不足的 job 会在提交时立即被拒绝。

高优先级配额比低优先级配额成本更高。生产优先级配额受限于 cell 中实际可用资源，因此提交了符合配额的生产优先级 job 的用户可以预期它会运行，前提是不受碎片化和约束影响。虽然我们鼓励用户不要购买超过实际需要的配额，但很多用户会超买，以避免应用用户增长后出现资源短缺。我们的应对方式是在较低优先级层级超卖配额：每个用户在优先级 0 都有无限配额，不过由于资源超订，这通常很难真正使用。低优先级 job 可能被准入，但因为资源不足一直处于 pending（未调度）状态。

配额分配在 Borg 之外处理，并和物理容量规划密切相关，其结果会反映在不同数据中心的配额价格和可用性上。只有具备所需优先级下足够配额的用户 jobs 才会被准入。配额机制减少了对 Dominant Resource Fairness（DRF）这类策略的需求。Borg 还拥有 capability 系统，给予某些用户特殊权限，例如允许管理员删除或修改 cell 中的任意 job，或者允许用户访问受限的内核功能或 Borg 行为，如在其 jobs 上禁用资源估计。

只是创建和放置 tasks 还不够，服务客户端和相关系统还需要能够访问到对应的服务，即使这些服务被重新调度到新的机器上。因此，Borg 会为每个 task 创建一个稳定的 "Borg name service"（BNS）名称，其中包括 cell 名、job 名和 task 编号。Borg 用这个名字将 task 的主机名和端口写入 Chubby 中一个一致且高可用的文件，该文件用于 RPC 系统查找 task endpoint。BNS 名也是 task DNS 名的基础，如用户 ubar 在 cell cc 上执行的 job jfoo 的第 50 个 task，可以通过 50.jfoo.ubar.cc.borg.google.com 访问。Borg 还会在发生变化时把 job 大小和 task 健康信息写入 Chubby，以便负载均衡器知道应将请求路由到哪里。

几乎所有运行在 Borg 上的 task 都包含一个内建的 HTTP server，用于发布 task 的健康信息和数千个性能指标（如 RPC 延迟）。Borg 监控健康检测 URL，并在 tasks 没有及时响应或者返回 HTTP 错误码时重启它们。其它数据会被监控工具追踪，展示在 dashboards 上，并在服务级别目标（SLO）违背时触发告警。

名为 Sigma 的服务提供了一个 Web 用户界面，用户可以通过它检查自己所有 jobs 的状态、查看特定 cell，或者深入查看各个 jobs 和 tasks，检查它们的资源行为、详细日志、执行历史以及最终命运。应用程序会产生大量日志，这些日志会自动轮转以避免磁盘空间耗尽，并且在 task 退出后保留一段时间以协助调试。如果一个 job 没有运行，Borg 会提供一个 "why pending?" 注释，并给出如何修改 job 资源请求以更好适配 cell 的指导。

Borg 记录所有 job 提交和 task 事件，以及详细的逐 task 资源使用信息，并将这些信息记录在 Infrastore 中。Infrastore 是一个可伸缩的只读数据存储，并且由 Dremel（Google 交互式数据分析系统）提供类 SQL 的交互式接口。数据被用于按使用量计费、调试 job 和系统故障以及长期容量规划。它也提供了 Google 集群工作负载跟踪数据。

所有的这些特性帮助用户理解和调试 Borg 以及他们的 jobs，并且帮助我们的 SREs 每人管理数万台主机。

每个 cell 的 Borgmaster 包含两个进程：主 Borgmaster 进程和一个独立的调度器。主 Borgmaster 进程处理客户端 RPC 请求，这些请求要么改变状态（如创建 job），要么提供只读数据访问（如查找 job）。它还管理系统中所有对象的状态机（如机器、tasks、allocs 等），和 Borglets 通信，并提供一个 Web UI 作为 Sigma 的备份。

Borgmaster 在逻辑上是一个单一进程，但实际上会复制五份。每个副本都在内存中维护大部分 cell 状态的副本，并且这个状态也会记录在一个高可用、分布式、基于 Paxos 的存储中，该存储位于这些副本的本地磁盘上。每个 cell 会选举出一个 master，同时作为 Paxos leader 和状态修改者，处理所有变更 cell 状态的操作，例如提交 job 或终止某台机器上的 task。master 会在 cell 启动和已选 master 失效时通过 Paxos 选举产生；它会获取一个 Chubby 锁，以便其它系统可以找到它。选举 master 并故障转移到新的 master 通常需要约 10s，但在大型 cell 中，因为部分内存状态需要重建，可能需要一分钟。当副本从中断中恢复时，它会从其它最新的 Paxos 副本动态重新同步状态。

Borgmaster 在某个时间点的状态称为 checkpoint，其形式是保存在 Paxos 存储中的定期快照加变更日志。Checkpoint 有多个用途，包括将 Borgmaster 的状态恢复到过去的任意点（例如，恢复到刚接受某个触发 Borg 软件缺陷的请求之前以便调试）；在极端情况下进行手工修复；为将来的查询构建持久事件日志；以及离线模拟。

一个名为 Fauxmaster 的高保真 Borgmaster 模拟器可以用于读取 checkpoint 文件，并包含生产 Borgmaster 代码的完整副本，以及 Borglets 的存根接口。它接收 RPCs 来进行状态机变更和执行操作，如 "调度所有待处理的任务"，我们使用它来调试失败，通过与它进行交互就好像它是一个实时 Borgmaster，利用 checkpoint 文件模拟 Borglets 重放真实交互。用户可以按步执行并观察过去实际发生的系统状态变化。Fauxmaster 还可以用于容量规划（"这种类型的新 jobs 多少适合？"），以及在变更 cell 配置前进行健全性检查（"这次变更是否会驱逐其它重要的 jobs？"）。

当提交一个 job 后，Borgmaster 会将它持久记录在 Paxos 存储中，并将 job 的 tasks 加入 pending 队列。调度器会异步扫描该队列，如果有足够的可用资源满足 job 约束，则将 tasks 分配到机器上。（调度器主要针对 tasks 操作，而不是 jobs。）扫描按优先级从高到低进行，在同一优先级内通过轮询方案调节，以保证用户之间的公平性，并避免被大型 job 阻塞队首。调度算法由两部分组成：可行性检查，用于寻找 task 可以运行的机器；评分，用于从可行机器中选择一台。在可行性检查中，调度器会找到一组既满足 task 约束、也有足够“可用”资源的机器，这些可用资源包括分配给可驱逐的低优先级 tasks 的资源。在评分中，调度器会评估每台可行机器的“好坏”。评分会综合用户指定的偏好，但主要由内置标准驱动，例如最小化被抢占 tasks 的数量和优先级，选择已经拥有 task 软件包副本的机器，将 tasks 分散到电力和故障域中，以及 packing 质量，包括把高优先级和低优先级 tasks 混布到同一台机器上，以便高优先级 tasks 在负载峰值时扩展。

Borg 最初使用 E-PVM 的一种变体进行评分，它可以跨异构资源生成单一成本值，并在放置 task 时最小化成本变化。在实践中，E-PVM 最终会把负载分散到所有机器上，为负载峰值留下余量，但代价是增加碎片化，特别是对那些需要占用大半台机器的大型 tasks；我们有时称之为 "worst fit"。

光谱的另一端是 "best fit"，它尝试尽可能紧密地填充机器。这会让一些机器没有用户 jobs 运行（它们仍然运行存储服务器），因此放置大型 tasks 会很直接；但紧密 packing 会放大用户或 Borg 对资源需求估计错误的代价。这会损害具有突发负载的应用程序，对于为了易于调度并尝试机会性利用未使用资源而声明低 CPU 需求的批处理 jobs 尤其糟糕：20% 的非生产 tasks 请求少于 0.1 个 CPU 核。

我们当前的评分模型是一个混合模型，它试图减少搁浅资源的数量，也就是那些因为机器上的另一种资源已被完全分配而无法使用的资源。对于我们的 workloads，它提供的 packing 效率比 best fit 高约 3-5%。

如果评分阶段选择的机器没有足够的可用资源来容纳新 task，Borg 会从最低优先级到最高优先级依次抢占（杀死）低优先级 tasks，直到可以容纳为止。我们将被抢占的 tasks 加回调度器的 pending 队列，而不是迁移或者休眠它们。例外情况是为 Google Compute Engine 用户提供虚拟机的 tasks 会被迁移。

Task 启动延迟（从 job 提交到 task 开始运行的时间）是一个已经受到并继续受到大量关注的领域。它的变化很大，中位数通常约为 25s。软件包安装大约占总时间的 80%：一个已知瓶颈是写入软件包的本地磁盘竞争。为了减少 task 启动时间，调度器更倾向把 tasks 分配到已安装必要软件包（程序和数据）的机器上：大多数软件包是不可变的，因此可以共享和缓存。（这是 Borg 调度器支持的唯一数据局部性形式。）此外，Borg 使用树形和类似 torrent 的协议将软件包并行分发到机器。

另外，调度器使用多种技术使其扩展到数万台主机的 cells。

Borglet 是 cell 中每个主机上运行的本地 Borg agent。它负责启动和停止 tasks；如果失败了就重启它们；通过操作系统内核设置来管理本地资源；滚动调试日志；并且汇报所在主机状态给 Borgmaster 和其它监控系统。Borgmaster 每隔几秒轮询 Borglet 以检索主机的当前状态并向其发送未完成的请求。这使得 Borgmaster 可以控制通信速率，避免需要明确的流控机制，并防止恢复风暴。

被选举的 master 负责准备发送信息给 Borglets 并且通过它们的响应来更新 cell 的状态。为了提升性能，每个 Borgmaster 副本运行一个无状态的链接分片来处理与某些 Borglet 的通信；每当 Borgmaster 选举发生时，都会重新计算分区。为了弹性，Borglet 始终报告其完整状态，但链接分片通过报告的信息和机器状态的差异来聚合和压缩此信息，以减少选定 master 的更新负载。

如果 Borglet 多次没有响应轮询信息，则将其主机标记为关闭，并重新调度主机上的 tasks。如果恢复响应，Borgmaster 会通知 Borglet 杀死那些已经重新调度的 tasks，以避免重复。Borglet 即使失去和 Borgmaster 的联系也会继续正常运行，因此即使所有的 Borgmaster 副本失败，当前正在运行的任务和服务也会保持正常运行。

我们还不确定 Borg 集中式架构的最终可扩展性限制会来自哪里；到目前为止，每次接近瓶颈时，我们都设法消除了它。一个 Borgmaster 可以在一个 cell 中管理数千台机器，并且有几个 cells 的到达率超过每分钟 10,000 个 tasks。一个繁忙的 Borgmaster 使用 10-14 个 CPU 核和最多 50GiB 内存。我们使用多种技术来实现这种规模。

早期版本的 Borgmaster 有一个简单的同步循环，用来接收请求、调度 tasks 并与 Borglets 通信。为了能处理更大的 cells，我们将调度器拆分为一个独立进程，使它可以与其它为了容错而复制的 Borgmaster 功能并行运行。调度器副本在 cell 状态的缓存副本上运行。它会重复以下流程：从被选举的 master 检索状态变化（包括已分配和 pending 的工作）；更新本地副本；执行一次调度遍历以分配 tasks；并通知被选举的 master 这些分配。master 会接收并应用这些分配，除非它们不合适（如基于过期状态），这种情况下它们会在调度器下一轮遍历中被重新考虑。这在精神上与 Omega 中使用的乐观并发控制非常相似，实际上我们最近在 Borg 中添加了为不同 workload 类型使用不同调度器的能力。

为了提升响应时间，我们添加了独立线程来与 Borglets 通信并响应只读 RPC。为了获得更高性能，我们又把这些功能分片（分区）到 5 个 Borgmaster 副本上。结合这些手段，UI 的 99%ile 响应时间保持在 1s 以内，Borglet 轮询间隔的 95%ile 保持在 10s 以内。

有几件事让 Borg 调度器更具扩展性：

Score caching （评分缓存）：评估一台机器的可行性和评分成本很高，因此 Borg 会缓存评分，直到机器或 task 的属性发生变化。例如，机器上的某个 task 终止、某个属性被修改，或者 task 的需求发生变化。忽略资源数量的微小变化可以减少缓存失效。 Equivalence classes （等价类）：一个 Borg job 中的 tasks 通常拥有相同的要求和约束，因此 Borg 不会为每台机器上的每个 pending task 判断可行性并为所有可行机器评分，而是只对每个等价类中的一个 task 做可行性检查和评分；等价类是一组具有相同需求的 tasks。

Relaxed randomization （放宽随机化）：计算大型 cell 中所有机器的可行性和分数是极大浪费的，因此调度器会以随机顺序检查机器，直到找到“足够多”的可行机器进行评分，然后在这个集合中选择最好的机器。这减少了 tasks 进入和离开系统时所需的评分和缓存失效量，并加快了将 tasks 分配给机器的速度。放宽随机化有点类似 Sparrow 的批量采样，同时还处理优先级、抢占、异质性和软件包安装成本。

在我们的实验中，从头开始调度一个 cell 的整个 workload 通常需要几百秒时间，但是在上述技术被禁用后，超过 3 天仍未完成。通常情况下，对 pending 队列的一次在线调度遍历会在半秒内完成。

我们的 jobs 有放置约束，需要处理罕见的工作负载峰值；我们的机器是异构的，并且我们会在从服务 jobs 回收的资源中运行批处理作业。因此，为了评估策略选择，我们需要一个比“平均利用率”更精细的指标。经过大量实验，我们选择了 cell compaction：给定一个 workload，通过移除 cell 中的机器，找出它最小能被装进多小的 cell，直到 workload 无法再放入为止，并反复从头重新打包 workload，以确保不会卡在某个不走运的配置上。这提供了清晰的终止条件，并便于自动化比较，同时避免了合成 workload 生成和建模的陷阱。

没有办法在生产环境 cells 上实验，但是我们使用 Fauxmaster 获取高保真模拟结果，使用来自实际生产 cells 和工作负载的数据，包括所有约束，实际限制，预留和使用数据。这些数据来自 Borg checkpoints 于周三 2014-10-01 14:00 PDT。（其它 checkpoints 也产生了类似的结果。）我们在消除特殊用途的前提下，选择了 15 个 Borg cells 进行报告，测试小型（小于 5000 主机）cells，然后对剩余种群进行取样，以在一定范围内实现大致均匀的分布。

为了保持压实 cell 中的机器异构性，我们随机选择要移除的主机。为了保持工作负载的异构性，我们保留了除特定机器（例如 Borglets） 相关的服务器和存储 tasks。对于大于原始 cell 大小一半的 jobs，我们将硬约束更改为软约束，如果它们非常"挑剔"并且只能调度在少数主机上，则允许 0.2% 的 tasks 处于等待状态。大量实验表明，这以很小的方差产生了可重复的结果。如果我们需要比原来更大的 cell，则在压实前多克隆原始 cell 几次；如果需要更多的 cells，我们只从原始 cell 克隆。

针对每个 cell 和不同随机数种子，每个实验重复 11 次。在图中，我们使用误差条显示所需机器数量的最小值和最大值，并选择 90%ile 值作为“结果” - 如果系统管理员想合理确定 workload 能否放得下，平均值和中位数并不能反映他应该怎么做。我们认为 cell compaction 提供了一种公平一致的方式来比较调度策略，并且可以直接转换为成本/收益结果：更好的策略需要更少的机器来运行相同的 workload。

我们的实验侧重于从某个时间点调度（打包）工作负载，而不是重放长期工作负载跟踪。一部分原因是为了避免应对打开和关闭队列模型困难，一部分是因为传统的完成时间指标不适用于我们的环境以及长期运行的服务，一部分是为了压实提供一个干净的信号，一部分是我们不相信结果会有显著差异，以及一部分实际问题：我们发现自己在某一时刻因为我们的实验消耗了 200000 Borg CPU 内核 – 即使在 Google 这个规模上，这也是一项非常大的投资。

在生产中，我们会故意为 workload 增长、偶发的“黑天鹅”事件、负载峰值、机器故障、硬件升级以及大规模局部故障（如供电母线槽故障）留下显著余量。图 4 展示了如果对真实世界的 cells 应用 cell compaction，它们可以缩小多少。

我们几乎所有的机器同时运行生产和非生产的 tasks：98% 的主机在共享 Borg cells 中，在 Borg 管理的整套机器中占 83%。（我们有一些特殊用途的专用 cells）

由于许多其他组织会在独立集群中运行面向用户的 jobs 和批处理 jobs，我们审查了如果我们也这样做会发生什么。图 5 显示，在中位数 cell 中，分离生产和非生产工作需要额外 20-30% 的机器来运行我们的 workload。这是因为生产 jobs 通常会预留资源来处理罕见的工作负载峰值，但大多数时候并不使用这些资源。Borg 会回收未使用的资源来运行大部分非生产工作，因此我们总体上需要更少的机器。

大多数 Borg cells 由数千个用户共享。图 6 展示了原因。对于这些测试，针对需要至少 10TiB 的内存（或 100TiB）的用户，我们将用户的工作负载分成新的 cell。我们现有的政策看起来很好：即使门槛较大，我们也需要 2-16 倍的 cells，以及 20-150% 的额外机器。再次强调，汇集资源可以显著降低成本。

但是，将不相关的用户和 job 类型打包到同一台主机会导致 CPU 竞争，因此我们需要更多的机器来补偿？为了评估这一点，我们研究了在具有相同时钟速度的相同机器类型下运行不同环境中的 CPI（每条指令的周期）如何变化。在这些条件下，CPI 值具有可比性，可用作性能干扰的一个代理，因为 CPI 加倍会使 CPU 绑定程序的运行时间加倍。数据是一周内从大约 12000 个随机选择的生产 tasks 中收集的，使用⁸³ 中描述的硬件配置基础设施计算 5 分钟间隔内的周期和指令，并对样本进行加权，以便每秒计算 CPU 时间。结果并不明确。

• 我们发现 CPI 与同一时间间隔内的两次测量正相关：机器上的总体 CPU 使用率，以及（很大程度上独立地）机器上的任务数量；向机器添加 task 会使其它 tasks 的 CPI 增加 0.3%（使用适合数据的线性模型）；将机器 CPU 使用率提高 10% 会使 CPI 增加不到 2%。但即使相关性具有显著性，它们也只解释了我们在 CPI 测量中看到的 5% 的方差；其它因素占主导地位，例如应用和特定干扰模式的固有差异^24,83。
• 将我们从共享 cells 中采样的 CPI 与应用种类较少的专用 cells 比较，我们看到共享 cells 的平均 CPI 为 1.58（σ = 0.35），专用 cells 的平均 CPI 为 1.53（σ = 0.32）– 即，共享 cells 中的 CPU 性能差大约 3%。
• 为了解决应用在不同 cells 中可能有不同的 workload，甚至可能存在选择偏差（也许对干扰更敏感的程序已经被移入专用 cells）的担忧，我们查看了 Borglet 的 CPI，它会在两种类型 cells 的所有机器上运行。我们发现它在专用 cells 中的 CPI 为 1.20（σ = 0.29），在共享 cells 中的 CPI 为 1.43（σ = 0.45），这表明它在专用 cell 中的运行速度是在共享 cell 中的 1.19 倍，尽管这会过度放大轻负载机器的影响，使结果稍微偏向于专用 cells。

这些实验证实，仓库规模的性能比较是棘手的，加强了⁵¹ 中的观察，并且表明共享并不会大幅度增加程序运行的成本。

但即使我们假设我们的结果最不利，共享仍然是占优的：由于几种不同分区方案所需要的机器减少，CPU 减速不再受到影响，共享优势适用于所有资源，包括内存和磁盘，而不仅仅是 CPU。

Google 构建了大型 cells，既允许运行大型计算，又可以减少资源碎片。我们通过在多个较小的 cells 中划分 cell 的工作负载来测试后者的影响 - 首先随机置换 jobs 并在分区间以循环方式分配它们。图 7 证实使用较小的 cells 需要更多的机器。

Borg 用户以 milli-core（千分之一核）为单位请求 CPU，以 bytes（字节）为单位请求内存和磁盘空间。（一个 core 是处理器超线程，并按不同机器类型的性能做了标准化。）图 8 显示了它们确实利用了这种粒度：请求的内存或 CPU 核数量中几乎没有明显的“甜点”，并且在这些资源间几乎没有明显的相关性。这些分布与⁶⁸ 中的分布非常相似，除了我们看到 90%ile 以及以上的内存请求略大。

提供一组固定大小的容器或者虚拟机，虽然在 IaaS（基础设施即服务）提供商中很常见，但并不能很好地满足我们的需求。为了证明这一点，我们把生产 jobs 和 allocs 的 CPU 核与内存资源限制“分桶”，也就是在每个资源维度上向上取整到最接近的 2 的幂，CPU 从 0.5core 开始，内存从 1GiB 开始。图 9 显示，这样做在中位数情况下需要额外 30%~50% 的资源。上限来自在压缩开始前把原始 cell 扩大四倍之后，仍需要把整台机器分配给无法放入的大型 tasks；下限来自允许这些 tasks 进入 pending。（这比³⁷ 报告的大约 100% overhead 要少，因为我们支持超过 4 个 buckets，并允许 CPU 和内存容量独立扩展。）

一个 job 可以指定资源 limit，也就是每个 task 应该获得的资源上限。Borg 使用这个 limit 来确定用户是否有足够的配额准入这个 job，并确定特定机器是否有足够的空闲资源来调度这个 task。正如有些用户会购买超过实际需要的配额一样，有些用户请求的资源也比 tasks 实际会使用的资源更多，因为 Borg 通常会杀死尝试使用超过请求值的内存或磁盘空间的 task，或者把 CPU 限制在其请求值内。此外，某些 tasks 偶尔需要使用其全部资源（例如，在一天的高峰时段或应对拒绝服务攻击时），但大多数情况下并不会。

与其浪费当前未被消耗的已分配资源，我们会估计一个 task 将使用多少资源，并把剩余资源回收给可以容忍较低质量资源的工作，例如批处理 jobs。整个过程称为资源回收。这个估计值称为 task 的 reservation，并由 Borgmaster 每隔几秒使用 Borglet 捕获的细粒度使用（资源消耗）信息计算。初始 reservation 设置为等于资源请求（limit）；在 300 秒之后，为了留出启动瞬态时间，它会朝着实际使用量加安全余量缓慢衰减。如果使用量超过 reservation，则 reservation 会迅速增加。

Borg 调度器使用 limits 来计算生产 tasks 的可行性，因此它们从不依赖回收资源，也不会暴露在资源超订中；对于非生产 tasks，它使用现有 tasks 的 reservations，因此可以把新的 tasks 调度到回收资源中。

如果预留（预测）错误，机器可能会在运行时耗尽资源 - 即使所有 tasks 的使用都低于其限制。如果发生这种情况，我们会杀死或限制非生产 tasks，从来不针对生产 tasks。

图 10 显示了如果没有资源回收会需要多得多的机器。大约 20% 的 workload 在中位数 cell 中运行在回收资源上。

我们可以从图 11 中看到更多的细节，其中显示了预留和使用与限制的比率。超出其内存限制的 task 将是第一个在需要资源时被抢占的 task，无论其优先级如何，因此在 tasks 超出其内存资源限制的情况下比较少见。另一方面，CPU 可以很容易地被限制，因此短期峰值可以相当无害地推动使用超出预留。

图 12 显示了发生的事情。第二周 reservations 明显更接近使用量，第三周也有一定接近，而基线周（第 1 周和第 4 周）显示出最大差距。正如预期的那样，内存 OOM 事件的发生率在第 2 周和第 3 周略有增加。在审查这些结果后，我们认为净收益超过了负面影响，并将中等资源回收参数部署到其它 cells。

我们使用 Linux chroot jail 作为同一台机器上多个 tasks 之间的主要安全隔离机制。为了允许远程调试，我们过去会自动分发（和撤销）ssh 密钥，以便用户只有在机器运行该用户的 tasks 时才能访问这台机器。对大多数用户来说，这已经被 borgssh 命令取代；该命令会与 Borglet 协作构建一个到 shell 的 ssh 连接，这个 shell 与 task 运行在相同的 chroot 和 cgroup 中，从而更严格地锁定访问权限。

VM 和安全沙箱技术用于运行 Google 的 AppEngine（GAE）³⁸ 和 Google Compute Engine（GCE）的外部软件。我们在运行每个托管 VM 的 KVM 进程⁵⁴ 中运行 Borg task。

Borglet 的早期版本具有原始的资源隔离：对内存、磁盘空间和 CPU 周期性进行事后检查，结合终止使用过多内存或磁盘的 tasks 以及积极应用 Linux 的优先级来控制使用 CPU 太多的 tasks。但是，流氓 tasks 太容易影响机器上其它 tasks 的性能，因此一些用户夸大他们的资源请求，以减少 Borg 可以与他们共同调度的 tasks 数量，从而降低利用率。由于所涉及的安全边际，资源回收可能会收回部分盈余，但不是全部。在最极端的情况下，用户请求使用专用机器或 cell。

现在，所有的 Borg tasks 运行在一个基于 Linux cgroup 的资源容器中^17,58,62，并且 Borglet 会操作容器设置；因为操作系统内核参与其中，控制能力得到了很大改善。即使如此，偶发的低层资源干扰（例如内存带宽或 L3 高速缓存污染）仍然会发生，如^60,83。

为了帮助处理过载和超配，Borg tasks 有一个 application class 或 appclass。最重要的区别在于延迟敏感（LS）appclasses 和其它 appclasses，本文中将后者称为批处理。LS tasks 用于需要快速响应请求的面向用户的应用程序和共享基础设施服务。高优先级 LS tasks 获得最佳处理，并且可以一次让批处理 tasks 暂时饿死几秒钟。

第二个划分是在可压缩资源和不可压缩资源之间。可压缩资源（如 CPU 周期、磁盘 I/O 带宽）是基于速率的，可以通过降低服务质量从 task 中回收，而不必杀死 task；不可压缩资源（如内存、磁盘空间）通常不杀死 task 就无法回收。如果机器耗尽了不可压缩资源，Borglet 会立即从最低优先级到最高优先级终止 tasks，直到可以满足剩余的 reservations。如果机器耗尽了可压缩资源，Borglet 会限制使用（支持 LS tasks），以便在不中断任何 tasks 的情况下处理短负载峰值。如果事情没有改善，Borgmaster 将从机器中删除一个或者多个 tasks。

Borglet 中的用户空间控制循环会根据预测的未来使用（针对生产 tasks）或者内存压力（针对非生产 tasks）为容器分配内存；处理来自内核的 OOM 事件；并且当 tasks 尝试分配超过内存限制时，或者当一台超配机器实际耗尽内存时杀死它们。由于需要精确的内存统计，Linux 的 eager file-caching 会显著增加实现复杂度。

为了提高性能隔离，LS tasks 可以保留整个物理 CPU 核，从而阻止其它 LS tasks 使用它们。批处理 tasks 允许在任何核上运行，但是相对于 LS tasks，它们只获得很小的调度器 share。Borglet 会动态调整贪婪 LS tasks 的资源上限，以确保它们不会让批处理 tasks 持续饿死数分钟，并在需要时选择性地应用 CFS 带宽控制⁷⁵；仅靠 shares 不够，因为我们有多个优先级级别。

和 Leverich⁵⁶ 一样，我们发现标准 Linux CPU 调度器（CFS）需要进行大量调整以同时支持低延迟和高利用率。为了减少调度延迟，我们的 CFS 版本使用扩展的 per-cgroup 负载历史¹⁶，允许 LS tasks 抢占批处理 tasks，并在多个 LS tasks 可在 CPU 上运行时减少调度时间片。幸运的是，我们的许多应用程序都使用 thread-per-request 模型，这可以减轻持续负载不平衡的影响。我们谨慎使用 cpusets 将 CPU 内核分配给具有特别严格延迟要求的应用程序。这些努力的一些结果如图 13 所示。该领域的工作仍在继续，正在增加能够感知 NUMA、超线程和功耗的线程放置与 CPU 管理（例如⁸¹），并提高 Borglet 的控制精度。

Tasks 被允许消耗资源直到其 limit。大多数 tasks 被允许在 CPU 等可压缩资源上超过 limit，以利用未使用的（slack）资源。只有 5% 的 LS tasks 会禁用此功能，可能是为了获得更好的可预测性；不到 1% 的批处理 tasks 这样做。默认情况下禁用使用 slack 内存，因为它会增加 tasks 被杀的可能性，但即便如此，10% 的 LS tasks 会覆盖这个设置，79% 的批处理 tasks 也会这样做，因为这是 MapReduce 框架的默认设置。这补充了回收资源的结果。批处理 tasks 愿意机会性利用未使用以及已回收的内存：大多数时候这是有效的，尽管当 LS tasks 急需资源时，偶尔会牺牲批处理 tasks。

我们从 Borg 的一些特征开始，作为警示故事，并在 Kubernetes 中提供有根据的替代设计。

Job 作为唯一的 tasks 分组机制，是有限制的。 Borg 没有一等方式将整个 multi-job 服务作为单个实体进行管理，或者引用某个服务的相关实例（例如 canary 和 production tracks）。作为一种 hack，用户会在 job 名称中编码服务拓扑，并构建更高级别的管理工具来解析这些名字。另一方面，也不能引用 job 的任意子集，这会导致滚动更新和 job 大小调整等语义不灵活的问题。为了避免这种困难，Kubernetes 摒弃了 job 概念，而是通过 labels 来组织调度单元（pods）- 用户可以将任意 key/value 对附加到系统中的任何对象。等价于 Borg 的一个 job，可以通过将 job:jobname 标签关联到一组 pods 实现，也可以表示任何其它有用的分组，例如 service、tier 或者 release-type（如 production、staging、test）。Kubernetes 中的操作通过标签查询来识别其目标对象并应用操作。这种方式比单个固定的 job 分组更灵活。

每个主机一个 IP 地址带来复杂性。 在 Borg，主机上的所有 task 都使用其主机的单个 IP 地址，从而共享主机的端口空间。这会导致很多麻烦：Borg 必须将端口作为资源，tasks 必须预先声明它们需要多少端口，并且声明在启动时使用哪些端口；Borglet 必须强制执行端口隔离；以及命名和 RPC 系统必须像对待 IP 地址一样处理端口。

由于 Linux 命名空间，VMs，IPv6，以及软件定义网络的出现，Kubernetes 可以采用对用户更加友好的方式，来消除这些复杂性：每个 pod 和 service 都有自己的 IP 地址，允许开发人员选择端口而不是要求他们的软件适配基础设施，并消除了端口管理的基础架构复杂性。

为了高级用户而优化，以牺牲普通用户为代价。 Borg 提供了一系列针对 "power users" 的功能，使他们可以微调程序的运行方式（BCL 规范列出了大约 230 个参数）：最初的焦点是支持 Google 最大的资源消费者，对他们来说效率提升至关重要。不幸的是，这种 API 的丰富性使得 "casual" 用户更难使用，并限制了它的发展。我们的解决方案是在 Borg 之上构建自动化工具和服务，并通过实验确定适当的设置。这些工具可以从容错应用提供的实验自由度中获益：如果自动化出错，那只是麻烦，而不是灾难。

另一方面，Borg 的一些设计特性非常有益，并经受住了时间考验。

Allocs 非常有用。 Borg alloc 抽象催生了广泛使用的 logsaver 模式，以及另一种流行模式：由一个简单的数据加载器 task 定期更新 Web server 使用的数据。Allocs 和 packages 允许这样的 helper 服务由不同团队开发。Kubernetes 中等效于 alloc 的概念是 pod，它是一个或多个容器的资源包，这些容器始终被调度到同一台机器上并可以共享资源。Kubernetes 使用同一个 pod 中的 helper 容器，而不是 alloc 中的 tasks，但思路是一样的。

集群管理不仅仅是 task 管理。 虽然 Borg 的主要职责是管理 tasks 和主机的生命周期，但在 Borg 上运行的应用程序可以从许多其它集群服务中受益，包括命名和负载均衡。Kubernetes 通过 service 抽象支持命名和负载均衡：一个 service 有一个名字和一个通过标签选择器的动态 pod 集。集群中的任何一个容器都可以通过 service 名来访问服务。在这一层上，Kubernetes 会自动对和标签选择器匹配的 pod 之间的服务连接进行负载均衡，并跟踪由于故障而重新调度的 pod。

自我检查是至关重要的。 虽然 Borg 几乎总是 "正常工作"，但当出现问题时，找到根因可能是很具挑战性的。Borg 的一个重要设计决策是向所有用户显示调试信息而不是隐藏它：Borg 拥有数千名用户，因此 "自助" 必须是调试的第一步。尽管这使得我们更难以弃用功能并改变用户所依赖的内部策略，但是它仍然是一个胜利，我们发现实际没有选择的余地。为了处理庞大的数据，我们提供了多个级别的 UI 和调试工具，因此用户可以快速识别与其 jobs 相关的异常事件，然后深入查看其应用程序和基础架构本身的详细数据和错误日志。

Kubernetes 旨在复制 Borg 的许多自我检查技术。例如，它附带了用于资源监控的 cAdvisor¹⁵ 工具，以及基于 Elasticsearch/Kibana³⁰ 和 Fluentd³² 的日志聚合。可以查询主服务器以获取其对象状态的快照。Kubernetes 有一个统一的机制，所有组件都可以用来记录事件（例如，正在调度的容器，失败的容器）以提供给客户。

master 是分布式系统的内核。 Borgmaster 最初被设计为一个单体系统，但是随着时间推移，它变得更像一个内核，位于协作管理用户 jobs 的服务生态系统的核心。例如，我们将调度器和主 UI（Sigma）拆分为单独进程，并添加了用于准入控制、垂直和水平自动扩展、重新打包 tasks、周期性 job 提交（cron）、工作流管理以及归档系统行为以供离线查询的服务。

Kubernetes 架构进一步采用了这种思路：它的核心拥有一个 API server，只负责处理请求和操作底层状态对象。集群管理逻辑则构建为这个 API server 客户端的一组小型、可组合 micro-services，例如复制控制器，它可以在出现故障时维护 pod 所需的副本数量，以及节点控制器，它管理机器生命周期。

实际上，Google 的所有集群工作负载在过去十年中都转向使用 Borg。我们会继续发展它，并将我们从中学到的经验应用到 Kubernetes。