本文是对 Large-scale cluster management at Google with Borg 的总结。

简介

Google 的 Borg 系统是集群管理系统，在它上面运行着成千上万个任务，包括各种各样的应用，运行在千上万个机器上。

Borg 的功能包括：

• 准入/权限控制
• 高效的任务调度
• 资源管理
• 进程级别的性能隔离

Borg 带来 3 个收益；

• 隐藏资源管理和错误处理，用户可以专注应用程序的开发；
• 高可靠和高可用；
• 高效的在成千上万个机器上运行工作负载。

当前云原生大红大紫的 Kubernetes 的思想就来自于 Borg。

用户视角

Borg 运行 Google 的应用和服务，用户将他们的工作（服务或者应用）以 job 的形式提交，job 由多个 task 组成，每个 task 都是由同一个二进制程序运行。每个 job 运行在一个 Borg 的 cell 里，多个机器作为一个单元来管理。

工作负载

工作负载分为两类：

• 长时间运行的服务，它们不会停下来，比如 web 服务，Gmail 等
• 批处理任务，任务执行结束后就会停止，比如 MapReduce，管理这类任务还有 YARN。

集群和 cell

一个 cell 中的多个机器，它们属于一个集群，由高性能数据中心规则的网站连接起来。一个集群活在数据中心建筑里，多个建筑构造一个站点。一个集群通常包括一个大规模的 cell，可能还有小规模的测试 cell 以及其他用户的 cell。

job 和 task

job 的属性包括名称，所属者和它的 task。job 可用限制运行在什么样的机器上，比如 CPU 架构，操作系统等等。一个 job 只运行在一个 cell 中。

每个 task 包括一个或者多个 linux 进程，它们运行在一个容器内。这与 k8s 的 pod 非常类似。Borg 没有使用虚拟机的方式来运行任务，因为虚拟机本身非常消耗资源。

每个 task 都有一些属性，包括资源需求，比如 CPU、内存、磁盘IO、TCP 端口等，它们都可以更细粒度的指定。

用户提交 job 时通过 RPC 向 Borg 发起通知。每个 job 都是通过特定领域的语言描述的，类似 k8s 的 yaml。

用户可以修改 job 的属性，然后让 borg 以滚动更新的方式让应 job 的新配置生效。

每个任务在关闭时首先会发出 SIGTERM 信号，这个时候任务自己有时间做一些清理动作，然后任务自己结束。超过一定时间任务还未结束会发出 SIGKILL 让操作系统强制杀死。

图-1 job 和 task 的状态

Alloc

Alloc 是一个机器上预留的一组资源（资源管理器），在这些资源中可以运行一个或多个任务（也就是为任务分配资源，Alloc 就是 Allocate 的简称，意思是分配）。

Alloc 的资源类似机器的资源，跑在里面的多个任务共享它们的资源。（比如在 k8s 中，给一个 pod 设置为 2G 内存，多个进程共享这 2G 内存）。

Alloc set 就像是一个 job 一样，在多个机器上预留的一组资源。如果一个 alloc set 创建后，多个任务可以运行在这组资源下。

优先级、配额和准入控制

使用优先级和配额来评估 Borg 是否可以承担得起任务运行所需的资源。

高优先级的任务可以获得的配额比低优先级的高，而且还会通过抢占低优先级任务配额的方式来满足高优先级的任务。Borg 定义了优先级带宽：monitoring, production, batch, 和 best effort 这四种。生产级别的 job 属于 monitoring 和 production 。

配额用来决定哪个任务允许调度，配额使用 CPU、RAM 资源矩阵表示，可以定义每个优先级的配额，也可以定义一个周期时间内所需要的配额。配额检查是准入控制的一部分，不属于调度。如果任务的配额不足时会立即拒绝接入。

高优先级配额要比低优先级配额消耗的多，生产级别的配额受到一个 cell 实际可用资源的限制。当用户提交了生产级别的任务时，只有满足任务所需的配额时才可能期望任务能够运行。

