基于应用负载的自适应资源供应方法

摘要

本发明属于云计算资源管理领域，涉及一种应用负载预测技术，具体涉及一种云计算中基于应用负载的自适应资源供应方法。该发明中根据应用负载的历史数据，分析应用模式并动态的选择相应预测模型，对应用将来一段时间内的负载进行预测。本发明可以根据预测的准确程度及时的修正所运用的预测模型及相关参数以获得更高的准确度，为后面的资源分配提供决策支持。

权利要求

1.基于应用负载的自适应资源供应方法，其特征在于，该方法根据应用负载的历史数据，分析应用模式并动态的选择相应预测模型，对应用将来一段时间内的负载进行预测，该方法中包括预测模块和调整模块；

所述预测模块包含三个子模块，分别为：选择器，周期性预测模型和多项式拟合预测模型，其中，①选择器根据应用负载的历史数据分析负载的模式，并动态选择相应的预测模型，同时，选择器实时的观察预测的准确度，当预测数据出现大的偏差时，选择器立刻对应用负载序列进行重新分析并选择合适的预测模型；②周期性预测模型对周期性序列进行预测；③多项式拟合预测模型预测瞬时尖峰序列；

所述调整模块在预测后对预测值进行修正处理，利用预测误差序列计算预测负载的修正值；

所述的选择器中，给定一个序列，利用快速傅里叶转换判断该序列中是否存在周期性成分，如果是周期性序列并且确定其周期，则采用周期性预测模型进行预测，检测出序列中存在多个周期成分时，采用如下公式选择最合适周期：

其中，Err(Ti)是周期为Ti时的总误差， 是周期为Ti时的-周期性部分，选择误差值最小的周期为最合适周期；

所述的多项式拟合预测模型中，采用下述公式对尖峰序列进行均值处理：

其中 为 的下取整，L的值为奇数。

2.如权利要求1所述的基于应用负载的自适应资源供应方法，其特征在于，该方法中输入应用负载的历史数据序列，在云环境中，以虚拟机的负载情况表示应用负载，由监控系统对系统中所有虚拟机负载情况进行监控与记录以及对监控数据进行预处理。

3.如权利要求2所述的基于应用负载的自适应资源供应方法，其特征在于，所述的应用负载选自访问量的负载参数，通过下述方法获得：每隔10分钟采取一个样本点，然后组成负载序列{X(t)}，即为t时刻负载的值，或根据不同负载的样本序列应用的特点选择不同的采样周期。

4.如权利要求1所述的基于应用负载的自适应资源供应方法，其特征在于，所述的调整模块中，采用多项式拟合方法进行误差值估计。

5.如权利要求1所述的基于应用负载的自适应资源供应方法，其特征在于，所述的应用模式为混合模式时，采用动态的调整预测模型适应负载模式的变化。

说明书

基于应用负载的自适应资源供应方法

技术领域

[0001] 本发明属于云计算资源管理领域，涉及一种应用负载预测技术，具体涉及一种云计算中基于应用负载的自适应资源供应方法。本发明根据应用负载的历史数据，分析负载的模式并动态地选择相应预测模型，对应用将来一段时间内的负载情况进行预测。

背景技术

[0002] 云计算作为一种新型的服务模式，得到了公众的广泛关注。近年来，不断发展进步的虚拟化软件使得云计算能够灵活地提供可扩展性，弹性和低成本的基础设施。凭借这些优势，云计算逐渐成为现代IT解决方案中的普遍选择。基础设施即服务的提供商使用虚拟化技术来封装应用并为没有合作关系的用户提供隔离。然而静态的为虚拟机划分物理资源，可能会导致许多问题。通常，应用的负载是不断变化，如果根据应用的峰值负载为其分配资源，这样会导致大量资源的浪费。相反地，如果为应用分配的资源少了，应用可能在某些时刻会因为资源的不足而违反应用服务目标。为了实现资源的有效利用并保证应用的性能，云环境需要一个高效的资源供应系统。

