王 旭，倪 宏，韓 銳

(1.中國科學院聲學研究所國家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心，北京 100190； 2.中國科學院大學,北京 100049)

0 引 言

近年來，云計算技術(shù)蓬勃發(fā)展，其應(yīng)用也越來越受到重視[1-3]。用戶可以通過租用數(shù)據(jù)中心資源的方式靈活構(gòu)建自己的應(yīng)用，而不必像傳統(tǒng)方式那樣采購主機、自行維護。所有的主機維護均由數(shù)據(jù)中心代為完成。當需求發(fā)生變化時，用戶也能快速改變虛擬機資源以適應(yīng)這種變化。在云計算系統(tǒng)中，數(shù)據(jù)中心利用大量商用服務(wù)器來為用戶提供虛擬計算服務(wù)，通過為終端用戶分配虛擬機，使得用戶能夠訪問數(shù)據(jù)中心的資源，并且能夠輕松更新系統(tǒng)配置。

用戶可在虛擬機創(chuàng)建過程中定制需求，包括一系列功能性需求，如操作系統(tǒng)版本、預裝應(yīng)用軟件等；一系列非功能性需求，如CPU虛擬內(nèi)核數(shù)量、CPU主頻、內(nèi)存數(shù)量、內(nèi)存讀寫速率、存儲空間大小、存儲介質(zhì)、網(wǎng)絡(luò)性能等，同時也包括對特殊處理單元的需求，如對支持CUDA(Compute Unified Device Architecture)顯卡的需求。然而，用戶需求往往各不相同，進而造成了用戶需求的異構(gòu)性。此外，由于硬件性能的提高和價格的下降，系統(tǒng)資源的異構(gòu)性體現(xiàn)在，當進行系統(tǒng)擴充時，人們往往會購買或開發(fā)新型的計算機系統(tǒng)，而不是采用系統(tǒng)中已有的設(shè)備類型，保持系統(tǒng)的同構(gòu)性；而且，把不同硬件和軟件系統(tǒng)結(jié)合往往可以得到較高的性價比。因此，在一般情況下，用戶需求和系統(tǒng)資源均是異構(gòu)的[4]。

進一步地，虛擬機的資源利用率及主機的總體資源利用率均隨時間變化[5]。通過提高主機資源利用率，減少空閑主機數(shù)量，數(shù)據(jù)中心能夠在一定程度上減少電力消耗，進而降低運行成本[6]。通常情況下，虛擬機對各項資源的需求并不相同，因此導致了主機資源消耗不平衡，最終導致了較差的主機資源利用率[7]，同時造成了能量的浪費[8]。舉例來說，諸如圖像紋理采集之類的任務(wù)會大量使用CPU資源，然而對內(nèi)存需求不高。某一主機中存在過多這類任務(wù)時，主機CPU滿載時，內(nèi)存尚未被充分利用，主機資源無法被充分利用。進一步地，某些主機因其底層硬件架構(gòu)關(guān)系尤其適合執(zhí)行某些特定任務(wù)的虛擬機[9]。數(shù)據(jù)中心固有的異構(gòu)性和其所負載的動態(tài)性也常被忽視[10]。因此，云計算數(shù)據(jù)中心使用虛擬機在線遷移操作完成動態(tài)負載管理[11-12]。通過虛擬機在線遷移技術(shù)，虛擬機能夠從一個主機遷移到另一個主機，并且在此過程中盡量少地影響虛擬機中執(zhí)行的任務(wù)[13]。

拍賣是買賣沒有標準價值的商品或服務(wù)的過程。連續(xù)雙向拍賣(Continuous Double Auction，CDA)[14]是一種市場化的資源管理方式，并且在近年來應(yīng)用的比較普遍[15-17]。事實證明，市場化手段針對云環(huán)境下的資源分配問題效果較為顯著。通過拍賣方式為資源分配問題引入供求機制，利用市場化方法就可以解決數(shù)據(jù)中心內(nèi)部的資源配置和管理問題。

本文提出基于市場化雙向拍賣的云數(shù)據(jù)中心資源管理架構(gòu)。它是一種基于CDA的算法，旨在運用市場理論解決數(shù)據(jù)中心內(nèi)部資源的分配和管理問題。然而，與原始CDA算法不同，本文所述場景涉及多種資源類別。在拍賣中，每種資源類別的需求均需要被滿足。同時，本文在拍賣成交策略中引入資源匹配度，以此匹配資源相似度高的主機與虛擬機。

1 虛擬機遷移流程

