混合云環境下考慮工作流的任務調度策略

翟青海, 謝曉蘭

(桂林理工大學 a.信息科學與工程學院; b.廣西嵌入式技術與智能系統重點實驗室, 廣西 桂林 541006)

0 引 言

云計算技術有低成本、 配置靈活和資源利用率高的特點, 正在以極快的速度興起。云計算的計算中心由一系列的異構網絡服務和計算資源組成[1]。在云計算領域中, 任務調度策略對用戶的任務執行效率以及云環境下資源的使用效率有十分重要的作用。任務調度就是根據當前的目標要求, 將不同的任務調度到合適的資源上, 建立適當的任務執行順序, 使得該調度策略盡可能滿足當前目標要求。

混合云是一種將私有云資源和公有云資源結合起來使用的云計算環境[2]。但是由于安全性因素, 企業不希望將一些數據放至公有云上托管。而混合云模式則既可以提供私有云的安全性以達到對敏感數據的安全保證, 又可以利用公有云龐大的計算資源處理非關鍵任務和數據。因此， 研究混合云下的任務調度具有重要意義。

針對云計算環境下的工作流調度問題, 許多研究者將元啟發式算法引入到云任務調度中, 元啟發式優化算法可以降低搜索空間的復雜性并且算法運行的時間也可以接受。羅智勇等[3]提出了一種面向云計算的花朵差分授粉工作流算法, 該算法將工作流任務和虛擬機建模成花粉, 將完整的調度序列建模成花朵, 再利用任務的偏序關系進行離散花朵授粉過程。Singh等[4]提出了基于蟻群算法的混合云工作流調度模型, 在滿足任務的最低期限的基礎上, 降低任務的執行成本。徐俊等[5]提出了基于混合蛙跳算法的調度優化策略, 該算法利用時間貪心算法來優化初始種群以提高搜索效率, 同時增加對局部最優個體的重建策略跳出局部最優, 增加全局搜索能力， 由于使用貪心算法提高了初始化種群質量, 使得算法搜索耗時縮短。黃婷婷等[6]提出了基于模擬退火和遺傳算法結合的多目標優化算法, 首先利用任務的影響程度生成合適的初始化種群; 再對交叉、 變異等遺傳操作產生的個體分別進行模擬退火操作, 避免引起早熟收斂問題； 最后在變異階段引入失敗率, 提高調度結果的可靠性。針對混合云環境下的任務調度問題, Sanaj等[7]提出了在混合云環境下保證服務完成時間的基礎上最大化私有云利潤的鯨魚優化算法, 該算法相對人工蜂群和遺傳算法具有更高的效率。Zhou等[8]提出了兩種有效的混合云工作流調度方法, 既考慮了完成時間又考慮了完成成本: 單目標工作流調度優化方法用于優化截止期約束下的完成成本, 多目標工作流調度優化方法用于同時優化完成時間和完成成本。

本文根據混合云環境下的工作流調度問題特點建立了相關問題模型, 借鑒黏菌算法(slime mould algorithm,SMA)和粒子群算法(particle swarm optimization,PSO)的思想對算法進行重新設計: 當黏菌個體解的質量較差時, 有較大概率保留全局最優解的特征, 加快較差解的收斂速度; 當解的質量較好時, 則進行局部變異, 避免陷入局部最優; 同時, 加入了交叉算子解決當任務調度問題中解空間較大時, 局部尋優粒度不夠的問題。

1 混合云環境下工作流調度模型

1.1 混合云的相關定義

1)混合云模型: 目前, 越來越多的公有云廠商和私有云廠商向混合云轉型。如果企業和用戶最終需要同時訪問本地和云服務提供商提供的資源, 則使用混合云模型, 即選擇同時使用公共云和私有云。

