多DAG工作流在云計算環境下的可靠性調度方法

景維鵬,吳智博,劉宏偉,舒燕君

(1.哈爾濱工業大學計算機科學與技術學院,黑龍江哈爾濱 150001; 2.東北林業大學信息與計算機工程學院,黑龍江哈爾濱 150040)

?

多DAG工作流在云計算環境下的可靠性調度方法

景維鵬1,2,吳智博1,劉宏偉1,舒燕君1

(1.哈爾濱工業大學計算機科學與技術學院,黑龍江哈爾濱 150001; 2.東北林業大學信息與計算機工程學院,黑龍江哈爾濱 150040)

摘要:針對云計算環境中多個DAG科學工作流的可靠性調度問題,提出一種考慮虛擬機之間鏈路通信競爭的動態多DAG分層調度算法.首先使用通信競爭模型描述虛擬機之間的通信,然后分別計算主版本及副版本任務的最早完成時間,并限定任務所調度的虛擬機單元.再對多個同時到達的DAG工作流任務使用動態分層方法,計算每個DAG任務的不公平程度因子.該算法有效解決了當多個DAG中任務的權值相差較大時,之前到達的DAG不會因為剩余任務遲遲得不到調度而導致執行時間跨度增大的問題.仿真實驗表明,在保證可靠調度的前提下,該算法不僅能提高多個DAG調度的公平程度,而且能有效地縮短多個DAG調度的平均最早完成時間.

關鍵詞:云計算;多個DAG;可靠性調度;公平因子

云計算作為一種嶄新的計算模式得到越來越多的關注.它將各種分布的計算、存儲及應用資源進行整合并實現多層次的虛擬化與抽象化,有效地將各類資源以服務的形式提供給用戶.云計算中資源調度的目的是實現計算資源、存儲資源集合與調度任務集合滿足有效空間和時間映射關系.因此,云計算環境下設計有效解決任務之間依賴關系的資源調度策略,是實現云計算科學工作流高可擴展、高可用性的關鍵.

在云計算科學工作流的應用中,面臨的是海量密集型數據的處理,具體表現為:在云計算科學工作流調度過程中,存在多個有向無環圖(Directed Acyclic Graph,DAG)同時提交或在計算過程中動態提交的情況,因此要求多DAG的科學工作流的調度算法必須要滿足環境的動態變化和對動態到達的工作流進行實時處理的需求;企業級的工作流應用中,需要設置有效的容錯保障機制以容忍系統運行時遇到的故障;合理地調度機制應該保障用戶提交的科學計算請求不因數據中心的負載、位置而受到影響.文獻[1]從不同角度證明了調度算法在科學工作流應用中的重要性.

近年來,針對單個DAG任務的科學工作流調度,無論是調度模型,或是調度目標的多樣性均取得很大進展,然而針對科學工作流應用的多DAG調度的研究相對較少,文獻[13]提出一種逐個執行多DAG任務的方法,該方法導致虛擬機會產生大量的空閑等待時間,延長了任務的執行時間.文獻[2,4,13]提出將多個DAG合并成為一個復合DAG后,再使用調度整個DAG任務的方法來調度負荷后的DAG任務.這些方法均忽略了存在于各DAG之間調度的不公平性問題.

文獻[3]提出了一種Planner-guided的調度策略,算法使用動態RANK-HYBD方法對多DAG任務分配優先級,但該算法未考慮DAG任務在不同時間到達的情況.另外,由文獻[3]分析表明,簡單的DAG任務合并,并不能顯著提升算法的性能.文獻[14]提出了一種面向數據密集型應用的離線時間開銷多DAG任務調度算法,但該算法沒有解決之前到達的DAG任務不會因為剩余任務遲遲得不到調度而導致執行時間跨度增大的問題.綜上,如何有效地解決多DAG任務調度的公平性,滿足多個DAG任意時間提交的可靠性調度技術是云計算環境下多DAG調度問題的關鍵.