[0003] 虽然现有技术公开了一些针对云计算应用的资源供应方法和技术，但是解决从负载模式分析到为不同模式的负载提供合适的预测模型这一关键重要需求上，这些方法仍存在一些问题，主要有：

[0004] 1.对负载模式认识不够清晰。负载的基本模式有周期性模式和非周期模式，也就是应用负载呈现出周期性特征或非周期性特征。事实上，有些应用的负载表现出多种模式相混合的特征。比如，在一段时间内负载呈现出周期性，而后却表现出非周期特点，一段时间后又出现周期性特征的负载；或者负载的周期会发生改变的周期性负载。所以对于应用，实践中需要实时地检测应用负载的模式，然后选择相应的预测模型进行预测。然而目前的资源供应方法中，有些并没有考虑负载的模式就直接建立预测模型，有些方法考虑了应用的模式来建模预测。对于这些资源供应方法，如果负载模式发生改变，而预测模型不能及时地发现并进行调整，这样会导致严重的预测误差，从而影响资源的整体供应。

[0005] 2.开销大。目前尚无一个通用的预测模型，能够对所有模式的负载可以进行很好的预测，即不同模式的负载需要不同的预测模型来保证预测的准确度。有些方法采用多种预测模型同时对负载进行预测，然后选择准确度比较高的结果。这种预测方法虽然能够取得好的预测结果，但是多个预测模型方法同时进行预测会导致方法本身的开销变大。

[0006] ⒊预测的准确性。不同的负载模式需要不同的预测模型。对于非周期性应用，尤其是具有很多尖峰的应用，因为负载序列不存在明显的自相关性，序列之间的随机性很大，对这种负载的预测具有很大的挑战性。对于周期性序列，周期性预测模型能够获得很好的预测效果，同时也能降低预测的计算开销。

[0007] 由此可见，在云计算资源管理中，为了实现资源的高效利用，降低应用成本，动态地为应用提供所需资源是非常重要的。预测结果作为分配资源的依据，其准确性直接影响系统应用的性能。本发明拟提出一种基于应用负载的自适应资源供应方法，其考虑了应用的模式，实现预测模型的动态切换，在保证准确性的前提下，降低本身计算开销。

[0008] 与本发明相关的现有技术有：

[0009] [1]Gong,Z.,Gu,X.,Wilkes,J.:PRESS:PRedictive Elastic ReSource Scaling for cloud systems.In:2010International Conference on Network and Service Management,pp.9-16.Niagara Fall,ON(2010)

[0010] [2]Peter,J.B.,Richard,A.D.:Introduction to Time Series and Forecasting.Springer-Verlag New York Inc.,2002.

发明内容

[0011] 本发明的主要目的是针对云计算环境中现有的各种资源供应方法中存在各种问题，提出一种基于应用负载的自适应资源供应方法。该方法通过对应用负载历史数据处理，分析出负载的模式，然后动态地选择相应的预测模型。

[0012] 具体的，本发明的基于应用负载的自适应资源供应方法，包括两个模块：预测模块和调整模块，其中预测模型包括周期性预测模型和多项式拟合预测模型。所述的周期性预测模型主要针对具有周期性特征的负载，多项式拟合预测模型主要是针对非周期性负载。

[0013] 本发明中，所述的预测模块给定应用负载的历史序列，预测模块能够计算出该应用在将来一段时间内的负载情况。

[0014] 预测模块包含三个子模块，分别为：选择器，周期性预测模型和多项式拟合预测模型。

[0015] （1）选择器

