【论文】精读笔记3-前沿-用RL进行VM重调度以整理碎片-B-相关工作发展脉络梳理

📖《Towards VM Rescheduling Optimization Through Deep Reinforcement Learning》

2025 年 UC Merced大学、 UC Berkeley大学、字节跳动团队 发表于 CCF-A 类会议 EuroSys。

系列博客：

1. VMR2L-初步略读笔记
2. VMR2L-整体逻辑精解笔记
3. VMR2L-相关工作发展脉络梳理笔记

🚧现状

调度算法

• 在实践中，字节跳动使用的是最佳拟合[27,50]，它将所有符合当前VM要求的PM根据加入VM前后的FR减少量进行排序，并选择减少量最大的PM。
• 向量装箱问题（α-VBPP）：VBPP[49]算法

重调度算法

a. 转化为装箱问题的最优化方法：

• 现状：基于成熟的MIP求解器进行求解加速[48,66]，无法满足严格的延迟要求（5s）。
  • 使用分支限界法[48]来确定最佳解决方案。
  • 混合整数规划（MIP）求解器：通过现成的MIP求解器解决，如CPLEX[2]和Gurobi[3]，它通过分支定界、切割平面等找到接近最优的解。在我们的实验中，我们使用Gurobi。
  • 分区优化问题（POP）[47]：它通过将问题随机拆分为子问题（每个子问题包含VM和PM的子集），对每个子问题应用MIP求解器，最后将结果组合成全局解决方案来解决最优化问题。
  • 蒙特卡洛树搜索（MCTS）[67]：由于传统的基于搜索的方法需要在推理时间内执行多次推出以获得良好的性能，我们使用DDTS[67]来修剪搜索空间。
• 问题：数据中心中VM和PM的总数很容易达到数千个或更多[63]，远远超过通常不超过几百个对象的装箱问题的典型规模[41,67]。

b. 转化为装箱问题的启发式方法：

• 现状：依赖人为设计的启发式方法[27]，导致次优解决方案。
  • 手工调整的启发式方法基于人类的专业知识，通过修剪搜索空间来克服可扩展性挑战。然而，启发式方法必须针对每个数据中心的不同集群条件单独设计，因为没有适用于所有场景的通用启发式方法。
  • 基于过滤的启发式算法（HA）：为了在短时间内获得可行的解决方案，启发式算法通常用于工业数据中心[4]。它们通常包括两个阶段：过滤和评分。在过滤阶段，我们计算每个VM的FR变化，就好像它从其源PM中删除一样，并且只选择对应于FR下降最多的VM候选。在评分阶段，我们计算FR的变化，就好像选择的VM被迁移到每个合格的PM。然后，我们贪婪地将选择的VM分配给导致FR下降最大的PM。上述两个阶段重复，直到达到MNL。
  • 向量装箱问题（α-VBPP）：我们将初始调度到重新调度的VBPP[49]算法推广。我们首先将整个事件分为 𝑀𝑁 𝐿/𝛼 阶段。在每个阶段，我们贪婪地删除导致最多片段的数量的VM，然后应用VBPP将它们视为传入的VM。我们仔细调整（在我们的情况下为10）以实现最佳的FR减少。
• 问题：
  • 首先，VM重调度问题涉及动态调整VM对PM的初始分配，需要考虑已有的VM关系，现有的装箱解决方案通常不考虑这些关系。
  • 其次，重新平衡已经装入箱子中的物品在其他装箱应用的背景下很少受到关注。

c. 面向优化问题的强化学习方法：

• 现状：RL被广泛用于选择分支变量等场景[23,25,26]，也可以应用于MIP问题下启发式方法的质量优化[9,58]。
  • Decima[44]：Decima使用图神经网络对VM和PM信息进行编码，并使用深度RL进行训练。Decima通过将VM重新安排决策分解为二维动作来平衡动作空间的大小和所需动作的数量，二维动作输出i）需要迁移的VM，ii）选择作为目的地的PM子集的上限。
  • NeuPlan[66]：在第一阶段，RL代理将问题作为图接收，并生成前几个VM迁移以修剪搜索空间。在第二阶段，它对剩余的MNL使用MIP求解器。松弛因子（在我们的例子中为30）用于控制MIP探索的MNL空间的大小。
• 问题：但都只面向传统简单场景，难以在VM重调度问题下获得较好训练结果。

🧠疑问

1. 重调度问题应该是一个自分布式系统出现以来就广受关注的问题。直觉上应该已经被研究很久了，在这个老问题下，本文做了什么“新”事？
   • VMR2L的特点体现在效率目标（5s）下的质量最优，而这个目标（5s）是根据业界数据集进行模拟实验推导出的，传统方法没有这样大规模的数据集因此也没有条件推导该目标。
2. 更进一步说，作为高校学生，在类似的大规模问题下，该如何有说服力地表明“效率目标”？

---

---

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

🗺参考文献

[1] Xianzhong Ding, Yunkai Zhang, Binbin Chen, Donghao Ying, Tieying Zhang, Jianjun Chen, Lei Zhang, Alberto Cerpa, and Wan Du. 2025. Towards VM Rescheduling Optimization Through Deep Reinforcement Learning. In Proceedings of the Twentieth European Conference on Computer Systems (EuroSys ‘25). Association for Computing Machinery, New York, NY, USA, 686–701. https://doi.org/10.1145/3689031.3717476