徐友洪 李 杰,2

1(衢州職業(yè)技術學院信息工程學院 浙江 衢州 324000)2(武漢大學印刷與包裝系 湖北 武漢 430072)

0 引 言

云提供商將其資源提供給虛擬機(Virtual Machine,VM)實例，并將它們分配給特定時間段的用戶。提供、分配和定價這些VM實例是一個挑戰(zhàn)性課題，必須通過云提供商來解決。商業(yè)云提供商(如阿里云、騰訊云、百度云及天翼云計算)所采用的固定價格分配機制不能有效地分配VM實例，也不能對動態(tài)反映變化的用戶需求資源進行定價。經(jīng)濟學理論認為，當拍賣成本較低時，拍賣比固定價格機制更有效，因為產(chǎn)品與估價最高的客戶相匹配。特別地，基于組合拍賣的機制最適合云計算中的資源分配，這源于分配需求的特性。組合拍賣中的勝者決定是一個NP-Hard問題，因此要求解這種大量用戶和資源的問題相當費時。

文獻[1]設計了2種基于組合拍賣的貪婪算法即CA-貪婪算法作為VM實例分配，但假設VM實例是靜態(tài)提供的，即要求VM實例已經(jīng)配置好，不能更改。如果這種靜態(tài)機制不能準確地預測用戶需求，則會由于資源利用率不足而導致效率低下。文獻[3]提出了一種VM提供的分布式在線聚類算法，并提出了基于模型的方法來生成長期的工作負荷估計，但這種算法過于依賴工作負荷的特點，需要對工作負荷特性進行預測來捕獲當前的VM需求，這無疑限制了用戶的擴展并增加了分配機制的復雜性。為解決虛擬機調度分配的多目標優(yōu)化問題，文獻[4]提出了一種適用于云環(huán)境下虛擬機調度的優(yōu)化方法，這種提供機制主要支持云中科學應用的實現(xiàn)而限制了應用范圍。文獻[5]采用基于多代理的協(xié)商模型來處理網(wǎng)格資源所有者和網(wǎng)格資源使用者之間的交互，設計了市場和行為驅動的談判代理機制。測試結果表明，該協(xié)商模型能夠較好地實現(xiàn)協(xié)商決策和預算支出，存在的主要不足在于資源使用者和網(wǎng)格資源所有者必須交互協(xié)商，這種談判機制降低了資源的實時有效利用。文獻[6]針對云資源的在線分配進行了研究，建立基于拍賣的在線云資源分配機制，這種云資源定價模型存在擴展局限性。文獻[7]提出的資源市場分配和定價是采用計算資源的交換市場來確定的。在交換中，服務提供商和用戶表達他們的標價和出價，只有匹配正確才被準予分配，顯然降低了效率。文獻[8]研究了異構網(wǎng)絡中基于勢博弈和演進博弈的聯(lián)合資源分配算法，主要目標是實現(xiàn)無線資源和云資源的協(xié)調管理，而對資源提供商的經(jīng)濟利益考慮較少。文獻[9]提出了關于組合拍賣的基礎知識，未對組合拍賣的具體實施策略和機制進行深入研究。文獻[10-11]針對組合拍賣的復雜性和專一投標人的組合拍賣進行了研究，但僅考慮了勝者決定和貪婪組合拍賣，這僅對獲勝用戶有利，忽略了出價低的用戶，從而導致資源的分配不均。文獻[12-13]提出了在專一環(huán)境下真實機制設計的附加構建技術，但這種專一環(huán)境排除了大多數(shù)提供商和資源用戶的復雜環(huán)境，因而不具有可擴展性。文獻[14]提出了一種均衡價格拍賣機制，該機制為采購拍賣提供了近似解，但不能保證真實性。文獻[15]將資源分配問題構建為一種采購拍賣，該模型中，用戶向拍賣代理表達他們的需求，云提供商參與由代理運行的拍賣。這種機制假設存在幾個云提供商，拍賣在它們之間進行，但這種機制仍然不是真實的。

