原文见 osdi24-choudhury.pdf

背景

Meta 内部存在数十个分布在世界各地的数据中心，起初由用户选择一个数据中心来上传训练数据并运行 ML 任务，慢慢发现不同的数据中心资源利用率差距会非常大，比如某些数据中心可能排着长长的队，而某些数据中心闲得要死，导致严重资源浪费。所以 Meta 设计了一套跨 Region 的调度系统 来解决这个问题，全名为 ML Application Scheduler on Twine，缩写为 MAST，Twine 是 Meta 20 年发的一篇论文，可以理解为 MAST 的单 Region 版本。

挑战

MAST 主要面临以下两个挑战：

三个原则范围解耦（Scope decoupling）穷尽搜索（Exhaustive search）架构

为了应对可扩展性的挑战，MAST 引入了三级调度的结构：全局 ML 调度器（GMS）-> 区域 ML 调度器（RMS）->集群管理（CM）。慢速路径除了管理数据放置外，还通过管理动态集群的机器限制 RMS 的可用机器搜索范围。可以看到 ML 集群和非 ML 集群是隔离的，由不同的调度器负责调度。

GMS 负责全球范围内的任务队列管理，资源分配由 RMS 在 Region 内部决策，容器编排由 CM 在最小的动态集群范围内进行决策。这种方法允许作业队列管理和资源分配在更大的范围内操作，以最小化闲置资源并优化作业的分配。

多个 RMS 可以在不同 Region 并发计算一个作业的资源分配计划，每个 RMS 会给出该计划的成本，最终通过拍卖决定最佳计划。

RAS 负责动态集群（Dynamic Cluster）的机器分配，支持灵活的机器管理策略，这样 RMS 只需要专注于调度逻辑，从而实现与节点管理逻辑解耦。通常 ML 动态集群会同时包含 GPU 机型和 CPU 机型。动态集群的机器分配被抽象为一个 MIP 问题，问题输入为 Region 内所有机器和每个动态集群的预期大小和硬件规格，RAS 每 30 分钟（可配）重新分配机器，当新数据中心上线时，RAS 会逐步将动态集群的机器分散到这些新数据中心，来减少应对数据中心故障所需的缓冲区大小。

还有一点值得注意的是，Meta 内部有多个调度器，这样不同的调度器可以针对不同的场景进行优化：Shard Manager 负责有状态服务的调度，主要优化数据库的高可用；Chronos 负责分析任务调度，主要优化高吞吐；MAST 负责 ML 任务调度，主要优化调度决策质量。

数据放置（慢速路径）

数据仓库存储着 EB 级别的数据，采用三级层次结构：Namespace（百） -> Table（百万） -> Partition（十亿）。每个 Partition 一旦创建就不可更改，但可以向现有表中添加新 Partition。例如，"user_activity" 表每天会添加一个新的 Partition 来记录过去 24 小时的用户活动。Partition 同时被用于机器学习训练和数据分析（如 Spark 和 Presto），一个名为 Tetris 的系统会根据 Spark 和 Presto 任务的放置计划优化跨区域的数据放置。

每个表都有一个主 Region，即生成其新数据的地方，但可以在其他 Region 生成副本。如果一个 ML 任务以某个表为输入，那么该表的至少一个 Region 应该拥有任务所需的 GPU 类型。由于数据仓库的数据量巨大，而跨 Region 的网络带宽有限，复制会有延迟，这导致其他 Region 的副本比主 Region 的副本更加陈旧。因此，为了保证高优先级任务的数据质量，这些任务需要在其输入表的主 Region 运行，即这些 Region 必须具有这些任务所需的 GPU 类型。对于低优先级任务，优先在主 Region 训练，但不是必需的。

Tetris 首先确定每个表的主 Region，然后确定副本 Region。之所以不同时确定这二者是因为 Meta 发现其计算成本太高。表的所有 Partition 必须位于同一 Region，确定 Region 之后，还需要为 Partition 选择放置的数据中心。这两个步骤的算法相似，所以这里只描述第一步的算法。

Tetris 需要获取每个任务的输入表的使用信息、硬件需求和估计运行时间。

高优先级训练任务通常都是周期性的，且每次提交使用信息几乎不会改变，因此 Tetris 可以从其历史数据中推导出这些信息。

首次提交的任务没有历史信息，需要依赖 MAST 的快速路径在提交时进行决策。如果没有区域同时具有任务所需的数据和硬件，MAST 会通知 Tetris 启动数据迁移并等待其完成，然后再调度任务。但实际情况是许多首次任务不会因为数据复制而被阻塞，因为同一个团队的任务通常共享输入表并需要相同类型的硬件。例如，多个一次性实验任务经常被提交来微调生产周期性任务的参数。Meta 的生产数据显示，虽然大约 70% 的任务是首次任务，但只有少数会触发按需数据移动。

