文一憑 , 王志斌 , 劉建勛 , 許小龍 , 康國勝

(1.湖南科技大學 知識處理與網(wǎng)絡化制造湖南省普通高校重點實驗室, 湖南 湘潭 411201；2.南京信息工程大學 計算機與軟件學院, 江蘇 南京 210044)

0 引言

隨著云計算技術(shù)的深入發(fā)展與大數(shù)據(jù)時代的到來，云計算逐漸成為一種新的社會基礎(chǔ)設施。亞馬遜、微軟、阿里云、谷歌、華為、騰訊、百度等知名企業(yè)紛紛推出了各自的云服務產(chǎn)品。但是，單個云提供者 (cloud vendor)擁有的計算與存儲資源總是有限的。即使是阿里云這樣的龍頭企業(yè)，每年“雙十一”也要減少對外的資源供給，將一些與網(wǎng)購無關(guān)的云服務消費者(cloud service consumer)暫時遷移到其他云上[1]。如果云提供者根據(jù)其突發(fā)峰值業(yè)務需求配置資源，將帶來巨大的資源效費比問題：資源利用率低而成本顯著增加。而云提供者之間的協(xié)作不僅有助于應對突發(fā)峰值業(yè)務需求，還可規(guī)避用戶依托單一云提供者帶來的平臺鎖定等問題。因此，使用多方的云資源，近年來成為了云服務消費者的主流選擇[2-3]。而且，隨著云業(yè)務與云資源需求的不斷擴大，云服務提供者之間的開放協(xié)作成為必然，新一代云計算將是圍繞云際協(xié)作的云計算，學術(shù)界和工業(yè)界也已針對云際協(xié)作環(huán)境的構(gòu)建等問題開展了大量研究[1-2]。

云工作流調(diào)度是映射并管理一組相互依賴的任務在云資源中執(zhí)行的過程。在云際協(xié)作環(huán)境中，不同云服務提供者部署的云數(shù)據(jù)中心、提供的虛擬機種類及收費方式都不相同，可更好地滿足一些復雜工作流(例如，醫(yī)療應用領(lǐng)域中的DNA測序工作流[4])對云資源的需求，并可為用戶按需、高效、低成本地獲取云資源提供更好的解決方案。另一方面，從云服務提供者的角度看，通過協(xié)作管理所共享的資源，將任務分配到不同的數(shù)據(jù)中心，即有可能更好地提升云數(shù)據(jù)中心的資源利用率，從整體上實現(xiàn)所有云數(shù)據(jù)中心的節(jié)能減排。但是，現(xiàn)有云工作流調(diào)度研究卻并未考慮在云際協(xié)作環(huán)境中，如何在為用戶節(jié)約云資源租賃成本的同時，降低或節(jié)約工作流執(zhí)行能耗。而該問題是源于實踐、符合云計算實際應用需求的新問題，且與傳統(tǒng)云計算環(huán)境中的工作流調(diào)度相比，具有更大的挑戰(zhàn)性。

針對該問題，本文在現(xiàn)有云工作流調(diào)度研究的基礎(chǔ)上，提出一種云際協(xié)作環(huán)境下能耗與成本感知的工作流調(diào)度方法。該方法可在滿足工作流截止時間約束的前提下，優(yōu)化多個工作流的執(zhí)行費用與能耗。

1 相關(guān)研究

任務調(diào)度一直是云計算領(lǐng)域的研究熱點，而成本是其中的重要考慮因素之一，文獻[5]對此進行了綜述。近年來，隨著云基礎(chǔ)設施規(guī)模的持續(xù)擴張，云數(shù)據(jù)中心的能耗不斷增長，如何實現(xiàn)云計算環(huán)境中任務的節(jié)能調(diào)度，成為學術(shù)界和產(chǎn)業(yè)界共同關(guān)注的重要問題[6]。在此背景下，提出了許多以降低或節(jié)約能耗為目標的云工作流調(diào)度方法。目前，這些方法主要利用關(guān)閉/休眠、動態(tài)電壓調(diào)整(Dynamic Voltage Scaling，DVS)和虛擬化(virtualization)等技術(shù)實現(xiàn)任務執(zhí)行時的節(jié)能。

