基于多維資源動態(tài)監(jiān)測SLA沖突算法研究

陳 亮，王江勇，彭 艦

（四川大學(xué)計(jì)算機(jī)學(xué)院，四川成都610065）

0 引 言

云計(jì)算是繼分布式計(jì)算、網(wǎng)格計(jì)算、效用計(jì)算之后的一種新的計(jì)算模式［1］，并在商業(yè)上取得巨大的成功，將計(jì)算資源作為基礎(chǔ)設(shè)施供應(yīng)，并采用“即付即使用”支付方式，使得計(jì)算資源可以像水電那樣購買。而服務(wù)等級協(xié)議（service level agreement，SLA）是云計(jì)算服務(wù)商和客戶之間對服務(wù)質(zhì)量（quality of service，QoS）的一種協(xié)商［2，3］。云計(jì)算服務(wù)商需要管理不同客戶的SLAs，并監(jiān)測QoS以滿足不同用戶的SLAs。通常SLA針對不同的應(yīng)用而采用不同的衡量標(biāo)準(zhǔn)，例如Web應(yīng)用一般采用響應(yīng)時間來作為SLA，而對主機(jī)資源（CPU、RAM、IO等）需要一定時間持有的應(yīng)用，SLA則需要考慮主機(jī)的資源利用率［4］。盡管不同客戶的SLA不同，但是云計(jì)算服務(wù)商的主機(jī)資源是統(tǒng)一的，如何利用有限的資源，實(shí)現(xiàn)云系統(tǒng)中任務(wù)或虛擬機(jī)的分配和調(diào)度，以最大限度滿足不同的SLA，是云計(jì)算中廣泛研究的熱點(diǎn)之一［5］。

為了給用戶提供高度可用性、高度伸縮性的云服務(wù)［6］，數(shù)據(jù)中心一般都采用負(fù)載均衡機(jī)制［7］。當(dāng)創(chuàng)建大量虛擬機(jī)得不到滿足時，多隊(duì)列系統(tǒng)應(yīng)運(yùn)而生用于解決任務(wù)排隊(duì)的問題。同時，多個任務(wù)分布在大量主機(jī)上，顯然沒有有效利用資源，常見的辦法是通過虛擬機(jī)遷移將多個虛擬機(jī)聚集在同一臺主機(jī)以提高資源利用率和節(jié)約能耗［8］。文獻(xiàn)［9］提出一個負(fù)載均衡下的隨機(jī)模型，并定義了吞吐量最優(yōu)的概念，根據(jù)該概念提出兩個吞吐量最優(yōu)的算法，但沒有考慮SLA約束。文獻(xiàn)［10］提出基于資源預(yù)算條件下的動態(tài)調(diào)整自適應(yīng)應(yīng)用程序的參數(shù)，以滿足資源動態(tài)變化的供應(yīng)。文獻(xiàn)［11］提出虛擬機(jī)復(fù)用技術(shù)，將多個虛擬機(jī)整合在同一主機(jī)上，本文將整合的思想擴(kuò)展到多隊(duì)列系統(tǒng)中。

本文采用文獻(xiàn)［9］提到的基于時間片的分時系統(tǒng)，將資源SLA考慮在內(nèi)，給出資源SLA違反模型，并提出一個多維資源SLA感知的優(yōu)化算法，該算法減少了SLA違反率，并加快了任務(wù)的執(zhí)行速度。

1 模型描述

1.1 多隊(duì)列系統(tǒng)

基于多隊(duì)列系統(tǒng)，本文作出以下幾點(diǎn)假設(shè):

（1）采用分時系統(tǒng)，系統(tǒng)的最小時間單位，即一個時間片t；

（2）用戶請求的任務(wù)是非長期的計(jì)算密集型任務(wù)，不存在類似Web應(yīng)用的任務(wù)長期駐留在服務(wù)器上；

（3）用戶向系統(tǒng)發(fā)出的請求，描述了所需虛擬機(jī)（virtual machine，VM）的類型和大小，分別記為m和S。虛擬機(jī)類型一共有1…m種，而VM的大小是該VM執(zhí)行完任務(wù)所需要的時間片數(shù)量。

根據(jù)以上假設(shè)，當(dāng)有大量的用戶請求時，系統(tǒng)為用戶請求的任務(wù)創(chuàng)建對應(yīng)類型的VM，同一類型的VM進(jìn)入同一隊(duì)列排隊(duì)，因此產(chǎn)生m個隊(duì)列。在每一個時間片t時，分別從m個隊(duì)列中取出一個m維的VM向量N（簡稱“向量N”），它的每一維是對應(yīng)每種類型的VM數(shù)量。系統(tǒng)將這些VM派發(fā)給特定的服務(wù)器（physical machine，PM）去執(zhí)行，當(dāng)VM所需時間片（即VM的大?。┯猛陼r，用戶請求的任務(wù)完成，該VM從主機(jī)上銷毀。

