云计算环境下的资源分配关键技术研究综述

姜栋瀚，林海涛

(1.海军驻上海江南造船(集团)有限责任公司军事代表室，上海 201913;2.海军工程大学 电子工程学院，武汉 430033)

0 引 言

随着信息技术的进步和大数据时代的到来，越来越多的人能够访问更广泛的信息资源。以往单个物理机难以对大规模数据进行处理，用户急需可扩展、可定制、高效可靠的计算模式来支撑其应用需求。在这种情况下，分布式计算[1]、网格计算[2]和效用计算[3]混合演进形成了现如今较为成熟的云计算[4]服务模式和商业模型。云计算基于大量分布式虚拟环境，允许用户租赁满足其需求的资源，并动态运行广泛的应用程序。然而，在云计算发展过程中，资源分配机制始终是数据中心效能优化中亟待解决的问题，也是云计算领域内的研究热点。由此可见，提高云计算资源灵活性和可扩展性是十分重要的。

1 云计算概述

1.1 基本概念

美国国家标准与技术研究院(National Institute of Standards and Technology，NIST)将云计算定义为一种用户能按需访问共享资源池的计算模式[5]，其旨在为用户提供可靠、定制和具有服务质量保证的动态计算环境。其实，云计算是互联网技术、分布式计算、网格计算和系统管理等几种技术融合的结果。虚拟化是对物理资源的软件抽象，是云计算中的关键技术之一[6]。通过虚拟化将所有应用程序和文件都托管在由数千台计算机互连在一起的云上，并向用户提供类似于传统公用事业服务(即水、电、煤气和电话)的计算资源。云计算遵循“按需付费”模式，用户不需要购买软件或计算平台，可以即时扩展容量，而无需投资新的基础设施。

1.2 资源类型

云环境中的处理单元称为虚拟机[7](Virtual Machine，VM)，数据中心作为云计算的基础设施，通过虚拟机使得物理服务器(Physical Machine，PM)提供的资源能有效共享。云数据中心[8]需要处理大量虚拟机，因此高可用性、低时间跨度、低能耗和满足SLA是云数据中心中最重要的性能指标。

云数据中心的资源主要分为以下几种：

物理服务器：又称为物理服务器，它是云数据中心的基本组成部分。在资源管理过程中，物理服务器为虚拟机的运行提供载体。

虚拟机：云提供者通过虚拟化技术管理其基础架构，其中虚拟机以镜像文件形式动态地分配到物理服务器，并从物理服务器中释放。为了满足功耗、成本和服务水平协议等要求，虚拟机可以随着负载变化而迁移到不同的物理服务器。

物理资源：由物理设备组成的资源集合，包括CPU、内存、磁盘等。

虚拟资源：通过虚拟化技术将物理设备有效集成，隐藏了物理资源的复杂性，从而形成虚拟资源池，其中包括计算资源、存储资源、网络资源等[9]。云提供者根据用户需求对共享资源进行分配，也可以根据负载变化进行动态调整。

1.3 角色设定

在本文中，设定云数据中心主要包含以下两种角色：

终端用户：终端用户包括一些企业机构和个人，每个用户对所需的计算能力等方面都有预期要求。用户可以租赁云资源提供者提供的各类资源以满足其业务需求，这有效减少了用户的资源规划和不必要的前期投资。一般来说，终端用户和云提供者签订合同量化为服务水平协议(Service Level Agreement，SLA)，以描述每个用户所需的计算能力等方面的预期要求。

云提供者：云提供者在接受到用户请求后，根据任务类型、大小和服务水平协议向用户提供虚拟机资源。当虚拟机资源不足时，根据虚拟机大小、类型等参数的不同，将新的虚拟机合理分配到物理服务器或者从物理服务器中取消分配以提高资源利用率，也可以根据负载变化将其迁移到不同的物理服务器以满足服务水平协议。当虚拟机资源不足时，将直接将业务请求调度到虚拟机上。

2 云计算资源分配框架及其研究现状

2.1 资源分配管理框架

在介绍本文提出的云数据中心资源分配管理框架之前，我们有必要先说明资源分配管理模块在整个云计算架构中的地位。

2.1.1 云计算整体参考架构

由于云计算分为IaaS、PaaS和SaaS三种类型，不同的机构又提供了不尽相同的解决方案，目前还没有统一的体系结构。本文基于现已提出的云计算解决方案，结合实际构造了一个参考架构，如图1所示。其中，管理中间件是云计算架构中极其重要的组成部分，其包括用户管理、安全管理和资源分配管理等模块。其中，建立高效的资源分配机制是云计算资源分配管理中需要解决的主要问题[10]，也是本文的研究重点。

