基于线性回归与最小二乘法的物理主机状态异常检测方法

徐胜超，宋 娟，潘 欢

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

0 引 言

虚拟机迁移是近年来大规模节能云数据中心构造的关键技术[1-3]。虚拟机迁移中最重要的一个步骤是物理主机异常状态检测，它通过监视云数据中心的所有主机的物理资源使用状态来判断，采用一定的算法或者策略，把那些运行异常(超负载或低负载)的物理节点选择出来[4-5]，形成侯选迁移物理主机列表。在接下来的虚拟机选择和虚拟机放置步骤中，也有各自特定的选择算法[6-7]、放置算法操作[8-10]。主机状态检测、选择、放置这3个步骤的优化算法还可以组合起来使用，但是最终评价标准是虚拟机迁移后的云数据中心的节能效果、物理资源利用实际效果和SLA违规效果等指标[11-13]。

本文重点研究物理主机状态检测阶段，这种状态检测策略可以分为主动法和被动法。主动的检测方法可以使得云数据中心的物理资源被充分利用，是一类比较好的检测方法。目前已有的物理主机状态检测方法大多采用被动式的或者静态管理策略，其考虑的维度因素也比较单一，已经不能适应云客户端的动态、自适应的访问需求。为此本文提出一种基于线性回归与最小二乘法的物理主机状态异常检测方法EPADA(Efficient Physical host status Anomalous Detection Approach)。

本文的EPADA是一种主动的、自适应的、动态的物理主机状态检测方法，它采用回归操作预测出物理主机在未来的一段时间内的资源使用率情况来确定其阈值边界，为后续迁移步骤做准备。EPADA通过CloudSim来实现和仿真,性能分析表明EPADA的各项性能指标与期望的相符合。

1 物理主机状态检测的相关工作

早期的静态阈值边界管理方法不能适应越来越复杂的云客户端的需求[14-15]，还有一些早期的资源使用率边界管理方法考虑的因素只有CPU这个维度[16]，比较好的物理主机状态检测方法应该考虑CPU、内存、网络带宽、网络接口等综合因素。

EPADA属于CloudSim项目的一种后续研究工作。CloudSim工具包中已有许多物理主机异常状态检测方法，它把异常物理主机划分为超负载over-utilized状态或者低负载under-utilized状态,并且根据物理资源使用率的阈值情况来完成状态检测[3]。

近年来也有大量的采用智能算法进行优化物理主机状态检测的文献，例如处理器温度感知[17]、二次平滑预测法[18]、稳定匹配算法[19]、K邻近回归预测法[20]等，这些文献在研究思路、测试指标等方面基本上都参考了CloudSim项目。

2 工作背景与相关术语

2.1 物理主机状态检测的工作场景

一个云客户端向云数据中心的全局代理请求虚拟机，该全局代理Global Broker将虚拟机分派到具体的可用的物理主机上执行。图1显示了EPADA工作模块。在CloudSim中每个物理主机上都运行有一个本地代理Local Broker，它监视物理主机的软硬件资源，EPADA物理主机状态检测策略的实现代码主要在本地代理模块中完成。本地代理根据物理主机的处理器的利用率情况把其划分为3类：Pnormal、Pover、Punder，即正常主机、超负载主机、低负载主机。一般CPU的利用率低于或者高于一个阈值边界都处于Pover或Punder状态，其他的为正常状态Pnormal。利用率阈值边界具体取值多少可以通过各类阈值管理策略来测试和调整。虚拟机管理器Virtual Machine Manager用来配合本地代理Local Broker具体地完成虚拟机迁移的启动与关闭，这个工作场景在文献[3]有描述。

图1 EPADA物理主机状态检测的工作场景

2.2 回归与最小二乘法技术

回归方法可以预测数据的下一阶段的值，回归方法被广泛使用在数据预测领域[21]。回归技术有2种模型，单个输入的单一回归和多个输入的多回归。EPADA算法采用了单一权值线性回归来预测物理主机的资源使用率情况。该思想如公式(1)所示：

