📖《Gödel: Unified Large-Scale Resource Management and Scheduling at ByteDance》

2023 年 Virginia大学、字节跳动团队发表于 CCF-B 类云计算顶级会议 SoCC。

系列博客：
Gödel-初步略读笔记
Gödel-相关工作发展脉络梳理
Gödel-研究方案梳理
Gödel-实验梳理

🎯需求

字节跳动对生产调度系统的主要要求是在异构机器上调度各种工作负载（如表 1 所列），提高资源利用率，跟上每个计算集群不断增长的机器规模，并实现高吞吐量。

在异构机器上需要调度各种工作负载（如下表）。

🛩创新

为了应对这些挑战，我们提出了一个名为 Gödel 的资源管理和调度系统。
- 它为所有业务部门提供了一个统一的计算基础设施，以便在统一的资源池下运行各种工作负载。它将各种工作负载集中在每台机器上，以实现更好的资源利用率和弹性。
- Gödel 基于 Kubernetes（事实上的开源容器编排系统）构建，但其核心调度器使用全局共享状态调度器进行了重新发明。相应地，我们还大幅增强了其周边组件。通过替换或增强重要组件，实现适应大规模的各种工作负载。
本文的贡献如下：
- （1）我们引入了一种统一异构资源的新模式，以共同定位在线和离线工作负载，从而在超大规模上提供更好的拓扑亲和性、更高的资源弹性和更低的运营开销。
- （2）我们在 Kubernetes 的基础上设计并实现了名为 Gödel 的新型资源管理和调度系统。我们对 Kubernetes 进行了多项优化和增强，以提高调度性能。
- （3）我们在 ByteDance 的多个数据中心部署了 Gödel，这些数据中心拥有数万台机器，除了在模拟环境中进行密集测试外，我们还在实际工作负载下进行了评估。对 Gödel 的详细评估证明了它的实用性以及如何实现我们的目标。我们的结果表明，Gödel 在各种调度方案中都实现了卓越的性能和效率。
本文报告了我们使用 Gödel 的设计和实施情况。此外，本文还讨论了我们在 ByteDance 大规模生产中开发和运行 Gödel 的经验教训和最佳实践。

📊实验验证及效果

本节评估了在模拟的大规模测试环境中 Gödel 的性能。

请注意，尽管 Gödel 已在生产集群中部署了近两年，但在这些生产集群中进行密集实验以评估 Gödel 在高压下的性能是有风险的，因为它可能会对正常业务运营造成意外中断。请参阅下一节以了解我们使用 Gödel 的生产经验。

我们进行了丰富的实验，以展示 Gödel 调度器：

在单个调度器实例中与广泛使用的开源解决方案（如 Kubernetes 和 Yarn）相比的调度吞吐量性能，
以及在多个调度器实例中的可扩展性。

实验环境

通过 Kubemark 建立了测试平台，它允许我们改变虚拟节点（也称为空心节点 Hollow Nodes）的数量及其容量，以测试不同集群规模下 Kubernetes 和 Gödel 的性能。

Kubemark 的高保真模拟与生产集群的主要区别在于任务执行。
- Kubemark 在每个节点上启动一个 HollowKubelet，假装是一个普通的 Kubelet，消耗请求的计算资源，但并不真正启动任务。
- 然而，从 Kubemark 集群获得的结果与我们在生产集群中实际运行的 Gödel 调度器的性能非常接近，因为我们的测试床使用与生产集群中运行的相同构建，并应用了生产环境中的相同设置。

设置 Settings

测试平台由 40 台 Debian x86_64 服务器组成，每台服务器包含 256 个逻辑 CPU、2TB 内存和 7TB SSD 存储空间。

我们最多使用 21 台服务器作为 Kubemark 主服务器，托管 Gödel 调度器和其他相关组件，包括备份存储集群。
其余 19 台服务器作为空心节点 Hollow Nodes 虚拟托管所有创建的 Pod。
请注意，我们在这里使用了完整的设置用于评估，其中包括所有控制平面组件，这种设置能够支持由 10K - 20K 个生产节点组成的集群。
至于 Gödel 本身，4-6 台服务器（包括备份副本）就足够了。在实践中，Gödel 服务器占整个集群的比例低于 0.05%。

合成工作负载 Synthetic Workloads

