【论文】精读笔记4-前沿-字节跳动统一调度架构Gödel-B-相关工作发展脉络梳理

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

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

系列博客：

1. Gödel-初步略读笔记
2. Gödel-相关工作发展脉络梳理
3. Gödel-研究方案梳理
4. Gödel-实验梳理

🎯需求

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

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

表1：字节跳动的工作负载分解

现状概览

管理/调度体系

行业巨头的传统体系为：资源管理、资源调度分级。

• 资源管理 resource management ： 切分资源给业务组
• 资源调度 resource scheduling ： 调度任务到切分后的资源

这种分级架构导致资源碎片和资源浪费（分配给业务组后，业务组没有利用起来）。
因此，需要使用统一的体系（资源管理+资源调度一体）进行管理调度。

调度架构

使用事实上的开源调度器并不能满足我们的所有要求，例如

• 1）Kubernetes[6]，它能为微服务提供灵活的资源分配/亲和性，但存在可扩展性问题；
• 2）YARN[31]，更适合需要复杂调度语义（即 Gang 调度）的批处理作业，但缺乏对微服务的支持。

学术界研究了不同的调度系统，如单体调度器、两级调度器和分散式多调度器，但每种调度系统在实现我们的生产目标方面都有不足之处。

• 3）单体调度器[16,19,21,30,32,34]面临高吞吐量的挑战，而且难以添加定制的调度策略。
• 4）两级调度器[20]采用资源管理器在不同调度器之间划分资源，但这种悲观的锁定方式会损害资源间的资源弹性。

为了满足超大规模的增长，一些业务部门采用了运行不同调度系统（如 Kubernetes、YARN）的方式来管理自己的计算基础架构堆栈，这造成了两大痛点：不同业务部门之间的资源日益分散，不同业务优先级的工作负载之间的资源弹性不足。不同业务群组之间的隔离（及其计算基础设施管理）导致计算资源利用效率低下，无法长期满足业务增长需求。

• 5）在 ByteDance，在 Gödel 之前，我们在同一个计算集群上同时运行 Kubernetes 和 YARN，由资源管理器在它们之间调度资源。
  • 这种方法提高了我们的资源利用率，但在调度器之间转移资源会降低弹性，影响吞吐量。
• 6）Borg[29,32]、Omega[26] 及其开源实现 Kubernetes[6] 提出的分散式多调度器（也叫状态共享调度器）可以使用不同的调度器，每个调度器都可以访问整个计算集群，并使用乐观并发控制解决调度冲突。
  • 然而，Kubernetes 解决节点级冲突是为了防止资源超用（over-commit），这在调度周期中为时已晚，会降低吞吐量和集群规模。

从我们之前的经验和学术研究中，我们发现需要建立一个统一的调度器，它可以为不同的工作负载及其调度策略提供丰富的语义支持，可以横向扩展以满足我们的吞吐量和可扩展性需求，还可以共同定位工作负载以提高资源利用率。

🪵动机

• 本节介绍了字节跳动在集群管理方面面临的挑战，我们想要实现的目标以应对不断增长的规模，以及为什么现有的集群管理解决方案无法满足我们的需求。

🪨挑战

异构性：

如表1所示，字节跳动的作业负载高度异构。例如：

• 长时间运行的服务，如内存数据库；
• 资源密集型短时工作负载，如机器学习训练任务。

这些工作负载具有不同的业务关键性。例如，

• 关键工作负载不应被抢占以确保服务质量（QoS）。
• 相比之下，非关键工作负载可以被抢占以释放资源供关键工作负载使用。

更具挑战性的是处理不同工作负载所需的拓扑约束。

• 以内存数据库、推理和推荐服务为例，它们都将在内存中保留数据。因此，为了降低内存访问延迟，对于容器而言，使用固定NUMA节点（专用或共享）是首选。

弹性：

资源业务组织架构