[0016] 选择器有三个任务。第一：给定一个序列，选择器分析该序列中是否存在周期性特征。如果该序列是周期序列，选择器则选择周期性预测模型进行预测，相反，如果序列中不存在明显的周期性，选择器则决定用多项式拟合模型来建模预测。第二：切换序列的预测模型。选择器实时地监控预测的误差情况，当预测出现了严重的误差时，选择器会立即对最新的历史序列进行分析，并确定合适的预测模型；当系统中连续出现N个预测值，其误差的绝对值大于某个阈值，这说明应用的模式可能发生了改变，选择器会对最新的历史序列进行分析，判断是序列的周期发生了改变，还是周期性消失，序列变成了非周期序列，然后选择相应的预测模型。第三：对于使用多项式拟合预测模型的情况，为了降低预测的计算量，在保证误差的情况下，选择器每个一段时间Ts进行周期性检测，判断其周期性，如果有，则切换到周期性预测模型，如果没有，则保持多项式拟合预测模型。

[0017] （2）周期性预测模型

[0018] 选择器检测出序列具有周期性之后，周期性预测模型则计算出序列的最佳周期，然后根据这个周期对序列进行处理，建模，预测。该模型一次可以预测一个周期的数据。

[0019] （3）多项式拟合预测模型

[0020] 如果序列不存在周期性，选择器则选择此预测模型进行预测。该模型适用于非周期模式的平稳序列和瞬时尖峰序列。相对于现有技术的多项式拟合的方法，本发明选择使用周期性预测模型来预测周期性负载，能保证预测准确性，降低预测开销。目前现有技术中有些资源供应方法采用多项式拟合对平稳序列进行预测，实验表明对于瞬时尖峰序列，多项式拟合的方法同样可以获得很好的预测效果，但为了更好的拟合负载的趋势，拟合方法往往不同，通过历史数据的拟合，得到多项式之后就可以对负载进行预测，由于多项式拟合模型主要针对局部趋势进行拟合，所以它也可以对周期性负载进行预测。

[0021] 本发明中，调整模块在预测之后对预测值进行一些误差纠正处理，优选采用多项式拟合方法进行误差值估计。

[0022] 预测中，误差是不可避免的。如果预测值大于实际的负载（高估），这时可能会导致资源的浪费，但是如果预测值低于实际负载（低估），应用可能会因为资源的不足致使违反应用服务目标。为了减少这种情况的发生，通常会在预测之后对预测值进行一些误差纠正处理。在本方法中，维护了每个应用负载序列的误差序列，这个序列保存了最新的误差值序列，同样采用多项式拟合的方法估算下一时刻的误差值。

[0023] 本发明中，为了保证预测的准确性同时降低计算开销，需要实现预测模型的切换。

[0024] 切换预测模型的原因有两点：第一，准确性，对于周期性序列，周期性预测模型能够获得很好的准确度，而对于非周期性序列，多项式拟合模型的准确性更好；第二，计算复杂度，在本发明中，周期性预测模型的复杂度是O(n)，多项式拟合模型的复杂度是O(n*m5)，其中，n是历史数据的量，m是拟合多项式的最高次幂。本发明中周期性预测模型一次可预测整个周期的值，而多项式拟合预测模型为了保证其准确度，一次预测只一个值或者最近的几个点。

[0025] 本发明方法中，要求输入应用负载的历史数据序列，在云环境中，以虚拟机的负载情况表示应用负载，由监控系统对系统中所有虚拟机负载情况进行监控与记录以及对监控数据进行预处理，本发明的一个实施例中，应用负载选自访问量的负载参数，通过下述方法获得：每隔10分钟采取一个样本点，然后组成负载序列{X(t)}，即为t时刻负载的值，或根据不同负载的样本序列应用的特点选择不同的采样周期。

[0026] 本发明方法中，选择器中，给定一个序列，利用快速傅里叶转换判断该序列中是否存在周期性成分，如果是周期性序列并且确定其周期，则采用周期性预测模型进行预测，检测出序列中存在多个周期成分时，采用如下公式选择最合适周期：

[0027]

[0028] 其中，Err(Ti)是周期为Ti时的总误差，是周期为Ti时的周期成分，选择误差值最小的周期为最合适周期。

