云計算中彈性伸縮負(fù)載預(yù)測算法的研究和改進(jìn)

作者/楊若琪，鄭州市一中分校

引言

目前，國內(nèi)外對云計算的投資力度逐漸增大，對彈性伸縮的研究不斷增強，但是現(xiàn)有的企業(yè)級別的彈性伸縮的應(yīng)用存在不足[2]。以亞馬遜AWS為例，彈性伸縮服務(wù)只是進(jìn)行了水平層面的伸縮。這些企業(yè)的伸縮策略主要有三個部分：告警策略、定時策略/周期策略。告警策略是通過監(jiān)測某個測量值，當(dāng)這個測量值大小超過閾值，就會通知報警系統(tǒng)進(jìn)行相應(yīng)的伸縮，其中這個測量值的閾值，是在用戶使用彈性伸縮服務(wù)的時候創(chuàng)建的。定是策略是指系統(tǒng)時間與預(yù)定時間相同的時候就觸發(fā)伸縮進(jìn)行資源的動態(tài)分配，用戶創(chuàng)建定時的彈性伸縮的時候不僅要創(chuàng)建預(yù)定的時間，還要規(guī)定具體的伸縮動作，比如增加兩臺云主機。周期策略指的是在某一段時間內(nèi)彈性伸縮服務(wù)按照周期進(jìn)行相應(yīng)的資源擴展和縮小。這種策略要求用戶創(chuàng)建伸縮服務(wù)的時候需要指明開始時間和結(jié)束時間以及周期大小。

上述已經(jīng)實現(xiàn)的三種彈性伸縮策略均需要在執(zhí)行的時候?qū)?yīng)用的服務(wù)暫停，將運行的云主機掛起。在這段時間內(nèi)用戶無法進(jìn)行任何操作。通過相關(guān)資料顯示，一般配置的云主機進(jìn)行這種的伸縮服務(wù)就需要暫停將近十分鐘，給用戶帶來了極差的體驗感。

針對上述問題本文進(jìn)行大量研究發(fā)現(xiàn)利用負(fù)載預(yù)測，可以解決這個問題。根據(jù)這個思路本文提出利用改進(jìn)的KMP字符串匹配的算法進(jìn)行負(fù)載預(yù)測，到達(dá)了較高的預(yù)測準(zhǔn)確性。

1.負(fù)載預(yù)測相關(guān)算法

數(shù)學(xué)建模中的預(yù)測方法有很多，包括時間序列預(yù)測法、趨勢外推預(yù)測法、回歸預(yù)測法、灰色模型預(yù)測法，本文主要對時間序列預(yù)測法和回歸預(yù)測法進(jìn)行了研究。

1.1 時間序列預(yù)測法

時間序列就是按照時間排序的數(shù)列。時間序列預(yù)測法指的是通過分析和研究時間序列反映出事情的發(fā)展過程，發(fā)展方向和發(fā)展趨勢。然后進(jìn)行類比，延伸，得到預(yù)測下一時間段的數(shù)列。時間序列預(yù)測法的主要研究內(nèi)容是，收集和整理歷史數(shù)據(jù)，對這些數(shù)據(jù)進(jìn)行排列，分析這些時間數(shù)列，尋找其時間的變化規(guī)律得到一定的模式，然后根據(jù)這個模式預(yù)測未來的情況[3]。但是，這種模式效率較低，準(zhǔn)確率較差。

1.2 回歸預(yù)測法

回歸預(yù)測法是指根據(jù)目前的歷史時刻值模擬得到一條變化直線或者是曲線，然后根據(jù)這條曲線的變化趨勢和下一個時間點得到下一時刻值。這種預(yù)測方法主要表現(xiàn)在利用時刻值的變化趨勢上，被廣泛用于天氣預(yù)測，金融市場變化，學(xué)生成績等具有周期性變化的數(shù)據(jù)。回歸預(yù)測的步驟如下：①根據(jù)具體情況確定因變量和自變量，得到還有未知數(shù)的目標(biāo)函數(shù)。②根據(jù)歷史數(shù)據(jù)帶入因變量和自變量確定預(yù)測的未知參數(shù)。③將下一時刻的自變量帶入確定了參數(shù)的目標(biāo)函數(shù)，從而求得下一時刻因變量的值[4]。

