基于任務(wù)分配和數(shù)據(jù)集副本的科學(xué)工作流數(shù)據(jù)布局

尚 蕾,劉茜萍

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院 江蘇省大數(shù)據(jù)安全與智能處理重點(diǎn)實(shí)驗(yàn)室,南京 210023)

0 概述

工作流是對(duì)工作流程及其各操作步驟之間業(yè)務(wù)規(guī)則的抽象、概括與描述[1]。近年來(lái),隨著信息技術(shù)不斷發(fā)展,天文學(xué)[2]、高能物理學(xué)[3-4]以及生物信息學(xué)[5]等研究領(lǐng)域需要處理的數(shù)據(jù)量呈爆炸式增長(zhǎng),科學(xué)工作流(Scientific Workflow,SW)應(yīng)運(yùn)而生。科學(xué)工作流是一種面向海量密集型數(shù)據(jù)流、以減少計(jì)算成本為目標(biāo)的應(yīng)用系統(tǒng),可提升科學(xué)實(shí)驗(yàn)過(guò)程的自動(dòng)化程度,降低資源消耗。但科學(xué)工作流任務(wù)的數(shù)據(jù)量較為龐大,執(zhí)行費(fèi)用高,常規(guī)計(jì)算平臺(tái)環(huán)境難以滿足其需求。而云計(jì)算采用按需使用付費(fèi)模式,使用戶(hù)能以更低廉的價(jià)格獲取計(jì)算資源和存儲(chǔ)資源,并提供互聯(lián)網(wǎng)模式使研究者更方便地進(jìn)行資源分享和任務(wù)合作,為科學(xué)工作流的高效運(yùn)行提供了較為理想的平臺(tái)環(huán)境。

然而,云環(huán)境下科學(xué)工作流的運(yùn)行面臨諸多挑戰(zhàn)[6],最主要的問(wèn)題之一是數(shù)據(jù)布局。科學(xué)工作流數(shù)據(jù)布局本質(zhì)上是一種帶有最大完成時(shí)間[7]和費(fèi)用[8]等約束條件的NP難問(wèn)題。首先,云數(shù)據(jù)中心分布在世界各地,例如亞馬遜EC2云服務(wù)在美國(guó)、日本等地?fù)碛?0多個(gè)數(shù)據(jù)中心,導(dǎo)致科學(xué)工作流運(yùn)行時(shí)需要跨數(shù)據(jù)中心進(jìn)行數(shù)據(jù)存儲(chǔ)與傳輸,增加了數(shù)據(jù)傳輸費(fèi)用。此外,若數(shù)據(jù)集中存儲(chǔ)在一個(gè)云數(shù)據(jù)中心,將導(dǎo)致此中心的存取、復(fù)制、備份與分析工作量過(guò)大,影響工作流執(zhí)行的整體效率[9-10],因此需要在數(shù)據(jù)中心實(shí)現(xiàn)負(fù)載均衡。對(duì)此,已有研究者提出了多種數(shù)據(jù)布局解決方案。文獻(xiàn)[11]提出一種根據(jù)K均值算法對(duì)數(shù)據(jù)集依賴(lài)矩陣進(jìn)行劃分的數(shù)據(jù)布局方法。文獻(xiàn)[12]提出一種基于遺傳算法的3階段數(shù)據(jù)布局方法。文獻(xiàn)[13]提出一種基于粒子群算法的工作流數(shù)據(jù)布局方法,將依賴(lài)度高的數(shù)據(jù)集盡量放在同一數(shù)據(jù)中心。文獻(xiàn)[14]提出一種BDAP方法。文獻(xiàn)[15]提出一種兩階段數(shù)據(jù)放置方法,初始階段對(duì)數(shù)據(jù)集進(jìn)行聚類(lèi)分配,中間階段重新動(dòng)態(tài)分配數(shù)據(jù)集。文獻(xiàn)[16]提出一種云環(huán)境下基于整數(shù)線性編程模型的數(shù)據(jù)放置算法。文獻(xiàn)[17]提出一種基于圖區(qū)分的數(shù)據(jù)布局方法,減少了跨數(shù)據(jù)中心數(shù)據(jù)傳輸費(fèi)用。文獻(xiàn)[18]提出一種基于遺傳算法算子的自適應(yīng)離散粒子群優(yōu)化算法。文獻(xiàn)[19]提出一種多目標(biāo)優(yōu)化的數(shù)據(jù)布局策略,先對(duì)固定數(shù)據(jù)集布局,再對(duì)非固定數(shù)據(jù)集進(jìn)行分配。文獻(xiàn)[20]提出一種基于粒子群算法的工作流層的數(shù)據(jù)布局方法。但在以上方法中,文獻(xiàn)[11-13]并未考慮任務(wù)分配的不同結(jié)果對(duì)數(shù)據(jù)傳輸費(fèi)用產(chǎn)生的影響,文獻(xiàn)[14,20]考慮了數(shù)據(jù)集副本問(wèn)題,但并不是針對(duì)減少整體數(shù)據(jù)傳輸費(fèi)用,不能從本質(zhì)上解決整體數(shù)據(jù)傳輸費(fèi)用問(wèn)題,文獻(xiàn)[18]未考慮科學(xué)工作流數(shù)據(jù)階段布局問(wèn)題。

本文提出基于任務(wù)布局和數(shù)據(jù)集副本建立的云環(huán)境下兩階段科學(xué)工作流數(shù)據(jù)布局方案。該方案以減少數(shù)據(jù)傳輸費(fèi)用為主要目標(biāo),同時(shí)盡可能地兼顧數(shù)據(jù)中心負(fù)載均衡。

1 問(wèn)題描述

科學(xué)工作流是一種數(shù)據(jù)密集型應(yīng)用程序,任務(wù)和數(shù)據(jù)集之間是多對(duì)多的關(guān)系,任務(wù)和任務(wù)之間存在著非常強(qiáng)的依賴(lài)關(guān)系。此外,任務(wù)和任務(wù)之間還有著時(shí)序上的先后關(guān)系,只有當(dāng)一個(gè)任務(wù)的前驅(qū)任務(wù)全部執(zhí)行完畢時(shí),該任務(wù)才能執(zhí)行。

