通过数学规划模型，在云数据中心实现可扩展的、考虑能源效率的虚拟机分配

《Future Generation Computer Systems》：Scalable energy-aware VM allocation on cloud data centers through mathematical programming models

本文提出了一种基于数学规划模型的虚拟机分配策略，通过Micro和Macro两种模型与可扩展算法框架的结合，解决了传统启发式方法在异构环境和能效优化上的局限性。实验表明，该策略在收益、能源消耗和扩展性方面分别提升了16%、54%和线性可扩展性，显著优于现有方法。

　　云数据中心已成为现代社会不可或缺的支柱，推动了人工智能创新、全球互联和数据驱动的进步。随着这些中心的规模和复杂性不断增加，对可持续和高效解决方案的需求也日益迫切，以应对运营和环境方面的挑战。虚拟机（VM）分配问题正是这些挑战的核心，直接影响能源消耗、可扩展性和成本效益。尽管启发式方法因其快速执行时间而被传统上广泛采用，但它们在处理异构环境和日益增长的能源感知需求方面表现不佳。在这项工作中，我们重新定义了数学规划模型的潜力——这些模型通常因可扩展性限制而被认为不适用，通过将模型嵌入可扩展的算法中，使其能够分配计算负载并利用求解器能力。这种方法实现了线性可扩展性——这是数学规划领域前所未有的里程碑，使我们能够整合VM分配问题中的详细和异构方面。最终的算法在可扩展性和解决方案质量上显著优于最先进的启发式和元启发式方法，实现了平均16%的净收益增加、54%的总能耗减少和能源效率提高超过一倍。我们的算法旨在满足现代云数据中心日益变化的需求，能够高效地扩展以管理增长的负载，适应异构性，并通过优先考虑能源效率，符合可持续性和监管要求。

虚拟化技术是云数据中心的重要推动因素，因其众所周知的优势。在管理方面，它们的敏捷和细粒度资源分配与平衡机制，使得集群利用率更高，故障恢复更有效。特别是，它们可以将多个虚拟机集中在一个物理机上，提高利用率，同时节省能源，因为未使用的物理机可以被挂起。此外，虚拟机的实时迁移允许重新考虑虚拟机的分配，以适应负载变化和物理机的可用性。

因此，能够准确且快速地解决虚拟机分配问题（即确定在哪个物理机上运行虚拟机）是云数据中心高效运作的基础。然而，这并非一项简单的任务。同质物理机的虚拟机分配问题可以与装箱问题相关，装箱问题已知是NP难的。由于迁移的动态性质和物理机的异构性（在容量、性能、能耗和其他特性上的差异），这个问题变得更加复杂。这些差异不仅使目标更加复杂，还引入了额外的因素和约束，显著增加了问题的复杂度。

在当前解决虚拟机分配问题的先进解决方案中，数学规划往往被启发式方法所忽视。尽管数学规划模型提供了诸多优势——如更高的解决方案质量、更大的灵活性以及轻松整合新约束或适应目标函数的能力——但它们通常被认为是非可扩展的，因为随着问题规模的增长，解决时间迅速增加。在大型云数据中心中，使用纯数学规划模型可能是不可行的，导致对启发式方法的偏好。

在这篇论文中，我们提出了一种新的视角，即利用数学规划模型作为元启发式方法，而不是用于推导严格最优分配的工具，从而实现可扩展的模型，这些模型能够持续优于最先进的启发式算法。这种范式转变将使数学规划模型在解决云数据中心和超级计算环境中的虚拟机分配问题时变得特别有吸引力，因为在这些环境中异构性已成为常态。

与传统方法不同，我们的策略并不依赖数学模型直接解决虚拟机分配问题。相反，我们的模型作为算法的构建块，这些算法实际上是虚拟机分配问题的实际求解器。在这种视角下，我们介绍了一种全面的云数据中心虚拟机分配策略，该策略采用了可扩展的数学规划模型。这些模型不追求精确的最优分配，而是专注于当前时间步，简化问题并显著减少求解时间。

虽然我们工作中提出的模型Micro和Macro可以作为独立求解器运行，但它们被设计为算法中的基础构建块，这些算法是虚拟机分配问题的实际求解器。在本文中，我们提出了五种不同的算法Maxi、Mini、Hybrid、Compound和Multilayer，这些算法通过以不同方式组合模型来分配虚拟机的负担，从而有效加速执行。需要注意的是，根据输入的不同，Micro模型可以承担不同的角色，从而在算法中发挥不同的构建块作用。

