貪心算法優(yōu)化云數(shù)據(jù)中心的虛擬機分配策略①

徐勝超

(廣州華商學院 數(shù)據(jù)科學學院,廣州 511300)

近年來云數(shù)據(jù)中心的構造與使用成了政府和各大IT 企業(yè)越來越重視的問題,為了倡導綠色云計算,云數(shù)據(jù)中心的構造目標是低能量消耗、高服務質量(Quality of Service,QoS)、節(jié)省物理空間和高可靠性等[1-3].一個數(shù)據(jù)中心(Data Center,DC)通常配置有大量的緊密堆積在一起物理節(jié)點(Physical Machines,PMs),目的是提高建筑物空間的利用率;虛擬化技術是云數(shù)據(jù)中心中最重要的技術,虛擬化允許用戶對云資源的訪問是透明與簡單方便的,它通過虛擬機(Virtual Machines,VM)的形式將應用程序封裝在虛擬機之中,通過虛擬機分配策略將其分配到具體的數(shù)據(jù)中心的物理節(jié)點之中執(zhí)行.所以虛擬機分配(Virtual Machine Distribution,VMD)等策略很大程度上影響了云平臺的整體性能,目前大量的文獻把性能指標關注在SLA 違規(guī)比率、服務質量QoS、系統(tǒng)能量消耗、虛擬機遷移次數(shù)等方面[4].

虛擬機分配的理想目標是盡量利用個數(shù)比較少的云數(shù)據(jù)中心,同時提高每個數(shù)據(jù)中心的云資源利用效率,在此基礎上提高云數(shù)據(jù)中心的靈活性和可用性,降低硬件成本和操作成本(能量消耗,物理空間占用等)[5].

本文設計了一種用于企業(yè)的云數(shù)據(jù)中心的工作場景,它可以接受大量客戶端的虛擬機的請求,并將這些虛擬機分配到云數(shù)據(jù)中心的具體物理節(jié)點執(zhí)行.參考了經(jīng)典的裝箱問題(classical in packing problem)模型,包括經(jīng)典的最好適應算法Best-Fit-Algorithm (BFA)、首次適應算法First-Fit-Algorithm (FFA),下次適應算法Next-Fit-Algorithm (NFA)、最壞適應算法Worst-Fit-Algorithm (WFA)和隨機算法Random Allocation -Algorithm (RAA)等來將大量的虛擬機放置到各個數(shù)據(jù)中心的物理節(jié)點完成云計算.建立了虛擬機放置過程中各種約束因素的數(shù)學模型,利用貪心算法(greedy algorithm)優(yōu)化云數(shù)據(jù)中心之間的虛擬機放置策略.測試結果表明,經(jīng)過優(yōu)化的最好適應算法BFA 具有比較好的性能,這對于其他企業(yè)建立與構造云數(shù)據(jù)中心有比較好參考價值.

1 相關工作

目前學術界針對云端的虛擬機分配與遷移策略,進行了大量的研究.主要分為兩類,第一類是針對從虛擬機到單數(shù)據(jù)中心中的物理節(jié)點的分配與遷移.第二類是針對從虛擬機到多個云數(shù)據(jù)中心的分配與調度.前一類關注的虛擬機在物理節(jié)點之間的選擇、分配和遷移;后者關注的是虛擬機在多個云數(shù)據(jù)中心的分配與放置.

針對第一類問題,例如文獻[6]提出并評價了云端多虛擬機遷移的負載與性能變化;文獻[7]提出了一種利用動態(tài)放置應用程序的方法EnaCloud,實現(xiàn)云平臺的能效管理.文獻 [8]同樣從CPU 維度對虛擬機的動態(tài)配置問題進行建模,并利用改進的蟻群算法進行求解.文獻[9]提出了PS-ABC 算法,該方法能夠在長期服務項目的局部時間段內(nèi)實現(xiàn)較好節(jié)能效果,但是在服務項目全局的能耗優(yōu)化問題上,效果并不理想.文獻[10]在此基礎上提出了PS-ES 啟發(fā)式算法,不僅實現(xiàn)了當前場景的能源優(yōu)化,而且也有效降低了長期服務項目總體的能源消耗,但其考慮的維度較單一.文獻 [11]在Beloglazov 研究的基礎上提出(Service Level Agreement,SLA)違規(guī)算法,引入最小能源最大利用率策略,進一步優(yōu)化虛擬機配置方法.