[0029] 本发明多项式拟合预测模型中，采用下述公式对尖峰序列进行均值处理：

[0030]

[0031] 其中 为 的下取整，L的值为奇数。

[0032] 本发明方法中，当应用模式为混合模式时，采用动态的调整预测模型适应负载模式的变化。

[0033] 本发明的优点有：

[0034] 本发明提出的基于应用负载的资源供应方法，充分利用负载的模式，动态的选择相应的预测模型。并结合了应用的反馈信息实现预测模型的及时切换，在保证准确性的同时，降低了计算量。本发明通过动态选择预测模型，有效克服了因应用模式改变带来的预测准确性降低的问题，为准确预测应用的负载提供了一种有效的方法。同时，本发明不限于应用的种类，除了云环境，也可以应用于其他的IT环境中，比如IDC。

[0035] 为了便于理解，以下将通过具体的附图和实施例对本发明进行详细地描述。需要特别指出的是，具体实例和附图仅是为了说明，显然本领域的普通技术人员可以根据本文说明，在本发明的范围内对本发明做出各种各样的修正和改变，这些修正和改变也纳入本发明的范围内。

附图说明

[0036] 图1为本方法的架构图。

具体实施方式

[0037] 实施例1

[0038] 1.历史数据的提取

[0039] 在云环境中，应用封装在虚拟机中，一个应用可以封装在一个或多个虚拟机中。本发明以虚拟机为单位，进行负载的预测。关于虚拟机各种负载信息存储在数据库中。在实现中，以某种负载为例，比如访问量。对于每一个VM，每10分钟作为一个样本区间，计算每个时间区间中的平均访问量为该区间的访问量，组成访问量序列{X(t)}。同样，也可以选择负载为预测的对象，其中，样本区间的长短可以根据应用的特点选择不同的值。

[0040] 2.选择模块

[0041] 系统刚开始运行时，数据库中没有VM的历史数据，这时为VM分配一定配额的资源供应用使用，系统运行一段时间后，有了少量的历史数据，此时可以选择利用多项式拟合预测模型进行预测，因为周期性预测模型在进行建模的时候需要的历史数据的要比多项式拟合预测算法多。待历史数据增多之后，选择器可以快速傅里叶变换分析序列中是否具有周期性并决定使用哪个预测模型。

[0042] 在系统运行过程中，应用负载的模式可能发生变化，此时，使用的预测模型将出现误差变大的情况，这时需要重新判断负载的模式并实现预测模型的切换。选择器实时的检测负载的误差序列，当系统中连续出现N个误差绝对值大于某个阈值的预测值，说明负载的模式可能发生了变化，此时，选择器重新分析最新的历史数据，并选择合适的预测模型。这其中有两种情况：第一，序列的模式发生了改变，如原来是周期性负载，此时负载则表现出非周期性；或者非周期性负载变成了周期性负载；第二，模式没有发生变化，而是预测模型的参数不再适合此时的负载，如周期性负载的周期发生了改变，周期变大或是变小了，多项式的参数不再适合。选择器在重新选择了预测模型之后会对新的负载序列建模，求参数等。此外，为了降低预测本身所带来开销，如果序列中出现周期性特点，则选择能够快速的转换到周期性预测模型，如果当前是多项式拟合预测模型，经过一段时间Ts，选择器自动检测一下序列中是否出现了周期性，如果出现周期性，切换模型；如果没有，则不做任何事，再经过时间Ts之后，再进行检测，如此反复进行。本发明中Ts的选择尤为重要，如果Ts太小，选择器则频繁的进行周期性测试，则增大了开销；如果Ts太大，可能无法及时发现序列的周期性特征，系统在第一次检测到周期性特征的时候，将这时的周期记录下来，并将Ts设置为这个周期，之后每次检测出新的周期时，都将更新记录下来，并重新设置Ts。

[0043] 3.周期性预测模型

