云計算中一種高效的虛擬機在線動態分配算法

張麗敏

（西安外事學院現代教育技術中心 西安 710077）

1 引言

虛擬技術為云供應商提供更加便捷的方法來分配計算資源。云供應商定義不同的虛擬機（VM）組合，并以VM實例為單位出售資源。當前，云供應商使用定價策略分配和出售VM實例[1]，使用拍賣算法來出售定價之后仍然閑置的資源。云供應商希望分配算法能夠支持動態供應，以便他們根據市場需求就不同類型的VM實例數量做出決策。云供應商也希望實現營運收入最大化。

多篇文獻已經對云計算的經濟問題進行了研究。參考文獻[2]針對目前國內并沒有相應的云計算計價標準，價格高低直接影響網絡利用率和收益的問題，在計價時考慮價格因素對網絡負載的影響，提出了一種改進的蟻群算法，解決了計算資源閑置導致的網絡利用率低下和收益減少問題。參考文獻[3]提出了一種面向資源分配的第k+1個價格拍賣算法。通過理論分析與仿真得出，當資源和用戶較多時，該算法既可以提高分配的效率，又可以增加云服務商的收入。參考文獻[4]設計了一種基于馬爾可夫決策過程的資源在線算法，給出了同一模型面對大規模問題時的近似求解方法。參考文獻[5]設計了一種并行系統下可拓展并行作業的資源在線調度算法。該算法在其模型中支持作業搶占，如果作業的價值更高，那么即使提交時間晚于當前分配的作業，也可以獲得優先權支持。參考文獻[6]提出了一種云資源調度模型（cloud-resource scheduling model，CSM），該模型以實現效用最大為調度目標，可以充分提高用戶的滿意程度。文中通過求解CSM優化問題得到最優的虛擬機和物理機映射關系，實現了對云資源的最優分配。

另外，參考文獻[7]針對云商務環境下信息服務資源分配過程中的定價問題，分別建立了服務者、服務用戶和服務環境的模型，并提出相應的求解方法。仿真實驗結果表明，當交易者的規模增加時，該方法可以在保證第三方收入的情況下，使參與交易的雙方獲取更高的服務效用。參考文獻[8]提出了一種基于組合拍賣的VM分配算法CA-Provision，該算法通過假設資源以數量固定但類型不同的VM實例形式提前供應，從而解決VM分配問題。另外，CA-Provision算法拓展了參考文獻[7]中的模型，并支持VM實例的動態供應和分配。然而，該算法在運行時需要收集一段時間內所有用戶請求的所有信息，即這些算法是離線算法，需要定期運行來為用戶分配資源。

為此，本文設計了一種云條件下VM實例的在線供應和分配算法。首先，設計了一種申請協議，當用戶申請一批VM時，表明用戶只對整批VM感興趣，而不是其中的一部分。在接收到這些申請后，本文算法在線計算分配策略和花費。同時，分配不得被搶占，如果用戶在時間t接收到分配策略，則在用戶所請求的該段時間內始終占有資源。最后，通過理論分析和仿真實驗驗證了本文算法的有效性。

2 VM實例分配問題

假設云服務提供商提供的計算資源共有m種不同的VM實例類型，本文將這些實例類型表示為VM1,…,VMm。對每種類型的實例 VMi關聯一個 “權重”ωi∈，ωi表示VMi相對云供應商提供的最強大VM實例 （即類型為VM1的實例）的計算能力。不失一般性，本文認為ω1=1且ω1≤…≤ωm。將可以用于分配的可用計算資源的總計算能力表示為M，定義為類型VM1的M個實例的等價計算能力。假設云供應商提供3種類型的VM實例：小型（VM1）、中型（VM2）、大型（VM3）。這些 VM 的配置如下：VM1為 1 個2 GHz處理器、8 GB內存、2 TB硬盤；VM2為 2個 2 GHz處理器、8 GB內存、2 TB硬盤；VM3為2個2 GHz處理器、16 GB內存、4 TB硬盤。對于該配置來說，VM的權重為：ω1=1、ω2=2、ω3=4。假設云提供商有足夠的資源來提供100 000個VM1實例，則M=100 000。云提供商的目的是將其可用資源動態供應為VM實例，在將其高效提供給用戶的同時實現收益最大化。

