許建豪

(南寧職業(yè)技術(shù)學(xué)院 信息工程學(xué)院，廣西 南寧 530008)

?

云計(jì)算中基于拍賣的虛擬機(jī)動(dòng)態(tài)供應(yīng)和分配算法

許建豪

(南寧職業(yè)技術(shù)學(xué)院 信息工程學(xué)院，廣西 南寧 530008)

摘要：當(dāng)前云計(jì)算供應(yīng)商通過定價(jià)算法或類似拍賣的算法來分配虛擬機(jī)(virtual machine,VM)。針對這些算法大多要求虛擬機(jī)靜態(tài)供應(yīng)，無法準(zhǔn)確預(yù)測用戶需求，導(dǎo)致資源未得到充分利用的問題，提出一種基于組合拍賣的虛擬機(jī)動(dòng)態(tài)供應(yīng)和分配算法，在做出虛擬機(jī)供應(yīng)決策時(shí)考慮用戶對虛擬機(jī)的需求。該算法將可用的計(jì)算資源看成是“流體”資源，且這些資源根據(jù)用戶請求可分為不同數(shù)量、不同類型的虛擬機(jī)實(shí)例。然后可根據(jù)用戶的估價(jià)決定分配策略，直到所有資源分配完畢?；诓⑿泄ぷ髫?fù)載存檔(parallel workload archive，PWA)的真實(shí)工作負(fù)載數(shù)據(jù)進(jìn)行了仿真實(shí)驗(yàn)，結(jié)果表明該方法可保證為云供應(yīng)商帶來更高收入，提高資源利用率。

關(guān)鍵詞：云計(jì)算；虛擬機(jī)實(shí)例；拍賣；分配；云供應(yīng)商；資源利用率

0引言

云計(jì)算系統(tǒng)所提供的未來計(jì)算基礎(chǔ)設(shè)施使得用戶可以為他們的計(jì)算需求分配更多的遠(yuǎn)程資源，節(jié)約了自己建立系統(tǒng)所需的前期成本。云供應(yīng)商將他們的資源以多種類型虛擬機(jī)(virtual machine,VM)實(shí)例的方式供應(yīng)。然后，使用定價(jià)策略來分配和出售VM實(shí)例[1]，使用拍賣算法來出售定價(jià)之后仍然閑置的資源。云供應(yīng)商希望分配算法能夠支持動(dòng)態(tài)供應(yīng)，以便他們根據(jù)市場需求就不同類型的VM實(shí)例數(shù)量做出決策。

多篇文獻(xiàn)對虛擬機(jī)的動(dòng)態(tài)供應(yīng)和分配問題進(jìn)行了研究。文獻(xiàn)[2]設(shè)計(jì)了一種在線虛擬機(jī)動(dòng)態(tài)供應(yīng)和分配算法。在該算法下，每當(dāng)有足夠多的資源和合適的申請，就會(huì)分配VM實(shí)例。然而，該算法在運(yùn)行時(shí)需要收集一段時(shí)間內(nèi)所有用戶請求的所有信息。文獻(xiàn)[3]為了改善云采購平臺(tái)中的顧客滿足情況。提出了載有虛擬供應(yīng)商資源的虛擬機(jī)分配流程，并且建立模型；然后分別采用最佳遞減匹配(best fit decrease, BFD)方法和儀跟蹤多群粒子群優(yōu)化(finder-tracker multi-swarm particle swarm optimization，F(xiàn)TMPSO)算法對其求解。然而該方法還存在很多不足，例如對于需求到達(dá)的模擬過于粗糙，對虛擬機(jī)遷移的成本沒有過多的考慮。文獻(xiàn)[4]分析和研究了Xen 虛擬機(jī)管理器的Credit調(diào)度算法的不足，提出了改進(jìn)的調(diào)度算法對虛擬機(jī)進(jìn)行Credit比例預(yù)分配，采用動(dòng)態(tài)調(diào)度時(shí)間片機(jī)制,以非工作保留模式(non-work-conserving)實(shí)現(xiàn)軟實(shí)時(shí)任務(wù)周期調(diào)度。然而，Credit值更新會(huì)受到更新時(shí)間片長度、虛擬機(jī)數(shù)量、虛擬機(jī)權(quán)重等影響，響應(yīng)性能受到限制，系統(tǒng)的公平性無法保證。文獻(xiàn)[5]提出基于組合拍賣的近似策略(combinatorial auction-greedy，CA-GREEDY)，并證明了基于組合拍賣的機(jī)制是虛擬機(jī)拍賣問題的最優(yōu)求解策略。雖然該策略可以提高虛擬機(jī)實(shí)例的分配效率及云供應(yīng)商的收入，但是該策略要求虛擬機(jī)實(shí)例已經(jīng)供應(yīng)完畢且不會(huì)再變，資源未得到充分利用。