每个算法都协调输入和输出在模型与其他辅助组件（即可扩展的支撑结构）之间的流动，将虚拟机分配过程分布在不同的构建块上。例如，不同的构建块负责在活跃的物理机上分配虚拟机和管理物理机的开关状态。这种工作负载的划分降低了个体数学问题实例的复杂度，提高了可扩展性。

此外，我们的算法采用了可扩展的支撑结构来增强模型的求解性能。这些支撑结构包括，例如，用于工作负载分布的协议，如Divide et Impera；用于引导求解引擎向最优解靠近的技术，如Warmstart；以及用于应对求解时间缓慢情况的应急措施，如备份分配。这种支撑结构方案解决了数学规划求解时间的指数增长，使我们的虚拟机分配算法在现代场景中能够有效可扩展。

通过我们对数学规划使用的可扩展方法，我们的模型可以无缝整合虚拟机分配问题的许多关键方面，如迁移成本（包括能源和时间），以及（异构）物理机的各种特性，包括容量和（非线性）性能和能耗曲线。此外，我们能够轻松添加特定于客户要求的约束——这是启发式方法难以实现的优势。总体而言，我们能够提供一种更强大的解决方案，以应对虚拟机分配问题在异构系统中日益增加的复杂性。

我们的贡献可以总结如下：

- 一种可扩展的数学规划方法，用于解决云数据中心的虚拟机分配问题。
- 两个数学规划模型，作为分配算法的构建块，能够整合复杂的方面，如异构容量、非线性性能和能耗曲线，以及迁移成本。
- 五种不同的算法，通过以不同方式组合模型来以可扩展的方式执行实际求解，同时使用各种支撑结构来增强模型的性能。
- 对真实和合成工作负载的广泛实验，展示了我们的算法在利润、能源效率和可扩展性方面优于最先进的启发式方法。

本文的其余部分结构如下：第2节回顾相关工作，讨论数学规划和启发式方法在虚拟机分配问题上的最新进展。第3节概述了初步假设，并描述了所提出的数学模型Micro和Macro，详细说明了它们的目标、决策变量和约束。第4节描述了使用的支撑结构，如Divide et Impera和Warmstart，这些支撑结构有助于实现可扩展性和高效执行。第5节介绍了五种算法Maxi、Mini、Hybrid、Compound和Multilayer，这些算法是虚拟机分配问题的实际求解器。第6节呈现了实验设置，包括工作负载跟踪、指标和结果分析。最后，第8节总结了我们的贡献，并提出了未来研究的方向。

为了应对云数据中心日益增长的规模和复杂性，我们提出了一种基于数学规划模型的虚拟机分配策略，将模型嵌入可扩展的算法中，以实现计算负载的分布和求解器能力的利用。通过引入各种支撑结构，如Divide et Impera和Warmstart，我们实现了线性可扩展性，使我们的算法能够高效处理大规模的虚拟机分配问题。这些算法在处理大规模负载时表现卓越，同时能够适应异构性，并通过优先考虑能源效率，满足可持续性和监管要求。

在实验部分，我们使用了真实和合成的工作负载进行测试，结果显示我们的算法在利润、总能耗和可扩展性方面均优于最先进的启发式方法。通过将数学规划模型与支撑结构相结合，我们能够有效处理虚拟机分配问题中的复杂因素，从而实现更高的解决方案质量。此外，我们的算法在不同规模的云数据中心中表现良好，表明它们在处理大规模问题时具有良好的可扩展性。

我们的研究还发现，数学规划模型在处理虚拟机分配问题时，通过使用支撑结构，如Divide et Impera和Warmstart，可以显著减少求解时间，同时保持较高的解决方案质量。这些支撑结构使得数学规划模型能够处理大规模问题，从而实现线性可扩展性。这表明，数学规划模型在处理云数据中心的虚拟机分配问题时，可以成为一种高效且有效的解决方案。

通过本研究，我们展示了数学规划模型在解决虚拟机分配问题时的潜力，特别是在处理大规模和异构性问题时。我们的方法不仅提高了解决方案的质量，还实现了显著的可扩展性，这在传统方法中是难以实现的。这些成果为未来在云数据中心和超级计算环境中进一步研究数学规划模型的应用提供了重要的参考。