滿足的約束條件為：

式（1）表示問題的目標，即云供應商使成功申請資源的用戶價值之和最大化。式（ 2 ） 表示在已知時間t分配的資源不得超過最大可用資源數量M。其中，，該集合表示在時間t及t之前分配到資源，并且在時間t所分配到的時間間隙還沒有結束的用戶集合。

上述問題的一種直接求解方法就是選擇價值最大的用戶，然后向這些用戶收取各自的費用。然而，用戶是理性用戶，他們可能為了自身利益而誤報自己的類型。例如，用戶可能少報價值以便減少支付額度，或者多報價值以增加被分配概率。如果云提供商偏好截止日期較早的作業而忽略價值，則用戶可能會早報他們的截止日期。因為這一信息是隱私信息，所以提供商需要使用一種算法來根據用戶報告的價值計算分配策略及相關費用，以便提供商設定的全系統目標能夠實現。

3 在線算法的設計

每個用戶j可將價值函數Vj定義如下：

如果用戶申請成功，則用戶接收到的價值為υj；否則，接收到的價值為0。本文用效用函數來定量描述用戶j的效益，該效用函數定義為用戶從算法接收到的價值與用戶需要支付的費用之差，即：

如果在線算法拒絕為其分配資源，則用戶接收到的價值為0。此時，如果算法不向其收取任何費用，用戶的效用也將為0。

定義 1 （激勵作用）如果對任意用戶j有∈Θj、-j∈Θ-j、并滿足式（5），則算法E具有激勵作用[9]。

用戶如果不管其他用戶的申請如何，而把自己的真實類型匯報給算法，則可以實現自身效用最大化。這是非常重要的算法，因為如果滿足這一屬性，參與算法的用戶就不會向算法匯報虛假類型，即匯報真實屬性是用戶的最優策略。

不管其他用戶的申請如何，用戶只要參與在線算法并匯報了自己的真實類型，自己的效用一定不會為負。這也是在線算法的重要屬性，因為可以鼓勵用戶積極參與在線算法。為了使算法具有激勵作用，分配函數A必須單調且費用函數P必須實現臨界值支付[10]。

如果用戶j通過匯報類型而申請成功，則該用戶匯報也會申請成功 ，其 中′比更 受 偏 好 。

定義4 （臨界值支付）用戶j的臨界值 定義為

臨界值是指用戶為了申請成功而必須向算法匯報的最小值。費用函數應該向用戶收取臨界值費用，以便使算法具有激勵功能。本文設計了一種解決OVMPA問題的在線算法。

4 在線VM分配算法

本節給出了解決OVMPA問題的在線VM分配和供應算法。

4.1 ODAA-VM

ODAA-VM采取事件處理程序架構，當新的申請到達或者用戶分配到的批量資源到期，并且將VM實例返回給供應商時，調用事件處理程序。假設通過某種標準化協議，用戶和資源的信息對算法是已知的。ODAA-VM利用這一信息來確定用戶集合及當前時間可用資源，并可調用分配函數和費用函數。ODAA-VM流程如下。

ODAA-VM以事件、當前分配集合及費用集合為輸入。事件類型包括資源的釋放或到達的用戶申請。假設系統存儲這兩個集合，并且當ODAA-VM被調用時將其傳輸給ODAA-VM。ODAA-VM更新集合，然后返回給系統。在第1～4行，ODAA-VM設置當前時間為t，且3個變量的初始化如下：N(t)為迄今還沒有申請成功的用戶申請集合；(t)為已經成功申請但是分配的資源還沒有到期的用戶申請集合；M(t)為在時間t可用于分配的資源總權重。只有當資源和用戶可用時，算法才會運行。算法會調用以未獲得成功的用戶申請和時間可用資源為參數的函數ODAA-VM-Allocate。ODAA-VM-Allocate函數（見第4.2節）返回在時間t申請成功的用戶集合A(t)。