為此，本文描述了虛擬機(jī)動(dòng)態(tài)供應(yīng)和分配問題，提出一種基于組合拍賣的求解算法。該算法可保證為云供應(yīng)商帶來更高收入，提高資源利用率。文中還分析了運(yùn)行本文算法時(shí)的成本和效益，并給出部署指導(dǎo)原則。最后基于并行工作負(fù)載存檔(parallel workload archive，PWA)[6]的真實(shí)工作負(fù)載數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)，評(píng)估了本文方法的有效性。

1虛擬機(jī)動(dòng)態(tài)供應(yīng)和分配問題

假設(shè)連續(xù)2次拍賣的時(shí)間間隔為一個(gè)時(shí)間單位。設(shè)cR和cI表示一個(gè)VM1實(shí)例在一個(gè)單位時(shí)間內(nèi)處于運(yùn)行狀態(tài)和空閑狀態(tài)時(shí)的成本。很顯然，有cR>cI。云供應(yīng)商運(yùn)行所有可用資源的成本(即所有M個(gè)VM1實(shí)例)為M·cR，而使所有可用資源處于空閑狀態(tài)的成本為M·cI。本文用x=(x1,x2,…,xn)表示分配向量，其中如果用戶uj請求的批量實(shí)例被分配給該用戶，則xi=1，否則xi=0。已知一個(gè)具體的分配向量和支付費(fèi)用，云供應(yīng)商的收益為

(1)

(2)

文獻(xiàn)[7]已經(jīng)證明，相比于當(dāng)前的固定價(jià)格機(jī)制，組合拍賣機(jī)制可提高虛擬機(jī)實(shí)例的分配效率和收益。然而該文獻(xiàn)研究的組件拍賣機(jī)制要求虛擬機(jī)已經(jīng)提前分配完畢。本文認(rèn)為，如果在拍賣時(shí)對虛擬機(jī)實(shí)例實(shí)行仔細(xì)的動(dòng)態(tài)選擇，以反映當(dāng)時(shí)的市場需求，則可提升系統(tǒng)的總體性能。

2基于組合拍賣的虛擬機(jī)實(shí)例動(dòng)態(tài)供應(yīng)和分配機(jī)制

本節(jié)提出求解DVMPA問題的組合拍賣算法(combinationalauctionalgorithm-dynamicvmprovisioningandallocation，CAM-DVMPA)。通過確定云供應(yīng)商需要供應(yīng)的虛擬機(jī)的分配策略、價(jià)格和最優(yōu)配置來提高收益。該算法可以確定獲勝用戶需要支付的價(jià)格以及為了滿足獲勝用戶的要求需要供應(yīng)的虛擬機(jī)實(shí)例集合。該算法可同時(shí)保證被分配的資源數(shù)量最大，且虛擬機(jī)實(shí)例分配時(shí)價(jià)格不低于底價(jià)。

CAM-DVMPA的具體過程見算法1。該算法需要部分系統(tǒng)信息，以便云供應(yīng)商在供應(yīng)資源時(shí)將計(jì)算資源總量M表示為VM1虛擬機(jī)總量。該機(jī)制同時(shí)需要可用的虛擬機(jī)類型數(shù)m及其權(quán)重向量w。它還需要知道VM1虛擬機(jī)實(shí)例的運(yùn)行成本cR及空閑成本cI。

算法1CAM-DVMPA算法

輸入：M;m;wj:j=1,…,n;cR,cI;

輸出：W;pj:j=1,…,n;ki:i=1,…,m;

1：{階段1：收集出價(jià)}

2：forj=1,…,ndo

4：endfor

5：{階段2：確定獲勝用戶和供應(yīng)策略}

6：W←? {獲勝用戶集合}

7：υres←cR-cI

8：增添出價(jià)為B0=(1,0,0,…,0,υres)的虛擬用戶u0

9：forj=0,…,ndo

11：dj←υj/sj{‘出價(jià)密度’}

12：endfor

13：對用戶u1,…,un重新排序，于是有d1≥d2≥…≥dn

