面向負載-時間窗口的基于PSO-GA的云軟件服務自適應資源分配方法

楊立堅，陳 星，黃引豪

(福州大學 數學與計算機科學學院，福州 350108)

(福建省網絡計算與智能信息處理重點實驗室，福州 350108)

1 引 言

云計算是將某一個或某幾個數據中心的計算資源虛擬化之后，向用戶提供以租用計算資源的服務，其為海量數據和計算資源提供基礎性的接入，并且這些資源可以按需進行動態接入和釋放.在云計算環境中，云軟件服務面臨著動態變化的工作負載，然而，這種動態和不可預測的工作負載可能導致軟件服務質量的下降，特別是當對資源的需求增加時.為了在不斷變化的工作負載下提供資源的可伸縮性和彈性，云提供商通常需要在共享基礎設施中提供軟件和硬件資源的按需配置.如今，基于云的軟件服務的大量使用證明了云軟件工程正在獲得發展勢頭[1].如何為這些云軟件服務合理分配資源是一項具有挑戰性的任務.近年來，隨著云軟件資源自適應技術[2-5]的不斷發展，云應用分配資源的有效性有所提高，用戶追求的高軟件服務質量與云廠商追求的低云資源開銷之間的矛盾關系也有所平衡.與此同時，如何更好地提高資源分配的有效性成為了自適應技術發展新的挑戰.

現有的自適應技術中，大都是針對云環境中當前負載的狀況做出響應，并進行資源自適應分配.AlQayedi等人[6]提出一種基于排隊理論的方案，根據當前的工作負載來估計滿足響應時間所需的VM實例的數量，該方案還采用響應式資源調配技術，以CPU利用率為閾值，定期(每1或2分鐘)檢查工作負載狀況，重新計算所需的VM實例，以調整(添加或刪除)所分配的VM數量，但當未來工作負載波動比較嚴重時，該方案未能得出較好的虛擬機資源分配方案.Maurer等人[2]設計了一種新的自適應和資源高效的決策方法，并根據工作負載的波動性，提出了基于規則的自適應知識管理方法來實現虛擬機的自主重構，但其未考慮資源成本最小化目標.Xie等人[7]提出了一種基于粒子群算法的資源配置和價格調整策略，根據工作負載的特點，設計了一個效用函數來評價服務質量.根據所有工作負載對資源的需求，由相應的資源代理動態調整資源價格，以獲得每個工作負載的最大利潤，但粒子群算法存在局部收斂問題，在計算資源配置與價格調整時，得到的方案無法代表整體最優解.Dhrub等人[8]了一種考慮QoS指標的動態調整資源分配的自伸縮模型，它在虛擬機級別執行資源更正，同時考慮使用不足和使用過度的情況，雖然該方法能夠根據不斷改變的負載對分配給應用程序的資源進行按需調整，但未綜合考慮QoS與虛擬機租賃成本之間的關系，且未將未來復雜波動的負載變化情況考慮到方法中.Chen等人[9]提出了一種適用于云計算環境下軟件服務的自適應資源管理框架，該框架由3部分構成，首先通過歷史數據訓練QoS預測模型，其次采用基于PSO的運行時決策算法結合QoS預測值來確定未來的資源分配操作，再通過引入反饋控制使資源分配達到預期效果，但其在計算QoS預測值時，未考慮未來負載的影響.

對基于云資源的系統應用來說，應用的負載情況是影響資源分配的主要因素之一.在云環境中，預測工作負載對于更有效地分配資源是可行的.僅通過當前負載來進行資源分配，其有效性受到未來負載波動的影響，而通過預測工作負載[10-12]來提高資源分配有效性則受到工作負載預測模型精度的影響.針對以上問題，受Wang等人[13]的啟發，本文提出一種面向負載時間窗口的云軟件服務資源自適應分配策略，并在此基礎上建立優化虛擬機資源分配方案計算模型，在進行資源分配時，將當前的負載以及窗口內未來的負載加入模型計算過程中，使用基于PSO-GA的運行時決策算法搜索合適的資源分配方案.該模型旨在提高云軟件服務的自適應資源分配的有效性.由于工作負載的變化是給定的，因此本文的模型是正交于工作負載預測的，可以與現有的負載預測模型相關聯.