根據(jù)上述回歸預(yù)測法的步驟可以得到這種預(yù)測法比較適合變化比較大的，比較頻繁的場景。對于預(yù)測負(fù)載并進(jìn)行彈性伸縮，回歸預(yù)測法是一種簡單粗粒度的算法。因為云計算負(fù)載值具有周期性和相似性，而且變化頻率較低，波動較小，所以回歸預(yù)測法不適合應(yīng)用于負(fù)載預(yù)測。

1.3 KMP字符串匹配

最簡單的字符串匹配是按位從左到右依次匹配，這種字符串匹配算法雖然可以完全利用歷史值的周期性和相似性，比較適合應(yīng)用于云計算的負(fù)載預(yù)測，但是這種預(yù)測算法效率較低。經(jīng)過一段時間的查詢和研究發(fā)現(xiàn)效率較高并受到廣泛應(yīng)用的字符串匹配算法—KMP字符串匹配算法。

KMP字符串匹配算法是指在簡單的匹配算法的基礎(chǔ)上，進(jìn)行提高和改進(jìn)的一種算法。這種匹配與簡單匹配算法的主要區(qū)別是在一輪匹配過程中KMP字符串匹配算法不用回溯到指針的起點，而是利用以前的匹配記錄回溯到指針起點后的某一位，這一位由具體的匹配字符串確定，詳細(xì)情況請閱讀參考文獻(xiàn)數(shù)據(jù)結(jié)構(gòu)教學(xué)中KMP算法解析[5]。這種字符串匹配算法比較適合一位匹配，也比較適合文本字符串匹配，對于負(fù)載變化值這種兩位數(shù)字串難以適應(yīng)，需要進(jìn)行改進(jìn)。本文針對上述問題提出改進(jìn)的KMP字符串匹配算法，即數(shù)字串匹配算法。

2.數(shù)字串匹配算法

首先，由于字符串匹配算法關(guān)鍵在于計算負(fù)載趨勢，所以每次開始匹配時將兩個待匹配負(fù)載序列分別減去其序列的第一個負(fù)載值，當(dāng)生成匹配結(jié)果后再加上相應(yīng)的第一個負(fù)載值；然后由于字符串匹配算法是為了尋找相似的負(fù)載趨勢而不是完全相同的負(fù)載序列，所以在對兩個待匹配負(fù)載序列進(jìn)行比較時設(shè)定一個誤差范圍，只要匹配誤差在所設(shè)定的誤差范圍內(nèi)即把待匹配的兩個負(fù)載序列視為相等。

所述的字符串匹配算法的具體內(nèi)容是包括如下操作子步驟：

（101）選取歷史負(fù)載數(shù)據(jù)序列S0；選取當(dāng)前負(fù)載數(shù)據(jù)序列T0，S0和T0是由多個兩位整數(shù)的負(fù)載值組成；

（102）把當(dāng)前負(fù)載數(shù)據(jù)序列T0中的每一個負(fù)載值減去其序列的第一個負(fù)載值，得到新序列T1，其中T1的每三位代表一個相對負(fù)載值，第一位為符號位，符號“+”代表正數(shù)，符號“–”代表負(fù)數(shù)，后兩位代表相對量；

（103）把歷史負(fù)載數(shù)據(jù)序列S0中的每一個負(fù)載值減去其序列的第一個負(fù)載值，得到新序列S1，其中S1的每三位代表一個相對負(fù)載值，第一位為符號位，符號“+“代表正數(shù)，符號“–”代表負(fù)數(shù)，后兩位代表相對量；