14：設(shè)l表示索引，于是當(dāng)j≤l時(shí)dj≥d0，否則dj

15：排除用戶ul+1,…,un

16：將用戶u0重命名為ul+1

17：設(shè)置n←l+1

18：n←l+1

19：forj=1,…,n-1do{排除虛擬用戶}

20：ifsj≤Rthen

21：W←W∪uj

22：R←R-sj

23：endif

24：endfor

25：fori=1,…,mdo{確定虛擬機(jī)配置}

27：endfor

28：{階段3：支付}

29：for所有的uj∈Wdo

32：pj←dlsj

33：endfor

34：for所有uj?Wdo

35：pj←0

36：endfor

37：返回(W,p,k)

CAM-DVMPA分為3個(gè)階段。在第1階段，它收集用戶的出價(jià)Bj(第1至4行)。在階段2，該機(jī)制確定云供應(yīng)商需要供應(yīng)的虛擬機(jī)配置及獲勝出價(jià)方。具體為：它增加一個(gè)虛擬用戶u0，出價(jià)內(nèi)容包括1個(gè)VM1實(shí)例，出價(jià)為υres=cR-cI(第8行)。該虛擬用戶只用于模擬支持底價(jià)的拍賣模型，不會(huì)被分配任何資源。然后，它將計(jì)算所有用戶的批量資源規(guī)模sj及出價(jià)密度dj(第9—12行)。此后，除了虛擬用戶外的所有用戶按照出價(jià)密度降序排列，dj

此后，算法采用貪婪策略確定獲勝用戶。只要有資源可用，那么便按照出價(jià)密度降序向用戶分配他們所請求的批量資源。然而，在分配時(shí)不考慮虛擬用戶。確定了獲勝用戶后，該算法將聚集獲勝用戶請求的批量資源，確定需要分配給用戶們的虛擬機(jī)配置(第25—27行)。

在第3階段，算法確定所有用戶的支付價(jià)格。對每個(gè)獲勝用戶uj，算法尋找失敗用戶ul(如果uj不參與，則ul將獲勝)。然后，用戶uj的支付費(fèi)用計(jì)算為其批量資源規(guī)模sj與ul的出價(jià)密度之積。所有失敗用戶支付費(fèi)用為0。這種支付類型通常稱為臨界支付。

3理論分析

本文中如果用戶通過為批量虛擬機(jī)表達(dá)自己的真實(shí)估價(jià)來實(shí)現(xiàn)其效用最大化，則稱該機(jī)制具有真實(shí)性。其中，用戶uj的效用表示為用戶uj對批量虛擬機(jī)的估價(jià)υj及為了使用該批虛擬機(jī)而向分配機(jī)制提交的支付費(fèi)用pj之差。因?yàn)閰⑴c真實(shí)的分配機(jī)制的用戶必須采用復(fù)雜的出價(jià)策略才能使其效用最大，所以上述特點(diǎn)非常重要。他們只需為批量虛擬機(jī)提交自己的真實(shí)估價(jià)即可。文獻(xiàn)[8]指出，如果分配功能具有單調(diào)性，且支付過程屬于臨界支付，則該分配機(jī)制具有真實(shí)性。該描述有助于我們證明定理1。

定理1CAM-DVMPA是真實(shí)的

證明首先證明，CAM-DVMPA分配具有單調(diào)性。用戶通過增加其出價(jià)的密度就可以增加申請成功的概率。提交的估價(jià)越大，密度越大；批量虛擬機(jī)規(guī)模越大，密度越小。于是，用戶若想在CAM-DVMPA進(jìn)行分配決策時(shí)用到的排序表上位置靠前，只能提高出價(jià)或降低批量虛擬機(jī)申請規(guī)模。因此，CAM-DVMPA分配具有單調(diào)性。其次，根據(jù)CAM-DVMPA的支付方式，用戶需要為其申請的批量虛擬機(jī)支付一定費(fèi)用，以便單位虛擬機(jī)實(shí)例的平均價(jià)格等于其臨界支付費(fèi)用。用戶只是支付了贏取申請所需要的最小費(fèi)用。單調(diào)分配和臨界支付特點(diǎn)保證CAM-DVMPA具有真實(shí)性。底價(jià)不會(huì)影響分配機(jī)制的真實(shí)性，因?yàn)榈變r(jià)基本只是虛擬用戶的出價(jià)，而虛擬用戶受云供應(yīng)商控制，所以真實(shí)出價(jià)仍然是用戶的主要策略。證畢。