本文的主要貢獻如下：

?對面向負載時間窗口的資源分配進行形式化定義.

?使用基于PSO-GA的運行時決策算法，結合QoS預測模型，根據面向負載的時間窗口，搜索目標資源分配方案，并對當前分配方案作出調整.

?我們在RUBiS基準上評估我們的方法.實驗結果表明，該方法能夠提高資源分配的有效性.

本文剩余的部分由以下內容構成，第2部分進行問題的形式化定義.第3部分整體概述了方法的實現框架，并詳細介紹PSO-GA算法，其中包括算法中變量的定義以及具體實現，然后介紹如何根據算法結果調整資源分配方案.第4部分實例研究，報告了我們的方法與其他方法在RUBiS基準上不同指標進行對比的實驗結果.第5部分對本文進行總結.

2 問題定義

在這部分，我們對問題進行形式化定義.

當運行的環境變化的時候，云中軟件服務就會有不同的服務質量(Quality of Service，QoS).而運行環境變化在本文中主要分為外部環境變化與內部環境變化.外部環境變化是由外部因素造成的，內部環境變化主要是受管理系統影響.在本節的問題定義中，有兩個主要的因素，如表1所示.

表1 問題定義中的主要元素

外部因素主要指系統工作負載.假設負載是一個分段函數，每個時間段的負載不變，如式(1)所示：

(1)

我們假設每段負載持續的時間是相等的，并由二元組表示：wi=.ni表示ti時刻的請求數量，ri表示ti時刻的請求讀寫率.另外，在t≥ti+1的負載是我們不能觀測到的.

內在因素指的是由不同類型與數量的虛擬機組成的分配方案.由于虛擬機在租賃的時候是按小時來收費，所以我們假設虛擬機每次租賃一小時，且一小時后自動關閉.則我們在調整虛擬機分配方案時刻，只需考慮增加的虛擬機方案.對應于每個時段的負載，虛擬機增加方案可以表示為：

(2)

假設每個調整方案中有m種可增加的虛擬機類型Type=<1，2，3，…，m>，則ti時刻增加虛擬機配置方案addi可以表示為：

(3)

對應于增加虛擬機分配方案的是每個時刻調整后的虛擬機分配方案：

(4)

其中q=1h/Δt，表示最大的未過期增加虛擬機分配方案的數量.Δt=ti+1-ti，表示每種負載持續的時間段.由公式(4)可知，每個時段的虛擬機分配方案是由對應時段未到期的所有增加虛擬機方案相加得到.

當為云系統應用分配資源時，云工程師或者自適應系統的目標是需要權衡分配方案對應的服務質量QoS與資源耗費Cost之間的關系.我們通過目標函數來表示它們之間的關系.

目標函數的其中一個參數為QoSi，它表示ti時刻的QoS值，通常使用服務等級協議(Service-Level Agreement，SLA)來指定，包括響應時間(Response Time，RT)，數據吞吐量(Data Throughput，DT)等等.響應時間表示用戶請求服務的時候，等待服務響應所需時間.而數據吞吐量表示在一個給定時間系統能夠處理的信息量.但是這些指標無法用來預測系統的QoS值，因為只有分配完虛擬機資源后，這些指標才能被監控到.于是就需要一個QoS預測模型[13，14]，如公式(5)所示，該模型的輸入包括請求數量與類型(w)，虛擬機數量與類型(vm)，輸出為QoS預測值.

QoSpredicted=QoS(w，vm)

(5)

通過該QoS預測模型，給定一個負載w與資源配置方案vm，模型就能夠預測出對應的QoS值.

函數的另一個參數為Costi它表示ti時刻負載區間對應的增加虛擬機addi的成本.假設每種類型虛擬機租賃消費P=，則Costi可表示為

(6)

那么目標函數可以通過QoSi與Costi表示為：

(7)

公式中r1與r2代表權重，是由工程師根據經驗進行選定.

