云计算中弹性伸缩负载预测算法的研究和改进

作者/杨若琪，郑州市一中分校

引言

目前，国内外对云计算的投资力度逐渐增大，对弹性伸缩的研究不断增强，但是现有的企业级别的弹性伸缩的应用存在不足[2]。以亚马逊AWS为例，弹性伸缩服务只是进行了水平层面的伸缩。这些企业的伸缩策略主要有三个部分：告警策略、定时策略/周期策略。告警策略是通过监测某个测量值，当这个测量值大小超过阈值，就会通知报警系统进行相应的伸缩，其中这个测量值的阈值，是在用户使用弹性伸缩服务的时候创建的。定是策略是指系统时间与预定时间相同的时候就触发伸缩进行资源的动态分配，用户创建定时的弹性伸缩的时候不仅要创建预定的时间，还要规定具体的伸缩动作，比如增加两台云主机。周期策略指的是在某一段时间内弹性伸缩服务按照周期进行相应的资源扩展和缩小。这种策略要求用户创建伸缩服务的时候需要指明开始时间和结束时间以及周期大小。

上述已经实现的三种弹性伸缩策略均需要在执行的时候将应用的服务暂停，将运行的云主机挂起。在这段时间内用户无法进行任何操作。通过相关资料显示，一般配置的云主机进行这种的伸缩服务就需要暂停将近十分钟，给用户带来了极差的体验感。

针对上述问题本文进行大量研究发现利用负载预测，可以解决这个问题。根据这个思路本文提出利用改进的KMP字符串匹配的算法进行负载预测，到达了较高的预测准确性。

1.负载预测相关算法

数学建模中的预测方法有很多，包括时间序列预测法、趋势外推预测法、回归预测法、灰色模型预测法，本文主要对时间序列预测法和回归预测法进行了研究。

1.1 时间序列预测法

时间序列就是按照时间排序的数列。时间序列预测法指的是通过分析和研究时间序列反映出事情的发展过程，发展方向和发展趋势。然后进行类比，延伸，得到预测下一时间段的数列。时间序列预测法的主要研究内容是，收集和整理历史数据，对这些数据进行排列，分析这些时间数列，寻找其时间的变化规律得到一定的模式，然后根据这个模式预测未来的情况[3]。但是，这种模式效率较低，准确率较差。

1.2 回归预测法

回归预测法是指根据目前的历史时刻值模拟得到一条变化直线或者是曲线，然后根据这条曲线的变化趋势和下一个时间点得到下一时刻值。这种预测方法主要表现在利用时刻值的变化趋势上，被广泛用于天气预测，金融市场变化，学生成绩等具有周期性变化的数据。回归预测的步骤如下：①根据具体情况确定因变量和自变量，得到还有未知数的目标函数。②根据历史数据带入因变量和自变量确定预测的未知参数。③将下一时刻的自变量带入确定了参数的目标函数，从而求得下一时刻因变量的值[4]。

根据上述回归预测法的步骤可以得到这种预测法比较适合变化比较大的，比较频繁的场景。对于预测负载并进行弹性伸缩，回归预测法是一种简单粗粒度的算法。因为云计算负载值具有周期性和相似性，而且变化频率较低，波动较小，所以回归预测法不适合应用于负载预测。

1.3 KMP字符串匹配

最简单的字符串匹配是按位从左到右依次匹配，这种字符串匹配算法虽然可以完全利用历史值的周期性和相似性，比较适合应用于云计算的负载预测，但是这种预测算法效率较低。经过一段时间的查询和研究发现效率较高并受到广泛应用的字符串匹配算法—KMP字符串匹配算法。

KMP字符串匹配算法是指在简单的匹配算法的基础上，进行提高和改进的一种算法。这种匹配与简单匹配算法的主要区别是在一轮匹配过程中KMP字符串匹配算法不用回溯到指针的起点，而是利用以前的匹配记录回溯到指针起点后的某一位，这一位由具体的匹配字符串确定，详细情况请阅读参考文献数据结构教学中KMP算法解析[5]。这种字符串匹配算法比较适合一位匹配，也比较适合文本字符串匹配，对于负载变化值这种两位数字串难以适应，需要进行改进。本文针对上述问题提出改进的KMP字符串匹配算法，即数字串匹配算法。

