第 6 课：容量、配额、公平与 Backfill

本课目标与完成标准

本课产出：实现不延误保留作业的 backfill 选择，并解释利用率、公平性与碎片的冲突。

通过要求：唯一代码填空题通过给定检查；Q1～Q3 都给出因果链；能指出一个正确性边界和一个性能/运营取舍；总分至少 8/10。

与既有六条主线的边界

上一课解决单个 gang 放置；本课处理多租户队列、配额、优先级、reservation 与空洞利用。

前置：Linux/网络基础、runtime 补充线、train 分布式章节。本课只补 AI Infra 缺口，不重复已经完成的 kernel 或并行算法推导。

核心心智模型

1. 它是什么，解决什么问题

在多团队共享的大规模企业级 AI 算力中心（通常汇聚数百至数千张高端 GPU，单卡硬件与能耗成本极高），平台运营与调度系统面临着三大核心诉求的激烈博弈：

1. 多租户保底配额与商业公平性（Guaranteed Quota & Tenancy Isolation）：
   团队 A 采购了 400 张 GPU，团队 B 采购了 400 张 GPU。平台必须确保任何团队随时都能兑现其购买的“保证配额（Guaranteed Quota）”，杜绝因某一团队恶意突发提交上千任务而将其他团队完全挤占；同时，在某些团队配额闲置时，应允许其他团队弹性突发超售（Elastic Bursting / Oversubscription）借用，极大化集群资产的投资回报率（ROI，如图 6-1 所示）。

2. 多维异构资源的瓶颈均衡（Multi-Resource Fair Allocation）：
   大模型端到端工作流不仅需要 GPU，还重度消耗 CPU 核心（负责数据解压、Tokenization 与分词）、Host 内存（用于显存溢出与 Page Cache）、以及 RDMA 网络带宽。传统单一维度的配额无法解决“CPU 被打满而 GPU 闲置”的资源倾斜，需要引入主导资源公平调度算法（Dominant Resource Fairness, DRF）。

3. 高优先级大作业等待与算力空洞（The Reservation vs. Utilization Dilemma）：
   当一个千亿大模型训练任务（如申请 64 卡或 512 卡）到达队首时，当前集群仅有部分卡空闲（例如 8 张卡空闲，其余 56 张卡需等待 30 分钟后正在运行的前序任务释放）。若为了等待该大任务而将这 8 张卡完全闲置 30 分钟，集群利用率将发生断崖式下跌；若直接把这 8 张卡分配给一个运行 10 小时的普通长任务，大任务的启动时刻将被严重延误

回填调度（Backfill Scheduling）通过计算确定性的“保留时间窗口（Reservation Window）”，利用时间与空间维度上的缝隙，精准调度短小作业填充算力空洞（如图 6-2 所示），在零推迟大作业启动的前提下最大化集群利用率。

2. 它如何工作

(1) 多租户配额模型与主导资源公平（DRF，如图 6-1 所示）

集群总资源配额池 (1000 GPUs)

部门 A 保证配额 (Guaranteed: 400 GPUs)

部门 B 保证配额 (Guaranteed: 400 GPUs)

共享空闲与突发池 (Oversubscription: 200 GPUs)

主导资源公平调度 (Dominant Resource Fairness)

根据 CPU、GPU、内存中占比最高的主导份额实现均衡分配

图 6-1：多租户配额保障、弹性突发超售与 DRF 资源公平模型

• 分层配额池设计（Hierarchical Quota Pools）：
  平台将物理卡池划分为“保证配额（Guaranteed）”与“共享突发池（Shared Elastic Pool）”。租户在保证限额内提交的任务享有最高优先级；超出保证限额的任务只能作为“可抢占突发任务（Preemptible Burst Jobs）”在共享池中运行。一旦保证配额的合法持有者提交新作业，突发任务将被优雅回收退让。