命名和监控

客户端如何找到 job 的那个任务来提供服务呢，是 BNS（全称是 Borg name service)，类似 DNS。BNS 包括 cell 的名字、job 的名字以及 task 的数量。Borg 将一个 task 的主机名和端口写入 Chubby 服务中（可以将 Chubby 看做是 Zookeeper），这样才能让 RPC 系统找到 task 端点（endpoint）。此外 Borg 会将 job 的大小和任务健康状态信息写入 Chubby 以便 RPC 系统可以路由到健康服务中。

Borg 通过检测每个 task 暴露的健康 HTTP 接口来判断系统是否正常工作，如果接口返回了错误或者响应不正常，则可以任务服务工作不正常了，RPC 系统就不会路由到故障节点上。

Borg 提供了日志数据卷用来存储日志，如果任务停止时，日志还会保留一段时间，方便用户排查问题。Borg 为每个 task 都详细的记录了资源使用情况、详细日志、执行历史记录和最终命运。

Borg 架构

图-2 Borg 架构

如图-2所示，Borg 的成分包括：

• 由多个机器组成的一个 cell；
• 一个逻辑上的中心化控制节点 Borgmaster；
• 运行在每个机器上的 Borglet；

Borgmaster

每个 cell 的 Borgmaster 都由两个进程组成：Borgmaster 的主进程和一个分离的调度器。Borgmaster 负责接受 RPC 请求来完成对集群状态的修改或者是读取数据。

中心化的 Borgmaster 也是多副本的，每个副本都在内存中维持一份 cell 最新的状态数据，这些数据当然也会维护在 Chubby 中（还包括它的副本和磁盘）。每个 cell 选举的单节点 master 由两个作用：作为 Paxos 的 leader 和状态修改。当 master 出现错误需要选举时可能会执行 10 秒钟，如果 cell 集群更大，则需要消耗更多的时间，因为需要在新 master 内存中重建集群状态。当一个副本从中断中恢复时，它会动态的从其他副本中再次同步状态数据。

Borg 在时间上的某个点的状态被称为检查点（checkpoint），由存储在 Chubby 上的周期性快照和更新日志组成。检查点有很多用途，包括恢复到任意时间点的状态。

Borgmaster 还有一个高保真的模拟器，称为 Fauxmaster，它可以用来读取检查点文件，并且包括与线上 Borgmaster 一样的代码逻辑和与 Borglet 交互的代码逻辑。它可以接收 RPC 请求执行操作，用来调试错误信息，就好像是跟 Borgmaster 交互一样，与模拟的 Borglet 从 checkpoint 文件中重放交互流程。

调度

当一个任务提交时，Borg 将它的状态存储在 Chubby 中，然后将 job 添加到 pending 队列中。调度器异步扫描 pending 队列作业(job)，将其任务分配在一个满足资源限制条件的机器上运行。分配算法包括两部分：可行性检查和打分。可行性分析就是找到可以运行该任务的机器，而打分就是从可行性分析得到的机器列表中再选择最合适的机器来运行任务。

打分有两种策略：worse fit 和 best fit，使用 worse fit 意味着为负载分摊到所有机器中，而 best fit 则使用紧凑的方式、尽量耗尽机器的资源。每种方法都有优缺点，Borg 使用中庸的方法，也就是给机器留下一定的资源来应对突发流量。

如果无法从打分阶段获取合适的机器来运行任务，Borg 会从优先级低到高来抢占一些任务的资源。被抢占的任务会停止运行，然后重新进入调度阶段，也就是放入 pending 队列。

为了加快任务启动的时间，Borg 会有限选择已经有该任务的二进制程序的集群，避免下载文件而耗费大量的时间。

Borglet

每台机器上都会跑一个 Borg agent，称为 Borglet。它的功能包括：