虛擬機遷移過程中，源主機對虛擬機資源進行打包，發(fā)送至目標主機。目標主機獲得虛擬機后立即恢復虛擬機執(zhí)行。一般而言，為保證虛擬機遷移的有效性，即能夠獲得資源平衡或主機資源利用率的提高，源主機、目標主機、虛擬機的選擇都十分重要。對應(yīng)地，本文引入主機選擇算法、虛擬機選擇算法、虛擬機拍賣算法。算法流程如圖1所示。

圖1 主機算法流程

主機選擇算法針對源主機和目標主機，利用啟發(fā)式算法選擇所有應(yīng)遷出虛擬機的過載主機作為備選源主機，選擇所有資源過剩主機作為備選目標主機。雙方備選主機將參與后續(xù)虛擬機拍賣，但并非所有備選主機均能在拍賣中成功遷出或遷入虛擬機。

虛擬機選擇算法針對源主機，按照啟發(fā)式規(guī)則選擇源主機中的某一虛擬機作為備選虛擬機。備選虛擬機作為待遷出對象，在后續(xù)拍賣過程中作為標的物。備選虛擬機的自身屬性將決定其在拍賣過程中的價值。

虛擬機拍賣算法通過連續(xù)雙向拍賣，將備選源主機與備選目標主機引入市場競爭之中，通過市場化方法確定買賣關(guān)系。拍賣算法主要需要確定買賣雙方的定價策略及中間人的交易策略。

2 主機啟發(fā)式算法

2.1 主機選擇算法

主機選擇啟發(fā)式用于選擇需遷移部分虛擬機到其他主機的過載主機及可用于接收虛擬機遷入的欠載主機。過載主機在后續(xù)拍賣過程中將作為賣方出現(xiàn)，欠載主機在后續(xù)拍賣過程中將作為買方出現(xiàn)。

虛擬機的遷移過程對當前主機和目標主機的資源狀況均會產(chǎn)生影響?；跈?quán)衡考慮，本文僅考慮CPU與RAM的資源狀況。

對于CPU而言，當使用率升高時，系統(tǒng)處理效率下降，能耗上升。本文采用了基于滑動窗口的管理策略。令滑動窗口長度為T，在某時刻t時窗口平均CPU利用率為：

(1)

(2)

(3)

2.2 虛擬機選擇算法

虛擬機選擇啟發(fā)式算法用于選擇要進行遷移的虛擬機。由于主機異構(gòu)性，同一虛擬機在不同主機運行對主機資源的影響也并不相同。為了能夠有效預測虛擬機對不同主機的資源及性能影響，尤其是計算能力的占用情況，需要了解各個主機的真實性能。因此，需要在各主機上運行綜合基準程序，以了解各主機CPU處理能力。Whetstone和Dhrystone均為經(jīng)過精心設(shè)計的經(jīng)典綜合基準程序，它們通過在統(tǒng)計意義上模擬常用程序的使用來測試CPU性能[18]。一般而言，獲得較高基準程序得分的處理器能夠在一定時間內(nèi)處理更多指令，即性能更佳。

假定虛擬機目前在主機Hi上運行，并將要遷移至主機Hj。在遷移完成后，虛擬機Vj對主機Hi的CPU利用率影響為：

(4)

相似地，可以計算在遷移完成后，虛擬機Vj對主機Hi的RAM利用率的影響為：

(5)

當主機過載并準備遷出虛擬機時，虛擬機選擇啟發(fā)式用于選擇要進行遷移的虛擬機。一旦超載，主機會選擇一個或多個虛擬機來進行遷移。為了盡量快速地降低負載，資源消耗最大的虛擬機會被優(yōu)先選擇。

設(shè)虛擬機的總體資源利用率為主機CPU利用率與RAM利用率的加權(quán)平均值,可以表示如式(6)：

(6)

其中，λCPU和λRAM分別為CPU和RAM負載的權(quán)重因子，且滿足：

λCPU+λRAM=1， λCPU,λRAM∈0,1

(7)

為了反映CPU和RAM的負載，現(xiàn)定義λCPU和λRAM進一步表達如式(8)：

(8)

可得到：

(9)

該權(quán)重因子設(shè)定方法會使得uij更加關(guān)注利用率較高的資源。綜上，具有越高uij值的虛擬機被遷移的優(yōu)先級越高。

3 虛擬機分配中的拍賣過程

3.1 拍賣理論