• 主导资源公平算法（Dominant Resource Fairness, DRF）：
  设集群总资源向量为 $\mathbf{R} = \langle R_{\text{GPU}}, R_{\text{CPU}}, R_{\text{Mem}} \rangle$。
  对于租户 $i$，其当前已占用的资源向量为 $\mathbf{U}_i = \langle U_{i,\text{GPU}}, U_{i,\text{CPU}}, U_{i,\text{Mem}} \rangle$。
  租户 $i$ 的主导资源份额（Dominant Share）定义为其占全集群比例最高的那项资源的份额： $$s_i = \max \left( \frac{U_{i,\text{GPU}}}{R_{\text{GPU}}}, \frac{U_{i,\text{CPU}}}{R_{\text{CPU}}}, \frac{U_{i,\text{Mem}}}{R_{\text{Mem}}} \right)$$ 调度器在每一轮调度中，始终优先为当前主导份额 $s_i$ 最小的租户分发资源，从而在多维异构环境下严格实现帕累托最优与无嫉妒性（Envy-Freeness）。

(2) 回填调度算法与保留时间窗口填充（Backfill Scheduling，如图 6-2 所示）

高优先级大作业等待 64 卡 (预计 30 分钟后到位)

调度器计算预留时间窗口 (Reservation Window)

扫描等待队列中的碎片小作业 (如 4 卡、运行 15 分钟)

小作业是否能在预留时间前结束?

立即回填调度 (Backfill) 启动小作业，极大化集群利用率

小作业保持等待，确保绝不推迟大作业启动时刻

是否

图 6-2：回填调度 (Backfill Scheduling) 与保留时间窗口填充工作流

如图 6-2 所示，Backfill 调度的核心执行流水线分为三步：

1. 建立大作业未来预留点（Reservation Window）：
   队首高优先级大任务因资源不足无法立即启动。调度器依据当前所有运行中作业声明的截止时间（Walltime），向前模拟时间线，推算出该大任务最早能够集齐全部卡数的未来时间点 $T_{\text{res}}$。调度器将该大作业锁定在该时间点，并计算出当前的空闲卡数 $N_{\text{free}}$ 与可用时间空洞 $\Delta t_{\text{gap}} = T_{\text{res}} - T_{\text{now}}$；

2. 回填候选任务可行性过滤（Feasibility Filter）：
   调度器跳过队首，遍历排队队列中的低优先级或短小任务。候选作业 $j$ 允许被“回填（Backfill）插队”的一个充分条件是： $$\text{Requested GPUs}(j) \le N_{\text{free}} \quad \land \quad \text{Estimated Walltime}(j) \le \Delta t_{\text{gap}}$$ 这一约束保证了该作业在 $T_{\text{res}}$ 之前运行完毕并释放资源，不推迟队首大作业的预定启动时刻。它不是必要条件：若作业只占用大作业在 $T_{\text{res}}$ 时用不到的多余空闲卡，即使运行得更久也不会推迟大作业。

3. 价值最大化排序目标（GPU-Time Maximization）：
   在所有满足可行性约束的候选作业中，调度器优先挑选能够最大化填充物理算力面积的作业，即最大化 $\text{GPUs} \times \text{Minutes}$。平局时通过作业名称字典序实现确定性裁决。

3. 正确性条件与常见误区

• 误区一：按“申请 GPU 数量最少”作为回填贪心策略
  许多人直觉认为“卡数越小的作业越容易填洞，因此应该最先调度卡数最少的小作业”。然而，极小作业（如 1 卡运行 2 分钟）产生的 GPU-Time 极低（仅 2 GPU·min），频繁调度它们会留下大量无法拼凑出稍大规格的微观碎片，反而降低了整体算力吸收率。回填必须以最大化“GPU-Time 吞吐总面积（$\text{GPUs} \times \text{Duration}$）”为优化目标。

• 误区二：无条件信任用户填写的申请运行时间（Walltime）
  Backfill 的正确性前提是“回填作业绝不推迟大作业的启动时间”。然而在工程实践中，用户填写的时长往往极不准确（例如申报运行 10 分钟，实际由于收敛慢跑了 2 小时）。如果调度器未设置硬性强制超时杀任务（Hard Walltime Enforcement），超时的回填任务将直接霸占资源，导致大作业的预留点被严重延误。系统必须建立基于历史运行数据的运行时预测校准，并在超时时自动触发 Checkpoint 保存或强制终止。

