OpenStack環(huán)境下的虛擬機(jī)調(diào)度算法研究

陳昊 文成玉

摘 要：隨著云數(shù)據(jù)中心的大規(guī)模應(yīng)用，文章通過對(duì)當(dāng)今主流的開源云平臺(tái)OpenStack在虛擬機(jī)初始化放置機(jī)制的研究，針對(duì)OpenStack在創(chuàng)建虛擬機(jī)時(shí)初始化放置算法的不足，提出了基于虛擬機(jī)的綜合優(yōu)化放置算法作為OpenStack的虛擬機(jī)初始化放置算法，通過在仿真云平臺(tái)CloudSim上仿真，結(jié)果表明，該算法性能更好，能更好地提高物理機(jī)的資源利用率。

關(guān)鍵詞：OpenStack；虛擬機(jī)；調(diào)度算法

繼個(gè)人計(jì)算機(jī)、互聯(lián)網(wǎng)變革之后，2010年以來，云計(jì)算作為第三代IT浪潮的代表正在向我們走來，它將帶來人類生活、生產(chǎn)方式和商業(yè)模式的根本改變，成為當(dāng)前全社會(huì)關(guān)注的焦點(diǎn)。

隨著云計(jì)算的蓬勃發(fā)展，基于云平臺(tái)下的基礎(chǔ)設(shè)施的規(guī)模也變得越來越大，數(shù)據(jù)中心上部署的物理服務(wù)器也越來越多，各種各樣的服務(wù)和程序運(yùn)行在這些物理服務(wù)節(jié)點(diǎn)上，怎樣有效利用數(shù)據(jù)中心的共享資源，有效提高大規(guī)模的物理數(shù)據(jù)中心的資源利用率，具有重要意義。

現(xiàn)階段，云平臺(tái)的虛擬機(jī)初始化部署的研究主要分為傳統(tǒng)的啟發(fā)式算法和生物智能啟發(fā)式算法兩個(gè)方面。傳統(tǒng)的啟發(fā)式算法有首次匹配算法、最佳匹配算法等。生物智能啟發(fā)式算法主要有蟻群算法、遺傳算法等。上述算法在一定的情況下都能表現(xiàn)出較好的性能，但是在云平臺(tái)這種沒有環(huán)境限制下算法的性能會(huì)不穩(wěn)定。本文針對(duì)OpenStack內(nèi)置的算法的不足對(duì)傳統(tǒng)算法的啟發(fā)式的算法進(jìn)行了改進(jìn)，提出了綜合優(yōu)化放置算法。

1 0penStack虛擬機(jī)放置機(jī)制

1.1 0penStack虛擬機(jī)的創(chuàng)建流程

在OpenStack搭建的云環(huán)境中，分布著大量的性能不同的物理機(jī)，此時(shí)，當(dāng)有用戶在OpenStack的Web頁(yè)面dashboard上請(qǐng)求創(chuàng)建虛擬機(jī)時(shí)，就面臨著將虛擬機(jī)部署在哪個(gè)物理計(jì)算節(jié)點(diǎn)上的問題。OpenStack中，nova-scheduler（調(diào)度器）負(fù)責(zé)在資源池中篩選合適的物理服務(wù)器作為虛擬機(jī)實(shí)例的初始化部署節(jié)點(diǎn)。OpenStack中虛擬機(jī)的創(chuàng)建流程如圖1所示。

1.2 0penStack中內(nèi)置了兩種初始虛擬機(jī)放置算法

1.2.1 即時(shí)服務(wù)放置算法

即時(shí)服務(wù)放置算法即如果當(dāng)前的物理主機(jī)所剩余的內(nèi)存等資源滿足所申請(qǐng)創(chuàng)建的虛擬機(jī)的請(qǐng)求時(shí)，在滿足條件的物理機(jī)列表中隨機(jī)的選取一個(gè)物理主機(jī)做為虛擬機(jī)創(chuàng)建實(shí)例的初始化部署節(jié)點(diǎn)。

1.2.2 過濾稱重算法

過濾稱重算法如圖2所示。

過濾稱重算法主要是分為兩個(gè)步驟，首先OpenStack計(jì)算服務(wù)Nova中的過濾調(diào)度器FilterScheduler使用配置的過濾器（Filter）對(duì)物理服務(wù)器進(jìn)行過濾，篩選出符合要求的物理主機(jī)，然后對(duì)滿足條件的主機(jī)進(jìn)行權(quán)值排序，將獲得剩余資源最多的主機(jī)最終作為放置虛擬機(jī)實(shí)例的節(jié)點(diǎn)。