然而，在實際環境中，僅通過當前的負載計算出的對應資源分配方案有效性無法得到保障，于是，我們需要使用面向負載的時間窗口，根據窗口內的負載給出對應的增加虛擬機分配方案，進而求出對應時刻的虛擬機分配方案.

面向負載時間窗口，在進行資源分配的時刻，時間窗口能夠觀察相對于當前時刻之后的一段負載，進而對資源進行相應調整.

假設窗口i能夠預測到長度為l(包含的區間數量)的工作負載區域，結合公式(1)，該區域內的負載Wi可表示為：

(8)

與負載窗口Wi對應的是窗口內增加虛擬機分配方案ADDi，它表示為：

(9)

那么根據公式(9)，窗口內虛擬機分配方案VMi可表示為：

(10)

于是，問題就轉化為搜索窗口內一個最優的增加虛擬機資源分配方案.由于該問題是一個經典的組合優化問題，在理論上屬于np難題，所以，我們可以使用啟發式算法基于適應度函數來搜索一個合適的資源分配方案.

3 方 法

本節介紹方法的實現，整體架構如圖1所示.

圖1 方法概覽圖

3.1 方法概覽

本文介紹了面向負載的時間窗口，并通過負載窗口計算虛擬機資源分配方案，如圖1所示，可以分為以下幾個部分：

首先，初始化時間窗口參數，其中包括時間窗口對應的負載、負載對應的增加虛擬機分配方案以及虛擬機分配方案.其次，我們使用PSO-GA算法，在QoS預測模型的支持下，搜索窗口內的目標資源分配方案.最后，根據目標資源分配方案，對當前的虛擬機分配方案作出相應調整.

3.2 PSO-GA搜索目標資源分配方案

3.2.1 粒子群優化算法(PSO)

PSO算法[15，16]屬于進化算法的一種，通過模擬自然界鳥群遷徙的活動，讓粒子不斷地迭 代從而尋找最優解.粒子在PSO算法中是非常重要的概念，每一個粒子代表優化問題的一個候選解，粒子通過自身歷史最優值與族群歷史最優值不斷在解空間中迭代更新.式(11)是粒子的速度公式，式(12)是粒子的位置公式.

(11)

(12)

3.2.2 遺傳算法(GA)

GA算法[16]是通過模擬生物界中生物進化過程的計算模型.遺傳算法同樣從隨機解出發，按照自然界優勝劣汰的原則，通過上一代優秀個體的組合交叉和變異過程，逐代演化生成越來越好的下一代個體，從而找到更優的近似解.

3.2.3 基于PSO-GA的目標虛擬機資源分配方案搜索策略

本章提出一種改進的粒子群算法PSO-GA，PSO-GA算法通過引入PSO算法對粒子個體的優化過程，使GA算法中的粒子個體得到優化，從而解決了GA算法搜索后期效率低下的問題.PSO-GA算法先通過粒子的適應度評價函數對粒子進行排序，保留其中優秀的個體用于下一次PSO算法迭代，而淘汰表現較差的個體.通過對優秀個體的交叉與變異操作得到剩下的粒子，進入下一代.在本章中，一個粒子只是代表一個時間窗口內的解，每經過一個固定的時間間隔，通過PSO-GA求出一個最佳的粒子當做該時刻的目標虛擬機資源分配方案.下面對改進粒子群算法中的粒子編碼、適應度函數、以及更新策略進行設計.

3.2.4 粒子編碼

對于云軟件服務資源分配問題的編碼，本章采用離散編碼方式對PSO的粒子進行編碼[17].對于時間窗口k，窗口內的增加虛擬機資源分配方案可以表示為：

(13)

其中l為時間窗口k的長度，它表示窗口內增加虛擬機資源分配方案的數量.

將窗口k內增加虛擬機分配方案ADDk作為粒子X，一個粒子代表窗口k對應的增加虛擬機資源分配方案.假設窗口中虛擬機類型有m種，窗口長度為l，則第i個粒子的第t次迭代可表示為：

(14)

