【论文】略读笔记83-前沿-Eva考虑干扰的任务共置成本优化

📖《Eva: Cost-Efficient Cloud-Based Cluster Scheduling》

2025 年 威斯康星大学麦迪逊分校（University of Wisconsin-Madison）团队 发表于 CCF-A 类会议 EuroSys。

🎯需求

云计算提供了资源调配的灵活性，允许企业通过动态调整基于云的集群（从云中调配的实例集合）的规模和组成，以经济高效的方式托管批处理工作负载。

• 云计算已被广泛采用，由于机器学习（ML）和大数据分析等新兴技术的兴起，对云计算的需求不断增加[12, 18]。
  • 具体来说，对于批量计算工作负载，云平台的灵活性和可扩展性为企业提供了一种解决方案，使其可以使用基于云的集群（即从云中调配的实例池），以具有成本效益的方式托管作业[8]。因此，研究机构和企业已将批处理工作负载从内部计算集群迁移到由数百或数千个云实例组成的云集群[17, 41, 53, 54]。
• 为确保云计算集群的成本效益，必须采用有效的调度机制，将提交的任务映射到适当的实例上[1]。

🚧现状

然而，由于任务和实例调度策略不理想、同地任务之间相互干扰以及实例调配开销等原因，现有的调度程序无法最大限度地降低总成本。
传统方案：虽然针对批处理工作负载的任务调度已在固定规模的集群设置中进行了广泛研究[19、23、28、36、37、43、45、47、62、63、67]，但基于云的集群的额外灵活性为调度问题带来了复杂性。

• 挑战一：无限云资源下，代替排队执行的按需分配决策
  • 具体来说，资源的按需分配消除了作业因资源不足而在队列中等待的时间[6]，而这正是大多数固定规模集群调度器的主要关注点。
• 挑战二：吞吐量保证的异构实例成本优化决策
  • 此外，基于云的集群可以利用云提供商提供的各种异构实例动态调整其组成，每种实例类型都有自己的成本。
    • 因此，这些因素将调度问题的目标从仅最小化作业完成时间（JCT）转变为在不影响作业吞吐量的情况下最小化总供应成本。

云上方案：有鉴于此，先前的工作提出了云环境下的调度器[6, 26, 57, 71]。然而，这些调度器未能解决某些难题，而这些难题对于以具有成本效益的方式托管批处理作业至关重要（第 2.3 节）。

• 前提：由于任务调度和实例供应从根本上是相关联的，因此应联合优化这两个方面，以确定最佳集群配置，其中包括组成集群的实例数量和类型以及任务到实例的分配。
  • 任务调度：应有效利用供应实例的可用资源，
  • 而实例供应：选择应与任务的需求相匹配。
• 挑战三：考虑干扰下的互补任务共置
  • 首先，集群中的批处理作业对资源的需求多种多样，且相关性较弱[19, 73]，这就提供了将多个任务共置到同一实例上的机会，以减少实例配置数量，从而降低总成本。
  • 然而，共置任务之间的干扰会导致性能下降，不同任务之间的性能下降幅度可能很大。
    • 图 1 显示，**仅两个共置任务的性能降低幅度就可达 0-36%**。
    • 因此，简单地将任务共置可能会导致作业持续时间大大延长，这反过来又会增加实例的正常运行时间，导致总体配置成本增加。
• 挑战四：迁移时间开销导致资源浪费感知
  • 此外，随着作业提交到系统或在系统中完成，最佳集群配置也会随时间发生变化。集群重新配置，即从一种集群配置切换到另一种集群配置，可以提高资源配置的成本效益。
  • 但涉及任务迁移和实例启动，会带来几分钟数量级的延迟，如表 1 所示。在这些延迟期间，已配置的资源仍处于闲置状态，导致成本浪费。因此，调度程序必须考虑长期供应成本节约与短期迁移开销之间的权衡。

图1：批处理任务在同一实例上共置时的性能。每个单元显示的是工作负载 1 与工作负载 2 同处一地时的归一化吞吐量。如表 7 所列，两个工作负载都获得了各自所需的资源，并被分配给同一实例上的不同 GPU 和 CPU。工作同时启动并运行 10 分钟。在此期间对每个作业的吞吐量进行测量，并将其除以该作业在未共置实例上的独立吞吐量进行归一化。

表 1.重新配置延迟。与实例相关的延迟基于 AWS EC2 上 126 个实例的测量结果，而与作业相关的延迟则是根据表 7 所列 10 个工作负载中 120 个作业的抽样测量结果得出的。

🛩创新

为了应对这些挑战，我们提出了 Eva，这是一种基于云的集群调度器，可降低托管长期批处理作业的总成本。在 Eva 中，我们建议将任务打包到一组实例中，以提高利用率并降低成本。

创新一：Eva 利用经济学中的预订价格来推导出最佳实例配置集和任务到实例的分配。

• (1) 为了将任务调度和实例供应联系起来，Eva 的调度算法从一个有效的启发式中汲取了灵感，该启发式可用于解决可变大小的装箱问题（VSBPP），众所周知，该问题具有 NP 难度[13]。
  • 该启发式优先考虑较大的桶类型和球，以减少已使用的桶数量和每个垃圾桶内未使用的空间，从而降低总成本。
  • 虽然启发式在单维环境中很有效，但由于存在多维资源（如 GPU、CPU、RAM），很难为实例类型和任务定义单一的 “大小”，因此将启发式推广到基于云的集群调度中会带来挑战。