定義1(科學(xué)工作流) 科學(xué)工作流(SW)可以定義為三元組,其中:T={t1,t2,…,tn}表示SW的所有任務(wù)的集合;C=[cij]n×n表示任務(wù)之間控制流的鄰接矩陣,如果cij=1,則表示任務(wù)tj必須在任務(wù)ti執(zhí)行結(jié)束之后才可以執(zhí)行;DS={d1,d2,…,dm}表示SW中所有數(shù)據(jù)集的集合。

定義2(任務(wù)ti)ti定義為四元組,ti∈T,其中:ID表示任務(wù)需要的輸入數(shù)據(jù)集合,ID?DS;OD表示任務(wù)產(chǎn)生的輸出數(shù)據(jù)集的集合,OD?DS;ext表示任務(wù)執(zhí)行需要耗費(fèi)的時(shí)間;FT表示任務(wù)tj的前驅(qū)任務(wù)集合,即對(duì)于集合FT中的每一個(gè)任務(wù)ti,cij=1。

定義3(數(shù)據(jù)中心) 數(shù)據(jù)中心集合定義為DC,單個(gè)數(shù)據(jù)中心dcv定義為二元組,dcv∈DC,v=1,2,…,l,其中:size表示數(shù)據(jù)中心總存儲(chǔ)容量;aS表示數(shù)據(jù)中心當(dāng)前的可用容量。

科學(xué)工作流數(shù)據(jù)中的數(shù)據(jù)集擁有多重屬性,可以根據(jù)數(shù)據(jù)集放置位置是否固定分為固定數(shù)據(jù)集和靈活數(shù)據(jù)集;也可以根據(jù)數(shù)據(jù)集是否被至少兩個(gè)任務(wù)使用,分為共享數(shù)據(jù)集和非共享數(shù)據(jù)集。本文數(shù)據(jù)集產(chǎn)生后不會(huì)被修改,可以直接進(jìn)行使用,下文是關(guān)于科學(xué)工作流中數(shù)據(jù)集相關(guān)概念的定義。

定義4(數(shù)據(jù)集) 數(shù)據(jù)集dp定義為四元組,dp∈DS,p=1,2,…,m,其中:ds表示數(shù)據(jù)集dp的大小;preT表示數(shù)據(jù)集dp的前驅(qū)任務(wù),即生成數(shù)據(jù)集dp的任務(wù),preT?T;sucT表示數(shù)據(jù)集dp的后繼任務(wù)集合,包含了需要使用數(shù)據(jù)集dp的所有任務(wù);fix表明此數(shù)據(jù)集是否為固定數(shù)據(jù)集,取值為整數(shù)。當(dāng)fix=0時(shí),表明該數(shù)據(jù)集的位置是靈活的,反之,該數(shù)據(jù)集的位置是固定的fix對(duì)應(yīng)的數(shù)值,即該固定數(shù)據(jù)集所應(yīng)當(dāng)在數(shù)據(jù)中心的編號(hào)。當(dāng)preT=null時(shí),表示該數(shù)據(jù)集為初始數(shù)據(jù)集,大小已經(jīng)確定,所有preT=null的數(shù)據(jù)集集合表示為DSinit,反之為生成數(shù)據(jù)集,大小未確定,但是可以進(jìn)行預(yù)估,所有preT≠null的數(shù)據(jù)集集合表示為DSgen,DSinit∩DSgen=?,DSinit∪DSgen=DS;當(dāng)sucT=null時(shí),表示該數(shù)據(jù)集為最終結(jié)果,若|dp.sucT|≥2,則dp為共享數(shù)據(jù)集,否則為非共享數(shù)據(jù)集。考慮到存在著某些任務(wù)需要使用或者生成固定數(shù)據(jù)集的情況,本文進(jìn)一步定義了固定任務(wù)和靈活任務(wù),當(dāng)dp.fix≠0時(shí),dp.preT與dp.sucT中的任務(wù)均為固定任務(wù),固定任務(wù)集用Tfix表示,T中的非固定任務(wù)即為靈活任務(wù),其集合用Tflex表示,Tfix∩Tflex=?,Tfix∪Tflex=T。

在科學(xué)工作流中,任務(wù)與數(shù)據(jù)集緊密相關(guān),一個(gè)任務(wù)可以與多個(gè)數(shù)據(jù)集相關(guān),一個(gè)數(shù)據(jù)集也可以與多個(gè)任務(wù)相關(guān)。研究數(shù)據(jù)布局問(wèn)題可以從任務(wù)布局著手,研究任務(wù)與數(shù)據(jù)集之間的關(guān)系來(lái)優(yōu)化解決數(shù)據(jù)布局的相關(guān)問(wèn)題。本文采用數(shù)據(jù)費(fèi)用開(kāi)銷(xiāo)來(lái)衡量數(shù)據(jù)布局結(jié)果的好壞,表示為Cost;數(shù)據(jù)費(fèi)用開(kāi)銷(xiāo)包括數(shù)據(jù)傳輸和數(shù)據(jù)集存儲(chǔ)兩部分費(fèi)用開(kāi)銷(xiāo)。數(shù)據(jù)傳輸費(fèi)用表示為DTCost(dp),其值為數(shù)據(jù)集大小與傳輸單價(jià)的乘積;數(shù)據(jù)集存儲(chǔ)費(fèi)用表示為DSCost(dp),其值為該數(shù)據(jù)集的存儲(chǔ)時(shí)間與存儲(chǔ)單價(jià)的乘積,數(shù)據(jù)費(fèi)用開(kāi)銷(xiāo)越小,則說(shuō)明該布局方案結(jié)果越好。此外,考慮到科學(xué)工作流中經(jīng)常涉及同一個(gè)數(shù)據(jù)集需要在多個(gè)數(shù)據(jù)中心之間傳輸,可以設(shè)置數(shù)據(jù)集副本,通過(guò)增加數(shù)據(jù)集副本的存儲(chǔ)費(fèi)用來(lái)減少整體傳輸?shù)馁M(fèi)用消耗,而本文以增加數(shù)據(jù)集存儲(chǔ)費(fèi)用來(lái)減少數(shù)據(jù)集傳輸費(fèi)用以達(dá)到降低總費(fèi)用的效果,因此,本文數(shù)據(jù)集存儲(chǔ)費(fèi)用開(kāi)銷(xiāo)指數(shù)據(jù)集副本存儲(chǔ)開(kāi)銷(xiāo)。下文依次給出任務(wù)布局、數(shù)據(jù)集副本和數(shù)據(jù)布局的相關(guān)定義。