私有云作為企業或個人所獨有的專有云平臺, 其規模相對公有云而言不會很大, 因此提供的各類資源一般比較有限。而公有云是由云服務提供商架設好大規模的IT基礎設施, 通過互聯網為企業提供服務器、 存儲、 應用程序等租用服務。公有云通常是指可以同時提供大量的虛擬機實例供用戶使用的云平臺。因此, 本文假設公有云總有足夠的資源處理任務, 并且每一個任務都在不同的虛擬機上執行。

2)計費模型: 公有云資源由公有云提供商提供, 云服務提供商會根據其向用戶提供的資源收取一定的費用。2017年, 微軟、 亞馬遜和阿里云等服務商實現了按秒計費[9], 不需要將虛擬機的啟動時間和銷毀時間計算在內。 而私有云為企業個體所有, 數量有限, 但是基本不需要考慮使用費用的問題。因此, 本文混合云的計費方法僅考慮公有云的收費, 計算方法為

(1)

其中:pricej表示公有云資源j的單位價格；Start_Timei表示任務i的運行開始時間;End_Timei表示任務i的運行結束時間。Start_Timei和End_Timei的計算方式如式(4)和式(5)。

1.2 工作流的相關定義

1)虛擬機模型: 服務商一般采用虛擬機進行抽象表示其計算資源, 用戶可以租用虛擬機執行工作流任務, 虛擬機可以用六元組M={id,ispublic,type,mip,costper,ram}表示。其中:id表示虛擬機的標識;ispublic表示該虛擬機是否屬于公有云;type表示虛擬機的型號; 同一型號的參數mip、costper、ram值相同,mip為虛擬機的運算能力,costper為租用虛擬機的單位時間費用,ram為虛擬機的內存。

2)任務模型: 任務采用六元組表示N={id,task_length,size,depth,parent_task_list,child_task_list}。 其中,id表示任務的標識；task_length表示任務的操作指令數；size表示任務的存儲大小；depth表示任務在工作流當中的深度層級, 如圖1所示, 任務之間的執行順序可以用有向無環圖(DAG)表示, 圖中共有6個任務, 并且任務1的深度為1, 任務2、 3、 4、 5的深度為2, 任務6的深度為3；parent_task_list表示當前任務的上一個深度的任務集合；child_task_list表示當前任務的下一個深度的任務集合。

圖1 任務深度

3)執行時間Texe(ti,mj)表示工作流中任務ti在虛擬機mj上的執行時間

Texe(ti,mj)=task_lengthti/mipmj,

(2)

其中,mipmj表示虛擬機mj的處理能力。

4)傳輸時間Ttrans(ti,tk)表示任務ti和任務tk之間的數據傳輸時間, 可由式(3)計算得出。當任務ti和任務tk處于同一個虛擬機時, 則傳輸時間為0。

(3)

其中:sizeti表示任務ti的傳出數據大小;Bwi和Bwk分別表示任務ti和任務tk所在虛擬機的帶寬。

5)任務ti的實際開始時間Start_Timei的計算方式如式(4)所示。當該任務沒有父節點時, 則為起始節點, 開始時間為0； 否則， 需要等待該任務的所有父節點任務執行完成并將數據傳輸至該任務所在的虛擬機上才能開始執行。

(4)

6)任務ti的完成時間End_Timei表示任務ti在對應虛擬機上的完成時間

End_Timei=Start_Timei+Texe(ti,mj)+Ttrans(ti,child)。

(5)

1.3 多目標模型

假設有n個任務Task={t1,t2, …,tn},m個虛擬機vm={vm1,vm2, …,vmm}, 則關于調度目標模型如下:

1)調度時間Tmakespan, 表示整個工作流的調度執行時間, 即為最后一個任務計算完成的時間和第一個任務開始的時間差

Tmakespan=End_Timelast-Start_Timefirst。

(6)

2)執行費用cost, 表示完成整個工作流任務所需要的執行花費

(7)

costperj表示租用虛擬機j的費用。

3)多目標優化, 適應度是評價智能算法解優劣程度的重要指標, 由于本模型的目標是使調度時間Tmakespan和執行費用cost盡可能小, 因此適應度函數可以由調度時間和完成成本計算

