IaaS云融合Q學習的自適應虛擬機部署

宋建松，連 瑋，陜粉麗，閆慧鵬

(1.長治學院 計算機系，山西 長治 046011；2.中國電信集團有限公司 長治分公司，山西 長治 046011)

0 引 言

虛擬化是云數據中心的主要技術，利用虛擬化可以在物理服務器上部署不同性能的虛擬機，提高資源利用率[1]。虛擬化的主要優勢是在數據中心內可以進行動態虛擬機合并來降低能耗，通過將虛擬機部署到更少物理主機上，將閑置主機轉換為睡眠以提升能效。動態虛擬機合并實現了運行時虛擬機在不同主機間的在線遷移[2]，尤其在主機處于低負載或超載狀態時，遷移將具有諸多好處。因此，通過遷移會使得數據中心的資源管理更加靈活。然而，虛擬機在線遷移對于運行在虛擬機上的任務具有負面影響[3]。由于在云服務提供者與其用戶間提供相應服務質量至關重要，所以動態虛擬機合并應該著重考慮優化虛擬機遷移量。

很多算法通過裝箱算法求解虛擬機部署問題，但會產生過多非必要遷移，增加SLA違例。比較已有工作最小化活躍主機量，本文設計一種基于Q學習的虛擬機部署算法，同步最小化虛擬機遷移量和SLA違例。所提算法由兩個階段組成，第一個階段目標是從超載主機上遷移虛擬機，避免SLA違例；第二個階段目標是合并非超載主機的虛擬機。為了預測負載，設計了一種Q學習機制的預測方法，對未來資源利用率進行有效預測。實驗部分通過運行云環境中的兩種現實負載流對算法進行評估，驗證了該算法在優化能效、提升性能和降低虛擬機遷移量上的優勢。

1 相關工作分析

目前，很多方法已被提出用于求解多目標優化的資源管理問題，在IaaS云提供方與其用戶間維持需要的QoS等級是當前云資源管理的最主要目標之一。基于這一考慮，多數已有算法利用靜態利用率閾值預防服務性能的下降。文獻[4]利用一個上限值避免主機CPU的利用率達到100%，從而導致性能降低。文獻[5]設計的虛擬機部署算法將主機CPU利用率維持在靜態上限與下限值之間。文獻[6]利用靜態CPU閾值發現數據中心內的低載和超載主機。靜態閾值設置雖然具有簡單性，但在動態的云負載環境中，不同類型的應用負載運行在一臺主機上，靜態閾值不切實際。因此，利用率閾值應用根據負載類型的不同做出相應調整，并以此執行有效的虛擬機優化部署。文獻[7] 根據歷史數據的統計分析設計多種CPU閾值的預測方法，在當前的主機CPU利用率超過上限值的基礎上，通過虛擬機部署算法實現虛擬機遷移。然而，該算法僅考慮了當前的資源請求，忽略了未來的資源請求，此時得到的閾值會無法反映當前的負載狀況。因此，該過程會產生過多非必須的虛擬機遷移，進而增加數據中心內SLA違例的風險。

本文設計了IaaS中的一種自適應的多層次資源管理系統SARMS，在此系統的基礎上，主要做了以下工作：

(1)利用Q學習機制設計了一種自適應利用率閾值AUT機制動態調整資源利用率閾值。不同于現有工作僅僅考慮CPU利用率，AUT同步考慮了CPU資源和內存資源利用率。結合兩類資源閾值，SARMS系統可以更好識別SLA違例并對其進行預防。

(2)在SARMS系統內設計了一種虛擬機部署優化算法可維持主機利用率在自適應閾值以內，以避免SLA違例；同時，算法可以將虛擬機合并至最小數量的活躍主機上，以降低數據中心內的整體能耗。

(3)利用Google負載和PlanetLab負載兩種現實數據流在模擬云環境中對算法性能進行評測，評估了Q學習機制下對利用率閾值自適應調整的有效性，并與其它閾值算法在整體能耗、SLA違例比例以及虛擬機完成的遷移量進行了系統比較，體現了本文算法的性能優勢。

2 系統模型