定義5(任務(wù)布局方案) 工作流的一個(gè)任務(wù)布局(Task Layout,TL)方案是從任務(wù)集合T到數(shù)據(jù)中心集合DC的一個(gè)映射,對(duì)于?ti∈T,?dcv∈DC與之對(duì)應(yīng),i=1,2,…,n，v=1,2,…,l,表示為:

TL=∪i=1,2,…,n{ti→dcv}

即TL(ti)為任務(wù)布局方案TL中任務(wù)ti所對(duì)應(yīng)的數(shù)據(jù)中心。

定義6(數(shù)據(jù)集副本rq)rq定義為二元組,全體rq的集合定義為R,即rq∈R,其中:dr表示對(duì)應(yīng)正本數(shù)據(jù)集dp的編號(hào),取值為[1,m];rsucT表示副本rq對(duì)應(yīng)的后繼任務(wù)集合,該集合為dp后繼任務(wù)集合的真子集,即rsucT?dp.sucT。 例如若有副本數(shù)據(jù)集r1=<1,{t3}>,則說(shuō)明其為正本數(shù)據(jù)集d1=<5,{t1},{t2,t3},0>的副本,且d1.sucT={t2,t3},r1.rsucT={t3}。

定義7(數(shù)據(jù)布局方案) 工作流的一個(gè)數(shù)據(jù)布局(Data Layout,DL)方案是從數(shù)據(jù)集集合DS和數(shù)據(jù)集副本集合R到數(shù)據(jù)中心集合DC的一個(gè)映射,對(duì)于?dp∈DS,?dcv,dcu∈DC與之對(duì)應(yīng),p,q=1,2,…,m,v=1,2,…,l,表示為:

即DL(dp)為數(shù)據(jù)布局方案DL中數(shù)據(jù)集dp所對(duì)應(yīng)的數(shù)據(jù)中心,DL(rq)為數(shù)據(jù)布局方案DL中副本集rq所對(duì)應(yīng)的數(shù)據(jù)中心。本文云環(huán)境下科學(xué)工作流的數(shù)據(jù)布局由運(yùn)行前所得布局方案DLinit和運(yùn)行中布局方案DLgen兩部分組成。

2 任務(wù)分配

給定一個(gè)涉及n個(gè)任務(wù)和m個(gè)數(shù)據(jù)集的科學(xué)工作流,以及可存放數(shù)據(jù)集和執(zhí)行任務(wù)的l個(gè)數(shù)據(jù)中心,本文在實(shí)現(xiàn)任務(wù)分配的基礎(chǔ)上解決云環(huán)境下科學(xué)工作流的數(shù)據(jù)布局問(wèn)題。科學(xué)工作流中數(shù)據(jù)集與任務(wù)之間存在著密不可分的依賴(lài)關(guān)系,而這些關(guān)系在工作流設(shè)計(jì)之初便已經(jīng)存在,基于此,本文將任務(wù)分配納入數(shù)據(jù)集布局方法考慮中。本文中任務(wù)的分配基于數(shù)據(jù)集與任務(wù)的依賴(lài)關(guān)系,即依據(jù)這些依賴(lài)關(guān)系再進(jìn)行任務(wù)之間依賴(lài)度的定量計(jì)算,根據(jù)計(jì)算結(jié)果得到相應(yīng)的任務(wù)分配結(jié)果。

2.1 任務(wù)依賴(lài)矩陣

本文提出的任務(wù)依賴(lài)度為任務(wù)之間相關(guān)數(shù)據(jù)集大小之和而不是相關(guān)數(shù)據(jù)集個(gè)數(shù),簡(jiǎn)單工作流示例如圖1所示。

圖1 簡(jiǎn)單工作流示例

在圖1中,t1的輸入數(shù)據(jù)集為{d1,d2},輸出數(shù)據(jù)集為{d3},t2的輸入數(shù)據(jù)集為{d2,d3,d5,d6},輸出數(shù)據(jù)集為{d4},t3的輸入數(shù)據(jù)集為{d4,d5,d6},輸出數(shù)據(jù)集為{d7},各數(shù)據(jù)集大小如表1所示。

表1 數(shù)據(jù)集大小

此時(shí),t1與t2之間相關(guān)數(shù)據(jù)集個(gè)數(shù)為2,t2與t3之間相關(guān)數(shù)據(jù)集個(gè)數(shù)為3,若按相關(guān)數(shù)據(jù)集個(gè)數(shù)來(lái)計(jì)算,那么t2與t3之間存在著最高的依賴(lài)度,若將t2與t3分配至同一個(gè)數(shù)據(jù)中心dc1,t1位于另一個(gè)數(shù)據(jù)中心dc2,則此時(shí)需要從dc2傳輸數(shù)據(jù)集d2與數(shù)據(jù)集d3至dc1,傳輸?shù)臄?shù)據(jù)總量為11 GB。而若是按照兩個(gè)任務(wù)之間相關(guān)數(shù)據(jù)集的大小之和定義其依賴(lài)度,則t2應(yīng)與t1具有最高的依賴(lài)度,應(yīng)將t1與t2分配至同一個(gè)數(shù)據(jù)中心dc1,t3位于另一個(gè)數(shù)據(jù)中心dc2,此時(shí)需要從dc1傳輸數(shù)據(jù)集d4、d5和d6至dc2,傳輸?shù)臄?shù)據(jù)總量為3 GB。為盡可能降低這種影響,本文提出任務(wù)依賴(lài)度的定量計(jì)算方法,任務(wù)之間的依賴(lài)度為任務(wù)之間共同關(guān)聯(lián)數(shù)據(jù)集的大小之和,下文給出本文中任務(wù)依賴(lài)度的定義。

定義8(任務(wù)依賴(lài)矩陣) 任務(wù)依賴(lài)矩陣(Task Dependency Matrix,TDM)表示所有任務(wù)之間的依賴(lài)度,本文將任務(wù)與任務(wù)自身的依賴(lài)度設(shè)置為0,即任務(wù)依賴(lài)矩陣是一個(gè)n×n的對(duì)角線為0的對(duì)稱(chēng)矩陣,n是任務(wù)的個(gè)數(shù),tdmij是ti和tj之間的任務(wù)依賴(lài)度,表示為:

