基于时间序列的服务器负载预测.doc

基于时间序列的服务器负载预测

简介：1
引言随着计算机网络的迅速发展，各种服务器越来越难以满足用户的需求。负载均衡集群的出现，在一定程度上解决了这个问题。负载均衡算法作为影响负载均衡的三大要素之一，它的好坏在很大程度上决定了负载均
...
关键字：时间序列 服务器 负载预测
1 引言
随着计算机网络的迅速发展，各种服务器越来越难以满足用户的需求。负载均衡集群的出现，在一定程度上解决了这个问题。负载均衡算法作为影响负载均衡的三大要素之一，它的好坏在很大程度上决定了负载均衡集群的性能。但是目前负载均衡集群大多采用的是静态的负载均衡算法，由于这种算法没有考虑到服务器的当前负载情况，很难做到真正的负载均衡；当然也有一些负载均衡集群采用的是动态负载均衡算法，这种算法一方面使各个服务器之间的负载更加均衡，但另一方面又造成了服务器的资源的巨大浪费，因为各个服务器要在很小的时间间隔内（甚至是实时的）就要向前端调度器发送自身的负载信息。基于以上原因，本文提出了基于时间序列的服务器的负载预测方法。目前，国内外利用时间序列等其他方法进行预测的研究主要集中在网络流量的预测上，对服务器负载预测研究的相对较少。这两者的不同主要在于：网络流量预测关心的是TCP/IP流量大小和延迟，而服务器负载预测关心的是服务器的平均负载量，这是一个服务器消耗资源的综合体，包括CPU利用率、网络利用率、内存使用情况以及硬盘可使用空间。文献[1]提出了基于ARMA模型的网络流量预测的方法，但是它并没有为实际序列寻找拟合最好的时间序列，而是采用了ARMA(2,
1)序列。这样虽然减少了计算量，但同时也降低了预测的准确性。本文根据服务器负载的特性以及负载动态变化的规律，提出了基于时间序列的负载预测方法。该方法是以服务器的历史负载数据为基础，首先对负载数据进行预处理剔除误差较大的数据，再对进行预处理的序列进行平稳化处理、剔除趋势项和周期项，得到随机项序列；接下来对随机项序列进行模型识别，确定是时间序列的三种模型中的哪一个模型；接着对选定的模型进行定阶，确定其中的p、q的大小；再对模型中的参数进行估计、同时对模型进行考核；然后利用得到的模型对负载进行预测，最后对负载预测的结果进行了分析，结果显示预测效果较好。因此，此方法不仅为实现高效的负载均衡打下了基础，而且提高了服务器的资源利用率。

2 负载特性
为了能够进行准确的负载预测，就要知道如何准确的衡量负载，即要了解负载的特性。美国卡内基梅隆大学的Peter A.
Dinda在1997年和1998年分两次对38台不同的机器，包括集群服务器、计算服务器和桌面主机等进行长期的跟踪抽样获得了大量的负载图样。通过对这些图样进行统计分析，Dinda总结出了负载的特性，这些研究成果收录于文献[2]。从这篇文献中，可以得出负载的特性主要有以下七个方面：
(1) 负载的变化是一种随机过程。
(2) 负载一般处于较低的水平，但具有很强的波动性。
(3)
平均负载量高的其负载的绝对波动量也大，即其最大负载量与最小负载量间的差值大；但从相对波动量来说，平均负载量高的要低于平均负载量低的。这种最大负载量与平均负载量的关联性表明对重负载机器进行负载预测有更高的价值。
(4)
负载值的分布是比较复杂的，尤其是平均负载量高的，其负载值呈现复合多样性。这种分布复杂性表明对负载进行分析、预测应该是图样驱动，而不能简单的依据分布曲线。
(5)
负载随时间变化有很强的关联性，即过去的负载值对将来的负载值有很大的影响。这表明依据过去的负载值对将来的负载值有很大的影响，同样依据过去的负载值进行负载预测是可行的，而且利用时间序列模型进行负载预测是合适的。
(6) 负载的变化又有高度的自相似性，即在所有的时间尺度下负载的变化既复杂，又具有长期的依赖性，所以负载的模型化和预测是困难的。
(7) 负载的变化又具有突变性。负载值在某一个时刻会有比较大的波动，然后又趋于平稳。负载的这种突变性表明负载预测应具有修正和重适应机制。