圖2展示了長度為3，虛擬機種類為3的時間窗口內的一個粒子編碼.它表示窗口中第1個增加虛擬機分配方案為[011]，第2個增加虛擬機分配方案為[014]，第3個增加虛擬機分配方案為[001].

圖2 增加虛擬機資源分配方案粒子編碼

3.2.5 適應度函數建立

在引入時間窗口之后，適應度函數需要通過窗口內的負載以及虛擬機資源分配方案來計算.假設時間窗口的長度為l，則窗口i內的負載Wi可表示為：

(15)

由公式可以看出，窗口i內的負載是分段函數.

時間窗口i內的虛擬機資源分配方案VMi需要通過窗口i內增加的虛擬機資源分配方案ADDi計算得到，ADDi如公式(16)所示：

(16)

則VMi可表示為：

(17)

由于我們已經對窗口i內增加的虛擬機資源分配方案ADDi進行粒子編碼，所以VMi可以通過粒子編碼計算得到.

窗口內增加虛擬機資源分配方案通過fitness函數進行評估.fitness函數在QoS值與資源成本Cost之間進行權衡，能夠指導粒子群優化算法搜尋求解的方向.由于引入了時間窗口，則由上述公式，fitness函數可表示為：

(18)

fitness函數中的QoS值為窗口i內總的QoS值，如公式(18)前半部分所示，其中wk∈Wi，表示窗口i內l個時段中某個時段的負載.而vmk∈VMi，表示窗口i內l個時段中某個時段的虛擬機資源分配方案

于是，根據時間窗口i內的負載Wi以及虛擬機分配方案VMi中每個時段對應的wk與vmk，通過QoS預測模型(式(5))，分別計算出QoS，然后再對這l個QoS求和，就能得到窗口i內總的QoS值.

另外，它們的權重r1與r2是專家通過對不同系統的需求而定的.且從公式中可以明顯看出，窗口內越好的增加虛擬機資源分配方案，所對應的評估值也越小.因此，在給定窗口i內的負載Wi以及ADDi對應的粒子編碼后，我們就可以通過fitness函數計算出對應的評估值.

3.2.6 粒子更新策略

我們通過遺傳算法的交叉變異過程來更新整個粒子群的狀態.

變異操作隨機選取粒子中的一個基因段，不規律改變其基因值，且新值必須都在對應的閾值內[18].圖3為對圖2粒子編碼的變異操作，隨機選擇粒子的一個基因段mg1，mg1位置上的值由(0，1，4)變異為(0，2，3)，該變異符合虛擬機分配準則.

圖3 粒子編碼慣性部分變異

圖4為局部(或全局)最優粒子部分的交叉操作[19]，隨機產生兩個交叉的基因段位置cg1與cg2，將這兩個基因段內的值替換為pBest(或gBest)對應基因段的值.在更新過程對于局部(或全局)最優粒子的交叉概率都為50%.

圖4 粒子編碼局部(或全局)最優粒子部分的交叉操作

3.2.7 算法流程

如PSO-GA算法所示，搜索目標虛擬機配置方案的流程如下：

Step 1.隨機初始化粒子種群，其中包括種群規模大小N、最大迭代次數以及種群本染色體addi，并初始化每個種群的局部最優解pBesti以及全局最優解gBest，如算法2-6行.

Step 2.在滿足算法執行條件下，通過粒子的交叉變異操作對粒子群進行更新操作，通過公式(13)計算每個種群染色體addi的評估值，并更新全局最優與局部最優染色體，如算法7-16行所示.

Step 3.輸出最終的全局最優解gBest.

算法.PSO-GA

輸入：種群規模N

輸出：滿足執行條件下的一個全局最優解gBest

1.procedure PSO-GA

2.foreach particlei

3. Initialize velocityaddifor particlei

4. Evaluate particleiand setpBesti=addi

5.endfor

6.gBest=min{pBesti}

7.whilenot stop

8.fori=1toN

9. update particleibymutateandcrossover

10. Evaluate particlei

11.ifFitnessi(addi)

12.pBesti=addi

13.ifFitnessi(pBesti)

14.gBest=pBesti

15.endfor

16.endwhile

17.printgBest