• 误区三：高估高优先级抢占（Preemption）的零成本性
  平台不能因为支持硬抢占，就肆无忌惮地随意终止低优先级任务。杀掉一个运行了 6 小时的分布式任务，若其未能及时落盘 Checkpoint，意味着白白浪费了数十卡时昂贵算力与电力，甚至造成数据集读写管道损坏。抢占必须将 Checkpoint 转储成本、网络抖动与级联重试开销全面纳入综合收益模型。

4. 性能与工程取舍

• 保守回填（Conservative Backfill）vs. 激进回填（EASY Backfill）：
  • 保守回填：为队列中每一个排队作业都计算并锁定一个严格的未来预留点，极度公平且高度可预测，但会产生过多保守的保留空洞，导致集群平均利用率偏低；
  • EASY 回填：仅为队首的第 1 个大作业维护单一预留点，后续所有小作业只要不推迟这唯一的队首作业即可任意插队抢跑。EASY 回填利用率更高，但排在第 2 位及以后的作业可能被不断推迟。实际系统多介于两者之间：Slurm 的 sched/backfill 会为多个高优先级作业预留资源（受 bf_max_job_test 等参数限制），更接近保守回填；Volcano 等 Kubernetes 批调度器默认不基于 Walltime 做 EASY 式回填。
• 配额超售（Oversubscription）与排队体验的权衡：
  过高的弹性突发超售比（如 200% 超售）能让集群时刻处于打满状态，但一旦多个部门在月末集中提交突发实验，会引发大面积的抢占排队风暴，导致任务反复失败重跑。工程上通常将弹性超售比例控制在总池的 15%～30% 之间。

具体演示

设当前集群空闲 free_gpus = 8，距离队首大作业的保留时刻还有 gap_minutes = 30 分钟：

• 候选作业列表为：a（4 卡，20 分钟）、b（8 卡，40 分钟）、c（2 卡，25 分钟）。

分析过程如下：

1. 可行性筛选：
   • 作业 a：$4 \le 8$ 且 $20 \le 30$，可行，贡献算力面积为 $4 \times 20 = 80\text{ GPU·min}$；
   • 作业 b：运行时间 $40 > 30$，若启动将推迟大作业，属于不可行候选，被剔除；
   • 作业 c：$2 \le 8$ 且 $25 \le 30$，可行，贡献算力面积为 $2 \times 25 = 50\text{ GPU·min}$。
2. 最优选择： 作业 a 的算力面积（80）显著高于作业 c（50），算法确定性选择作业 a 立即执行回填启动，高效利用空洞。

请先独立复述“输入 → 状态变化 → 输出/指标”，再开始填空。

实践任务：唯一代码填空题

补齐确定性 backfill：选择可完成候选中 GPU-time 最大者。

只能修改 TODO/______ 位置，不得删除断言或放宽通过条件。

def choose_backfill(candidates, free_gpus, gap_minutes):
    """candidate=(name, gpus, minutes)"""
    feasible = [job for job in candidates
                if job[1] <= free_gpus and job[2] <= gap_minutes]
    if not feasible:
        return None
    # TODO：最大化 gpus*minutes；平局按名称最小。
    return ______

jobs = [("a", 4, 20), ("b", 8, 40), ("c", 2, 25)]
assert choose_backfill(jobs, 8, 30) == ("a", 4, 20)
assert choose_backfill(jobs, 1, 30) is None

检查方法

运行本单元格，所有断言必须通过；再补一个边界输入并解释预期。

Q1

为什么按 GPU 数最少优先不一定提高整体利用率？

你的答案：

Q2

用户低估作业时长，backfill 会造成什么？如何防护？

你的答案：

Q3

高优先级抢占低优先级作业前应计算哪些成本？

你的答案：

评分规则

• 代码 4 分：正常输入 2 分、边界输入 1 分、解释 1 分；
• Q1～Q3 各 2 分；
• 一票否决：混淆测量与推测、忽略租户/请求隔离、用平均值掩盖尾延迟、删除失败路径。

Tip💡 点击展开参考答案与详细代码实现

参考答案（仅 answer 分支）

先独立完成。核对后请改变一个规模或故障条件重新推演。