3 时间序列
由上一节可知，服务器负载的变化是一种时间序列，而且具有高度的自相似性，因此利用时间序列对服务器的负载进行预测是可行的。
时间序列是按时间次序排列的随机变量序列。任何时间序列经过合理的函数变换后都可以被认为是由趋势项部分、周期项部分和随机噪声项部分等三部分叠加而成的。它主要包括自回归模型AR(p)、滑动平均模型MA(q)、自回归滑动平均模型ARMA(p,
q)三种简单的模型，其中，AR(p)和MA(q)都是ARMA(p, q)的特殊情况。
定义：设 是白噪声 ，实系数多项式A(z)和B(z)没有公共根，满足 和
称差分方程 是一个自回归滑动平均模型，简称ARMA(p,
q)模型。当q=0时，它为AR(p)模型；当p=0时，它为MA(q)模型。与AR、MA模型相比，ARMA模型具有更小的预测误差方差；与AR模型，MA模型相比具有相对稳定的特点；另外ARMA、AR、MA模型都可以进行短期预测，并且预测步数越少，误差越小，这一点将会在下面涉及到。

4 实验
(1) 数据采集
下面以IP网关服务器为例对其负载进行预测， IP网关服务器运行在Red Hat Linux AS
4平台上，主要实现控制校园网（或园区网）用户访问的站点、记录用户访问的站点信息、采集用户流量等功能。在IP网关服务器中连续采集5周的负载数据，每周采集7个工作日，采样的时间间隔为5分钟，通过/proc文件系统收集IP网关服务器的负载值（用百分数表示）作为观测值。此处的负载是一个百分数，它表示系统的CPU、网络带宽、内存、硬盘等的综合使用情况。尽管校园网（或园区网）中单个用户的网络行为是不确定的，但是所有的校园网（或园区网）用户的网络行为促使IP网关的负载值变化呈现一定的周期性和时间关联性。
(2) 数据的预处理

在采集的负载数据中，肯定会存在一些含有粗大误差的数据，这些数据会扭曲最终结果。因此，要把这些含有粗大误差的数据剔除。在5周的相同工作日的相同时刻有5个不同的数据
，其中i=1,2,3,4,5。对这5个数据计算平均值 ，然后求出它们的标准差 。即
根据格拉布斯准则，如果 满足 ，则
为坏值，应该剔除不用，其中k为格拉布斯准则系数，与置信区间95%相对应的k2.03。这样就得到正常的IP网关负载值变化曲线，如图1所示。
(3) 平稳化数据序列

图2 样本自相关函数图

图1 预处理后的负载变化图

首先要判定经过预处理后的观测值序列是否平稳，这里利用自相关函数法进行判定。当然，通过观测图1也可以初步判定观测值序列具有明显的周期性，不是一个稳定的时间序列。图2是观测值序列的自相关函数。可以看出，该序列的自相关函数呈现出周期性缓慢衰减的现象，由此可以判定该序列存在某种趋势或周期所以不是稳定的。

平稳化的目的就是去除时间序列中的趋势项和周期项，为建立时间序列模型做准备。本文将采用方差分析的方法进行平稳化处理。具体来讲，用
表示一周当中第i天第j个5分钟的观测值，其中 i=1,2,3 …7；j=1, 2, … 288。首先对 取对数，这样可以有效地减少标准差，然后把
划分为趋势项 、周期项 （季节项）、随机噪声项三部分，即 ，其中， 表示在第j个时刻的平均值， 表示第i天的平均值，
是观测值的残余。这样，就把一周当中不同的工作日以及每天的不同时刻这两个影响因素都从原观测值
中剔除掉了。如果服务器的负载在周与周之间的变化比较大的话，也可以把不同周的影响剔除掉。
经过平稳化处理以后，就得到了如图3所示的一个平稳的时间序列 。从图中可以看出，序列
没有明显的趋势性和周期性，是一个平稳的时间序列。

图3 平稳化的时间序列

(4) 模型识别
对经过平稳化处理得到的时间序列
进行模型识别，即确定该时间序列拟合AR、MA、ARMA中的哪一个模型最好。本文采用Box-Jenkins的模型识别方法即根据自相关函数、偏自相关函数的截尾性和拖尾性判定时间序列
所拟合的模型类型。时间序列 的自相关函数、偏自相关函数分别见图4和图5。

图4自相关函数

图5 偏自相关函数

由图4和图5可以看出，时间序列 的自相关函数和偏自相关函数都不截尾，而且都被收敛到零，因此可以判定 很有可能是ARMA序列。
(5) 模型定阶
时间序列 被识别为ARMA(p, q)序列，下面就要确定ARMA(p,
q)中的p、q的值，也就是模型定阶。本文采用AIC定阶方法，首先设P为p的上界，Q为q的上界，对每一对(k, j)，其中， ， ，计算AIC函数
，其中，N为样本总数，

