【论文阅读】Gödel:Unified Large-Scale Resource Management and Scheduling at ByteDance

论文基础信息

论文地址： Gödel: Unified Large-Scale Resource Management and Scheduling at ByteDance

收录会议： 云计算顶会-ACM Symposium on Cloud Computing(SoCC2023)

作者机构： 字节跳动基础架构团队

背景

资源

大规模： 字节跳动在全球范围内运营着数十个大规模集群，每个集群包含有数十万台机器。
高异构： 数据中心内的机器也是异构的。包括不同型号的GPU、不同架构的CPU等。
资源利用率低，弹性差： 之前的做法是每个业务组都有一个独立的集群，这会导致集群的资源利用率低，出现资源碎片。同时也导致在集群之间进行资源移动时需要的运营开销高，即弹性差。

请求

• 高并发： 请求的并发是数千个容器每秒，每天运行着数千万到数亿个容器。

• 高异构： 在生成环境中包含着不同资源需求、不同服务级别协议（SLA）的异构任务，如下图所示。例如，1) 微服务​​、在线推理和数据库等关键业务服务，它们也可以抢占非关键业务的资源，2) 广泛的数据分析或机器学习 (ML) 模型训练等低优先级作业。

  注意这里提到了NUMA节点。在多CPU处理器架构中，NUMA节点中CPU有自己的内存，可以非常快速地访问自己的内存。例如对于推荐系统，推荐系统中的模型就需要存在内存中以降低获取延迟，这类任务就通常必须独占NUMA节点或者与其他非内存密集型任务共享 NUMA 节点。

调度

生产调度系统的主要要求是在异构机器上调度不同的任务，提高资源利用率，跟上每个计算集群不断增长的机器规模并实现高吞吐量。

现有的开源调度程序不能满足所有的需求。

• Kubernetes：
  • 可以为微服务提供灵活的资源分配，但是面临可拓展性问题。一方面他的调度吞吐量差，另一方面他最多也只能支持5000个节点。
  • 它也缺乏工作负载感知能力，无法很好地调度批处理作业。例如将机器学习任务放在一组共享相同网络前缀的节点上或在具有同质设备（例如相同的 GPU 型号）的特定节点上运行。虽然存在一些社区解决方案，但它们也存在一些问题，无法用于生产环境。
  • 它也缺乏拓扑感知能力，即在调度Pod时遵守Pod的资源拓扑约束。传统的k8s做法是在调度到节点后再进行资源约束的检查，更合适的做法是在调度时就考虑资源拓扑约束。
• YARN：
  • 适合复杂的批处理作业调度，但是不适用于微服务。
  • 在将作业彼此隔离以及处理依赖性控制方面存在不足。
  • 还缺乏资源碎片优化，导致资源利用率低。

学术界也有很多调度架构的研究，但是在该场景下也都存在一些问题。

• 单体式： 拓展性受限，无法解决高吞吐问题，且不够灵活，难以添加定制的调度策略。
• 两级式： 悲观的资源分配策略会损坏资源的弹性，同时存在资源碎片问题，资源利用率低。
• 状态共享式： 使用乐观并发控制来解决全局调度带来的冲突问题，其典型实现Kubernetes在调度到节点时进行冲突解决，但是这种解决方式在整个调度流程中都太晚了，降低了吞吐量和集群规模。
• 分布式/混合式： 分布式缺乏集中式调度器会限制调度的灵活性。

字节跳动在早期参考过往经验将Kubernetes和YARN组合使用，经历了如下3个阶段：

1. 分别使用 Kubernetes 和 YARN 在单独的资源池中运行在线（即微服务）和离线（即批处理）工作负载。
2. 通过一个协调器持续监控 Kubernetes 和 YARN 的资源供应和需求，然后根据流量模式在两个系统之间移动资源。它还利用历史数据来做出资源分配决策。移动资源依赖的是Kubernetes的污点机制。
3. 进一步完善协调器等机制，使Kubernetes和YARN代理能够不断地进行通信。共享实时资源信息，以便离线工作负载可以利用同一节点上在线工作负载未使用的机会资源。

但是这种组合做法仍然存在一些问题：

• 组合无助于放置具有特殊要求的工作负载，例如更高的网络带宽、GPU 或 NUMA 关联性。
• 交换节点与节点上运行的任务无关。通过这种粗粒度的方法，选择驱逐的节点可能会造成级联故障（例如，驱逐运行参数服务器的节点会使训练工作人员失去所有进度）。
• 这种方法会产生大量的运营开销。例如，为了准备春节等特殊活动的高峰使用，运营团队必须提前几周开始与多个团队协调以预测扩大资源池的估计需求，这非常耗时且无法适应我们不断增长的需求基础设施。