本文將主機分為3類：買方(主機欠載，準備接受虛擬機遷移請求)、賣方(主機過載，準備遷出虛擬機)以及旁觀者(既未欠載也未過載，不參與虛擬機遷移)。本文只針對買方和賣方進行討論。在拍賣進行過程中，拍賣中間人負責收集賣方價格和買方價格信息，并按照拍賣規(guī)則進行交易匹配。文中將虛擬機作為拍賣標的物，將資源作為貨幣。至此，虛擬機分配與管理問題便可轉(zhuǎn)化為云計算虛擬市場中的買賣問題。該市場中，過載主機作為賣方出售虛擬機，欠載主機作為買方利用其空閑資源購入虛擬機。

拍賣中，當存在潛在買方和潛在賣方時，交易便有可能達成。在連續(xù)雙向買賣中，單次拍賣存在交易時間限制。在時限內(nèi)，買賣雙方可以連續(xù)出價，并根據(jù)既定價格策略調(diào)整價格。在本文場景中，買賣雙方實際上是在買賣虛擬機。通過引入多種資源類型，使得拍賣中交易雙方需要考慮的因素增多。在達成交易時，買方在每種資源上的買方價格均要符合賣方對應(yīng)資源的賣方價格。通過引入這種市場化手段，確保了虛擬機在正確的主機中運行。

3.2 定價策略

在決定最終定價時，需要考慮多種策略來解決在拍賣過程中的不同問題。單次拍賣的剩余時間、系統(tǒng)資源余量均為常用的定價策略。本文使用剩余時間和系統(tǒng)剩余資源來決定買方價格，使用剩余時間和虛擬機占用資源來決定賣方價格。

3.2.1 基于時間的策略

在給定的議價期限τ內(nèi)，假設(shè)在某一時刻t，議價的剩余時間為δ(t)，且滿足δ(t)∈[0,τ]。

給定資源k的最低和最高賣方價格分別是akmin和akmax。在時刻t，ak(t)∈[akmin,akmax]。a(t)初始值為akmax，隨著時間接近于最后期限，最終降至akmin?；谏鲜鲈O(shè)定，設(shè)ak(t)可表示為：

ak(t)=akmax-f(δ(t))(akmax-akmin)

(10)

式中,f是δ(t)的函數(shù)，用以計算賣方價格。

滿足要求的函數(shù)f的選擇多種多樣。文獻[19]中給出了常用的多項式函數(shù)：

(11)

易得出，賣方價格：

(12)

類似地，買方價格bk(t)可表示為：

(13)

3.2.2 基于資源的策略

至于資源，實際資源量被視為價格，因此在議價期價格相對固定。但是，值得注意的是，實際資源量僅為主機能夠支撐虛擬機的最低要求。若主機當前空閑資源與虛擬機需求資源相當，則在遷移后極有可能導致主機過載，進而產(chǎn)生新的虛擬機遷移需求，對系統(tǒng)穩(wěn)定性造成影響。因此，通過適當提升賣方價格，有助于篩選主機，減少后續(xù)遷移的可能性。

策略中，主機Hi針對虛擬機Vj的CPU資源基礎(chǔ)賣方價格為虛擬機Vj占用主機Hi的CPU資源實際計算量，可表示為：

(14)

類似地，主機Hi針對虛擬機Vj的RAM資源基礎(chǔ)賣方價格為虛擬機Vj占用主機Hi的RAM資源實際大小，可表示為：

(15)

設(shè)資源k的最低和最高賣方價格為：

(16)

其中，1<μkminμkmax。當1<μkmin，虛擬機要求更多的資源，同時降低后續(xù)遷移的可能性；當μkmin=μkmax，資源k的賣方價格在議價期限內(nèi)是常數(shù)。

類似地，Hi對CPU資源的出價為主機Hi的CPU資源實際可用計算量，可表示為：

(17)

Hi對RAM資源的出價為主機Hi的RAM資源實際可用大小，可表示為：

(18)

與賣方價格類似地，資源k的最低和最高買方價格為：

(19)

其中，1<μkminμkmax。

3.2.3 總體價格

總體的賣方價格和買方價格將通過上述2項策略進行整合。在時刻t，針對資源k，賣方價格為：

強化工程全過程質(zhì)量監(jiān)督，實行定期工程質(zhì)量管理巡查與不定期檢查相結(jié)合，堅持開工初期、施工中間、隱蔽工程施工、工程支付驗收四到場，嚴把工程質(zhì)量關(guān)，跟蹤督查，精準監(jiān)管，全面提升工程質(zhì)量，為水利項目建設(shè)保駕護航。不定期開展水利工程質(zhì)量大檢查，發(fā)現(xiàn)的問題按照影響程度分別以現(xiàn)場口頭告知、下發(fā)整改通知和通報等方式責令整改，對各單位的問題整改情況逐一進行跟蹤銷號，有效提高了實體工程質(zhì)量。

