云数据中心基于皮尔逊相关系数的虚拟机选择策略*

徐胜超 ，宋 娟 ，潘 欢

(1.广州华商学院 数据科学学院，广东 广州 511300；2.宁夏大学 宁夏沙漠信息智能感知重点实验室，宁夏 银川 750021)

0 引言

如何提高云数据中心的物理主机的利用效率并进行负载均衡操作至关重要[1]，目前大部分云服务提供商都采用虚拟机迁移技术[2]。虚拟机选择是整个虚拟机迁移过程的一个重要步骤，它的功能是从云数据中心的异常物理主机中运用一定的算法选择出需要候选迁移的虚拟机，从而为后续的虚拟机放置过程提供输入参数。

具有高关联度的虚拟机之间更容易触发超负载事件，因此如何防止那些高关联性的虚拟机在虚拟机放置过程中被分配到同一个物理节点上就是一个关键问题[3-4]。

文献[5]提出了虚拟机选择和虚拟机放置过程结合起来,可以充分提高物理资源的使用效率,具有一定的优势；文献[6-7]提出了贪心算法优化的虚拟机选择策略，在选择过程中通过动态调整物理资源利用阈值边界，可以很好地降低能量消耗；文献[8-9]提出了温度感知的虚拟机选择策略，它将物理主机的处理器的温度作为虚拟机选择的标准，是一种考虑硬件的虚拟机选择策略。文献[10]提出了数据依赖的虚拟机选择策略，它在选择候选迁移虚拟机的过程中考虑虚拟机之间的数据依赖关系，它的思路与本文的考虑十分相似。实验结果表明该策略也可以提高云数据中心的各类指标性能，但是文献[5]-[10]都没有考虑虚拟机的关联性。

虚拟机之间的相关性如果按照统计学的方式进行建模，考虑物理资源的历史信息，在这种因素下考虑虚拟机选择问题会更加接近真实的情况。本文提出一种考虑虚拟机关联性的虚拟机选择策略，称为PC-VMS(Pearson Correlation coefficient Virtual Machine Selection)，即把皮尔逊相关系数的计算方法应用于虚拟机CPU历史利用率数据，建立了衡量每对虚拟机CPU 利用率之间的相关性的数学模型；PC-VMS 会获取每对虚拟机最近n 次的CPU 利用率，根据输入的两组数据来计算皮尔逊相关系数，最后在一组相关性最高的虚拟机中选择一个CPU 利用率最高的对象作为候选迁移虚拟机，从而为后续的虚拟机放置步骤作为输入参数。

PC-VMS 虚拟机选择策略的仿真和测试过程是放到整个虚拟机迁移过程中完成的。经过PC-VMS 虚拟机选择策略优化后的虚拟机迁移实验结果表明，PC-VMS 可以稳定云计算的服务质量水平,降低能量消耗。

1 PC-VMS 虚拟机选择策略概况

1.1 PC-VMS 的工作背景

PC-VMS 依托CloudSim 模拟器工具来工作与仿真云数据中心的各类性能指标，经过PC-VMS 优化后的虚拟机迁移过程具体包括以下4 个步骤[11]：

(1)周期性地完成云数据中心的所有物理主机状态检测(over-utilized 或under-utilized)，形成异常物理主机列表；

(2)针对异常的物理主机，采用PC-VMS 策略完成虚拟机的选择,形成侯选迁移虚拟机列表；

(3)针对候选迁移的所有虚拟机，完成虚拟机放置过程；

(4)反复执行步骤(1)～(3)，通过设置一个是周期(通常是一周),达到该时间段虚拟机迁移过程就结束。

PC-VMS 与CloudSim 项目中不同的是，在步骤(2)中，着重考虑虚拟机的处理器利用率的关联度，通过建立虚拟机之间的关联度数学模型，设计了虚拟机之间的皮尔逊相关系数，其他的步骤(1)和步骤(3)继续借鉴了CloudSim 项目中的已有的优化策略。

1.2 PC-VMS 的相关术语

1.2.1 皮尔逊相关系数

假设一个物理主机上面有n 个运行的虚拟机VM，假设这些虚拟机组成了一个向量，VM={VM1，VM2，…，VMn}，为了计算物理主机上虚拟机之间的相关性，本文算法使用了皮尔逊相关系数，其计算公式如下：

式中，r 表示皮尔逊相关系数，i 和n 表示虚拟机的编号，xi和yi分别表示的是虚拟机VMi最近的k 次CPU 利用率，各自表示虚拟机最近的k 次CPU 利用率的平均值。式(2)为虚拟机CPU 历史利用率矩阵U：

式中，矩阵的行代表超负载主机上的某个虚拟机VMi的利用率，矩阵的列表示模拟器运行过程中的某个时间点tj，矩阵中的数据uij表示虚拟机VMi在时间点tj下的CPU 利用率。接下来，利用CPU 历史利用率矩阵，根据皮尔逊相关系数的计算公式计算虚拟机之间的相关性，同样把结果保存在一个矩阵(C)中，如式(3)所示：

