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

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

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

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

0　引言

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

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

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

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

1　OpenStack虛擬機放置算法

1.1OpenStack 虛擬機創建流程

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

圖1　虛擬機創建內部流程圖

1.2OpenStack 放置算法

nova-scheduler中內置了2個虛擬機放置算法：

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

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

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

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

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

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

圖2　過濾稱重分配過程圖

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

2.1虛擬機放置的數學模型

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

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

約束條件為:

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

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

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

距離公式為：

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

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

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

輸出：實際使用的物理機數目Pused。

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

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

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

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

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

⑤輸出Pused。

3　仿真實驗與結果分析

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

3.1CloudSim 云計算仿真平臺

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

3.2仿真實驗結果分析

本次仿真實驗設置的物理節點的為100臺，每臺的CPU大小為1.6GHz，內存大小為1.6GMB，磁盤空間大小為2000GB,網絡帶寬為500Mbps。

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

表1　虛擬機配置表

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

表2　實驗結果對比

圖3　實驗效果

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

4　結語

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

[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]楊星,馬自堂,孫磊.云環境下基于改進蟻群算法的虛擬機批量部署研究[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-），男，四川德陽人，碩士研究生，研究方向為網絡與信息安全安全胡曉勤（1977-），男，四川內江人，講師，碩士研究生導師，研究方向為信息安全收稿日期：2016-01-19修稿日期：2016-02-20

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

OpenStack；云計算；放置算法；虛擬機調度；資源利用率

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.