由于云計算是建立在大規模廉價服務集群上的一種新的服務模式,加上計算任務的復雜性和動態性,導致計算節點極易出現故障,因此,調度算法必須在探求整體任務的最短完成時間的情況下進行,提高任務調度的可靠性.文獻[5-8]中論述使用主副版本的調度機制是有效提高調度算法可靠性的主要方法.文獻[5]提出使用完全復制方法對任務進行復制,并定義執行副本的具體時間;文獻[6]提出一種能夠滿足最佳最早完成時間(Makespan)和可靠性的實時調度算法;文獻[7]在文獻[6]算法的基礎上使用Map Reduce編程框架,實現可靠性和性能最優;文獻[8]提出優先級約束、可靠性代價驅動的容錯調度方法,該算法強調“強主版本復制”,要求任務必須收到它所有前驅節點的結果,使該算法只考慮任務的前驅節點,而沒有考慮所有節點任務的完成問題.文獻[5,7-8]使用復制的方法在可靠性和系統性能之間取得折衷.但這些方法僅僅對復制任務本身進行判斷,沒有算法對副版本任務開始時間進行準確的計算,這樣使得算法性能受到極大影響.

另外,上述調度算法均假設任意網絡的虛擬機是全互連結構,同時也假設調度器與虛擬機之間及虛擬機之間是可以隨時獲取相關調度信息,而在實際應用中,在云計算復雜環境中這種假設是不成立的.文獻[11]的研究表明,考慮通信鏈路通信競爭的調度算法能有效提高算法的精度.文獻[9]在異構計算環境下的通信競爭模型,利用該模型證明了調度算法的有效性,但該模型是考慮任意網絡互連情況;文獻[10]在通信競爭模型下,使用最短路徑的搜索算法實現了任意互連網絡中虛擬機的查找問題及調度問題.

綜上,筆者提出一種面向科學工作流應用的動態多DAG分層調度算法(CCRH).該算法首先使用通信競爭模型描述虛擬機之間的通信競爭,使用主副版本技術提高調度算法的可靠性,針對多DAG使用公平因子的分層調度策略;仿真實驗表明了算法的有效性.

1 任務調度模型

典型的云計算科學工作流的應用,在不同時刻動態提交的任務用DAG來表示,進行形式化定義如下.

定義1 四元組G=(V,E,w,c),表示節點和邊的DAG圖,其中,V={v1,v2,v3,…,vN},表示任務集合,N表示任務數,任務之間具有的依賴關系用E={eij|vi,vj∈V}表示,w(vi)表示任務vi的計算代價,c(eij)表示任務vi和vj之間的通信代價.

定義2 集合{vx∈V:exi∈E}表示任務vi前驅節點集合,記為pred(vi).集合{vx∈V:eix∈E}表示任務vi后繼節點集合,記為succ(vi).如果pred(vi)=?,則任務節點vi是入口節點,記為ven try.如果succ(vi)=?,則任務節點vi是出口節點,記為vexit.

定義3 云計算的計算資源由于進行虛擬化,這里將虛擬化后異構的虛擬機集合描述為P={P1,P2…,PM},其中M表示虛擬機個數,調度到虛擬機Pk上的任務vi的主版本開始時間表示為tps(vi,pk),完成時間分別表示為tpf(vi,pk);任務vj副版本開始時間和完成時間分別表示為tBs(vj,pk),tBf(vj,pk),任務vi的主、副版本任務被調度的虛擬機表示為Pp(vi)和PB(vi).

定義4 云計算系統是任意互聯的網絡結構.虛擬機之間的網絡連接包括計算節點內部、同一機柜內部以及不同機柜,這里用lhk表示Ph與Pk之間的通信代價.

2 多DAG調度算法CCRH

2.1 任務優先級

單個DAG任務優先級使用靜態調度方法計算,受HEFT[12]算法啟發,假設任務vi和vj具有依賴關系,且vj的運行直接依賴于vi的運行結果.考慮計算與通信總體消耗的任務優先級表示為

云計算環境下的通信存在于處理機內、機柜內、機柜之間,因此必須將通信邊調度考慮進來,以此實現更加嚴謹的調度模型.文中使用文獻[11]提出的基于插入策略的最短路徑搜索算法,實現云計算環境下任意網絡互連異構計算系統的通信路徑查找.這里,定義LST(eij,l),LFT(eij,l)為eij在通信鏈路l的通信開始時間和完成時間,且LFT(eij,l)≥LST(eij,l)+c(eij).