y=β0+β1x

(1)

其中，y是受依赖的变量，x是独立的变量，β0和β1是回归系数，输出变量y的预测值表示数据集中每个数据点的变化情况。

(2)

(3)

(4)

(5)

简化上面2个等式后可以得到：

(6)

(7)

2.3 EPADA状态检测的相关术语

1)云数据中心能源消耗模型(Energy Consumption)。

假设物理主机是空闲的，它的能源消耗的百分比是k,Pfull表示物理主机在完全满负载工作时的能源消耗，CPUutil(i)是当前的物理主机i的CPU使用率,这样物理主机的能源消耗定义为公式(8)：

Ei=k×Pfull+(1-k)Pfull×CPUutil(i)

(8)

设m是云数据中心中的所有物理主机个数，整个云数据中心的能量消耗可以定义为公式(9)：

(9)

2)云数据中心SLA违规比率(SLA Violation)。

SLA违规的具体值可以通过公式(10)来计算:

SLAV=SLATAH×PDM

(10)

其中，SLATAH是活动主机的CPU具有100%的使用率所占的比例，PDM是整个系统因为虚拟机迁移后的性能降低情况。

3)SLA违规与能量消耗联合指标ESV。

CloudSim中的ESV(Energy and SLA Violations)方法可以很好地评价整个云数据中心的性能,ESV的计算公式如下：

ESV=Etotal×SLAV

(11)

其中，Etotal是云数据中心的整体能量消耗，SLAV的含义是SLA违规情况,ESV体现了能量与SLA违规的平衡。

3 EPADA物理主机状态检测算法描述

3.1 物理资源使用率预测

云数据中心中预测物理资源的未来情况和需求是十分重要的，由于目前的能量消耗模型大部分都是基于物理主机的CPU来完成计算，例如公式(8)。本文提出的EPADA模型，线性回归的函数主要针对过去1个小时CPU使用率的情况，从而迭代出当前CPU使用率的情况。首先解释EPADA物理主机状态检测算法如何评估出物理主机的理想CPU请求，接着描述EPADA算法如何检测出云数据中心的超负载物理主机和低负载物理主机，并且将其运用到后续的虚拟机选择和虚拟机放置过程中。

EPADA算法利用一个线性回归方法来设计预测函数。该函数显示了未来的和当前的物理主机CPU使用率之间的线性关系。

y=β0+β1x

其中，β0和β1是回归相关系数，它们可以通过过去的k次物理主机使用率来完成计算，y是物理主机使用率的期望值，x是物理主机的当前物理资源利用率。在EPADA中，把k设置为12，因为在云数据中心中把虚拟机迁移的周期设置为5 min，所以要预测1个小时后的资源利用率的具体值，需要完成12次迭代。EPADA物理主机状态使用率边界预测值的计算如算法Algorithm1所示。

Algorithm1EPADA Algorithm

Input:h

Output: predictUtil

1.// Approximate the prediction function based onkpast utilization

2.Initialize theβ0andβ1to a random small value;

3.Fori=1 tokdo

4.xi=UtilHistory (i);

5.yi=UtilHistory (i+1);

7.// Calculate the loss

9.Update theβ0value using Equation (6) overisamples ofk

10.Update theβ1using Equation (7) overisamples ofk

11.end for

12.// Use the regression function

13.PredictUtil=β0+β1*CurrTotalUtil(h)

14.return predictUtil;

该算法是EPADA物理主机状态检测的一个核心功能，输入值为h，输出值为predictUtil。最初的时候，相关系数被设置为一个比较小的随机值(代码第2行)，接下来执行k次循环,根据处理器的历史数据，迭代计算出资源使用率的预测值。由于线性回归所计算的是每个数据点的真实值和预测值之间的差值，所以每一次的迭代得到的资源使用率预测值更加接近于真实数据。