然后，ODAA-VM將整個分配集合A更新為A(t)。A(t)中的申請也被插入費用集合，且 為初始費用。然而，通過調用ODAA-VM-Payment函數（見第4.3節）可以更新該費用（第11行）。實際上，用戶j的費用會被更新多次，直到t=δj（即用戶接收到所要求的批量實例）為止。因此，ODAA-VM-Payment函數計算這些用戶的費用并更新費用集合P。ODAA-VM算法的下一個步驟是確定當前時間已經超過δj的用戶j的申請集合NP（第12行）。然而，這一集合只包括t′之后已經度過δi時間的用戶，其中t′表示上次調用ODAA-VM的時間（第12行）。如果用戶j已經分配到了批量資源，則該用戶的費用不會再改變，當前時刻的費用即最終費用。如果用戶j直到時間t還沒有申請成功且t>δj，則用戶不會申請到完成他的作業所需要的資源。此時，用戶j將支付的費用為pj=0（第14～19行）。

4.2 ODAA-VM-Allocate函數

函數ODAA-VM-Allocate的具體過程如下。

首先，ODAA-VM-Allocate函數按照ρj的非升次序對所有申請排序。按照如下次序打破關聯：偏愛更早的δj、更小的以及更小的。然后，當資源允許時，算法將為這些用戶分配各自請求的資源。最后，算法返回在時間t被選擇分配資源的用戶集合A(t)。

ODAA-VM-Allocate函數的目的是實現申請成功的用戶價值之和最大化。當存在關聯情況時，通過向δj較小的用戶賦予優先級（即沒有申請成功而將較早離開系統的用戶），也可以保證受到服務的用戶數量最大化。基于同樣原因，對于δj關聯情況，資源使用時間較短的用戶也將受到優先對待。

4.3 ODAA-VM-Payment函數

ODAA-VM-Payment函數如下。

ODAA-VM-Payment函數的輸入包括當前時間t、費用集合P、調用分配函數M(t)之前的可用資源、分配函數N(t)考慮的用戶集合以及當前時間t占據資源的用戶集合(t)。在時間t申請成功的用戶也屬于集合N(t)。

ODAA-VM-Payment函數的主要思路是將用戶的到達時間看成t，然后計算δj≤t的用戶j的臨界費用。通過每個事件重復調用這一函數，ODAA-VM可以保證和 δj之間每次出現事件時，均會計算用戶j的臨界費用。ODAA-VM-Payment函數對 δj≥t的所有用戶j計算時間t時的臨界值為：

以該臨界值為基礎，ODAA-VM將臨界值計算為：

ODAA-VM-Payment函數考慮費用集合中 δj≤t的用戶。對于每個用戶j，將其類型的到達時間元素設為t，價值設為每個用戶的價值，以便確定用戶j為了申請成功而需匯報的最小值（第2～16行）。如果未找到最小值，則將支付費用設為0（第17～21行），也可以將該數值設為預先確定的底價。最后，將更新過的集合P返回給在線算法。在線算法通過調用ODAA-VM-Payment函數以持續更新P，并在時間t向的δj

5 算法性能

定理1ODAA-VM具有激勵作用。

定理2ODAA-VM的時間復雜度為O(nlogn)。

ODAA-VM主要包括ODAA-VM-Allocate函數和ODAA-VM-Payment函數。其中，ODAA-VM-Allocate函數成本最大的操作是第2行的用戶排序，這一操作的復雜度為O(nlogn)。ODAA-VM-Payment函數看上去非常復雜，因為它重復調用ODAA-VM-Allocate函數。但是，在實際部署中，當確定臨界值時并不需要調用ODAA-VM-Allocate函數。對申請成功的用戶j，需要以他們的非升次序考慮在時間t沒有申請成功的用戶j′，并且弄清如果j沒有參與，用戶j′能否申請成功。只需比較j占據的資源和j′請求的資源，就可以弄清這一點。當首次發現這一用戶j′時，用戶j的費用為′。需要在算法開始時對失敗的申請進行一次排序，這一過程的復雜度仍然為O(nlogn)。因此，ODAA-VM的時間復雜度為O(nlogn)。

定理3 ODAA-VM的競爭比為η。

設有兩個申請 θ1和 θ2，且s1=1，s2=M,(a1,l1,d1,υ1)=(0,l,l,υ)，(a2,l2,d2,υ2)=(1,l,l+1,Mv+ε),l>1。一方面，ODAA-VM 將為用戶1分配其在時間l>1要釋放的資源。因為對于θ2，有a2+l2=1+l=d2，所以用戶2必須在時間a2=1申請成功，否則用戶2需要收回申請。由于其無法在截止日期前完成作業，因此ODAA-VM只會為用戶1分配VM實例，并獲得價值υ（式（1））。另一方面，最優離線算法將為用戶2分配資源，獲得價值Mυ+ε>M×υ。因此，ODAA-VM 算法的競爭比為 η。