2.2 主副版本任務調度

為了提高云計算系統的可靠性,文中使用主副版本的調度方法,即通過在備份虛擬機上執行冗余任務來實現容錯,同時保證任務的實時性.通過準確分析主、副版本任務的開始時間及滿足所調度的虛擬機(虛擬計算節點)的約束,在滿足系統可靠性的前提下,獲得較好的Makespan.

2.2.1 主版本任務調度

調度方法首先解決主版本任務調度,依據前驅節點集合pred(vj)中任務的副版本完成時間,任務vj的主版本的開始時間tps(vj,p)有以下3種狀態:

(1)任務vj的主版本的完成時間小于集合pred(vj)中任務的副版本最遲完成時間與通信鏈路完成時間的最大值.

(2)任務vj的主版本開始時間大于集合pred(vj)中的任務的副版本最遲完成時間與通信鏈路完成數據傳輸時間的最大值.

(3)任務vj的主版本開始時間介于pred(vj)中任務主、副兩個版本最遲完成時間與通信鏈路完成時間的最大值之間,且其完成時間在其最大副版本完成時間之后.

由以上3種情況可知,算法CCRH中不同DAG任務的主版本調度約束,在滿足其自身優先級任務約束的情況下,可以對其進行獨立調度,只需依據調度虛擬機隊列尋找最早開始的完成任務的虛擬機即可,其調度的虛擬機也沒有嚴格的限制.

2.2.2 副版本任務調度

下面分析任務vj的副版本任務執行的最早開始時間.首先定義副版本調度滿足的約束條件,當任務vj的主版本調度滿足狀態(2)或(3)時,它的副版本任務的開始時間必須滿足

當任務vj的主版本調度滿足狀態(1)時,副版本任務的最遲開始時間必須滿足

任務vj的主版本調度滿足狀態(2)時,它的副版本任務的所能調度虛擬機滿足

任務vj的主版本調度滿足狀態(1)或(3)時,pred(vj)2表示集合pred(vj)中滿足狀態(1)或(3)的任務集合,pd(vj)為vj所有任務中與vj存在間接與直接依賴關系滿足狀態(1)或(3)的任務集合.由于

云計算環境下科學工作流任務調度的一個重要目標是獲取任務的最早完成時間(Makespan).多DAG任務的最早完成時間可以用出口節點副版本的完成時間表示,CCRH尋求的副版本的最早開始時間,即完成了對整個任務調度策略的出口任務的副版本最早完成時間即可,即

2.3 多DAG分層調度

在云計算系統的多DAG調度模型中,由于一個DAG工作流a要與其他的DAG工作流爭用同一組計算資源,所以工作流a的Makespan(從提交DAG a開始到DAG a的最后一個任務執行完畢所用的時間)很可能比a單獨使用該云計算環境的Makespan要長,這兩個Makespan可分別被表示為Mmulti(a)和Mown(a),文獻[12]定義Slowdown描述這一比值:SSlowdown=Mmulti(a)Mown(a),因此某個調度算法S的不公平程度因子UUn faines(s)定義為

3 實驗結果與分析

仿真實驗將算法與HEFT[12]、BMCT[13]分別采用公平因子調度后的公平性、調度時長、虛擬機利用率、任務運行時間這4個方面性能進行比較(HEFT的多DAG任務采用與文獻[13]相同的分層方法).為了更好體現算法在科學工作流調度中的優勢,使用兩種類型的DAG任務:隨機DAG任務、快速傅里葉變換(Fast Fourier Transform,FFT),其中每種類型的DAG包括2～10個DAG任務,每個DAG包含10～50個任務.使用CCR描述DAG任務圖中通信與計算比率,CCR的值選擇0.1～1的隨機數.

實驗環境為Inter(R)Xeon E7420 2.13 GHz,RAM 4GB,硬盤1 TB的10臺服務器搭建具有30個虛擬計算平臺,為了模擬云計算平臺,在每個計算節點上使用虛擬化Xen創建了虛擬集群,以模擬數據中心的云計算環境,

3.1 公平性

