一種任務合并機制下的云工作流多階段調度方法

2019-12-12 07:06:34黃志剛

計算機應用與軟件 2019年12期

關鍵詞：資源

黃志剛劉峰

1(湖南科技職業學院湖南長沙 410004 )2(長沙理工大學計算機學院湖南長沙 410082)

0 引言

工作流是復雜計算問題的常用建模方式，云計算特有的按需提供和即付即用的資源定制模式使得云環境下進行調度工作流變得更為復雜[1]。工作流任務結構與傳統批或包任務的調度方法極為不同，工作流任務通常擁有嚴格的執行次序，或稱邏輯依賴，需要在滿足用戶指定的服務質量約束的前提下，對各任務實現與其對應虛擬機資源的映射。工作流調度過程中的調度任務選擇與虛擬機實例提供決策對于是否能夠滿足給定約束和全局調度代價均具有重要影響[2]。傳統的調度方法偏向于關注調度效率，忽略了資源利用費用，此時的調度問題在不同資源和不同調度方案下的執行時間和代價均有所不同。因此，云環境下需要同步考慮用調度時間和調度代價，這更符合云工作流的調度場景[3]。

有關研究中，文獻[4]設計了基于執行時間和調度費用的多目標工作流調度算法，作者將多目標轉化為單目標優化進行了優化方案的求解，但卻忽略了云資源虛擬機的性能變化，僅討論了同質資源的情形。文獻[5]設計基于局部關鍵路徑的調度算法IC-PCP，IC-PCP優先將處于局部關鍵路徑上的任務調度至最低代價虛擬機上執行，避免了每個局部關鍵路徑的通信代價，實現截止時間的約束，但算法卻忽略了虛擬機的啟動和部署時間，這在實際場景中占比較重。文獻[6]中提出的RTC和RCT算法是分別針對執行時間優先和執行代價優先提出的工作流調度最優化算法，均是單目標無約束式優化，費用與時間只考慮了一種，不符合云工作流實際調度特征。與上文不同，文獻[7]提出一種基于粒子群的工作流調度優化算法，雖然考慮了資源提供彈性與異構特征，但利用智能優化算法仍然無法擺脫時間復雜度過高和早熟問題。文獻[8]在混合云中設計一種整數非線性規化方法求解工作流調度，其目標是滿足截止時間約束最小化執行總代價。文獻[9]提出一種動態規化方法處理多約束工作流調度問題，但沒有考慮多類型異構虛擬機提供場景。

本文將設計時間復雜度更低的工作流調度算法，滿足截止時間的同時尋找工作流調度優化最優可行解。本文設計了一種代價優化的工作流調度算法WSCO，算法著重考慮了云資源提供時虛擬機性能的動態性和異構性，最終實現在不同要求的截止時間約束程度下的工作流調度代價的最小化。

1 系統模型

1.1 應用模型

云計算工作流應用W=(T,E)可表示為有向無循環圖DAG，T={t1,t2,…,tn}代表任務的圖頂點集，E代表任務間數據傳輸關系的有向邊集，邊eij表示任務對(ti,tj)間的順序約束關系，ti,tj∈T,ti≠tj，表明任務tj(子任務)只能在ti(父任務)完成并傳輸相關數據后才可以開始執行。換言之，子任務在其所有父任務完成且數據傳輸完成之前是無法執行的。截止時間D用于限定所有工作流任務完成的最后期限。工作流示例如圖1所示，每個節點代表一個任務，邊值代表任務間的數據傳輸時間。

圖1 工作流示例

1.2 資源模型

云資源由IaaS云服務提供者提供的虛擬機資源構成，假設所有計算或存儲資源處于同一數據中心內，則服務間的帶寬是相同的。計算資源由不同類型的虛擬機VMs提供，各VMs類型擁有不同的CPU類型、內存大小和定價。假設應用任務租用的VM實例數量不受限制，且一個VM被租用時，需要有啟動時間進行初始化。相應地，VM被釋放時，需要有一定的關機時間停止服務。VM定價模型使用基于即付即用的帳單策略(與商業云Amazon EC2相似)，用戶根據租用VM的時間間隔Tintervals進行付費，Tintervals由云提供商定義，如Amazon以一小時作為付費間隔。因此，即使VM利用不足一小時，也將以一小時付費。云資源模型中，將VM類型VMv定義為一個二元組{(ETti)v,Cv}，描述每個任務ti的估計計算時間和每個Tintervals的代價。任務ti執行于VMv類型的VM上的代價計算為：