2.数字串匹配算法

首先，由于字符串匹配算法关键在于计算负载趋势，所以每次开始匹配时将两个待匹配负载序列分别减去其序列的第一个负载值，当生成匹配结果后再加上相应的第一个负载值；然后由于字符串匹配算法是为了寻找相似的负载趋势而不是完全相同的负载序列，所以在对两个待匹配负载序列进行比较时设定一个误差范围，只要匹配误差在所设定的误差范围内即把待匹配的两个负载序列视为相等。

所述的字符串匹配算法的具体内容是包括如下操作子步骤：

（101）选取历史负载数据序列S0；选取当前负载数据序列T0，S0和T0是由多个两位整数的负载值组成；

（102）把当前负载数据序列T0中的每一个负载值减去其序列的第一个负载值，得到新序列T1，其中T1的每三位代表一个相对负载值，第一位为符号位，符号“+”代表正数，符号“–”代表负数，后两位代表相对量；

（103）把历史负载数据序列S0中的每一个负载值减去其序列的第一个负载值，得到新序列S1，其中S1的每三位代表一个相对负载值，第一位为符号位，符号“+“代表正数，符号“–”代表负数，后两位代表相对量；

（104）按照改进的字符串匹配算法KMP（Knuth–Morris–Pratt算法）对序列S1和T1进行匹配，其中序列T1作为搜索串；首先匹配S1和T1的前三位也就是对应S0和T0的第一个值，如果S1的前三位和T1的前三位所代表的数值之差在系统设定的误差范围内（如–4～+4），则认为是匹配成功的，否则认为是匹配失败的；如果匹配成功则匹配S1和T1的再往后的三位也就是对应S0和T0的下一个值；如果匹配失败则S0去掉第一个负载值，然后转步骤（103）；如果T0或者T1每一位匹配成功则认为最终整个序列匹配成功；其他步骤与标准的字符串匹配算法KMP完全一致；

（105）把序列S1中最后匹配成功的那个数据的下一个数据取出来，加上当前负载数据序列T0的第一个负载值，作为系统负载的预测值，算法结束。

3.数字串负载预测算法应用

假设历史负载数据序列为：12，14，18，22，25，28，33，38，43，54，67，52，44…

当前负载数据序列为：37，45，57，69，53

即：

(104) |(+00)–(+00)|＜=4，比较下一位 ,|(+08)–(+05)|＜=4,比 较 下 一 位，|(+20)–(+16)|＜=4,比 较 下 一 位，|(+32)–(+29)|＜=4,比较下一位，|(+16)–(+14)|＜=4,T0 或者 T1 每一位匹配成功则认为最终整个序列匹配成功。

(105)S1中最后匹配成功的那个数据的下一个数据为+06,所以(+06)+(+37)=43即为系统负载的预测值。

4.总结

本文根据云计算弹性伸缩的特点和现状进行了研究，明确了目前弹性伸缩应用的不足。经过大量研究发现应用负载预测可以弥补上述不足。本文对时间序列预测法，趋势外推预测法，回归预测法进行了研究，发现这几种预测法并不符合变化频率较低，波动较小的云计算负载，最终本文利用KMP字符串匹配算法的原理，并进行改进提出数字串匹配算法。本文还利用数字串负载预测算法进行应用，得到需要预测的较为理想的负载值。

* [1]孙香花.云计算研究现状与发展趋势 [J].计算机测量与控制 ,2011,19(5)∶ 998—1001.

* [2]张建勋,古志民,郑超.云计算研究进展综述[J].计算机应用研究 ,2010, 27(2)∶ 429—433.

* [3]何勇,鲍一丹,吴江明.随机型时间序列预测方法的研究[J].系统工程理论与实践 , 1997, 17(1)∶36—43.

* [4]管弈.回归预测法[J].学习与实践,1985(10)∶33—34.

* [5]李静.字符串的模式匹配算法—基于KMP算法的讨论[J].青岛科技大学学报(自然科学版),2002,23(2)∶78—80.