文超，胡曉勤（四川大學計算機學院，成都　610065）

基于OpenStack的虛擬機初始放置算法研究

文超，胡曉勤
（四川大學計算機學院，成都610065）

0　引言

近些年來，云計算已經(jīng)成為一種流行的計算模式，它一般用來在互聯(lián)網(wǎng)上托管虛擬機和提供服務(wù)[1]。云計算最大的貢獻在于它改變了硬件物理資源的分配方式，可以根據(jù)用戶的需求彈性的分配計算、存儲、網(wǎng)絡(luò)等資源。云計算主要分為三種服務(wù)類型：基礎(chǔ)設(shè)施即服務(wù)（IaaS），平臺即服務(wù)（PaaS），和軟件即服務(wù)（SaaS）。OpenStack是一種開源的IaaS云計算平臺，是目前最流行的開源云計算平臺，主要將物理資源CPU、內(nèi)存、磁盤等硬件設(shè)施虛擬化為資源池提供給用戶分配使用。國內(nèi)也已經(jīng)有大型公司如新浪、中國移動等搭建使用OpenStack云平臺并進行二次開發(fā)，同時，由于其開源性，大大減少了中小企業(yè)云平臺建設(shè)成本，使得Open-Stack得到了廣泛的推廣，也讓云計算真正的走進了企業(yè)。

隨著云計算突飛猛進的發(fā)展，云平臺下基礎(chǔ)設(shè)施的規(guī)模也不斷擴大。大到數(shù)據(jù)中心成千上萬的物理節(jié)點部署在云計算平臺中，小到幾十上百的物理節(jié)點在中小企業(yè)中部署。這些都是充分利用云計算來提高物理資源的利用率，但是隨著雖然物理節(jié)點的增多，不合理的虛擬機放置算法卻會降低整個平臺的資源利用率。虛擬機的放置是指在初始創(chuàng)建虛擬機的時候，將所要創(chuàng)建的虛擬機映射到某一物理節(jié)點上。如果虛擬機放置到不合適的物理節(jié)點上，將會造成資源浪費的問題。例如要放置的物理機的CPU資源很充足，內(nèi)存資源較少，而創(chuàng)建的虛擬機卻是需求CPU很少，需求內(nèi)存很多的情況，物理機的CPU和內(nèi)存的利用率的差距進一步擴大，這樣會造成物理機內(nèi)存剩余資源不足以創(chuàng)建任何虛擬機時，但CPU資源卻有很大的剩余，從而浪費了CPU資源。

由此可以看出虛擬機的放置問題是云基礎(chǔ)設(shè)施中改善資源利用率的一個重要途徑。對于中小企業(yè)，物理資源有限，如何高效的利用資源，提高資源的利用率就顯得格外重要。

現(xiàn)有的對于云計算虛擬機初始化放置的研究主要分為傳統(tǒng)啟發(fā)式方法如首次匹配算法、最佳匹配算法和生物智能啟發(fā)式算法如遺傳算法、蟻群算法[2]。文獻[3]建立了一種基于分組遺傳基因的算法,文獻[4]建立了基于性能匹配的蟻群算法。以上算法都能在一定應(yīng)用條件下表現(xiàn)出較好的性能，但是在OpenStack這種沒有環(huán)境限制的情況下會有不穩(wěn)定的性能，所以本文在構(gòu)建了OpenStack私有云平臺后[5]，深入研究了虛擬機創(chuàng)建流程，分析負責虛擬機放置的模塊，分析該模塊使用的虛擬機調(diào)度算法原理以及不足，提出了基于交叉裝填思想的OpenStack虛擬機放置算法。

1　OpenStack虛擬機放置算法

1.1OpenStack 虛擬機創(chuàng)建流程

創(chuàng)建虛擬機的過程如圖1所示，其中nova-sched-uler負責完成虛擬機調(diào)度的功能，即通過放置算法選擇物理機，完成虛擬機到物理機的映射。

圖1　虛擬機創(chuàng)建內(nèi)部流程圖

1.2OpenStack 放置算法

nova-scheduler中內(nèi)置了2個虛擬機放置算法：