我们的测试平台允许我们预先配置可部署的工作负载。为了全面了解 Gödel 在不同情况下的性能，我们沿以下维度构建了几种可配置的工作负载：

（1）我们配置工作负载中的任务类型分布，以确定哪种任务类型主导工作负载。例如，我们可以配置由 20% 在线任务和 80% 离线任务组成的目标部署；
（2）我们可以通过配置总体 Pod 数量和提交截止日期来测试不同工作负载提交率。

基准 benchmark 会根据配置统一提交作业。

性能指标 Performance Metrics

我们使用调度吞吐量作为主要的性能指标。

调度吞吐量是指每秒分配到首选资源槽的任务数。
- 由于调度器的责任是找到最合适的节点来运行 Pod，因此调度吞吐量计算公式为每秒在集群中成功创建的 Pod 数量。

我们还报告冲突的数量以分析多个调度器实例的性能。

请注意，基于 Kubemark 的测试床主要用于评估调度器性能；它不会在集群中执行生产工作负载。
因此，诸如资源利用率和资源弹性之类的指标无法在此（模拟实验）报告。
- 但是，我们将在下一节中展示在生产集群中观察到的这方面结论。

可扩展性 Scalability

在线工作负载 Online Workloads

单调度器实例

如 Gödel-相关工作发展脉络梳理所述，Kubernetes默认调度器仅支持在线工作负载，并且存在可扩展性问题。因此，我们首先通过运行以在线作业为主的负载来评估单个 Gödel 调度器实例的性能。

我们将Pod提交率配置为每秒2800个Pod，这足以使单个调度器饱和。
我们逐步将集群大小从100个节点调整到20,000个节点，以观察对调度器的可扩展性影响。

【左-图5】单调度器下的吞吐量对比（作业提交速率为每秒2800个pod）。【中-图6】不同 Gödel 调度器实例下的吞吐量。【右-图7】混合工作负载下的 Gödel 调度吞吐量

图5显示了Gödel调度器和Kubernetes默认调度器的调度吞吐量。

整体：即使只有一个调度器实例，Gödel在调度吞吐量方面仍然比纯Kubernetes高出10倍。
K8s：在500个节点的集群中，Kubernetes的调度吞吐量达到最佳结果，而当集群大小超过5000个节点时，Kubernetes默认调度器不再正常工作。
Gödel调度器：在5000个节点时达到每秒2600个Pod的最佳吞吐量；然后，由于单个实例的不足，调度器的吞吐量开始下降。
- 与Kubernetes只能支持最多5000个节点不同，Gödel即使在20,000个节点的集群中也能获得可接受的性能。
K8s+KubeBrain：当集群大小在5000个节点或更小时，其调度吞吐量几乎是原生K8s（使用ETCD）的两倍，即使集群扩展到10,000-20,000个节点，它仍然表现良好。
- Kubernetes难以支持更大集群的一个基本原因是其存储后端（即ETCD）的不足。
  - 为了解决这个问题，字节跳动为Gödel开发了一个名为 KubeBrain 的高吞吐量存储后端，以替换ETCD来存储系统元数据。在2022年夏季，我们开源了KubeBrain。
  - 为了公平比较Gödel与Kubernetes，我们将Kubernetes连接到KubeBrain并重新运行了之前的测试。
  - 图5中的橙色条显示了使用KubeBrain作为支持存储的Kubernetes的调度吞吐量。
- 然而，即使使用KubeBrain，它也只能达到Gödel约1/10的调度吞吐量。

总结而言，相比之下，Gödel即使在只有一个调度器实例的情况下，也能为大规模集群的编排提供更高的容量。

多调度器实例

Gödel 被设计为一个分布式调度系统，可以同时运行多个调度实例以提高整体调度吞吐量。

这个特性对我们业务至关重要，因为我们每天可能操作数百万个新Pod。
为了评估多实例调度的性能，我们将调度实例从1个增加到6个；
在一个10,000节点集群中；
运行与上次测试相同的压力测试设置，并将Pod提交率增加到每秒10,000个Pod，以使多个调度器实例达到饱和状态。

为了展示调度实例之间的冲突，这次测试中

禁用了“分片模式 sharding mode”（如 Gödel-研究方案梳理所述，每个调度器实例只能在其拥有的分区中寻找可行节点，以降低冲突率）。
相反，每个调度实例可以从中寻找整个集群中最合适的节点。

