云環境下科學工作流的調度算法①

馮復劍

(江蘇第二師范學院,南京 210013)

近年來隨著科學研究越來越依賴于海量數據集的分析和分布式資源的使用,科學工作流[1-3]得到了巨大的發展.通過管理分析的復雜性、在分布式資源上執行必要的計算、收集分析結果的信息以及記錄和再現科學分析等手段,科學工作流管理系統提供了一個輔助科學發現過程的環境,加速了科學進步的步伐.

商業云因其高彈性、專用軟硬件基礎設施和按需付費的成本模型等特性[4-6],已經成為進行大規模科學分析的支撐平臺.通過各種云服務,可以促進工作流的執行.其執行過程中,需要考慮一個或多個QoS 約束,常見的為時間-成本優化.工作流調度的時間-成本優化是一個難題,國內外學者已從不同方面展開了研究并取得了豐富的成果[7-15].一些綜述文章[16-18]對其進行了較完整的闡述,這里就不再一一回顧.為了簡潔起見,僅描述本文解決的問題.

現有的科學工作流調度算法多基于有向無環圖(Directed Acyclic Graph,DAG)建模,僅對工作流結構中的順序和“與”結構適用,并不支持“或”結構.這限制了算法的使用范圍和性能.文獻[12]提出,可以將“或”結構轉換成“與”結構進行處理.這是不合理的,違背了工作流語義.對于“或”結構中的支路每個流程實例只會選擇其中一條,而“與”結構的所有支路都是同時執行的,兩者是不可以直接轉換的.正因為未考慮“或”結構,現有的算法存在以下不足:

(1) 同一層活動分配相同的截止期限不合理

逆向分層調度算法[12](Deadline Bottom Level,DBL)以及基于此而改進的算法中,認為同一層的所有活動具有相同的截止期限.圖1為一個簡單的基于逆向分層的工作流實例,圖中活動節點的上方數字表示選擇最快執行服務所需要消耗的時間.活動1 完成后,根據輸出條件選擇執行支路{2,3,4}或者支路{5}.依據DBL 算法求得每個活動的時間區間如表1.活動5 的時間區間為[4,27],所以可選服務的耗時范圍為[7,23],假定其執行最慢的服務耗時23 個單位時間.基于滿足截止期限的前提下選擇最低成本的原則,工作流在實例執行過程中若選擇支路{5}將會調用執行時間最長的服務,因此將消耗掉額外16 個單位的時間.由此 帶來兩個問題:

圖1 一個簡單的工作流實例

表1 DBL 活動時間區間

① 活動5 本可以在時間點11 時刻即可結束,則活動6 將提前16 個單位時間開始,在不改變后續活動既定調度方案的情況下,將使得整個工作流提前16 個單位時間結束；

② 將額外消耗的16 個單位時間分配給后續未開始的活動,從而獲得更優的執行方案.

當這兩種情況下帶來的效益遠遠大于單個活動5 優化帶來的效益時,DBL 對截止期限的分配存在弊端.

(2) 松弛時間優化未同時考慮活動控制結構和服務效益

當給定的工作流截止期限大于算法計算得出的截止期限時,工作流存在松弛時間.為了提高效益,需要將這部分時間資源合理地分配給能夠帶來費用優化的活動.表2為圖1工作流實例中部分活動對應的候選服務列表.

表2 候選服務列表

假設現有2 個單位的工作流松弛時間,由于只有活動{5,6}有多個候選的服務,因此只需要對這兩個活動進行優化.根據文獻[13]提出的寬裕時間有效分配算法(Slack-time Effective Allocation,SEA),活動5,6 的鄰服務級差性價比分別為1 和0.5,因此將松弛時間全部分配給活動5.基于“或”結構的特性,若工作流實際執行過程中選擇活動5 所在的支路是小概率事件,此時分配的松弛時間將不會帶來費用優化,從而導致時間資源的浪費.

(3) 其它問題

文獻12 中定理2 認為BLmin≥LCT,其中:BLmin是按照逆向分組后求得的工作流最小完工時間,LCT為最小關鍵路徑法計算的完工時間.該定理不成立,因為BLmin和LCT均根據每個活動的最快服務求得,若BLmin＞LCT表示同一工作流在活動執行者相同的條件下通過兩種不同方法得到不同的完工時間,這是不合理的.

