MAST: Global Scheduling of ML Training across Geo-Distributed Datacenters at Hyperscale

OSDI24：MAST: Global Scheduling of ML Training across Geo-Distributed Datacenters at Hyperscale

来自TPDS24的survey《Task Scheduling in Geo-Distributed Computing: A Survey》，三层分级：全局队列管理 → 区域资源分配 → 集群级编排

在Meta的私有云中，用户原本需要手动选择数据中心区域来存放训练数据和运行任务，导致区域间资源供需严重不平衡。例如，高优先级任务的GPU需求与供给比曾高达2.63。
此外，跨区域调度面临两大挑战：

数据与GPU的协同位置要求高，但跨区域网络带宽有限。
调度规模巨大，涉及数十个区域、数百万台机器。

设计原则（这里叙述也包括了工作流）

Temporal decoupling.
- 慢路径（Tetris） Tetris含义为俄罗斯方块
  - 负责跨区域数据放置，考虑GPU、存储、CPU等多维资源，支持“软平衡”策略（允许GPU超卖）和高优先级作业的“训练在原始区域”约束。使用混合整数规划（MIP）和爬山算法。
  - 每日运行约5小时，移动数百PB数据，显著提升数据与GPU的协同放置率。
- 快路径（实时调度）：基于慢路径准备好的数据和资源，进行快速调度。
Scope decoupling. 将调度职责分为三个层次
- - Global ML Scheduler (GMS)：管理全局作业队列（全球范围）。
    - 用户提交一个 ML 训练作业。GMS 接收作业，将其放入全局队列。GMS 周期性扫描队列，计算每个作业的 <优先级, 信用值>，决定下一个应该被调度的作业。GMS 将该作业的状态更新为“待调度”，并写入共享的作业队列数据库。
  - Regional ML Scheduler（RMS）：进行资源分配（区域范围）。
    - 各区域的 RMS 实时监控共享数据库，发现“待调度”的作业。
      - 每个 RMS 检查自己所在的区域：
        
        是否有该作业需要的数据（提醒：数据放置已经由Tetris（就是那个俄罗斯方块）提前做好了预放置，使得多个区域都有资格参与拍卖。）
        
        是否有该作业需要的GPU/CPU 硬件类型？
        
        如果满足条件，该区域的 RMS 开始进行资源分配（即装箱计算）：
        
        查看区域内多个动态集群的当前空闲资源。
        
        如果需要，计算需要抢占哪些低优先级作业。
        
        生成一个具体的放置计划（例如：在集群 A 的哪几台机器上运行）。
        
        为这个计划打一个放置质量分数。分数可能要考虑的维度：是否抢占、被抢占作业的数量、被抢占作业的运行时长、数据局部性、硬件类型匹配
        
        所有参与的 RMS 将各自的计划及其分数写回共享数据库。
        
        GMS 或一个轻量级仲裁者选取分数最高的（最简陋的拍卖算法），获胜的 RMS 将其放置计划发送给对应的 CM。
  - Cluster Manager（CM）：负责容器编排（集群范围）。
    - 使用原有的Twine [44]（Meta内部自研的统一集群管理系统，本文名称MAST的含义即 short for ML Application Scheduler on Twine）实现，管理动态集群，支持与RAS系统 [36] 协同进行机器资源的动态分配。
    - CM 收到指令后，执行具体的容器编排：如果需要抢占，通知现有作业保存检查点并终止。拉取新作业的容器镜像。在指定的机器上启动容器。监控容器的运行状态。
    - 作业开始运行。
Exhaustive search. 穷举搜索
- 对于每个作业，多个RMS并行计算其在不同区域的放置方案，通过“拍卖”机制选出最优方案，避免传统联邦调度中简单启发式带来的次优决策。

[36] Andrew Newell, Dimitrios Skarlatos, Jingyuan Fan, Pavan Kumar, Maxim Khutornenko, Mayank Pundir, Yirui Zhang, Mingjun Zhang, Yuanlai Liu, Linh Le, Brendon Daugherty, Apurva Samudra, Prashasti Baid, James Kneeland, Igor Kabiljo, Dmitry Shchukin, Andre Rodrigues, Scott Michelson, Ben Christensen, Kaushik Veeraraghavan, and Chunqiang Tang. RAS: Continuously Optimized Region-Wide Datacenter Resource Allocation. In Proceedings of the 28th ACM Symposium on Operating Systems Principles, 2021.

[44] Chunqiang Tang, Kenny Yu, Kaushik Veeraraghavan,Jonathan Kaldor, Scott Michelson, Thawan Kooburat,Aravind Anbudurai, Matthew Clark, Kabir Gogia, Long Cheng, Ben Christensen, Alex Gartrell, Maxim Khutornenko, Sachin Kulkarni, Marcin Pawlowski, Tuomas Pelkonen, Andre Rodrigues, Rounak Tibrewal, Vaishnavi Venkatesan, and Peter Zhang. Twine: A Unified Cluster Management System for Shared Infrastructure. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI), pages 787–803. USENIX Association, 2020.

总结：太阳底下没有新鲜事，这个先准入在细粒度排序在单机OS中就讲过。这是来自工业界的论文，典型的大规模系统，解决超大规模生产环境中的实际问题，向社区展示这是OK的。