Fitness=w1Tmakespan+w2cost,

(8)

w1、w2分別為調度時間和執行費用的權重, 且滿足w1+w2=1。在本文中, 適應度值Fitness越小, 表示解的質量越好。

1.4 編碼模型

參考文獻[2]的編碼方法解決混合云環境下的工作流調度編碼問題。一個可行解的調度方案如式(9)所示, 由3條染色體編碼組成

scheduler=(task_order,vm_order,vm_type),

(9)

3條染色體都由一個一維數組表示, 由于一個任務最多可放置在一個虛擬機上, 且本文定義公有云資源數量為無限多, 因此3個數組長度都相同, 長度為參與該次調度過程的任務數量。task_order表示任務的調度順序, 數組中每個值表示任務的id, 該數組表示具有依賴關系的調度順序；vm_order表示每個任務到虛擬機的映射關系, 數組中每個值表示虛擬機的id；vm_type表示每個虛擬機對應的虛擬機型號。

2 算法流程

2.1 黏菌算法

黏菌算法是根據黏菌在尋找食物過程中的變化建立的智能搜索算法。主要模擬黏菌在覓食過程中的行為和形態變化, 通過權值指標模擬黏菌靜脈狀管的形態和收縮模式之間的3種相關性[10]。在黏菌覓食過程中, 根據空氣中的食物濃度接近食物, 食物濃度越高, 生物振蕩波越強, 細胞質流動越快, 黏菌靜脈狀管越粗, 該區域會聚集更多黏菌; 當該區域的食物濃度較低時, 黏菌會有較大概率探索其他區域。黏菌接近食物的表達式

(10)

p=tanh|S(i)-DF|;

(11)

a=arctanh(-t/tmax)+1)。

(12)

(13)

式中:r為[0, 1]間的隨機數;bF表示在當前迭代過程中最佳的適應度;S(i)表示當前個體適應度值;wF表示在當前迭代過程中最差的適應度值;i=C表示種群中適應度值最好的前一半個體;i=O表示其余個體;Sort(i)按照適應度值排序的氣味指數。

當黏菌找到了更好的食物, 仍然會分離出部分個體探索其他區域進行全局尋優, 黏菌種群更新位置的計算方法為

(14)

rand是[0, 1]間的隨機數,LB與UB表示解空間的上下邊界,z是進行全局尋優的閾值。

2.2 本文算法設計

由于傳統的黏菌算法和粒子群算法都是用于連續的數值優化, 進行迭代計算的都是實數, 但是工作流調度問題都是組合優化問題, 解由3組整數序列組成, 因此， 本文對算法進行重新設計。本文工作流調度算法的基本思想如下: 首先隨機初始化符合工作流執行序列的初始種群, 計算種群中個體的適應度值, 并確定最佳的適應度值, 之后采用交叉算子對每個個體進行計算, 計算個體的適應度值判斷是否進行粒子群優化全局尋優或局部變異， 最后標識出當前種群中的最優個體Gbest。算法的主要符號說明如表1, 具體步驟如下。

表1 主要符號說明

步驟1:按照算法1初始化種群, 并計算每個個體的適應度值和當前最優個體Gbest。

算法1 種群初始化算法INPUT: 工作流任務集合G, 種群規模NPOUTPUT: 相應規模的個體種群pop1.init i=02.while i

步驟2:按照文獻[2]的做法更新任務調度順序task_order。

步驟3:每個個體的vm_type根據算法2進行交叉計算, 其中v和b的計算方法為

v=|-b+(2·b)·r|;

(15)

b=0.25-iter/(max_iter·4)。

(16)

其中:r表示區間[0, 1]內的隨機值;iter表示當前迭代次數;max_iter表示最大迭代次數；v表示交叉的位點個數, 隨著迭代次數的增加而逐漸變小, 細化局部尋優的粒度進而增加算法的局部尋優能力。