調度于不同VM的任務間的數據傳輸時間TT(eij)計算為dti/β，其中，dti為ti與tj間的輸出數據量，β為數據中心的帶寬。當兩個任務調度于同一VM時，TT(eij)=0。

1.3 問題定義

本文的目標是尋找工作流的調度方案，使得執行代價達到最小，并且滿足用戶定義的截止時間要求。為了得到截止時間限定下的調度方案，首先需要確定截止時間是否可達，若不可達，調度問題將沒有可行解，需要修正截止時間。在截止時間內可完成的情況下，目標即是在截止時間約束下為每個任務尋找合適的調度決策，進而實現調度代價的最小，該過程涉及以下三個決策問題：

1)cheapesttask-VMmapping：代價最低映射，用于為等待調度的每個任務尋找代價最低的VM類型：

cheapesttask-VMmapping={(ti→VMv)}

2)ProvisioningPlan：用于基于運行任務的狀態和等待任務的cheapesttask-VMmapping確定不同階段工作流執行時每種VM類型的利用數量。定義資源池中的每一個VMvk均擁有類型type、開始時間stk及結束時間etk等屬性：

VMPool={vk,type(vk),stk,etk}

3)SchedulingPlan：用于決定任務ti調度于資源池中的哪個VM類型vk及任務相應的估計開始時間tstart和結束時間tend：

Schedule={ti,vk,tstart,tend}

算法目標是尋找工作流應用W的調度方案S，使得工作流的調度總代價達到最小，并且總體執行時間TET不超過截止時間D的約束，可形式化為：

(1)

s.t.TET≤D，TET=maxti{AFT(ti)}

2 相關說明與定義

文中涉及的主要符號含義說明如表1所示。

表1 符號說明

續表1

1)MET(ti)：任務ti的最小執行時間定義為任務ti在所有可用VM類型中，在擁有最小執行時間ET(ti,VMv)的VM實例類型VMv∈VMset上執行時得到的時間，表示為：

(2)

2)EST(ti)：任務ti的最早開始時間定義為其所有前驅任務在最快VM類型上調度且關聯數據已傳送至ti時的開始執行時間，表示為：

(3)

3)EFT(ti)：任務ti的最早完成時間定義為：

EFT(ti)=EST(ti)+MET(ti)

(4)

4)XFT(ti)：任務ti調度至VMvk時的期望完成時間定義為：

(5)

5)XST(ti)：任務ti的期望開始時間定義為其所有前驅調度后ti開始執行的估計時間，表示為：

(6)

6)XIST(vk)：資源池中一個活動VMvk的期望空閑開始時間為vk期望完成其上調度的最近任務的時間。若tp為調度于vk的最近任務，則vk的期望空閑開始時間為：

(7)

7)LFT(ti)：任務ti的最遲完成時間定義為所有任務在工作流截止時間D之前完成時ti完成的最遲時間，表示為：

(8)

8)LST(ti)：任務ti的最遲開始時間定義為所有任務在工作流截止時間D之前完成時ti開始執行的最遲時間，表示為：

LST(ti)=LFT(ti)-MET(ti)

(9)

9)XET(ti,VMv)：VM類型VMv上從任務ti開始的關鍵路徑(最長執行路徑)的期望執行時間定義為從ti開始執行整個關鍵路徑任務的總時間，表示為：

(10)

10)MET_W：工作流最小執行時間為所有任務均執行于最快VM時的關鍵路徑長度(時間)，即最長的執行路徑，表示為：

(11)

11)CLI(vk)：租用VMvk的當前租用間隔定義的是該VM被租用索價的時間跨度。給定vk提供的時間stk，帳單的時間單位Tintervals以及當前的Tintervals(n)，則CLI(vk)可表示為：