• 供给方：在字节跳动，我们运营着包含数十万台机器的大型集群。像许多其他行业巨头一样，我们将集群切分为为独立的计算基础设施为不同的业务组提供服务。（资源管理 resource management ：切分资源给业务组）
• 需求方：每个业务组可能都有自己的调度器来适应其特定的负载行为的资源需求。（资源调度 resource scheduling ：调度任务到切分后的资源）

问题

• 不幸的是，不同业务组的资源需求随时间变化，通常速度不同。
• 这导致资源利用率降低，集群间资源碎片化，以及由于资源弹性低（即不同集群间资源流动性差）而导致的高运营成本。

因此，需要一个统一资源管理和调度系统来提高资源利用率，改善调度性能，并降低运营成本。

吞吐量：

在字节跳动，为了服务数十亿终端用户和异构工作负载，每秒创建数千个容器，每天运行数千万至数亿个容器。
这要求我们的调度系统具有非常高的吞吐量和响应速度，以便在适当的服务器上启动任务。这个标准比今天所有现成的开源解决方案都要高。

现有研究的缺陷

Kubernetes [6]

简介：Kubernetes是跨机器集群的容器化应用程序的事实上开源编排系统。

问题1：可扩展性差

当集群扩展到数千个节点时，Kubernetes及其默认调度器会遭受性能下降。

• 我们测试了从100到5000个节点的不同集群大小的纯Kubernetes（来自开源社区的默认版本）的调度吞吐量。
• Pod提交率固定为每秒2800个Pod。如图1所示，纯Kubernetes每秒只能完成160-180个Pod的调度。
• 当集群规模超过500个节点时，由于其计算复杂性，其调度吞吐量开始下降。
• 此外，纯Kubernetes默认只能支持5000个节点。

在字节跳动，典型的集群部署范围在数万个节点，因此纯Kubernetes无法适应我们不断增长的超大规模集群。

图1：Vanilla Kubernetes 的调度吞吐量

问题2：异构负载感知差

除了其低效的调度吞吐量外，Kubernetes默认调度器缺乏对工作负载的感知，并且无法很好地调度批处理作业（例如字节跳动典型的大数据处理和机器学习工作负载）。

• 以机器学习为例，我们需要在具有相同网络前缀的一组节点上运行任务，或者在具有同质设备（例如，相同的GPU型号）的特定节点上运行任务。

问题：

• 不幸的是，Kubernetes默认调度器不提供此类功能。
• 一些社区解决方案（Kube-batch、Volcano）[4, 8]可以部分解决这些挑战。然而，这些解决方案存在其他问题，例如调度性能（例如表3）、系统稳定性和在线服务支持不足，因此它们不适合我们的生产集群。

表3：离线工作负载的调度吞吐量

问题3：拓扑感知能力差

Kubernetes调度器也缺乏拓扑感知能力。
定义：在这篇论文中，拓扑感知的概念是指调度器在将Pod放置在节点上时，应遵守资源之间的拓扑约束。

• 例如，分配给内存密集型Pod的CPU核心和内存最好位于同一CPU插槽上，以最大限度地减少内存访问延迟。

问题：

• 借助拓扑管理器、每个节点的代理，如果节点上的资源总量足够，但资源分配无法满足适当的拓扑策略，它可以拒绝Pod启动。
• 不幸的是，这发生在kubelet接受阶段，此时调度器已经做出了错误的调度决策。
• 对于其调度器来说，一个更好的行为是拥有每个节点上可用资源的拓扑信息，从而能够选择既能满足资源请求又能满足拓扑约束的适当节点。

YARN

简介：YARN是另一个用于大规模集群的资源管理和作业调度系统。

由于以下限制，YARN不适合我们快速增长的集群舰队（fleet），该舰队托管了许多异构的工作负载。

问题1：可扩展性差（吞吐量仅在批处理作业下高）

与Kubernetes相比，类似YARN的系统提供了更高的调度吞吐量[9]。

• 然而，YARN只有在运行批处理作业时才能超越Kubernetes的吞吐量。
• 此外，它不是用于调度长时间运行的在线服务的本地系统，更不用说在同一资源池中调度异构的工作负载了。

