基于多重选择的MGGA算法在容器调度优化研究.pdf

2023 年第 10 期109计算机应用信息技术与信息化基于多重选择的 MG G A算法在容器调度优化研究魏建兵1 WEI Jianbing 摘要 容器即服务架构，正在被广泛采用，其三层的架构方式，给资源调度问题带来新的挑战。现代化云计算中心有能耗和利用率两个指标，这两个指标之间密切相关。对于容器、虚拟机、物理机的三层调度模型来说，调度的复杂性比两层结构高得多，同时中间虚拟机资源供给的类型和数量也会很大程度上影响总能耗。结合多种选择算子，并且观察到适应度的变化与虚拟机的数量有联系，因此在精英保留策略中增加了虚拟机数量这一指标。最后经过实验，提出的算法出现了更好的适应度。关键词 资源调度；能耗；锦标赛选择；精英保留策略；虚拟机 doi：10.3969/j.issn.1672-9528.2023.10.0231.大连交通大学计算机与通信工程学院 辽宁大连 1160280 引言云计算目前已经得到广泛的应用，通过网络以按需、易扩展的方式来租用获得所需资源，用户只需提供客户终端1。云计算得到广泛应用的原因在于，其可以快速搭建应用，具有更大的灵活性和扩展性，以及为用户节约基础设施的成本等优点。因其规模较大，也带来了一些问题，比如功耗、运营费用和环境污染等。其中，能源消耗是最重要的。根据相关文献资料可知，2018 年，中国数据中心的用电总量超过了整个上海市全社会的用电总量，占中国全社会用电量的 2.35%；2030 年，数据中心能耗最高可以达到 1.4 万亿千瓦，占全社会能耗的 20%。因此，研究人员需要关注数据中心的能耗问题，以避免资源浪费，提高能源利用效率。目前，云计算的主要运行模式有四种：软件即服务（SaaS）、平台即服务（PaaS）、基础设施即服务（IaaS）、容器即服务（CaaS）2。容器由于其轻量级、较好的隔离性，得到了广泛的应用，CaaS 就是其中的一员。在过去很长一段时间内，云计算底层只是应用虚拟机和物理机两层，虽然给当时那个年代的云计算提供了不少便利，但由于虚拟机本身的量级较大，反应迟钝，对当前快速发展的时代不能够完全适应，因此出现了容器这样一个技术。在当前流行的 CaaS 架构中，容器需要放在虚拟机上，然后虚拟机被放置在物理机上。在 CaaS 中，容器、虚拟机和物理机这三层架构的分配问题是一个 NP-hard 问题，放置策略的不同影响着资源的利用率，进而影响数据中心的能源消耗。如何对三者进行合理的放置，是值得深入研究的问题。虚拟机最优放置的策略在于把多个虚拟机放置在单个物理机上，提高资源利用率，容器就是放置在单个虚拟机上。Falkenauer 提出了分组遗传算法（GGA），并启发了许多解决 VM 分配问题的研究。与其他遗传算法不同，分组遗传算法是一个可变长度的方法，它省去了普通遗传算法中编码和解码的过程，每个箱子都是其中一部分解，多个箱子组合成一个解集。原本的解决方案是在一个二层架构上。Tan3的文章将其扩展至三层架构，并对其中的交叉和 unpack、merge 算子进行了改进。其在选择算子的问题上采用了锦标赛算法，锦标赛算子由于经常会选择适应度最高的个体，在寻找全局最优解的问题上相对于轮盘赌表现较弱，但其收敛速度较快。轮盘赌在寻找全局最优解的问题上表现更好，但是其收敛速度较慢。本文采用一种结合两种算子优点的方法。根据数据结果分析，随着适应度提升，其虚拟机的数量相应地减少，二者是负相关的关系。因此，本文考虑把虚拟机数量作为第二个指标放在精英保留策略中。同时，在初始化阶段，把所有容器随机分配给虚拟机，实现更加离散的初始解分布，加深算法的寻优能力。可见，本文的改进集中在以下两点中。一是对分组遗传算法选择算子的改进，采用了结合锦标赛算法和轮盘赌算法结合的方法，兼顾收敛速度以及全局最优的寻找，同时在精英选择策略中添加了虚拟机数量这个指标。二是在初始化阶段，采用更加随机的策略，把容器随机分发到虚拟机中，让其初始化结果更加分散。1 相关工作尽管容器技术作为一种云服务模型得到了普及，但在降低 CaaS 数据中心功耗方面的努力仍然有限。在下面的讨论2023 年第 10 期110计算机应用信息技术与信息化中，将根据考虑的级别数来讨论这些工作，即仅容器放置级别或容器和 VM 一起放置级别。为了单独解决容器放置问题，本文进行了多种尝试。例如，对 Nardelli 等人4将此任务作为整数线性规划问题进行了处理。他们的解决方案考虑了容器和 VM 资源类型的异构性。在同一背景下，Boukadi 等人5提出了一种算法，通过结合 First-Fit 方法和线性规划技术来解决相同的问题。本文将他们提出的方法与基于 VM 的部署方法和基于 First-Fit 的方法进行了比较。同样，Nanda 等人6提出使用一种基于深度学习的方法，称为 Fit-for-Packing。本文将该问题视为多资源装箱问题。这种方法直接将接近最优的容器映射到物理机上，而不考虑虚拟机。Chen 等人7提出使用稳定匹配理论方法来进行容器部署。其核心思想是尝试通过计算容器对虚拟机的偏好来选择容器的主机虚拟机，从而减少容器迁移的次数。减少容器迁移的数量应该会降低数据中心的能源消耗。此外，一些研究人员将容器整合问题作为联合优化问题进行了研究，即同时考虑容器放置（为一组容器选择一个 VM，或 VM 选择）和 VM 放置。例如，Mann8提出了一种方法来解决真实世界工作负载跟踪的动态容器整合联合优化问题。同样，Shi 等人9分别在两个级别/阶段使用粒子群优化（PSO）技术解决了联合优化问题。本文建议在第一阶段使用 First-Fit 技术容器放置，而在第二阶段，使用 PSO 将 VM 映射到活动 PM。Shi 等人10应用了一种利用 NSGA-II 算法的方法来找到最合适的主机，其中包含每次重新分配时需要迁移的容器。一旦找到这些主机，就会应用 First-Fit 方法将迁移容器映射到新的主机 PM 上。Tan 等人11分两个阶段解决了这个问题。本文结合了两种技术来创建具有手工规则的遗传编程超启发式来解决容器放置问题。首先，使用第一种技术来决定容器是分配给新的 VM 还是分配给现有的 VM，将第二种技术用于 VM 选择或创建某种类型的 VM 的过程中。其次，提出使用 First-Fit 方法将 VM 映射到资源充足的 PM 上。Piraghaj 等人12提出了一个由两个阶段组成的框架搜索应使用静态欠载（UL）和过载（OL）阈值迁移的过载或欠载容器。然后，“MCor”和“MU”两种算法决定要迁移的容器。最后，该框架使用三种 bin-packing 主机选择算法（即 First-Fit、随机和 Least-Full 主机），为迁移容器映射迁移目标 VM。分布式系统中优化能源效率的问题也可以通过建模来解决。Bessis 等人13针对分布式系统中的消息交换优化任务提出了一个模型。其提出的方法最大限度地减少了实体通信时的消息总数，因此，该模型最大限度地减少了放置这些消息所消耗的能量。Sirbu 等人 14提出了一个配置和启动持续时间预测模型作为金属即服务（MaaS）系统中的多元回归任务。其所提出的模型有助于减少已配置资源的空闲时间，从而降低能耗。Vasile 等人15对异构分布式计算调度的资源感知任务进行了建模。本文首先提出了一种将可用资源分层聚类的算法，然后在第二阶段将任务分配给资源组，最后对每组资源使用经典的调度算法。2 问题定义本文所进行改进的云计算模型类似 CaaS 模型，该模型包括三层架构：容器、虚拟机和物理机。首先把容器放到虚拟机上，然后把虚拟机放到适合的物理机上。本文考虑的一个目标就是总的物理机功耗最低，不同的 CP 会影响服务器的运行效率，进而提升所需的功耗，加大企业维护成本，因此本文想要找出一种最佳的 CP 结构，以使总的能耗最低。在进行两层分配的时候，需要宿主有一定的资源来接纳，其涉及 CPU、内存、硬盘大小等，本文只考虑其中两个因素，即 CPU 和内存。本文的模型和文献 3 类似，容器分为500、1000、1500 个总数量，虚拟机的种类有 20 种，这些虚拟机所能容纳的资源都不一样，当创建虚拟机时，就从这 20种虚拟机中选择一个，物理机暂定数量为不限个数，每个物理机所拥有的 CPU 和内存资源都相同，容器先放置在虚拟机中，然后虚拟机放置在物理机上。根据资源要求，有以下几个限制条件。（1）每个容器只能单独分配给一个虚拟机。（2）每个虚拟机所容纳的容器资源不能超过该虚拟机的资源。（3）每个已经创建的虚拟机只能分配给一个物理机。（4）每个物理机所容纳的虚拟机资源不能超过该物理机的资源。对于本文所针对的能耗问题，其计算公式为：()utilization PMiidleMax idle pmiEEEE=+（1）本文采用的是一个线性的主机功耗模型，空闲状态下的主机能耗是满载状态下功耗的 50%70%。根据公式（1）计算出单个物理机的功率，然后把所有物理机的功耗加起来就是总的功耗。3 改进的群遗传算法如前文所述，文献 3 的群遗传算法由于进行交叉变异的父代个体的同质性，导致其更容易陷入局部最优，因此本文把轮盘赌算法加了进去，把子代个体的生成分成 4 个部分。同时，在观察了原本算法结果与其虚拟机数量的分布后，发现虚拟机数量越少，结果越好，因此把虚拟机数量作为精英选取算法中的另一个权重因素。算法流程如下。算法 1：改进的群遗传算法 2023 年第 10 期111计算机应用信息技术与信息化输入：容器集合，虚拟机类型集合，物理机集合输出：容器的分配方案Pop 初始化Sel_method(i)是第 i 种选择算法.i=1,2,3,4Pop_num(i)是 第 i 种 选 择 算 法 需 要 生 成 的 个 体 数量,i=1,2,3,4while Iter=Max_iter do 对 pop 进行分割 Pop_part(i)是第 i 种选择算法的群体,i=1,2,3,4New population=elitismfor i=1,2,3,4 dofor j=1,2,pop_ num(i)doparents=sel_method(I,pop_part(i)children=gen crossover(parent)unpack(children)merge(children)将 children 添加到 new pop num(i)中将 new pop num 中所有个体添加到 new pop 中Pop=new pop3.1 种群初始化本文所采用的解决方案的结构是容器放置的最直观表现形式。如图 1，这样的表示方法在迭代过程中，可以直接对其中的某个物理机或者虚拟机进行改变，对于一些资源需求的限制条件可以直接判断，不会影响其他物理机和虚拟机。锦标赛群体A1A2 A3轮盘赌群体B2 B3B1A2 B3B2 A3新群体图 1 多重选择算子在种群初始化过程中，容器与虚拟机的分配遵循FF算法。首先依次对容器进行分配，对于每个容器，依次寻找已存在的虚拟机，若能放置就直接放进去，若不能则随机选择一个可以放置该容器的虚拟机种类。然后每创建一个新的虚拟机，就需要依次检查物理机，若能满足资源需求，则直接放进去，若不能则寻找下一个。3.2 选择算子考虑到文献 11 使用的锦标赛算法有一定的局限性，在寻找全局最优解方面不如轮盘赌，因此本文考虑结合两种算子的选择方式。把群体分成两个部分，一个是锦标赛部分，另一个是轮盘赌部分，选出父代个体，分别进行各自的遗传进化，并且随机选出两部分中的少量个体，直接让锦标赛群体中选出来的个体和轮盘赌群体选出来的个体进行交叉变异操作。每个选择算子群体分为两部分，其中一部分是运用当前选择方式，另一部分是用来直接和另一个群体进化，产生子代。A1 运用的是锦标赛选择方式，B1 运用的是轮盘赌选择方式。锦标赛群体另一部分为 A2、A3，轮盘赌群体另一部分为 B2、B3。A2 与 B3 直接交配进化，B2 和 A3 直接进行交配进化，最后产生的子代分别再放回到两群体中。3.3 交叉操作交叉是对父母基因的一次融合和选择，为了让其更加趋近于想要的结果，要控制选择的方向。在本文中，交叉的方向是高的利用率，根据公式（1），每多一个开机的物理机就会多出来一个运行的能耗常量。因此，本文的目的由适应度最少转换为己用的物理机最少。进一步说，已用的物理机越少，每个物理机中存放的容器就越多，也就是物理机的利用率越高。最后得出结论，适应度最少代表着各个物理机的利用率最高，最优的解决方案一定是物理机的空闲资源最少，利用率最高的。在文献 3 中，对两个解决方案中每个对应的物理机进行比较，其中利用率高的遗传到子代，利用率低的则被抛弃。由于二者每个物理机中放置的容器都不同，可能往后选择物理机时会漏掉一些容器，因此需要把这些容器拿出来，根据重排运算符进行重新分配。3.4 解包和合并操作Unpack 操作使用了轮盘赌的机制，轮盘赌的依据是各个物理机的利用率，其目的是尽可能把低利用率的物理机找出来，让其中的容器和虚拟机完全释放出来，然后根据重排运算符重新分配容器，这一步相当于是原遗传算法中的突变操作。Merge 运算符是对现有的虚拟机进行容量升级，用一个更大的虚拟机代替原本一个或者两个较小的虚拟机。其目的是减少空闲资源，由于每个容器的大小都不是固定的，因此放入虚拟机中的容器大概率也不能全部占满空间，这样就会剩下一些多余的资源，造成了浪费。对此，可以用大的虚拟机代替多个小的虚拟机，减少可用资源的浪费，并减少虚拟机本身开销造成的资源浪费。3.5 重排运算符对于上面解包和交叉操作得出来的待分配的容器，文献3 根据重排运算符来进行分配，其主要的操作是查看每个虚2023 年第 10 期112计算机应用信息技术与信息化拟机中两个最小的容器是否能被待分配的目标容器替换，若能，则把两个较小的容器拿出来，把目标容器放进去，然后根据FF算法把两个较小的容器再重新分配到其他虚拟机中。该操作的核心思想是较小的容器更容易分配。4 实验本文通过与原 GGA 算法以及基于规则的 FF&BF 算法进行比较，采取的数据集与文献 3 的类似，观察结果，验证本文算法改进的必要性。实验初步结果以及分析如下。4.1 测试用例以及实验环境本文采用的测试用例与文献 3 一样，容器是里面具体负载的运行数据；虚拟机分为两种，一种是现实世界真实的虚拟机状况，另一种是模拟的、随机资源需求的虚拟机状况。实验测试是在配备 2.4 Ghz IntelCore i5-9300H CPU 与 8 GB RAM 的计算机上实施的。使用的操作系统是 64 位Windows 系统，用 Python 实现代码。4.2 参数设置对于本文的算法与 GGA 算法，其运行的交叉率都是70%，个体数量设置为 101，最大迭代次数为 100，精英主义大小为 5，锦标赛选择大小为 7。测试用例分为 3 种，即500、1000、1500 个容器。本文中两种群体的个体的数量都是48，因此 A1、B1 中个体数量为 44，A2 和 A3 分别为 2，B2和 B3 也是 2。4.3 实验结果本文的主要目的是能耗最小化，主要针对能耗这个指标，因此本文展示了三种算法随着迭代次数的能耗变化，如图2、图 3，这两个图分别是在真实世界下的虚拟机能耗和模拟的虚拟机能耗。02040608010010000105001100011500120001250013000能耗(Kwh)迭代次数(次)GGA MGGA FF&BF 能耗/(kWh)迭代次数/次图 2 1500 个容器下三种算法在真实世界虚拟机下的能耗状况迭代次数/次能耗/(kWh)020406080100950010000105001100011500120001250013000能耗(Kwh)迭代次数(次)GGA MGGA FF&BF图 3 1500 个容器下三种算法在模拟虚拟机下的能耗状况在初始点，本文算法的变化幅度较大，这是因为本文采取了更加随机的策略，使解集更加分散地遍布在解空间中。在前期迭代过程中，本文算法与 GGA 算法相差不大，但之后迭代中 GGA 算法陷入局部最优值，而本文的算法还有进一步跳出局部最优的能力，这就证明了本文算法的有效性。在前 20 次迭代中，本文算法收敛的速度较慢，这是因为结合了轮盘赌。表 1 展示了各种容器数量下的能耗的平均值和标准差。从表 1 中可以看出，本文在高容器数量下的表现比其他两种算法好，并且在模拟的更加随机的资源供给虚拟机状况下，本文的表现比真实世界的更好，这证明了本文适合处理更加复杂的状况下的资源调度。在低容器数量下，如 200 和 500，本文与其他两种算法的表现区别不大。表 1 在置信水平 95%下的平均值和标准差真实20050010001500MGGA1026232122.3679096.510 29068.5GGA10241.532342.16924156.210 410120.8FF&BF10360330007600011 6240模拟20050010001500MGGA890125605.358321329697154GGA8900.626205.862309410 050176FF&BF9100275006564011 7000综上所述，本文算法在寻找全局最优解方面比 GGA 算法和 FF&BF 算法更加优秀。5 结论在本文中，针对容器调度中的能耗这一问题，提出了一种改进的遗传算法，其主要是在 GGA 这个群遗传算法的基础上，采用了一种多种群选择的方式，并且结合了一种随 2023 年第 10 期113计算机应用信息技术与信息化机的策略方法，同时对精英选择方式进行改进，进一步地对GGA 算法进行优化，得出本文的 MGGA 算法。MGGA 的主要优点是对 GGA 算法全局最优解的寻找能力的拓展，实验结果也证明了该创新的有效性。在未来工作中，本文将考虑将其他优秀的算法与本文算法结合，并且考虑更多的指标，如 QoS、负载均衡等。参考文献：1 ZHANG Q,CHENG L,BOUTABA R.Cloud computing:state-of-the-art and research challengesJ.Journal of internet services and applications,2010,1(1),7-18.2 PIRAGHAJ S F,DASTJERDI A V,CALHEIROS R N,et al.Efficient virtual machine sizing for hosting containers as a serviceC/IEEE World Congress on Services.Piscataway:IEEE,2015:31-38.3 TAN B,MA H,MEI Y.A group genetic algorithm for resource allocation in container-based cloudsC/European Conference on Evolutionary Computation in Combinatorial Optimization.Cham:Springer Nature Switzerland AG,2020:180-196.4 NARDELLI M,HOCHREINER C,SCHULTE S.Elastic provisioning of virtual machines for container ceploymentC/International Workshop on Autonomous Control for Performance and Reliability Trade-Offs in Internet of Services(ACPROSS 2017)at 8th ACM/SPEC International Conference on Performance Engineering(ICPE 2017).S.l.:s.n.,2017:5-10.5 BOUKADI K,GRATI R,REKIK M,et al.From VM to container:a linear program for outsourcing a business process to cloud containersC/On The Move Confederated International Conferences.Rhodes:Springer,2017:488-504.6 NANDA S,HACKER T J.RACC:resource-aware container consolidation using a deep learning approachC/Proceedings of the First Workshop on Machine Learning for Computing Systems.S.l.:s.n.,2018.7 CHEN F,ZHOU X,SHI C.The container deployment strategy based on stable matchingC/2019 IEEE 4th International Conference on Cloud Computing and Big Data Analysis.Piscataway:IEEE,2019:215-221.8 MANN Z.Resource optimization across the cloud stackJ.IEEE transactionson parallel and distributed systems,2017,29(1):169-182.9 SHI T,MA H,CHEN G.Energy-aware container consolidation based on PSO in cloud data centersC/2018 IEEE Congress on Evolutionary Computation.Piscataway:IEEE,2018:1678-1685.10 SHI T,MA H,CHEN G.Multi-objective container consolidation in cloud data centersC/In Australasian Joint Conference on Artificial Intelligence.Berlin:Springer,2018:783-795.11 TAN B,MA H,MEI Y.A hybrid genetic programming hyper-heuristic approach for online two-level resource allocation in container-based cloudsC/In 2019 IEEE Congress on Evolutionary Computation.Piscataway:IEEE,2019:2681-2688.12 PIRAGHAJ S F,DASTJERDI A V,CALHEIROS R N,et al.A framework and algorithm for energy efficient container consolidation in cloud data gentersC/In 2015 IEEE International Conference on Data Science and Data Intensive Systems.Piscataway:IEEE,2015:368-375.13 BESSIS N,SOTIRIADIS S,POP F,et al.Using a novel message-exchanging optimization(MEO)model to reduce energy consumption in distributed systemsJ.Simulation modelling practice and theory:international journal of the federation of european simulation societies,2013,39:104-120.14 SIRBU A,POP C,SERBANESCU C,et al.Predicting provisioning and booting times in a metal-as-a-service systemJ.Future generation computer systems,2017,72:180-192.15 VASILE M A,POP F,TUTUEANU R I,et al.Resource-aware hybrid scheduling algorithm in heterogeneous distributed computingJ.Future generation computer systems,2015,51:61-71.【作者简介】魏建兵（1997），男，山西阳泉人，硕士研究生，研究方向：容器调度。（收稿日期：2023-04-11 修回日期：2023-04-23）