【论文】略读笔记80-前沿-混合云等待时间自动决策

📖《Starburst: A Cost-aware Scheduler for Hybrid Cloud》

2024 年 UC Berkeley大学团队 发表于 CCF-A 类会议 ATC。

🎯需求

• 为了有效地应对工作需求的爆发，组织采用混合云架构将批量工作负载从私有集群扩展到公共云。这需要将集群调度程序转换为支持公共云的版本，以在云成本和调度程序目标（例如作业完成时间（JCT））之间进行权衡。
  • 随着人工智能 (AI) 和数据分析工作负载需求的不断增长，企业构建了大型多租户私有集群（以下简称固定集群）以及高端 GPU 加速器。这些固定集群利用集群管理器根据定义的调度策略将资源分配给作业。在即将到来的截止日期或产品发布等事件期间，这些集群还会经常遇到作业量的大幅激增，从而导致长时间的排队延迟。
  • 许多组织没有投资更多的本地硬件，而是采用混合云架构。这些架构利用云在峰值负载期间动态配置额外资源，提供更具成本效益的解决方案。
• 然而，云对无限资源容量的幻想给支持云的调度程序带来了新的挑战。这些调度程序不仅必须在固定集群和云之间分配作业，而且还必须了解云成本。

🚧现状

• 然而，我们对生产级跟踪的分析表明，由于集群利用率低，现有的支持云的调度程序会导致低效的成本与 JCT 权衡。
• 当作业到达时集群已满时，调度程序会执行两种选择：等待（Wait）或立即将作业发送到云端（No-Wait）。
  • （1）No-Wait：具有云自动扩展功能的现有集群管理器选择后者——我们称之为“No-wait”的策略。这种方法消除了排队延迟并减少了平均作业完成时间 (JCT)**，但由于仅考虑当前时刻而不考虑未来时刻，使得集群利用率较低**，因此会带来较高的云成本。No-Wait 忽略等待选项，这会延迟集群上的作业执行，以避免配置昂贵的云资源。
  • （2）Constant-Wait：如果我们选择等待（Wait），下一个问题是：要等多久？一种简单的策略，Constant-Wait，在将所有作业 j 发送到云之前分配恒定的等待时间。在实践中，选择正确的 C 具有挑战性。
    • 较短的等待时间可以减少排队延迟，但会带来较高的云成本和较低的集群利用率,大型作业往往在等待一小段时间后仍不能获取资源，则容易被发送到云端。
    • 相反，较长的等待时间可以降低成本，并且对于较长的作业来说是可以接受的，但较长的等待时间会阻塞并不公平地延迟较短作业的运行。
• 这些不同的问题凸显了支持云的调度程序需要进行权衡：平衡云成本与作业完成时间 (JCT)。
  • 如果集群已满，No-Wait 会立即调度作业，从而导致高昂的云成本。
  • 如果没有云，作业可以无限期地排队（无云，C=∞），从而导致零云成本和高 JCT。
  • 最后，Constant-Wait 根据不同的 C 值调整成本和 JCT。

🛩创新

• 在本文中，我们探讨了何时在云上安排作业的问题，以降低云成本，同时避免长时间的排队延迟。

• 我们推出了 Starburst，这是一个最大化集群利用率以简化成本与 JCT 权衡的系统。

  • Starburst 的调度程序动态控制作业的等待时间以提高利用率 - 它为大型作业分配较长的等待时间以增加其在集群上运行的机会，为小型作业分配较短的等待时间以增加其在云上运行的机会。
  • 为了提供可配置性，Starburst 为系统管理员提供了一个简单的等待预算框架，以调整他们在成本 JCT 曲线上的位置。
  • 与传统的集群调度程序不同，Starburst 在私有集群和动态云集群上作为更高级别的资源管理器运行。
  • 我们的主要见解是，与作业的计算成本成正比的等待可以更好地平衡成本和 JCT；大型昂贵作业可以更好地利用集群，等待足够长的时间才能在集群上运行，而较小的作业成本较低，等待时间较短，更有可能在云上运行。

• （1）Starburst 引入了一种新颖的框架，可以根据作业的特征动态分配等待时间。我们提出了两种调度算法：Compute-Wait（假设了解作业运行时间）和 Star-Wait（不需要先验知识）。

  • Compute-Wait 根据作业的总计算量（其预测运行时间和请求的资源的乘积）来分配作业的最大等待时间。
  • 与 Compute-Wait 类似，Star-Wait 具有运行时和资源感知能力，但假设作业运行时的知识为零。为了将长时间运行的作业与短期作业分开，它会抢占从云端返回集群执行时间超过一小段时间的云运行作业。然后，被抢占的作业将根据其资源需求的比例分配等待时间。
  • 更重要的是，为大型作业分配长时间等待会阻塞队列中更靠后的较小作业。为了减少阻塞，Starburst 积极地在队列中无序执行作业。该技术可以有效地调度小型作业，同时大型作业则等待足够的资源。
    • 无序调度（Out-of-order）改进了无云环境中的 JCT，但在 JCT 中产生了长尾。在混合云环境中，由于作业超时到云，我们在 Starburst 中没有观察到不公平的作业延迟。
  • 总的来说，Starburst 的策略将成本-JCT 曲线转向更帕累托有效的解决方案（图 2），使 Starburst 能够实现高达集群利用率为 99%，与最佳解决方案的误差不超过 5%。

• （2）鉴于各组织的工作负载和预算限制各异，在 costJCT 权衡方面不存在一刀切的立场。 Starburst 提供了一个简单的等待预算功能，为系统管理员提供了一个单一的旋钮来确定他们在成本-JCT 曲线上的位置。这被定义为管理员**愿意接受的平均作业运行时间增加的最大百分比 P%**。

• （3）与集群调度程序不同，Starburst 是一种通用的高级资源管理器，它通过私有集群和动态配置的云集群跨集群协调作业，并且对其用户是透明的，不需要对作业进行修改。

• 本文的主要贡献是：

  • • 我们将云成本-JCT 权衡形式化为混合云环境中的调度问题。
  • • Starburst 根据作业的特征动态分配等待时间，以最大限度地提高集群利用率，更好地平衡成本和 JCT。 Starburst 可以利用作业运行时的知识，但也可以在没有先验知识的情况下进行操作。
  • • Starburst 的等待预算框架为系统管理员提供了一个旋钮来定义他们在成本-JCT 曲线上的位置。
  • • 我们的系统易于部署，并显示出显着的性价比改进。

📊效果

• 我们实现了一个高保真模拟器，用于在多个生产轨迹上测试 Starburst。
• 我们在 32 个 GPU 私有物理集群上的结果表明，与 No-Wait 相比，Starburst 降低了 80% 的成本，而 JCT 仅增加了 5.8%。对于大规模模拟，Starburst 可以将成本降低 54-91%，同时将 JCT 提高最多 5%。
• 最后，Starburst 对于数据传输开销、高度突发的工作负载以及较低级别的排队和装箱策略具有鲁棒性。

🧠疑问

1. 有点意思的文章，粗看问题觉得很简单，但看到解决方案又觉得挺好玩。一方面刻画了C值曲线，另一方面提出了“需要先验知识”和“不需要先验知识”的两种方案。
2. 这类看起来很简单的文章该如何体现新？被ATC看中的原因是什么？是实用？

---

---

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

🗺参考文献

[1] Luo, Michael, et al. “Starburst: A Cost-aware Scheduler for Hybrid Cloud.” 2024 USENIX Annual Technical Conference (USENIX ATC 24). 2024.