主 Region 放置算法

主 Region 的放置问题建模为混合整数规划（MIP）问题。Tetris 评估了以下三种资源分配的方法：

在根据生产经验多次改进后，发现不同的资源类型需要不同的方法。对于 GPU，由于其稀缺性，应用 hard-quota 往往会使问题无解。因此，Tetris 采用 soft-balance 方法，根据需要抢占低优先级任务来满足高优先级任务。并且为了保证整体使用率更加均衡，Tetris 会惩罚使用率偏离整体的区域。最初，过载和欠载情况被同等惩罚，但实际上，过载更为棘手，因为它会导致影响任务的等待时间更长。所以后来的实现会更严厉地惩罚过载。

存储空间需要改为 hard-quota，因为当需求超过供应时我们不能删除数据。但只依赖 hard-quota 是不够的，因为各区域之间的数据分布不平衡可能会导致某些区域的 GPU 在访问数据时受到 I/O 带宽的瓶颈。因此，存储也应用 soft-balance。之所以不采用 hard-balance 因为它完全阻止了将数据从一个区域移动到需求与供应比率更高的另一个区域。

Tetris 对每个表进行遍历，选择满足最低的成本（表达式 1-3）并满足所有约束（表达式 4-6）的 Region。如果新 Region 不同于当前的主 Region，该表将被添加到移动队列中，队列按移动收益排序。Tetris 每天运行该算法，耗时约五小时完成。

在确定所有表的新主区域后，Tetris 会遍历队列，从移动收益最高的表开始移动。在移动表之前，它会重新计算最佳区域，因为之前的移动可能已改变该表的移动成本。移动操作将持续进行，直到队列为空或达到每日移动配额（由于跨区域网络带宽有限）。Tetris 每天运行此算法，大约需要五小时完成，但实际的数据复制可能需要更长时间。

虽然新的主区域在迁移过程中可能会变得次优，Tetris 通常会在次日重新运行以修正该问题。

原始算法是一个 NP 难题，Tetris 使用爬山算法来计算高效的近似解。

副本放置

除了表的主存储区域外，表可能由于多种原因在其他区域有副本。为了实现灾难恢复（DR），每个表的副本都位于其主存储区域之外。存储DR副本的区域是基于DR策略选择的，考虑到区域故障的概率和灾难后应对负载增加的硬件可用性。

在爬山算法完成后，一些ML任务可能无法在任何区域运行，因为它们的主存储区为空或没有所需类型的GPU。DR副本可能会解决部分问题，对于剩余的任务，Tetris会在其他区域创建额外的表副本，从而允许任务在那里调度。

任务调度（快速路径）

遵循范围解耦原则，MAST将调度职责分配给不同的组件：全球ML调度器（GMS）管理全局作业队列，区域ML调度器（RMS）分配区域资源，集群管理器（CM）负责容器编排。

GMS

GMS的主要职责是从全局作业队列中的所有待处理作业中选择下一个要调度的工作负载。对于每个待处理的工作负载，GMS 为每个待处理的 Workload 计算其 ，优先调度具有最高优先级的工作负载，如有并列，则选择具有最高信用的。

优先级受 Quota 使用情况影响。每个 Workload 属于一个租户，即一个团队。租户被分配优先级和运行其工作负载的配额。租户未超出配额的工作负载被赋予租户的优先级，而超出配额的工作负载则被赋予最低优先级，只能在有资源时运行，并可能在高优先级的 Workload 到达时被抢占。租户优先级根据业务优先级手动分配。目前，MAST使用七个优先级。

工作负载的信用按照其等待时间和资源进行计算：一个工作负载等待的时间越长或租户使用资源越少，则其信用越高。

GMS 依据每个工作负载的对待处理的工作负载进行排序，并定期更新所有待处理工作负载的，因为一个工作负载的状态变化可能会影响其他工作负载的。这种策略使MAST能够实现复杂的配额和优先级管理策略。

RMS

RMS 以分布式拍卖的形式来调度 ML 工作负载：每个 RMS 不断检查由 GMS 维护的作业队列，并尝试调度具有最高 的工作负载。为了调度工作负载，RMS 会咨询 Tetris 的实时组件，检查其本地区域是否具有所需的数据和必要的硬件类型。如果没有，RMS将放弃拍卖。如果所有 RMS 都放弃拍卖，MAST 将启动数据复制，这可能发生在新工作负载首次执行时。