(1)

CD=(ti.ID∪tj.OD)∩(tj.ID∪tj.OD),

i,j=1,2,…,n,i≠j

其中,ti.ID表示任務(wù)ti的輸入數(shù)據(jù)集集合,ti.OD表示任務(wù)ti的輸出數(shù)據(jù)集集合,ti.ID∪tj.OD表示與任務(wù)ti相關(guān)的數(shù)據(jù)集集合,CD表示同時(shí)與任務(wù)ti和tj相關(guān)數(shù)據(jù)集集合。

2.2 基于定量計(jì)算任務(wù)依賴(lài)度的任務(wù)布局方法

本文任務(wù)布局的目的在于將所有任務(wù)分配至適合的數(shù)據(jù)中心,為之后的數(shù)據(jù)集分配奠定基礎(chǔ)。本文按照任務(wù)起始時(shí)間對(duì)n個(gè)任務(wù)進(jìn)行排序,分為固定任務(wù)分配、起止時(shí)間計(jì)算、任務(wù)依賴(lài)度計(jì)算、非固定任務(wù)分配4個(gè)步驟(本文中研究的科學(xué)工作流只有唯一的一個(gè)起始任務(wù),并假設(shè)為t1):

步驟1將固定任務(wù)分配至相應(yīng)數(shù)據(jù)中心

輸入數(shù)據(jù)集DS,數(shù)據(jù)中心DC,任務(wù)集T

輸出靈活數(shù)據(jù)集Tfix,當(dāng)前任務(wù)布局TL

1.for each dpin DS:

2.if dp.fix != 0:

3.allocate(dp.preT∪dp.sucT)to dcfix

4.update TL

5.Tfix←Tfix+(dp.preT∪dp.sucT)

該方法主要是分配固定任務(wù),時(shí)間復(fù)雜度為O(m),固定任務(wù)被定義為與固定數(shù)據(jù)集相關(guān)的任務(wù),即固定數(shù)據(jù)集的前驅(qū)任務(wù)和后繼任務(wù)均為固定任務(wù),考慮到固定數(shù)據(jù)集無(wú)法移動(dòng),與之相關(guān)的任務(wù)都需要在其所在數(shù)據(jù)中心執(zhí)行。科學(xué)工作流任務(wù)執(zhí)行的前提是所有的輸入數(shù)據(jù)集都傳輸?shù)酵粋€(gè)數(shù)據(jù)中心,而固定數(shù)據(jù)集不可移動(dòng),故本文中不考慮同一個(gè)任務(wù)需要使用位于不同數(shù)據(jù)中心的多個(gè)數(shù)據(jù)集的情況。

步驟2根據(jù)式(2)計(jì)算各個(gè)任務(wù)的起止時(shí)間

輸入任務(wù)集T

輸出任務(wù)的起止時(shí)間ti.st和ti.et

1.for each tiin T

2.ti.st←0

3.if i=1:

4.ti.et←ti.ext

5.else:

6.for each tjin ti.FT

7.if ti.st

8.ti.st←tj.et

9.ti.et←ti.st+ti.ext//calculate the starting time and //ending time of tasks

該方法主要是計(jì)算任務(wù)起止時(shí)間,時(shí)間復(fù)雜度為O(n2)。一個(gè)任務(wù)的開(kāi)始時(shí)間取決于其前驅(qū)任務(wù)的最晚執(zhí)行時(shí)間,而結(jié)束時(shí)間為開(kāi)始時(shí)間與執(zhí)行時(shí)間之和,因此起止時(shí)間可由下式計(jì)算得出(t1為初始任務(wù)):

(2)

ti.et=ti.st+ti.ext,i=1,2,…,n

其中,ti.st表示任務(wù)ti的開(kāi)始時(shí)間,tj.et表示任務(wù)tj的結(jié)束時(shí)間,ti.FT表示任務(wù)ti的前驅(qū)任務(wù)集合。

步驟3計(jì)算任務(wù)依賴(lài)度

輸入數(shù)據(jù)集DS,任務(wù)集T,數(shù)據(jù)中心DC

輸出任務(wù)依賴(lài)矩陣TDM

1.for each tito n in T:

2.for j to i:

3.tdmij=0

4.while(ti!=tj):

5.CD=(ti.ID∪ti.OD)∩(tj.ID∪tj.OD)

6.if CD !=?:

7.for each dpin CD:

8.tdmij=tdmji=dp.ds+tdmij//build TDM

該方法主要計(jì)算任務(wù)之間的依賴(lài)度,算法時(shí)間復(fù)雜度為O(n3),主要依據(jù)2.1節(jié)中的任務(wù)依賴(lài)度的計(jì)算式(1)。每?jī)蓚€(gè)任務(wù)都會(huì)有一個(gè)共同數(shù)據(jù)集集合,集合中數(shù)據(jù)集大小之和即為兩個(gè)任務(wù)之間的依賴(lài)度,依賴(lài)度數(shù)值越大,兩個(gè)任務(wù)關(guān)系更為緊密。

步驟4分配非固定任務(wù)

輸入靈活任務(wù)集Tfix,數(shù)據(jù)中心DC

輸出任務(wù)布局方案TL

1.sort tiin Tfix according to ti.st//sort the tasks by //starting time

2.Tflex←T-Tfix

3.while Tflex:

4.aven←|Tflex|/|DC|

5.for each tiin Tfix:

6.S←{ti}

7.Denp←0

8.while |S-ti|

9.for each tjin Tflex:

10.for each tkin S:

11.Denp←denp+tdmjk

12.find the max denp

13.add tjinto S

14.allocate tjto ti.dc

15.update TL

16.delete tjin S from Tflex//allocate flexiable tasks

17.return TL