為了解決以上的不足,本文提出一種新的調度算法,充分考慮工作流控制結構中的順序、“與”和“或”結構,并分別從靜態調度和動態監控兩個階段對截止期限的分配進行討論.

1 模型和相關概念

1.1 工作流模型

定義1.工作流的DAG 模型是一個二元組 〈N,E〉,其中:N={1,2,3,4,···,n|n∈N?}表示所有的活動集；是活動之間的邏輯關系.

為了討論方便,下面給出一些變量的定義及其數學表達式:

(1)S(i):活動i的 候選服務集合,其大小為L(i).

(2)S(i)j:活動i的 第j個候選服務.

(3)T(i)j:S(i)j所需的處理時間和數據傳輸時間之和.

(4)C(i)j:S(i)j對應的服務費用和數據傳輸成本之和.

(5)D(i):活動i的截止期限.

(6)TS(i) :活動i的松弛時間,當選定S(i)j后有:D(i)=T(i)j+TS(i).

(7)pred(i)/succ(i):活動i的前驅/后繼.

為了排除網絡等其它客觀環境的影響,假設云服務供應商能夠提供無限數量的實例訪問,且不同存儲服務之間的帶寬基本相同.

1.2 關鍵活動優先級

為了敘述方便,下面給出一些符號的語義:

(1)CP:工作流的最長執行路徑,即關鍵路徑.

(2)CP(i) :活動i是關鍵活動.

(3)CPs(i)/CPand(i)/CPor(i):關鍵活動.i.處于順序支路/“與”支路/“或”支路,同步活動為關鍵活動,且在順序支路上.

定義2.關鍵活動優先級(Critical Activity Priority,CAP),反應活動時間-成本優化對整個流程性能提升的影響程度.優先級越高,表示活動的優化帶來的影響越大,反之越小.

關鍵活動按照其所處控制結構的不同,相應的優先級不同.下面分別對3 種拓撲結構進行闡述.

(1) “與”支路

“與”控制結構中的每條支路需要在同步活動處等待,當關鍵活動獲得額外的時間資源后,將延長所在支路的執行時間,進而影響整個控制塊中每條支路的運行.因此,“與”支路上單個關鍵活動的優化將會提升整個“與”控制結構的性能.

(2) 順序支路

順序支路上的關鍵活動,對其分配額外的時間資源只會優化該活動本身,并不會波及其它活動.

(3) “或”支路

由于“或”結構在實例運行之前無法確定選擇哪條支路,因此,對“或”支路上的關鍵活動分配額外的時間資源有可能無法帶來效益.

綜上所述,可以得到關鍵活動的優先級為:CAP(CPand(i))＞CAP(CPs(i))＞CAP(CPor(i)).

2 調度算法

本文按照如下步驟解決調度問題:

步驟1 尋找工作流的最小關鍵路徑.

步驟2 查詢可用時隙,根據每個任務的局部最優解生成最優調度計劃.

步驟3 實時監控流程實例的運行狀態.

接下來詳細陳述步驟2-3,關鍵路徑的尋找通過文獻[19]提出的方法實現.

2.1 松弛時間分配策略

定義3.服務效益比(Service Benefit Ratio,SBR),衡量服務替換所帶來效益的大小,其計算公式為:

式(1)中的m、n分別表示第m、n個候選服務.

對優先級相同的活動集合A,基于服務效益比的松弛時間分配算法(Slack Time Allocation Based on SBR,STABSBR)如下:

算法1.STABSBR 算法輸入:A ,?i∈A 具 有相同的活動優先級；松弛時間TS；輸出:{TS(i)}；Begin 1 計算 A 中每個活動i 的下一個候選服務(S (i)按照成本降序排列)與當前選擇服務的Δ C(i)m,n,Δ T(i)m,n,SBR(i)m,n；2 while(A ≠?)3 {4從 A 中去除所有Δ T(i)m,n＞TS 的活動,并按照SBR(i)m,n降序、ΔT(i)m,n 升序排列得到B ；5 if (B≠?)6 {7 TS(B(0))=ΔT(B(0)),TS=TS-TS(B(0))；8 將活動 B (0)移 出 A；9 }10 }End