基于DVS的云工作流節(jié)能調(diào)度方法主要根據(jù)互補金屬氧化物半導體(Complementary Metal Oxide Semiconductor，CMOS)電路動態(tài)功率公式及任務截止時間等約束，通過降低或動態(tài)調(diào)整處理器的電壓以實現(xiàn)節(jié)能。例如，文獻[7]基于多目標離散微粒群優(yōu)化與DVS技術(shù)設計了一種可最小化完成時間、成本和能耗的多目標云工作流調(diào)度方法。文獻[8]則結(jié)合DVS與虛擬化技術(shù)，給出一種計算工作流執(zhí)行能耗的新方式，并提出了一種云工作流節(jié)能調(diào)度方法。

但是，DVS技術(shù)在應用時存在僅能降低處理器能耗等局限性[9]。因此，近年來，基于關(guān)閉/休眠或虛擬機遷移技術(shù)設計云工作流節(jié)能調(diào)度方法成為主流。文獻[10]從科學工作流應用在云環(huán)境中執(zhí)行的角度，提出一種能耗感知的資源分配方法，可在任務執(zhí)行過程中利用虛擬機實時遷移技術(shù)對虛擬機進行動態(tài)調(diào)度，從而實現(xiàn)科學工作流在動態(tài)執(zhí)行過程中的高能效目標。文獻[11]考慮了工作流在執(zhí)行時的截止時間約束，提出一種成本與能耗感知的科學工作流調(diào)度算法。該方法根據(jù)成本效用的概念，通過虛擬機選擇、序列任務合并、并行任務合并、空閑虛擬機重用等策略來降低工作流執(zhí)行成本與能耗。筆者的前期工作[12]則通過引入物理機資源利用率預測等策略，提出一種能耗與成本感知的實例密集型工作流調(diào)度算法。但是，這些方法主要適用于由一個云提供者管理或者單個云數(shù)據(jù)中心構(gòu)成的傳統(tǒng)云計算環(huán)境。

與傳統(tǒng)云計算環(huán)境相比，云際協(xié)作環(huán)境中的工作流調(diào)度更具挑戰(zhàn)性，現(xiàn)有研究成果也相對較少。在云際協(xié)作研究方面，《中國計算機學會通訊》以“云際計算：面向云際協(xié)作的云計算”為專題介紹了云際計算研究情況[1]，文獻[2]提出了云際協(xié)作環(huán)境的體系結(jié)構(gòu)模型。在相關(guān)云工作流調(diào)度研究方面，文獻[13]最早考慮了異構(gòu)多云計算環(huán)境的特點，提出了兩種動態(tài)資源分配算法以執(zhí)行可搶占式任務并提升云資源利用率。文獻[14]考慮了多個不同類型工作流應用在異構(gòu)多云計算環(huán)境中的調(diào)度問題，并以最小化完成時間與最大化云資源利用率為目標，提出了3種調(diào)度方法。在此基礎(chǔ)上，文獻[15]進一步利用歸一化技術(shù)對這些方法進行了改進，但是，這些算法均未考慮執(zhí)行任務所需要的成本問題。對此，文獻[16]以最小化科學工作流在多云環(huán)境中的執(zhí)行成本為目標，利用離散微粒群優(yōu)化等技術(shù)優(yōu)化計算成本與數(shù)據(jù)跨云傳輸成本，提出一種截止時間約束下基于元啟發(fā)式策略的科學工作流調(diào)度方法。文獻[17]則進一步綜合考慮了多云環(huán)境下工作流調(diào)度的可靠性約束等因素，以最小化完成時間與執(zhí)行成本為目標，提出一種基于微粒群優(yōu)化的多目標科學工作流調(diào)度方法。但是，這些方法均未考慮如何降低工作流執(zhí)行過程中的能耗，而如何實現(xiàn)兼顧成本與能耗的云工作流調(diào)度是云際協(xié)作應用中的重要問題。為此，本文在上述研究的基礎(chǔ)上，進一步提出一種云際協(xié)作環(huán)境下能耗與成本感知的工作流調(diào)度方法。

2 問題描述

2.1 系統(tǒng)模型

定義1一組工作流應用。一組工作流應用可描述為WS={W1,W2,…,Wi,…,WI}為工作流應用集合。Wi為第i個工作流應用，可以描述為Wi=(Ti, CEi,DEi,Di)，其中：