下面分析CAM-DVMPA的復(fù)雜性。算法1的主要計(jì)算負(fù)載來自第19-24行和29-33行循環(huán)。第1個(gè)循環(huán)的最大復(fù)雜性為O(M)，即：所有獲勝用戶所申請的批量實(shí)例均只包含1個(gè)單位的VM1實(shí)例。第29-33行循環(huán)的總運(yùn)行時(shí)間為O(n)。這是因?yàn)樗鼘Λ@勝用戶進(jìn)行循環(huán)操作，對失敗用戶進(jìn)行搜索操作。因?yàn)橐呀?jīng)對用戶排序，所以獲勝用戶uj+1的臨界支付搜索實(shí)際上是從uj的“臨界支付用戶ul”處開始(不失一般性，我們假設(shè)此時(shí)uj和uj+1為獲勝方)。因此，該循環(huán)的總體最大復(fù)雜性為O(n)，其中第13行的排序復(fù)雜度為O(nlogn)。于是，CAM-DVMPA機(jī)制的復(fù)雜性為O(M+nlogn)。

4仿真實(shí)驗(yàn)

本文利用真實(shí)的工作負(fù)載數(shù)據(jù)進(jìn)行全面的仿真實(shí)驗(yàn)，來評(píng)估CAM-DVMPA機(jī)制的性能。比較CAM-DVMPA與基于虛擬機(jī)靜態(tài)分配的組合拍賣策略(combinatorialauction-greedy，CA-GREEDY)[5]的性能。文獻(xiàn)[5]的研究已經(jīng)證明，CA-GREEDY與當(dāng)前云供應(yīng)商采用的固定價(jià)格虛擬機(jī)分配機(jī)制[9-10]的性能相比，CA-GREEDY的性能遠(yuǎn)優(yōu)于固定價(jià)格機(jī)制，因此在本文實(shí)驗(yàn)中采用該機(jī)制作為比較對象。利用并行工作負(fù)載存檔[9]中的11種工作負(fù)載日志共進(jìn)行264次實(shí)驗(yàn)，其中每個(gè)工作負(fù)載有24種不同的參數(shù)組合。

4.1實(shí)驗(yàn)配置

實(shí)驗(yàn)內(nèi)容主要從已知的工作負(fù)載中生成作業(yè)提交，然后同時(shí)運(yùn)行CA-GREEDY和CAM-DVMPA來分配作業(yè)并供應(yīng)虛擬機(jī)。在配置實(shí)驗(yàn)時(shí)還要處理工作負(fù)載選擇、申請生成及建立拍賣等問題。

1)工作負(fù)載選擇：利用文獻(xiàn)[6]中的并行工作負(fù)載存檔負(fù)載。該存檔包括許多網(wǎng)格和超級(jí)計(jì)算站點(diǎn)收集而來的大量工作負(fù)載。表1中給出了工作負(fù)載的部分統(tǒng)計(jì)數(shù)據(jù)。

表1　負(fù)載日志的統(tǒng)計(jì)數(shù)據(jù)

2)作業(yè)和出價(jià)生成：為日志文件中的每條記錄，生成一個(gè)作業(yè)，用戶需要運(yùn)行該作業(yè)并為該作業(yè)生成一個(gè)出價(jià)。然后，需要為作業(yè)生成2個(gè)重要參數(shù)：請求的批量虛擬機(jī)及相應(yīng)出價(jià)。為了生成作業(yè)的批量虛擬機(jī)實(shí)例，根據(jù)(3)式確定其通信與計(jì)算比。

(3)

(3)式可衡量有多少運(yùn)行時(shí)間花費(fèi)于給定作業(yè)的進(jìn)程之間的通信上。以該值為基礎(chǔ)，可確定作業(yè)的類別，其中共有m種類別，m表示可用的虛擬機(jī)類別數(shù)量。作業(yè)的類別指定了該作業(yè)的“首選”虛擬機(jī)類型。用因子μ描述被請求的總體虛擬機(jī)中有多少屬于“首選”類型的虛擬機(jī)實(shí)例。例如，請求qj個(gè)處理器的類別為i的作業(yè)將會(huì)生成一個(gè)批量的虛擬機(jī)，該批量由一定數(shù)量的VMi實(shí)例構(gòu)成，以便分配μqj個(gè)處理器。通過隨機(jī)選擇其他虛擬機(jī)類型來請求剩余處理器。生成批量虛擬機(jī)后，將生成相應(yīng)的出價(jià)。為此，定義作業(yè)的加速因子為