资源使用率预测值的估计值也是基于相关系数的参数和当前的数据值，通过第7行的代码得到过去i个数据点的残差平方和，最后更新β0和β1的值可以继续减少资源使用率的预测值和真实值的差异性。最后在第13行代码中把物理主机上的所有虚拟机的总体资源使用率赋予资源使用率预测值。

3.2 高负载主机检测过程

EPADA可以预测出所有物理主机在将来一段时间内的资源使用情况，在实体迁移过程中被用来判断物理主机是超负载或低负载。当某个主机超负载时，则将一些虚拟机迁移到其他主机上以减少SLA违规率；当某个主机低负载时，该主机切换到睡眠状态以减少能量消耗。这些对云数据中心整体性能的提高是极其有利的操作。

EPADA的超负载物理主机检测的伪代码称为算法Algorithm2。

Algorithm2Over-Loading Physical Host Detection

Input: host

Output: Boolean

1.if(UtilHistory.length <12)

2.if(CurrTotalUtil(host)>0.85*TotalUtil(host))

3.return true;

4.else

5.return false;

6.end if

7.else

8.predictUtil=EPADA(host);

9.if(predictUtil>CurrTotalUtil(host))

10.return true;

11.else

12.return false;

13.end if

14.end if

上面代码表明，在收集了过去的12个物理资源使用率之后，如果当前的资源使用率大于所有物理资源可用率的85%，那么该物理主机将设置为超负载状态，这里的85%是可以调整的。通过算法Algorithm1可以预测未来的CPU使用率的情况，在资源使用的预测值大于可用的CPU计算能力的情况下，该物理主机也设置为超负载状态。如果上面2个情况都没有，则该物理主机不是超负载状态。从这个代码可以看出，通过设置一定的时间周期，EPADA检测方法可以随时避免出现超负载物理主机的情况，最终启动虚拟机选择和放置程序。

3.3 低负载主机检测过程

EPADA的低负载物理主机检测的伪代码称为算法Algorithm3。

Algorithm3Under-Loading Physical Host Detection

Input: host

Output: Boolean

1.if(UtilHistory.length <12)

2.if(CurrTotalUtil(host)=0)

3.return true;

4.else

5.return false;

6.end if

7.else

8.predictUtil=EPADA(host);

9.if(predictUtil<0.1*TotalUtil(host));

10.return true;

11.else

12.return false;

13.end if

14.end if

从上面的代码可以看出，如果一个物理主机的CPU使用率为0则处于低负载状态；在1个小时后，通过算法Algorithm1可以预测未来CPU使用率的情况，如果通过迭代后得到的当前资源使用率小于所有物理资源可用率的10%，则该物理主机也处于低负载状态，这里的10%是可以进行调整的。从这个代码可以看出，通过设置一定的时间周期，EPADA检测方法可以随时避免出现低负载物理主机的情况，运行在低负载状态的物理主机其上运行的虚拟机将被选择及重新放置，最终将该物理主机切换到睡眠模式或者关闭物理电源，间接地节省了云数据中心的总体能量消耗。

3.4 虚拟机迁移过程

EPADA检测方法在后续的虚拟机迁移过程中也有涉及，称为算法Algorithm4。

Algorithm4VMs Live Migration

1.For each host in hostList do

2.while(OverloadeingDetection (host)=true OR

UnderloadeingDetection (host)=true) then

3.VM=VMSelection(host);

4.otherHosts=hostList-host;

5.h=VMsAllocation(otherHosts, VM);

6.migrate(VM,h);

7.end while

8.end for

从上面的代码可以看出，只要云数据中心的物理主机处于异常状态(超负载或低负载)，都将进入侯选迁移物理主机列表，其上运行的虚拟机将通过后续的虚拟机选择策略而形成侯选迁移虚拟机列表，而云数据中心中的其他物理主机将在虚拟机放置阶段作为容纳新的虚拟机的节点存在。

4 仿真实验与性能分析