• (2) 在 Eva 中，我们通过成本捕捉最小化资源分散的直觉，成本与所涉及的资源数量和类型成正比（第 4.2 节）。
  • 具体来说，任务按从高到低的预订价格[58]来考虑。
    • 预订价格是从经济学中借用的概念，代表买方愿意为商品或服务支付的最高价格，而实例类型则按从低到高的小时成本来考虑。
    • 在调度上，执行任务的预订价格是指如果任务在独立实例上执行而不共用位置，则会产生的每小时成本。
    • 这为评估任务分配到实例的成本效率提供了依据：分配到实例的一组任务的预订价格之和不应低于实例的实际每小时成本。

创新二：Eva 还考虑到了共置任务时的性能下降，并在考虑改变集群配置时定量评估了短期迁移开销与长期供应节省之间的权衡。

• (1) 为了考虑主机托管干扰造成的性能下降，我们扩展了预订价格，以考虑任务的吞吐量（第 4.3 节）。
  • 任务的吞吐量归一化预订价格代表用户愿意支付的最高价格，以便在干扰情况下以一定的吞吐量水平托管任务。
    • 例如，如果一个任务可以托管在一个每小时花费 3 美元的实例类型上，并且在没有共置的情况下吞吐量达到 100%，那么当它的吞吐量由于与其他任务共置的干扰而下降到 80% 时，用户愿意支付每小时 3 美元 × 0.8 = 2.40 美元。
    • 这样，即使存在多任务工作（同一工作中各任务的性能相互依赖），我们也可以根据性能对任务到实例的分配进行相同的成本效益评估（第 4.4 节）。
• (2) 基于吞吐量归一化预订价格，我们设计了两种调度算法：完全重新配置（§4.2）和部分重新配置（§4.5）。这两种算法结合使用，可在线更新集群配置。
  • a. “完全重新配置”考虑了当前系统中的所有任务，以确定能使配置成本最小的集群配置。
  • b. **”部分重新配置 “**保留了当前集群配置的大部分，只更新了任务和实例的子集，以尽量减少迁移开销。
  • 在每一轮调度中，Eva 都会运行这两种算法来生成两个候选集群配置，并从中选择一个。
    • 直观地说，当节省的潜在配置成本能够证明迁移开销的合理性时，尤其是当节省的成本可观且持久时，完全重新配置是首选。
  • 我们提出了一种定量方法（第 4.5 节）来估算节省的配置成本和迁移开销之间的权衡，Eva 将其作为在两个候选集群配置中做出选择的标准。

📊效果

AWS EC2 上的实验和大规模跟踪仿真表明，与为每个任务分配单独实例相比，Eva 降低了 42% 的成本，而 JCT 仅增加了 15%。

• 我们用 Python 实现了 Eva 和高保真模拟器。
  • 虽然目前的实现假定 AWS EC2 [55] 为云平台，但 Eva 的模块化设计（第 3 节）可确保轻松适应其他云提供商。
  • 任务在云中作为容器执行，确保不受框架或任务环境的限制。
  • 此外，Eva 还包含一个轻量级的迭代器应用程序接口（API），用于监控作业吞吐量，只需在用户端进行少量代码修改。
• 我们在 AWS EC2 上对 Eva 进行了评估，跟踪了 ML 和科学计算中的各种批处理应用（表 7）。
  • 我们发现，Eva 将总成本降低了 25%，将平均资源分配提高了 1.2 倍。
  • 此外，我们使用阿里巴巴生产跟踪[66]的 6200 多个作业进行的模拟显示，Eva 降低了 42% 的成本，即使在共置干扰和任务迁移延迟较高的不利情况下，也能持续实现显著的成本降低。

表 7.评估的工作负载和每个任务的资源需求。除 ResNet18 外，所有工作负载均为单任务工作。对于 CPU 需求，括号外的数字代表 P3 实例的需求，而括号内的数字（如有）代表 C7i 和 R7i 实例的需求。由于 C7i 和 R7i 实例的 CPU 频率较高，CPU 作业在这些实例上可以用较少的 CPU 达到相同的吞吐量。

⛳️未来机会

• 目前对共置干扰影响的分析刻画是黑盒的，且没有对共置预估方法合理性做理论分析。可以考虑利用基于白盒分析的方法预估，并全面地描述准确性。
• 目前共置干扰分析不考虑资源的影响，没有分析在不同资源下共置干扰是否会不同。

🧠疑问

1. “任务迁移和实例启动会带来几分钟级的延迟”和常识有所差别，理论上容器应该是秒级启动？且热迁移技术也能在秒级完成。
   1. 本文的前提是AWS EC2，虚机确实有较长的启动时间，这是否意味着在容器场景下可以忽略该冷启动问题？另外，实时租用AWS EC2（并在虚机上以容器形式启动任务）这个操作直观上很不符合实际，长租虚拟机、或直接租容器更像是符合实际情况的方案。
   2. 像本文一样，如果希望有论据，则应该在实际场景下收集数据以论证。
2. 引入“经济学中的预订价格”有什么好处？
3. 传统方法难道都没有考虑共置？对这部分现有研究分析很缺乏，这影响到了对本文创新性的评估。

---

---

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

🗺参考文献

[1] Tzu-Tao Chang and Shivaram Venkataraman. 2025. Eva: Cost-Efficient Cloud-Based Cluster Scheduling. In Twentieth European Conference on Computer Systems (EuroSys ’25), March 30–April 3, 2025, Rotterdam, Netherlands. ACM, New York, NY, USA, 18 pages. https: //doi.org/10.1145/3689031.3717483