基于互補機制的虛擬機放置算法*

孫素云

(廣東輕工職業(yè)技術(shù)學(xué)院信息技術(shù)學(xué)院，廣東 廣州 510300)

云計算作為一種新型的資源供給模式，用戶可以按需獲取所需要的網(wǎng)絡(luò)資源[1]。數(shù)據(jù)中心通過采用虛擬化技術(shù)，將服務(wù)器資源(如CPU、內(nèi)存、帶寬等)以虛擬機方式進行封裝，然后按需提供給網(wǎng)絡(luò)用戶。虛擬機放置問題是指將用戶請求的虛擬機放置到數(shù)據(jù)中心的服務(wù)器上，實現(xiàn)虛擬機到服務(wù)器之間的映射。目前中等規(guī)模數(shù)據(jù)中心通常由成千上萬臺服務(wù)器組成，數(shù)據(jù)中心的能耗已成為一個巨大的運營開銷[2]，因此虛擬機放置算法的優(yōu)劣不僅關(guān)系到用戶服務(wù)水平協(xié)議(service level agreement，SLA)，而且影響數(shù)據(jù)中心的資源利用率和能耗效率[3]。

在數(shù)據(jù)中心中，將M個虛擬機放置到N(M≤N)個服務(wù)器中，其解空間為MN，這是一個典型NP-hard問題[3]。近幾年，學(xué)者們對虛擬機放置問題進行了廣泛的研究，提出許多啟發(fā)式虛擬機放置算法[4]，例如：首次適應(yīng)(first fit，F(xiàn)F)、最佳適應(yīng)(best fit，BF)、降序首次適應(yīng)(first fit decreasing，F(xiàn)FD)和降序最佳適應(yīng)(best fit decreasing，F(xiàn)FD)等[5]。文獻[2]根據(jù)數(shù)據(jù)中心的運行記錄，提出了一個虛擬機資源預(yù)測模型，然后根據(jù)預(yù)測的虛擬機請求量和服務(wù)器資源量之間的互補關(guān)系，將虛擬機放置到服務(wù)器中?；趧討B(tài)規(guī)劃思想，文獻[3]通過將虛擬機放置問題轉(zhuǎn)化為多階決策背包問題，然后采用動態(tài)規(guī)劃算法對虛擬機放置問題進行求解。文獻[6]通過計算CPU資源和內(nèi)存資源的比值，然后按照比值大小依次將虛擬機放置到相應(yīng)的服務(wù)器中。文獻[7]采用偏斜度刻畫CPU資源和內(nèi)存資源等利用率的差異性，然后將虛擬機依次遷移到資源利用率均方差最小的服務(wù)器中。通過對虛擬機負(fù)載高峰特征進行建模，文獻[8]提出了基于負(fù)載相似度矩陣的虛擬機放置算法。

綜上所述，有的虛擬機放置算法有的只考慮一個或兩個資源維度，有的只考慮虛擬機之間的互補關(guān)系，有的只考慮虛擬機和服務(wù)器的互補特性，特別是在設(shè)置分配權(quán)重時，大部分采用靜態(tài)閾值方法，忽略了網(wǎng)絡(luò)資源的動態(tài)變化特性。本文在現(xiàn)有研究工作的基礎(chǔ)上，通過綜合考慮虛擬機之間的互補關(guān)系，以及虛擬機和服務(wù)器之間的互補特性，通過提出動態(tài)閾值方法，使資源分配能適應(yīng)資源狀態(tài)的動態(tài)變化，從而有效地提高數(shù)據(jù)中心網(wǎng)絡(luò)資源的利用效率。

1 問題描述

