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

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

引言

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

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

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

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

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

1.1 時(shí)間序列預(yù)測(cè)法

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

1.2 回歸預(yù)測(cè)法

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

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

1.3 KMP字符串匹配

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

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

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

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

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

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

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

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

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

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

3.數(shù)字串負(fù)載預(yù)測(cè)算法應(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)為最終整個(gè)序列匹配成功。

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

4.總結(jié)

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

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

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

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

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

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