问题2：异构负载感知差

YARN可能需要与对实时处理等高需求工作负载做出妥协，并且无法跟上现代云原生工作负载的需求。

• 这些工作负载正趋向于微服务和短生命周期服务，而不仅仅是大型作业。

问题3：拓扑感知能力差

此外，YARN在隔离作业和处理依赖控制方面存在不足。YARN还缺乏资源碎片优化，导致资源利用率低。

• 根据我们在专门用于机器学习的YARN集群中的测试，该集群包含1,300个节点（每个节点8个GPU），GPU碎片率**高达30%至40%**。

结合 Kubernetes 和 YARN。

我们解决上述挑战的重要努力之一是通过在两个调度系统之间来回沟通资源供需，将 Kubernetes 和 YARN 结合起来。这种模式在业界许多科技巨头中得到广泛应用。

方案

大约两年时间里，我们经历了几个阶段，使这种方法得以实现：

• • 阶段 1：我们分别使用 Kubernetes 和 YARN 在独立的资源池中运行在线（即微服务）和离线（即批量）工作负载。
• • 阶段 2：我们实现了一个协调器，该协调器持续监控 Kubernetes 和 YARN 的资源供需情况，然后根据流量模式在两个系统之间移动资源。它还利用历史数据来做出资源分配决策。
  • 当向 YARN 添加资源时，协调器通过在节点上标记“污点”来将其从在线池中移除，以防止 Kubernetes 调度新的工作负载。
  • 同样，当将资源返回给 Kubernetes 时，协调器从这些节点上移除“污点”，使它们可用于在线工作负载。
  • 如果离线任务仍在新添加的节点上运行，Kubernetes 将无论其进度如何都将其终止。
• • 阶段 3：我们进一步改进了协调器和其他机制，使 Kubernetes 和 YARN 代理能够持续通信。
  • 两个代理分别向它们的调度器（即 Kube-Scheduler 和 YARN 资源管理器）反馈实时资源使用信息。
  • 这样，两个调度器都可以根据实际资源使用情况做出动态调度决策，以便离线工作负载可以利用同一节点上在线工作负载未使用的潜在资源。

尽管有一些早期成功，上述方法也有一些缺点。

问题1：可扩展性差

这种方法会产生重大的运营开销。

• 没有统一资源池，导致需要人工协商资源池需求。
• 例如，在准备特殊事件（如春节）高峰使用时，运营团队必须提前几周开始与多个团队协调，预测扩大资源池的估计需求，这既耗时又无法适应我们不断增长的基础设施。

问题2：异构负载感知差

其次，交换节点对在其上运行的任务是不可知的。

• 使用这种粗粒度的方法，选择驱逐的节点可能会产生级联失败（例如，驱逐运行Parameter Server的节点会使训练工作者失去所有进度）。

问题3：拓扑感知能力差

综合解决方案无法帮助放置具有专用要求的工作负载，例如更高的网络带宽、GPU或NUMA亲和力。

总结

• 上述Kubernetes和YARN的不足，以及它们的结合，激励我们追求一种新的解决方案，利用它们的优点和生态系统。与YARN相比，Kubernetes拥有更活跃的社区、更好更大的生态系统以及更广泛的应用场景。因此，如果我们能够增强其默认调度器，以实现针对各种工作负载的高性能调度、高资源利用率和可扩展性，那么一个类似Kubernetes的系统将会更好。

表2：开源解决方案的缺陷

目标

上述讨论激发我们为我们的目标集群管理解决方案设定以下目标：

统一资源池（可扩展性）

为了提高资源管理和降低运营成本，提供统一资源池至关重要。

• 最终将较小的集群及其工作负载集成到大规模统一集群中。

改进资源利用率（可扩展性+异构负载感知）

随着集群舰队规模的增加，继续优化整体资源利用率至关重要。

• 使用来自高优先级工作负载的未使用资源来协同定位低优先级工作负载将提供最佳平衡。

高吞吐量（可扩展性+异构负载感知）