針對第二類研究,主要涉及到經(jīng)典裝箱問題,此類問題是一個基于多約束的整數(shù)規(guī)劃問題,同時也是一個NP-hard 問題.即將云數(shù)據(jù)中心抽象為箱子,箱子的容量是云數(shù)據(jù)中心資源的大小,包括物理服務器個數(shù)、CPU 主頻高低、CPU 內(nèi)核個數(shù),內(nèi)存大小、空余磁盤空間大小和應用程序類型等;虛擬機抽象為裝入的物品.例如文獻[12]利用裝箱問題提出了啟發(fā)式算法,但是它們考慮的維度比較單一.文獻[13]提出了向量裝箱和多維裝箱問題,文獻[14]采用了首次適應減少算法(First-Fit Decreasing,FFD)來提高裝箱性能與效果.文獻[15]采用遺傳算法來優(yōu)化資源的消耗,能量的消耗和虛擬機的放置.文獻[16]將多虛擬機放置設計為一個多目標約束滿意問題,目標是為了最小化物理節(jié)點個數(shù)和虛擬機遷移次數(shù).文獻[17]利用了約束編程模式,采用一個靈活和能量相關的框架來分配虛擬機到各個云數(shù)據(jù)中心.

在貪心算法方面文獻[18,19]提出了云計算中的基于貪心算法的任務調度及改進,把改進任務競爭時間和改進任務執(zhí)行代價作為主要因素.實驗結果表明貪心算法在串行調度算法的基礎上可以改進任務調度的性能,但是它們并沒有將貪心算法使用到物理資源使用和低能量消耗相關的算法之中,也沒有用來優(yōu)化云端的虛擬機到數(shù)據(jù)中心的分配.

最近這三年又有文獻提出采用軟件的方法來提高虛擬機分配和虛擬機放置策略的性能,還有文獻提出需要在虛擬機遷移過程中考慮網(wǎng)絡攻擊危險,保證云數(shù)據(jù)中心的可靠性.例如文獻[20]把虛擬機遷移過程劃分為物理主機狀態(tài)檢測、虛擬機映射、虛擬機選擇、虛擬機放置4 個復雜的步驟,虛擬機映射主要通過任務粒度、軟件代價等來進行調整;虛擬機放置屬于一類經(jīng)典裝相問題,即把大量的虛擬機VM 放置到大量的物理節(jié)點之中,它提出要考慮虛擬機映射和虛擬機放置之間的相互聯(lián)系的算法來改善性能.文獻[21]提出了云數(shù)據(jù)中心基于安全檢測的虛擬機遷移策略.利用隔室技術及SIR (Susceptible,Infected,Recovered)模型在虛擬機遷移過程將有安全威脅的虛擬機隔離出來,保證云數(shù)據(jù)中心的能量消耗與安全威脅的平衡.

本文提出的虛擬機分配策略屬于第二類方法,主要針對從虛擬機到云數(shù)據(jù)中心的分配,考慮的問題裝箱問題的維度不僅是硬件條件,還有軟件條件,采用貪心算法進行優(yōu)化,即在虛擬機分配的時候只要局部的各個維度的資源最高即可得到資源,完成分配.

2 貪心算法的虛擬機分配策略描述

2.1 虛擬機分配的層次結構

本文提出的云數(shù)據(jù)中心的虛擬機分配的工作場景如圖1,包括3 層的邏輯結構:用戶層、云服務提供者層、云數(shù)據(jù)中心集層.

圖1 貪心算法的虛擬機分配工作場景

用戶層Users 處于頂層.所有的應用程序的請求在這一層產(chǎn)生,并形成虛擬機請求集(VM Request Set,VMRS)它們將被發(fā)送到下一層:云服務提供者層(Cloud Service Provider Layer,CSPL).

中間層CSPL 包括兩個子層,上面的子層全部是來自用戶層的虛擬機請求集.虛擬機請求由CPU 使用率、內(nèi)存大小、內(nèi)核數(shù)目、應用程序類型(基于CPU的請求或基于I/O的請求)組成.下一子層是(Data Center Control Layer,DCCL)數(shù)據(jù)中心控制層,它擁有虛擬機請求和各個數(shù)據(jù)中心的信息,虛擬機分配過程中要考慮各種約束條件,包括資源是否滿足約束條件、用戶請求約束條件、用戶端和CSP 之間的SLA約束條件等.

所有的虛擬機請求都被放置到云數(shù)據(jù)中心被執(zhí)行,所以最下一層是(Data Center Set Layer,DCSL)云數(shù)據(jù)中心集層.數(shù)據(jù)中心集層的功能是完成被分配到每個具體的數(shù)據(jù)中心的虛擬機到其下物理節(jié)點的分配.