考慮數據中心由m臺異構物理主機構成，表示為PM={PM1,PM2,…,PMm}。 每臺物理主機擁有D類資源屬性，包括CPU、內存、網絡I/O和存儲能力。多臺虛擬機VM可以通過虛擬機監視器VMM部署在一臺主機上。初始時，虛擬機根據降序最佳適應啟發式方法BFD部署在虛擬機上。在任意給定的時間，用戶發送n臺虛擬機的請求，表示為VM={VM1,VM2,…VMn}， 部署在物理主機上。由于虛擬機和主機的請求資源利用率會隨著時間發生改變，云資源管理系統需要根據資源請求控制物理和虛擬資源分配。基于此，本文設計了一種基于分層的自適應資源管理系統，如圖1所示，將系統命名為SARMS。系統由3層拓撲結構組成，最低下的訪問層由物理主機構成，主機由機架頂層ToR交換機連接。中間層為聚合層，主機集群通過聚合交換機AS連接在不同的模塊中。最高層為核心層，通過AS和核心交換機的安全連接至互聯網。

圖1 系統模型

SARMS體系將云資源管理問題劃分為跨層的多代理模型，每個代理求解一個子問題。因此，可將其視為多代理的分布式資源管理系統。系統一共由4類代理構成。在核心層，全局代理GAs接收用戶的虛擬機請求，并將其派發至聚合層中的不同模塊代理MAs。每個MA根據來自于CAs的接收信息(包括集群中已經利用和總體資源能力)將虛擬機VM請求分派至集群代理CAs。每個CA接收來自于MA的請求并分配請求至集群的本地代理LAs。同時，數據中心內為了降低SLA違例和降低能耗，需要周期性運行虛擬機部署優化算法。每個LA監測一臺主機，根據自適應利用率閾值AUT機制發現該主機的超載或非超載狀態，并將其報告至集群代理CAs。LAs、CAs和MAs的數量則分別對應于主機、ToRs和CSs的數量。

3 自適應虛擬機部署算法設計

3.1 假設條件

數據中心內，每臺主機PMi擁有一個d維總能力矢量，表示為CPMi={C1,PMi,C2,PMi,…,Cd,PMi}， 其中，Cd,PMi表示PMi的d維資源總能力。每一維度對應一種物理資源，如：CPU能力、內存、網絡I/O和磁盤存儲。PMi利用的能力矢量表示為UPMi={U1,PMi,U2,PMi,…,Ud,PMi}， 其中，Ud,PMi表示PMi的d維資源已利用能力矢量。如：若3臺虛擬機VM部署在一臺主機上，則主機PM已利用的CPU能力為3臺虛擬機的CPU利用率之和。PMi的負載為每個個體資源d∈D的資源利用率Rd,PMi之和，表示為

LoadPMi=RCPU,PMi+Rmem,PMi

(1)

其中，Rd,PMi表示主機PMi已利用資源Ud,PMi與其總資源能力Cd,PMi之比，表示為

Rd,PMi=Ud,PMi/Cd,PMi

(2)

需要說明的是：云數據中心內，相比網絡資源和磁盤存儲資源，CPU資源和內存資源是相對更為受限的資源，因此本文僅考慮了這兩類資源的限制。但以現有模型將其擴展至另外兩種資源上，也是比較容易的，不會對虛擬機部署決策的性能表現產生反轉式影響。

虛擬機VMi的負載定義為

LoadVMi=RCPU,VMi+Rmem,VMi

(3)

式(3)表明，虛擬機上的負載為其請求的CPU和內存負載之和。相應地

Rd,VMi=Ud,VMi/Cd,VMi,d=CPU,mem

(4)

式中：Rd,VMi表示VMi請求的d維資源利用與VMi的d維資源消耗的比率，d指CPU或內存mem資源。式(4)表明，某一維度資源上的資源請求應為虛擬機上資源消耗與資源能力之比。

3.2 主機超載狀態發現