CLI(vk)=[stk,stk+n×Tintervals]

(12)

3 算法設計

算法1給出了WSCO算法的偽代碼。算法首先需要驗證截止時間D的可達性。對于可達的截止時間，需要大于工作流的最小執行時間MET_W。因此，算法首先評估MET_W并將其與截止時間D作比較，若D大于MET_W，算法繼續尋找合適的調度；否則，用戶將修正截止時間D。一旦確定了截止時間的可達性，算法通過預處理步驟和控制循環過程確定所需的調度方案。預處理步驟通過合并管道任務為單個任務降低算法運行開銷，控制循環過程維持運行任務的更新信息并相應為等待的未調度任務作出調度決策。以下對算法作詳細描述。

算法1WSCO算法

輸入: 工作流W(T,E) ，代價矩陣C，執行時間矩陣ET，傳輸時間TT，截止時間D以及作務請求間隔

1.開始

2. 以式(2)(3)(4)(11)計算MET_W

3. 若D>MET_W

4. 調用算法2進行管道任務合并

5. 計算MET,LFT和XET

6. 尋找工作流結構的根節點為{tentry}

7.for每個屬于{tentry}中的任務te

8.To_Provision←CheapesttaskVMMap(te)

//調用算法4

9. 生成類型為To_Provision的虛擬機ve

10. 在時間XST(te)時將te調度至ve

11. 更新虛擬資源池VM_Pool_Status

12.結束for循環

13.whileT中所有任務未完成

14. 發送調度任務至執行管理器

15. 更新任務AST，XFT

16. 將任務ti的父任務集中被調度和正在運行的任務組成任務集合to_be_scheduled

17. 在任務集to_be_scheduled上調用算法3

18.結束while循環

19.結束

20. 在MET_W以內修正截止時間

21.結束if

22.結束

3.1 任務預處理

為了降低任務運行時開銷，算法通過任務預處理過程將管道任務合并為單個任務執行，如圖2所示。預處理可以節省任務間通信的數據傳輸時間，加快動態調度方案的生成。圖3為預處理示例，任務t1和t2可合并為任務t1+t2，這使得t2可以在與t1相同的資源上執行并在本地直接利用t1的執行結果，避免t1與t2在不同資源上執行時的數據傳輸時間，降低循環控制過程中的運行開銷。預處理步驟的執行過程如算法2所示。

圖2 管道任務

圖3 合并管道任務

算法2Pre-processing(W)

輸入: 工作流W(T,E)

1. 開始

2. 入口任務{tentry}置入初始任務隊列tksqueue

3.while任務隊列tksqueue非空

4. 隊首任務賦予tp

5.tp的子任務置入Sc

6.ifSc的基數為1且tc僅有一個父任務tp

7. 合并tp和tc為tp+c

8. 設置tp+c為tc子任務的父任務

9. 新任務執行時間ET(tp+c)

10. 添加合并任務tp+c至隊首

11.else

12. 添加tp的子任務至隊列tksqueue的隊尾

13.結束if

14.結束while循環

15.end

3.2 循環控制過程

預處理后，算法提供代價最低的可用資源(cheapestapplicable)用于執行工作流入口任務，然后進入循環控制過程。由于入口任務是第一個調度任務，故入口任務的期望開始時間XST設置為期望VM獲取時間(expectedVMacquisitiontime)。在每次循環控制中，算法更新調度運行任務的實際開始時間AST，確定父節點已被調度的任務及將運行(to-be-scheduled)的任務，然后利用PlanandSchedule算法作出合適的調度決策。循環控制過程直到所有工作流任務被調度時結束。在每一階段中，任務的cheapestapplicableVM類型由CheapesttaskVMMap算法決定，若T時刻請求一個新的VM，則此時確保VM可用的expectedVMacquisitiontime也為T。

1) PlanandSchedule算法。PlanandSchedule算法接收一個任務集作為輸入，并將其調度至合適(appropriate)VM實例上。與CheapesttaskVMmap算法一致，該算法尋找最小代價且擁有最小數據傳輸時間的調度方案。算法試圖將一個任務調度至最后一個父節點(擁有最大期望完成時間XFT的父任務)相同的資源上，以避免調度在不同資源時的數據傳輸。PlanandSchedule如算法3所示。