本文是假設每個云數(shù)據(jù)中心的節(jié)點是同構條件下的物理節(jié)點,同構條件下的計算機在統(tǒng)計其計算能力和存儲能力的時候可以按照線性關系累加.同時該工作場景下的所有云數(shù)據(jù)中心在同一個地理位置,這樣各個物理主機的網(wǎng)絡帶寬基本類似.

2.2 虛擬機分配的多維約束描述

我們把各個云數(shù)據(jù)中心的最大能量消耗和最小能量消耗分別定義為energymax和energyidle.被分配到各個云數(shù)據(jù)中心的虛擬機也定義了一個與其相關的代價變量dcprice,dcprice的數(shù)值相當于是一種資源需求,就是混合多個維度的資源需求.虛擬機分配主要用來處理n個虛擬機的請求,每個虛擬機VMi由CPU 利用率,內(nèi)存大小,CPU 內(nèi)核數(shù)量和應用程序操作類型(CPU based 或者I/O based)組成.所有的這些虛擬機的請求組成了虛擬機請求集合:{VM1,VM2,···,VMn}.每個數(shù)據(jù)中心(DC)由于k個同構的物理節(jié)點組成,每個物理節(jié)點都有自己的CPU,內(nèi)存大小和內(nèi)核個數(shù);所有每個數(shù)據(jù)中心的所有物理節(jié)點組成了物理主機集合:{PM1,PM2,···,PMk}.云數(shù)據(jù)中心組成了數(shù)據(jù)中心的集合:{DC1,DC2,···,DCm}.這里每個DCj都具有一個應用程序類型(CPU 或者 I/O),與具體的虛擬機請求對應,這樣方便VMi可以被分配到具體的DCj.

DC集合中的云數(shù)據(jù)中心必須記錄一個具體的價值參數(shù)dcprice,該dcprice為放置到該DC中的虛擬機的多維的資源請求數(shù)值,在云計算的服務等級協(xié)議SLA 協(xié)議中,在用戶User和云服務提供者CSP 之間,該價值dcprice為固定不變的.利用一個向量來表示DC集合中的所有數(shù)據(jù)中心中的價值:dcpricevector={dcprice1,dcprice2,···,dcpricem}.DC集合中的每個云數(shù)據(jù)中心必須記錄energymax值和energyidle值.這兩個值用來計算每個數(shù)據(jù)中心中的虛擬機放置后的能量消耗.可以把能量向量定義如下:

根據(jù)前面的思路,認為把虛擬機請求集放置到具體的云數(shù)據(jù)中心為裝箱問題,我們需要考慮的問題的約束條件和維度具體包括:

1)應用程序請求調度約束條件:這個約束將考慮虛擬機請求的所有維度參數(shù),包括虛擬機請求的CPU使用率、內(nèi)存大小、內(nèi)核數(shù)目、請求類型(基于CPU的請求或基于I/O的請求).

2)能力約束條件(capacity).這個約束主要是判斷云平臺的整體的資源使用狀態(tài),虛擬機請求集的整體資源需求之和必須小于或者等于云數(shù)據(jù)中心的整體資源,當然這個資源數(shù)據(jù)必須考慮多個維度之總和.

3)放置約束條件.這里約束了如果整體資源已經(jīng)足夠,可以只從云數(shù)據(jù)中心集合中選擇一個云數(shù)據(jù)中心,它們要求盡量少的使用云數(shù)據(jù)中心.

2.3 貪心算法優(yōu)化的虛擬機分配方法

根據(jù)前面提到的,在虛擬機分配的時候假設每個DC中有k個物理主機PM,設計CPMr(i)定 義為PMi中的第r維度的資源提供能力(capacity),那么一個數(shù)據(jù)中心中的所有物理主機在第r維度的資源提供能力可以根據(jù)式(1)進行計算.

這里PMi的維度表示的是本文前面提到的CPU 速度、內(nèi)存大小和CPU 內(nèi)核數(shù)目.這樣m個同構條件下的云數(shù)據(jù)中心組成的云平臺在第r維度的總體資源提供能力可以定義為式(2):

類似于式(2),我們定義n個虛擬機請求組成的虛擬機請求集的整體資源需求能力(capacity)為式(3):

這里CVMr(j)表示了第j個虛擬機申請在第r維度的資源需求.我們把DCi在第r維度的利用效率可以定義為放置到第i個數(shù)據(jù)中心的整體虛擬機請求資源和DCi在第r維度的總體資源提供能力的比例,見式(4).