(20)

買方價格為：

(21)

3.3 交易策略

在交易中僅存在一類資源的情況下，對于資源r，對買方價格和賣方價格按照自然順序排序，即對買方價格按照降序排序，對賣方價格按照升序排序。例如，一次拍賣中存在n名買方及m名賣方。對買方價格按照降序排序，b1≥b2≥…≥bn；對賣方價格按照升序排序，a1≤a2≤…≤am。設(shè)平衡點索引位置為k，k為滿足bk≥ak的最大值。隨后，賣方價格低于ak的賣方與買方價格高于bk的買方之間進行交易。

但在本文場景下，由于拍賣中存在多種資源，因此上述方法并不適用。為解決文中多種資源情況下的拍賣問題，本文提出一種基于虛擬機資源與買方主機資源的匹配程度的交易策略。

(22)

(23)

(24)

在資源數(shù)目為2的情況下，以上過程如圖2示。

圖2 資源相似度計算方法示意圖

賣方集合記為A，買方集合記為B。

雙方通過下列步驟匹配交易：

1)對A中任意Hi及B中任意Hj，計算二者間的相似度dij；

2)對所有dij按照升序排列，記排序結(jié)果為D；

3)選擇剩余dij中最小者；

4)若Hj能負擔Hi需求的所有價格，則轉(zhuǎn)至步驟5，否則轉(zhuǎn)至步驟6；

5)Hi與Hj進行交易，將所有Hi與Hj從D中去除；

6)重復步驟3～步驟5，直至D為空。

4 實驗評估

4.1 評估方法

本評估中涉及3組，每組6臺，共計18臺主機。同組主機具有相同的系統(tǒng)參數(shù)配置和閾值設(shè)置，不同組主機間系統(tǒng)參數(shù)配置有所差異，且根據(jù)其自身特點設(shè)定了不同的閾值，用以模擬數(shù)據(jù)中心的異構(gòu)性。

表1 主機參數(shù)設(shè)置

主機參數(shù)設(shè)定如表1所示。其中，高閾值用于判定主機是否過載，若超出該閾值則主機執(zhí)行虛擬機遷出機制；低閾值用于判定主機是否欠載，若低于該閾值則主機將接受虛擬機的遷入請求。

系統(tǒng)中，由獨立的管理單元負責提交新的虛擬機分配申請。虛擬機的到達與離開為泊松過程。在仿真中，設(shè)定平均任務(wù)到達時間為1000 ms。為模擬虛擬機的異構(gòu)性，虛擬機被CPU設(shè)定為2核、4核或8核，內(nèi)存被設(shè)定為2 GB、4 GB或6 GB。各類虛擬機的數(shù)量符合平均分布，且各虛擬機的長期平均資源利用率為0.5。

在相關(guān)研究中，隨機算法常作為不同方法比較的基準方法，因此，本文仿真中加入隨機算法作為基準方法。當主機過載時，隨機算法在當前主機中隨機選取一個虛擬機，并將其遷移至其他某個隨機主機中。理論上，全局資源信息對隨機算法透明，因此，隨機算法在穩(wěn)定狀態(tài)波動較大。

4.2 資源占用率

仿真中，針對每種方法，本文分別統(tǒng)計了第1組、第2組和第3組各組內(nèi)部主機在各個時刻CPU、RAM利用率，并給出了各組的平均值與標準差。值得注意的是，平均值指標給出了各組資源利用率總體水平，通過平均值是否達到設(shè)定值可對各組主機整體資源利用率是否達到設(shè)定值做出簡要的判斷；標準差給出了各組內(nèi)部各主機資源利用率的差異程度。

4.2.1 基準方法

圖3給出了基準方法第1組主機的資源利用率統(tǒng)計。第1組目標資源利用率介于0.4～0.5之間。仿真中，基準方法CPU與RAM平均利用率達標，CPU與RAM利用率標準差約2%～8%，波動較大。對于第1組，基準方法能夠有效地控制資源利用率，但同組各主機之間資源利用率相差較大，資源利用不平衡。

圖3 資源占用統(tǒng)計(基準方法，第1組)

圖4給出了基準方法第2組主機的資源利用率統(tǒng)計。第2組目標資源利用率介于0.6～0.7之間。仿真中，基準方法CPU平均利用率達標，RAM平均利用率較低約50%，CPU與RAM利用率標準差約2%～6%，波動較大。對于第2組，基準方法能夠有效地控制資源利用率不使主機過載，但主機各類資源利用不平衡；同組各主機之間資源利用率相差較大，資源利用不平衡。