1.3 0penStack虛擬機(jī)初始部署算法的不足

OpenStack在默認(rèn)的情況下只是根據(jù)物理主機(jī)剩余的CPU進(jìn)行權(quán)值的計(jì)算。因此，物理主機(jī)剩余的可利用的CPU越多，則該物理主機(jī)被選為最佳放置虛擬機(jī)主機(jī)的概率就越大。這種算法的優(yōu)點(diǎn)是算法的實(shí)現(xiàn)相對(duì)比較簡(jiǎn)單。缺點(diǎn)是只是根據(jù)物理主機(jī)剩余的CPU大小來進(jìn)行權(quán)值的排序，進(jìn)而來選擇物理主機(jī)作為放置虛擬機(jī)實(shí)例的目標(biāo)主機(jī)，并不符合實(shí)際生產(chǎn)環(huán)境中云平臺(tái)的使用要求。另外，只是單一地根據(jù)物理計(jì)算節(jié)點(diǎn)所剩余的CPU的大小來決定虛擬機(jī)的放置策略，使得云環(huán)境中各個(gè)物理主機(jī)的CPU的利用率都不高，因此，在實(shí)際的云生產(chǎn)環(huán)境中，需要綜合考慮CPU、內(nèi)存、帶寬、磁盤等各個(gè)資源，最大限度地提高物理主機(jī)的資源利用率，避免資源的浪費(fèi)。

2 0penStack綜合優(yōu)化放置算法

2.1 問題模型

虛擬機(jī)的初始化部署問題可以簡(jiǎn)化為一種裝箱問題。即將m個(gè)w維的盒子裝入n個(gè)w維的箱子。每個(gè)虛擬機(jī)可以看成是一個(gè)盒子，每個(gè)物理主機(jī)看作是一個(gè)箱子。盒子的重量是該虛擬機(jī)占用的資源。虛擬機(jī)的調(diào)度優(yōu)化目標(biāo)是將多個(gè)虛擬機(jī)放入物理主機(jī)中。保障用戶的服務(wù)質(zhì)量，同時(shí)，每個(gè)物理主機(jī)上虛擬機(jī)占用的資源總量不能超過物理主機(jī)所能提供的資源總量。并且，使虛擬機(jī)占用的物理主機(jī)的數(shù)量最少。達(dá)到節(jié)省能耗、提高資源利用率的目的。

問題定義：將數(shù)據(jù)中心的n個(gè)物理主機(jī)定義為集合P={P₁，…，P_n}，將需要放置的m個(gè)虛擬機(jī)定義為集合V={v₁，…，v_m），物理主機(jī)上虛擬機(jī)的放置向量為H={h_i1，h_i2，…，h_im）。h_ij=1表示虛擬機(jī)v_j放在物理主機(jī)p_i上。定義每個(gè)物理節(jié)點(diǎn)上的資源為w維。因?yàn)槲锢矸?wù)器節(jié)點(diǎn)的資源主要有CPU、內(nèi)存、網(wǎng)絡(luò)帶寬和磁盤存儲(chǔ)，所以簡(jiǎn)化定義物理服務(wù)器資源向量為四維向量P_i=（SC_i，SM_i，SM_i，SH_i）相應(yīng)的虛擬機(jī)的資源定義為v_j=sc_i，sm_i，sn_i，sh_i）。

虛擬機(jī)的部署問題可以描述如下：

公式組（1）中第一個(gè)公式表示虛擬機(jī)只能部署在一臺(tái)物理機(jī)上。后面4個(gè)公式為約束條件分別表示某個(gè)物理機(jī)上虛擬機(jī)占用的CPU、內(nèi)存、帶寬、磁盤存儲(chǔ)的資源總數(shù)不能超過物理機(jī)提供的總的資源總量。n表示物理主機(jī)的總數(shù)，m表示虛擬機(jī)的總數(shù)。目標(biāo)函數(shù)（2）為云平臺(tái)所使用的物理機(jī)最少，即云平臺(tái)的資源利用率最高。

F=min（P_used）

（2）

2.2 基于啟發(fā)式算法改進(jìn)的虛擬機(jī)綜合優(yōu)化放置算法