如果VMi被分配到了DCj中,則這里有Vij=1.前面我們提到,云數(shù)據(jù)中心與3 個價值向量相關,分別是dcpricevector,energymaxvector和energyidlevector.隨著DCs中的DC個數(shù)從1 到m的變化,dcpricevector會持續(xù)的增加,這3 個向量表達如下:

如果把能量最大向量和能量最小向量考慮進去,那么云數(shù)據(jù)中心DCj的整體能量消耗可以通過公式(5)來計算.

式中,DCj的能量消耗包括新增虛擬機VMs的能量消耗和其在空閑時間內(nèi)的能量消耗.新分配虛擬機的能量消耗是通過考慮DCj在所有3 個維度的價值的最大值減去DCj在所有3 個維度的價值的最小值,然后乘以利用效率的最大值.這樣DCj的整體能量消耗(Total Energy Consumption,TEC)可通過式(6)進行計算.

與每個數(shù)據(jù)中心關系密切的這兩個參數(shù)就是在跨數(shù)據(jù)中心進行虛擬機分配的總價值參數(shù)dcprice和其對應的能量消耗參數(shù)TEC.我們定義DCj的目標函數(shù)為fnDC,它可以通過式(7)來表示.

這里ωen和ωex是總能量消耗參數(shù)和總價值參數(shù)分別對應的權重,ωen+ωex=1.如果VMi被分配到了DCj中,這里有Vij=1.整體云計算平臺的目標函數(shù)為式(8):

overallfnDC是所有在DC集中的每個fnDC(j)的算術總和.overallfnDC用來分析虛擬機的請求和目標函數(shù)約束.目標函數(shù)的約束條件如式(9)～式(12).

式(9)滿足了前面提到的虛擬機調度約束條件;式(10)滿足了資源使用能力約束條件;式(11)和式(12)滿足了虛擬機放置約束條件,一個虛擬機只能放置到惟一的云數(shù)據(jù)中心,因為通過Vij=0或Vij=1保證了這個約束條件.

虛擬機分配是一個NP-Hard 問題,本文應用貪心算法的啟發(fā)式算法,參考前面公式中計算的overallfnDC總體價值參數(shù)和總能量消耗TEC參數(shù),將虛擬機請求集放置到目標函數(shù)最合適的云數(shù)據(jù)中心之中.

云數(shù)據(jù)中心控制層使用和收集虛擬機請求集的所有信息,數(shù)據(jù)中心集DCs在面向虛擬機在跨云數(shù)據(jù)中心分派的過程中,應用了貪心算法的具體規(guī)則,例如,隨機選擇random allocation,下次適應next fit,首次適應first fit,最好適應best fit和最壞適應worst fit,最終完成虛擬機的放置.

3 算法的測試與性能分析

3.1 測試環(huán)境

在針對應用程序虛擬機分配時,本文把貪心啟發(fā)式算法應用到經(jīng)典的裝箱問題解決辦法之Random Allocation Algorithm (RAA)隨機選擇算法、下次適應算法Next Fit Allocation (NFA)、首次適應算法First Fit Allocation (FFA)、最好適應算法Best Fit Allocation(BFA)和最壞適應算法Worst Fit Allocation (WFA)之中.

利用某個企業(yè)的4 個大規(guī)模云數(shù)據(jù)中心作為測試環(huán)境,訪問云服務器的客戶端的物理節(jié)點硬件組成情況如下表1,云數(shù)據(jù)中心的物理節(jié)點情況配置如表2,虛擬機請求通過一個統(tǒng)一的Web 應用程序訪問,主要包括3 類虛擬機,每個虛擬機對資源的請求需求如表3.

為了仿真需要,實驗中改變虛擬機請求個數(shù)從25到250 個,其中步長為25.因為本文利用的云數(shù)據(jù)中心中的物理主機是同構的,且每個云數(shù)據(jù)中心中的主機個數(shù)是常量,所以針對啟發(fā)式算法而言,首次適應算法FFA和最好適應算法BFA的實驗結果應該是一樣的,所以我們的實驗結果統(tǒng)計主要針對于RRA、WFA、BFA、NFA 四類算法.

表1 云客戶端配置

表2 云數(shù)據(jù)中心中的物理節(jié)點配置

表3 應用程序端的虛擬機需求情況

3.2 云數(shù)據(jù)中心的數(shù)量測試

表4顯示了隨著虛擬機數(shù)目的增加,被分配了云數(shù)據(jù)中心的個數(shù)的變化情況,從表可以看出,NFA,BFA及RAA 三類啟發(fā)式算法DCs隨著虛擬機的個數(shù)的增加而增加,但是在WFA 算法中,云數(shù)據(jù)中心的個數(shù)一直保持在4 個,這說明每個云服務器都被分配了虛擬機.得到這個實驗結果的原因是WFA 算法一直會分配虛擬機到那些擁有最大數(shù)量物理資源的數(shù)據(jù)中心.