（104）按照改進(jìn)的字符串匹配算法KMP（Knuth–Morris–Pratt算法）對序列S1和T1進(jìn)行匹配，其中序列T1作為搜索串；首先匹配S1和T1的前三位也就是對應(yīng)S0和T0的第一個值，如果S1的前三位和T1的前三位所代表的數(shù)值之差在系統(tǒng)設(shè)定的誤差范圍內(nèi)（如–4～+4），則認(rèn)為是匹配成功的，否則認(rèn)為是匹配失敗的；如果匹配成功則匹配S1和T1的再往后的三位也就是對應(yīng)S0和T0的下一個值；如果匹配失敗則S0去掉第一個負(fù)載值，然后轉(zhuǎn)步驟（103）；如果T0或者T1每一位匹配成功則認(rèn)為最終整個序列匹配成功；其他步驟與標(biāo)準(zhǔn)的字符串匹配算法KMP完全一致；

（105）把序列S1中最后匹配成功的那個數(shù)據(jù)的下一個數(shù)據(jù)取出來，加上當(dāng)前負(fù)載數(shù)據(jù)序列T0的第一個負(fù)載值，作為系統(tǒng)負(fù)載的預(yù)測值，算法結(jié)束。

3.數(shù)字串負(fù)載預(yù)測算法應(yīng)用

假設(shè)歷史負(fù)載數(shù)據(jù)序列為：12，14，18，22，25，28，33，38，43，54，67，52，44…

當(dāng)前負(fù)載數(shù)據(jù)序列為：37，45，57，69，53

即：

(104) |(+00)–(+00)|＜=4，比較下一位 ,|(+08)–(+05)|＜=4,比 較 下 一 位，|(+20)–(+16)|＜=4,比 較 下 一 位，|(+32)–(+29)|＜=4,比較下一位，|(+16)–(+14)|＜=4,T0 或者 T1 每一位匹配成功則認(rèn)為最終整個序列匹配成功。

(105)S1中最后匹配成功的那個數(shù)據(jù)的下一個數(shù)據(jù)為+06,所以(+06)+(+37)=43即為系統(tǒng)負(fù)載的預(yù)測值。

4.總結(jié)

本文根據(jù)云計算彈性伸縮的特點和現(xiàn)狀進(jìn)行了研究，明確了目前彈性伸縮應(yīng)用的不足。經(jīng)過大量研究發(fā)現(xiàn)應(yīng)用負(fù)載預(yù)測可以彌補上述不足。本文對時間序列預(yù)測法，趨勢外推預(yù)測法，回歸預(yù)測法進(jìn)行了研究，發(fā)現(xiàn)這幾種預(yù)測法并不符合變化頻率較低，波動較小的云計算負(fù)載，最終本文利用KMP字符串匹配算法的原理，并進(jìn)行改進(jìn)提出數(shù)字串匹配算法。本文還利用數(shù)字串負(fù)載預(yù)測算法進(jìn)行應(yīng)用，得到需要預(yù)測的較為理想的負(fù)載值。

* [1]孫香花.云計算研究現(xiàn)狀與發(fā)展趨勢 [J].計算機測量與控制 ,2011,19(5)∶ 998—1001.

* [2]張建勛,古志民,鄭超.云計算研究進(jìn)展綜述[J].計算機應(yīng)用研究 ,2010, 27(2)∶ 429—433.

* [3]何勇,鮑一丹,吳江明.隨機型時間序列預(yù)測方法的研究[J].系統(tǒng)工程理論與實踐 , 1997, 17(1)∶36—43.

* [4]管弈.回歸預(yù)測法[J].學(xué)習(xí)與實踐,1985(10)∶33—34.

* [5]李靜.字符串的模式匹配算法—基于KMP算法的討論[J].青島科技大學(xué)學(xué)報(自然科學(xué)版),2002,23(2)∶78—80.