def choose_backfill(candidates, free_gpus, gap_minutes):
    """candidate=(name, gpus, minutes)"""
    feasible = [job for job in candidates
                if job[1] <= free_gpus and job[2] <= gap_minutes]
    if not feasible:
        return None
    return min(feasible, key=lambda job: (-job[1] * job[2], job[0]))

jobs = [("a", 4, 20), ("b", 8, 40), ("c", 2, 25)]
assert choose_backfill(jobs, 8, 30) == ("a", 4, 20)
assert choose_backfill(jobs, 1, 30) is None

Q1 参考答案

在回填与集群容量调度中，盲目采取“按申请 GPU 数量最少优先（Smallest-GPU-First）”的贪心策略往往无法提高甚至会恶化整体有效利用率，核心原因如下：

1. 算力填充面积（GPU-Time Product）极低：集群利用率的本质是单位时间内完成的有效算力面积总和（$\text{GPUs} \times \text{Duration}$）。若优先调度申请卡数极少（如 1 卡）的作业，即便其耗时很短，其贡献的算力吸收面积也非常微小（例如 1 卡运行 5 分钟仅吸收 5 GPU·min 算力）；而一个 8 卡运行 25 分钟的作业能吸收 200 GPU·min 算力。过度偏好微小作业会导致算力空洞大面积闲置；

2. 制造严重的微观碎片（Micro-Fragmentation）：极小任务零散散布在各个物理节点的插槽中，将原本规整的物理节点切割破碎，直接破坏了后续原本能够整体回填的较大规格作业（如 4 卡、8 卡短作业）所需的连续拓扑空间；

3. 队列饥饿与公平性失衡：过度偏好微小作业会导致海量微型作业无限期插队抢跑，造成中等规格作业在队列中长期被压制饿死，违背了多租户平台的 SLA 契约。

Q2 参考答案

后果：回填作业实际运行超过申报时长时，到达预留时刻 $T_{\text{res}}$ 资源仍被占用，队首大作业被推迟，调度承诺失效。

防护：

• 硬性 Walltime 截断：到申报时长先发 SIGTERM，宽限期后 SIGKILL；
• 安全余量：回填窗口预留 15%～20% 缓冲（如 30 分钟空洞只接受申报不超过 24 分钟的作业）；
• 历史校准：按用户历史的申报/实际时长比修正预估，长期低报者限制参与回填；
• 可抢占回填：要求回填作业支持快速 Checkpoint，预留时刻到达时落盘并释放资源。

Q3 参考答案

当高优先级作业抢占低优先级作业以获取资源时，绝非简单的“零成本释放 GPU”，必须在控制面全面核算以下系统级沉没损失与连锁开销：

1. 已消耗算力的完全沉没损失（Sunk Compute Cost）：被抢占的低优先级作业如果已经连续计算了数小时且未触发 Checkpoint，强行杀死该进程意味着此前消耗的数十甚至上百卡时的电力、硬件折旧与时间完全报废作废；

2. 优雅停机与 Checkpoint 转储开销（Draining & IO Overhead）：若允许被抢占作业在退出前执行紧急 Checkpoint 转储，多个并发终止的 Pod 会瞬间向底层存储网络发起巨大的写 IO 洪峰，挤占高优先级任务启动所需的数据加载带宽；且等待转储完成的超时宽限期（Termination Grace Period）直接构成了高优先级任务的拉起时延；

3. 级联调度震荡与 API Server 压力（Cluster Churn）：大规模抢占会导致被逐出的任务在队列中引发级联重调度，产生大量的 Pod 删除与重建事件，极大加重 Kubernetes API Server、etcd 以及节点 Kubelet 的并发负载；

4. 综合 ROI 收益决策模型：调度器在执行抢占决策前，必须对比“高优先级任务提前启动带来的业务收益”与“被抢占任务沉没成本 + 重启恢复成本”之间的差值。只有在净收益显著为正时才允许触发抢占，坚决避免为了提前几分钟启动高优先级任务而摧毁一个已完成 99% 的重大长任务。

参考资料

• Kubernetes Scheduling Framework
• Kubernetes Gang Scheduling

API 与平台能力会演进；部署前应按目标版本重新核对。

← 上一课
第 5 课：Gang Scheduling … 下一课 →
第 7 课：Metrics、Logs、Tra…