本文提出了一種用于云中動態(tài)虛擬機實例分配機制。該機制在作出分配決策時考慮了變化的用戶需求，還考慮了保留價格和確定的方法，并證明了其是真實的，即保證了一個參與用戶僅有通過投標其對VM包的真實估價來最大化其效用。最后通過采用來自于并行工作負荷存檔中的歸一化工作負荷進行大量的仿真實驗評價了本文算法的性能。實驗結果表明，本文提出的算法機制不僅能為云提供商帶來更高的收益，而且還提高了云資源的利用率。

1 問題建模

虛擬化技術允許云計算提供商將計算資源配置到幾乎所有不同類型VM的組合中，因此，可以通過組合拍賣確定VM實例的最佳組合，然后動態(tài)地提供。這將確?；谑袌鲂枨髞泶_定不同類型的VM實例數(shù)量，然后有效地分配給用戶。本文構建的動態(tài)VM提供和分配問題如下。

將m種有差別的VM實例VM1,VM2，…,VMm計算服務提供給用戶。一個VM實例類型VMi(i=1,2,…,m)的計算能力假設為wi，這里w1=1,w1

為了創(chuàng)建最小計算能力類型的M個VM實例，云提供商可以根據(jù)VM1,VM2,…,VMm給定的指定類型，以多種方式提供VM實例。將提供的VMi實例的數(shù)量表示為ki，則提供商可以提供由向量(k1,k2,…,km)給定的任意實例組合，只要：

(1)

(2)

考慮成本cR和cI的目的是在需求非常低或用戶估價過低時減少云提供商的損失。在這兩種情況下，通過拍賣將資源分配給用戶將導致用戶付費非常低，這將間接導致拍賣商的收入損失。正如后面將看到的，考慮這些成本有助于確定一個保留價格，以阻止出價極低的用戶參與拍賣，并隱含地保證提供商在需求低時仍能獲得一些利潤。

這樣，就可將動態(tài)VM提供和分配問題構建為：

maxΠ

(3)

(4)

xj∈{0,1}j=1,2,…,n

(5)

0≤pj≤vjj=1,2,…,n

(6)

目前的云服務提供商采用固定價格機制分配VM實例，且依賴于統(tǒng)計數(shù)據(jù)以靜態(tài)方式提供VM。而通過動態(tài)方式選擇VM實例集，反映了拍賣時的市場需求，可以提高系統(tǒng)的總體性能。因此，本文提出一種算法機制，通過確定云提供商需要提供的VM的分配、定價和最佳配置來求解云中動態(tài)VM提供和分配問題，以獲得更高的利潤和資源利用率。

2 動態(tài)虛擬機實例分配算法

2.1 算法原理及實現(xiàn)

本文提出的動態(tài)虛擬機實例分配算法簡稱為DVMIA(Dynamic Virtual Machine Instances Allocation)算法。算法決定獲勝用戶必須支付的價格，以及為滿足獲勝用戶需求需要提供的VM實例集，還確保分配最大可能的資源，并且任何VM實例都不會以低于保留價格的價格分配。

DVMIA算法采用投標密度來決定分配。用戶uj的投標密度定義為：

dj=vj/sj

(7)

DVMIA算法首先收集用戶的投標，計算出全部投標的投標密度，并根據(jù)他們的投標密度對投標進行排序，然后計算保留價格，并丟棄投標密度低于保留價格的投標；接下來將計算資源按排序分配給用戶，并提供相應的資源；最后，計算每個獲勝用戶的付款，即他們必須支付給云提供商的金額。付款是獲勝用戶為獲得其所要求的資源而必須出的最低價(即臨界支付)，全部失敗用戶的支付為零。算法1給出了DVMIA算法的實現(xiàn)原理。算法需要來自系統(tǒng)的一些信息，如計算資源總量M，表示為由云提供商可以提供的VM1類型的VM總數(shù)量，算法還需要輸入可用VM類型的數(shù)量m以及它們的權值向量w，還需要知道cR即運行一個VM1類型的VM實例的成本以及即保持一個VM1類型的VM實例空閑的成本cI。

算法1DVMIA算法

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

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

1.{階段一：收集投標}