4.1 仿真环境的设置

1)创建物理主机。

在实验中，云数据中心的能量消耗模型采用的是常见的CoMon Project,也是目前典型的BenchMark模型[23]。测试指标都参考了第2章中提到的SLA违规率、能量消耗情况。

在CloudSim项目中设置的云数据中心主要由4类物理服务器组成，物理主机总数为800台，物理主机配置如表1所示。

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

2)创建虚拟机。

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

表2 EPADA物理主机状态检测方法的配置参数表

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

表3 EPADA物理主机状态检测方法测试时间

4.2 性能比较对象

表4 EPADA物理主机状态异常检测性能比较对象

CloudSim中原始的虚拟机迁移模型称之为LRR-MMT-BFD策略，将它作为首要比较对象[3]。还与其他主机检测方法进行了比较，例如AEEVC[16]检测方法、ATEA检测方法[5]、稳定匹配虚拟机迁移[19]、关联性虚拟机迁移[24]、蚁群优化的虚拟机迁移[13]等，分析这些物理主机异常状态检测对云数据中心的性能改变情况，如表4所示。

4.3 仿真结果与性能分析

1)云数据中心总体能量消耗。

从图2可以看出，有了物理主机异常检测算法EPADA后，EPADA-MMT-BFD迁移模型比CloudSim中的LRR-MMT-BFD迁移策略在总体能量消耗上要节约25%到30%，比Stable-Matching策略、Correlation-Based策略和ACS-VMM策略的能量消耗也要低，因为EPADA能够每次回归检测到状态异常的超负载物理主机和低负载物理主机，关闭这些物理主机可以达到节能的效果。

图2 各类虚拟机迁移策略的总能量消耗比较

2)虚拟机迁移次数。

图3显示了EPADA-MMT-BFD的虚拟机迁移次数都低于其他策略。Stable-Matching策略、Correlation-Based策略和ACS-VMM策略的优化主要在虚拟机放置阶段，很难降低虚拟机迁移次数，要想减少虚拟机迁移次数，必须在虚拟机选择阶段、物理主机状态检测阶段完成优化。

图3 各类虚拟机迁移策略的虚拟机迁移次数

3)SLA违规率分析。

从图4可以看出，EPADA-MMT-BFD迁移策略的SLA违规率比LRR-MMT-BFD迁移策略要低。这是因为EPADA-MMT-BFD周期性地完成超负载物理主机检测，它可以避免物理主机出现100%的CPU利用率的机会。Stable-Matching策略、Correlation-Based策略和ACS-VMM策略在虚拟机放置阶段都采用另外的优化算法，它们的SLA违规率在某些时候还优于EPADA-MMT-BFD策略。

图4 各类虚拟机迁移策略的SLA违规率比较

4)能量与SLA违规的联合指标ESV。

从图5可以看到，EPADA-MMT-BFD迁移策略的ESV也低于LRR-MMT-BFD迁移策略，但是它与其他的迁移模型比较起来，也不是最好的。所以虚拟机迁移策略应该属于一种多目标优化问题，关键看各类算法的目标函数设置情况。ACS-VMM的综合性能指标最优，但是它是以牺牲能量消耗与虚拟机迁移次数为代价的。

图5 各类虚拟机迁移的能量消耗联合指标ESV

5 结束语

低能量消耗与高服务质量是云数据中心的主要性能目标，目前国内外的研究主要采用虚拟机迁移技术来达到这2个目标。物理主机异常状态检测是虚拟机迁移的重要步骤，本文提出了云数据中心中一种新的物理主机状态异常检测算法EPADA。EPADA具有自适应性、动态性的特点，它利用统计学中回归函数及最小二乘法，经过多次循环迭代预测出云数据中心的物理资源使用率的情况。实验表明，EPADA-MMT-BFD比近3年来的虚拟机迁移策略性能优秀，EPADA物理主机状态检测算法可以为其他节能绿色云数据中心的构造提供参考。