通過采用虛擬化技術(shù)將數(shù)據(jù)中心的網(wǎng)絡(luò)資源，如CPU，內(nèi)存和鏈路帶寬資源等進行抽象化，使數(shù)據(jù)中心成為一個可擴展、可按需分配的虛擬資源池。在云計算模式中，用戶的資源請求通過虛擬機進行封裝，如圖1所示的應(yīng)用場景中，用戶1，用戶2，…，用戶t向數(shù)據(jù)中心提交m個虛擬機請求，控制器根據(jù)服務(wù)器中資源狀態(tài)，將m個虛擬機分別放置到k個服務(wù)器中(k≤n，n表示服務(wù)器的個數(shù))，并為虛擬機分配相應(yīng)的資源量。因此虛擬機放置問題其實質(zhì)即為m個虛擬機和n個服務(wù)器之間的映射問題。

圖1 用戶請求虛擬機與虛擬機放置模型Fig.1 Virtual machine request and placement model

由于網(wǎng)絡(luò)應(yīng)用的異構(gòu)性，不同的虛擬機資源請求量會存在差異性，如虛擬機1中CPU資源量較多，內(nèi)存資源量較小，虛擬機2中CPU資源量較小，內(nèi)存資源量較多?？刂破髟诜胖锰摂M機請求的時候，如果隨機地將虛擬機部署到服務(wù)器中，某些服務(wù)器中可能出現(xiàn)可用的CPU資源量為0，而內(nèi)存資源量較多，從而影響資源的利用效率。另一方面，由于數(shù)據(jù)中心規(guī)模日益龐大，電能消耗已成為一個巨大的運營開銷。不合理的資源分配不僅影響資源的利用效率，而且會導(dǎo)致運行的服務(wù)器個數(shù)增多，數(shù)據(jù)中心的能耗增大。通過提出一個基于資源互補機制的虛擬機放置算法，將虛擬機放置到資源互補的服務(wù)器中，使服務(wù)器中各種資源量呈現(xiàn)均衡分布狀態(tài)，達(dá)到提高資源的利用效率以及降低數(shù)據(jù)中心能耗的目的。

1.1 資源消耗模型

(1)

(2)

(3)

(4)

式(1)表示每個虛擬機只能放置在一個服務(wù)器中，式(2)表示當(dāng)服務(wù)器放置了虛擬機后，變量yj的值為1，否則yj的值為0，式(3)表示服務(wù)器中所有虛擬機第k維的資源請求量總和不能大于服務(wù)器的第k維可用資源量，式(4)表示數(shù)據(jù)中心中運行的服務(wù)器個數(shù)。

1.2 能耗模型

合理的虛擬機放置算法不僅可以提高資源的利用效率，而且可以降低數(shù)據(jù)中心的電能消耗。數(shù)據(jù)中心的電能消耗通常包括服務(wù)器的能耗、制冷設(shè)備的能耗和照明設(shè)備的能耗等。數(shù)據(jù)中心的能耗可以用服務(wù)器的能耗進行近似計算[3]，單個服務(wù)器的能耗和整個數(shù)據(jù)中心的能耗定義為：

(5)

(6)

(7)

2 基于互補的虛擬機放置

2.1 基于互補機制的虛擬機組合算法

為了提高虛擬機放置算法的網(wǎng)絡(luò)性能，在虛擬機放置到服務(wù)器之前，采用基于互補機制對虛擬機進行組合，使新組合的虛擬機(可視為新的虛擬機)中各種資源量盡可能均衡的分布，見圖2。

圖2 虛擬機與虛擬機互補示例圖Fig.2 The complementary examples among virtual machines

圖2中豎線和橫線方框分別表示CPU、內(nèi)存資源量，方框高度表示資源請求量大小。如圖2所示，如果將虛擬機1和虛擬機2組合在一起，新組合的虛擬機中CPU和內(nèi)存資源量呈現(xiàn)均衡分布，如果將虛擬機1和虛擬機3組合在一起，新組合的虛擬機中CPU和內(nèi)存資源量分布不均衡。通過對虛擬機組合問題進行分析，我們提出虛擬機之間的互補關(guān)系模型。

(8)

表1 基于互補的虛擬機組合算法Table 1 Algorithm of virtual machine combination based on complementary

