基于資源特征匹配的虛擬機放置算法

馮 偉，陳靜怡，吳 杰

（復旦大學 計算機科學技術學院，上海200433）

0 引 言

目前，數據中心通過虛擬化技術使虛擬機共享物理機資源池的方式，以物理機服務單元承載虛擬機，同時以虛擬機服務單元來承載應用服務。對于數據中心中物理資源（如服務器，網絡，存儲等）和虛擬資源的大量聚集，如何通過虛擬資源的調度管理改變傳統IT的資源提供與管理模式，實現IT資源的集約共享，提高資源整體利用率，降低服務成本，并保證服務質量是當前迫切需要解決及改善的重要問題。目前亟需解決的問題突出表現在：

（1）傳統的虛擬機資源分配與調度通常未能做到面向應用的動態自適應［1］。典型的Internet應用的訪問通常是負載隨時間動態變化的，如何根據應用模式及負載，結合虛擬資源特征，在進行虛擬機資源的多目標優化，目前尚未很好的解決；

（2）為實現應用負載自適應的需求，將導致虛擬機放置問題［2］的復雜化。目前學術界和工業界主要關注虛擬機與物理機之間的容量映射［3］（NP難問題），卻未考慮虛擬機承載的應用資源消耗類型、用戶對應用的訪問模式以及虛擬機應用負載匹配關系等因素；

（3）虛擬機遷移策略［4］：目前學術界關于虛擬機遷移的研究主要考慮獨占性資源如CPU、內存等的利用率，以及能耗，卻沒有綜合考慮共享性資源I/O狀況以及未考慮虛擬機具有本地動態伸縮能力。因此，在新的情況下，綜合考慮各方面因素，需要確定虛擬機需要遷移的時機和策略，以確保遷移能具有較長時間的穩定。

上述問題的解決將會對數據中心的虛擬資源調度管理［5］重要意義。而以上3個問題產生的根本原因是由于虛擬機的資源消耗特征與物理機資源配置不匹配造成的。為解決該問題，本篇論文論述了一種新的虛擬機放置算法：基于資源消耗特征匹配的虛擬機放置算法。算法綜合考慮虛擬機資源消耗特征、應用訪問模式以及虛擬機資源配置與負載匹配關系等因素，能夠有效地對虛擬機進行優化放置，同時大幅提高了物理機資源整體利用率。

1 相關研究

傳統數據中心提供以物理機為基本單位的服務器租賃服務，由于資源分配的粗粒度，造成數據中心資源利用率低，能耗較高，同時服務能力無法動態擴展。

由于虛擬化技術的廣泛應用，虛擬機正逐步取代物理機成為數據中心的基本服務單元。根據虛擬機具備的遷移以及本地動態伸縮的不同特性，可以提供不同形式的服務以提高資源使用率，降低能耗并保證服務質量。

以亞馬遜EC2為代表的傳統彈性云服務提供服務能力固定、不可遷移的虛擬機服務，采用以虛擬機為單位、按需增減開啟運行的虛擬機數量，進行負載自適應。與傳統數據中心以物理機作為租賃服務單位相比，能夠提供較小粒度的資源分配，將有限的物理資源分配給更多的虛擬機以容納更多用戶請求；同時，數據中心資源整體利用率有所提高。文獻 ［6］，研究了虛擬化數據中心的網絡特征以及虛擬機的網絡性能。文獻 ［7］通過研究虛擬機放置和遷移策略，使用流量感知的虛擬機放置算法，將具有通信關聯的虛擬機遷移到同一或網絡位置相近的物理機上，降低數據中心內部通信量，提高網絡可擴展性。

文獻 ［8－10］等研究了粒度較為精細的動態虛擬機資源伸縮模型，通過本地資源的動態伸縮來適應負載變化，以達到提高可擴展性和保證服務質量的目的。另外文獻［11］提出了一種應用無關的負載均衡機制，通過實時監控物理機及虛擬機的各項資源使用情況，結合應用的當前負載并預測其變化趨勢，及時調整物理資源到虛擬資源的重新分配。文獻 ［12］研究的資源控制系統能夠自動的適應應用負載動態變化，并獲取應用程序性能和資源分配值之間的復雜關系，按需調整分配資源量，在保證服務質量的同時提高數據中心的可擴展性。