（1）隨機放置算法，在物理機當前可用的CPU、內(nèi)存、磁盤空間資源滿足虛擬機需求時，隨機選擇1個物理機進行放置。該算法默認不使用，沒有實用價值。

（2）過濾稱重放置算法，如圖2所示。

該放置算法主要分為2個步驟，首先根據(jù)物理機可用資源與虛擬機資源請求以及配置文件和系統(tǒng)設(shè)置的一些條件篩選出滿足條件的物理機，然后對篩選出來的物理機根據(jù)剩余可用內(nèi)存指標計算權(quán)重，根據(jù)權(quán)重排序，最后選擇的是剩余可用內(nèi)存最多物理機進行放置。

1.3OpenStack 虛擬機放置算法的不足

OpenStack云平臺在默認情況鍵下只根據(jù)剩余可用內(nèi)存大小做權(quán)重計算，也就是說物理主機擁有的剩余內(nèi)存資源越多，被選中為放置的物理機的幾率越大。

這種算法實現(xiàn)非常簡單，復(fù)雜度低，很容易理解，但是這種單一根據(jù)內(nèi)存來排序并決定物理機選中的方法并不適合在實際的云平臺環(huán)境中使用。另外，在針對內(nèi)存進行虛擬機放置時，總是選擇剩余內(nèi)存多的物理機，這樣整體上各個物理機的內(nèi)存利用率都不高。而在實際的生產(chǎn)環(huán)境中，需要權(quán)衡各種資源的利用率，盡可能多的提高CPU、內(nèi)存、磁盤、網(wǎng)絡(luò)帶寬四種主要資源的利用率，避免大量資源的浪費。

圖2　過濾稱重分配過程圖

2　OpenStack虛擬機交叉裝填放置算法

2.1虛擬機放置的數(shù)學模型

虛擬機在物理機中的放置問題，是典型的裝箱問題（Bin Packing Problem，BPP）[6]。其數(shù)學模型可以描述為：

云平臺中物理機集合表示為 P=（p1，p2，…，pn），虛擬機集合表示為 V=（v1，v2，…，vM）,其中n和m表示為物理機數(shù)目和虛擬機數(shù)目。假設(shè)一個物理機共有（1，2，…，h）中資源（例如CPU、內(nèi)存等），則1個物理機pi可以表示為pi=pi（si1，si2，si3，…，sih），s表示第i個物理機上資源的提供量，即剩余可用資源。同理一個虛擬機vj=可以表示為vj=（rJ1，rj2，rj3，…，rjh），r表示第j個虛擬機對資源的需求量。目標函數(shù)為云平臺物理機總資源利用率最高，即所使用的物理機數(shù)目最少，表示為：

約束條件為:

其中，約束式（2）保證了虛擬機各種資源的總需求量不會超過物理機提供的對應(yīng)資源總量，q是一個系統(tǒng)閾值，通常設(shè)置為0.9，該值是除去虛擬化的系統(tǒng)開銷后物理機可以提供的資源比例，即物理機資源的90%能夠提供給虛擬機分配；約束式（3）保證每一個虛擬機最多只能被放置到一個物理機上；約束式（4）和（5）是決策變量。

2.2基于交叉裝填的虛擬機放置算法

OpenStack虛擬機放置是一個四維向量的裝箱問題（四維資源：CPU、內(nèi)存、磁盤空間、網(wǎng)絡(luò)帶寬）。本文通過將該四維的裝箱問題轉(zhuǎn)化為一維裝箱問題來降低復(fù)雜度。本文采用的方法是將四維向量通過距離公式，轉(zhuǎn)換為一維的歐氏距離。

距離公式為：

其中，P代表當前物理機的剩余可用資源，v代表虛擬機的請求資源。

文獻[7]提出了一種解決一維裝箱問題的近似算法——交叉裝填算法，并證明了該算法能達到裝箱問題最優(yōu)的近似值3/2，同時算法的復(fù)雜度能達到非線性最優(yōu)O（nlogn），因此適用于虛擬機放置問題。本文根據(jù)交叉裝填算法的思想，結(jié)合物理機與虛擬機性能的歐氏距離，得出OpenStack虛擬機放置算法。算法具體流程如下：

輸入：物理機集合P（具有相同的配置），虛擬機集合V。