算法的公平性能夠有效反應調度算法在處理多個DAG任務時,能夠公平的對待不同優先級以及不同時間提交的問題,實驗通過不同的科學工作流的DAG任務,對CCRH、HEFT、BMCT算法的公平性進行比較.圖1表示3種算法在隨機DAG任務、FFT下的DAG任務的公平性.由圖1可以看出,由于HEFT與BMCT采用相同的分層的方法,其公平性沒有太大的差異,而CCRH由于采用動態分層的方法,其公平性有了較大的提高,而且沒有出現較大的跳變現象.

3.2 算法Makespan

算法Makespan性能可以有效反應不同調度算法的調度時長,實驗通過不同的科學工作流的DAG任務,對CCRH、HEFT、BMCT算法的Makespan進行比較.圖2表示3種算法在隨機DAG任務、FFT圖中的Makespan.由圖2可以看出,3種算法的Makespan性能均在可接受的范圍之內.其主要原因是,3種算法選擇相似的優先級比較算法.BMCT優于HEFT的原因是BMCT考慮任務之間的通信約束,而CCRH由于采用主副版本技術,提高系統可靠性,但其副版本任務的執行增加了算法的Makespan.可以看到,在提高系統可靠性的前提下,系統增加的Makespan在可接受的范圍內.

圖1 算法公平性比較

圖2 算法平均Makespan比較

3.3 大規模數據運算時間

為了更好測試算法的在大規模數據運算時的Makespan性能,驗證主副版本技術在提高系統可靠性同時,對計算性能的犧牲.實驗分別對比3種算法在隨機產生的100個DAG圖任務的運行時間(Makespan)進行比較,由圖3可以看出,HEFT在3種算法在40個任務時,其Makespan基本相同,隨后BMCT表現出較差的Makespan,在DAG任務達到80時,CCRH的Makespan性能下降較為明顯,在100個DAG任務時調度算法獲得的Makespan為原來的2倍,其犧牲的系統運行時間在可接受范圍之內.

圖3 大規模數據運行時間比較　

圖4 資源利用率比較

3.4 資源利用率

為了更好體現算法對云環境資源的利用,考查不同的科學工作流負載中,虛擬計算節點的平均使用情況.從圖4中可以看出,CCRH擁有較高的虛擬機利用率,因而在資源使用計費的云環境中,CCRH擁有較好的效益,并且能提高系統的負載均衡性.

4 結束語

筆者針對云計算系統中科學工作流的可靠調度問題,通過使用主副版本技術,利用動態分層調度的方法,有效解決了多DAG調度的不公平性問題.仿真實驗表明,該算法在滿足可靠性要求的前提下,其公平性、Makespan、資源利用率、系統運行時間均表現出較好的性能.

參考文獻:

[1]WIECZOREK M,PRODAN R,FAHRINGER T.Scheduling of Scientific Workflows in the Askalon Grid Environment [J].SIGMOD Record,2005,3(34):56-62.

[2]MANDAL A.Scheduling Strategies for Mapping Application Workflows onto the Grid[C]//Proceedings of the 14th International Symposium on High Performance Distributed Computing.New York:ACM,2005:125-134.

[3]田國忠,肖創柏,徐竹勝,等.異構分布式環境下多DAG工作流的混合調度策略[J].軟件學報,2012,23(10):2720-2734.TIAN Guozhong,XIAO Chuangbai,XU Zhusheng,et al.Hybrid Scheduling Strategy for Multiple DAGs Workflow in Heterogeneous System[J].Journal of Sofware,2012,23(10):2720-2734.

[4]ZHAO H,SAKELLARIOU R.Scheduling Multiple DAGs onto Heterogeneous Systems[C]//Proceedings of the 20th International Parallel and Distributed Processing Symposium.Piscataway:IEEE,2006:1639387.

[5]ZHANG J,SHA E H M,ZHUGE Q,et al.Efficient Fault-tolerant Scheduling on Multiprocessor Systems via Replication and Deallocation[J].International Journal of Embedded Systems,2014,6(2/3):216-224.