6 實驗結果

通過對ODAA-VM和一種高性能離線算法的比較，證明ODAA-VM的優缺點。

6.1 實驗配置

[8]中的CA-Provision離線算法與本文的ODAA-VM進行比較。CA-Provision算法解決了云環境下的動態VM供應和分配問題。以固定時間間隔（如1 h）調用CA-Provision算法。當調用時，該算法考慮上次間隔期間收集的所有申請，通過組合拍賣來確定申請成功的用戶、費用及分配的VM實例數量。分配的VM實例只能使用一個時間間隔，用戶如果需要繼續訪問資源，就必須繼續申請，直到滿足這些用戶的時間要求。如果需求量上升，則當前分配給用戶的資源在以后可能被搶占。

本文使用的輸入來自于參考文獻[11]中的Parallel Workload Archive（并行工作負載數據庫）。表1給出了工作負載的日志信息及相關統計信息，前4列分別為工作負載日志的名稱、日志的采集時間、作業數量及日志總小時數，第5列給出了生成日志的系統的處理器數量。假設VM實例的權重對應于分配給該實例的處理器數量，則一個系統的處理器總數量表示計算資源的總權重s，將分配給工作負載ω的總體計算資源表示為Mω。表1的后4列表示相關統計數據：Jω表示每小時遞交給系統的平均作業數量；平均運行時間Tω及單個作業的平均處理器數量Pω在計算時考慮工作負載日志的所有記錄；最后一列為負載ω的“正規化負載”ηω，其計算式為：

表1 工作負載日志

正規化負載用來衡量請求的平均資源量與可用的單位計算資源之間的相對關系，幫助對異構工作負載進行排序，并解釋部分實驗結果。

表2 仿真參數

CA-Provision算法根據單個空閑VM實例的相關成本參數計算底價υres=cR-cI。雖然本文沒有給出帶有底價的ODAA-VM，但是通過拋棄低于底價的用戶，并對申請成功的用戶收取底價費用而不是0費用（ODAA-VM-Payment函數的第20行），即可集成底價策略。在本文實驗中，ODAA-VM的底價與CA-Provision算法的底價相同。表2給出了所有參數值，對每個工作負載日志，基于不同的參數組合進行18次實驗。

6.2 結果分析

在圖1中總結了每個工作負載的結果。水平軸表示工作負載和正規化負載，垂直軸表示成功申請的用戶比例、每個成功申請的用戶的平均收入以及每個成功申請的用戶的平均效用。在圖1(a)中，ODAA-VM的用戶服務比例高于CA-Provision算法。最明顯的性能增益出現于日志 LLNLuBGL-2006（正規化負載 7.41）和 DAS2-fs0-2003（正規化負載2.01）中，且是這里使用的工作負載的最大值。DAS2-fs0-2003負載的用戶服務比例幾乎翻倍，LPC-EGEE-2004負載的用戶服務比例增長將近6倍。這是因為在CA-Provision算法中，即使有可用資源，用戶也必須等待下次拍賣時間。那時，可能有更多用戶到達，因此該用戶可能拍賣失敗。此外，對于部分用戶來說，即使在部分拍賣中取得成功，但是如果他們需要長期占用資源來完成任務，將可能發生資源搶占，所以他們會選擇離開。由于上述兩種工作負載增加了申請密度，所以導致拍賣數量上升，而ODAA-VM由于其在線設計，可以容納更多的申請。

從圖1（b）可知，每個成功申請用戶帶來的平均收益下降。由于在線算法根據不完全信息確定分配策略，所以無法實現收入最優。一種直觀解釋就是ODAA-VM通過盡快做出分配決策，幫助用戶避免與后續用戶競爭。對于CA-Provision算法，用戶必須與相同周期內的其他用戶展開競爭，因此價格將會上升，但是成功申請用戶的數量上升彌補了收益損失。