(4)

該加速因子與“估價(jià)因子”相乘，即可生成出價(jià)。估價(jià)因子與用戶類型有關(guān)。利用用戶的ID號(hào)與5的模數(shù)將用戶劃分為5種類別。為作業(yè)設(shè)置的最后一個(gè)參數(shù)是其截止時(shí)間，此時(shí)工作負(fù)載日志內(nèi)無信息提供。假設(shè)截止時(shí)間為完成作業(yè)所需時(shí)間的4-8倍。因此，將一個(gè)作業(yè)的截止時(shí)間設(shè)置為4-8的隨機(jī)數(shù)與所需時(shí)間之積。

對可以運(yùn)行的作業(yè)并行且獨(dú)立地運(yùn)行CA-GREEDY和CAM-DVMPA機(jī)制。用戶(或作業(yè))參與拍賣，直到其作業(yè)完成或確定其作業(yè)在截止時(shí)間前無法完成。如果其作業(yè)完成，則認(rèn)為用戶“被服務(wù)”，否則便“未被服務(wù)”。不失一般性，假設(shè)每個(gè)用戶只提交一項(xiàng)作業(yè)，于是在下文中“用戶”與“作業(yè)”可互用。

3)拍賣設(shè)置：假設(shè)云供應(yīng)商提供4種不同類型的虛擬機(jī)：VM1,VM2,VM3,VM4。這些虛擬機(jī)類型由權(quán)重向量w=(1,2,4,8)描述。對每個(gè)負(fù)載文件，提取用戶總數(shù)N及可用的處理器總數(shù)M。隨著拍賣的進(jìn)行，動(dòng)態(tài)確定參與一次拍賣的用戶數(shù)量。

本文在生成一個(gè)用戶提交的作業(yè)所需的批量虛擬機(jī)時(shí)，只配置了幾個(gè)參數(shù)。向量(C1,C2,C3)確定了用于描述作業(yè)情況的通信比。如果(C1,C2,C3)=(0.05,0.15,0.25)即通信比低于0.05的作業(yè)屬于類型1，所需要的大部分虛擬機(jī)實(shí)例μqj將請求VM1，其中，qj表示uj請求的處理器數(shù)量。假設(shè)μ取值0.5和0.75。利用其余類型的虛擬機(jī)實(shí)例來隨機(jī)確定其余批量虛擬機(jī)。利用日志文件的用戶ID字段來確定用戶的估價(jià)范圍。有5種類型的用戶提交作業(yè)。用戶的類型t計(jì)算方法為(用戶ID)%5。日志的用戶ID為實(shí)數(shù)，因此這種分類方法實(shí)際上可生成用戶的分布。用戶的每種類型t關(guān)聯(lián)一個(gè)“估價(jià)因子”ft。確定用戶屬于類型t后，利用加速因子及向量f的“估價(jià)向量”ft，即可確定用戶對批量虛擬機(jī)的估價(jià)。向量f有5個(gè)元素(等于用戶類型數(shù))，每個(gè)元素表示該類型的用戶對“每個(gè)單位的加速因子”的平均估價(jià)。具體來說，假設(shè)有用戶uj，其作業(yè)的加速因子為Sj，則如果uj屬于類型t，則該用戶為了能夠在一個(gè)小時(shí)內(nèi)使用其申請的批量虛擬機(jī)，平均愿意支付ftSj。在(0，2ft)生成一個(gè)隨機(jī)數(shù)，然后與Sj相乘以生成均值為ftSj的估價(jià)。本文使用2組f向量，如表2所示。

表2　仿真參數(shù)

CAM-DVMPA機(jī)制本身就可確定云供應(yīng)商需要供應(yīng)的虛擬機(jī)的配置，而CA-GREEDY假設(shè)虛擬機(jī)靜態(tài)供應(yīng)，因此需要提前供應(yīng)虛擬機(jī)配置。為了生成CA-GREEDY需要的虛擬機(jī)靜態(tài)供應(yīng)，使用的向量h，在仿真中假設(shè)有2個(gè)h實(shí)例。第1個(gè)為h=(0.07,0.13,0.27,0.53)，可保證已知權(quán)重向量w后，每種類型的虛擬機(jī)實(shí)例數(shù)量相等或基本相等。另一個(gè)為h=(0.25,0.25,0.25,0.25)，可保證所有的處理器均衡分布給不同類型的虛擬機(jī)。在表2中給出了所有的仿真參數(shù)。通過對數(shù)值進(jìn)行全面組合，我們對每個(gè)日志文件實(shí)驗(yàn)24次，共計(jì)264次實(shí)驗(yàn)。