算法3PlanandSchedule算法

1. 將虛擬機池中的活躍虛擬機列表賦予Active_VMs

2.for任務列表中的每個任務t

3.vmmap←CheapesttaskVMMap(ti)

4. 尋找滿足約束條件的目標虛擬機集合

5.if{vk}存在

6. 尋找XIST(vk)與XST(ti)差值最小的虛擬機vk

7. 在vk調度任務ti并更新XST(ti)

8. 更新虛擬機資源池VM_Pool_Status

9.else

10. 尋找滿足約束條件的目標虛擬機集合

11.if{vj}存在

12. 尋找XIST(vj)與XST(ti)間差值最小的虛擬機vj

13. 在vj上調度任務ti并更新XST(ti)

14. 更新虛擬機資源池VM_Pool_Status

15.else

16. 生成新虛擬機

17. 按XST在v上調度任務ti

18. 更新虛擬機資源池VM_Pool_Status

19. 結束if

20.結束if

21.結束for循環

22. 撤銷關閉空閑虛擬機

23.返回

對于任務列表中的任務ti，PlanandSchedule算法調用CheapesttaskVMmap算法(即步驟3)得到調度ti的cheapestapplicableVM類型vmmap。由于VM按完整的時間間隔Tintervals收取費用，因此為了盡可能密集地利用VM，PlanandSchedule算法試圖決策是否ti能夠在當前租用間隔CLI結束前調度于已經租用的VM上。為了完成這個目標，算法首先尋找與vmmap同類型且滿足以下條件的活動VMs {vk}：

(1) 若ti調度于vk，ti僅利用CLI(vk)的剩余時間部分；

(2)ti的期望完成時間小于或等于ti的最遲完成時間；

(3) 若ti調度于vk，不存在任一ti的子任務tc，使得tc的期望開始時間大于tc的最遲開始時間。

若該活動VM集合存在，則從該集合中選擇擁有最小期望空閑開始時間XIST與期望開始時間之差的VMvk用于調度ti。XST(ti)與VM_Pool_Status通過步驟4-步驟8進行更新；否則，PlanandSchedule算法試圖尋找活動VMs{vj}，使得type(vj)≥vmmap且以下條件得到滿足：

(1) 若ti調度于vj，ti可在CLI(vj)的剩余時間內完成；

(2)ti的期望完成時間小于或等于ti的最遲完成時間；

(3) 若ti調度于vj，不存在任一ti的子任務tc，使得tc的期望開始時間大于tc的最遲開始時間。

若該活動VM集合存在，則從該集合中選擇擁有最小期望空閑開始時間XIST與期望開始時間之差的VMvj用于調度ti。XST(ti)與VM_Pool_Status通過步驟10-步驟14進行更新；若不存在活動VMs可利用于調度ti，則需要從云端生成新的VM類型vmmap調度ti，即步驟16-步驟18。任務列表中的所有任務調度后，PlanandSchedule算法需要查證無任務調度的空閑VMs及已完成任務的VMs，即步驟22。

2) CheapesttaskVMmap算法。CheapesttaskVMmap算法接收一個任務t作為輸入，并返回其cheapestapplicable的VM類型taskvmmap。盡管cheapestapplicable的VM類型可以在任務的最遲完成時間內完成任務，但可能不是最優選擇，這是因為選擇代價最小的VM類型并未考慮對其子任務的影響，即可能迫使子任務執行于更快的VM而增加了總代價。因此，算法將任務的cheapestapplicable的VM類型定義為代價最小類型的單個VM，若利用該VM類型調度關鍵路徑上從t開始的所有任務，則可在截止時間D內完成全部關鍵路徑任務的執行，即所討論的目標是利用最小的可能數據傳輸時間尋找最小代價的調度方案。因此，若任務t無需等待即可得到VM上一個空閑(免費)的時間間隔，則算法將確認任務t是否能夠調度于其最后的父任務(擁有最大期望完成時間的父任務)相同的VMvp上。若t調度于vp，XST(t)將被首次評估并與XIST(vp)比較。若XIST(vp)小于XST(t)(表明vp在t的期望開始時間上是空閑的，可用于調度t)，調度于vp上可確保在截止時間D前完成執行，然后可將taskvmmap設置為type(vp)，并更新XST(t)，即步驟4-步驟10。然后，PlanandSchedule算法將任務t調度于vp。否則，利用以下規則(步驟12-步驟18)更新XST(t)和對于t的taskvmmap：