通常，多个 Region 具有所需的数据和硬件类型，并参与竞拍。每个 RMS 会计算该工作负载的放置计划及相应的分数 Pscore。GMS 会选择最高 Pscore RMS 执行该工作负载。

一个 Region 可能有多个 ML 动态集群，工作负载可以包括多个作业，每个作业可以分配给不同的集群。对于工作负载中的每个作业，RMS 会为区域内每个 ML 动态集群计算放置计划和 Pscore，并选择 Pscore 最高的集群来托管作业。工作负载的 Pscore 为工作负载中所有作业的 Pscore 之和。

作业的 Pscore 根据以下规则来计算：

RMS 按照如下的算法来生成一个放置计划：

先检查是否可以使用可用资源分配作业而不抢占正在运行的作业。并且为了增强同一作业中的任务局部性，RMS 会根据机架 ID 对可用机器进行排序，批量分配位于同一机架或附近机架的机器。在扫描过程中，RMS 通过优先使用具有最高可用 CPU/GPU 资源的机器来减少机器的数量。如果需要抢占，RMS会优先抢占低优先级的作业。它根据优先级和运行时间对所有正在运行的作业进行排序，从优先级最低、运行时间最长的作业开始扫描。并且 RMS 会尽量减少抢占的作业。例如，如果一个新作业需要10个 GPU，而扫描显示通过抢占 job1、job2 和 job3 分别可以获得5、5 和12个GPU，那么最佳选择是抢占 job3 而不影响 job1 或 job2。为了实现这一点，RMS 会根据作业的大小重新排序抢占的作业，优先考虑较大的作业。

RMS 使用了多种方法来提升性能，其中最有效的是负缓存（negative cache）。当 RMS 无法为一个作业分配资源时，它会将决策保存在缓存中。如果之后尝试分配相同或更大的作业，缓存会发出分配失败的信号。具体而言，负缓存在每次检查所有待处理作业的 GMS 扫描阶段开始时初始化，并在 GMS 扫描阶段结束后清除。它被实现为一个哈希表，存储无法调度的作业的调度属性，例如作业请求的 GPU 和 CPU 核心数、内存、硬件类型等。这些信息占用内存很少，并且在 GMS 扫描阶段期间不需要缓存驱逐。综合来看，负缓存能有 80% 的缓存命中率，它可以及早过滤出大多数这些失败的尝试。

CM

CM 负责管理动态集群，集群的机器会由 RAS 不断更新。ML 集群 和非 ML 集群的 CM 实例是分开的，并且不会相互干扰，而 RAS 可以动态地在它们之间移动机器，以避免资源闲置。

之所以不使用一个通用的集群来同时处理 ML 和非 ML 工作负载，因为将两种工作负载的优化方向不同，混合在一起会互相影响。在线服务倾向于跨越故障域进行分布，而 ML 训练工作负载则倾向于不广泛分布，以获得更好的网络性能。此外，ML 训练工作负载可能希望 100 个作业中有10 个完全失败，而其余 90 个继续运行，而不是每个作业都经历 10% 的任务终止，而在线服务倾向于后者。以前，CM 在实时作业调度的快速路径上处理这些 ML 和非 ML 工作负载之间的复杂差异，通常由于计算时间有限而导致不理想的选择。因此，我们采取在慢速路径上运行 RAS 的策略，以预构建针对各自工作负载深度优化的 ML 和非 ML 动态集群，从而简化了 CM 在快速路径上的职责。

CM 和 RMS 在工作负载管理上相互协作，RMS 在内存中缓存了完整的信息，可以高效地计算放置计划。当新机器被添加到 ML 动态集群中时，CM 会通知 RMS 这一变化以更新缓存。当某个 Region 的放置计划被选定为执行的最佳计划时，RMS 会指示相应集群的 CM 执行该计划并运行相关作业。这可能需要抢占正在运行的作业，保存 Checkpoint，然后启动新任务的容器，并恢复其被抢占之前的作业状态（如果有）。

容错

GMS，RMS，CM 都是高可用的组件，由一个 Leader 和多个 Follower 组成。具体来说，有两个 GMS 实例在不同的区域运行，两个 RMS 实例在同一区域运行，三个 CM 实例服务于同一个集群。它们都遵循无状态设计，将其持久状态存储在一个共享且复制的数据库中。在 Leader 故障的情况下，Follower 可以从数据库和下一级组件（即 GMS 从RMS，RMS 从 CM）中重建其状态。

局限

在我们的超大规模生产环境中，我们优先考虑实现的简洁性和稳健性，这导致了一些实现上的限制，而非设计上的固有缺陷。