未來數據中心的虛擬機服務單元將具備動態遷移和伸縮能力［13］，需要對虛擬資源進行自適應調度和管理以適應應用負載的動態變化。究其核心問題依然是虛擬機的優化放置問題，本文將從虛擬機的負載—資源—服務性能模型出發，研究虛擬機資源特征表達和虛擬機特征匹配算法。

2 基于資源特征匹配的虛擬機放置算法

本文首先建立應用負載—資源消耗—服務性能的關系模型，并根據三者的內在聯系，采用統計和回歸方法建立基于虛擬機應用性能表現和訪問模式的資源特征表達。進而，虛擬機放置算法在資源特征表達的基礎上，根據物理機的資源配置，選擇關聯與特征匹配的虛擬機集合，提高資源的整體利用率。

2.1 虛擬機性能特征模型

應用負載的變化將會影響數據中心中服務單元的內部網絡帶寬消耗、能耗、CPU和內存利用率的變化，而服務單元消耗的內部網絡帶寬、CPU和內存利用率的變化又將影響最終的服務性能。本節首先在數據中心的虛擬機服務單元層面對應用負載、服務單元資源與服務性能建立關系模型，如圖1所示。

圖1 應用負載—資源消耗—服務性能的關系模型

負載—資源—服務性能的關系模型的關鍵問題是如何根據虛擬機的CPU利用率、內存使用量和占用的內部網絡帶寬標識虛擬機應用的性能特征 （為簡化模型，本文暫未考慮能耗的影響）。由于CPU和內存是虛擬機獨占性資源，內部網絡帶寬是一臺物理機上所有虛擬機的共享性資源，而且3個影響因素的量綱均不不同。為統一表征對虛擬機應用性能的影響，本節通過采用各影響因素的變化率來表征虛擬機應用響應性能的變化率進行歸一化處理。本節采用統計和線性回歸的方法建立虛擬機性能敏感因素的特征表達，描述如下

式中：Rate（VM）——應用請求數量每變化△ （Request）時虛擬機響應時間的變化率；C——常數；ki——影響系數，用以表征敏感程度；Rate（CPU）、Rate（MEM）、Rate（TRA）——應用請求數量每變化△ （Request）時，虛擬機CPU使用量與內存使用量以及內部網絡帶寬的變化率，且Rate（TRA）指虛擬機所在物理機的帶寬消耗變化率 （包括虛擬機響應請求所消耗內部網絡帶寬的變化率和同一物理機上其它虛擬機消耗內部網絡帶寬的變化率）。

同時，本節采用標準差分析方法表達虛擬機資源消耗特征與物理機資源配置的匹配程度，匹配度公式定義如下

式中：▽i——虛擬機m性能敏感因素要求的標準系數，根據虛擬機實際運行數據得知；Sm——影響系數標準差，用以表示各類虛擬資源消耗與物理機資源配置的匹配程度；Ω（m，n）——虛擬機n對虛擬機m消耗各類虛擬資源的優化程度。

負載—資源—服務性能的關系模型能夠根據負載、資源和服務性能之間的影響關系，定量確定各因素的影響程度，為虛擬機資源特征匹配算法的有效性提供評判依據。

2.2 基于訪問模式的虛擬機資源特征表達

在虛擬機具有動態伸縮能力和遷移特性情況下，虛擬機已經不再是固定的資源配置，而是動態適應應用負載變化、與時間序列相關的資源配置序列集合。因此，本節將根據虛擬機的資源配置序列來關聯組合特征匹配的虛擬機，建立基于訪問模式的虛擬機資源特征表達模型。為簡化模型，本模型暫不考慮能耗因素，把CPU、內存資源和實時流量作為關鍵指標，描述如下：VM （APPi）＝＜（WLD1，CPU1，MEM1，TRA1），...， （WLDT，CPUT，MEMT，TRAT）＞；其中VM （APPi）即 （WLDi，CPUi，MEMi，TRAi）表示在ti時間點，應用APPi的負載請求為APPi時，消耗的計算資源、內存資源量以及內部網絡帶寬；T （APPi）＝ ＜t1，t2，…，tn＞表示應用APPi的時間序列。確定每個虛擬機基于訪問模式的資源特征表達具體過程如下：