如图6所示，

当2个调度实例同时运行时，调度吞吐量显著提高。
然而，加速并不是线性的。当运行3-5个实例时，整体吞吐量略有增加。
然后，当添加第6个调度实例时，观察到轻微的退化。
- 原因：同时运行的实例数量越多，冲突数量就越多（冲突数量参考图6中的蓝色线）。
  - 冲突是由于多个调度实例试图在节点上消耗相同的资源槽位。
  - 因此，只有一个请求成功，其他请求将被拒绝并重试。
  - 因此，重试次数与冲突成正比。
  - 高冲突率会负面影响调度吞吐量。
- 我们正在研究“节点洗牌 node shuffling”等解决方案来解决这个问题。我们将在未来的工作中展示其有效性。

离线工作负载 Offline Workloads

Kubernetes 允许运行自定义调度器以满足特定需求。例如，k8s-volcano 是 Kubernetes 社区广泛使用的离线作业调度器。

在本实验中，它被选为 YARN 和 Gödel 的对手；
在 10,000 节点集群中评估离线作业调度的性能；
与先前的案例类似，Pod 提交率仍然是每秒 2800 个 Pod。
- 离线作业通常以组group为单位部署，其中所有作业都具有相同的资源亲和性或必须同时满足。
- 在本测试中，组group大小设置为 10。

表 3 显示了评估结果。

与 k8s-volcano 相比，Gödel 调度吞吐量显著更高（约 162 倍）。
即使与擅长调度离线工作负载且已用于此类工作负载超过 10 年的 YARN 相比，Gödel 的吞吐量也几乎翻倍。

工作负载感知调度 Workloads-Aware Scheduling

异构工作负载混合时的统一调度

字节跳动生产环境中的工作负载高度异构。为了验证 Gödel 是否能够在统一资源池中调度在线和离线作业，并研究工作负载类型对 Gödel 调度器的影响，我们调整了提交请求的在线/离线百分比。

我们将提交请求中在线服务的百分比分别设置为 0%、25%、50%、75% 和 100%**，其余工作负载为离线作业**。
基于这两种负载的配置，我们按比例调整活跃调度器的数量，以反映调度并发性的实现情况。
我们在一个 10,000 节点集群中尝试了不同的在线/离线组合。

如图 7 所示，我们观察到 Gödel 可以很好地处理在线和离线作业。

调度吞吐量非常稳定，这意味着 Gödel 可以支持异构工作负载，并且不受工作负载混合的影响。
这项测试只使用了一个调度器实例，但我们还观察到使用多个调度器实例时也有类似的结果。

拓扑感知调度

此外，为了验证我们能否从上述拓扑感知调度（将特殊需求POD放置在相同节点上，例如，分配给内存密集型POD的CPU内核和存储器优先位于同一CPU插槽上，以便将内存访问延迟最小化）中受益，让我们评估在有和无拓扑亲和力情况下的应用级性能。

以我们的推荐服务为例，它利用AML模型向客户发送准确的广告。为了确保高响应性，预训练模型存储在内存中。
对于此服务，使用专用CPU集和固定NUMA节点启动Pod会更合适。

Gödel适用于此场景，在做出调度决策时，它能够选择具有足够的CPU/内存资源和适当资源分配的节点。为了展示拓扑亲和力的好处，我们：

在一个真实测试集群中（没说有多少个节点）；
创建了100个8核-80GB的Pod；
每个物理节点有96个逻辑CPU核心和1024GB内存。

表4显示了有和无拓扑感知的数据获取延迟。

具有拓扑感知的Gödel能够将平均和P99延迟分别降低21%和22.8%。
请注意，这些延迟结果是从一个托管真实节点和流量的推荐服务集群收集的，而不是空容器。

消融实验-优化贡献 Optimization Contributions

为了显著提高Gödel在Kubernetes上的性能，我们除了将其改为分布式而非单实例调度器外，还进行了一系列优化（例如，可行节点缓存和降低评分百分比）。优化细节在 Gödel-研究方案梳理中已进行了说明。

我们评估了这些优化，并在本节中展示了每个优化贡献了多少。在这个实验中，

我们再次运行了图5所示的压力测试。
部署模板中的90%的Pod配置了相同的资源请求，这接近我们在生产集群中观察到的结果。