(1)Ti是一組工作流任務的集合，Ti={tij|tij=〈Iij,Wij,Oij,〉}，Iij、Oij分別為任務tij的輸入與輸出數(shù)據(jù)集，Wij描述了任務tij的計算量大小。

(2)CEi為一組有向邊的集合，用以描述工作流任務間的控制流依賴情況，CEi={〈tia,tib〉|〈tia,tib〉∈Ti×Ti}；若〈tia,tib〉∈CEi，則稱tia為tib的前驅(qū)任務，稱tib為tia的后繼任務，任務tia的前驅(qū)任務集合可以表示為pre(tia)，它的后繼任務集合可以表示為succ(tia)；沒有前驅(qū)任務的工作流任務被稱為開始任務，它可以表示為ti, entry。沒有后繼任務的工作流任務被稱為結(jié)束任務，它可以表示為ti, exit。

(3)DEi為工作流任務間的傳遞數(shù)據(jù)的集合，它可以表示為DEi={dei,ab|〈tia,tib〉∈CEi}，其中dei,ab為任務tia向tib傳遞的數(shù)據(jù)量大小。

(4)Di為工作流的截止時間。

定義2云服務提供者。一組云服務提供者可描述為PRO={pro1,pro2,…,prom,…,proM}。

定義3云數(shù)據(jù)中心。云服務提供者prom(1≤m≤M)所提供的云數(shù)據(jù)中心可表示為DCm={dcm,n|1≤n≤N}，其中dcm,n表示云服務提供者prom的第n個數(shù)據(jù)中心。

定義4物理機資源。云數(shù)據(jù)中心dcm,n所提供的物理機資源可表示為PMm,n={pmm,n,p|cpm,n,p,ωm,n,p,1≤p≤P}，其中pmm,n,p表示云數(shù)據(jù)中心dcm,n的第p臺物理機，cpm,n,p表示物理機pmm,n,p的計算能力，ωm,n,p為物理機pm,n,p的運行時間。

定義5虛擬機資源。云服務提供者prom可提供不同租賃價格與配置的虛擬機類型，可表示為VMm={vmm,k|vmm,k=〈vcpm,k,ctm,k,cm,k〉, 1≤k≤K}，其中vmm,k表示云服務提供者prom提供的第k類虛擬機資源，vcpm,k表示vmm,k的計算能力，ctm,k表示vmm,k的計價時間單位，cm,k表示vmm,k單位時間內(nèi)的收費。

2.2 能耗計算模型

工作流執(zhí)行過程中的總能耗E可表示為物理機能耗Eexe與傳輸能耗Etra兩部分：

E=Eexe+Etra

(1)

基于筆者的前期工作[12]，物理機pmm,n,p產(chǎn)生的能耗Em,n,p可按式(2)和式(3)進行計算：

(2)

(3)

其中:PEm,n,p(t)為物理機pmm,n,p在時間t的能耗率；usm,n,p表示物理機pmm,n,p在t時刻的CPU利用率；bem,n,p表示物理機pmm,n,p的基礎(chǔ)能耗；αm,n,p是一個常數(shù)，αm,n,p=bem,n,p/7。

在傳輸能耗的計算方面，為簡化問題，本文不考慮同一物理機中虛擬機之間數(shù)據(jù)通信所產(chǎn)生的能耗。同一數(shù)據(jù)中心內(nèi)不同物理機之間數(shù)據(jù)通信所產(chǎn)生的能耗CEsd，不同的數(shù)據(jù)中心間數(shù)據(jù)通信所產(chǎn)生的能耗CEdd可分別按式(4)和式(5)進行計算：

(4)

(5)

其中：dam,n、bwm,n和?m,n分別表示數(shù)據(jù)中心dcm,n中物理機之間的數(shù)據(jù)通信量、通信帶寬及數(shù)據(jù)傳輸能耗率；DAmn,m′n′、BWmn,m′n′和ηmn,m′n′分別表示數(shù)據(jù)中心dcm,n與數(shù)據(jù)中心dcm′,n′之間的數(shù)據(jù)通信量、通信帶寬及數(shù)據(jù)傳輸能耗率。

綜上所述，工作流執(zhí)行過程中所耗費的物理機能耗Eexe與傳輸能耗Etra可表示為：

(6)

Etra=CEsd+CEdd。

(7)