該方法主要是利用已經(jīng)分配完成的固定任務(wù),完成非固定任務(wù)的分配,該算法時(shí)間復(fù)雜度為O(n3)。基于非固定任務(wù)可以分配在任何一個(gè)數(shù)據(jù)中心,然而分配在不同的數(shù)據(jù)中心上會(huì)導(dǎo)致后續(xù)數(shù)據(jù)集傳輸量存在不一樣的結(jié)果的考慮,本文從非固定任務(wù)與固定任務(wù)的關(guān)系尋找突破口,首先將固定任務(wù)按照起始時(shí)間排序;接著將最早開(kāi)始的固定任務(wù)所在的數(shù)據(jù)中心上的所有固定任務(wù)一起加入空集S中,依次計(jì)算該集合中任務(wù)與非固定任務(wù)之間的任務(wù)依賴(lài)度,尋找依賴(lài)度最高的非固定任務(wù)加入集合S,繼續(xù)尋找與集合S中任務(wù)依賴(lài)度之和最高的任務(wù),加入集合S,直到集合S里任務(wù)數(shù)量等于每個(gè)數(shù)據(jù)中心上的平均任務(wù)數(shù)量為止,然后刪除非固定任務(wù)集Tflex中對(duì)應(yīng)的已經(jīng)分配完畢的非固定任務(wù),如果非固定任務(wù)集合Tflex不為空集,則重復(fù)該階段之前所有操作,直到任務(wù)完全分配結(jié)束。

3 數(shù)據(jù)布局

在完成任務(wù)分配后,需要根據(jù)任務(wù)分配的結(jié)果,將工作流中涉及的m個(gè)數(shù)據(jù)集合理布局至l個(gè)數(shù)據(jù)中心。考慮到有些數(shù)據(jù)集需要被多個(gè)任務(wù)所使用,若這些任務(wù)分散在各個(gè)數(shù)據(jù)中心,則不可避免地需要將數(shù)據(jù)集進(jìn)行多次傳輸,這無(wú)疑會(huì)增加數(shù)據(jù)集的傳輸總量,導(dǎo)致數(shù)據(jù)傳輸費(fèi)用的上升,對(duì)于需要多次傳輸?shù)臄?shù)據(jù)集,本節(jié)將在相應(yīng)的數(shù)據(jù)中心上建立數(shù)據(jù)集副本以達(dá)到降低數(shù)據(jù)傳輸量的目的。此外,考慮到有些數(shù)據(jù)集是工作流運(yùn)行之前便已經(jīng)存在,有些數(shù)據(jù)集是工作流運(yùn)行之后才生成的,本節(jié)將數(shù)據(jù)布局分成工作流初始階段和工作流運(yùn)行階段兩個(gè)階段完成。綜上,本節(jié)主要任務(wù)是在兼顧負(fù)載均衡和任務(wù)執(zhí)行時(shí)間的基礎(chǔ)上,以第2節(jié)中的任務(wù)分配結(jié)果為基礎(chǔ),盡可能地以降低數(shù)據(jù)費(fèi)用開(kāi)銷(xiāo)為主要目的,并提出一個(gè)兩階段的基于數(shù)據(jù)集副本的數(shù)據(jù)布局方法。下文分別給出費(fèi)用計(jì)算公式、數(shù)據(jù)集副本建立條件、初始階段數(shù)據(jù)布局方法和運(yùn)行階段數(shù)據(jù)布局方法。

3.1 數(shù)據(jù)傳輸與副本存儲(chǔ)費(fèi)用計(jì)算

本文假定所有數(shù)據(jù)集在任務(wù)執(zhí)行之前傳輸?shù)轿?其傳輸時(shí)間可以忽略不計(jì),且所有數(shù)據(jù)集在數(shù)據(jù)中心上的最后一個(gè)后繼任務(wù)執(zhí)行完畢時(shí)被刪除。

數(shù)據(jù)中心的數(shù)據(jù)傳輸費(fèi)用分為傳出費(fèi)用與傳入費(fèi)用,總費(fèi)用與傳輸?shù)臄?shù)據(jù)總量正相關(guān),傳輸?shù)臄?shù)據(jù)總量越大,傳輸費(fèi)用越高,傳輸數(shù)據(jù)總量越小,傳輸費(fèi)用越低,以亞馬遜AWS亞太地區(qū)(https://aws.amazon.com/cn/pricing/?nc2=h_ql_p)(東京)為例,每月傳入數(shù)據(jù)1 TB～499 TB,0.07美元/GB,每月傳出數(shù)據(jù)1 TB～499 TB,0.141美元/GB。本文單個(gè)數(shù)據(jù)傳輸費(fèi)用的目標(biāo)函數(shù)為:

DTCost(dp)=dp.ds×(up+dp),

q=1,2,…,|DS|

(3)

其中,dp.ds表示數(shù)據(jù)集dp的大小,up表示各數(shù)據(jù)中心的傳出單價(jià),dp表示各數(shù)據(jù)中心的傳入單價(jià),up和dp取值均為常數(shù)。

數(shù)據(jù)中心的存儲(chǔ)費(fèi)用通常按時(shí)間計(jì)費(fèi),存儲(chǔ)時(shí)間越長(zhǎng),費(fèi)用越高。考慮到云環(huán)境下可能存在一些異常導(dǎo)致數(shù)據(jù)集丟失的情況,本文正本數(shù)據(jù)集的存續(xù)時(shí)間為從其第一個(gè)后繼任務(wù)開(kāi)始執(zhí)行到所有數(shù)據(jù)中心上的最后一個(gè)后繼任務(wù)執(zhí)行結(jié)束,這樣無(wú)論在何種情況下,正本存儲(chǔ)時(shí)間都是一定的,所以正本存儲(chǔ)費(fèi)用可直接假設(shè)為常數(shù)C,而副本數(shù)據(jù)集在其相應(yīng)的數(shù)據(jù)中心上用完即刪除,副本的存儲(chǔ)費(fèi)用是需要計(jì)算的。

下面給出本文單個(gè)數(shù)據(jù)集存儲(chǔ)費(fèi)用的目標(biāo)函數(shù):

DSCost(dp)=dp.ds×(latest(sucT.et)-

earliest(sucT.st))×dsp

(4)

其中,dp.ds表示數(shù)據(jù)集dp的大小,earliest(sucT.st)表示數(shù)據(jù)集dp的后繼任務(wù)的最早開(kāi)始時(shí)間,latest(sucT.et)表示數(shù)據(jù)集dp的后繼任務(wù)最晚結(jié)束時(shí)間,dsp表示單位時(shí)間單位容量的存儲(chǔ)價(jià)格。

云環(huán)境下科學(xué)工作流的數(shù)據(jù)布局總費(fèi)用為包括副本數(shù)據(jù)集在內(nèi)的所有數(shù)據(jù)集的傳輸費(fèi)用與存儲(chǔ)費(fèi)用之和,本文中數(shù)據(jù)總費(fèi)用開(kāi)銷(xiāo)的目標(biāo)函數(shù)為:

(5)

3.2 初始階段數(shù)據(jù)集布局方法

初始階段的數(shù)據(jù)集布局方法用于布局DSinit中的數(shù)據(jù)集,該方法基于第2節(jié)任務(wù)分配結(jié)果,以建立數(shù)據(jù)集副本的方法來(lái)減少數(shù)據(jù)總費(fèi)用開(kāi)銷(xiāo)為主要目標(biāo),分為分配DSinit中靈活數(shù)據(jù)集和建立數(shù)據(jù)集副本兩個(gè)步驟(默認(rèn)固定數(shù)據(jù)集已經(jīng)存在于對(duì)應(yīng)的數(shù)據(jù)中心):

步驟1分配DSinit中的靈活數(shù)據(jù)集

輸入數(shù)據(jù)集DSinit,任務(wù)布局方案TL,數(shù)據(jù)中心DC

輸出數(shù)據(jù)布局方案DLinit

1.Sort tiaccording to ti.st

2.for each tiin T:

3.allocate ti.ID to ti.dc//allocate the flexiable datasets

該方法主要是分配DSinit中的靈活數(shù)據(jù)集,時(shí)間復(fù)雜度為O(n)。考慮到DSinit中的數(shù)據(jù)集在工作流運(yùn)行之前便已經(jīng)全部存在,可以從任務(wù)的角度來(lái)分配數(shù)據(jù)集,將任務(wù)按起始時(shí)間排序,起始時(shí)間早的任務(wù)可以?xún)?yōu)先選擇需要用到的數(shù)據(jù)集,將需要用到的數(shù)據(jù)集分配至自己所在的數(shù)據(jù)中心。一般來(lái)說(shuō)任務(wù)個(gè)數(shù)是小于數(shù)據(jù)集個(gè)數(shù)的,從遍歷任務(wù)角度出發(fā)去分配數(shù)據(jù)集比從遍歷數(shù)據(jù)集角度去分配數(shù)據(jù)集更能夠降低時(shí)間復(fù)雜度。

