Google Research 发布 SPAA 2025 论文：时变容量下的非抢占式吞吐量最大化算法

云调度新范式：应对时变容量的理论突破

在传统的算法作业调度理论中，计算资源通常被视为静态的：服务器拥有固定数量的 CPU，或集群具有恒定数量的可用机器。然而，现代大规模云计算的现实要动态得多。由于硬件故障、维护周期或功率限制，资源会不断波动。

现实挑战：优先级抢占与作业连续性

更重要的是，在分层调度系统中，高优先级任务通常会按需占用资源，为低优先级批处理作业留下随时间变化的“剩余”容量。想象一家餐厅，餐桌在不同时间被 VIP 预订；在剩余餐桌上安排普通顾客就变成了一个复杂的难题。

当这些低优先级作业是非抢占式（Non-preemptive）时——意味着它们无法暂停并在稍后恢复——风险就很高。如果作业因容量下降而中断，所有进度都将丢失。调度器必须决定：我们现在启动这个长作业吗，冒着未来容量下降的风险？还是等待一个更安全的窗口，但可能错过截止时间？

SPAA 2025 核心论文：理论框架与算法设计

据 Google Research 官方披露，在 SPAA 2025 上发表的论文《时变容量下的非抢占式吞吐量最大化》（Non-preemptive Throughput Maximization under Time-varying Capacity）中，研究团队首次系统研究了在可用容量随时间波动的环境中最大化吞吐量（总权重或成功作业数量）的问题。该研究为这一问题的多个变体提供了首个常数因子近似算法，为在波动云环境中构建更鲁棒的调度器奠定了理论基础。

核心模型：四要素作业与容量约束

研究团队设计了一个调度模型，捕捉了多个关键约束。他们考虑一台机器（或集群），其容量随时间变化。这个容量曲线决定了在任何给定时刻可以并行运行的作业的最大数量。给定一组潜在作业，每个作业由四个关键属性表征：

• 释放时间：作业何时变得可运行
• 截止时间：作业必须完成的硬性截止时间
• 处理时间：机器必须在作业上工作的持续时间
• 权重：如果作业成功完成所获得的价值

目标是选择一个作业子集并调度它们，使得每个选中的作业在其有效窗口内连续运行。关键约束是，在任何时间，运行作业的总数不得超过当前容量。目标是最大化吞吐量，即所有完成作业的总权重。

算法性能：离线与在线环境下的突破

离线环境：已知未来的规划

在离线设置中，可以提前规划，研究团队发现简单策略表现惊人地好。由于在此设置中找到最优调度被认为是“NP-hard”，他们专注于具有严格近似保证的算法。他们分析了一种称为贪心算法的短视策略，该策略迭代地调度最早完成的作业，并证明当作业具有单位利润时，这种简单启发式算法实现了 1/2 近似比。这意味着即使在最坏情况下，该算法也保证调度至少一半的最优作业数量。当不同作业具有不同关联利润时，他们利用原始-对偶框架实现了 1/4 近似比。

在线环境：动态决策的复杂性

真正的复杂性在于在线设置，作业动态到达，调度器必须立即做出不可撤销的决策，而不知道接下来会到达什么作业。研究团队通过竞争比来量化在线算法的性能，这是在线算法的吞吐量与已知所有作业的最优算法吞吐量之间的最坏情况比较。

标准的非抢占式算法在这里完全失败，因为它们的竞争比趋近于零。这是因为调度一个长作业的单个错误决策可能会破坏调度许多未来较小作业的可能性。

允许重启的模型：实现 1/2 竞争比

为了使在线问题可解并反映现实世界的灵活性，研究团队研究了两种模型，允许中断正在运行的作业（如果出现更好的机会）。在允许作业重启的模型中，在线算法可以中断当前正在执行的作业。虽然中断作业上已执行的部分工作丢失，但作业本身保留在系统中并可以重试。

他们发现，允许作业重启提供的灵活性非常有益。迭代调度最早完成作业的贪心算法变体继续实现 1/2 竞争比，与离线设置的结果相匹配。

严格丢弃模型：共同截止时间下的创新算法

在更严格的模型中，中断作业上执行的所有工作都丢失，并且作业本身被永久丢弃。不幸的是，他们发现在这种严格模型中，任何在线算法都可能遇到一系列作业，迫使其做出阻止未来满足更多工作的决策。再次，所有在线算法的竞争比趋近于零。

分析上述困难实例后，研究团队专注于所有作业共享共同截止时间的实际场景（例如，所有数据处理必须在夜间批处理运行前完成）。对于此类共同截止时间实例，他们设计了新颖的常数竞争算法。他们的算法非常直观，并为单位容量曲线（即任何时间只能调度一个作业）的简单设置进行了描述。

在此设置中，算法通过将已到达的作业分配到不相交的时间间隔来维护一个暂定调度。当新作业到达时，算法通过采取以下四个操作中的第一个适用操作来修改暂定调度：

1. 将作业放入空区间，将其添加到暂定调度中
2. 如果新作业显著更小，则替换暂定调度中的另一个未来作业
3. 如果新作业小于执行作业的剩余时间，则中断当前正在执行的作业
4. 丢弃新到达的作业

主要结果表明，将此算法推广到任意容量曲线为该问题提供了首个常数竞争比。形式上，他们获得了 1/11 的竞争比。虽然保证仅调度约 9% 的最优作业数量听起来像是一个弱保证，但这是一个最坏情况保证，即使在最对抗的情况下也成立。

研究意义与未来方向

随着云基础设施变得更加动态，调度算法中静态容量的假设不再成立。本文开启了时变容量下吞吐量最大化的正式研究，弥合了理论调度模型与数据中心波动现实之间的差距。

虽然研究团队建立了强大的常数因子近似，但仍有增长空间。在线设置的 1/11 竞争比与理论上限 1/2 之间的差距表明，可能存在更高效的算法。探索随机算法或对未来容量知识不完善的场景，可能为实际应用带来更好的结果。

该研究是与伊利诺伊大学厄巴纳-香槟分校的 Aniket Murhekar、Google Research 的 Zoya Svitkina、Erik Vee 和 Joshua Wang 的合作成果。