云計算中彈性伸縮負載預測算法的研究和改進

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

引言

目前，國內外對云計算的投資力度逐漸增大，對彈性伸縮的研究不斷增強，但是現有的企業級別的彈性伸縮的應用存在不足[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.