• 启动和停止任务（task）；
• 任务失败时重启任务；
• 操作 OS 内核来管理本地机器的资源；
• 滚动 debug 日志；
• 将机器状态报告给 Borgmaster；
• 上报监控数据。

Borgmaster 按照一定的速率与 Borglet 通信（获取 Borglet 机器的状态），减少网络流量，避免出现恢复风暴。为了提高性能，Borgmaster 的每个副本都以无状态分片的模式与 Borglet 通信，Borgmaster 每次选举都会重新计算分片，决定哪些副本管理哪些 Borglet。基于弹性的考虑，Borgmaster 副本收到 Borglet 完整的状态信息后，会聚合、压缩消息，并将差异信息上报给 Borgmaster。

如果 Borgmaster 没有收到 Borglet 的心跳信息（也就是未回复 poll 消息），则将这台机器标记为故障，跑在这台集群上的任务会重新调度。如果机器恢复，新调度的任务就需要停止运行。

扩展性

一个 Borgmaster 可以管理一个上千台机器的 cell，多个 cell 时每分钟可以达到 10000 个任务。Borgmaster 采用多种方法来增加性能。

为了处理更大规模的 cell，Borgmaster 将调度器独立为一个进程，它可以与其他 Borgmaster 副本功能并行的处理。一个调度器副本操作在它本地内存状态下，重复的执行：1）从选举的 master 中接收变更的状态数据，包括分配数据和 pending 队列的数据；2）更细本地内存副本信息；3）调度任务；4）通知选举的 master 关于任务分配的信息。

其他几个提高 Borg 扩展性的方法如下。

缓存打分：评估可用的机器和打分是非常昂贵的，通过缓存打分可以加快速度。

同等类别：评估可用的机器和打分应用在一批相同需求场景下，减少重复计算。

随机化：给所有机器计算可行性和打分太慢，可以随机选择一批可行的机器然后打分。

可用性

Borg 为提高可用性使用了多副本机制，虽然使用了中心化的模式，但是 master 节点通过将状态日志同步到多副本中来保证服务不中断。假如 master 挂了，其他副本会选择一个新的 master。

Borg 还使用如下技术提高可用性。

• 自动重新调度失败的任务
• 减少关联错误，将一个 job 的多个任务分发到不同错误域下，比如不同机器、不同机甲、不同电源。
• 杜绝因机器维护时让一个 job 的任务同时关闭的情况；减少任务崩溃的频率；
• 使用声明式期望状态表示法和幂等性，让失败的服务可以重新提交而不会有任何影响；
• 由于在一个大规模的 cell 中比较难以分辨机器不可达是因为网络问题还是机器故障，所以需要控制任务因为机器不可达而“挪地”的操作速率；
• 避免重复修复机器带来的任务崩溃的情况；
• 重复跑 logsaver 任务，使其可以从中间状态中恢复。

Borg 有一个关键设计就是如果 master 或者 borglet 挂了之后，正在运行的任务可以让他们继续运行。

通过这些优化，Borg 可以达到 99.99% 的可用性：因为机器故障而使用副本机制；准入控制避免超负载；使用简单的方法部署实例；使用底层工具最小化外部依赖。

利用率

方法评估

Borg 使用 cell 压缩的方式来评估调度策略的利用率，也就是通过 Fauxmaster 读取生产的日志文件来模拟线上流程，并且通过减少机器数量来记录使用率，直到刚好能满足需求。通过 cell 压缩来评估调度策略是一个比较公平和一致的方法，因为它直接反映了投入和产出。更好的策略可以使用更少的集群来满足同样的工作负载。

一般线上环境会预留一部分空间来应对突发事件、黑天鹅事件。

共享 cell

共享 cell 可以提高机器利用率，从而节省成本或开支。