步驟2建立數(shù)據(jù)集副本

輸入數(shù)據(jù)集DSinit,任務(wù)布局方案TL,數(shù)據(jù)中心DC

輸出數(shù)據(jù)布局方案DLinit

1.for each dpin DSinit:

2.if |dp.sucT|≥2:

3.for each dcvin DC:

4.if |dp.sucT|≥2 and dpnot in dcv:

5.calculate DTCost(dp)

6.calculate DSCost(dp)

7.if ((|dp.sucT|-1)×DTCost(dp)>DSCost(dp)

8.build dp’ replication rq //build the //datasets’ replication

9.update dcv.aS

該方法主要是通過(guò)遍歷數(shù)據(jù)集檢查是否需要建立數(shù)據(jù)集副本,算法時(shí)間復(fù)雜度為O(ml),是否建立數(shù)據(jù)集副本,主要取決于以下兩個(gè)條件:

1)|dp.sucT|≥2。

2)(|dp.sucT|-1)×DTCost(dp)-DSCost(dp)>0。

考慮到如果數(shù)據(jù)中心只有一個(gè)任務(wù)需要用到該數(shù)據(jù)集,那么無(wú)論是否建立副本都需要進(jìn)行一次傳輸,此時(shí)建立副本沒(méi)有意義,因此條件1)表示副本存在的條件為一個(gè)數(shù)據(jù)中心至少存在著兩個(gè)任務(wù)需要使用該數(shù)據(jù)集;又考慮到如果數(shù)據(jù)集存儲(chǔ)費(fèi)用大于數(shù)據(jù)集的傳輸費(fèi)用,那么做不到通過(guò)增加存儲(chǔ)費(fèi)用來(lái)降低傳輸費(fèi)用這一目的,因此條件2)表明只有當(dāng)數(shù)據(jù)集的存儲(chǔ)費(fèi)用小于其傳輸費(fèi)用時(shí),副本才會(huì)被建立并存儲(chǔ)。

3.3 運(yùn)行階段數(shù)據(jù)布局方法

工作流運(yùn)行階段數(shù)據(jù)布局方法用于布局DSgen中數(shù)據(jù)集,基于第2節(jié)中任務(wù)分配結(jié)果,仍然以建立數(shù)據(jù)集副本的方法來(lái)減少數(shù)據(jù)總費(fèi)用開(kāi)銷(xiāo)為主要目標(biāo)。

下文給出運(yùn)行階段科學(xué)工作流數(shù)據(jù)布局步驟如下:

輸入數(shù)據(jù)集DSgen,任務(wù)布局TL,數(shù)據(jù)中心DC,任務(wù)集T

輸出數(shù)據(jù)布局方案DLgen

1.for each dpin DSgen:

2.calculate the earliest tiwhich is in dp.sucT

3.if dp.ds

4.allocate dpto TL(ti)

5.update dcv.aS

6.else:

7.calculate next tiwhich is in dp.sucT

8.skip to line 5

9.if |dp.sucT|≥2:

10.for each dcvin DC:

11.if |dp.sucT|≥2 and dp.ds≤dcv.aS and dpnot in dcv:

12.calculate DTCost(dp) and DSCost(dp)

13.if ((|dp.sucT|-1)*DTCost(dp)>DSCost(dp)

14.build dp’ replication rq //build the //datasets’ replication

15.update dcv.aS

16.Return Dlgen

該方法考慮科學(xué)工作流執(zhí)行過(guò)程中的動(dòng)態(tài)性,從單個(gè)數(shù)據(jù)集的角度出發(fā),去考慮數(shù)據(jù)集的分配以及數(shù)據(jù)集副本的建立,每生成一個(gè)數(shù)據(jù)集,便考慮該數(shù)據(jù)集應(yīng)該分配的位置以及是否需要建立數(shù)據(jù)集副本,該方法時(shí)間復(fù)雜度為O(ml)。

該階段數(shù)據(jù)布局思路為依次分配數(shù)據(jù)集并判斷是否需要建立數(shù)據(jù)集副本,與初始階段布局方法的不同之處主要有以下3點(diǎn):

1)分配數(shù)據(jù)集的方法不同;