該算法能夠將全局額外的時間資源合理的在活動之間進行分配,從而產生最優的調度方案.假設現有順序串聯的兩個活動1 和2,其候選服務集分別為S(1)={(T,C)}={(5,9),(8,8)},S(2)={(T,C)}={(6,10),(8,8)},且根據工作流執行時間下界求得其松弛時間為TS(WF)=3.從前面的分析可以知道,因此,給活動2 分配兩個單位的松弛時間,即選擇第2 個候選服務作為執行服務.剩余的1 個單位時間資源由于無法提供給活動1 以滿足其最低的時間增量,將不再繼續優化.

2.2 靜態調度

靜態調度需要考慮活動的拓撲結構,由關鍵活動優先級可知對于順序和“或”結構松弛時間的再分配只影響單個活動,而“與”結構會影響到整個控制塊.因此,需 要對“與”結構進行單獨說明.

圖2 “與”控制結構

以圖2所示的“與”控制結構為例,branch(1),branch(2)...branch(i)分別表示每條支路,假設branch(i)是子關鍵路徑.現根據松弛時間分配策略為某個關鍵活動m分 配了 ΔT的松弛時間,則可求得“與”控制塊新的截止期限為(D(branch(i))+ΔT),因此其他非關鍵路徑支路獲得的松弛時間為(D(branch(i))+ΔT-D(branch(n))),1 ≤n≤i-1.此時,可在每條支路內部按照松弛時間分配策略再對調度進行調整.

考慮工作流控制結構的靜態調度算法(Static Scheduling Considering Workflow Control Structure,SSCWCS)如下:

算法2.SSCWCS 算法輸入:〈 N,E〉,D (WF)；輸出:D (i)；Begin 1 為每個活動選擇執行最快的服務,以此求得工作流的關鍵路徑CP,并計算其執行時間下界D (CP)min；2 if (D (WF)＜D(CP)min )3 {4 提醒管理者需要修改 D (WF)；5 }6 else if(D (WF)＞D(CP)min)7 {8 計算工作流的松弛時間TS=D(WF)-D(CP)min；

9 將關鍵活動按照拓撲結構分類,分別求得；for(i=0;i＜4;i++)B=[{CPand(i)},{CPs(i)},{CPor(i)},{N-({CPand(i)}∪{CPs(i)}∪{CPor(i)})}]10 11 {12 將 分別代入算法1 進行優化；13 }B(0)≠?A=B(i),TS 14 if ()15 {16 計算“與”關鍵支路新的截止期限 D (branch(CPand))′并將其作為整個控制塊新的截止期限；for(i=0;i＜length(and);i++)17 18 {19 if ()20 {21 TS(branch(i))=D(branch(CPand))′-D(branch(i)),按照算法1 對該支路進行調優；22 }23 }24 }25 }Endbranch(i)≠branch(CPand)

2.3 動態監控

由于“或”結構在流程定義階段無法確定實際運行過程中所選擇的支路,因此靜態調度并未對非關鍵路徑支路和關鍵路徑支路設置相同的截止期限.這就需要在執行過程中,為“或”結構設置監測點,根據選擇的支路動態的為后續未執行的活動重新生成調度方案.

通過為每個“或”分支活動設置監測點,進而監聽該活動的結束事件,并根據輸出條件判斷后續所選擇的支路.若選擇的是關鍵路徑支路,則不更改現有的調度方案,否則對其進行優化.“或”結構動態監控優化算法(OR Dynamic Monitoring,ORDM)如下.

算法3.ORDM 算法輸入:〈 N,E〉,D (WF)；輸出:D (i)；Begin 1 找出所有的“或”控制結構,并設置“或”分支活動 ior_split為監測點；2 監聽ior_split 的 結束事件,記錄其完成時間TF(ior_split),并根據輸出條件判定后續選擇的支路branch；3 if (branch=branch(CP))4 {5 按照靜態調度方案對活動進行調度；6 }7 else 8 {9 根據當前的調度方案求得未完成活動的關鍵路徑CP′及其需要消耗的時間D (CP′)；

10 D (WF)′=D(WF)-TF(ior_split)；11 分別將CP=CP′,D (CP)min=D(CP′),D (WF)=D(WF)′代入算法2,對未完成的活動進行調優；12 }End