從圖1（c）可以看出，ODAA-VM成功申請用戶的平均效用與CA-Provision算法相當。雖然本文希望通過降低用戶支出提高用戶的效用，但是前提是兩次拍賣所選擇的分配用戶集合相同。這是不可能實現的，原因有兩點：一是CA-Provision算法會搶占價值較低的用戶，將資源分配給價值高的用戶，而ODAA-VM會把VM分配給用戶，并讓用戶在其所申請的整個時段內使用資源，但是如果有價值更高的用戶到達，則這可能導致沒有可用資源，從而丟失該用戶；二是ODAA-VM中成功申請的用戶數量要多于CA-Provision算法，這說明ODAA-VM容納了低價值用戶，而這些用戶導致平均效用較低。

總體來說，本文認為ODAA-VM提升了用戶和云供應商的云體驗，云供應商服務了更多用戶，增加了用戶滿意度，最終增加了總體收入。

7 結束語

本文設計了一種云環境下VM在線供應和分配算法。在該算法下，每當有足夠多的資源和合適的申請，就會分配VM實例。本文算法對用戶具有激勵作用，且可在多項式時間內運行；可增加被服務的用戶數量，但是降低了平均收益，然而增加的用戶數量可以彌補平均收益損失。在未來工作中，將針對CA-Provision算法中用戶VM被搶占的情況，設置相應的賠償代價，并將其再次與ODAA-VM進行比較，觀察“用戶的平均收益”是否有所改進。

圖1 CA-Provision算法和ODAA-VM的總體結果

參考文獻

1 劉正偉,文中領,張海濤.云計算和云數據管理技術.計算機研究與發展,2012,49(Z1):26～31

Liu Z W,Wen Z L,Zhang H T.Cloud computing and cloud data management technology.Journal of Computer Research and Development,2012,49(Z1):26～31

2 范杰,彭艦,黎紅友.基于蟻群算法的云計算需求彈性算法.計算機應用,2011,31(1):1～4

Fan J,Peng J,Li H Y.Demand elasticity algorithm for cloud computing based on ant colony optimization algorithm.Journal of Computer Applications,2011,31(1):1～4

3 Lin W Y,Lin G Y,Wei H Y.Dynamic auction mechanism for cloud resource allocation.Proceedings of the 10th IEEE/ACM International Conference on Cluster,Cloud and Grid Computing(CCGrid),Melbourne,Australia,2010:591～592

4 ParkesD C,Singh S.An mdp-based approach toonline mechanism design.Proceedings of the 17th Annual Conference on Neural Information Processing Systems,Sydney,Australia,2003:1421～1426

5 Carroll T E,Grosu D.Incentive-compatible online scheduling of malleable parallel jobs with individual deadlines.Proceedings of the 39th International Conference on Parallel Processing,San Diego,CA,USA,2011:418～425

6 師雪霖,徐恪.云虛擬機資源分配的效用最大化模型.計算機學報,2013,36(2):252～262

Shi X L,Xu K.Utility maximization model of virtual machine scheduling in cloud environment.Chinese Journal of Computers,2013,36(2):252～262

7 羅賀,孫錦波,胡笑旋等.云商務環境下的多源信息服務資源分配模型.計算機集成制造系統,2013,19(10):137～142

Luo H,Sun J B,Hu X X,et al.Resource allocation model for multi-sources information service in cloud business.Computer Integrated Manufacturing Systems,2013,19(10):137～142

8 Zaman S,Grosu D.Combinatorial auction-based dynamic vm provisioning and allocation in clouds.Proceedings of IEEE 3rd International Conference on Cloud Computing Technology and Science(CloudCom),Athens,Greece,2011:107～114

9 Zaman S,Grosu D.A combinatorial auction-based mechanism for dynamic VM provisioningand allocation in clouds.IEEE Transactions on Cloud Computing,2013,1(2):129～141

10 Mu’alem A,Nisan N.Truthful approximation mechanisms for restricted combinatorialauctions.Proceedings ofthe 18th National Conference on Artificial Intelligence, Edmonton,Alberta,Canada,2002:379～384

11 Lublin U, Feitelson D G. The workload on parallel supercomputers:modeling the characteristics ofrigid jobs.Journal of Parallel and Distributed Computing,2003,63(11):1105～1122