2)判斷數(shù)據(jù)集是否需要建立副本的時(shí)間不同;

3)建立數(shù)據(jù)集副本的條件稍有不同。

對(duì)于第1)點(diǎn),運(yùn)行階段在分配數(shù)據(jù)集時(shí),由于數(shù)據(jù)集是實(shí)時(shí)生成的,數(shù)據(jù)集不能夠由任務(wù)挑選數(shù)據(jù)集,只能依次被分配,默認(rèn)分配至后繼任務(wù)中最早執(zhí)行的任務(wù)所在的數(shù)據(jù)中心。對(duì)于第2)點(diǎn),初始階段的方法中判斷哪些副本需要被建立是在正本數(shù)據(jù)集分配完畢之后,而考慮到工作流運(yùn)行階段每生成一個(gè)數(shù)據(jù)集都需要被后續(xù)任務(wù)使用,因而運(yùn)行階段每分配一個(gè)數(shù)據(jù)集便需要進(jìn)行一次判斷,如果等所有數(shù)據(jù)集全部產(chǎn)生完畢再進(jìn)行遍歷,此時(shí)已經(jīng)沒(méi)有意義,當(dāng)最后一個(gè)數(shù)據(jù)集生成時(shí),整個(gè)工作流已經(jīng)執(zhí)行完畢。對(duì)于第3)點(diǎn),運(yùn)行階段數(shù)據(jù)布局方法中建立副本的條件比初始階段數(shù)據(jù)集副本建立條件多一個(gè),即還需要判斷當(dāng)前數(shù)據(jù)中心可用容量dcv.aS是否大于當(dāng)前數(shù)據(jù)集大小dp.ds,即需要滿足dcv.aS>dp.ds,如果小于數(shù)據(jù)集大小,則不能建立副本。考慮數(shù)據(jù)中心容量的情況只是為了預(yù)防現(xiàn)實(shí)情況中的過(guò)載,盡管過(guò)載情況極少發(fā)生,然而還是有必要將此考慮在內(nèi)。

4 實(shí)例分析

4.1 輸入設(shè)置

圖2是一個(gè)簡(jiǎn)單的工作流示例,它由10個(gè)任務(wù)t1～t10、15個(gè)初始數(shù)據(jù)集d1～d15和10個(gè)生成數(shù)據(jù)集d16～d25組成,其中,d1、d6和d9為固定數(shù)據(jù)集,分別放置于dc1、dc2和dc33個(gè)數(shù)據(jù)中心上,3個(gè)數(shù)據(jù)中心可用容量均為200 GB。假定各數(shù)據(jù)中心之間上行傳輸費(fèi)用為0.15美元/GB,下行傳輸費(fèi)用為0.1美元/GB,數(shù)據(jù)存儲(chǔ)費(fèi)用為每小時(shí)0.2美元/GB。各數(shù)據(jù)集大小如表2～表4所示。根據(jù)式(2)和表5、表6可得出各任務(wù)起止時(shí)間。

圖2 工作流示例

表2 初始數(shù)據(jù)集

表3 數(shù)據(jù)集生成(預(yù)估大小)

表4 數(shù)據(jù)集生成(實(shí)際大小)

表5 任務(wù)執(zhí)行時(shí)間

表6 各任務(wù)起止時(shí)間

4.2 任務(wù)布局

由上述輸入設(shè)置可以基于式(1)構(gòu)造出以下任務(wù)關(guān)系依賴(lài)矩陣:

可以看出,總?cè)蝿?wù)數(shù)10個(gè),固定任務(wù)3個(gè),非固定任務(wù)7個(gè),數(shù)據(jù)中心3個(gè),因此為一定程度上的負(fù)載均衡,每個(gè)數(shù)據(jù)中心應(yīng)有總?cè)蝿?wù)3個(gè)或4個(gè),固定任務(wù)1個(gè),非固定任務(wù)2個(gè)或者3個(gè)。又因?yàn)閐1、d6和d9為固定數(shù)據(jù)集,分別放置于dc1、dc2和dc33個(gè)數(shù)據(jù)中心上,所以與數(shù)據(jù)集d1相關(guān)的任務(wù)t1應(yīng)放置于數(shù)據(jù)中心dc1上,與數(shù)據(jù)集d6相關(guān)的任務(wù)t4應(yīng)放置于數(shù)據(jù)中心dc2上,與數(shù)據(jù)集d9相關(guān)的任務(wù)t6應(yīng)放置于數(shù)據(jù)中心dc3上。按照第2節(jié)中的思路,第一步將固定任務(wù)按起始時(shí)間排序,排序結(jié)果為:t1→t4→t6,即t1最先開(kāi)始執(zhí)行,t6最后執(zhí)行;第二步將t1加入空集S中,S={t1},與t1依賴(lài)度最高的任務(wù)是t2,將t2加入集合S中,此時(shí)S={t1,t2},接著計(jì)算與t1和t2依賴(lài)度最高的任務(wù),結(jié)果為t3,因此將t3加入S中,此時(shí)S={t1,t2,t3},將此3個(gè)任務(wù)分配至數(shù)據(jù)中心dc1上,刪除Tflex中對(duì)應(yīng)的任務(wù),并將集合S置為空集。由于Tflex不為空集,因此循環(huán)第二步,將第二個(gè)開(kāi)始執(zhí)行的固定任務(wù)t4加入空集S中,此時(shí),S={t4},與t4依賴(lài)度最高的任務(wù)是t8,將t8加入集合S中,此時(shí)S={t4,t8},接著計(jì)算與t4和t8依賴(lài)度最高的任務(wù),結(jié)果為t9,將t9加入S中,此時(shí)S={t4,t8,t9},將此3個(gè)任務(wù)分配至數(shù)據(jù)中心dc2上,刪除Tflex中對(duì)應(yīng)的任務(wù)。由于此時(shí)只剩一個(gè)數(shù)據(jù)中心的任務(wù)沒(méi)有分配,因此剩余所有任務(wù)均分配至數(shù)據(jù)中心dc3上。分配結(jié)果如圖3所示。

圖3 任務(wù)分配結(jié)果