圖4 資源占用統(tǒng)計(基準方法，第2組)

圖5給出了基準方法第3組主機的資源利用率統(tǒng)計。第3組目標資源利用率介于0.8～0.9之間。仿真中，基準方法CPU平均利用率達標，RAM平均利用率較低約50%，CPU與RAM利用率標準差約2%～4%，波動較小。對于第3組，基準方法能夠有效地控制資源利用率不使主機過載，但主機各類資源利用不平衡。

圖5 資源占用統(tǒng)計(基準方法，第3組)

總體而言，基準方法能夠有效地控制資源利用率，但主機各類資源利用率不平衡，同組各主機之間資源利用不平衡。

4.2.2 本文方法

圖6給出了本文方法第1組主機的資源利用率統(tǒng)計。第1組目標資源利用率介于0.4～0.5之間。仿真中，方法2的CPU與RAM平均利用率達標，CPU與RAM利用率標準差約2%，波動較小。對于第1組，方法2能夠有效地控制資源利用率，同組各主機之間資源利用率相差較小，資源利用平衡。

圖6 資源占用統(tǒng)計(本文方法，第1組)

圖7給出了本文方法第2組主機的資源利用率統(tǒng)計。第2組目標資源利用率介于0.6～0.7之間。仿真中，方法2的CPU與RAM平均利用率達標，CPU與RAM利用率標準差約2%，波動較大。對于第2組，方法2能夠有效地控制資源利用率，同組各主機之間資源利用率相差較小，資源利用平衡。

圖7 資源占用統(tǒng)計(本文方法，第2組)

圖8給出了本文方法第3組主機的資源利用率統(tǒng)計。第3組目標資源利用率介于0.8～0.9之間。仿真中，方法2的CPU平均利用率達標，RAM平均利用率較低約70%，CPU與RAM利用率標準差約2%～4%，波動較小。對于第3組，方法2能夠有效地控制資源利用率，同組各主機之間資源利用率相差較小，資源利用平衡。

總體而言，基準方法能夠有效地控制資源利用率，同組各主機之間資源利用率相差較小，資源利用平衡。

圖8 資源占用統(tǒng)計(本文方法，第3組)

4.2.3 討論

為能夠更加清晰地了解各方法的優(yōu)勢與不足，現(xiàn)將各方法CPU利用率達標狀況、RAM利用率達標狀況、各類資源平衡狀況、組內(nèi)主機平衡狀況等信息列于表2中。

表2 遷移算法結(jié)果比較

基準方法能達到最終系統(tǒng)平衡，且各類資源自利用率均低于設(shè)定的上限閾值。然而，基準方法無法實現(xiàn)整體資源的平衡利用，且各組內(nèi)主機負載均衡性差，遷移次數(shù)過多。這是由于基準方法采用隨機化方法，無視系統(tǒng)資源狀況。隨機遷移無法保證資源的平衡利用，同時一定程度上會導致虛擬機遷移至瀕臨過載主機。大量的虛擬機遷移造成了過多的系統(tǒng)開銷。

本文方法不僅實現(xiàn)了整體資源的平衡利用，且各組內(nèi)主機負載均衡性好，同時，虛擬機遷移次數(shù)更少。這是由于方法2在利用市場化拍賣手段的同時，在拍賣交易策略中引入了資源利用率相似度的概念。通過將虛擬機遷移至資源利用率相似度較高的宿主機，能夠保證宿主機與其上各虛擬機各種資源利用率的一致性。

5 結(jié)束語

為解決虛擬機資源與云計算主機資源之間的匹配問題，本文提出了一種基于拍賣的方法來處理云計算環(huán)境數(shù)據(jù)中心的資源分配和管理問題。通過制定出價策略，建立拍賣規(guī)則，實現(xiàn)了云計算數(shù)據(jù)中心環(huán)境下的虛擬機拍賣市場。通過引入基于拍賣的市場化方法，對資源有不同要求的虛擬機能被分配給適當?shù)闹鳈C進行執(zhí)行。本文通過引入一種基于資源匹配度的拍賣規(guī)則實現(xiàn)了拍賣交易。仿真實驗結(jié)果表明，文中提出的方法均能有效解決云數(shù)據(jù)中心虛擬機分配問題。異構(gòu)的任務(wù)負載能夠獲得合適的數(shù)據(jù)中心資源，同時異構(gòu)主機也可以根據(jù)自身的能力獲得負載均衡，從而提高整體效率，保證了云資源與虛擬機之間的適配性。