是残差方差，P、Q为30（因为较大的p、q会导致较多的待估参数，其结果会使建立的模型关于数据过于敏感，降低模型的稳健性）。求得AIC(k,
j)的最小值，其中的k、j就是p、q的值。根据Pandit-Wu方法，对于ARMA(p, q)的定阶可以按ARMA(2n,
2n-1)的方式进行，其中 。图6是时间序列 的AIC定阶图。

图6 AIC定阶图

从图6可以看出，在n=4时，AIC(2n, 2n-1)最小，因此p=8，q=7，即时间序列 为ARMA(8, 7)序列。
(6) 参数估计
时间序列 确定为ARMA(8, 7)序列后，接着就要确定在第3节提到的 、 的值，即 ；然后用矩估计方法，求得参数：

，接下来就要对参数进行平稳性判定，也就是求解ARMA(p, q)模型定义中的A(z)=0 和 B(z)=0
的根，并判断这些根是否在单位圆外，如果在单位圆外，则ARMA(8,
7)是平稳的时间序列；否则就是不稳定的。经过计算可以得到A(z)=0和B(z)=0的根都在单位圆外，因此ARMA(8, 7)是平稳的时间序列。
(7) 预测

ARMA(8,7)模型的预测就是利用ARMA的时间相关性对未来某一时间点的负载值进行预测，那么t+1步预测值就等于ARMA(8,7)模型中以
为参数的前8步负载值之和加上其以 为参数的7步预测的所有预测误差之和。下面对服务器的负载值进行平稳线性最小方差预测。这里采用模型递推法。
若线性最小均方误差为 ，l为向后预测步数，可得l步预测的最小均方误差是 ，其中 是ARMA(8, 7)的格林函数。可见，
与预测时间无关，只与预测的步数有关，预测的步数越多，即预测的时间越远，方差越大，预测的结果与实际值的差别越大，越不可预测。也正是由于这个原因，在接下来的预测中，采用的就是1步预测的模型递推法，来降低预测误差。
根据ARMA(8,7)模型 ，可得
，
同理可得： ，
……，
令 ，所以一步预测值 。从以上几个表达式可以看出，1步预测的模型递推法只需要预测之前的15个观测值。这样，把得到的下一个时间点的预测值 （即随机项
）、下一个时间点的趋势项 和当天的周期项
加在一起，然后把这个值作为以e为底的幂次，最后求得的值就是这一个下一个时间点的服务器负载的预测值。图7就是利用ARMA(8,7)模型的1步预测的模型递推法产生的一周的预测值，图7是50个预测值与实际值的比较图，其中实线是实际值，虚线为1步预测值。

图7 预测值与实际值比较图

(8) 结果分析
利用ARMA(8,7)模型对一个周的负载进行了预测。为了衡量预测的效果，这里引入了绝对误差、相对误差、最大绝对误差、最小绝对误差、平均相对误差等几个概念。
；
；
；
；
对负载的预测值与实际值的计算可以得出，平均相对误差为7.25%，最大绝对误差为8.73634，最小绝对误差为0.00069。这一结果在一定程度上说明利用ARMA(8,7)模型进行服务器的负载预测是可行的，而且具有较好的预测效果。

5 结论与下一步的工作
本文在分析服务器负载特性的基础上，结合应用时间序列提出了时间序列的服务器预测方法，这种预测方法可以较好的预测服务器的负载。如果把这一方法用在负载均衡集群的负载均衡算法中将会发挥出它作为相对高效的动态负载均衡能力和较少利用服务器的资源的特点。下一步一方面会利用最小二乘法对ARMA模型的参数进行估计，提高参数的估计精度；另一方面会将基于ARMA模型的负载预测方法作为一种动态负载均衡算法增加到Linux
Virtual Server中去，使这种负载预测法的优点得到体现。

参考文献
[1] 邹柏贤、刘强. 基于ARMA模型的网络流量预测. 计算机研究与发展, 2002, 39(12): 1645-1652
[2] Peter A. Dinda. The statistical properties of host load. Scientific
Programming, Also available as CMU Technical Report CMU-CS-98-175, 1999
[3] 王振龙. 时间序列分析. 北京: 中国统计出版社, 1999
[4] 何书元. 应用时间序列分析. 北京: 北京大学出版社, 2003
[5] 吕林涛、王鹏、李军怀、吕晖、张景. 基于时间序列的趋势性分析及其预测算法研究. 计算机工程与应用, 2004, 40(19):
172-174
[6] 李庆华、郭志鑫. 一种面向工作站网络的系统负载预测方法. 华中科技大学学报（自然科学版）, 2002, 30(6): 49-51
[7] 陈志刚、许伟、曾志文. 一种基于预测的动态负载均衡模型及算法研究. 计算机工程, 2004, 30(23):87-89