（1）對VMi的負載請求、資源使用和能耗情況進行監測，確定負載的訪問周期T和變化關系 WLDi＝fi（t＋T），以及資源消耗變化關系RESOURCE （CPUi，MEMi，TRAi）＝hi（t＋T），并將每個訪問周期T內的資源需求＜（WLD1，CPU1， MEM1，TRA1）， …，（WLDT，CPUT，MEMT，TRAT）＞作為一組樣本；

（2）對每個虛擬機維護一定數量的資源需求樣本信息，若樣本信息超過樣本容量時則根據各樣本的預測誤差大小對樣本更新維護；

（3）處理樣本數據，確定虛擬機基于訪問模式的資源特征表達TimeResourFeature（VMi）。

2.3 虛擬機資源特征匹配算法

虛擬機資源特征匹配算法建立在虛擬機資源特征表達的基礎之上，選擇同時滿足性能特征和應用訪問特征資源匹配條件虛擬機集合進行關聯，進而有效匹配物理機的資源配置。

算法將所有數據中心的物理機PMSET邏輯劃分為n個物理機集合，其中物理機集合PMSETi中包含的物理機數量為pi；根據物理機的劃分，將數據中心的所有虛擬機VMSET劃分為相應的虛擬機集合，虛擬機集合VMSETi中包含的虛擬機數量為vi。物理機集合關系表述如下

式中：PMSET（i，j）——物理機集合 PMSETi中的第j臺物理機。虛擬機集合關系表述如下

式中：VMSETi——PMSETi中所有的虛擬機集合，VMSET（i，k）——虛擬機集合 VMSETi中的第k個虛擬機。具體算法流程如下：

Match （PMSETi，VMSETi）//特征匹配算法

while（PMSET）｛//遍歷物理機集合

foreach （PMSET（i，j）） ｛//隨機選擇某一虛擬機對物理機初始化

VMSET（i，j，k）＝ RandomSelect （VMSET）；

//將物理機的可使用資源去除虛擬機需要的資源得到空閑資源IdleResource （PMSET（i，j）） ＝InitResource （PMSET（i，j））－Resource （VMSET（i，j，k））；

while （IdleResource （PMSET（i，j）） ＞ MinResource（VMSETi））｛

//尋找同時滿足兩個特征匹配條件的虛擬機組合

if（KeyFactorMatch （VMSET（i，j，k），VMSETi－ VMSET（i，j，k）））

selectVMs＝ TimeFeatureMatch （VMSET（i，j，k），VMSETi－ VMSET（i，j，k））

//調整物理機空閑資源

IdleResource （PMSET（i，j）） ＝ IdleResource （PMSET（i，j））－Resource （selectVMs）；

｝//end while

｝//end foreach

｝//end while

其中，TimeFeatureMatch（）表示基于訪問模式的資源特征匹配條件，KeyFactorMatch（）表示性能敏感因素的特征匹配條件。特征匹配算法 Match（PMSETi，VMSETi）的平均時間復雜度為O（·pi），將VMSETi經過排序優化后可達到O（K·vi·pi）其中K為常數；算法可對多個物理機集合同時進行匹配，進而可提高匹配效率。

3 實驗設計及結果分析

實驗目的是根據監控資源實際運行情況，利用本文描述的資源消耗特征模型對應用所使用的資源建模，并驗證基于資源消耗特征匹配的虛擬機放置算法有效性。