考虑到Kubernetes良好的社区生态，字节跳动决定在Kubernetes上构建一个新的调度系统Gödel，以解决上述问题。

创新与贡献

1. 引入了一种面向在线和离线任务调度的新范式，从而提供更好的拓扑亲和性（topology affinity），更高的资源弹性度，以及在非常大规模情况下更低的运营开销。

2. 基于Kubernetes设计并实现了新的资源管理和调度系统Gödel，并提出了对普通 Kubernetes 的一些优化和增强的方法，以提高调度性能。

3. 在字节跳动的多个数据中心实际部署了Gödel，拥有数万台机器，并在真实工作负载下进行了评估，并在模拟环境中进行了测试。结果表明了它的优越的实用性和性能。

   实践表明Gödel可以实现高达 5000 个 Pod/秒的吞吐量，同时在单个 Gödel 集群上保持约 60% 的总体资源利用率。对于内存敏感的工作负载，借助 Gödel 支持的拓扑感知调度，数据获取延迟可减少 20% 以上。此外，与字节跳动的传统部署模式相比，Gödel 可以在几分钟内（而不是几小时或几天）在关键业务服务和低优先级作业之间转移计算资源，以响应紧急流量变化，而无需人工干预。

调度系统已开源：https://github.com/kubewharf/godel-scheduler

Gödel系统架构

Gödel系统整体的设计思想与Kubernetes类似，整体架构如上图所示。由于发现Etcd可能是调度的瓶颈，故Gödel默认使用字节跳动自研的开源KubeBrain作为高性能后背存储。为了提高调度的吞吐量，Gödel调度器被设计为分布式的状态共享式调度器。Gödel的关键组件包括：

1. Dispatcher
2. Scheduler
3. Binder
4. CustomNodeResource(CNR)

Dispatcher

Dispatcher是Gödel的调度逻辑入口，它验证所有收到的作业请求，并根据资源请求和 QoS 优先级将它们存储在基于优先级的队列中，并最终将每个有效请求转发到所需的调度程序实例。

在Dispatcher中，我们使用逻辑队列来表示分配给不同业务组的资源配额，每当一个业务组提交一个部署Pod的任务请求时，就将该Pod放入到逻辑队列中，然后扣除逻辑队列的对应的可用资源。队列的排序策略支持多种。

Dispatcher还有一大功能是分区以控制调度器的冲突。初始只有一个分区，但是，在集群分配超过 90% 或吞吐量超过 2000 个 Pod/秒且多个调度器之间的调度冲突高于 1%（所有阈值均可配置）的场景下，Dispatcher 会动态对集群进行分区并分配每个调度器实例相应的一组分区。

Scheduler

Scheduler接收Dispatcher转发的作业请求，并做出调度决策（支持抢占）。Scheduler的调度单元不是单个Pod而是一个Scheduling Unit。Scheduler可以存在多个，采用状态共享式，如前所述，会受到分区调控，既可以调度到本分区也可以调度到整个集群。调度到本分区可以避免冲突，降低节点扫描开销，但是代价是调度质量的降低，还会资源碎片的存在，导致无法在本地找到所有需要的资源。系统会自动调节调度器的调度模式，例如当资源不足冲突上升时调节到只能在分区中调度。

系统还支持添加、删除调度器，但是经过实验验证，更多调度器会导致更高的调度冲突，从而导致调度器并不是越多越好。

Binder

Binder使用乐观并发控制来解决调度冲突，支持抢占、协同调度，最终将pod绑定到Scheduler选择的特定节点上。它的工作原理与 Kubernetes 默认调度程序的绑定周期类似，但处理地更快。

Binder 使用优先级队列来执行多个调度程序发送的调度决策，并按顺序处理 Pod 绑定。被拒绝的 Pod 将返回给 Dispatcher 以进行调度重试。其冲突处理的细节如下：

1. 检查节点是否有足够的资源，是否满足 Pod 的拓扑约束。
2. 对于抢占调度，如果多个Scheduler试图抢占同一个Pod，那么只满足第一个
3. 对于Gang调度，会尝试解决所有Pod的冲突，通过了就绑定所有的Pod，否则不绑定任何Pod。

CustomNodeResource(CNR)

CNR代表自定义节点资源，用以支持拓扑感知调度，集群中的每台服务器都会有一个CNR对象。每个 CNR 对象代表特定节点的拓扑和资源使用情况以及该节点上每个 pod 的拓扑。依赖这些信息，Gödel 调度器就可以在调度阶段就考虑资源拓扑约束。

Scheduling Unit

Scheduling Unit是Gödel的基本调度单元，每个Scheduling Unit包含一个或多个Running Unit。整体采取的是一个两级结构，Job是一个Scheduling Unit，Job中的pod或者subtasks是Running Unit，只有当调度器为Scheduling Unit至少Min Member个Running Units找到可用资源时，Scheduling Unit才会被标记为可调度的，否则不会有pod运行。