2.3 工作流完成時間計算模型

(8)

(9)

(10)

因此，工作流Wi的完成時間可通過式(9)計算其結(jié)束任務ti,exit的完成時間獲得。

2.4 云資源使用成本模型

用戶執(zhí)行工作流的成本主要包括虛擬機的租賃成本costrent與數(shù)據(jù)傳輸成本costtrans，可表示為：

cost=costrent+costtrans。

(11)

按照云服務提供者的定價方式，虛擬機的租賃成本可以表示為：

(12)

(13)

執(zhí)行工作流所需數(shù)據(jù)傳輸成本costtrans可以表示為：

(14)

(15)

3 能耗與成本感知的云工作流調(diào)度算法

3.1 算法介紹

在云際協(xié)作環(huán)境中，將工作流在不同云中執(zhí)行有助于應對突發(fā)峰值業(yè)務需求，并可兼顧云資源租賃成本與能耗，但需要滿足工作流截止時間約束。為此，本文提出一種云際協(xié)作環(huán)境下能耗與成本感知的工作流調(diào)度方法(Energy and COst aware workflow scheduling in joint cloud cooperation environment, ECO)。該算法的基本思想是根據(jù)截止時間約束，將工作流任務分組后再分配資源，以減少能耗與成本。其中，關(guān)鍵路徑與任務組是該算法的重要概念，具體定義如下：

定義7工作流路徑。工作流路徑是工作流中一個連通的子圖。給定一個工作流Wi, 其工作流路徑集合可描述為SPwi={spi,j|spi,j=〈STi,j,SCEi,j,sti,j,entry,sti,j,exit〉,STi,j?Wi.Ti,SCEi,j?Wi.CEi,sti,j,entry∈STi,j,sti,j,exit∈STi,j}，其中sti,j,entry與sti,j,exit分別為該路徑中的開始任務與結(jié)束任務。

基于上述定義，ECO算法的主要步驟可用算法1進行描述。

算法1ECO算法。

輸入:PM: 物理機資源，

VM: 虛擬機資源，

WS: 一組工作流應用，

DC: 一組云數(shù)據(jù)中心，

PRO: 一組云服務提供者，

RC:一組虛擬機資源位置記錄；

輸出: 資源調(diào)度結(jié)果。

1: for each Wi∈WS

2: {Wi,un=Wi,dc=NULL, pro=NULL

3: while Wi,un≠?do

4: {select the critical path spi,cpin Wi,un, and add all the tasks in spi,cpto nt

5: if ti,exitin Wi,unthen

6: Dnt=Di

7: else

9: if VMReuse(nt,RC,Dnt,dc)==Failed then

10:if dc==NULL then

11:AssignVM_PM_DC_PRO (nt,PRO, DC, PM,VM, RC, Dnt,dc,pro)

12:else

13: AssignVM_PM (nt,PRO, DC, PM, VM, RC, Dnt,dc,pro)

14: Wi,un=Wi,un- spi,cp}

15: }

ECO算法的主要步驟如下：

步驟1(語句1～2)對每一個待調(diào)度的工作流Wi，首先為其生成一個臨時工作流Wi,un，然后設置其所分配的虛擬機資源所屬的數(shù)據(jù)中心dc與云服務提供者pro等信息，以便后續(xù)操作。

步驟2(語句3～8)從臨時工作流Wi,un中挑選出一條關(guān)鍵路徑spi,cp，根據(jù)該關(guān)鍵路徑生成一個任務組nt，并計算任務組的最晚完成時間Dnt。其中，對于Wi,un生成的第一個任務組，Dnt設置為Wi,un的截止時間Di；其他任務組則通過已分配資源的后繼任務的最晚開始時間計算得出Dnt。語句8中，LST(tia)為任務tia的最晚開始時間，succ(nt)為任務組nt的后繼任務集，即succ(nt)={succ(tij)|tij∈nt}。

步驟3(語句9)嘗試通過復用空閑虛擬機為任務組分配資源，如果不能復用，則進入步驟4。復用空閑虛擬機的具體步驟為：

首先生成尚存在空閑時間、可復用的虛擬機候選集，并限制同一工作流的任務只能復用同一數(shù)據(jù)中心dc中的虛擬機；然后，在滿足任務組的最晚完成時間約束下，從虛擬機候選集中選擇執(zhí)行成本最低的虛擬機進行復用。