在時間片t的起始時刻，到達(dá)系統(tǒng)的m類型VM的集合記為m（t），其數(shù)量是Am（t）＝｜m（t）｜。有如下隊(duì)列模型［8］，即

式（1）和式（2）中，在時間片t時刻時，Wm（t）是達(dá)到的m類型任務(wù)的總大小，Qm（t）是當(dāng)前隊(duì)列中未處理完的m類型任務(wù)的總大小，Dm（t）是能被系統(tǒng)處理的任務(wù)總量。

系統(tǒng)將m個隊(duì)列分布在每個服務(wù)器s上，但是邏輯上可以看作系統(tǒng)只存在m個隊(duì)列，如圖1所示。

圖1 多隊(duì)列系統(tǒng)

每個服務(wù)器從自己的m個隊(duì)列中選擇最優(yōu)的配置向量N＊，因此式（2）可以進(jìn)一步寫成

文獻(xiàn)［9］給出了兩種優(yōu)于JSQ（Join－the－shortestqueue）算法的路由算法，分別是Power－of－two算法和Pick－and－Compare算法。這兩種算法減少了集中維護(hù)隊(duì)列長度信息的開銷，提高了系統(tǒng)負(fù)載性能，但是對減少系統(tǒng)的SLA沖突沒有幫助。本文以簡單的JSQ算法（算法在1.2節(jié)中描述）作為VM派發(fā)階段的路由算法，集中討論主機(jī)PM上資源SLA違反情況和資源利用率。

1.2 JSQ算法

JSQ算法是一種針對服務(wù)器集群的常用路由策略［12］，該算法集中維護(hù)所有隊(duì)列的長度，將需要分發(fā)的任務(wù)分配給當(dāng)前具有最短長度隊(duì)列的服務(wù)器。JSQ算法分配任務(wù)的基本思想是，根據(jù)每個服務(wù)器上隊(duì)列的長度，決定每個服務(wù)器的處理能力，即隊(duì)列越短，該服務(wù)器處理能力越強(qiáng)。由于隊(duì)列的長度是動態(tài)變化的，因此主機(jī)的處理能力也是動態(tài)確定的，不存在某一個隊(duì)列的長度很長的情況。

在1.1節(jié)中提到的多隊(duì)列系統(tǒng)中，虛擬機(jī)類型有m種，而這m種虛擬機(jī)對主機(jī)資源的需求不同，因此多隊(duì)列系統(tǒng)中的m隊(duì)列，相對于某一個主機(jī)來說，被處理的速度不同，具體體現(xiàn)在隊(duì)列的長度不同。本文將JSQ算法擴(kuò)展到所有主機(jī)上的m個隊(duì)列，當(dāng)系統(tǒng)收到用戶的虛擬機(jī)請求時，根據(jù)虛擬機(jī)的類型，確定當(dāng)前所有主機(jī)上對應(yīng)該虛擬機(jī)類型的最短隊(duì)列，并將請求的虛擬機(jī)分配給具有該最短隊(duì)列的主機(jī)。根據(jù)JSQ算法的思想，顯然具有該最短隊(duì)列的主機(jī)更有能力處理此類型的虛擬機(jī)。

1.3 SLA沖突檢測模型

假設(shè)每臺服務(wù)器有i種不同的資源（例如CPU、內(nèi)存、磁盤等），每種資源記為Ri，其總量為Ti，則由m種類型VM組成的可行配置向量N，應(yīng)滿足如下公式

顯然，N取值有很多，這些可行配置向量N構(gòu)成可行配置向量集合，每次達(dá)到服務(wù)器的工作量λ為這些可行配置向量N的組合。

由文獻(xiàn)［11］啟發(fā)，本文給出如下SLA模型，在［1，L］個時間片內(nèi)，有

上述公式中符號的含義，見表1。

顯然，上述SLA模型針對i種資源有i種約束，Pi和βi這兩個參數(shù)是根據(jù)不同應(yīng)用性能設(shè)定的，也受不同資源特點(diǎn)的影響。在Pi時間段內(nèi)，是資源i的平均量，當(dāng)它大于當(dāng)前服務(wù)器剩余資源i時，說明資源i存在SLA違反。這時，需要考慮檢查當(dāng)前最優(yōu)可行配置向量中存在SLA違反的VM類型，在文中第2節(jié)給出了具體算法。

表1 主要符號及其含義

2 多維資源SLA沖突優(yōu)化算法

2.1 優(yōu)先隊(duì)列