图1 云计算参考架构图

2.1.2 传统的资源分配管理框架

在传统的云计算资源分配管理中，通常是初始阶段将虚拟机分配到物理机，然后将任务分配到虚拟机中，从而实现两级分配架构[11]。然而，在任务开始执行之后，由于工作负载的频繁变化和云环境的动态性，现有的虚拟机资源往往难以满足应用需求，需要实时启动新的虚拟机导致不必要的时间延迟；或者现有虚拟机数量较多，引起了不必要的开销，从而导致后期大量频繁的虚拟机迁移。本文将传统的云计算资源分配管理问题分为资源映射、资源调度两级分配架构。

资源映射：资源映射实际为虚拟机放置过程。云提供者根据虚拟机请求类型和大小，将其分配到不同的物理服务器，实现虚拟机到物理服务器的合理映射，本文将这一过程称为资源映射。

资源调度：本文假设工作负载是由不同用户提交的作业集合。每个作业中的任务需要按顺序进行处理，任务在不同类型的虚拟机上可能具有不同的执行时间和运行速度。因此，当用户提交业务请求时，云提供者通过各种任务参数和SLA，可以优先选择不同的虚拟机类型，并将任务队列合理调度到虚拟机资源上，本文将这一过程称为资源调度。

资源分配管理是云数据中心的核心问题，这些问题通常借助于性能建模、优化算法产生最优或接近最优的解决方案，以最小化开销提高整个系统的效率。图2为云计算资源分配管理关系图。

图2 云计算资源分配管理关系图

2.1.3 提出的资源分配管理框架

云数据中心使用户可以在任何地方、任何时间访问应用程序和相关数据，然而，在云数据中心中满足用户需求的一个主要挑战就是资源的合理分配[12]。众所周知，现有的云数据中心资源分配管理大多是由云提供者预先设定实例化不同类型的虚拟机，终端用户通过租赁或购买虚拟机来运行自己的业务应用。面对应用负载变化，云提供者多采用被动式应对，通过虚拟机迁移等措施进行资源调整。然而频繁的虚拟机迁移会在一定程度上增加停机时间，难以满足SLA需求。

图3 新型云计算资源分配管理框架

如图3所示，本文提出一种新的资源分配管理框架，将传统的两级分配机制改成平行分配机制，并增加了资源预测模块，可以更好地应用于实时运行的数据中心中。具体来说，新资源分配管理框架通过资源预测进行决策，避免了现阶段虚拟机过量导致的资源浪费，也可以提前进行虚拟机迁移从而避免任务运行时大量的停机时间。另外，当现阶段虚拟机不足时，会导致新启动虚拟机时间过长，难以满足SLA，本文提出的资源分配管理框架可以有效解决这一问题。

如图所示，用户请求被提交给工作流管理器，形成任务队列。由资源预测模块预测数据中心中未来的VM请求数量。跟踪判别模块负责跟踪任务队列大小或虚拟机状态等系统信息。对于每个提交的任务，它决定启动新的VM还是将任务分配给现有的VM。如果VM请求数量大于目前已有的虚拟机数量，则启动资源映射模块，根据VM请求将新启动的虚拟机合理放置到物理服务器中；如果VM请求数量小于目前已有的虚拟机数量，则启动资源调度模块，将任务请求直接调度到相应虚拟机中。

2.2 云计算资源分配研究现状

2.2.1 资源预测

云计算的一个重要特征就是可扩展性，即按需分配计算资源的能力[13]。这就允许用户以弹性方式运行应用程序，只使用他们需要的计算资源。研究表明，实例化新虚拟机的过程需要5～15 min[14]。云环境的复杂性和动态性，使得系统需要进行资源预测，这是提高当今云服务可扩展性的有效方法。

目前，国内外已经开发了很多种预测模型，这些模型大多基于时间序列分析应用于云计算的资源管理中。传统的资源预测方法包括基于蒙特卡罗的负载预测方法[15]、指数平滑算法[16]、移动均值模型[17]、自回归移动均值模型[18]和隐马尔可夫模型[19]，这些方法已经被证明可以进行短期时间序列预测。但是，由于以上模型多是通过历史数据直接建模预测，没有对负载模式的特点进行分类，这会导致后期预测的适用性受限和准确度降低。