步驟4(語句10～13)通過資源動態(tài)管理，為任務組nt分配合適的虛擬機。具體步驟為：

首先判斷當前數(shù)據(jù)中心dc信息是否為空，如果為空則執(zhí)行AssignVM_PM_DC_PRO子過程(語句11)，即根據(jù)不同云服務提供商所提供的虛擬機類型與租賃費用、不同數(shù)據(jù)中心中物理機的負載與能耗情況以及任務組的最晚完成時間約束，選擇或創(chuàng)建一個成本最低的虛擬機，并確定其所屬的物理機(其能耗最低)、數(shù)據(jù)中心dc與云服務提供者pro等信息，更新或新增相關(guān)虛擬機資源位置記錄，然后將該虛擬機分配給任務組nt。

如果當前數(shù)據(jù)中心dc信息不為空，則執(zhí)行AssignVM_PM子過程(語句13)。具體步驟為：首先嘗試在數(shù)據(jù)中心dc中，根據(jù)任務組的最晚完成時間約束、物理機的負載情況，選擇或創(chuàng)建一個成本最低的虛擬機，并確定其所屬的物理機；如果數(shù)據(jù)中心dc中無合適的虛擬機或物理機(即數(shù)據(jù)中心dc能提供的虛擬機無法滿足最晚完成時間約束，或者物理機已滿負荷)，則調(diào)用AssignVM_PM_DC_PRO子過程。

步驟5(語句14)從Wi,un中刪除包含在當前關(guān)鍵路徑spi,cp中的任務與邊，以便生成下一個任務組。

3.2 算法復雜度介紹

算法一共分為5個步驟，步驟1的算法復雜度為O(J)，其中J為工作流的任務數(shù)；步驟2的最壞算法復雜度為O(J×J!);步驟3的最壞算法復雜度為O(MNKJ);步驟4的最壞情況為先嘗試數(shù)據(jù)中心的虛擬機，失敗后調(diào)用AssignVM_PM_DC_PRO子過程，嘗試數(shù)據(jù)中心虛擬機的算法復雜度為O(K)，AssignVM_PM_DC_PRO子過程的算法復雜度為O((MNK)2);步驟5的算法復雜度為O(J)。因此，總體的最壞算法復雜度為O(I(J×J!+MNKJ+(MNK)2))。

4 仿真實驗

4.1 實驗參數(shù)設置

為分析和評估本文提出的ECO算法的性能。假設各個數(shù)據(jù)中心均使用3種不同規(guī)格的物理機器來構(gòu)建云仿真環(huán)境，參照文獻[18]中的實驗方案，設置了3個云服務提供商、共15種不同類型的虛擬機實例進行仿真實驗，詳細參數(shù)如表1～表3所示。實驗時設置各個數(shù)據(jù)中心均使用3種不同規(guī)格的物理機，物理機的具體結(jié)構(gòu)和相關(guān)的能耗設置如表4所示。每個云服務提供者均擁有3個數(shù)據(jù)中心，數(shù)據(jù)中心內(nèi)部帶寬為200 MB/s，屬于同一云服務提供者的不同數(shù)據(jù)中心之間的數(shù)據(jù)傳輸帶寬為100 MB/s，屬于不同云服務提供者的數(shù)據(jù)中心之間的數(shù)據(jù)傳輸帶寬為50 MB/s。

此外，實驗中使用的4種不同的工作流如圖1所示，這些工作流實例的到達時間服從泊松分布且λ=0.01，任務所需的計算量大小服從范圍[10 000,50 000] MIPS的均勻分布。而且，參照文獻[17]中的設置，任務輸入/輸出數(shù)據(jù)的大小服從[50,350] MB的均勻分布。

表1 云服務提供商1虛擬機實例參數(shù)設置

表2 云服務提供商2虛擬機實例參數(shù)設置

表3 云服務提供商3虛擬機實例參數(shù)設置

表4 物理機參數(shù)設置

為評估ECO算法的性能，選用以下5個算法作為對比算法：

(1)在線多工作流調(diào)度框架[19](onliNe multi-workflOw Scheduling Framework，NOSF)。通過采用本文中的能耗計算模型，ECO算法與該算法比較執(zhí)行工作流所需成本與能耗。