實驗環境采用CentOS系統，并且部署Xen虛擬化環境，在Xen的Domain0上發布虛擬機作為虛擬化資源；同時采用SNMP協議獲得CPU利用率、內存使用量以及占用的內部網絡帶寬等資源實時運行數據，使用Jmeter獲得不同請求數量下的虛擬機響應時間RTT。實驗環境包括3臺物理機，其中一臺作為SNMP監控服務器，其余兩臺部署虛擬機。

3.1 虛擬化環境下內部網絡帶寬分配機制

由于內部網絡作為多個虛擬機的共享資源，需要首先研究虛擬化環境下的網絡帶寬分配機制。在試驗環境的某一臺物理機上部署3臺同樣配置的虛擬機VM1、VM2和VM3。在0s時，VM1向VM2，VM2向VM3同時進行文件傳輸；40s時VM3向VM1進行文件傳輸；100s時停止VM1向VM2的文件傳輸，實驗結果如圖2所示。

圖2 Xen虛擬化環境下的內部網絡帶寬使用情況

根據實驗結果分析得知Xen虛擬化環境下的內部上行網絡總帶寬可達到11MB/s，網絡帶寬分配采用可搶占式的平均共享機制。因此在虛擬化環境下，同一物理機上不同用戶的虛擬機將會相互影響，這種內部網絡帶寬分配機制在將來的理論研究和實踐中需要進行改進。

3.2 虛擬機性能影響因素特征表達

在兩臺虛擬機VM1和VM2上分別部署兩種應用：SNS1和SNS2，其中SNS1主要處理HTTP請求，SNS2主要處理檢索請求；同時為簡化處理數據，本文設置二者的應用訪問周期相同，包含請求量遞增到最大請求量的全部過程。根據監控得到的實際運行數據，本文在實驗環境中以虛擬機性能敏感因素的影響系數均值作為物理機資源的配置要求標準。VM1性能特征表達的回歸分析結果見表1。

表1 VM1性能特征表達的回歸分析

得到SNS1應用的虛擬機性能影響因素特征表達為：Rate（VM1）＝2.11－0.31·Rate （CPU）－0.04·Rate（MEM）－0.12·Rate（TRA）；虛擬機 VM2性能特征表達的回歸分析結果見表2。

表2 VM2性能特征表達的回歸分析

得到SNS2應用的虛擬機性能影響因素特征表達為：Rate（VM2）＝2.29－0.33·Rate （CPU）－0.55·Rate（MEM）－0.30·Rate（TRA）；根據公式計算得到，影響系數標準差S1＝0.337672，S2＝0.094403，即 VM2的資源消耗均衡程度優于VM1。

3.3 算法性能分析

模擬虛擬機應用的請求變化，根據兩種應用訪問模式的虛擬機資源特征表達關系進行特征匹配，匹配后兩虛擬機的綜合性能特征表達見表3。

表3 VM1和VM2綜合性能特征表達的回歸分析

得到SNS1和SNS2兩種應用的綜合虛擬機性能影響因素特征表達為：Rate（VM12）＝2.44－0.32·Rate（CPU）－0.25·Rate（MEM）－0.29·Rate（TRA）；根據公式計算得到，影響系數標準差 S12＝0.029427。優化度為Ω（s12，s1）＝11.48，Ω（s12，s2）＝3.21，即將虛擬機 VM1和 VM2關聯在同一物理機上時，與將兩虛擬機分別放置在不同的物理機上時相比，其消耗資源的優化程度將顯著提高。

在本實驗環境中，一臺物理機最多可承載4臺VM1或VM2類型的虛擬機。首先在一臺物理機上承載4臺VM1虛擬機，當應用請求使虛擬機的CPU利用率達到90%以上，即CPU資源已經充分利用時，其內存使用率僅為37%。一個訪問周期內，虛擬機VM1的資源特征如圖3所示。

圖3 虛擬機VM1的資源利用率

根據實驗的設計，可以VM1實驗結果等效為物理機的資源使用情況，即物理機的CPU資源充分利用時，其內存資源處于低效利用狀態，造成很大浪費。