这个实验在一个配置了一个调度实例的10,000节点集群中进行。我们也观察到了多个调度实例场景下类似的结果。

从图8我们可以看出，可行节点缓存和降低评分百分比的组合对性能的提升**贡献超过90%**。

图8(a)分别显示了启用Gödel全功能、禁用可行节点缓存和禁用降低评分百分比时的调度吞吐量。
图8(b)显示了相应的贡献分解。
- 对于任何集群规模，可行节点缓存在性能优化中始终发挥着关键作用，其贡献占到了性能提升的60%以上。
- 降低评分百分比的贡献**接近30%**。

Gödel 生产环境经验与教训 PRODUCTION EXPERIENCES AND LESSONS LEARNED

统一调度带来更好的弹性与资源利用率

在字节跳动，大多数长期运行的工作负载运行在Kubernetes上，而短期批处理工作负载之前运行在YARN上。通过统一调度，Gödel通过将它们共置于每台机器上并自动在这些工作负载之间转移资源，为不同的工作负载提供了更好的资源弹性。

例如，在春节期间，长期运行的微服务的峰值使用量增加。
- 传统方案下，运维团队需要提前通过从YARN资源池重新分配机器，增加长期运行服务的资源池天数。
- Gödel提供了一个统一的资源池，其中跨工作负载的资源调配无缝、透明且按需，这提高了资源管理并减少了运营开销。

在图9中，我们看到

在2022-08-02早上7点左右，集群的在线负载增加，Gödel调度器自动撤销（withdraws）了尽力而为（best-effort）的资源，并驱逐了较低优先级的离线任务。
在2022-08-03凌晨3点左右，看到在线负载减少，Gödel调度器自动回收（reclaims）了尽力而为（best-effort）的资源并重新启动了低优先级的离线任务。
上述两个转换在几分钟内无缝完成，无需人工干预。

在 Gödel 之前，在我们的生产中，我们

实现了一个附加控制器来监视长时间运行的工作负载的未使用资源（参见 Gödel-相关工作发展脉络梳理）。
这些未使用资源提供给YARN以运行低优先级的可抢占工作负载。
然后，随着在线工作负载需求的增加，相同的资源通过驱逐（evicting）低优先级工作负载重新分配（reassigned）给Kubernetes。
- 采用这种方法，我们在共享集群中提高了CPU利用率至60%**，相比之下，行业平均CPU利用率不到30%**。
然而，如果资源返回缓慢、并且很少的正在进行的批量任务可以主动终止，有时会遭受尾部延迟的严重影响。

在生产中推出 Gödel 调度器后，我们

迅速在运行微服务、流、机器学习、有状态应用程序等工作负载的包含数万个节点的集群中实现了高达60%的CPU利用率（图10）。
此外，通过 Gödel 调度器在同一位置共存不同的工作负载类型（co-locating different workload types）并限制工作负载（throttling workloads in place），可以降低被驱逐的概率，更高的吞吐量有可能转化为增加的资源利用率。

更好的装箱算法有助于减少碎片化

在Gödel中实现更好的装箱算法有助于减少 GPU Pod 在机器学习工作负载中的碎片化。

之前使用YARN时，由于碎片化问题我们损失了30%的可分配容量，
而现在这一数字**已经减少到10%**，如图11所示。

其它经验教训

经验教训：在向 Gödel 迁移的过程中，我们遇到了一些挑战，并汲取了以下经验教训。

当集群分配超过60%**时，我们观察到具有数千个Pod的作业冲突率很高**。
- Gang调度或co-scheduling协同调度不允许碎片，这意味着在M个节点上同时调度N个Pod的“全有或全无”方法。
- 我们在调度器中实现了添加非保留缓冲节点（non-reserved buffer nodes，拿一些节点作为缓冲）的功能，当冲突阻止群组中所有Pod调度时，绑定器可以使用这些节点。
实例越多并不一定越好。
- Gödel支持运行多个调度器实例以提高调度吞吐量。
- 过度的调度并发（例如，> 5个实例）可能导致高冲突，从而导致吞吐量和调度质量次优。
为了进一步提高调度吞吐量，我们在调度器和绑定器实例中添加了对并发的支持，以便每个实例可以运行多个调度/绑定线程。这对于提交给单个调度器实例的群组作业尤其有影响。
更建议向用户展示简化和有限的调度状态。我们使用了一个复杂的有限状态机来跟踪中间调度状态。复杂的状态转换使用户感到困惑，并容易错误地取消作业部署。
不时地，值班人员会收到用户的查询，“为什么我的作业没有被调度？”为了减轻操作开销，我们添加了智能跟踪，它捕获有关每个硬约束评估的节点、结果、Pod抢占统计、队列配额、实时节点指标等信息。信息被汇总并易于用户查询。