随着我们将不同类别的负载协同定位（放于一起），保持至少与YARN相同的吞吐量对于短运行任务至关重要，而Kubernetes目前无法对其进行扩展。

高资源弹性（可扩展性+异构负载感知）

在字节跳动，我们努力将异构工作负载一起运行以实现更高的资源利用率，实施高资源弹性以根据需求在业务关键工作负载和低优先级任务之间转移计算资源至关重要。

拓扑感知调度（拓扑感知）

我们希望我们的调度器做出更多最优的调度决策，考虑各种拓扑约束，而不是在无法在kubelet admit操作上实现所需拓扑策略时失败Pod启动。

🚧现状

作为现代集群基础设施的一个基本组成部分，集群调度在近年来得到了广泛研究。

• 我们已介绍两种替代方案，Kubernetes和YARN，它们不符合我们的需求（如前文所述）。
• 在本节中，我们讨论了同一研究领域的其他相关工作，并简要回顾了四个类别的最先进集群编排调度器：单体调度器、两级调度器、共享状态调度器和分布式/混合调度器。

Gödel是一个共享状态调度器，取代了Kubernetes生态系统中的默认调度器。

单体调度器 Monolithic Schedulers

大量工作通过单体调度器完成，这些调度器为整个集群实现集中式调度[16, 18, 19, 21, 29, 30, 32, 34]。

• Borg[29, 32]在同一单元格中容纳“生产”和“非生产”工作负载。根据定义明确的准入控制和基于队列的高效调度器，Borg实现了显著高的资源利用率。
• Firmament[18]提出了一种通过最小成本最大流（MCMF）优化实现亚秒级放置延迟的集中式集群调度器。
• Quincy[21]将调度问题，如数据局部性、公平性和避免饥饿，编码到图数据结构中，并提出了一种标准求解器以产生优化的全局成本。
• 有些人将机器学习技术应用于统一的调度单元，以避免负面干扰和服务质量（QoS）违规[12, 13, 23, 24, 33]。

这类调度器在编排决策中，

• 优点：提供集群范围内的可见性
• 缺点：
  • 遭受复杂问题，如服务具有不同需求的异构工作负载。
  • 其次，单体调度器在扩展到我们生产中的集群规模时通常存在可扩展性问题。

两级调度器 Two-level Schedulers

• Mesos [20] 首创了这种方法，并为每个子框架提供资源。
• Twine [27] 动态地为Twine系统中的Entitlement（一个伪集群）分配资源，通过权益划分调度器。在Twine上构建了多个应用级调度器以支持批处理和机器学习工作负载。这些应用级调度器可以显著减少Twine的工作负载。
• YARN [31] 允许调度器从资源管理器请求资源。

这类调度器在编排决策中，

• 优点：能够解决单体调度器受集中式调度器的过载而导致的可扩展性问题，两级调度器通过中央协调器和独立任务调度器动态地为不同的工作负载分配资源。
• 缺点：由于缺乏全局可见性，两级调度器遭受资源碎片、负面干扰和次优问题。

共享状态调度器 Shared-state Schedulers

• 在Omega [26]中，每个调度器都有一个私有、频繁更新的副本，并做出独立的编排决策。最后，每个调度器提交其事务，并使用粗粒度或细粒度方法解决冲突。
• Nomad [7]将集群状态存储在规划队列中，并支持多个应用程序调度。
• ParSync [15]通过将全局状态分成N部分来减轻负面影响，允许调度器根据分区状态做出决定，而Gödel根据集群的总分配和吞吐量动态地在单个分区或多分区之间适应。Gödel还实现了多项增强，以减少即使单个分区时的冲突。
• Apollo [9]为每个作业分配一个调度器来管理作业的生命周期，并根据资源监控器的全局状态信息实现基于估计的调度。每当调度器同时做出竞争性决策时，Apollo乐观地推迟任何纠正操作，因为大多数冲突是无害的。

这类调度器在编排决策中，

• 优点：共享状态调度器具有全局集群视图，并使用无锁乐观并发控制来解决来自不同调度器的冲突。