算法3 動態監控“或”結構的執行情況,規避了為所有“或”分支分配相同截止期限而造成效益無法最大化的情況的出現.本文提出的動態監控思路同樣適合于流程執行過程中出現的簡單異常,如服務的延遲、異常導致服務不可用.此時,可以把異常節點至結束活動的拓撲當作是新的工作流,并按照算法3 中步驟8-12 重新調度.其它復雜的異常處理將是下一步研究的對象.

3 實例

本章對前文提出的調度方法進行實例應用.圖3是虛擬科學分析過程的DAG 模型,表3是模型中每個活動對應的候選服務集合,時間單位為分鐘(min),費用單位為人民幣(￥).設定工作流的開始時間為0,截止期限為110.

圖3 工作流DAG 模型

表3 活動候選服務集合

3.1 關鍵路徑時間下界

每個活動選擇耗時最短的服務的條件下,按照如下步驟求得關鍵路徑執行時間的下界.

(1) “與”結構

T(3,4)min=T(3)min+T(4)min=6+10=16,T(5)min=12,T(3,4)min＞T(5)min,因此關鍵路徑為活動3,4.

(2) “或”結構

T(8)min=5,T(9)min=15,T(9)min＞T(8)min,所以關鍵支路為活動9.

順序活動處于關鍵路徑上,因此整個工作流的關鍵路徑由活動1,2,3,4,6,7,9,10,11 組成,其執行時間下界為D(CP)min=T(1)min+T(2)min+T(3,4)min+T(6)min+T(7)min+T(9)min+T(10)min+T(11)min=94.

3.2 松弛時間分配

工作流的松弛時間TS(WF)=D(WF)-D(CP)min=110-94=16.將關鍵活動按照所處的控制結構分類得到 {CPand(i)}={3,4},{CPs(i)}={1,2,6,7,10,11},{CPor(i)}={9}.根據算法2 分配松弛時間.

(1) “與”關鍵活動

活動3 只有一個候選服務,已經是最優方案；活動4 的 ΔT=5 ＜16,所以其可以獲得5 個單位的額外時間,此時工作流的剩余松弛時間TS(WF)=16-5=11.

(2) 順序關鍵活動

同步活動6,7 只有單個候選服務,所以{ΔT}={ΔT(1),ΔT(2),ΔT(10),ΔT(11)}={2,2,4,8},{S BR}={0.5,0.5,0.5,1}.因此活動11 將優先獲得8 個單位的時間資源,此時工作流剩余的松弛時間為3 個單位.活動1,2 的服務替換產生相同的效益,因此給活動1 分配2 個單位時間.

經過上述的步驟,工作流剩余1 個單位的松弛時間,無法滿足其它活動更換服務所需的最小時間變量,且又因為調整過后的“與”控制結構中活動5 沒有可替換的服務,調優結束.工作流優化過后的調度方案如表4所示.

表4 活動執行服務

3.3 動態監控

活動7 處設置監測點,TF(7)=T(1,2,3,4,6,7)=75,根據其輸出條件判斷活動8 所在的支路被選中,此時活動8,10,11 組成了新的工作流WF′.其松弛時間TS=D(WF)-TF(7)-T(8,10,11)=110-75-24=11,ΔT(8)=2,ΔT(10)=4,易知活動8,10 均可分得對應的額外時間資源,即選擇成本最低的服務.

4 結束語

為了更好地解決云環境下科學工作流調度過程中的時間-成本優化問題,在DAG 模型中增加了對工作流“或”控制結構的支持,并提出了關鍵活動優先級的概念,此舉彌補了現有基于DAG 的調度算法無法支持“或”結構的不足；同時,給出了活動的松弛時間分配策略,并基于此提出了云環境下科學工作流的調度算法,該方法由靜態調度和動態監控組成.最后通過虛擬的科學分析過程對上述的算法進行了說明和應用.