文献[20]中提出一种多元线性回归预测模型，文中将观察数据作为线性方程来确定输入变量和输出变量之间的关系。但是该模型的线性特征容易忽略交互效应和非线性因果关系，而实际云计算资源工作模式通常具有明显的非线性特征。文献[21]使用人工神经网络和线性回归开发基于预测的资源配置策略，该模型能够映射时间序列中的线性和非线性属性，并使用滑动窗口技术进行准确预测。然而，该模式使用的人工神经网络学习率难以确定，并且易出现过度训练，引起泛化性能下降等缺点。文献[22]利用灰狼搜索优化支持向量机(Support Vector Machines，SVM)的短期资源负载预测模型，在样本区域里实现了资源请求预测。但是SVM模型借助凸二次优化来求解支持向量，而求解二次规划将涉及m阶矩阵的计算，从而耗费大量的机器内存和运算时间，不适用于大规模的云计算资源预测。另外，SVM解决多分类问题时应该与其他分类算法相结合。

综上所述，尽管国内外学者提出很多资源预测模型来提高云应用的可扩展性和可用性，但是都在一定程度上存在不足。因此，应该制定一种资源预测方法对资源请求进行预分类，克服传统预测方法的精度问题，找寻能避免局部最小值和复杂参数的机器学习预测方法，以应对大规模的云计算资源预测。

2.2.2 资源映射

虚拟化是云计算的核心技术，其处理来自云用户的业务请求，并将虚拟机资源映射到适当的物理机。随着云数据中心的日渐庞大，云资源提供者必须充分利用物理机才能更好地利用物理资源，在满足高性能的基础上尽可能减少物理机使用量是降低功耗的重要手段。众所周知，功耗的大量消耗，一方面会增加云数据中心的能量成本，另一方面过多的热耗散会增加硬件故障率。因此，减少资源映射中使用的物理机数量，显著影响云数据中心的可用性、生产力和可靠性。

通常，资源映射被看作是一个装箱问题[23]，将不同尺寸的物品包装到给定容量的箱子中，使得使用箱子的数量最小化。在该问题中，虚拟机被看作是要装箱的物品，其大小取决于资源利用率。箱子是物理机，其容量为物理机利用率阈值，尺寸由资源类型(如CPU、内存等)表示。在资源映射中资源类型通常为多维的，图4表示将三个虚拟机放置到具有两个维度(即CPU和内存)的物理机中。

图4 物理机中放置三台虚拟机的资源映射示例

目前用于解决资源映射问题的算法大致分为两类：

一类是基于经典装箱算法，通过排序理论解决资源映射问题。目前，用于装箱问题的经典算法主要有降序首次适应(First Fit Decrease，FFD)算法和降序最佳适应(Best Fit Decreasing，BFD)算法。这两种算法都是首先将虚拟机和物理机降序排列。不同的是，FFD算法将虚拟机放置到第一个能满足虚拟机资源需求的物理机中，而BFD算法是将虚拟机放置到最适合虚拟机资源需求的物理机中。Maruyama等人[24]提出了八种不同方法，根据多维尺寸对物品进行排序，将排序列表中的每个物品装在可容纳它的第一个箱子中。如果没有一个箱子可以容纳该物品，则将新的箱子引入到当前放置方案中，直到所有物品被成功装箱。最小负载(Least Load，LL)算法[25]通过将物品分配给最小负载的箱子来平衡现有负载。Ajiro等人[26]提出一种改进的降序首次适应(IFFD)算法和改进的最小负载(ILL)算法。实验证明，IFFD和ILL优于标准FFD和LL算法。但是，由于上述算法每次映射只能将一台虚拟机放置在物理机上，在规模较大时，其难以保证计算效率。

另一类是基于群体优化算法解决资源映射问题。例如在分组遗传算法[27](Generational Genetic Algorithm，GGA)中，使用基于组的编码方案，解决了经典遗传算法难以处理的分组问题。Wilcox等人[28]提出了重排序分组遗传算法(Reordered Grouping Genetic Algorithm，RGGA)，其使用基于组的编码和序列编码两种编码方案，采用GGA的适应度函数解决了多维度装箱问题。但是上述算法在规模较大时，容易陷入局部最优，难以得到全局最优解。

综上所述，现有虚拟机到物理机的资源映射算法还有诸多不足。尤其是在大规模资源映射时，目前的解决方案经常陷入局部最优，效率难以保证。因此，需要找寻一种既能避免局部最优问题，又具有更高性能优势的资源映射算法。

2.2.3 资源调度

在云计算环境中，物理机被虚拟化成可在同一处理器上运行的多个虚拟机。资源调度算法就是确定任务和虚拟资源之间的映射，以便满足一个或多个优化目标。通常，当用户提出应用请求后，云服务提供者通过管理中间件中的资源管理机制为任务分配虚拟化资源，适当的资源调度算法对降低云计算的计算成本和计算效率具有巨大影响。国内外已经提出了很多云计算环境下的资源调度方案，概括来说主要有以下两种：