本地代理LAi利用資源利用率自適應閾值AUT機制發現每臺物理主機PM的狀態。若CPU或內存利用率超過自適應閾值，則將PMi考慮為超載集合Pover中的成員；否則，可將其視為非超載集合Pnonover中的一個成員。由于負載的動態變化，自適應閾值Td,PMi需要根據當前負載狀況在每個資源維度上進行調整。為了解決該問題，AUT利用Q學習方法在線從當前環境中學習經驗，并利用該經驗知識尋找每個閾值的自適應值。Q學習機制在對環境無先驗知識的前提下提供了一種自適應機制。在Q學習機制中，LAi首先觀測環境的當前狀態s，然后在當前時槽t中執行一個行為a。定義AUT機制中的狀態s為 (RCPU,PMi,Rmem,PMi)，RCPU,PMi和Rmem,PMi分別表示主機PMi的CPU利用率和內存利用率。

根據觀測狀態s，LAi選擇一個利用率閾值Td,PMi={0.5,0.6,0.7,0.8,0.9} 作為每個d維度資源上的行為a。由于在PM的利用率接近于100%時，可能導致SLA違例的風險，本文將資源利用率限制在90%以內。在Q學習過程的初始階段，LA執行一個確定的搜索行為，此時隨機選擇一個行為。然后，LAi根據其經驗(搜索)選擇一個行為。

在下一個時槽t+1的開始階段，環境行為轉換為一個新的狀態s’，LAi根據加強信號改進其知識。該信號可以反映行為發生后系統的成功或失效。本文將信號考慮為本地懲罰值、集群和模塊懲罰值之和。由于LAi執行行為a時需要支付懲罰值，LAi在學習期間需要最小化其平均長期懲罰值。每個懲罰值即為所設計系統每一層次中的目標函數，該目標函數決定了代理行為對于性能和功耗的綜合影響。

本地懲罰值LPi表示本地代理i決策行為對于主機PMi的功耗和性能影響。由于該懲罰值由LA計算，因此將其稱為本地懲罰值。由于將PM轉換為節能模式會降低其性能等級，故AUT需要在功耗和性能間做出均衡考慮。因此，引入一個多目標函數LPi(SLAV,POW)， 將功耗和性能均考慮在內，并利用該函數給出在RL上的懲罰值。性能需求可形式化為服務等級協議SLA，而主機PMi的SLA違例SLAVt+1,PMi即為時槽t+1時所有虛擬機的請求資源與實際分配的資源之差。時槽t+1時的本地懲罰值可定義為SLA違例SLAV與主機PMi的總功耗POW的線性函數

LPi(SLAV,POW)=SLAVt+1,PMi+β×POWt+1,PMi

(5)

其中，β為權重因子，代表功耗目標與性能目標間的關系。

集群懲罰值CPj,i從集群代理j發送至本地代理i。該懲罰值代表本地代理i的行為決策對于同一集群中其它主機PM的影響。因此，集群懲罰值是除了LPi之外的集群j的本地懲罰的均值。此外，本地代理i可以得到集群中總體的性能與功耗

(6)

其中，Y表示集群j中本地代理的數量。

CAj接收來自模塊代理z的模塊懲罰值MPz,j， 該懲罰值表示除了其集群懲罰值之外的模塊內的其它集群的懲罰值，定義為

(7)

其中，X表示模塊z中的集群代理的數量。

最后，LAi更新一個Q值Qt+1(s,a)， 該值通過總體懲罰值Pt+1,i與相應的行為-狀態對相聯系，即總體懲罰值為本地懲罰值LP、集群懲罰值CP和模塊懲罰值MP之和

Pt+1,i=LPi+CPj,i+MPz,j

(8)

(9)

其中，α表示學習率，取值空間為0至1之間，若取值為0，表明算法沒有發生學習行為，若取值為1，則表明僅僅利用了最近的信息來學習。折扣因子γ取值0至1之間，給出近期未來和遠期未來的懲罰權重。Qt+1(s,a) 表示狀態s時行為a導致的期望功耗。因此，本地代理在再次觀測到狀態s時將選擇使得Q值達到最小的行為。

3.3 虛擬機部署最優化算法過程

為了降低SLA違例和物理主機能耗，每個集群代理均需要周期性運行算法1如示的虛擬機部署最優化算法，該算法通過兩個階段創建虛擬機遷移計劃M。