在1.1節(jié)描述的系統(tǒng)模型中，從VM類型劃分了m個隊(duì)列，但是沒有考慮任務(wù)SLA違反的情況，即存在一些任務(wù)可能占用某種資源（CPU密集型任務(wù)、IO密集型任務(wù)、Network密集型任務(wù)等），但是由于虛擬機(jī)預(yù)定配置造成某種資源的瓶頸，延長了任務(wù)的執(zhí)行時間。本文提出為每臺服務(wù)器增加一個優(yōu)先隊(duì)列，通過SBP（select by priority）算法（算法在2.2節(jié)中描述）將存在資源SLA違反的VM，放入優(yōu)先隊(duì)列中。當(dāng)服務(wù)器在每個時間片t的開始時，先從優(yōu)先隊(duì)列中讀取最優(yōu)可行配置VM向量，然后再根據(jù)服務(wù)器的當(dāng)前容量，從m個隊(duì)列中選擇一個最優(yōu)可行配置向量。采用優(yōu)先隊(duì)列的隊(duì)列模型，如圖2所示。

圖2 采用優(yōu)先隊(duì)列的隊(duì)列模型

在時間片L時，將資源違反SLA的VM放入優(yōu)先隊(duì)列中。很明顯，當(dāng)L足夠長時，收集SLA沖突的信息更多，更能準(zhǔn)確地預(yù)測出當(dāng)前VM向量中存在那類資源SLA違反。下面通過SBP算法將預(yù)測出的資源SLA違反的VM選擇出來放入優(yōu)先隊(duì)列中，該VM可以得到優(yōu)先執(zhí)行，因此可以滿足該VM對資源較高的需求。

2.2 SBP算法

SBP算法采用貪心策略，當(dāng)資源i發(fā)生SLA違反時，根據(jù)式（5）可以檢測出SLA違反，從當(dāng)前可行配置向量N（s）（t）中選擇對資源i需求最大的VM，放入優(yōu)先隊(duì)列中；如果資源i仍然不符合SLA，則重復(fù)上述步驟，直至N（s）（t）不存在SLA違反。這時，優(yōu)先隊(duì)列中的配置向量是可行配置向量，因?yàn)?/p>

根據(jù)SBP算法，服務(wù)器s先從優(yōu)先隊(duì)列中讀取最優(yōu)可行配置向量，再從m個隊(duì)列讀取最優(yōu)可行配置向量，則根據(jù)Myopic Max Weight分配算法的思想［9］，推導(dǎo)出如下公式

采用SQP算法的負(fù)載均衡調(diào)度策略，描述如下:

調(diào)度過程（1）VM分派階段（JSQ算法）對于所有在時間片t時達(dá)到的m類型任務(wù)，路由到對應(yīng)m類型VM的最短隊(duì)列中，即s＊m（t）＝arg min多隊(duì)列系統(tǒng)VM s Q ms（t）為選出的具有最短隊(duì)列的服務(wù)器。此時，該服務(wù)器上達(dá)到的負(fù)載量，如下W ms（t）＝W m（t），s＝s＊m（t）0，s｛為其他服務(wù)器（2）VM執(zhí)行階段（SBP算法）if（每臺服務(wù)器s采用SLA模型檢查到i類型資源發(fā)生SLA違反）｛1）從當(dāng)前可行配置向量N（s）（t）中選擇對資源i需求最大的VM，放入優(yōu)先隊(duì)列中；如果資源i仍然不符合SLA，則重復(fù)上述步驟，直至N（s）（t）不存在SLA違反。這時，優(yōu)先隊(duì)列中存在配置向量＾N（s）（t）2）服務(wù)器先讀取＾N（s）（t），再根據(jù)Myopic Max Weight分配算法，即公式珦N（s）（t）∈arg max Q m（t）N m求出珡N（s）m（t），并將該可行配置向量讀入服務(wù)器。｝else｛采用Myopic Max Weight分配算法，求出珡N（s）m（t），并將該可行配置向量讀入服務(wù)器。N:珡N（s）（t）＋N（s）（t－）＋＾N（s）（t）∈s∑m｝

3 實(shí)驗(yàn)與分析

本文采用CloudSim Toolkit工具［13］進(jìn)行模擬實(shí)驗(yàn)，實(shí)驗(yàn)平臺如下:Intel Core2 Duo CPU T5800 2.00GHz，RAM 2GB，Windows 7 SP1。CloudSim的基本模擬參數(shù)見表2。

表2 模擬實(shí)驗(yàn)基本參數(shù)

實(shí)驗(yàn)將Round Robin算法和采用SBP算法的Round Robin算法進(jìn)行對比分析。

圖3給出了CPU、RAM、IO資源的利用率的情況（VM數(shù)量為710時）。由于采用了資源SLA沖突模型，檢測出可能存在資源瓶頸的VM，并優(yōu)先執(zhí)行這一類VM，SBP算法明顯提高各項(xiàng)資源的利用率，優(yōu)于一般的Round Robin算法。