⛳️未来机会

未来还有很大的改进空间。

目前，dispatcher、scheduler 和 binder 使用的过渡阶段（transitory stages）都是在 ETCD 中（通过 API Server）持久化的。我们正在研究使用内存缓存来处理过渡状态，预计其扩展能力将超过 ETCD，吞吐量也将提高近一倍，达到每秒 10,000 个 pod。
此外，Gödel 调度程序的设计基于乐观并发控制，降低冲突率对提高吞吐量至关重要。目前，我们观察到的冲突率平均为 1%**，而在最糟糕的情况下（集群分配率超过 90%）为 5%。我们的目标是实现 0.1% 的冲突率**。
此外，我们还在努力将节点和 pod 智能分配（dispatching）到不同的调度器，以减少冲突并更好地平衡各调度器之间的负载。
最后，我们正在积极研究并在生产中部署Gödel重调度程序。重调度器用于监控正在运行的 pod，并采取抢占式行动来减少碎片和资源争用，从而为关键工作负载实现更高的服务质量。重调度程序中实施的一些措施包括对突发工作负载的 CPU 和内存利用率进行节流，平衡集群以实现统一的网络和功耗，以及减少高分配集群中的碎片问题。
多调度器并行导致高冲突，可通过“节点洗牌 node shuffling”等解决方案来解决这个问题。我们将在未来的工作中展示其有效性。

🧠疑问

实验环境-为什么用Kubemark？和Kind或Kwok相比有什么优势？
实验环境-“首选资源槽 preferred resource slots”如何定义？如果出现冲突后重调度到次选资源槽，还能够算调度吞吐量吗？
- 可能只是笔误，按后续说明，计算方式为“每秒在集群中成功创建的 Pod 数量”。
可扩展性在线工作负载实验-图5中，Gödel为什么在[100,5000]范围内吞吐量逐渐提高？是因为瓶颈为“资源量”，所以无处可调度导致的吞吐量限制？
- 根据后续消融实验，可能是因为资源量大时caching更有效（资源量小时在cache中找不到资源就需要重新计算）。
可扩展性在线工作负载实验-为什么不能无限增加调度器？调度器多会有哪些方面的负面影响、尤其是在实践方面？
- 在生产经验和教训中总结，只提到了“可能导致高冲突，从而导致吞吐量和调度质量次优”。
可扩展性在线工作负载实验-“节点洗牌 node shuffling”、“分区 partition”和“分片 sharding”之间的区别是什么？各有什么优劣？
可扩展性离线工作负载实验-Volcano的表现为何如此差？感觉和日常认知并不一致，且未说明Volcano和YARN之间的区别。
可扩展性离线工作负载实验-相比在线作业调度效率的2600，离线作业调度效率为何只有不到2000？是因为gang调度的相互依赖导致连锁失败反应？
工作负载感知-统一调度实验-未说明总Pod数量，是什么原因？虽然影响不太大。
工作负载感知-拓扑感知调度实验-未说明有多少个节点，是什么原因？这可能会影响结果。
消融实验-实验配置说的是“90%的Pod配置了相同的资源请求”，但前文说的是“同一个用户作业的90%Pod配置了相同的资源请求”，不确定两者是否是一个意思（前者假设更强，意味着所有用户所有作业的Pod都配置了相同的资源请求）。
消融实验-如何评估出的百分比？
一个可参考的数据：行业平均CPU利用率不到30%

希望这篇博客对你有帮助！如果你有任何问题或需要进一步的帮助，请随时提问。
如果你喜欢这篇文章，欢迎动动小手给我一个follow或star。

🗺参考文献

[1] Gödel: Unified Large-Scale Resource Management and Scheduling at ByteDance

Fre5h1nd's Blog

【论文】精读笔记6-前沿-字节跳动统一调度架构Gödel-D-实验梳理