文超，胡曉勤（四川大學(xué)計(jì)算機(jī)學(xué)院，成都　610065）

基于OpenStack的虛擬機(jī)初始放置算法研究

文超，胡曉勤
（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0　引言

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

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

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

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

1　OpenStack虛擬機(jī)放置算法

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

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

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

1.2OpenStack 放置算法

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

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

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

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

1.3OpenStack 虛擬機(jī)放置算法的不足

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

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

圖2　過濾稱重分配過程圖

2　OpenStack虛擬機(jī)交叉裝填放置算法

2.1虛擬機(jī)放置的數(shù)學(xué)模型

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

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

約束條件為:

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

2.2基于交叉裝填的虛擬機(jī)放置算法

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

距離公式為：

其中，P代表當(dāng)前物理機(jī)的剩余可用資源，v代表虛擬機(jī)的請求資源。

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

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

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

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

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

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

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

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

⑤輸出Pused。

3　仿真實(shí)驗(yàn)與結(jié)果分析

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

3.1CloudSim 云計(jì)算仿真平臺(tái)

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

3.2仿真實(shí)驗(yàn)結(jié)果分析

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

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

表1　虛擬機(jī)配置表

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

表2　實(shí)驗(yàn)結(jié)果對比

圖3　實(shí)驗(yàn)效果

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

4　結(jié)語

本文研究了OpenStack云計(jì)算平臺(tái)的虛擬機(jī)創(chuàng)建流程，分析了其虛擬機(jī)的放置算法，并提出了基于距離的交叉裝填放置算法，并通過CloudSim仿真平臺(tái)進(jìn)行了實(shí)驗(yàn)，表明距離交叉裝填算法提高了OpenStack云計(jì)算平臺(tái)的資源利用率，減少了中小企業(yè)部署OpenStack云計(jì)算機(jī)平臺(tái)的物理機(jī)數(shù)量，降低了成本開銷，具有實(shí)際使用價(jià)值。本文的下一步研究工作重點(diǎn)將放在多方面考慮放置策略，在資源利用率，用戶服務(wù)質(zhì)量和能耗等幾個(gè)方面綜合權(quán)衡，能在大規(guī)模數(shù)據(jù)中心環(huán)境下對虛擬機(jī)的放置進(jì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ìn)蟻群算法的虛擬機(jī)批量部署研究[J].計(jì)算機(jī)科學(xué),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].云南大學(xué)學(xué)報(bào):自然科學(xué)版,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-），男，四川德陽人，碩士研究生，研究方向?yàn)榫W(wǎng)絡(luò)與信息安全安全胡曉勤（1977-），男，四川內(nèi)江人，講師，碩士研究生導(dǎo)師，研究方向?yàn)樾畔踩崭迦掌冢?016-01-19修稿日期：2016-02-20

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

OpenStack；云計(jì)算；放置算法；虛擬機(jī)調(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.