輸出：實際使用的物理機數(shù)目Pused。

①由公式（6）計算所有要創(chuàng)建的虛擬機與物理機的歐氏距離，將v1，v2，…，vm的按dpv大小進行非減排序，不妨設(shè)dpv≤dpv≤…dpv。（距離越小，說明虛擬機請

12m求的資源數(shù)越多，虛擬機越“大”）

②首先把排序好的虛擬機隊列頭部v1放入物理機p1中，將v1從隊列中刪除，然后嘗試從隊列尾部將vm放入p1。如果vm能夠放入物理機p1中，則將放入物理機p1中，并將vm從隊列中刪除，然后 執(zhí)行③；如果不能則執(zhí)行④。

③從隊列頭部開始往后找出第一個能放置在當前物理機上pi的虛擬機vj，如果能找到，則將vj放入pi，b并將vj從隊列中刪除，再按照②中方法處理尾部虛擬機；如果不能找到，則執(zhí)行④。

④開啟新的物理機pk，然后按照②、③的方式處理，直到所有虛擬機放置完成。

⑤輸出Pused。

3　仿真實驗與結(jié)果分析

為了驗證該基于歐氏距離交叉裝填放置算法在OpenStack云計算虛擬機放置的實際應(yīng)用中的效果，本文通過對算法進行仿真實驗，并且與OpenStack內(nèi)置的放置算法進行對比，證明了本文算法的有效性與優(yōu)越性。

3.1CloudSim 云計算仿真平臺

由于實驗環(huán)境計算機資源有限，無法滿足企業(yè)級至少幾十臺物理節(jié)點的生產(chǎn)環(huán)境，所以本文采用在CloudSim云計算仿真平臺[8]上實現(xiàn)該算法。CloudSim是澳大利亞墨爾本大學的網(wǎng)格實驗室和Gridbus項目推出的云計算仿真軟件。它是在離散事件模擬包SimJava上開發(fā)的函數(shù)庫，是一個通用、可擴展的仿真框架。這個仿真框架具有以下幾個特性：（1）支持在單個主機上進行大規(guī)模云計算基礎(chǔ)設(shè)施的仿真和實例化；（2）CloudSim的CIS（Cloud Information Service）和DataCen-terBroker實現(xiàn)資源發(fā)現(xiàn)和信息交互，是模擬調(diào)度的核心，用戶自行開發(fā)的調(diào)度算法可在DataCenterBroker的方法中實現(xiàn)，從而實現(xiàn)調(diào)度算法的模擬。

3.2仿真實驗結(jié)果分析

本次仿真實驗設(shè)置的物理節(jié)點的為100臺，每臺的CPU大小為1.6GHz，內(nèi)存大小為1.6GMB，磁盤空間大小為2000GB,網(wǎng)絡(luò)帶寬為500Mbps。

虛擬機共設(shè)置10種不同配置，來模擬實際環(huán)境中各種類型，這10種虛擬機配置如表1所示。

表1　虛擬機配置表

實驗中，虛擬機以這10個類型為一組，實驗創(chuàng)建虛擬機數(shù)從10臺開始，每次增加10臺，直到200臺為止，來對比OpenStack默認的放置算法和本文得出的基于距離的交叉裝填放置算法所需要開啟的物理機數(shù)量。實驗結(jié)果如表2，圖3所示：

表2　實驗結(jié)果對比

圖3　實驗效果

可以看出，本文提出的距離交叉裝填算法比OpenStack默認的放置算法有效。在申請創(chuàng)建的虛擬機數(shù)量較少的時候，兩種算法并沒有太大的差別，但是隨著創(chuàng)建虛擬機數(shù)量的增加，距離交叉裝填算法的性能優(yōu)勢越來越明顯，所需要的物理機數(shù)量明顯小于OpenStack默認的虛擬機放置算法。說明距離交叉裝填算法用于OpenStack的虛擬機放置能夠提高云平臺的資源利用率。以此證明了本文算法的有效性。

4　結(jié)語