(2)能耗感知的虛擬機調(diào)度方法[20](Energy-aware VM Scheduling method，EVMS)。該算法參數(shù)設置與文獻[20]相同，ECO算法與該算法比較所需能耗。

(3)改進的微粒群優(yōu)化算法[21](Improved Particle Swarm Optimization， Improved PSO)。該算法參數(shù)設置與文獻[21]相同，ECO算法與該算法比較所需能耗。

(4)異構(gòu)計算環(huán)境下最早完成時間算法[22](Heterogeneous Earliest-Finish-Time algorithm，HEFT)與異構(gòu)計算環(huán)境下多目標最早完成時間算法[22](Multi-Objective Heterogeneous Earliest-Finish-Time algorithm，MOHEFT)。這兩種算法的參數(shù)設置均與文獻[22]相同，ECO算法與其比較所需成本。

4.2 對比實驗結(jié)果

如圖2所示為在工作流實例數(shù)量變化的條件下各算法性能比較實驗結(jié)果。由圖2a能耗對比可以看出，ECO算法比其他算法在節(jié)能方面的性能優(yōu)于其他算法，這是因為Improved PSO算法與EVMS算法雖然為任務找到了合適的虛擬機類型，但未考慮虛擬機復用，虛擬機的計算資源閑置導致資源浪費；NOSF算法雖然考慮到了虛擬機復用，但是忽略了輸出數(shù)據(jù)集對算法性能的影響。由圖2b成本對比可以看出，ECO算法在降低或節(jié)約成本方面也優(yōu)于其他對比算法。而且，通過圖2中的實驗結(jié)果可知，隨著所調(diào)度的工作流實例數(shù)量的增長，ECO算法相對其他算法在降低能耗與成本方面的效果越明顯。

圖3展示了在不同的數(shù)據(jù)中心資源利用率情況下各算法性能比較實驗結(jié)果。其中，60%的初始資源利用率意味著在待調(diào)度的工作流任務未到達數(shù)據(jù)中心之前，已有60%的物理機資源被占用。從結(jié)果對比可以看出，隨著數(shù)據(jù)中心初始資源利用率變高，任務不能在同一數(shù)據(jù)中心處理的概率的越高，因此所有算法的結(jié)果曲線的增長速率一直在增長，但可以看出ECO算法是增長最緩慢的，這是因為ECO中的任務組選擇策略將多個連續(xù)任務交由同一虛擬機執(zhí)行，大大減少了數(shù)據(jù)傳輸損耗。值得一提的是HEFT算法的執(zhí)行花費不會隨著數(shù)據(jù)中心初始資源利用率變化，這是因為HEFT算法為每個任務分配的最高級的虛擬機，所以虛擬機存在大量空閑時間可用于跨數(shù)據(jù)中心的數(shù)據(jù)傳輸，則執(zhí)行花費不變。而且，通過圖3中的實驗結(jié)果可知，隨著數(shù)據(jù)中心利用率的增長，ECO算法相對其他算法在降低能耗與成本方面的效果越明顯。

圖4展示了在不同規(guī)模的工作流任務輸出數(shù)據(jù)量情況下各算法性能比較實驗結(jié)果。由圖4a能耗對比可以看出，EVMS和PSO算法隨任務平均輸出數(shù)據(jù)量的增大變化較小，這是因為它們沒有虛擬機復用策略導致虛擬機存在空閑時間，而輸出數(shù)據(jù)量增大時所形成的傳輸數(shù)據(jù)的時間可以由這些虛擬機的空閑時間完成。而且，ECO算法結(jié)果曲線比NOSF算法更為平緩。這說明ECO算法中的任務組選擇策略能有效降低由數(shù)據(jù)傳輸導致的能源與成本。由圖4b對比可以看出相似的規(guī)律。

5 結(jié)束語

針對如何在云際協(xié)作環(huán)境中高效實現(xiàn)兼顧成本與能耗的云工作流調(diào)度問題，本文在前期研究工作的基礎(chǔ)上，建立了該問題對立的工作流調(diào)度模型，并設計了一種云際協(xié)作環(huán)境下能耗與成本感知的工作流調(diào)度方法ECO。在今后的工作中，將結(jié)合數(shù)據(jù)中心資源利用率預測方法，進一步研究云工作流節(jié)能調(diào)度問題。