2.forj=1,2,…,ndo

4.endfor

5.{階段二：勝者決定和提供}

6.W←?{勝者集合}

7.vres←cR-cI

8.添加投標B0=(1,0,0,…,0,vres)的虛擬用戶

9.forj=0,1,…,ndo

11.dj←vj/sj{計算投標密度}

12.endfor

13.重排序用戶u1,u2，…,un，以使d1≥d2≥…≥dn

14.令l為指標以使如果j≤l，dj≥d0，否則dj

15.丟棄用戶ul+1,…,un

16.重命名用戶u0為ul+1

17.n←l+1

18.M←R

19.forj=1,2，…,n-1do{刪除虛擬用戶}

20.ifsj≤Rthen

21.W←W∪uj

22.R←R-sj

23.endif

24.endif

25.fori=1,2,…,mdo{確定VM配置}

27.endfor

28. {階段三：支付}

29.for全部uj∈Wdo

32.pj←dlsj

33.endfor

34.for全部uj?Wdo

35.pj←0

36.endfor

37.return(W;pj:j=1,2,…,n;ki:i=1,2,…,m)

2.2 DVMIA算法創(chuàng)新特性分析

算法的一個重要創(chuàng)新就是激勵相容性，也稱為真實性，因為算法計算分配和支付是基于用戶報告的信息(即投標)，這是私人信息。一個理性的用戶可以通過投標虛假的估價來操縱這個機制，這樣對其有利。因此，設計這種算法的挑戰(zhàn)包括設計勝者決定和支付功能。支付功能給予用戶真實的投標激勵，因為參與真實分配的用戶不必采用復雜的投標策略來最大化他們的效用，他們只需要對VM包給出他們的真實估價。

(8)

也就是說，如果分配了所請求的包，則用戶uj將獲得vj的估價，否則，估價為0。用戶uj從獲得請求包中得到的效用是其估價Vj與付款pj之間的差值：

(9)

一般來說，用戶會基于理性來最大化他們的目標效用。一個真實的機制要確保一個用戶只有通過對包出價真實估價來最大化其效用。下面定義真實機制的概念。

(10)

也就是說，參與真實機制的用戶僅通過為競價其包的真實估價來最大化其效用，而不管其他用戶的出價。

即在臨界支付函數(shù)下，獲勝用戶支付其臨界值，而失敗用戶支付零，即該機制是一個規(guī)范化機制。

下面提出2個引理和1個定理來證明DVMIA算法是真實的。

引理1DVMIA算法實現(xiàn)一個單調的分配函數(shù)。

引理2DVMIA算法向獲勝用戶收取他們的臨界支付。

證明：為了得到獲勝用戶uj的支付，DVMIA算法要找到一個失敗用戶ul，當用戶uj不參與時，他會贏。這意味著用戶uj需要擊敗用戶ul，以獲得他所請求的包(即dj≥dl)，這也意味著vj/sj≥dl，因此vj≥dl·sj。DVMIA算法收取用戶uj的費用為pj=dl·sj，這是uj必須出價才能獲得他所請求的包的最低估價。失敗用戶支付零費用。因此，DVMIA算法實現(xiàn)了臨界支付。

定理1DVMIA算法是真實的。

證明：根據(jù)引理1和引理2，DVMIA算法實現(xiàn)了一個單調的分配函數(shù)，并向獲勝用戶收取他們的臨界支付，因此DVMIA算法是一個真實的機制。保留價格不影響機制的真實性，因為保留價格基本上是由云提供商控制的虛擬用戶提出的投標，而真實投標仍然是用戶的主導策略。

3 實 驗

本文采用來自網(wǎng)格和超級計算站點的并行工作負荷存檔中經(jīng)過歸一化的工作負荷進行仿真實驗來評價本文提出的DVMIA算法，并將其與文獻[1]提出的兩種基于組合拍賣的CA-貪婪算法進行比較。文獻[1]的原CA-貪婪算法采用靜態(tài)VM提供，其改進的CA-貪婪算法考慮了每種類型VM實例的預測需求。

3.1 實驗設置