經過算法關聯后，一臺物理機承載2臺VM1和2臺VM2虛擬機，當應用請求使虛擬機的CPU利用率達到90%以上，即CPU資源已經充分利用時，其內存使用率為76%，其中VM1和VM2資源綜合利用率為二者的加權平均值。一個訪問周期內，虛擬機VM1和VM2的資源綜合特征如圖4所示。

圖4 虛擬機VM1和VM2資源綜合利用率

同樣地，將VM1和VM2的綜合實驗結果等效為物理機的資源使用情況，即當物理機的CPU資源充分利用時（90%以上），其內存利用率由37%提高到76%，資源利用率得到顯著提高，進而驗證了算法的有效性。

4 結束語

本文在進行虛擬機的優化放置時，不再將虛擬機與物理機的映射這個NP難問題作為核心來解決，而是基于監控和統計對虛擬機資源消耗特征進行參數化表達，并將特征匹配的虛擬機進行關聯，使得每個物理服務單元的資源得到充分有效的利用。同時算法是在監控和統計分析的基礎上進行的，因此可以對，避免了虛擬機不必要的遷移。經過實驗驗證，虛擬機放置算法VMP－RUFM通過調整物理機上各虛擬機性能影響因素的影響系數以適應物理機的資源配置，達到了提高物理資源整體利用率的目的。

［1］Gupta R.A two stage heuristic algorithm for solving the server consolidation problem with item－item and bin－item incompatibility constraints［C］.IEEE International Conference on Services Computing，2008：39－46.

［2］Chris Hyser，Bret Mckee，Rob Gardner，et al.Autonomic virtual machine placement in the data center ［R］.HP Labs Technical Report，2007.

［3］Swarna Mylavarapu，Vijay Sukthankar，Pradipta Banerjee.An optimized capacity planning approach for virtual infrastructure exhibiting stochastic workload ［C］.Proceedings of the ACM Symposium on Applied Computing.New York，NY，USA：ACM，2010.

［4］Park J，Kim J，Choi H，et al.Virtual machine migration in selfmanaging virtualized server environments［C］.Proc Int Conf on Advanced Communication Technology，2009：2077－2083.

［5］Nie L，Xu Z.An adaptive scheduling mechanism for elastic grid computing ［C］.Proceedings of the Fifth International Conference on Semantics，Knowledge and Grid.Washington，DC，USA：IEEE Computer Society，2009：184－191.

［6］Wang Guohui，Eugene Ng T S.The impact of virtualization on network performance of Amazon EC2data center ［C］.San Diego，California，USA：Proceedings of the 29th conference on Information communications，2010：1163－1171.

［7］Vasileios Pappas，Li Zhang.Improving the scalability of data center networks with traffic－aware virtual machine ［C］.San Diego，CA：Proceedings of IEEE INFOCOM，2010：1－9.

［8］Timothy Wood，Prashant Shenoy，Arun Venkataramani，et al.Black－box and gray－box resource management for virtual machines ［J］.Computer Networks：The International Journal of Computer and Telecommunications Networking，2009：2923－2938.

［9］SONG Ying，LI Yaqiong.A service－oriented priority－based resource scheduling scheme for virtualized utility computing ［C］.High Performance Computing Conference，2008：186－193.

［10］SONG Ying，WANG Hui，LI Yaqiong，et al.Multi－tiered on－demand resource scheduling for VM－based data center，international symposium on cluster［C］.Cloud and Grid Computing，2009：148－155.

［11］ZHOU Wenyu，YANG Shoubao，FANG Jun，et al.A load balancing scheme for virtual machine cluster based on dynamic resource allocation ［C］.Barcelona，Spain：9th International Conference on Grid and Cooperative Computing，2010：87－98.

［12］PradeepPadala，Hou Kai－Yuan，Kang G Shin，et al.Automated control of multiple virtualized resources ［C］.Proceedings of the 4th ACM European Conference on Computer Systems，2009：13－26.

［13］Xu Jing，José A B Fortes.Multi－objective virtual machine placement in virtualized data center environments［J］.IEEE/ACM International Conference on Green Computing and Communications ＆ IEEE/ACM International Conference on Cyber，Physical and Social Computing，2010：179－188.