本文研究了OpenStack云計算平臺的虛擬機創(chuàng)建流程，分析了其虛擬機的放置算法，并提出了基于距離的交叉裝填放置算法，并通過CloudSim仿真平臺進行了實驗，表明距離交叉裝填算法提高了OpenStack云計算平臺的資源利用率，減少了中小企業(yè)部署OpenStack云計算機平臺的物理機數(shù)量，降低了成本開銷，具有實際使用價值。本文的下一步研究工作重點將放在多方面考慮放置策略，在資源利用率，用戶服務(wù)質(zhì)量和能耗等幾個方面綜合權(quán)衡，能在大規(guī)模數(shù)據(jù)中心環(huán)境下對虛擬機的放置進行優(yōu)化。

[1]Zhang Q,Cheng L,Boutaba R.Cloud Computing:State-of-the-Art and Research Challenges[J].Journal of Internet Services and Applications,2010,1（1）:7-18.

[2]Dorigo M,Maniezzo,Colorni A.The Ant System:Optimization by a Colony of Cooperating Agents[C].IEEE Trans.System Man Cybernet.1996（B26）:29-41

[3]Agrawal S,Bose S K,Sundarrajan S.Grouping Genetic Algorithm for Solving the Server Consolidation Problem with Conflicts[J].Gec Proceedings of the First Acm/sigevo Summit on Genetic&Evolutionary Computation,2009:1-8.

[4]楊星,馬自堂,孫磊.云環(huán)境下基于改進蟻群算法的虛擬機批量部署研究[J].計算機科學,2012,39（9）:33-37.

[5]OpenStack Installation Guide for Red Hat Enterprise Linux 7,CentOS 7,and Fedora 20[EB/OL].（2014-10-16）[2015-08-04].http:// docs.openstack.org/juno/install-guide/install/yum/content/.

[6]HYEAR C,MACKEE B,GARDNER R,et al.Autonomic Virtual Machine Placement in the Data Center[J].Hewlett Packard Laboratories,Tech.Rep.HPL-2007-189,2007:2007-189.

[7]孫春玲，陳智斌，李建平.裝箱問題的一種新的近似算法[J].云南大學學報:自然科學版,2004,26（5）:392-396.

[8]Calheiros R N,Ranjan R,De Rose C A F,et al.Loudsim:A Novel Framework for Modeling and Simulation of Cloud Computing Infrastructures and Services[R].GRIDS-TR-2009-1,Grid Computing and Distributed Systems Laboratory.The University of Melbourne, Australia,March 13,2009

OpenStack;Cloud Computing;Placement Algorithm;Virtual Machine Scheduling;Resource Utilization Ratio

Research on Virtual Machine Placement Algorithm Based on OpenStack

WEN Chao，HU Xiao-qin
（College of Computer Science,Sichuan University，Chengdu 610065）

1007-1423（2016）07-0003-05

10.3969/j.issn.1007-1423.2016.07.001

文超（1990-），男，四川德陽人，碩士研究生，研究方向為網(wǎng)絡(luò)與信息安全安全胡曉勤（1977-），男，四川內(nèi)江人，講師，碩士研究生導(dǎo)師，研究方向為信息安全收稿日期：2016-01-19修稿日期：2016-02-20

近幾年來，云計算技術(shù)飛速發(fā)展，對IT界以及人們的日常產(chǎn)生活帶來越來越大的影響。OpenStack是當今最流行的開源IaaS云平臺，研究OpenStack的虛擬機初始放置問題，指出OpenStack在虛擬機放置方面的不足，并且提出距離交叉裝填算法作為OpenStack的虛擬機初始放置算法。實驗結(jié)果表明，該算法比OpenStack默認的虛擬機放置算法性能更好，提高物理機資源利用率。

OpenStack；云計算；放置算法；虛擬機調(diào)度；資源利用率

In recent years,cloud computing technology is developing rapidly and it has brought more and more influence on the IT industry and people's daily life.OpenStack is one of today’s most popular open-source IaaS cloud platform,studies the virtual machine initial place-ment algorithm of OpenStack and points out the disadvantages of it,and then comes up with an distance-cross-filling algorithm as the virtual machine placement algorithm of OpenStack.Experimental results show that the proposed algorithm performs better than Open-Stack’s default algorithm,and that the proposed algorithm improves the utilization of physical machine resources.