18.end procedure

3.3 調整虛擬機資源分配方案

于是，在每個資源調整的時刻，通過PSO-GA算法在窗口內搜索目標增加虛擬機資源方案，該方案是在滿足算法執行條件下搜索到的適應度函數值最小的方案，可以表示為：

(19)

4 實例研究

我們在RUBiS[20]基準上評估我們的方法.評估的目標是：基于面向負載的時間窗口，通過比較PSO-GA算法與其他兩種方法計算出來的目標虛擬機分配方案的各項指標，評估PSO-GA算法的性能.

4.1 實驗環境

RUBiS是一個模仿eBay.com的拍賣網站原型，通常用于評估應用服務器的性能可伸縮性[20].它提供了一個客戶端，可以為各種工作負載模式模擬用戶行為.我們假設工作負載量在[2000，7000]范圍內，并且工作負載中有兩種類型的任務(讀與寫).實驗中使用到的虛擬機分為小中大3種類型，每種配置方案都是由虛擬機數量與類型構成的，具體的虛擬機信息如表2所示.

表2 虛擬機類型及價格

在實驗中，我們通過一個Sigmoid函數將響應時間(RT)的值映射到[0，1]的時間間隔，其值實際上是QoS值，根據經驗數據，映射的QoS值(代表客戶對服務質量的滿意度)與響應時間的函數如圖5所示.

圖5 QoS映射圖

本實驗在已知一段時間內連續的負載前提下進行的.這里，我們定義Wi={wi，wi+1，wi+2}，時間窗口長度為90分鐘(窗口內包含3段負載)，每30分鐘預測一次.并設置了實驗場景驗證方法的性能.

圖6是負載情況圖，我們一共預測了540分鐘的時間，為了使預測趨于穩定，假設540分鐘后的負載是無法觀測到的.對于每個時間段的負載，在其下方都有對應的讀寫比率.

圖6 工作負載情況圖

如公式(18)所示，適應度函數表示云工程師給出的資源分配目標.較好的資源配置方案應獲得較小的適應度函數值.云工程師預先定義的權重(r1和r2)反映了他們對服務質量和資源成本的不同偏好.在實際應用中，最常見的適應度函數是平衡服務質量和資源成本，由于云服務的服務質量和資源之間的復雜關系，這一點也很難實現.因此，在實驗中，我們根據我們的經驗設置r1=900和r2=1/6，以平衡QoS和資源成本，如公式(20)所示：

(20)

4.2 實驗總體介紹

我們在面向負載時間窗口計算目標虛擬機資源分配方案的過程中，使用3種方法進行實驗：

a)貪心算法.貪心法不考慮時間窗口中負載的變化，在每次計算虛擬機資源分配方案的時候，都是以上一時刻的最優配置計算當前時刻的負載對應的最優虛擬機配置.

b)單點最優局部隨機法.分成兩個階段來進行.首先，一個時間窗口內的負載區間Wi中包含3個負載，對于每個負載，我們依據Fitness函數，遍歷所有虛擬機配置方案，找到對應的一個評估值最小的方案，我們稱之為單點最優配置方案.其次，根據單點最優配置方案，在其附近隨機增減2臺虛擬機來進行實驗.在設定的運行時間內，得到窗口i內最優的一個虛擬機資源分配方案.

c)PSO-GA算法.初始化時間窗口對應的增加虛擬機ADDi的染色體，設定種群規模為50，迭代次數為100，每次迭代通過公式(18)計算每個粒子染色體的評估值，并選出全局最優粒子與局部最優粒子，再通過概率都為50%的變異交叉對粒子的染色體進行更新操作.在滿足算法執行條件的前提下，繼續進行更新后的粒子評估值計算，以及迭代更新.

我們設置單點最優局部隨機法與PSO-GA算法執行的時間都為2分鐘，進而比較上述3種實驗方法的性能.

4.3 實驗結果比較與分析

我們分別對單點最優局部隨機法、貪心法以及PSO-GA在給定的負載場景下進行實驗.對應的虛擬機分配結果如圖7至圖9所示，其中位于圖上方的表格表示每個時刻對應的增加虛擬機分配方案，條形圖表示每個負載根據增加虛擬機分配方案調整過后對應的虛擬機分配方案，它們由小中大三種虛擬機組成.