(1) 確定VM類型集合{VMk}，使得從t開始的關鍵路徑若調度于類型VMk的單個VM上，可以D內完成執行；

(2) 從集合{VMk}中確定VM類型VMj，可使得該關鍵路徑的總執行代價最小。

算法4CheapesttaskVMMap(t)算法

1. 開始

2. 映射集合taskvmmap置空

3. ift不是入口任務

5. 將正在運行最后一個父任務的虛擬機賦予vp

7. if((temp≥XIST(vp))且(temp+XET(t,type(vp)))≤D)

8.XST(t) ←temp

9.taskvmmap←type(vp)

10. 返回映射集合taskvmmap

11.else

13.結束if

14.else

15.XST(t) ←acquisitiondelay

16.結束if

17. 尋找滿足(XST(t)+XET(t,VMk))≤D的集合{VMk}

19. 將虛擬機VMj置入映射集合taskvmmap

20. 返回映射集合taskvmmap

3.3 算例說明

本節通過一個算例說明算法的執行過程。以圖4作為工作流示例，包括9個任務t1-t9，邊上的數值表示任務間的數據傳輸時間。設有三種VM類型{VMs,VMm,VMl}(s-small,m-medium,l-large)用于工作流任務的執行。圖5是任務在各VM上的執行時間矩陣和數據傳輸時間矩陣,圖6是合并管道任務后的工作流結構。最小租用時間間隔設置為10 min，VM獲取延時acquisitiondelay設置為1 min，每個時間間隔的代價設置為：smalle類型VM為＄0.01，medium類型VM為＄0.02，large類型VM為＄0.04，截止時間設置為50 min。

圖4 工作流示例

(a) 執行時間矩陣 (b) 數據傳輸時間矩陣圖5 執行時間矩陣和數據傳輸時間矩陣

圖6 預處理后的工作流結構

算法首先需要通過式(2)、式(3)、式(4)計算每個任務的最小執行時間MET、最早開始時間EST和最遲完成時間EFT，計算結果如表2所示。然后，比較工作流的最小執行時間MET_W(max(EFT(ti)=49))與截止時間D(D=50)，由于MET_W小于D，表明截止時間是可達的，算法需要繼續尋找調度方案。

表2 圖4中工作流各任務的MET、LFT和XET

首先，通過算法2進行任務預處理。算法2通過合并管道任務t4、t7和t8、t9為單個任務t4+7和t8+9，預處理后的工作流結構如圖6所示，預處理后的執行時間矩陣和數據傳輸時間矩陣如圖7所示。

(a) 執行時間矩陣 (b) 數據傳輸時間矩陣圖7 預處理后的矩陣

預處理后，WSCO算法通過式(2)、式(8)、式(10)計算每個任務的最小執行時間MET、最遲完成時間LFT和期望執行時間XET，結果如表3所示。

表3 圖6中各個任務的MET、LFT和XET(D=50)

然后，算法調用CheapesttaskVMmap算法尋找代價最低的VM類型調度入口任務t1。CheapesttaskVMmap算法設置XST(t1)為acquisitiondelay，并尋找執行代價最小的VM類型。由于三種VM類型中，XET(t1,VMm)和XET(t1,VMl)均小于D，算法比較在這兩種VM類型上執行從t1開始的關鍵路徑得到的代價，并確定VMm為調度t1的cheapestapplicableVM。然后，算法獲得VMm類型的一個VM進行調度t1，并更新VM池狀態。算法在步驟13輸入while循環，并執行循環過程直到所有任務調度完成。表4-表7列出了算法執行過程中任務不同參數的取值變化。

表4 初始狀態