Gödel是一个共享状态调度器，其中每个调度器实例共享全局状态以做出调度决策。

• [9, 15]中的调度器将全局状态分区，Gödel中每个调度器共享全局状态。
• 其次，每个调度实例支持所有调度策略，使其能够与通过吞吐量进行水平扩展的分布式多调度器[26]相比，后者运行不同调度器的一个实例。
• 最后，与在节点级别解决冲突的Kubernetes相比，Gödel在调度阶段解决冲突，显著提高了Gödel的吞吐量。

分布式/混合调度器 Distributed/Hybrid Schedulers

• Sparrow [25] 提出了一种完全分布式调度器，支持在决策中实现高吞吐量。然而，缺乏中央协调器可能会限制其调度灵活性。
• 相反，混合架构通过结合单体或共享状态设计 [10, 11, 14, 22, 28, 35] 来解决这个问题。

🧠疑问

1. 问题：在弹性部分提到两层调度架构，供给方的资源调度、需求方的任务调度，那么Godel到底是哪一侧的调度器？
   1. 如果是供给方，那么为什么需要考虑具体Pod？
   2. 如果是需求方，那么为什么会管理全局资源而非有限局部资源？
   3. 还是进行了大一统，作为供给方，但不按传统预分配资源（资源调度），而是只给出配额限制后直接调度Pod到全局资源（资源+任务调度）？
   • 回答：仔细看了弹性部分的最后一句话，突然理解了之前略读时的疑问——“统一资源管理和调度系统”的意思。按这弹性部分的最后一句话来说，上述第三种应该是比较合理的解释，这也就是统一的含义。
2. 像EuroSys'25-VMR2L一样，字节的几篇论文质量都非常高！具体体现在，论文中蕴含了很多工程实现的细节，完完全全是可落地的工作、并且能够给我这样难以接触一线的博士生提供很多业界的真实情况，描述地非常清晰。上一篇论文中是提供了很多关于VM重调度的细节，这一篇论文中是提供了很多K8s调度的细节。
3. YARN 为什么能够比 k8s 效率更高？省略了什么因素？相应地，Godel 是通过什么来提高的效率？能否复用于 volcano？
4. 相比于K8s+YARN，统一资源池为什么就可以避免运营代价？例如，还是需要人工协商以确定未来需求量情况。感觉没说清楚。
   1. 猜想A. 统一资源池后，所有信息打通，更方便自动化分析。
   2. 猜想B. K8s 和 YARN 分管的独立资源池只有 2 个大的，剩下还有很多小的集群由某些团队自行管理。当遇到大促等特殊情况时，为避免资源不够，就需要从小的集群中借用，而这是非常复杂的。（感觉这个比较靠谱）
5. 阿里巴巴在很早以前的论文就提到过在离线负载混合部署，但在字节的论文中并没有引用以对比。这是什么原因？
   1. 仔细一看发现阿里巴巴居然也是 2023 年才发表的论文，和我的记忆有些冲突，或许还需要再调研一下。
   2. 也可以精读阿里巴巴的相关工作，做印证。
6. 为什么只重点将yarn和k8s列为两大选项，它们和其它主流方法有什么区别？（例如 Mesos 之类的）
   1. 根据论文，是将这两者列为“业界实践标准”。其它调度器是学术界的成果。（可以回顾一下 Fuxi2.0 以互相印证）
7. 目标部分提了很多（吞吐量、异构感知、……），在实验部分最终用的是什么指标？
8. 对于现状分类的两级式调度类别：
   1. 对YARN的分类有争议，阿里和谷歌的论文中将YARN视为集中式架构。按我们的理解，YARN中ApplicationMaster只负责发起请求和执行任务，并不参与调度，因此应该只有YARN调度器本身负责集中式决策。
   2. 第一次看到提及Twine，非常有价值！简单浏览了下是Facebook内部的跨地域集群管理系统，发表于OSDI’20，和我们的思路基本一致：跨地域场景下两级式架构更适合。后续再进行精读。

---

---

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

🗺参考文献

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