表4 云數(shù)據(jù)中心個數(shù)隨的虛擬機請求的變化(單位:個)

因此,每個虛擬機被放置到數(shù)據(jù)中心的時候,它將都被訪問到,進一步觀察結果可以得到,BFA 比NFA使用更加少的云數(shù)據(jù)中心個數(shù),這是因為在分配虛擬機的時候,BFA 算法首先考慮的是云數(shù)據(jù)中心,而NFA算法往往首先考慮的是數(shù)據(jù)中心中的之前的虛擬機分配情況.

3.3 云數(shù)據(jù)中心的整體代價測試

表5顯示了隨著虛擬機請求數(shù)量的變化,云平臺的整體資源參數(shù)dcprice的變化.由于表4已經(jīng)表明被分配虛擬機的云數(shù)據(jù)中心數(shù)量是隨著虛擬機請求個數(shù)的增加,基于這個事實,價值向量dcpricevector也就是系統(tǒng)所包含的軟硬件資源數(shù)量也是隨著云數(shù)據(jù)中心的增加而增加,整個系統(tǒng)的總體資源可以通過式(13)進行計算.

如果VMi被分配到了DCj中,這里有Vij=1.

表5 云數(shù)據(jù)中心總價值向量隨著的虛擬機請求個數(shù)的變化

表5的結果表明BFA 啟發(fā)式算法比NFA 算法隨著虛擬機請求數(shù)量的變化,它增加得比較緩慢,它們之間的差異幾乎可以忽略;RAA 算法和WFA 算法的總體價值是不一致的,因為總體價值主要依賴于虛擬機請求被分配到的一個具體云數(shù)據(jù)中心.

3.4 系統(tǒng)整體能量消耗測試

表6顯示了隨著虛擬機個數(shù)請求變化,云平臺的總體能量消耗情況,能量消耗的通過式(6)進行計算,和表4和表5比較起來,BFA和WFA 兩個被優(yōu)化的貪心算法之間的差異不是很大,得到這種結果的原因是能量消耗的大小主要依賴于一個具體的云數(shù)據(jù)中心的利用效率,而不是云數(shù)據(jù)中心的被分配個數(shù);WFA和RA 兩個算法中云數(shù)據(jù)中心的利用效率要低于NFA和BFA 算法.NFA和BFA 算法中的云數(shù)據(jù)中心的資源利用效率比較高;整體來所能量消耗都是隨著虛擬機請求個數(shù)的增加而增加.

3.5 目標函數(shù)代價測試

表7顯示了隨著虛擬機請求個數(shù)的增加,系統(tǒng)的總體的代價函數(shù)值overallfnDC變化情況.overallfnDC主要通過式(8)來進行計算,同時滿足式(9)～式(12)的約束條件,overallfnDC主要考慮了2 類約束條件,能量TEC和總體價值dcprice.如果兩個權重值都設置為0.5,那么能量TEC和總價值fnDC都平衡考慮.

從表7中可以看出,如果既考慮云數(shù)據(jù)中心的數(shù)量也考慮云數(shù)據(jù)中心的使用效率,那么BFA和WFA兩個算法的差異比較小.NFA和FFA 算法的差異要小于WFA和RAA 算法,因為DCs中被使用的個數(shù)也具有差異.

表6 云數(shù)據(jù)中心能量消耗隨著的虛擬機請求個數(shù)的變化(單位:kWh)

表7 云數(shù)據(jù)中心總體價值隨著的虛擬機請求個數(shù)的變化

所有上面的實驗結果圖都顯示BFA 最好適應算法在跨云數(shù)據(jù)中心的虛擬機分配的啟發(fā)式算法中具有比較好的性能.

4 結論與展望

本文運用貪心算法優(yōu)化了傳統(tǒng)的虛擬機分配算法,云數(shù)據(jù)中心的物理節(jié)點規(guī)模將持續(xù)不斷擴大,這樣將導致能量消耗的增加和資源規(guī)模總價值的增加,本文主要考慮了這兩個重要參數(shù),討論了虛擬機分配的三類主要約束條件.但是隨著云平臺上的應用程序的種類增加和可用性的需求,為了完成高服務質量QoS的需求,云數(shù)據(jù)中心的虛擬機分配需要考慮更加多的維度,這個是本文的后續(xù)工作.