在第一個階段中，即步驟(1)～步驟(22)，算法目標是從超載主機上遷移部分虛擬機以避免可能的SLA違例。遷移虛擬機時選擇的是擁有最小遷移時間的虛擬機優先遷移，遷移時間計算為分配至虛擬機的內存除以源主機與目標主機間的可用網絡帶寬。算法首先對源主機pso上的虛擬機按其利用的內存能力進行降序排列(所有網絡帶寬均設置為1 GBps)，即步驟(3)，然后，開始按序遷移虛擬機直到源主機PM仍被考慮為超載集合Pover中的一個成員，即步驟(4)～步驟(5)。為了尋找重新分配遷移虛擬機v的合適目標主機pde，算法優先考慮的是集群中非超載主機集合Pnonover，即步驟(7)～步驟(12)。若虛擬機和主機的整體資源利用率低于自適應閾值，則該PM被選擇為目標主機pde，即步驟(8)。若算法在同一集群內無法找到目標主機pde，則將該請求發送至模塊代理，在其它集群內尋找，即步驟(13)～步驟(15)。若活躍狀態的主機沒有足夠的資源部署遷移虛擬機v，則算法重新開啟一臺休眠主機進行部署。最后，新的虛擬機部署被添加至遷移計劃M1中，即步驟(16)。遷移計劃是一個三元組集合，表示為 (pso;v;pde)，pso表示源主機，v表示遷移的虛擬機，pde表示目標主機。步驟(17)對源主機和目標主機的資源利用率進行更新。

在第二個階段中，即步驟(23)～步驟(45)，算法目標是合并非超載主機上的虛擬機。首先基于當前負載按降序排列非超載主機集合Pnonover內的主機，即步驟(24)。然后，從列表中的最低載主機開始遍歷，將其考慮為一個源主機pso，即步驟(25)～步驟(26)。算法嘗試遷移其上的所有虛擬機，以便釋放源主機pso。為了選擇從pso上優先需要遷移的虛擬機，算法根據其負載按降序對pso上的虛擬機進行排列，即步驟(27)。算法從集合Pnonover中的第一個主機(負載最重主機)開始遍歷尋找目標主機pde，即步驟(30)。若第一個主機不滿足，則選擇第二個主機，依此類推。算法選擇的目標主機pde需要在考慮閾值的情況下擁有足夠的虛擬機請求的資源能力，即步驟(31)。最后，新的虛擬機部署被添加至遷移計劃M2中，即步驟(32)。步驟(33)對源主機和目標主機的已利用資源能力進行更新，以反映出新的虛擬機部署結果。變量success定義為檢測是否來自于源主機pso上的所有虛擬機能夠完成遷移。若有一個虛擬機無法完成遷移，則全部不遷移。此時，success=false，算法將移除遷移計劃中的所有三元組，并恢復源主機和目標主機的資源能力，即步驟(39)～步驟(41)。否則，在其上的所有虛擬機遷移后，空閑源主機pso將轉換為休眠狀態，即步驟(42)～步驟(44)。算法的輸出為遷移計劃M，包括了在第一階段和第二階段中生成的所有遷移三元組，即步驟(46)～步驟(47)。最后，集群代理根據遷移計劃M將遷移指令發送至集群的本地代理，執行具體的虛擬機遷移。

算法1： 虛擬機部署最優化算法

(1)M1=null

(2)forpso∈Poverdo

(3)Vm←sort VMs onPMpsoin ascending order ofUmem,v

(4) forv∈Vmdo

(5) ifpso∈Poverthen

(6)pde=null

(7) forp∈Pnonoverdo

(8) if (RCPU,p+RCPU,v≤TCPU,p)&(Rmem,p+Rmem,v≤Tmem,p)

(9)pde=p

(10) break

(11) end if

(12) end for

(13) ifpde=null then

(14) send a request to the module agent to findpde

(15) end if

(16)M1=M1∪{(pso,v,pde)}

(17) updateRpsoandRpde

(18) else

(19) break

(20) end if

(21) end for

(22)end for

(23)M2=null

(24)sortPnonoverin descending order ofLoadp

(25)fori=|Pnonover| to 1 do

(26)pso=Pnonover[i]

(27)Vm←sort VMs onPMpsoin descending order ofLoadv

(28) forv∈Vmdo

(29)success=false

(30) forpde∈Pnonover-psodo