其中一个限制是，尽管我们有能力将工作负载作业分配到各种动态集群，但目前无法将一个作业的任务分布到不同的集群中。RMS 可以利用其对区域内所有 ML 集群资源的全面视图，计算出一个作业任务在不同集群之间的分布计划。CM 当前并不支持 虚拟作业，而这一功能对于有效管理作为一个虚拟作业的分散任务至关重要。

另一个限制是，目前 RMS 一次只能调度一个 ML 工作负载。虽然它可以并行计算将一个工作负载中的多个作业放置到不同的集群中，但在对当前工作负载做出决策之前，它不会开始调度下一个工作负载。之所以采用这种简单的方法，是因为当前调度不是瓶颈。如果未来出现瓶颈，我们已准备好过渡到并行调度多个工作负载。

一些数据

目前，MAST 每天在多个区域内调度数万个 ML 训练工作负载，消耗约10万台GPU和10万台CPU机器。大约 70% 的工作负载使用 GPU 进行训练，剩下的使用 CPU 进行训练。大约 30% 的工作负载是重复的，剩余的是首次运行的工作负载。平均而言，每个工作负载被抢占一次，这导致每天大约有 10 万次调度尝试。高优先级的工作负载可能永远不会被抢占，而低优先级的工作负载可能会被多次抢占。

就工作负载使用的机器数量而言，P50、P90 和 P99 分别为72、180和205台机器。对于使用 GPU 的工作负载，P50、P90 和 P99 分别为 16、64和128个GPU，而当前最大的工作负载，LLM预训练，使用了数万个GPU。工作负载的持续时间取执行开始时间到下一次抢占的时间，对于GPU工作负载，其时序时间的 P50、P90 和 P99 分别为 20 分钟、6.7小时和 66小时。对于CPU工作负载，相应的持续时间为38分钟、7.9小时和38小时。总体而言，训练工作负载在许多机器上运行时间较长，因此花时间计算高质量的调度决策是值得的。

由于能够在全球范围内灵活地放置数据和工作负载，MAST 的 GPU 机器平均分配率达到了 98%（图5）。2% 的损失是由于抢占的开销、调度的固有延迟以及各区域之间数据和 GPU 分布不均衡等因素造成的。分配率是通过将分配给工作负载的总硬件时间除以可用的总硬件时间来确定的。需要注意的是，GPU 分配率与 GPU 利用率不同，因为即使某些GPU被分配给了一个工作负载，它们也可能由于各种因素（如工作负载的内部通信瓶颈）而未被充分利用。我们使用分配率作为指标，因为它与调度系统更相关，而这是本文的主要焦点，而GPU利用率更适合用于衡量ML训练框架的表现。

相比之下，CPU机器的分配率较低，专用于 ML 工作负载的CPU机器分配率为 87%。主要是因为 CPU 资源存在轻微的超额配置，以确保昂贵的 GPU 机器不会因为缺乏可用的 CPU 机器而闲置。

图 6 可以看到无法满足数据与 GPU 而必须等待按需数据移动完成的工作负载的比例通常低于 0.1%，这表明 Tetris 的有效性。虽然 Tetris 通过创建额外的表副本来提高共置率，但由于某些工作负载首次出现或机器维护导致某些数据或硬件不可用，非共置情况仍可能发生。但考虑到 70% 的工作负载是首次出现的，这个数据表明大多数首次工作负载仍然可以从为重复工作负载规划的数据放置中受益。

得益于 Tetris，多数情况下有多个区域可以承载同一个工作负载，这使得 MAST 可以在不同的日子跨区域迁移工作负载。在图 7 中，“候选区域”是指具有所需训练数据和硬件类型来承载工作负载的区域，而“执行区域”是实际在不同日子承载该工作负载的区域。如图所示，大多数工作负载有两个或更多的候选区域，大约 40% 的工作负载有四个或更多的候选区域。每个工作负载的执行区域数量较少；大约 30% 的工作负载在此期间被跨区域重新定位，显示了全球ML调度确实按预期工作，动态优化了工作负载在各个区域的放置。

图 11(a) 和 (b) 分别显示了待处理工作负载进入运行状态的平均延迟和 P95 延迟，包括排队延迟、调度算法运行时间和抢占时间，但不包括工作负载的执行时间。抢占时间是总延迟的主要因素。如果工作负载 A 抢占了 B，那么在这些图中，B 的重新调度被视为一个新的调度事件，从 B 被抢占的时间算起，直到 B 再次运行。B 的抢占时间计入 A 的延迟，因为 A 需要等待抢占完成。MAST 的 SLO 之一是 P95 延迟。这些图显示，MAST 对于配额内的工作负载始终保持低延迟。然而，对于超出配额的工作负载，延迟有时可能会波动，这取决于集群的负载情况。