4.2結(jié)果分析

下面分析了不同負(fù)載條件下2種算法的性能。因?yàn)楣ぷ髫?fù)載在多個(gè)維度上均是異質(zhì)負(fù)載，所以首先定義一個(gè)指標(biāo)來描述工作負(fù)載，以便確定它們的次序。然后，對分配機(jī)制的性能指標(biāo)正規(guī)化，比較它們相對于工作負(fù)載特征的性能。觀察表1中列出的負(fù)載特點(diǎn)可以確定，對工作負(fù)載進(jìn)行比較的最優(yōu)指標(biāo)是正規(guī)化負(fù)載，定義為

每小時(shí)的作業(yè)數(shù)量×平均運(yùn)行時(shí)間×每個(gè)作業(yè)的平均處理器數(shù)量/總處理器數(shù)量

(5)

每小時(shí)的作業(yè)數(shù)量乘以每個(gè)作業(yè)的平均處理器數(shù)量可以獲得每小時(shí)期間作業(yè)需要的處理器數(shù)量。然后再與平均運(yùn)行時(shí)間相乘即獲得一個(gè)小時(shí)期間所有作業(yè)請求的處理器平均數(shù)量估計(jì)值。正規(guī)化負(fù)載可為我們提供負(fù)載集合的排序。

對每組仿真實(shí)驗(yàn)，計(jì)算生成的總營收、總成本及每次拍賣產(chǎn)生的總收益。但是生成工作負(fù)載時(shí)的系統(tǒng)時(shí)間不同，處理器數(shù)量也不同。因此，對每小時(shí)每個(gè)處理器的收益定義為

(6)

類似地，可以定義每個(gè)處理器每小時(shí)營收及每個(gè)處理器每小時(shí)成本。

我們在圖1a-圖1c中分別給出了不同負(fù)載日志條件下的平均營收、平均成本和平均收益。圖1中的負(fù)載按照其正規(guī)化負(fù)載升序排列。大部分情況下，CAM-DVMPA算法創(chuàng)造的營收更高。對不小于1.44的正規(guī)化負(fù)載，CAM-DVMPA的營收穩(wěn)步上升，比CA-GREEDY高出40%。于是我們得出結(jié)論，對資源的需求越高，CAM-DVMPA創(chuàng)造的營收越高。

從圖1b可以發(fā)現(xiàn)，無論負(fù)載情況如何，CAM-DVMPA的總成本均比較高。因?yàn)镃AM-DVMPA是動(dòng)態(tài)確定虛擬機(jī)的數(shù)量，所以在拍賣時(shí)如果申請方相同，則CAM-DVMPA分配的處理器數(shù)量高于CA-GREEDY。由于處理器運(yùn)行時(shí)成本較高(cR>cI)，所以分配的處理器越多，生成的總成本也越高。從圖1c可以看出，當(dāng)正規(guī)化負(fù)載大于1.44時(shí)，CAM-DVMPA的收益始終高于CA-GREEDY，且收益間的差異迅速增大。我們也發(fā)現(xiàn)，當(dāng)負(fù)載因子低于1.44時(shí)，CAM-DVMPA和CA-GREEDY分別領(lǐng)先于對方的情況數(shù)量相等。這表明當(dāng)負(fù)載較低時(shí)，分配機(jī)制的效果取決于其他參數(shù)。

在圖2和圖3中，我們比較了2種分配算法的資源利用率和被服務(wù)用戶比例。CAM-DVMPA在這兩方面的指標(biāo)數(shù)值更高。從圖2中可以看到，在大部分情況下，二者的資源利用率相差30%左右。這就是說，如果我們從靜態(tài)分配策略轉(zhuǎn)向動(dòng)態(tài)供應(yīng)和分配策略，則在這方面可獲得顯著的性能提升。因?yàn)槿藗円呀?jīng)認(rèn)可組合拍賣策略在提高分配效率方面的效果，將其與動(dòng)態(tài)供應(yīng)結(jié)合起來即可提高云計(jì)算資源分配機(jī)制的效率。