(31) if(RCPU,pde+RCPU,v≤TCPU,pde)&(Rmem,pde+Rmem,v≤Tmem,pde)

(32)M2=M2∪{(pso,v,pde)}

(33) updateRpsoandRpde

(34)success=true

(35) break

(36) end if

(37) end for

(38) end for

(39) ifsuccess=falsethen

(40)M2=null

(41) recoverRpsoandRpde

(42) else

(43) switchpsoto the sleep mode

(44) end if

(45)end for

(46)M=M1∪M2

(47)returnM

3.4 虛擬機分配

虛擬機分配需在SAMRS中的3層結構中得以求解，最低下的訪問層由物理主機構成，主機由機架頂層ToR交換機連接；中間層為聚合層，主機集群通過聚合交換機AS連接在不同的模塊中；最高層為核心層，通過AS和核心交換機的安全連接至互聯網在核心層和聚合層。具體分配流程是：首先，全局代理和模塊代理通過運行BFD算法先將虛擬機分配至模塊，然后分配虛擬機至集群。BFD算法根據當前的虛擬機負載狀況的降序對虛擬機進行排列，其目標是：如果模塊或集群擁有足夠資源能力分配至虛擬機，則將負載最輕的虛擬機分配至負載最重的模塊或集群中。最后，在訪問層，如果某主機擁有足夠的CPU和內存能力在當前自適應閾值的前提下部署虛擬機，同集群代理會將每個虛擬機分配至該主機上，即算法1中的步驟(8)。因此，這樣可以限制虛擬機請求的資源量在自適應度閾值以內，進而最小化可能的性能下降。

4 仿真實驗

4.1 測試負載說明

利用兩種現實負載流測試虛擬機部署優化算法，包括：Google集群數據GCD[8]和PlanetLab數據[9]。GCD提供的是集群系統中某一個月內的負載流數據。該負載流涉及12 000 臺異構主機上的650 k個任務。每個任務代表一個Linux程序，其中包含了在CPU(內核占用秒數)、內存、磁盤存儲空間等資源上的請求。每類資源的利用以5 min作為時間間隔進行收集。利用任務ID對任務進行標識，CPU和內存屬性分別考慮為CPU速率和內存量的利用。PlanetLab數據為CoMon工程的一部分，該工程中，CPU和內存利用數據從數以千計的虛擬機中每5 min收集一次。該負載流是一種典型的IaaS云環境負載流，如典型的Amazon EC2。GCD和PlanetLab中虛擬機的負載所對應的CPU和內存占用屬性見表1。

表1 測試負載流屬性

4.2 仿真環境搭建

為了測試算法效率，在云仿真平臺CloudSim[10]中進行仿真實驗。表2給出了針對兩種測試負載流的相關參數配置。模擬云數據中心由若干臺異構物理主機構成，一半主機配置為HP ProLiant ML110 G4服務器，每個內核1860 MIPS，另一個主機配置為HP ProLiant ML110 G5服務器，每個內核2660 MIPS。每個主機配置兩個內核，4 GB 內存和1 GBps的網絡帶寬。虛擬機實例的CPU和內存屬性參考Amazon EC2在平臺中設置，即：High-CPU中等實例(2500 MIPS,0.85 GB)，越大實例(2000 MIPS,3.75 GB)，小型實例(1000 MIPS,1.7 GB)，微型實例(500 MIPS,613 MB)。α和γ(Q學習因子)分別設置為0.5和0.8。

表2 仿真環境參數配置

4.3 評估指標

(1)SLA違例SLAV指標。SLAV是一種獨立的負載指標，用于評估虛擬機部署中SLA的交付情況。SLAV包括主機超載導致的SLA違例SLAVO和由于遷移導致的SLA違例SLAVM。對于云環境中的虛擬機合并問題而言，兩種SLA違例具有同等的重要性，因此，綜合的SLA違例指標可考慮為兩個參數的乘積，表示為

SLAV=SLAVO×SLAVM

(10)

其中，SLAVO表示活躍主機經歷CPU利用率100%所占的時間比例，表示為

(11)

其中，M表示主機數量，Tsi表示主機i經歷的CPU利用率100%(導致SLA違例)的總時間，Tai表示主機i活躍狀態的總時間。