虛擬機(jī)的初始化部署問題可以看成是n維裝箱問題，對(duì)于多維問題，通常選擇降維的方法將多維問題轉(zhuǎn)化成一維問題來解決。本文選擇的是利用歐氏距離將虛擬機(jī)的CPU、內(nèi)存、帶寬、磁盤存儲(chǔ)四維向量轉(zhuǎn)化成一維問題。

算法的流程如下。

（1）輸入虛擬機(jī)的集合V，物理服務(wù)器集合P，根據(jù)公式（3）分別計(jì)算每個(gè)虛擬機(jī)對(duì)應(yīng)的歐氏距離d_ij，并將對(duì)應(yīng)的虛擬機(jī)按照各自的歐氏距離的大小進(jìn)行升序排序。

（2）將虛擬機(jī)隊(duì)列中第一個(gè)放置物理機(jī)pl中，并將隊(duì)列首部的虛擬機(jī)從集合中移除，判斷隊(duì)列末尾的虛擬機(jī)能否放入物理機(jī)pl中，如果能，則將隊(duì)列末尾的虛擬機(jī)放入物理機(jī)pl中，并將隊(duì)列末尾的虛擬機(jī)從隊(duì)列中移除。如果不能，則重新開啟一臺(tái)物理主機(jī)。

（3）從虛擬機(jī)集合中檢索第一個(gè)能放入物理主機(jī)中的虛擬機(jī)，如果能找到，則將該虛擬機(jī)放入物理主機(jī)Pi中，如果不能找到，則新開啟一臺(tái)物理主機(jī)，將該虛擬機(jī)放入到物理主機(jī)p_i中。

（4）不斷重復(fù)步驟3，直到所有的虛擬機(jī)都放入物理主機(jī)中。

（5）輸出物理服務(wù)器所用的數(shù)量。

3 仿真結(jié)果分析

為了驗(yàn)證本文提出的綜合優(yōu)化虛擬機(jī)初始放置算法對(duì)在實(shí)際的云平臺(tái)上的效果，通過在CloudSim仿真云平臺(tái)上的仿真與OpenStack內(nèi)置的虛擬機(jī)初始化部署算法做對(duì)比來驗(yàn)證本文提出的算法的有效性。

實(shí)驗(yàn)中參與的模擬的物理服務(wù)器的規(guī)模為200個(gè)，每個(gè)服務(wù)器的配置為CPU2.1 GHz，內(nèi)存的大小為8 GMB，磁盤的大小為2 000 GB，網(wǎng)絡(luò)帶寬為1 000 Mbps。虛擬機(jī)總共有10種不同的配置。虛擬機(jī)的配置如表1所示。

試驗(yàn)中，每10個(gè)虛擬機(jī)一組，每次增加一組總共測(cè)得20組數(shù)據(jù)，實(shí)驗(yàn)結(jié)果如圖3所示。

由圖3可以看出，本文提出的基于啟發(fā)式算法改進(jìn)的虛擬機(jī)綜合優(yōu)化初始化部署算法，隨著虛擬機(jī)創(chuàng)建數(shù)量的增多，相對(duì)于OpenStack內(nèi)置算法的性能優(yōu)勢(shì)越來越明顯。以此說明了該算法的有效性。

4 結(jié)語(yǔ)

本文通過研究虛擬機(jī)的創(chuàng)建的流程，并通過對(duì)OpenStack內(nèi)置的虛擬機(jī)資源調(diào)度算法的分析，針對(duì)內(nèi)置算法的不足，對(duì)基于啟發(fā)式虛擬機(jī)資源調(diào)度算法進(jìn)行了改進(jìn)，并提出了綜合負(fù)載優(yōu)化調(diào)度算法，并通過在CloudSim云仿真平臺(tái)上進(jìn)行了算法的仿真，仿真結(jié)果表明該算法減少了物理服務(wù)器的使用數(shù)量，提高了資源利用率，減少了平臺(tái)的能耗。本文的下一步重點(diǎn)將放在虛擬機(jī)的動(dòng)態(tài)遷移策略上。

[參考文獻(xiàn)]

[1]賽迪顧問有限公司中國(guó)云計(jì)算產(chǎn)業(yè)發(fā)展白皮書[J]中國(guó)信息通信研究院，2010 （1）：3-4.

[2]孫春玲，陳智斌，李建平.裝箱問題的一種新的近似算法[J].云南大學(xué)學(xué)報(bào)，2004 （5）：392-396.

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