式中，矩阵的行和列都代表着虚拟机VMi；cij代表虚拟机CPU 利用率之间的皮尔逊相关系数，cij∈(-1，1)；矩阵中的数字1 是无效的值。

1.2.2 云数据中心的总体能量消耗模型

云数据中心能量消耗主要由物理主机的所有部件的能量消耗组成。一个物理主机所消耗的能量主要由处理器、内存、磁盘、网络带宽组成。根据这个思路，本文设计了单个物理主机的能量消耗。第j 个物理主机在[t0，t1]时间段的总体能量消耗Ej可以按照式(4)来计算：

那么整个云数据中心的能量消耗Etotal为式(5)：

其中，m 是物理主机个数。

1.2.3 SLA 违规在线时间(SLA violation Time per Active Host，SLATAH)

SLA 在线时间(SLA time per host)体现了物理主机具有高服务质量的在线时间情况。

其中，m 为云数据中心的物理主机数量，j 表示物理主机的编号，Tsj是物理主机CPU 利用率达到100%的时间，Taj是物理主机处于在线活跃状态的时间。

1.2.4 虚拟机迁移后的性能降低(Performance Degradation due to Migrations，PDM)

其中，n 表示云数据中心的虚拟机数量，i 表示虚拟机的编号，Ddi是由于虚拟机VMi迁移导致的性能下降的估计值，Dri是请求虚拟机VMi的整个时间段内总的CPU MIPS 计算能力。

1.2.5 SLA 违规率(SLA Violation)

SLA 的违规率的计算通过式(8)计算：

SLA Violation 违规率是体现云服务提供商的高服务质量的重要指标。

2 PC-VMS 虚拟机选择策略描述

2.1 PC-VMS 的策略描述

本小节详细描述PC-VMS 虚拟机选择策略涉及的算法及其工作流程。该策略使用了两个算法，在算法1中，计算皮尔逊相关系数矩阵，接着调用算法2 来寻找相关性大小位于前k 位分别所对应的虚拟机，最后从算法2 返回的虚拟机列表中选择一个CPU 利用率最大的虚拟机迁移出去。

(1)算法1：基于皮尔逊相关系数的虚拟机选择策略

输入：物理主机负载检测阶段的异常物理主机MigratedHostList

输出：要迁出的虚拟机列表VmsToMigratedList

①获取物理主机上的虚拟机列表，保存到变量migratableVms 列表中；

②计算当模拟器当前的时刻time，将time 除以300得到timeStep，如果timeStep<5，则启用备用的虚拟机选择策略，结束该算法，否则，进入步骤③；

③根据获取的migratableVms 计算CPU 历史利用率矩阵cpuUsage；

④根据矩阵cpuUsage 计算CPU 利用率之间的皮尔逊相关系数，结果保存到矩阵pearsonMatrix 中；

⑤调用算法2 寻找虚拟机列表，返回结果保存到列表vmList 中；

⑥在vmList 寻找一个CPU 利用率最大的虚拟机，保存该虚拟机在vmList 中的索引值index；

⑦返回vmList 中索引为index 的虚拟机，存入VmsTo-MigratedList。

(2)算法2：寻找皮尔逊相关系数大小最近的k 个所对应的虚拟机

输入：pearsonMatrix，migratableVms，k

输出：与最近k 个相关系数大小有关的虚拟机列表vmList

①遍历矩阵pearsonMatrix 的行和列，取出里面的元素，存放到一个名为maxCoefficients 的HashSet 集合中；

②对maxCoefficients 中的元素进行降序排列，结果赋给一个List 集合，取名为coefficientsList；

③取出集合coefficientsList 中前k 个元素，存放到List集合top_k 中；

④遍历pearsonMatrix 矩阵的每一行，找出这一行最大的那个元素，然后判断top_k 列表是否包含这个元素，如果包含，则从migratableVms 列表中根据当前遍历的行号找到一个虚拟机，添加这个虚拟机到列表vmList 中；

⑤返回vmList。算法1 和算法2 两个算法经过少量的修改即可转化成为代码。

2.2 PC-VMS 的策略实现模块

PC-VMS 依托了CloudSim 各个运行模块，在CloudSim云模拟器中每个物理主机上都运行有一个本地代理Local Broker，PC-VMS 虚拟机选择优化策略的实现主要在此模块中完成，算法1 和算法2 的实现基于Java 实现。上述算法1 和算法2 的运行流程经过少量修改即可转化为PC-VMS 的代码。

3 PC-VMS 仿真实验与性能分析

3.1 仿真环境的建立

(1)创建物理主机

