基于SLA的云計(jì)算多數(shù)據(jù)中心任務(wù)調(diào)度算法

于珊珊，陳冬林，李 偉，鄂雪妮

(1．武漢理工大學(xué)電子商務(wù)與智能服務(wù)研究中心，湖北 武漢 430070;2．新奇特車業(yè)服務(wù)股份有限公司，上海 201824)

云計(jì)算是一種新興的商業(yè)計(jì)算模式，使用戶可以按需使用分布在網(wǎng)絡(luò)各處的資源，并按使用量付費(fèi)［1］。云服務(wù)提供商和用戶通常需要通過協(xié)商談判簽訂服務(wù)等級(jí)協(xié)議以規(guī)定服務(wù)的響應(yīng)時(shí)間等QoS(quality of service)內(nèi)容以及計(jì)費(fèi)付費(fèi)模式，從而保證自身利益和服務(wù)質(zhì)量［2］。

云計(jì)算任務(wù)合理調(diào)度是提升云服務(wù)效率的關(guān)鍵。目前關(guān)于云計(jì)算任務(wù)調(diào)度的研究主要關(guān)注在單個(gè)數(shù)據(jù)中心內(nèi)部實(shí)現(xiàn)負(fù)載均衡，如文獻(xiàn)［3］通過排隊(duì)論方法解決IaaS(infrastructure as a service)平臺(tái)任務(wù)調(diào)度;文獻(xiàn)［4］基于神經(jīng)網(wǎng)絡(luò)和線性規(guī)劃預(yù)測未來需求從而提前知道虛擬機(jī)的開啟與關(guān)閉;文獻(xiàn)［5］通過綜合考慮用戶QoS和虛擬機(jī)的遷移次數(shù)等問題降低了虛擬機(jī)遷移次數(shù)和物理主機(jī)數(shù)量?；赟LA的調(diào)度技術(shù)支持云服務(wù)商對(duì)資源進(jìn)行重新配置從而滿足簽署的SLA中的服務(wù)質(zhì)量等級(jí)［6］，在對(duì)任務(wù)進(jìn)行調(diào)度的過程中云服務(wù)商必須考慮設(shè)計(jì)合理的懲罰策略［7］以及降低SLA違約率［8］。目前也有學(xué)者開始研究基于SLA的云計(jì)算任務(wù)調(diào)度，如文獻(xiàn)［9］提出了一個(gè)面向SLA的混合動(dòng)力資源配置方法;文獻(xiàn)［10］構(gòu)建了一種SaaS(software as a service)平臺(tái)上SLA約束下的任務(wù)接納機(jī)制;文獻(xiàn)［11］設(shè)計(jì)了一個(gè)適用于多層自主環(huán)境的資源調(diào)度分配程序以保證不同級(jí)別的SLA收益最大化。在實(shí)際資源服務(wù)提供商方面，近年來也出現(xiàn)了若干通過SLA技術(shù)實(shí)現(xiàn)服務(wù)質(zhì)量保證機(jī)制的商用云計(jì)算系統(tǒng)或平臺(tái)，主要包括Amazon EC2［12］、GoGrid和Rackspace［13］等。

總的來看，現(xiàn)有的云計(jì)算任務(wù)調(diào)度策略沒有考慮同一云服務(wù)商的不同數(shù)據(jù)中心的使用成本差異，僅僅考慮在單個(gè)數(shù)據(jù)中心內(nèi)部進(jìn)行負(fù)載均衡來調(diào)度資源。此外，云計(jì)算任務(wù)調(diào)度策略缺乏有效的任務(wù)接收機(jī)制，較少考慮基于SLA優(yōu)先處理緊急任務(wù)。因此，研究如何依據(jù)用戶定制的SLA，在多個(gè)數(shù)據(jù)中心間管理、分配和調(diào)度資源并考慮提前處理緊急的、預(yù)算高的任務(wù)以保證云服務(wù)商利益最大化，在理論上和現(xiàn)實(shí)中都具有重要意義。

1 基于SLA的任務(wù)調(diào)度效益模型

針對(duì)SLA合約中參數(shù)定義，任務(wù)調(diào)度考慮的SLA模型包括以下幾個(gè)指標(biāo):