Min Member是一个为了应对不同类型作业所提出的一个巧妙的设计，对于需要gang调度的作业，可以将Min Member设置为所有的Running Unit数量，如果运行的是微服务作业，可以将Min Member设置为1。

目前，我们在字节跳动生产集群中一般部署三种或更多类型的应用：微服务（线上）、批处理作业（线下）和机器学习（线下）。Scheduling Unit帮助其在调度程序级别上填补在线和离线作业之间的语义差距。

此外为了平滑地将原本的YARN任务迁移到Gödel，其还创建了多种自定义资源定义（CRD）来模仿YARN的资源请求，从而将所有原本的YARN任务迁移过来。

Performance Optimization

Gödel 采用与 Kubernetes 相似的顺序来进行调度决策：
1）筛选；
2）打分，确定优先顺序；
3）选择节点。

但是Gödel在这个基础上做了一些优化：

1. 缓存可行节点： 我们观察到，来自同一用户的一项作业的大约 90% 的部署 Pod 通常具有相同的资源请求。例如，社交媒体团队可能要求运行 20,000 个 HTTP Web 服务器，每个服务器有 4 个 CPU 和 8GB 内存。因此在筛选和打分阶段确定的Node也可以用于相同的后续Pod，直到节点状态改变。
2. 降低打分百分比： 扫描集群中的所有节点并进行打分十分耗时，基于调度质量和调度耗时之间的衡量，调度器在筛选步骤中选择（Scheduling Unit+50）个可行节点。
3. 丰富评分插件： Gödel 调度器允许通过实现不同的评分插件来定义特定于工作负载的评分策略。

实验

实验通过Kubemark构建了测试平台，测试平台由 40 台 Debian x86_64 服务器组成，每台服务器包含 256 个逻辑 CPU、2TB 内存和 7TB SSD 存储。我们使用多达 21 台服务器作为 Kubemark 主节点来托管 Gödel 调度程序和其他相关组件，包括后备存储集群。其余 19 台服务器充当空心节点，虚拟托管所有创建的 Pod。

可拓展性测试

在线工作负载测试

只使用单调度器，固定Pod的提交速率为2800Pod/s（使得单调度器基本饱和），将集群节点数量从100提高到20000，对比Gödel、Kubernetes、更改Etcd为Kubebrain的调度性能，结果如上图3中的图5所示，可以看到Gödel的性能遥遥领先，且在2w的节点下仍然能够保持高吞吐量。

多调度器测试

在1w个节点上，将Pod提交速率提高到10000Pod/s（使得多调度器基本饱和），禁用了分区模式，调度器在整个集群中调度，结果如上图中的图6所示，可以观察到加速不是线性的，因为运行的调度器越多也就会导致冲突越多，目前也正在研究节点改组等解决方案来解决这个问题。

离线工作负载测试

在1w个节点中，固定Pod的提交速率为2800Pod/s，将Gödel与Kubernetes-volcano（k8s社区中用于离线作业调度的调度器）、YARN进行对比，结果如上图所示，已经可以看的Gödel的性能优势。

在离线混合工作负载测试

在1w个节点中，将提交中在线服务的比例分别更改为0%、25%、50%、75%和100%，其余工作负载为离线作业。测试结果如上图中的图7所示，Gödel的调度性能非常稳定。

拓扑感知调度测试

为了验证我们是否可以从上述拓扑感知调度中受益，我们评估了具有和不具有拓扑亲和性的调度器的性能。我们采用不同的调度器调度需要调度到NUMA节点的推荐任务，然后测试调度后各个任务的数据获取延迟，结果如上图所示，可以看到Gödel能够将平均延迟和 P99 延迟分别减少 21% 和 22.8%。

性能优化分析测试

为了得到性能优化中缓存可行节点和降低打分百分比这两个操作的优化收益，我们重复运行了在线工作负载测试，然后结果如上图所示，可以看到，可行的节点缓存和降低评分百分比合计贡献了90%以上的性能提升。

生产经验

Gödel已经实际部署在了字节跳动的生产集群中。上图图9展示了在2022年8月2号时，随着上午7点在线工作负载的增加，Gödel调度器自动撤回尽力而为的低优先级离线作业的资源，然后在凌晨3点左右又自动将多余的资源分配给了尽力而为的低优先级离线作业。两个转换在几分钟内无缝完成，无需人工干预。

在上图10展示了Gödel的集群资源利用率，可以看到其高达60%，而行业平均利用率不到30%。

在 Gödel 中实施更好的装箱算法有助于减少机器学习工作负载的 GPU Pod 碎片。之前使用 YARN 时，由于碎片问题，我们损失了 30% 的可分配容量，现在已减少到 10%，如上图 11 所示。