圖7 貪心算法實驗虛擬機資源分配結果

圖8 單點最優局部隨機法實驗虛擬機資源分配結果

圖9 PSO-GA實驗虛擬機資源分配結果

為了更好的評估我們的方法的性能，我們將QoS值、成本以及公式(20)所獲取到的評估值一起作為資源分配有效性的評估指標，這可以證明我們的方法總體上提供了最合理的資源分配計劃.

圖10表示系統的總體Fitness值，它是由0-360分鐘內各個時段的評估值相加而來.從這個圖中可以看出，我們的方法比貪心算法跟單點最優局部隨機法的性能分別高出5.74%和4.15%.這些性能增益主要是由于PSO-GA算法既注重了種群每一代之間的進化過程，又注重了優秀個體的保留與再成熟，提高了種群多樣性，計算出來的虛擬機資源配置更接近最優資源分配方案.而單點最優局部隨機法，雖然是基于單點最優進行隨機實驗，但搜索沒有目的，具有隨機性，無法更好地向最優的資源配置方案靠近，貪心算法由于每次只考慮當前負載的最優資源分配方案，所以，其計算出來的方案會隨負載的波動而波動.

圖10 總體Fitness值比較

另外，從圖11可以看出，就QoS而言，PSO-GA計算出來的配置方案的平均QoS值為0.96，比其他兩種方法的平均QoS值好，且在0～360分鐘內，QoS值維持在0.91～0.99之間，特別是在60～150分鐘負載快速上升階段，我們可以看到基于PSO-GA算法的虛擬機資源分配方案能夠將QoS值維持在一個合理的水平，且比較穩定.再觀察貪心算法的QoS曲線，可以看出，它的QoS值波動比較嚴重，(在240分鐘的時候達到0.95，而到120分鐘時，降到0.77)而單點最優局部隨機法的QoS值在0.80～0.94之間，平均QoS值介于兩者之間，為0.89.其次，我們比較了PSO-GA算法與其他兩種對比方法的資源成本，如圖4～圖7中的條形圖所示，貪心算法在0～360分鐘內的每個時段的平均成本為89.24 RMB，單點最優局部隨機法為91.94 RMB，而我們的PSO-GA的平均成本最高，為102.65 RMB.可以發現，在保證服務質量的前提下，PSO-GA算法的資源成本是我們能夠接受的.

圖11 QoS與Cost比較

最后，我們比較3種實驗方法的執行時間，可以明顯地看出，在同樣執行2分鐘時間的前提下，PSO-GA算法在計算虛擬機資源分配方案的性能上比單點最優局部隨機法要好.雖然貪心算法計算虛擬機資源分配方案的速度是3種方法中最快的，但是，其虛擬機資源分配方案的各項指標比較差.

5 總 結

在進行資源分配的時候，通過每個時刻負載來計算資源分配方案無法滿足負載波動較大的云環境，且有效性無法得到保證.而使用面向負載的時間窗口，將當前的負載以及窗口內未來的負載加入計算，可以提高自適應資源分配的有效性.在本文中，我們提出面向負載時間窗口的云軟件服務自適應資源分配策略，并使用PSO-GA運行時決策算法來搜索合適的虛擬機資源分配方案.然后，通過將PSO-GA算法與另外兩種方法進行比較，驗證算法的性能.實驗結果表明，PSO-GA算法所表現出來的性能比其他兩種方法更好.

盡管本文的方法計算出的資源分配方案有效性有所提高，但是文中使用的負載是通過離散分段函數來定義的，在實際環境中，負載更多時候是連續的，此時，通過時間窗口觀察到的負載數量就比分段函數多，如何將窗口內的連續負載加入計算成為新的挑戰.未來的研究方向主要有兩點：一是結合實驗中3種算法的優缺點，繼續研究和改進算法，提高算法性能.二是引入連續負載函數，研究如何在連續負載環境中進行自適應資源分配.