(1)Deadline，表示任務(wù)的最遲完成時(shí)間;

(2)Reward，表示當(dāng)云服務(wù)商滿足用戶SLA需求、不需支付懲罰金時(shí)，完成任務(wù)獲得的費(fèi)用;

(3)Penalty Rate Ratio，表示當(dāng)云服務(wù)商執(zhí)行任務(wù)的時(shí)間違反了與用戶的約定時(shí)，懲罰在一定時(shí)間內(nèi)下降的比例;

(4)Input File Size，表示用戶提交任務(wù)的文件數(shù)據(jù)大小;

(5)Request Length，表示用戶提交的任務(wù)長度，即執(zhí)行這個(gè)請求需要的指令數(shù)。

筆者設(shè)計(jì)對(duì)懲罰加入可延遲時(shí)間，懲罰模型如圖1所示。任務(wù)的SLA違約金Penalty是一個(gè)與延遲時(shí)間delay相關(guān)的線性函數(shù)，Penalty=β×delay，其中β為該類服務(wù)的懲罰延遲率。不同服務(wù)規(guī)定的懲罰延遲率不同。

圖1 懲罰模型

根據(jù)以上指標(biāo)建立任務(wù)調(diào)度效益模型。

定義1任務(wù)接收收益。新任務(wù)在第j個(gè)數(shù)據(jù)中心的第i臺(tái)L類虛擬機(jī)的總使用成本為Cost，則云服務(wù)商接收新任務(wù)獲得的接收利益為Prof。SLA－MPS算法使云服務(wù)商獲得的總收益是大于nonSLA－MPS算法的，并且總收益都成增長趨勢。但隨著任務(wù)數(shù)量的增多，兩種收益的增長率都在下降，并且nonSLA－MPS算法的收益增長率逐步趨向0。這是因?yàn)镾LA－MPS算法增加了插入策略并且可以在支付罰金的情況下使得任務(wù)延遲，最大化利用了每個(gè)資源的時(shí)間碎片，從而減緩因資源不足拒絕任務(wù)而減少收益的情況。

