【论文】略读笔记12-前沿-分散式联合调度

📖《Megha: Decentralized Federated Scheduling for Data Center Workloads》

🎯需求

• 数据中心的规模和异构性不断增加，导致了联合集群的发展，如KubeFed、Hydra和Pigeon，它们联合了单个数据中心集群。
  • 为了满足不断增长的规模需求，组织正在投资拥有数十万台机器的数据中心。这些数据中心根据应用程序或实用程序进一步划分为集群。此基础设施的高利用率可带来更高的投资回报。为了实现高利用率，数据中心中的资源必须作为可共享的统一池呈现给用户，并且必须支持来自该池的细粒度分配。
  • 由于最近工作负载中普遍存在的异构性和复杂性，调度和资源分配是非同寻常的问题。为了有效地管理大量工作节点，调度框架正在转向联合架构，其中顶级调度程序做出由独立集群调度程序强制执行的高级调度决策。Hydra 和 Pigeon 是两个采用联合架构的调度程序。

🚧现状

• 调度程序大致可分为集中式、分布式、混合式和分层式调度程序。
  • 集中式调度程序，如 YARN，可以做出最佳决策，因为它们具有系统的全局视图。然而，正如先前的研究表明随着数据中心规模的增加，后续处理和收集大量状态会导致瓶颈的形成，因此这些调度程序无法实现所需的调度吞吐量。
  • 像Sparrow这样的分布式架构依赖于概率来找到具有可用资源的机器。对于每个任务，Sparrow 执行随机采样并将探针插入工作队列，以选择排队时间最短的机器。此方法中的调度开销微不足道。但是，当数据中心负载很高时，选择可用机器的可能性非常低。因此，依赖于随机抽样的分布式调度程序在高利用率条件下性能不佳。
  • 与Megha最相似的建筑是Pigeon。
    • Pigeon将数据中心划分为更小的组，每个组有一个Master。分布式调度程序在Master节点之间均匀分配作业中的任务。
    • 在Megha中，GM类似于分布式调度程序，LM类似于Master节点。
    • 但是，这两种体系结构之间存在三个主要区别。
      • 首先，Pigeon不执行细粒度的资源分配。它将工作线程划分为称为插槽的固定资源封装。这种粗粒度的分配将导致资源的碎片化和浪费。
      • 其次，Pigeon使用加权公平排队和预留来避免长时间的作业匮乏，并确保较低的短作业延迟。Megha 不区分工作类型。然而，由于其分散的性质，Megha 实现了低分配时间，并确保防止任何类别的工作出现线头阻塞和饥饿。
      • 第三，Pigeon中的组一旦形成是固定的，即分区方案没有灵活性的余地。Megha 允许使用灵活的分区在数据中心的任何地方安排任务。这样可以更好地利用数据中心的资源，尤其是在存在放置约束的情况下，这些限制限制了可以运行任务的合格计算机的数量。
  • Hydra 是一个联合资源管理框架，由 Microsoft 作为 Apollo 的继任者创建，以支持部署在其数据中心的工作负载所需的每秒高调度决策。
    • Hydra 将其大型集群划分为较小的 YARN 子集群。因此，每个子群集都有一个资源管理器 （RM），用于决定任务放置并执行资源分配。
    • Hydra 引入了一个名为 AM-RM 代理的组件，它允许任务跨越多个子集群。
    • 在Megha中，全局主节点类似于 AM-RM 代理，而本地主节点扮演 RM 的角色。但是，由于每个 Megha GM 都维护整个系统的全局视图的（可能过时的）本地副本，因此每次任务请求到达时都不需要联系集群管理器（LM）。
  • 混合调度器（如 Mercury、Hawk 和 Eagle）使用两组调度程序：
    • 一组用于需要资源保证的任务的集中式调度程序，
    • 另一组用于延迟敏感任务的分布式调度程序。
    • 但是，这些调度程序遇到了与前面提到的分布式调度程序相同的问题。
  • PCSsampler 通过缓存响应探测器时收到的状态信息来扩展基于随机采样的方法。
    • 缓存状态的有用性在很大程度上取决于探测的工作线程。
      • 在高负载的大型集群中，查找具有可用槽的工作线程可能需要多轮探测，从而导致高调度开销。
    • 另一方面，Megha 的 GM 在每次启动请求后收集有关整个 LM 集群的部分状态信息。GM 还使用来自 LM 的定期检测信号更新其存储的全局状态。 Megha 通过让 LM 验证它们来确保其所有决策都是最佳的。

🛩创新

• 在我们的论文中，我们介绍了Megha，一个分散的全局调度程序，它使用最终一致性和灵活的分区来克服现有调度程序的局限性。
  • Megha 采用灵活的集群逻辑分区来分配其调度负载，确保以非常低的调度开销满足工作负载的要求。它使用分布式全局调度程序，该调度程序不依赖于集中式数据存储，而是具有最终一致性，这与使用分层体系结构或依赖于集中式数据库的其他调度程序不同。
    • Megha 具有联合架构，并将数据中心划分为较小的集群，每个集群由本地主节点 （LM） 控制。
    • 它通过将负载分发到多个顶级全局主节点 （GM） 来实现高调度吞吐量。
    • 每个 GM 使用系统资源的最终一致的全局视图来做出调度决策。
    • LM 验证 GM 的决策，并将任务部署到它们处理的集群的工作节点上。
• 我们的主要贡献如下。我们：
  • 定义分配时间并将其分解为众多组件。我们还分析了不同调度方法中每个组件对分配时间的贡献。
  • 引入一种新颖的去中心化框架的设计，该框架使用最终一致性和动态分区来克服现有方法的局限性。
  • 演示与集中式调度程序和分布式调度程序（Sparrow）相比，使用我们的方法调度的任务分配时间的改进。

📊效果

• 我们对Megha的实验表明，它可以在资源分配时间短的情况下安排任务，同时考虑到资源需求和放置约束 - 大约几十毫秒。
  • 我们的实验是使用真实世界的生产轨迹进行的，以评估Megha的任务分配速度，并将其与集中式和分布式调度方法进行比较。
  • 结果表明，Megha 可以实现与基于随机抽样的分布式调度程序 Sparrow 相当的中位数分配时间。
  • Megha 还报告了比 Sparrow 好两个数量级的 99th 百分位分配时间。
  • 这些实验还演示了如何通过最终一致的全局状态满足任务放置约束，同时报告比集中式方法更少的分配时间。

🧠疑问

1. 使用全局中心-局部分散的模式时，所需时间情况如何？能否推广至全球大数据中心架构？

🗺参考文献

[1] M. Thiyyakat, S. Kalambur and D. Sitaram, “Megha: Decentralized Federated Scheduling for Data Center Workloads,” 2023 15th International Conference on COMmunication Systems & NETworkS (COMSNETS), Bangalore, India, 2023, pp. 278-286, doi: 10.1109/COMSNETS56262.2023.10041383.