比如 prod 和 non-prod 两种 cell 的共享模式。由于部署 prod 上的 task 是处理生产环境流量的，为了应对流量尖峰或者突发事件，会预留一些资源。这些资源大部分时间都不会用到。为了提高资源利用率，Borg 会回收一部分资源用来跑 non-prod 的任务。前面已经说到优先级的概念，也就是当生产环境需要更多资源时，会从低优先级（non-prod 的优先级就比 prod 的优先级低）获取，将低优先级的任务结束，释放资源。

资源池化也能有效的降低开销，比如很多 cell 都会被上千个用户共享。

Google 内部对一台机器跑着不同用户且不同类型的任务的性能影响做了研究，发现确实会受到任务类型的影响，但是影响是非常小的。相反，共享除了 CPU 外，还有磁盘、内存等资源，带来的收益更大。

大 cell

Google 创建更大的 cell，不仅可以运行大规模计算，而且还可以减少资源碎片。Google 内部通过对资源分桶和不分桶实验证明，资源分桶时需要更多的机器，而不分桶则能更好的容纳任务。

细粒度的资源请求

Borg 使用细粒度的资源管理，用户可以指定任务需要的资源，包括 CPU 核数和以字节表示内存及磁盘资源。Google 内部通过实验证明，像云厂商那种提供固定资源的场景是不适合 Google 内部的，当资源大小固定时，会使用更多的机器来满足同等规模的工作负载。

资源回收

一个作业可以指定一个资源限制：每个任务应该被授予的资源上限。这个限制被 Borg 用来决定用户配额是否足以提交任务，并且决定一台机器是否有足够的剩余资源调度任务。通常用户会申请更多资源配额，也意味着用户会为 task 设置的资源会超过 task 本身真正所需的资源大小。如果一个 task 尝试获取比请求更多的资源时，Borg 会将任务杀死。

如果当前的资源没有被真正使用，不应该浪费他们，而是将他们用于运行低优先级的任务，比如批处理任务。Borg 会估算任务会使用的资源，然后将多余的内存回收作它用，这个过程称为资源回收。

高优先级的任务只有在使用的资源超过自己指定的请求限制时才会被杀，如果高优先级任务需要更多资源时，但是当前资源无法分配时，Borg 会将低优先级任务杀死，让其释放资源给高优先级的任务使用。

隔离

前文说到机器资源共享，一台机器会运行不同用户提交的不同内容。需要一些机制阻止一个任务影响到另一个任务。

安全隔离

Borg 使用 chroot 和 cgroup 机制实现安全级别的隔离，borgssh 连接而创建的 shell 的任务会限制在一个 chroot 和 cgroup 下。

对于外部系统会使用 KVM 这种安全沙箱技术来提供更强的隔离性，KVM 是一个运行在 Borg 上的进程。

性能隔离

早起 Borglet 使用相对原始的资源隔离方式，进程出现一些任务占用或者吃掉其他任务所需要的资源，造成一些用户像把自己的任务放在一个特定的机器或者 cell 中来避免其他任务的干扰。现在 Borglet 使用 cgroup 技术可以有效控制资源隔离。

为了应对过量投入和超负荷，Borg 还使用了如下方法：

• 将任务划分为 latency-sensitive （缩写为 LS，意思是低延迟的线上用户服务）和 batch （批处理）任务，高优先级的 LS 任务会被更好的对待，而且还会从 batch 任务抢一些资源，使得 batch 任务处于饥饿状态；
• 将资源划分为可压缩（比如 CPU，磁盘 IO 带宽）和不可压缩（比如内存和磁盘空间）。可压缩的资源是基于速率的，而且可以在用杀死任务的情况下从任务中回收一些资源，这会降低任务服务的质量。而不可压缩的资源则无法在不杀任务的情况下就能回收资源的。
• 用户空间的控制，比如1）基于内存使用情况的预测来分配内存；2）在操作系统内核层面处理 OOM 事件；3）当任务使用过量资源时或者机器资源快耗尽时就将其杀死。
• 使用基于 cgroup 的调度策略，降低调度延迟。