表5 第1次迭代結果

表6 第2次迭代結果

表7 第3次迭代結果

4 仿真實驗

4.1 實驗配置

利用WorkFlowSim[10]構建仿真實驗評估工作流調度算法性能，選取四種不同領域的現實科學工作流作為測試工作流結構，包括：Montage、CyberShake、LIGO和Epigenomics工作流，不同工作流在執行結構和計算特征上均有所不同，具體可參見文獻[1]。每種工作流均配置三種規模的任務，小規模為30個任務，中規模為100個任務，大規模為1 000個任務。

云服務商提供五種類型VM，其配置與處理能力參考Amazon EC2進行設置[11]，具體見表8，其中，一個ECU等同于1.0～1.2 GHz的Xecon CPU計算能力，VM間的平均帶寬設置為20 Mbit/s，接近于Amazon web service的平均帶寬能力。VM的啟動時間設置為97 s[12]，賬單間隔時間設置為10 min。

表8 VMs類型配置

設置三種截止時間類型評估算法性能，包括嚴格型、適度型和寬松型，截止時間D=(1+μ)×MET_W。對于嚴格型截止時間約束，0≤μ<1;對于適度型截止時間，1≤μ<2;對于寬松型截止時間，2≤μ≤3。且μ可視為約束因子，μ的變化步長為0.25。選擇基于部分關鍵路徑算法IC-PCP[5]、健壯代價時間算法RCT[6]和健壯時間代價算法RTC[6]作為基準算法進行性能比較。

4.2 結果說明

1) 截止時間約束的評估。表9給出了算法滿足截止時間比例的情況。對于嚴格型約束，IC-PCP在所有工作流中均無法滿足截止時間約束，RCT在四種工作流中按從高到低的滿足率分別為52.5%、47.5%、40%和37.5%，RTC則比RCT的約束滿足率更高，而WSCO是所有算法中對截止時間約束滿足最好的。對于適度型約束，IC-PCP的性能并未得到改善，RCT在先前的基礎上得到了輕微改善，RTC和WSCO則均達到了對截止時間100%的約束滿足。對于寬松型約束，IC-PCP性能不變，RCT繼續提高。可以看出，IC-PCP性能最差，這源于此算法并未預測VM的性能改變，且未考慮VM的啟動時間，RCT和RTC基于資源選擇策略，一定程度上忽略了VMs的性能變化，WSCO同時考慮了以上因素，能夠估算單個任務的開始時間和完成時間，可以盡可能地確保截止時間內完成任務調度。

表9 截止時間滿足比例

續表9

2) 執行時間與執行代價評估。圖8同步觀察了平均執行時間和平均執行代價情況，由于為了產生更加經濟的調度方案需要以更長的調度時間作為代價，故需同步觀察這兩個性能表現。可以看到，IC-PCP產生了最便宜的調度方案，但其執行時間長于截止時間，無法滿足截止時間約束。由于算法設計的目標是生成更高低價的調度且滿足截止時間，因此，以對截止時間違例得到的經濟調度方案也是無效的。另外三種算法中，RCT在所有約束因子上均產生了最經濟的調度方案，且調度時間也最長，但約束滿足率平均僅為50%。對于0～0.25間的嚴格型約束，WSCO產生了最高代價調度但其調度時間最短，且其約束滿足率也高于其他算法，這是由于該算法通過適應VM的性能變化能以可接受的代價降低截止時間的違例。同時，在同樣的條件下，RTC以最小的調度時間產生了最高代價的調度。比較來說，隨著約束因子的增加，WSCO可以充分利用增加的VM空閑時間在滿足截止時間約束的同時得到最低價的調度。進一步，對于所有的截止時間約束因子，平均來說，WSCO相比RTC可以降低34%的代價和增加46%的調度時間，相比RCT可以降低28%的代價和降低16%的調度時間。因此，綜合評價，WSCO可以降低代價并滿足截止時間來交付，比對比算法有著更好的性能表現。對于嚴格型約束，算法可交付最高的約束滿意率，代價也更高。然而，隨著約束變得寬松，WSCO也可充分利用增加的空閑時槽進而降低執行代價。