實驗包括從給定的工作負荷生成作業(yè)提交，然后運行算法來分配作業(yè)和提供VM。來自于網(wǎng)格和超級計算站點的工作負荷存檔經(jīng)過歸一化的工作負荷的基本描述如表1所示，包含了日志文件的名稱、記錄日志的時間長度、提交的作業(yè)總數(shù)及系統(tǒng)中可用處理器總數(shù)；表2列出了全部仿真參數(shù)。

表1 工作負荷日志

表2 仿真參數(shù)

3.2 實驗結果及分析

圖1(a)-圖1(c)所示為每個處理器每小時平均利潤、平均收入和平均成本與歸一化負荷的關系。由圖1(a)可以看出，對于大于0.6的歸一化工作負荷，DVMIA算法比CA-貪婪算法能獲得更高的利潤，而且兩種算法的利潤差越來越大；由圖1(b)可以看出，DVMIA算法得到了更高的收入，而且對于大于0.6的歸一化工作負荷來說，由DVMIA算法所獲得的收入是迅速增加的。因此在資源需求很高的情況下，DVMIA算法能夠獲得更高的收入。通過圖1(c)可見，DVMIA算法會使得全部工作負荷的總成本更高。由于DVMIA算法是動態(tài)決定VM的數(shù)量，因此在相同競拍者的拍賣中，可以比CA-貪婪算法分配更多的VM實例，這就導致了更高的成本。這也驗證了上文分析：一個單位VM實例在空閑時每單位時間花費cI，在運行時(即分配給用戶)每單位時間cR>cI，因此通過提供和分配更多的VM實例，DVMIA算法會給云提供商帶來更高的成本。

(a) 每個處理器每小時平均利潤

圖2(a)、圖2(b)分別比較了2種算法獲得的資源利用率、服務的用戶百分比與歸一化負荷的關系。顯然，DVMIA算法對于資源利用率和服務的用戶的百分比都獲得了更高的值，在大多數(shù)情形下，DVMIA算法的資源利用率平均高于CA-貪婪算法約25百分點，服務的用戶的百分比平均要高約33百分點。對于DVMIA算法來說，服務的用戶數(shù)更多，是因為VM實例不是靜態(tài)配置的。對于CA-貪婪算法，當VM1實例不可用，而VM2實例是可用的時，則對于有2個VM1實例請求的用戶來說，將不會被分配，而DVMIA算法將其分配給為2個VM1實例進行投標的用戶或為1個VM2實例進行投標的用戶，這取決于誰報的估價更高，這就增加了DVMIA算法服務的用戶數(shù)量。

(a) 資源利用率

實驗評價了DVMIA算法與改進的CA-貪婪算法的平均利潤和資源利用率，結果如圖3所示。改進的CA-貪婪算法考慮了每種類型VM實例的預測需求。從圖3(a)可見，即使采用預測需求，CA-貪婪算法也無法獲得DVMIA算法所獲得的利潤；從圖3(b)可見，帶有需求預測的CA-貪婪算法也無法獲得DVMIA算法所獲得的資源利用率水平。主要是由于考慮的每種類型的VM實例的數(shù)量隨時間變化很大，故需求預測的CA-貪婪算法對一個時間窗口的平均值無法很好地捕捉需求，也就無法提高資源的利用率。

(a) 每個處理器每小時的平均利潤

總之，當需求與供給相匹配時，CA-貪婪算法可能能得到比DVMIA算法更高的收入，或在拍賣中存在項目不可配置時，CA-貪婪算法也是一種非常有效的拍賣，但是當存在可重新配置的項目時如云情形，則很難事先較好地預測需求。在這種情況下，DVMIA算法則是更好的選擇。

4 結 語

本文研究了云中動態(tài)VM實例的提供和分配，設計了一種名為DVMIA算法機制來解決這一問題。采用真實工作負荷進行的大量仿真實驗結果表明，DVMIA算法能夠有效地捕捉市場需求，提供與需求相匹配的計算資源，并得到比CA-貪婪算法更高的收入、服務的用戶百分比和云資源利用率，特別是在高需求情形下。