從圖3可以看出,任務(wù)t1、t2和t3位于數(shù)據(jù)中心dc1上,任務(wù)t8、t8和t9位于數(shù)據(jù)中心dc2上,其余4個(gè)任務(wù)位于數(shù)據(jù)中心dc3上。

4.3 初始階段數(shù)據(jù)集分配

首先將所有任務(wù)按起止時(shí)間排序,執(zhí)行時(shí)間早的任務(wù)優(yōu)先選擇需要用到的數(shù)據(jù)集,將數(shù)據(jù)集分配至對(duì)應(yīng)任務(wù)所在的數(shù)據(jù)中心,分配結(jié)果如圖4所示。從圖4可以看出,數(shù)據(jù)集d1、d2、d3、d4、d5和d7位于數(shù)據(jù)中心dc1上,數(shù)據(jù)集d6、d8、d10、d11、d12、d13和d15位于數(shù)據(jù)中心dc26上,其余數(shù)據(jù)集位于數(shù)據(jù)中心dc3上。

圖4 初始階段數(shù)據(jù)集分配結(jié)果

然后建立數(shù)據(jù)集副本,依據(jù)2.2節(jié)的數(shù)據(jù)集副本建立條件,在該階段中,數(shù)據(jù)集d12位于數(shù)據(jù)中心dc2,而位于數(shù)據(jù)中心dc3上的t6和t7都需要用到該數(shù)據(jù)集,d12的少傳的費(fèi)用為3.75美元,d12的存儲(chǔ)時(shí)間為1.5 h,純存儲(chǔ)費(fèi)用為4.5美元,不需要建立副本。

因此最終初始階段布局方案會(huì)有數(shù)據(jù)集d7從數(shù)據(jù)中心dc1傳輸?shù)絛c2;數(shù)據(jù)集d11、d12、d12和d15從數(shù)據(jù)中心dc2傳輸?shù)絛c3;數(shù)據(jù)集d2和數(shù)據(jù)集d5從數(shù)據(jù)中心dc1傳輸?shù)絛c3。

4.4 運(yùn)行階段數(shù)據(jù)集分配

運(yùn)行階段每生成一個(gè)數(shù)據(jù)集,便判斷其分配位置,分配結(jié)果如圖5所示。

圖5 運(yùn)行階段數(shù)據(jù)集分配結(jié)果

從圖5可以看出,數(shù)據(jù)集d16位于數(shù)據(jù)中心dc1上,數(shù)據(jù)集d17、d22、和d23位于數(shù)據(jù)中心dc2上,數(shù)據(jù)集d18、d19、d20、d24和d25位于數(shù)據(jù)中心dc3上。

依據(jù)2.2節(jié)中的數(shù)據(jù)集副本建立條件,在該階段中,數(shù)據(jù)集d17位于數(shù)據(jù)中心dc2上,而位于數(shù)據(jù)中心dc3上的t5、t6都需要用到該數(shù)據(jù)集,d17的單次傳輸費(fèi)用為3美元,存儲(chǔ)費(fèi)用為2.4美元,因此需要建立數(shù)據(jù)集副本r1。

最終,運(yùn)行階段會(huì)有數(shù)據(jù)集d17從數(shù)據(jù)中心dc1傳輸?shù)絛c2;數(shù)據(jù)集d18從數(shù)據(jù)中心dc1傳輸?shù)絛c3;數(shù)據(jù)集d18、d21和d22從數(shù)據(jù)中心dc3傳輸?shù)絛c2;數(shù)據(jù)集d19、d24和d17的副本r1從數(shù)據(jù)中心dc2傳輸?shù)絛c3。

4.5 費(fèi)用計(jì)算

本文的比較方法為文獻(xiàn)[20]中的方法,該方法以減少跨數(shù)據(jù)中心數(shù)據(jù)傳輸費(fèi)用為目標(biāo),比較結(jié)果如圖6、圖7所示。

圖6 初始階段費(fèi)用對(duì)比

圖7 運(yùn)行階段費(fèi)用對(duì)比

從圖6、圖7可以看出,在科學(xué)工作流初始階段,使用本文方法傳輸費(fèi)用為17.25美元,比較方法為23.5美元。副本存儲(chǔ)費(fèi)用本文為0美元,比較方法為0美元。本文方法傳輸費(fèi)用與副本存儲(chǔ)費(fèi)用之和為17.25美元,比較方法為23.5美元,本文方法降低了6.25美元,對(duì)比方法要比本文方法多出36%的費(fèi)用。圖7為運(yùn)行階段兩者費(fèi)用的對(duì)比,利用本文方法數(shù)據(jù)集傳輸費(fèi)用為22美元,比較方法傳輸費(fèi)用為28美元。副本存儲(chǔ)費(fèi)用本文方法為2.4美元,比較方法副本存儲(chǔ)為0美元,本文方法傳輸費(fèi)用與副本存儲(chǔ)費(fèi)用之和為24.4美元,比較方法為28美元。運(yùn)行階段中本文降低了3.6美元的傳輸費(fèi)用,對(duì)比方法比本文費(fèi)用多出15%。

圖8所示為本文方法與對(duì)比方法兩階段費(fèi)用之和。可以看出,本文為41.65美元,對(duì)比方法為51.5美元,比本文方法多出24%的費(fèi)用。

圖8 兩階段費(fèi)用之和對(duì)比

5 結(jié)束語(yǔ)

本文提出一種云環(huán)境下基于任務(wù)分配和數(shù)據(jù)集副本的科學(xué)工作流數(shù)據(jù)布局方法。該方法對(duì)各個(gè)任務(wù)之間的依賴(lài)度進(jìn)行定量計(jì)算,根據(jù)依賴(lài)度較為均勻地將任務(wù)分配至各數(shù)據(jù)中心。考慮到科學(xué)工作流中同一個(gè)數(shù)據(jù)集可能需要多次傳輸,給出基于數(shù)據(jù)集副本的兩階段科學(xué)工作流數(shù)據(jù)布局方法,將數(shù)據(jù)布局細(xì)分成初始階段和運(yùn)行階段。實(shí)例分析結(jié)果驗(yàn)證了該方法的有效性。下一步將結(jié)合云環(huán)境下優(yōu)化的科學(xué)工作流執(zhí)行時(shí)間進(jìn)行更深入的數(shù)據(jù)布局研究。