圖1　CAM-DVMPA和CA-GREEDY的性能比較Fig.1　Performance Comparison of CAM-DVMPA and CA-GREEDY

從圖3中可以看到，CAM-DVMPA可使更多的用戶被服務(wù)，因?yàn)樘摂M機(jī)實(shí)例不是靜態(tài)供應(yīng)。因此，如果無VM1實(shí)例可用但是有VM2實(shí)例可用，此時(shí)若采用CA-GREEDY則申請2個(gè)VM1實(shí)例的用戶將申請失敗，但是若采用CAM-DVMPA則該用戶將申請成功。原因在于，CAM-DVMPA將可用資源看成是2個(gè)VM1實(shí)例的等價(jià)計(jì)算資源，因此如果有用戶申請2個(gè)VM1實(shí)例或者申請1個(gè)VM2實(shí)例，則CAM-DVMPA會(huì)將可用資源分配給這些用戶，具體分配給哪個(gè)用戶取決于哪個(gè)用戶的估價(jià)更高。這種機(jī)制可使CAM-DVMPA服務(wù)更多的CA-GREEDY用戶。

圖2　不同正規(guī)化負(fù)載條件下CAM-DVMPA和CA-GREEDY的資源利用率Fig.2　Resourse utilization of CAM-DVMPA and CA-GREEDY under different load conditions

圖3　不同正規(guī)化負(fù)載條件下CAM-DVMPA和CA-GREEDY的服務(wù)用戶比Fig.3　Service user ratio of CAM-DVMPA and CA-GREEDY under different load conditions

總的來說，當(dāng)供需匹配時(shí)，CA-GREEDY的營收更高。如果拍賣期間的資源不像云拍賣那樣可配置， CA-GREEDY拍賣的效率也較高。但是如果資源像云拍賣那樣可配置，則難以提前準(zhǔn)確預(yù)測需求。此時(shí)，更應(yīng)采用CAM-DVMPA機(jī)制，隨著當(dāng)今技術(shù)的發(fā)展，該機(jī)制可部署為一種無需大量人工干預(yù)的獨(dú)立配置和分配工具。CAM-DVMPA算法還有另一種用途?？梢詫AM-DVMPA和CA-GREEDY結(jié)合起來，周期性地運(yùn)行CAM-DVMPA以確定當(dāng)前的市場需求，確定與需求最匹配的靜態(tài)分配策略，然后運(yùn)行CA-GREEDY。如果資源利用率低于某一閾值，則調(diào)用CAM-DVMPA以便再次確定高性能資源配置。這可避免確定CA-GREEDY的高效率靜態(tài)配置時(shí)進(jìn)行詳細(xì)的統(tǒng)計(jì)分析。

5結(jié)論

本文研究了云環(huán)境下虛擬機(jī)實(shí)例的動(dòng)態(tài)供應(yīng)問題，以便在確定基于組件拍賣的虛擬機(jī)分配策略時(shí)提高收益。我們提出CAM-DVMPA機(jī)制以解決這一問題。利用真實(shí)的工作負(fù)載數(shù)據(jù)進(jìn)行了全面的仿真實(shí)驗(yàn)，評(píng)估了本文方法的性能。結(jié)果表明，CAM-DVMPA可有效確定市場需求，并針對需求供應(yīng)計(jì)算資源，尤其是在需求較高時(shí)可提高云供應(yīng)商的營收。我們認(rèn)為本文算法是云環(huán)境下VM實(shí)例分配和供應(yīng)技術(shù)的良好選擇。在下一步工作中，我們打算建立一個(gè)私有云并在上面部署上述系統(tǒng)。

參考文獻(xiàn)：

[1]劉正偉, 文中領(lǐng),張海濤. 云計(jì)算和云數(shù)據(jù)管理技術(shù) [J]. 計(jì)算機(jī)研究與發(fā)展, 2012, 49(1): 26-31.

LIU Zhengwei, WEN Zhongling, ZHANG Haitao. Research and development of cloud computing and cloud data management technology, 2012, 49 (1): 26-31.

[2]張麗敏. 云計(jì)算中一種高效的虛擬機(jī)在線動(dòng)態(tài)分配算法[J]. 電信科學(xué), 2015, 31(4): 14-19.

ZHANG Limin. Cloud computing in an efficient online virtual machine dynamic allocation algorithm[J]. Telecom Science, 2015, 31(4): 14-19.