定義2任務(wù)接收成本。云服務(wù)商接收新任務(wù)需要付出的成本包括新虛擬機(jī)開啟成本IC、任務(wù)執(zhí)行成本PC、任務(wù)傳輸成本DTC、任務(wù)超過用戶要求的完成時(shí)間需要賠償?shù)倪`約金PDC。

定義3虛擬機(jī)開啟成本。在第j個(gè)數(shù)據(jù)中心開啟一臺(tái)L類虛擬機(jī)的時(shí)間為iniTij，該虛擬機(jī)的單位時(shí)間使用成本為PjL。

定義4任務(wù)執(zhí)行成本。執(zhí)行該新任務(wù)的成本取決于該任務(wù)的預(yù)計(jì)執(zhí)行時(shí)間procT與所需L類虛擬機(jī)的單位時(shí)間使用成本PjL。

定義5任務(wù)傳輸成本。執(zhí)行該任務(wù)需要輸入文件數(shù)據(jù)大小inDSnew、輸出文件數(shù)據(jù)大小outDSnew，而每個(gè)數(shù)據(jù)中心對(duì)數(shù)據(jù)輸入輸出的傳輸成本分別為inPj和outPj。

定義6任務(wù)延遲懲罰成本。云服務(wù)商未能在用戶要求的最大完成時(shí)間內(nèi)執(zhí)行任務(wù)，則根據(jù)懲罰率βnew與懲罰延遲時(shí)間PDT受到一定的懲罰。

定義7數(shù)據(jù)傳輸時(shí)間。任務(wù)執(zhí)行需要的文件傳輸總時(shí)間DTTj為:

定義8任務(wù)懲罰延遲時(shí)間。每執(zhí)行一個(gè)新任務(wù)，云服務(wù)商都需要開啟一臺(tái)新的虛擬機(jī)或調(diào)度到已經(jīng)開啟的虛擬機(jī)上。假設(shè)在將新任務(wù)調(diào)度到某個(gè)虛擬機(jī)上時(shí)，有M個(gè)任務(wù)正在等待執(zhí)行，新任務(wù)的最遲完成時(shí)間為DL，則新任務(wù)的懲罰延遲時(shí)間為:

定義9任務(wù)響應(yīng)時(shí)間。任務(wù)在虛擬機(jī)上能夠執(zhí)行完的時(shí)間為:

定義10接收回報(bào)。接收一個(gè)新任務(wù)每小時(shí)獲得的接收回報(bào)retnew為:

定義11目標(biāo)收益。云服務(wù)商根據(jù)成本有一個(gè)期待目標(biāo)收益，期待的收益回報(bào)率為μ，則:

2 基于SLA的多云數(shù)據(jù)中心任務(wù)調(diào)度機(jī)制

2．1 多數(shù)據(jù)中心任務(wù)準(zhǔn)入控制策略

在決定是否接收任務(wù)時(shí)，決策指標(biāo)比較接收回報(bào)是否大于目標(biāo)收益以在閾值條件下平衡收益與響應(yīng)時(shí)間。最后執(zhí)行調(diào)度時(shí)以接收回報(bào)最大化為最終調(diào)度決策，這樣可以使得開啟新虛擬機(jī)的概率增大，提高任務(wù)的接受率和響應(yīng)時(shí)間。

多數(shù)據(jù)中心任務(wù)準(zhǔn)入控制策略主要有3類:

(1)多數(shù)據(jù)中心新虛擬機(jī)開啟策略。尋找某一云服務(wù)商多個(gè)數(shù)據(jù)中心里符合任務(wù)需求的虛擬機(jī)模板。首先判斷任務(wù)在虛擬機(jī)上預(yù)計(jì)執(zhí)行完成時(shí)間是否小于任務(wù)最遲完成時(shí)間，若是則直接計(jì)算該任務(wù)在候選新開啟虛擬機(jī)上執(zhí)行的接收回報(bào)retnew，否則要在retnew中考慮懲罰成本。如果retnew大于目標(biāo)收益exp InvRetnew，將接受操作并記錄調(diào)度選擇信息SDij(數(shù)據(jù)中心號(hào)、虛擬機(jī)號(hào)、開始時(shí)間、完成時(shí)間和任務(wù)位置等)，否則將拒絕操作記錄。

(2)多數(shù)據(jù)中心等待策略。在新任務(wù)到來時(shí)，首先尋找云服務(wù)商多個(gè)數(shù)據(jù)中心中是否有開啟的對(duì)應(yīng)類型虛擬機(jī)，計(jì)算任務(wù)在每個(gè)虛擬機(jī)上的預(yù)計(jì)完成時(shí)間并判斷該任務(wù)是否能等待該虛擬機(jī)上已接收的全部等待任務(wù)完成。如果可以等待，則計(jì)算該任務(wù)在候選虛擬機(jī)的ret，如果大于exp InvRet，將接受操作以及將調(diào)度選擇信息SDij記錄到調(diào)度表，否則記錄拒絕操作。

(3)多數(shù)據(jù)中心插入策略。在新任務(wù)到達(dá)時(shí)，首先尋找多個(gè)數(shù)據(jù)中心中是否有開啟的對(duì)應(yīng)類型虛擬機(jī)，對(duì)每個(gè)虛擬機(jī)上的任務(wù)隊(duì)列尋找可以插入的位置，再計(jì)算該插入點(diǎn)下對(duì)應(yīng)的ret是否大于exp InvRet，若是則接受操作以及將調(diào)度選擇信息SDij記錄到調(diào)度表，否則記錄拒絕操作。

2．2 基于SLA的最大化收益任務(wù)調(diào)度算法

現(xiàn)有的云計(jì)算任務(wù)調(diào)度算法為保證云服務(wù)商收益最大，常常采取最小化開啟虛擬機(jī)數(shù)量的方式。由于這類任務(wù)調(diào)度算法往往不考慮SLA內(nèi)容造成的任務(wù)差異，將其統(tǒng)稱為非SLA最大化收益任務(wù)調(diào)度算法nonSLA－Max Profitby Scheduling(nonSLAMPS)。nonSLA－MPS的算法流程如圖2所示。

圖2 nonSLA－MPS算法流程

考慮SLA內(nèi)容，對(duì)于緊急并且預(yù)算高的任務(wù)不能僅執(zhí)行等待或開啟新虛擬機(jī)策略，而是可以通過重調(diào)度，將其按條件插入前一等待任務(wù)前。這樣可以利用最少的資源以及最大的時(shí)間空閑，最大化接受任務(wù)從而獲得高收益。于是提出基于SLA的最大化收益任務(wù)調(diào)度算法SLA－Max Profitby Scheduling(SLA－MPS)。SLA－MPS算法的調(diào)度流程如圖3所示。

圖3 SLA－MPS算法流程

3 實(shí)驗(yàn)及結(jié)果分析

3．1 實(shí)驗(yàn)設(shè)計(jì)

筆者在云仿真軟件CloudSim［14］上實(shí)現(xiàn)調(diào)度算法。該實(shí)驗(yàn)在多個(gè)不同SLA要求的用戶爭奪相同資源的情況下，從任務(wù)平均響應(yīng)時(shí)間、云服務(wù)商SLA違約率和云服務(wù)商總收益3個(gè)方面對(duì)比nonSLA－MPS和SLA－MPS算法，檢驗(yàn)兩種算法對(duì)云服務(wù)商利益的影響。限定每個(gè)數(shù)據(jù)中心開啟的虛擬機(jī)最大數(shù)為30，實(shí)驗(yàn)規(guī)定的總?cè)蝿?wù)數(shù)分別為400、600、800和1 000個(gè)。

任務(wù)參數(shù)、虛擬機(jī)參數(shù)及其使用成本分別如表1～表3所示。

表1 任務(wù)參數(shù)表

表2 虛擬機(jī)參數(shù)表

表3 虛擬機(jī)單位使用成本表萬元

3．2 結(jié)果分析

(1)任務(wù)平均響應(yīng)時(shí)間對(duì)比。圖4展示了任務(wù)的平均響應(yīng)時(shí)間隨任務(wù)增加的變化趨勢。SLA－MPS算法的任務(wù)響應(yīng)時(shí)間是明顯低于nonSLA－MPS算法的。這是因?yàn)镾LA－MPS算法的插入策略使得后到的任務(wù)在滿足前面任務(wù)時(shí)間和預(yù)算約束的條件下充分利用了因到達(dá)率不一樣而空閑的時(shí)間，使得在總時(shí)間減小的情況下增大了接收任務(wù)數(shù)，從而獲得較優(yōu)的響應(yīng)時(shí)間。

圖4 任務(wù)平均響應(yīng)時(shí)間對(duì)比

(2)云服務(wù)商SLA違約率對(duì)比。圖5展示了nonSLA－MPS和SLA－MPS算法隨任務(wù)增加對(duì)云服務(wù)商的SLA違約率的影響。因?yàn)榧尤肓藨土P延遲機(jī)制，所以這里考慮SLA違約是拒絕的任務(wù)數(shù)與總的任務(wù)數(shù)之比。筆者提出的結(jié)合多數(shù)據(jù)中心任務(wù)準(zhǔn)入控制的任務(wù)調(diào)度策略，在保證收益的同時(shí)有效提高了任務(wù)的接收比例。SLA－MPS算法相對(duì)于nonSLA－MPS算法延長了懲罰延遲的時(shí)間，提高了任務(wù)可以接受的完成時(shí)間，從而接受了更多任務(wù)，降低了整體SLA違約率。

圖5 SLA違約率對(duì)比

(3)云服務(wù)商總收益對(duì)比。圖6展示了在資源有限、任務(wù)增多的情況下，nonSLA－MPS算法和SLA－MPS算法對(duì)云服務(wù)商總收益的影響。SLA－MPS算法使云服務(wù)商獲得的總收益是大于nonSLA－MPS算法的，并且總收益都呈增長的趨勢。但隨著任務(wù)數(shù)量的增多，兩種收益的增長率都在下降，并且nonSLA－MPS算法的收益增長率逐步趨向0。這是因?yàn)镾LA－MPS算法增加了插入策略并且可以在支付罰金的情況下使得任務(wù)延遲，最大化利用了每個(gè)資源的時(shí)間碎片，從而減緩因資源不足拒絕任務(wù)而減少收益的情況。

圖6 云服務(wù)商總收益對(duì)比

4 結(jié)論

筆者建立了基于SLA的任務(wù)調(diào)度效益模型，設(shè)計(jì)了面向多數(shù)據(jù)中心的有效任務(wù)準(zhǔn)入策略，并通過合理組合所設(shè)計(jì)的策略提出基于SLA的最大化收益任務(wù)調(diào)度算法(SLA－MPS)。該算法使得云服務(wù)商實(shí)現(xiàn)了從在單個(gè)數(shù)據(jù)中心內(nèi)部以負(fù)載均衡為目標(biāo)調(diào)度資源到在多個(gè)數(shù)據(jù)中心之間以成本最低為目標(biāo)調(diào)度資源的跨越，以及基于SLA靈活處理緊要問題，確保了云服務(wù)商高效利用資源、調(diào)度任務(wù)，得到了最大化收益。

在云仿真軟件CloudSim上的實(shí)驗(yàn)證明，SLA－MPS算法能夠確保云服務(wù)商最大化地利用資源，從而在任務(wù)時(shí)間和預(yù)算的約束下獲得最大的收益，實(shí)現(xiàn)任務(wù)快速響應(yīng)、低違約率和高收益。

［1］林偉偉，齊德昱．云計(jì)算資源調(diào)度研究綜述［J］．計(jì)算機(jī)科學(xué)，2012，39(10):1－6．

［2］高云璐，沈備軍，孔華鋒．基于SLA與用戶評(píng)價(jià)的云計(jì)算信任模型［J］．計(jì)算機(jī)工程，2012，38(7):28－30．

［3］岳冬利，劉海濤，孫傲冰．IaaS公有云平臺(tái)調(diào)度模型研究［J］．計(jì)算機(jī)工程與設(shè)計(jì)，2011，32(6):1889－1892．

［4］ISLAM S，KEUNG J，LEE K，et al．Empirical prediction models for adaptive resource provisioning in the cloud［J］．Future Generation Computer Systems，2012，28(1):155－162．

［5］李強(qiáng)，郝沁汾，肖利民．云計(jì)算中虛擬機(jī)放置的自適應(yīng)管理與多目標(biāo)優(yōu)化［J］．計(jì)算機(jī)學(xué)報(bào)，2011，34(12):2253－2264．

［6］MAURER M，EMEAKAROHA V C，BRANDIC I，et al．Cost－benefit analysis of an SLA mapping approach for defining standardized cloud computing goods［J］．Future Generation Computer Systems，2012，28(1):39－47．

［7］DASTJERDI A V，TABATABAEI S G H，BUYYA R．A dependency－aware ontology－based approach fordeploying service level agreement monitoring services in cloud［J］．Software:Practice and Experience，2012，42(4):501－518．

［8］EMEAKAROHA V C，NETTO M A S，CALHEIROS R N，et al．Towards autonomic detection of sla violations in cloud infrastructures［J］．Future Generation Computer Systems，2012，28(7):1017－1029．

［9］GANDHI A，CHEN Y，GMACH D，et al．Hybrid resource provisioning for minimizing data center SLA violations and power consumption［J］．Sustainable Computing:Informatics and Systems，2012，2(2):91－104．

［10］WU L，KUMAR GARG S，BUYYA R．SLA－based admission control for a software－as－a－service provider in cloud computing environments［J］．Journal of Computer and System Sciences，2012，78(5):1280－1299．

［11］ARDAGNA D，TRYBIAN M，ZHANG L．SLA based resource allocation policies in autonomic environments［J］．Journal of Parallel and Distributed Computing，2007，67(3):259－270．

［12］WALKER E．Benchmarking Amazon EC2 for highperformance scientific computing［J］．Usenix Login，2008，33(5):18－23．

［13］HILLEY D．Cloud computing:a taxonomy of platform and infrastructure－level offerings［J］．Georgia Institute of Technology，2009(1):1－37．

［14］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．