[0044] 通过傅里叶变换，可以判断序列是否具有周期性。当在序列中可能存在多个周期时，需要在多个候选周期中选择最适合的作为模型的周期。已知序列有多个候选周期，对于每个周期Ti，计算出周期组件 其中 此时可以通过下述公式计算出周期Ti的累积误差，

[0045]

[0046] 本实施例中选取使Err最小的T为模型的周期。

[0047] 取得周期T后，将序列按周期分隔为m个周期部分{Pi}，采用下述公式预测下一个周期数据：

[0048]

[0049] 其中q≤m，P和Pi是列向量，P是要预测的一个周期数据，Pi是第i个周期的历史数据，wi是周期Pi的权重。可以采用最小二乘法计算出参数wi的值。在本实施例中，将每个wi赋值1/q,则P中的值等于相同位置历史数据的均值。

[0050] 4.多项式拟合预测模型

[0051] 如果序列中没有明显的周期性，则将其归类为非周期性序列。本实施例中采用多项式拟合进行预测该种序列，所述方法适用于平稳序列和瞬时尖峰序列，但是拟合的方法不同。本实施例的实验证明在应用场景中，优选二次多项式，它可以表示为下列形式：

[0052] X(t)＝β2t2+β1t+β。

[0053] 对于其中几乎没有明显的尖峰的平稳序列，本实施例中将整体趋势作为一个模式进行拟合，越多的数据能够更好的反映序列的整体趋势。鉴于瞬时尖峰序列中没有明显的自相关性，所以它需要短期预测来快速适应资源的动态需求，对于这种序列，其中含有大量的尖峰，而且这些尖峰的持续时间很短，如果依据尖峰给应用分配大量的资源，很快又需要将分配出去的资源收回来。在本发明的模型中，首先对序列按下述方法做平滑均值处理：

[0054]

[0055] 其中 为 的下取整，L的值一般为奇数。如果L太大，会减弱尖峰的特征，太小则起不到平滑的效果。在本发明的模型中，L指定为5。因为瞬时尖峰序列的高动态性，试图找出这个序列的趋势是不明智的，本发明中选取少量的最近的数据进行拟合，能够更准确地描述该时刻序列的趋势；得到多项式之后，为了保证预测的准确度，选择只预测一个点，即t+1时刻的值，即下一个时间段应用的平均负载。

[0056] 5.误差纠正模块

[0057] 在本方法中，进行了误差序列维护，误差序列可以通过反馈信息得到。计算误差ei的方法为X(i)-X＇(i)，其中X(i)为实际负载值，X＇(i)为预测的负载值。

[0058] 本发明中，对于误差序列进行均值处理以消除尖峰造成的抖动，然后用多项式拟合方法对局部趋势进行拟合，然后估算下一时刻的误差值，得到误差值之后，将小于零的误差值赋值为零，最后将预测值与误差值相加得到最终的应用负载的预测值，能明显减少低估的情况。

[0059] 结合附图1的架构图，其中展示了整个资源供应方法的工作流程，将负载序列输入到选择器，选择器利用快速傅里叶变化判断其中是否具有周期性，如果有，则选择周期性预测模型对序列进行建模预测，预测值通过误差纠正模块，得到最后的资源分配值；如果为非周期序列，则选择多项式拟合预测模型，得到预测之后进行修正得到最终的资源分配值；一旦选择器发现应用模式发生改变，就会出发选择器对最新的负载序列进行分析，选择合适的预测模型，进行建模预测。

[0060] 从上述实施过程可以看出，本发明采用基于应用负载的资源供应方法，在预测时充分考虑了负载的模式，针对不同的模式采用不同的预测模型来保证预测的准确性。本发明的核心之处在于它能够根据预测准确度实时地发现负载模式的变化，自适应的选择适合的预测模型，充分的配合了应用的动态性。本发明在保证预测的准确性的同时能降低本身的计算开销。