[3]黃莉，丁一，姚錦元，等. 云采購平臺(tái)虛擬供應(yīng)商資源動(dòng)態(tài)分配[J]. 計(jì)算機(jī)應(yīng)用，2014, 34(2): 377-381.

HUANG Li, DING Yi, YAO Jinyuan, et al. Dynamic allocation of resources for the virtual supplier of cloud platform[J].computer applications,34,2014(2):377-381.

[4]丁曉波，馬中，戴新發(fā)，等. 一種基于資源預(yù)分配的虛擬機(jī)軟實(shí)時(shí)調(diào)度方法[J]. 計(jì)算機(jī)工程與科學(xué)，2015,37(5)：865-872.

DING Xiaobo, MA Zhong, DAI ,Xinfa， et al. A software real-time scheduling method for virtual machines based on resource pre allocation [J]. computer engineering and science, 2015,37 (5):865-872.

[5]ZAMAN S, GROSU D. Combinatorial auction-based allocation of virtual machine instances in clouds [J]. Journal of Parallel and Distributed Computing, 2013, 73(4): 495-508

[6]KRAKOV D, FEITELSON D G. High-resolution analysis of parallel job workloads[C]∥Job Scheduling Strategies for Parallel Processing. Berlin Heidelberg: Springer, 2013, 178-195

[7]師雪霖, 徐恪. 云虛擬機(jī)資源分配的效用最大化模型[J]. 計(jì)算機(jī)學(xué)報(bào), 2013, 36(2): 252-262.

SHI, Xuelin， XUKe，The utility maximization model [J]. Chinese Journal of computers, cloud virtual machine resource allocation 2013, 36 (2): 252-262.

[8]ROUGHGARDEN T. Algorithmic game theory [J]. Commun-ications of the ACM, 2010, 53(7): 78-86.

[9]賁飛,汪蕓.云計(jì)算下基于容錯(cuò)QoS的虛擬機(jī)資源分配策略[J].微電子學(xué)與計(jì)算機(jī),2013,12(3):33-35.

BEN Fei, WANG Yun. Cloud computing based on fault-tolerant QoS of the virtual machine resource allocation strategy [J]. Electronics and computer, 2013, 12 (3): 33-35.

[10] 謝文靜, 唐卓, 楊柳, 等. 基于隨機(jī)規(guī)劃的云計(jì)算中虛擬機(jī)分配優(yōu)化研究[J]. 計(jì)算機(jī)工程與科學(xué), 2012, 34(5): 95-100.

XIE Wenjing，TANG Zhuo, YANG Liu， et al. Based on stochastic programming of cloud computing in virtual machine allocation optimization [J]. Computer engineering and science, 2012, 34 (5): 95-100.

DOI：10.3979/j.issn.1673-825X.2016.04.021

收稿日期：2015-05-28

修訂日期：2016-06-08通訊作者：許建豪jhaos@163.com

基金項(xiàng)目：國家自然科學(xué)基金(61373010，F(xiàn)020501)；廣西高?？蒲许?xiàng)目(YB2014495)

Foundation Items：The National Natural Science Foundation of Chine(61373070,F020501); The Guangxi University Scientific Research Project(YB2014495)

中圖分類號(hào)：TP391

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1673-825X(2016)04-0585-08

作者簡介：

許建豪(1977-)，男，壯族，廣西天等人，副教授。主要研究方向?yàn)樵朴?jì)算、信息處理。

(編輯：張誠)

Virtual machine dynamic supply and allocation algorithm based on auction in cloud computing

XU Jianhao

(School of Information Engineering, Nanning College for Vocational Technology, Nanjing 530008, P.R.China)

Abstract:Current cloud computing providers allocate their virtual machine (VM) instances via fixed price-based or auction-like mechanisms. However, most of these algorithms require static supply virtual machine, and unable to accurately predict the user demand so as lead to underutilization of resources. Thus, an auction-based algorithm for dynamic VM provisioning and allocation is proposed that takes into account the user demand for VMs when making VM provisioning decisions in this paper. Which treats the set of available computing resource as ‘liquid’ resources that can be configured into different numbers and types of VM instances depending on the requests of the users, and the proposed algorithm determines the allocation strategy based on the users’ valuations until all resources are allocated. Our mechanism is evaluated by performing simulation experiments using traces of real workload from Parallel Workload Archive, the results show that the proposed method can guarantee brings the higher income for cloud providers, and improves the resource utilization rate.

Keywords：cloud computing; virtual machine instances; auction; allocation; cloud providers; resource utilization rate