[6]BARUAH S,BONIFACI V,MARCHETTI-SPACCAMELA A,et al.A Generalized Parallel Task Model for Recurrent Real-time Processes[C]//Proceedings of the 33th Real-time Systems Symposium.Piscataway:IEEE,2012:63-72.

[7]RAJU R,AMUDHAVEL J,PAVITHRA M,et al.A Heuristic Fault Tolerant Mapreduce Framework for Minimizing Makespan in Hybrid Cloud Environment[C]//Proceedings of the IEEE International Conference on Green Computing,Communication and Electrical Engineering.Piscataway:IEEE,2014:6922462.

[8]XIE G Q,LI R F,LIU L,et al.DAG Reliability Model and Fault-tolerant Algorithm for Heterogeneous Distributed Systems[J].Information Processing Letters,2009,109(11):539-542.

[9]QIN X,JIANG H.A Novel Fault-tolerant Scheduling Algorithm for Precedence Constrained Tasks in Real-time Heterogeneous Systems[J].Parallel Computing,2006,32(5):331-356.

[10]SINNEN O,SOUSA L A.Toward a Realistic Task Scheduling Model[J].IEEE Transactions on Parallel and Distributed Systems,2006,17(3):263-275.

[11]景維鵬,吳智博,劉宏偉,等.支持優先級約束任務的容錯調度算法[J].清華大學學報,2011,51(S1):1440-1444.JING WEIPENG,WU ZHIBO,LIU HONGWEI,et al.Fault-tolerant Scheduling Algorithm for Precedence Constrained Tasks[J].Tsinghua Science and Technology,2011,51(S1):1440-1444.

[12]MACEY B S,ZOMAYA A Y.A Performance Evaluation of CP List Scheduling Heuristics for Communication Intensive Task Graphs[C]//Proceedings of the International Parallel Processing Symposium.Los Alamitos:IEEE Computer Society,1998:538-541.

[13]TOPCUOGLU H,HARIRI S,WU M.Performance Effective and Low-complexity Task Scheduling for Heterogeneous Computing[J].IEEE Transactions on Parallel and Distributed Systems,2002,13(3):260-274.

[14]謝國琪,李仁發,楊帆,等.異構網絡化汽車電子系統中多DAG離線任務調度[J].通信學報,2013,34(12):20-32.XIE Guoqi,LI Renfa,YANG Fan,et al.Multiple DAG Off-line Task Scheduling for Heterogeneous Networked Automobile Electronic Systems[J].Journal on Communications,2013,34(12):20-32.

(編輯:王 瑞)

Multiple DAGs dynamic workflow reliability scheduling algorithm in a cloud computing system

JING Weipeng1,2,WU Zhibo1,LIU Hongwei1,SHU Yanjun1
(1.School of Computer Science and Technology,Harbin Institute of Technology,Harbin 150001,China; 2.The College of Information and Computer Engineering,Northeast Forestry Univ.,Harbin 150040,China)

Abstract:In order to solve the reliable scientific workflow scheduling problem for cloud computing,a dynamic of the RANK-Hierarchical algorithm is put forward which takes account of communication contention as well as supports task dependencies(CCRH).A communication contention model is first defined,as soon as the earliest completion of the primary and backup task is deduced.Besides,the executived processor is limited.We use the dynamic hierarchical method and calculate each DAG unfair degree factor for multiple DAGs scientific workflow.It can deal with the situation that multiple DAGs workflow comes at different times and there are various kinds of structure.Both the theory and experiments have proved that the algorithm can not only improve the scheduling fairness of multiple DAGs workflow but also shorten the average execution Makespan.

Key Words:cloud computing;multiple DAGs;reliability scheduling;degree factor

作者簡介:景維鵬(1979-),副教授,博士,E-mail:nefujwp@gmail.com.

基金項目:國家自然科學基金資助項目(61202091);國家863重大科技專項資助項目(2013AA01A215);哈爾濱市科技局科技創新人才基金資助項目(2014RFQXJ132)

收稿日期:2014-11-03 網絡出版時間:2015-05-21

doi:10.3969/j.issn.1001-2400.2016.02.015

中圖分類號:TP306

文獻標識碼:A

文章編號:1001-2400(2016)02-0083-06

網絡出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20150521.0902.012.html