【论文】略读笔记15-经典-大规模调度

📖《Scaling Large Production Clusters with Partitioned Synchronization》

🎯需求

• 近年来，计算机集群的规模显着增长。
  • 如今，一个集群可能拥有 10 万台机器，每天执行数十亿个任务，尤其是短任务。因此，管理集群中资源利用率的调度程序也需要升级才能在更大规模的情况下工作。
  • 在阿里巴巴，我们运营着大型集群，每个集群包含数万台机器。每天都有数十亿个任务在集群中提交、调度和执行。集群调度程序（简称调度程序）管理集群中的机器和任务。调度器根据任务的资源需求（例如CPU、内存、网络带宽），使用各种调度算法将任务与合适的资源匹配，并在调度效率、调度质量、资源利用率、任务的公平性和优先级等多个调度目标之间进行复杂的权衡。平衡这些目标的能力在很大程度上取决于技术和业务因素，因此因公司和集群而异。
• 然而，在大型生产集群中升级调度器（中央系统组件）是一项艰巨的任务，因为我们需要确保集群的稳定性和鲁棒性，例如要保证用户透明度，并且需要其他集群组件和现有的调度策略保持不变。
  • 由于近年来我们业务的快速增长，我们在扩展调度程序（类似于 YARN）的集中式架构方面面临着严峻的挑战，因为我们的集群中的任务和机器大幅增加。如今，我们的一些集群的规模接近 100k 台机器，平均任务提交率约为 40k 任务/秒（在某些月份甚至更高）。这种规模完全超出了单个调度器的容量，升级到分布式调度器架构是不可避免的。
• 我们需要一种分布式调度器架构的设计，该架构可以处理集群规模和任务提交率的规模（可扩展性），同时实现低延迟和高质量的调度。所提出的设计还需要满足两个硬约束（§2）：向后兼容性和无缝用户透明度。来自这些约束的调度程序的鲁棒性和稳定性对于我们的生产环境至关重要。

🚧现状

• 我们调查了现有的调度程序设计，发现大多数都无法处理我们生产集群的规模，或者可能会危及它们的稳健性。
  • 集群调度程序已被广泛研究，我们在第 3 节中讨论了现有调度程序对于集群环境和工作负载的适用性。
    • 其中，Omega 中描述的共享状态调度器架构较符合需求
      • Omega 能够处理我们的集群大小并满足两个硬约束，因为它需要最少的侵入性架构更改。
        • 在 Omega 中，
          • 主节点维护集群状态，该状态指示集群中每台机器的资源可用性。
          • 有多个调度程序，每个调度程序通过定期与主副本同步来维护集群状态的本地副本。
          • 每个调度程序根据（可能是陈旧的）本地状态乐观地调度任务，并向主节点发送资源请求。
          • 由于多个调度程序可能请求同一块资源，这会导致调度冲突。主节点将资源授予第一个请求资源的调度程序，其他调度程序将需要重新调度其任务。
      • Omega 在可扩展性、低延迟和高调度质量方面仍不满足需求，
        • 当任务提交率较高时，调度冲突和重新调度开销会导致高延迟，我们在第 4 节中使用分析模型和模拟对此进行了验证。我们的结果表明，对优质资源的争夺和本地状态的陈旧性是造成高调度延迟的两个主要因素，因为它们都会大大增加调度冲突。

🛩创新

• 我们分析了一种遵循共享状态架构的最合适的设计，它的局限性导致我们提出了一种细粒度的陈旧状态共享设计，称为分区同步（ParSync）。
  • 在第 5 节中，我们提出分区同步（ParSync）来减轻“对优质资源的争夺”和“本地状态的陈旧性”这两个因素的负面影响。
    • ParSync 将集群状态划分为 N 个部分（N 是调度程序的数量），这样每个调度程序每次都会同步 1/N 的不同分区，而不是整个状态。因此，在任何时候，每个调度程序都有 1/N 分区的新视图，并且可以首先将其任务调度到这些分区。
      • 这显着减少了对高质量资源的争用（与其他调度程序）。
      • 根据分区同步的时间，调度程序知道其分区的陈旧程度；因此，算法设计者现在可以通过调整对更新分区的偏好来更好地平衡调度延迟和调度质量。
    • 我们还设计了一种自适应策略，可以在降低调度延迟和提高调度质量之间进行动态选择。

📊效果

• ParSync 具有维持生产集群稳健性所需的简单性，同时实现高调度效率和扩展质量。
  • 我们在§6中验证了ParSync以及基于ParSync开发的各种调度算法的有效性。
• ParSync已在我们的生产集群中部署并稳定运行。
  • ParSync已经部署在阿里巴巴最新版本的分布式集群调度器Fuxi 2.0中，并且在我们的生产集群中稳定运行，每个生产集群包含数千到10万台机器。

🧠疑问

1. 🗺参考文献

[1] Feng Y, Liu Z, Zhao Y, et al. Scaling large production clusters with partitioned synchronization[C]//2021 USENIX Annual Technical Conference (USENIX ATC 21). 2021: 81-97.