云数据中心的能量消耗模型是最常见的CoMon project，它是由planetlab 实验室开发的一个项目，也是目前云数据中心的模拟器的典型BenchMark 模型[12]。测试指标都参考了1.2 节中提到的虚拟机迁移次数、SLA 违规率、能量消耗情况。物理主机配置如表1 所示。

表1 云数据中心物理主机硬件配置

(2)创建虚拟机

创建的虚拟机参考的是普通网络客户端的应用程序访问类型，不同的是每个虚拟机都是CPU 能力不同，并且内存也有所改变。总共创建了4 种虚拟机类型，配置参数如表2 所示。

表2 PC-VMS 虚拟机配置参数表

对于虚拟机的初始化放置策略，使用的是首次适应的方法，即首次为虚拟机寻找宿主机的时候，如果找到了一个拥有足够资源创建这个虚拟机的物理主机，就立即分配给它，而不再考虑后面的主机，即使有更合适的选择。这样做的好处就是在为虚拟机首次寻找目标主机的过程中节约了时间，虚拟机请求的个数如表3 所示。

表3 PC-VMS 虚拟机选择优化策略运行时间

在实验中的物理主机负载检测中，采用的是鲁棒局部归约主机负载检测，即选择最近j 个物理主机进行规约预测出资源利用率边界然后选择，j 取值为10。

PC-VMS 虚拟机选择策略将与CloudSim4.0 内置的策略进行对比，这些内置的策略包括随机选择策略(Random Selection，RS)、最小利用率策略(Minimum Utilization，MU)、最大关联选择策略(Maximum Correlation，MC)和最小时间选择策略(Minimum Migration Time，MMT)。在虚拟机放置策略方面，实验中采用的是递减装箱方法(Best-Fit-Decreasing，BFD)。

3.2 固定虚拟机数量的实验分析

整个云客户端被分配了1 000 个虚拟机，然后让这些虚拟机执行2 000 个云任务，每个任务的长度是216 000 000 MI，给CloudSim 设定的模拟时间是24 h(86 400 s)。最后，每次保持上述的设置不变，在CloudSim 模拟器中测试了包括本文算法在内的5 种虚拟机选择策略。表4 展示了它们的测试结果。

从表4 的测试的结果来看，PC-VMS 虚拟机选择策略在降低能量消耗方面的效果要稍微好于其他策略，MU 策略的能量消耗是最大的，另外3 种策略的能耗基本持平。表4 的第3、4 列显示了在虚拟机迁移次数以及SLA 违规次数方面的情况，PC-VMS 虚拟机选择策略则明显少于其他4 种策略，所以PC 虚拟机选择策略带来的性能下降和SLA 违规率也是最低的。PC-VMS 虚拟机选择策略相比于其他策略拥有低能量消耗的优势，并且大幅度地降低了SLA 违规率，这有利于企业实现绿色节能的云计算。

表4 云数据中心不同虚拟机选择策略测试结果

从表4 也可以看出，PC-VMS 虚拟机选择策略明显地降低了虚拟机迁移次数，从而也降低了物理主机遭受SLA 违例的次数。由于MU 虚拟机选择策略每次选择CPU 利用率最低的那个虚拟机进行迁移，可能需要反复执行算法选择多个虚拟机迁出，才能使过度负载的物理主机重新回到正常负载水平，因此该策略的能耗、SLA违规率、虚拟机迁移次数和SLA 违规次数都较高。PC-VMS虚拟机选择策略还有一个重要的优势是它在整个迁移过程中所导致的性能下降比率最低，这得益于该策略的虚拟机迁移次数较少，因为每次虚拟在线迁移的过程中难免会损失部分性能。

3.3 不同虚拟机数量的实验分析

利用PC-VMS 虚拟机选择算法优化之后，当云平台的虚拟机的请求个数从100～600 个变化时，各个虚拟机选择策略的总体能量消耗比较如表5 所显示。从表5 可以看出，PC-VMS 比CloudSim4.0 中已有的策略在总体能量消耗上要节约20%～25%，能量消耗基本呈线性变化。分析原因是虽然云数据中心的整体物理主机个数为800 个，但是随着虚拟机个数的变化，在虚拟机比较少的时候，大部分物理主机可以切换到关闭状态，能量消耗自然降低了。

表5 各类策略总体能量消耗性能比较 (kWh)

4 结论

云数据中心利用虚拟机迁移技术来降低总的能量消耗，同时必须尽量满足SLA 违规。作为虚拟机迁移过程的一部分，虚拟机选择算法要从状态异常的物理主机中精准地选择出候选迁移的虚拟机。本文提出了一种根据虚拟机CPU 利用率之间的相关性来选择虚拟机的PC-VMS 策略，PC-VMS 虚拟机选择策略不仅仅限制于在CloudSim 模拟器中，还可以与其他的开源云平台结合起来使用，或与其他更加先进的虚拟机放置算法结合起来使用，可以更好地提高云数据中心的各个性能指标[13-15]。