算法1中第5行表示，對虛擬機中各種資源量先做正則化處理，然后計算虛擬機中最大資源請求量與最小資源請求量的比值，并按照比值進行降序排列，使得資源分布最不均衡的虛擬機優(yōu)先查找互補的虛擬機，以此改善虛擬機中資源的分布狀態(tài)。第7到第10表示，對資源請求量大于服務(wù)器資源量平均值的虛擬機不進行虛擬機組合操作。第11行到第18行表示為虛擬機查找具有互補關(guān)系的虛擬機，并將它們組合為新的虛擬機。通過運行算法1后，虛擬機中資源分布狀態(tài)將得到改善。算法1的時間復(fù)雜度為O(m2)，其中，m表示虛擬機請求個數(shù)。

2.2 基于互補機制的虛擬機放置算法

通過進行虛擬機組合操作后，虛擬機中資源請求量均衡度將得到改善。由于虛擬機中資源維度個數(shù)較多，仍然有可能是不均衡分布的。特別是，有的虛擬機沒有進行組合操作，它們不均衡分布狀態(tài)更加嚴(yán)重。因此在放置虛擬機的時候，需要考慮虛擬機和服務(wù)器之間的資源狀態(tài)，把虛擬機放置到具有互補關(guān)系的服務(wù)器中，提高計算資源的利用效率，見圖3。

圖3 虛擬機和服務(wù)器互補示例圖Fig.3 The complementary examples between VMs and servers

圖3中豎線和橫線方框分別表示CPU、內(nèi)存資源量，方框高度表示資源量大小。圖3(a)表示虛擬機和服務(wù)器的資源分布狀態(tài)。在圖3(b)中，當(dāng)將虛擬機i放置到服務(wù)器1中，服務(wù)器1的CPU資源和內(nèi)存資源均衡度得到改善, 當(dāng)將虛擬機i放置到服務(wù)器2時，服務(wù)器2的CPU資源和內(nèi)存資源不均衡度更嚴(yán)重。通過對虛擬機放置問題進行分析，提出虛擬機和服務(wù)器的資源互補關(guān)系模型。

(9)

算法2為虛擬機在數(shù)據(jù)中心中查找具有互補關(guān)系的服務(wù)器，使虛擬機放置到服務(wù)器后，服務(wù)器中各種資源量盡可能均衡分布。第6行用于保證服務(wù)器中可用的資源量能滿足虛擬機的需求量。如果待放置的虛擬機是組合型虛擬機，則表示將組合之前的虛擬機放置在服務(wù)器中。算法2的時間復(fù)雜度為O(m·n)，其中，m表示虛擬機請求個數(shù)，n表示服務(wù)器個數(shù)(表2)。

表2 基于互補的虛擬機放置算法(CBVMP)Table 2 Algorithm of virtual machine placement based on complementarity

3 仿真實驗

為了分析CBVMP算法的網(wǎng)絡(luò)性能，實驗中實現(xiàn)了first fit(FF)[10]、first fit decreasing sum(FFDSum)[11]以及compVM-Grp算法[2]。CBVMP算法首先進行虛擬機組合操作，然后基于互補機制實施虛擬機放置操作。FF算法將虛擬機放置到滿足其資源請求量編號最小的服務(wù)器中。FFDSum首先計算每個服務(wù)器中所有資源量的累積和，然后采用貪婪算法將虛擬機放置到累積和最小的服務(wù)器中。compVM-Grp首先將虛擬機隨機進行組合，然后采用compVM-Grp中互補模型將虛擬機放置到相應(yīng)的服務(wù)器中。

3.1 實驗環(huán)境設(shè)置

CloudSim[9]是一個虛擬化仿真實驗平臺，支持按需資源分配和管理操作。實驗中采用CloudSim對上述四個虛擬機放置算法進行仿真。仿真實驗期間，數(shù)據(jù)中心服務(wù)器的數(shù)量為600臺。實驗中其它參數(shù)，如服務(wù)器類型、虛擬機類型和服務(wù)器的電能消耗模型如表3、表4和表5所示。