圖3 資源利用率（710 VMs）

圖4給出了當(dāng)VM數(shù)量為710至960時，CPU、RAM、IO資源的平均沖突率。顯然，各個任務(wù)對RAM資源競爭程度強(qiáng)于CPU資源和IO資源，而SBP算法對CPU、RAM和IO資源沖突有不同程度的改善，較明顯的是SBP算法將Round Robin算法的RAM沖突率減少了26%?？傮w上SBP算法較Round Robin算法，減少了各種資源的SLA沖突。

圖5給出了VM總的執(zhí)行時間。當(dāng)VM數(shù)量小于200時，系統(tǒng)無論采用Round Robin算法，還是結(jié)合了SBP算法，系統(tǒng)都能在較短時間內(nèi)執(zhí)行完成VM。當(dāng)用戶請求的VM配置過多時，系統(tǒng)的排隊(duì)時間延遲加大，而且每種資源（CPU、RAM和IO）的沖突明顯增加。這時基于資源SLA沖突檢測的SBP算法，盡可能將對資源需求大的任務(wù)優(yōu)先執(zhí)行，有效減緩了排隊(duì)時間，VM的總執(zhí)行時間在一定程度下沒有劇增，VM的平均執(zhí)行時間比采用Round Robin算法要短很多。

圖4 平均SLA沖突率（710～960 VMs）

圖5 執(zhí)行時間

4 結(jié)束語

本文基于多隊(duì)列系統(tǒng)，提出一個檢測資源SLA的沖突模型和基于該模型的SBP算法，通過增加一個優(yōu)先隊(duì)列，將對資源需求大的VM放入優(yōu)先隊(duì)列并優(yōu)先執(zhí)行，最大化提高資源利用率和減少資源沖突情況，以減少系統(tǒng)的排隊(duì)時間和VM的執(zhí)行時間。仿真結(jié)果表明，采用SBP算法的Round Robin算法，有效減少各種資源（CPU、RAM和IO）的SLA沖突率，在提高資源利用率和縮短VM執(zhí)行時間方面，明顯優(yōu)于一般的Round Robin算法。

［1］Qi Zhang，Lu Cheng，Raouf Boutaba.Cloud computing:State－of－the－art and research challenges［J］.Journal of Internet Services and Applications，2010，1（1）:7－18.

［2］Pankesh Patel，Ajith Ranabahu，Amit Sheth.Service level agreement in cloud computing［R］.Ohio:Kno.e.sis Publications，2009:1－2.

［3］Philipp Wieder，Joe M Butler，Wolfgang Theilmann，et al.Service level agreements for cloud computing［M］.New York:Springer，2011:13－26.

［4］Inigo Goiri，Josep Ll Berral，J Oriol Fito，et al.Energy－efficient and multifaceted resource management for profit－driven virtualized data centers［J］.Future Generation Computer Sys－tems，2012，28（5）:718－731.

［5］Vladimir Stantchev，Christian Schropfer.Negotiating and enforcing QoS and SLAs in grid and cloud computing［G］.LNCS 5529:Advances in Grid and Pervasive Computing.Berlin:Springer Berlin Heidelberg，2009:25－35.

［6］Peter Mell，Timothy Grance.The NIST definition of cloud computing（draft）［R］.USA:NIST Special Publication，2011.

［7］Randles M，Lamb D，Taleb－Bendiab A.A comparative study into distributed load balancing algorithms for cloud computing［C］//IEEE 24th International Conference on Advanced Information Networking and Applications Workshops，2010:551－556.

［8］Sallam A，Li K.A multi－objective virtual machine migration policy in cloud systems［J］.The Computer Journal，2013，3（1）:1－10.

［9］Maguluri S T，Srikant R，Ying L.Stochastic models of load balancing and scheduling in cloud computing clusters［C］//IN－FOCOM.IEEE，2012:702－710.

［10］Zhu Q，Agrawal G.Resource provisioning with budget constraints for adaptive applications in cloud environments［C］//Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing.ACM，2010:304－307.

［11］Meng X，Isci C，Kephart J，et al.Efficient resource provisioning in compute clouds via VM multiplexing［C］//Proceedings of the 7th International Conference on Autonomic Computing.ACM，2010:11－20.

［12］Gupta V，Harchol Balter M，Sigman K，et al.Analysis of join－the－shortest－queue routing for Web server farms［J］.Performance Evaluation，2007，64（9）:1062－1081.

［13］Calheiros R N，Ranjan R，Beloglazov A，et al.CloudSim:A toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms［J］.Software:Practice and Experience，2011，41（1）:23－50.