一种是基于最优化理论对云计算资源调度问题建模，以实现整个系统的性能最佳。例如文献[29]中提出的分组任务调度算法，首先将任务从逻辑上分成若干类别，再根据不同资源的特点进行合理分配，该算法在满足用户需求的基础上保证了应用服务质量。文献[30]提出一种经济成本模型，通过杠杆调节、合理分配实现了资源成本最小化。文献[31]使用预算级别合理选择资源，实现了时间跨度最小化。上述算法在调度的过程中实现了一个或多个性能指标最优化，被广泛应用于小规模的资源调度。但是在多数情况下，云计算分布式系统上的资源调度是NP-hard问题，该问题无法在多项式时间内获得最优解。尤其在规模较大时，上述算法难以在有效时间内得到最优解。因此，另一种基于启发式的次优算法被提出。

基于启发式的次优算法，是指在可接受的范围内得到可行解来处理实际问题。例如文献[32]中基于模拟退火算法(Simulated Annealing Algorithm，SAA)，模拟物理学中的冷却过程通过内外循环使其达到热平衡状态，用更优解替换原有解，经过多次迭代找到较好的分配方案；文献[33]中基于遗传算法(Genetic Algorithm，GA)，通过初始化、交叉和变异算子，经过多次迭代最终找到较优解；文献[34]基于粒子群优化(Particle Swarm Optimization，PSO)算法，通过在空间中找寻适应度最优的粒子，找到最佳位置；文献[35]基于蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)，通过子种群群内通信和群间通信，最差解不断定向跳跃至最好解的位置，从而更好地进行资源调度。但是上述算法大多易陷入局部最优，且不具有约束能力，难以满足特定的服务水平协议。

3 结 语

本文对目前云计算资源分配关键技术进行了总结和分析，并提出了一种新型资源分配管理框架。虽然近年来学术界对云计算资源预测、资源映射、资源调度等方面进行了很多研究，但仍然存在一些不足和缺陷。在未来，这些问题可以从以下四个方面进行完善和改进：

(1)尽管本文提出的新型资源分配管理框架将传统的两级分配机制改成平行分配机制，并增加了资源预测模块，但是由于后期资源过量调整导致的虚拟机迁移依旧是不可避免的，还需要更好地迁移方案配合该框架的实施。另外，虽然本文对资源分配的各个阶段分别进行了研究，但各个阶段的交互还不是很好。为了解决一些特殊情况，需要把资源预测、资源映射、资源调度三个问题整合在一起进行更深入的分析，这样才能更好的进行优化管理，这也是我们下一步的研究方向之一。

(2)对于资源预测研究，我们可以先利用聚类算法对过去特定时间段内的虚拟机请求数据进行大致分类。然后，分别对每个类别的数据进行未来时间段虚拟机请求预测。预测方法可以选择极限学习机神经网络等泛化能力强的预测模型，以克服常规梯度学习方法难以选择学习率、过拟合和易陷入局部最小值等问题。

(3)对于资源映射研究，现有应用于虚拟机放置的启发式算法大多还存在易陷入局部最优的问题。我们可以通过加入莱维飞行[36]等措施，增加数据搜索的随机性。另外，CPU利用率与内存利用率之间的相关性，对于虚拟服务器整合具有重要作用[37]。数虚拟机放置算法，不考虑CPU利用率与内存利用率之间的相关性。下一步，应该对这一点进行分析研究。

(4)对于资源调度研究，目标大多是最小化总执行时间，从而降低总时间代价成本，而忽略了资源之间的通信成本和计算资源的执行成本。此外，一些启发式算法在面临大规模资源时很容易陷入局部最优。这些资源调度算法大多假设用户提交的任务之间彼此独立，没有任何相关性，忽略了任务依赖性成本。而在实际中，很多用户提交的应用请求的实现流程都较为复杂，这些复杂任务又分成若干主任务和子任务，它们彼此之间具有严格的依赖关系和业务规则，我们将任务自动控制、传递和执行的过程称为工作流[38]。云计算中的按需配置和资源可用性使其成为执行工作流应用的理想选择，但是工作流调度本身是一个较为复杂的问题，云计算环境的异质性和动态性又进一步增加了问题的研究难度。因此，需要制定一种适合于云工作流的资源调度算法，其应该同时衡量和优化完成时间、总执行成本和系统吞吐量等多个目标。