表3 服務(wù)器類型描述Table 3 Server type description

表4 虛擬機類型描述Table 4 Virtual machine type description

表5 服務(wù)器能耗和利用率Table 5 Server energy consumption and utilization W

3.2 實驗結(jié)果與分析

根據(jù)服務(wù)器的運行個數(shù)、數(shù)據(jù)中心的能耗，CPU、內(nèi)存和硬盤資源的平均利用率等評價上述四個算法的網(wǎng)絡(luò)性能。服務(wù)器的運行個數(shù)表示為放置虛擬機而啟動的服務(wù)器個數(shù)，數(shù)據(jù)中心的能耗表示啟動的服務(wù)器消耗電能總量，服務(wù)器的運行個數(shù)越少，數(shù)據(jù)中心的能耗越低，虛擬機放置算法的網(wǎng)絡(luò)性能也越好。資源的平均利用率表示所有啟動的服務(wù)器中CPU、內(nèi)存和硬盤資源的平均利用率，平均利用率越高，虛擬機放置算法的網(wǎng)絡(luò)性能也越好。實驗結(jié)果如圖4～圖6所示。

圖4顯示了在3種不同虛擬機請求個數(shù)時，四個算法為滿足虛擬機請求而啟動的服務(wù)器個數(shù)。圖4顯示： FF算法中運行的服務(wù)器個數(shù)最多，特別是在虛擬機個數(shù)較多時，F(xiàn)F算法運行的服務(wù)器個數(shù)比CBVMP算法高出25%以上。主要原因是FF算法根據(jù)服務(wù)器的編號順序依次將虛擬機放置到服務(wù)器中，沒有考慮虛擬機中資源請求量和服務(wù)器中可用資源量的相互關(guān)系，使服務(wù)器中可用資源量分布不均勻，導(dǎo)致運行的服務(wù)器個數(shù)增多。服務(wù)器的電能消耗和運行的服務(wù)器個數(shù)以及運行狀態(tài)有關(guān)，從圖5可以看出，F(xiàn)F算法的能耗也較大，進一步說明FF算法的資源分配效率和能耗效率都較低。

圖4 數(shù)據(jù)中心運行的服務(wù)器個數(shù)Fig.4 The number of running servers in the data center

圖5 數(shù)據(jù)中心的能耗Fig.5 Energy consumption in the data center

圖6 三種資源的平均利用率Fig.6 Average utilization rate of three resources

圖6顯示了四個算法的CPU、內(nèi)存和硬盤資源的平均利用率。從圖6可以看出， FF算法資源的平均利用率最低，CBVMP算法資源的平均利用率最高。圖6顯示FF算法和FFDSum算法內(nèi)存資源的利用率明顯低于硬盤資源的利用率、compVM-Grp算法硬盤資源的利用率明顯高于其它資源的利用率、CBVMP算法3種資源的平均利用率基本接近。實驗結(jié)果表明：基于互補機制的虛擬機放置算法能動態(tài)地適應(yīng)網(wǎng)絡(luò)資源狀態(tài)，合理地將虛擬機放置到最互補關(guān)系的服務(wù)器中，均衡地分配服務(wù)器中計算資源，提高資源的利用效率和能耗效率。

4 結(jié) 語

文章通過建立數(shù)學(xué)優(yōu)化模型，分析虛擬機放置問題中資源消耗和能源消耗的關(guān)系，并通過虛擬機放置實例，闡述虛擬機放置過程中需要考慮虛擬機與服務(wù)器之間的資源分布狀態(tài)。為了提高服務(wù)器資源的利用效率，文章基于互補關(guān)系模型，提出了基于互補機制的虛擬機放置算法，在虛擬機放置過程中動態(tài)考慮網(wǎng)絡(luò)中各個資源的分布狀態(tài)。實驗結(jié)果表明：CBVMP算法取得了較好的網(wǎng)絡(luò)性能，有效地提高了數(shù)據(jù)中心的資源效率和能耗效率。