SLAVM表示由遷移導致的虛擬機性能下降，度量為

(12)

其中，N表示虛擬機數量，Cdj表示由于遷移導致的虛擬機j性能下降的估算。仿真實驗中，該估算值一般設為虛擬機j在所有遷移過程中以MIPS計算的CPU占用的10%，Crj表示整個周期中虛擬機j的總CPU請求量。

(2)能耗指標。該指標表示數據中心中物理主機執行負載消耗的總體能耗。主機能耗取決于CPU、內存、存儲及網絡帶寬的利用率。研究表明，相比其它資源類型，CPU消耗了最多能源。因此，簡化能耗模型后，主機能耗可表示為其CPU利用率的關系式。實驗中根據SPECpower實驗床中現實的功耗數據。表3給出了在不同的負載條件下兩類主機HP G4和HP G5的功耗情況，從表中可以看出，低載主機轉換為休眠后可降低能耗。

表3 不同負載條件下主機的功耗/W

(3)虛擬機遷移量。在線虛擬機遷移涉及在源主機上的CPU處理、源和目標主機間的鏈路帶寬以及遷移時的服務停機、遷移時間等多重代價，因此，虛擬機合并過程中需要最小化虛擬機遷移量。

4.4 對比算法

(1)HiVM算法[11]：該算法利用了基于虛擬機管理方法的利用率預測方法，根據當前和未來的虛擬機資源利用優化了虛擬機部署方案。

(2)MADC算法[12]：基于多代理的動態虛擬機合并算法，該算法是一種雙層結構的多代理模型。

(3)3種自適應利用率閾值算法[5]：該類算法首先根據統計學方法動態調整CPU利用率上限閾值，相關統計學方法包括：絕對中位差法MAD、四分位差法IQR和局部回歸法LR。通過以上統計學方法確定上限閾值后，若主機的CPU利用率超過此上限值，則虛擬機部署優化根據負載均衡的原則重新進行虛擬機分配。通過與該算法的比較，可以顯示本文設計的AUT所使用的Q學習自適應機制與經典統計學方法的性能優勢。

(4)靜態閾值算法THR[7]：該算法設置CPU閾值為固定值，如80%，當主機當前利用率超過總能力的80%時，則需要從主機上遷移虛擬機。通過與算法的比較，可以顯示出自適應閾值設置的優勢。

4.5 結果分析

圖2給出了利用GCD數據流測試時7種算法在SLAV、能耗以及虛擬機遷移量的性能表現。可以看到，比較另外6種算法，本文可以有效降低SLA違例，這是因為本文設計的虛擬機部署優化算法可以通過AUT機制將主機利用率維持在自適應閾值以內。此外，比較HiVM、MADC、LR、MAD、IQR和THR這6種算法，本文算法可以分別降低13.7%、25.6%、43.3%、59.1%、66.3%和69.4%的能耗，這是由于本文算法可以最小化非超載主機的數量。同時，圖2(c)顯示出本文算法可以最小化虛擬機遷移量。

圖2 GCD負載流的測試結果

圖3(a)顯示了利用PlanetLab負載流時算法得到的SLAV指標情況，結果表明，本文得到了比基準算法更小的SLA違例，這是由于該算法在CPU或內存利用率超過自適應閾值時會從主機上遷移部分虛擬機預防SLA違例。圖3(b)顯示本文算法比其它算法也節省了更多的能耗，這是由于算法可以通過運行算法的第二階段將虛擬機合并至最小數量的非超載主機上。同時，本文算法也可以有效降低虛擬機遷移量，避免了過多非必要的虛擬機遷移。

圖3 PlanetLab負載流的測試結果

5 結束語

提出一種基于Q學習機制的自適應虛擬機部署算法。算法利用Q學習機制在無需先驗知識的前提下，可以自適應生成資源利用率閾值，根據動態自適應閾值動態地對主機超載狀態作出決策，以此判斷是否進行虛擬機遷移。通過兩種現實負載流數據對算法進行了實驗分析。結果表明，與另外6種典型虛擬機部署算法相比，該算法不僅可以降低主機能耗，還可以同步減小虛擬機遷移量和SLA違例率。