算法2 交叉算法INPUT: 交叉個體X, 較優個體XbOUTPUT: 交叉個體X’1.按照式(15)計算交叉位點個數num2.init start=random(0, T_length-num)3.init end=start+num4.while start

步驟4:按照式(17)判斷個體的vm_type迭代方式, 其中r表示區間[0, 1]內的隨機值, 當解的質量較差時, 則有較大概率按照算法3進行迭代, 這樣可以在前期加快全局尋優的速度。p值的計算方法為式(18), 在算法3中個體的速度值Vel按照式(19)和式(20)進行計算。由于個體位置vm_type的值為離散型變量, 采用相減的計算方法意義不大, 因此， 本文采用與運算處理離散型變量加快解的收斂速度。

(17)

p=tanh|best_fitness-fitness(X(j))|;

(18)

(19)

(20)

其中：c1和c2分別表示全局最優解和個體最優解的權重;best_fitness表示全局最優解的適應度值;fitness(X(j))表示當前個體j的適應度值;xg和xb分別表示全局最優解的vm_type和個體中最優解的vm_type。

算法3 全局尋優算法INPUT: 全局尋優個體X, 全局最優個體Xg, 個體最優XbOUTPUT: 全局尋優個體X’1. init j=02. while j

在算法4變異算法中,v和b的計算方式如式(15)和式(16)。由于解空間很大, 因此算法4并沒有對所有位點進行變異,而是基于較優的個體選擇局部位點進行變異。

算法4 局部變異算法INPUT: 局部變異個體XOUTPUT: 局部變異個體X’1.按照式(15)計算交叉個數num2.init j=0, x=[num]3.while j

步驟5:按照式(8)計算每個個體的適應度。

步驟6:更新當前迭代全局最優解和個體在迭代中的最優解,并判斷是否達到最大迭代次數,若未達到,則繼續從步驟2開始執行；若達到最大迭代次數,則停止搜索, 當前的全局最優解即為最終結果。

3 實驗與結果分析

為驗證本文設計算法在處理混合云環境下考慮工作流任務調度問題的有效性和可行性, 使用WorkflowSim作為仿真平臺, 在同樣的條件和環境下實驗, 并和經典的粒子群算法、 遺傳算法以及文獻[11]的算法進行對比。設置10種虛擬機類型,虛擬機配置參考亞馬遜的類型[12](表2),帶寬速度設置為0.02 GB/s,存儲費用為0.000 1 ＄/(GB·h)。實驗設置迭代次數為1 000次,w1、w2為0.5, 種群個體數為60, 私有云虛擬機數占總虛擬機數的1/5。實驗采用4種科學工作流模型, 即模型Epigenomic、

表2 虛擬機配置

Inspiral、 Montage和 Sipht。將這4種工作流的數據集進行優化調度, 各類算法在不同數據集和不同任務數量的完成時間和完成成本如圖2—4所示。隨著任務數量的增加, 由于遺傳算法的全局尋優能力較低, 因此性能普遍較低, 而文獻[11]的改進算法相對于遺傳算法和粒子群算法這兩種算法效果都要好。但是在任務數量較多時, 由于本文的算法有更細粒度的局部尋優能力, 因此在4種數據集上的整體表現都優于其他3種算法。

圖2 50個任務完成時間(a)和完成成本(b)

圖3 100個任務完成時間(a)和完成成本(b)

圖4 1 000個任務完成時間(a)和完成成本(b)

4 結束語

本文以黏菌算法為基本的研究思路, 在算法前期借鑒了粒子群算法的思想, 加快全局尋優速度, 同時增加了交叉算子提高局部尋優的粒度, 在算法迭代后期通過變異算子, 避免陷入局部最優。從實驗仿真結果看, 隨著任務數量的增加, 本文算法的尋優能力比其他算法更優。但是, 本文算法依然存在有待改進的地方, 如當某一個任務的屬性值和其他任務有明顯差異時, 該任務的分配結果會顯著影響算法尋優, 后續將針對該問題進行研究。