云科學(xué)工作流中任務(wù)可完成性預(yù)測方法

吳修國 蘇 瑋

(山東財(cái)經(jīng)大學(xué)網(wǎng)絡(luò)與信息安全系 濟(jì)南 250014) (xiuguosd@163.com)

科學(xué)工作流是自動(dòng)或半自動(dòng)地求解復(fù)雜科研問題的過程，是工作流技術(shù)在科學(xué)研究上的應(yīng)用.隨著問題求解規(guī)模的不斷擴(kuò)大，當(dāng)今大型科學(xué)工作流通常需要在復(fù)雜的分布式計(jì)算機(jī)系統(tǒng)上執(zhí)行，例如超級計(jì)算機(jī)、分布式集群系統(tǒng)以及網(wǎng)格系統(tǒng)等[1].然而，構(gòu)造這樣的系統(tǒng)往往需要付出異常昂貴的代價(jià)，申請?jiān)L問這些系統(tǒng)也需要復(fù)雜耗時(shí)的過程.云計(jì)算技術(shù)的靈活、彈性、可定制的特點(diǎn)為解決科學(xué)工作流運(yùn)行過程中遇到的問題提供了新思路[2].云科學(xué)工作流(cloud scientific workflow)通過云計(jì)算平臺(tái)提供的各種資源與服務(wù)部署和執(zhí)行科學(xué)工作流，以低廉的成本為不同地域的研究學(xué)者實(shí)現(xiàn)資源共享與合作研究提供了一個(gè)良好的協(xié)作契機(jī)[3-4].參照國際工作流聯(lián)盟(WfMC)的工作流模型定義，云科學(xué)工作流系統(tǒng)結(jié)構(gòu)模型由云工作流引擎、服務(wù)云、云服務(wù)管理機(jī)以及用戶接口4部分組成，其中，云工作流引擎負(fù)責(zé)創(chuàng)建協(xié)同服務(wù)流程、搭建協(xié)同服務(wù)執(zhí)行網(wǎng)絡(luò)以及管理流程執(zhí)行過程，是實(shí)現(xiàn)云科學(xué)工作流系統(tǒng)的核心[5-6].

作為一種數(shù)據(jù)密集型應(yīng)用，云科學(xué)工作流任務(wù)往往需要處理大量數(shù)據(jù)，為使科學(xué)工作流的多個(gè)子任務(wù)可以并行執(zhí)行，數(shù)據(jù)被放置在不同的數(shù)據(jù)中心，任務(wù)執(zhí)行時(shí)需要頻繁跨數(shù)據(jù)中心進(jìn)行數(shù)據(jù)傳輸和訪問；而在動(dòng)態(tài)分布式環(huán)境下，數(shù)據(jù)中心以及網(wǎng)絡(luò)等失效事件的發(fā)生具有不確定性[7].因此，如何確保云科學(xué)工作流任務(wù)的高效執(zhí)行一直是科學(xué)計(jì)算領(lǐng)域和分布計(jì)算領(lǐng)域共同面臨的熱點(diǎn)和難點(diǎn)問題之一[8-9].通常情況下，云科學(xué)工作流任務(wù)在啟動(dòng)之前，并不能確定任務(wù)所需數(shù)據(jù)是否可用，從而對工作流任務(wù)的完成情況未知.由此，一旦啟動(dòng)云科學(xué)工作流任務(wù)，可能會(huì)由于部分?jǐn)?shù)據(jù)不能訪問導(dǎo)致任務(wù)執(zhí)行中斷.理想的情況是，任務(wù)啟動(dòng)前事先對輸入數(shù)據(jù)的可用性情況進(jìn)行分析，如果發(fā)現(xiàn)所有的輸入數(shù)據(jù)都是可用的，那么可以推測：任務(wù)啟動(dòng)后，預(yù)先設(shè)定的任務(wù)完成的可能性較高；相反地，如果啟動(dòng)前就發(fā)現(xiàn)某些數(shù)據(jù)是不可用的，或者不能由其他數(shù)據(jù)生成，這時(shí)如果啟動(dòng)了云科學(xué)工作流任務(wù)，其執(zhí)行過程很可能會(huì)中斷，從而導(dǎo)致整個(gè)任務(wù)被掛起.云計(jì)算作為一種按需付費(fèi)的計(jì)算模式，用戶使用云計(jì)算資源需要支付一定的費(fèi)用.一旦任務(wù)被掛起，不僅造成經(jīng)濟(jì)損失，還會(huì)使科學(xué)工作流運(yùn)行過程滯后，甚至?xí)绊懙娇茖W(xué)研究的進(jìn)度[10].因此，云科學(xué)工作流對任務(wù)可完成性預(yù)測提出了很高的要求.

應(yīng)該認(rèn)識到，對一個(gè)科學(xué)工作流任務(wù)可完成性的判定是一項(xiàng)非常復(fù)雜的工作，這是因?yàn)楣ぷ髁魅蝿?wù)執(zhí)行處于一個(gè)動(dòng)態(tài)變化的云計(jì)算環(huán)境，任務(wù)所需的數(shù)據(jù)除了系統(tǒng)中已有的原始數(shù)據(jù)，還包括其他任務(wù)執(zhí)行時(shí)計(jì)算產(chǎn)生的中間數(shù)據(jù)；而中間數(shù)據(jù)的生成又有可能來自于一個(gè)或者多個(gè)其他的原始數(shù)據(jù)或者中間數(shù)據(jù).任務(wù)所需數(shù)據(jù)的可用性是預(yù)測任務(wù)可完成性的重要基礎(chǔ)；但是直接對輸入數(shù)據(jù)進(jìn)行可用性判斷是不夠的，還需要對產(chǎn)生該數(shù)據(jù)的原始數(shù)據(jù)進(jìn)行分析.除此之外，云科學(xué)工作流任務(wù)執(zhí)行過程中生成的中間數(shù)據(jù)，又在某種程度上反映了原始數(shù)據(jù)的可用性.所以，某一數(shù)據(jù)可用性可能與其他數(shù)據(jù)的可用性存在相互影響與相互制約的關(guān)系.云科學(xué)工作流任務(wù)的成功執(zhí)行對提高云科學(xué)工作流系統(tǒng)效率具有重要意義；而數(shù)據(jù)的可用性是工作流任務(wù)成功執(zhí)行的關(guān)鍵要素[11].基于上述分析，本文提出一種云計(jì)算環(huán)境下科學(xué)工作流任務(wù)可完成性預(yù)測方法，主要貢獻(xiàn)包括3個(gè)方面：

1) 從定性和定量2個(gè)方面對數(shù)據(jù)可用性以及數(shù)據(jù)間可用性相互支持/抑制關(guān)系建模，并提出數(shù)據(jù)可用性更新算法；

2) 基于任務(wù)的輸入數(shù)據(jù)可用性分析，提出任務(wù)可完成性預(yù)測方法，在云科學(xué)工作流任務(wù)啟動(dòng)前即可對其可完成性進(jìn)行評估；

3) 應(yīng)用不同數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明：基于數(shù)據(jù)可用性/不可用性的任務(wù)可完成性預(yù)測方法可以有效提高對云科學(xué)工作流任務(wù)可完成性情況的認(rèn)知，從而驗(yàn)證了算法的有效性.

1 相關(guān)工作

在云計(jì)算環(huán)境中，受到網(wǎng)絡(luò)、設(shè)備以及大量產(chǎn)生的劣質(zhì)數(shù)據(jù)的影響，云科學(xué)工作流的任務(wù)可完成性預(yù)測是一個(gè)非常重要且富有挑戰(zhàn)性的問題.目前相關(guān)的研究主要是通過不同的任務(wù)調(diào)度策略，提升云科學(xué)工作流系統(tǒng)的效率.比如文獻(xiàn)[12]提出了一種云平臺(tái)下基于相關(guān)度的2階段高效數(shù)據(jù)放置策略，將任務(wù)調(diào)度到數(shù)據(jù)依賴最大的數(shù)據(jù)中心執(zhí)行，以減少跨數(shù)據(jù)中心科學(xué)工作流執(zhí)行時(shí)的數(shù)據(jù)傳輸量.然而，該策略僅考慮了有關(guān)原始數(shù)據(jù)的可用性；同時(shí)，對每個(gè)工作流都要進(jìn)行數(shù)據(jù)布局與任務(wù)調(diào)度，勢必增加系統(tǒng)負(fù)擔(dān)，導(dǎo)致科學(xué)工作流的執(zhí)行效率反而下降.文獻(xiàn)[13]針對跨數(shù)據(jù)中心數(shù)據(jù)傳輸、數(shù)據(jù)依賴關(guān)系和全局負(fù)載均衡3個(gè)目標(biāo)，提出了3階段數(shù)據(jù)布局策略，對數(shù)據(jù)布局方案進(jìn)行求解和優(yōu)化.但是，云計(jì)算環(huán)境中的數(shù)據(jù)往往位于不同的數(shù)據(jù)中心，無論在構(gòu)建階段還是執(zhí)行階段，在任務(wù)所需數(shù)據(jù)的可用性未知的情況下，對云計(jì)算環(huán)境下的數(shù)據(jù)進(jìn)行密集型應(yīng)用是不現(xiàn)實(shí)的.文獻(xiàn)[14]引入局部關(guān)鍵路徑算法思想，提出基于代價(jià)驅(qū)動(dòng)的科學(xué)工作流調(diào)度策略.然而，該方法并沒有解決任務(wù)可完成性預(yù)測問題，也沒有考慮調(diào)度對任務(wù)完成率提升的影響.文獻(xiàn)[15]針對傳統(tǒng)自適應(yīng)慣性權(quán)重的粒子群任務(wù)調(diào)度算法容易陷入局部最優(yōu)，導(dǎo)致調(diào)度方案的執(zhí)行時(shí)間與費(fèi)用較高的問題，提出了一種新的自適應(yīng)慣性權(quán)重計(jì)算方法NAIWPSO，以獲得執(zhí)行費(fèi)用更優(yōu)的調(diào)度方案.該算法著重在提高調(diào)度的效率，對調(diào)度前后任務(wù)的完成情況涉及較少.副本也是云計(jì)算環(huán)境下提高數(shù)據(jù)可用性重要手段之一，通過在不同的數(shù)據(jù)中心復(fù)制副本，在降低網(wǎng)絡(luò)傳輸時(shí)間的同時(shí)，提高了數(shù)據(jù)可靠性與可用性[16].然而，過多的數(shù)據(jù)副本不僅會(huì)帶來系統(tǒng)存儲(chǔ)、更新等開銷，而且多副本帶來的不一致性對數(shù)據(jù)的可用性提出了更高的要求.

一般來說，數(shù)據(jù)可用性是指數(shù)據(jù)滿足一致性、精確性、完整性、時(shí)效性和實(shí)體同一性這5個(gè)特征的程度[17]；許多學(xué)者從上述可用性特征出發(fā)進(jìn)行研究，比如文獻(xiàn)[18]針對并行任務(wù)調(diào)度，通過感知任務(wù)“可用性需求”和計(jì)算資源“可用性保障”，提出了2種可用性感知的調(diào)度算法Afsa和Agsa，提高了任務(wù)調(diào)度的成功率；文獻(xiàn)[19]通過引入資源可用性模型，提出了一種用于維護(hù)可用性信息的方法；文獻(xiàn)[20]從已有的一致性維護(hù)方法出發(fā)，對一致性維護(hù)過程中所涉及的更新發(fā)布、更新傳播方式、更新傳播內(nèi)容、更新沖突解決等幾個(gè)方面進(jìn)行了分析，提出了相應(yīng)的解決辦法；文獻(xiàn)[21]研究了包含冗余記錄的集合在給定時(shí)效約束下的時(shí)效性判定問題，并首次提出了時(shí)效性判定問題的求解算法；為提升云平臺(tái)的數(shù)據(jù)可用性；文獻(xiàn)[22]設(shè)計(jì)并實(shí)現(xiàn)一種虛擬化故障檢測恢復(fù)系統(tǒng).在本文中，數(shù)據(jù)可用性是指數(shù)據(jù)是有效地、可訪問地.上述文獻(xiàn)從不同側(cè)面提出了提高任務(wù)可完成性的策略，但是大都以孤立的單一數(shù)據(jù)作為研究對象，既沒有考慮數(shù)據(jù)之間的生成關(guān)系，也沒有考慮數(shù)據(jù)之間可用性影響.如何保證具有關(guān)聯(lián)關(guān)系的數(shù)據(jù)在云計(jì)算環(huán)境中的可用性研究并不多，尤其是針對云科學(xué)工作流中中間數(shù)據(jù)可用性感知方面的研究較少，缺少具體的分析方法.文獻(xiàn)[23]從目標(biāo)之間相互支持/抑制的角度提出了一種目標(biāo)可滿足性推理方法，對本文的研究具有借鑒意義.

綜上，從云科學(xué)工作流任務(wù)執(zhí)行所需數(shù)據(jù)出發(fā)，基于數(shù)據(jù)間生成關(guān)系，提出數(shù)據(jù)可用性支持/抑制關(guān)系模型；之后，基于數(shù)據(jù)可用性/不可用性關(guān)系傳遞規(guī)則，給出數(shù)據(jù)可用性/不可用性更新算法，并提出基于數(shù)據(jù)可用性的任務(wù)可完成性預(yù)測方法，以此在云科學(xué)工作流任務(wù)啟動(dòng)之前預(yù)判任務(wù)的完成性情況，從而提高對云科學(xué)工作流任務(wù)執(zhí)行情況的認(rèn)知.

2 相關(guān)模型及問題定義

本節(jié)給出云科學(xué)工作流中任務(wù)、數(shù)據(jù)、數(shù)據(jù)生成關(guān)系及數(shù)據(jù)間可用性關(guān)系模型，并引入帶可用性支持度的數(shù)據(jù)生成關(guān)系圖.

2.1 任務(wù)以及數(shù)據(jù)生成關(guān)系模型

在云科學(xué)工作流中，任務(wù)是指為實(shí)現(xiàn)某一業(yè)務(wù)目標(biāo)而組合起來的數(shù)據(jù)、流程等.

定義1. 任務(wù).任務(wù)t可以描述為一個(gè)五元組形式(ti d，Gt，TL，Din，Dout)，其中：

1)ti d是工作流任務(wù)標(biāo)識，具有唯一性；

2)Gt是云科學(xué)工作流業(yè)務(wù)目標(biāo)描述；

3)TL=({st1，din1，R1，dout1，st2，din2，R2，dout2，…，}，Schedule)是工作流任務(wù)說明書，包括2部分：任務(wù)列表{st1，din1，R1，dout1，st2，din2，R2，dout2，…，}和任務(wù)調(diào)度Schedule；Ri是子任務(wù)sti的資源需求，i∈{1，2，…，n}；

云計(jì)算環(huán)境下，數(shù)據(jù)存儲(chǔ)在相對獨(dú)立的云數(shù)據(jù)中心；數(shù)據(jù)中心通過網(wǎng)絡(luò)建立連接.不失一般性，這里的數(shù)據(jù)是一個(gè)抽象概念，指具有完整意義的信息實(shí)體，既可以是文件系統(tǒng)中一個(gè)有一定獨(dú)立信息的文件，也可以是存儲(chǔ)系統(tǒng)中的一個(gè)對象.設(shè)數(shù)據(jù)集合為D={d1,d2,…,dn}.

云科學(xué)工作流環(huán)境中，依據(jù)數(shù)據(jù)的來源，可以將數(shù)據(jù)分為原始數(shù)據(jù)和生成數(shù)據(jù)2種形式，即dtype∈{T_ori，T_gen}，其中，T_ori為原始數(shù)據(jù)集，主要指作為流程應(yīng)用的初始數(shù)據(jù)，是科學(xué)工作流進(jìn)行數(shù)據(jù)分析和處理的基礎(chǔ)，其存儲(chǔ)位置相對固定，一旦被刪除將不能被恢復(fù).T_gen為生成數(shù)據(jù)集或者中間數(shù)據(jù)集，指由原始數(shù)據(jù)集經(jīng)過一次或多次計(jì)算產(chǎn)生的中間或者最終數(shù)據(jù)，其存儲(chǔ)位置可以靈活存放，如果已知數(shù)據(jù)的生成過程也可重新生成.

定義2. 生成關(guān)系.設(shè)有生成數(shù)據(jù)di和dj，如果dj(也可能聯(lián)合其他的數(shù)據(jù)dk)可經(jīng)過計(jì)算得到數(shù)據(jù)di，則稱數(shù)據(jù)di和dj之間具有生成關(guān)系，記為dj→di.

定義3. 數(shù)據(jù)生成關(guān)系圖.數(shù)據(jù)生成關(guān)系圖G可以描述為三元組(VD，ED，φ)，其中：

1)VD是數(shù)據(jù)節(jié)點(diǎn)的集合，它對應(yīng)于一個(gè)數(shù)據(jù)(原始數(shù)據(jù)或者生成數(shù)據(jù))；

2)ED是連接邊的集合，邊e=(di，dj)∈ED當(dāng)且僅當(dāng)數(shù)據(jù)di可由dj是生成；

3)φ是VD上2個(gè)或多個(gè)節(jié)點(diǎn)到{and，or}上的關(guān)系映射，其中，and表示“與”關(guān)系，在關(guān)系圖中用連接弧表示；or表示“或”關(guān)系，在關(guān)系圖中用箭頭表示.

Fig. 1 Data generation relation graph圖1 數(shù)據(jù)生成關(guān)系圖

利用數(shù)據(jù)之間的生成關(guān)系，可以構(gòu)造出數(shù)據(jù)生成關(guān)系圖G，具體構(gòu)造方法如下：

1) 將任意的數(shù)據(jù)di映射為圖G中的點(diǎn)vi；

2) 如果數(shù)據(jù)di，dj之間存在生成關(guān)系，則在圖中添加由vi到vj的有向邊；

3) 依據(jù)數(shù)據(jù)生成的{and，or}關(guān)系，添加連接弧.

2.2 帶可用性支持度的數(shù)據(jù)生成關(guān)系圖

數(shù)據(jù)之間的生成關(guān)系描述了數(shù)據(jù)的來源.在實(shí)際應(yīng)用中，數(shù)據(jù)之間往往還存在著相互影響與相互制約的關(guān)系.舉例來說，假設(shè)數(shù)據(jù)di表示通過計(jì)算得到的某一數(shù)據(jù)集的均值；數(shù)據(jù)dj表示的是對同一數(shù)據(jù)集求其得的方差，如果當(dāng)前數(shù)據(jù)di可經(jīng)過計(jì)算獲得，說明其原始數(shù)據(jù)集是可用的.同時(shí)，從另一方面來說，數(shù)據(jù)di的正確獲取，在很大程度上能夠支持?jǐn)?shù)據(jù)dj正確獲取的可能性，即數(shù)據(jù)di的可用性對數(shù)據(jù)dj的可用性起正向支持作用.再比如說，數(shù)據(jù)dk和數(shù)據(jù)dm被放置在同一個(gè)數(shù)據(jù)中心上存儲(chǔ)，硬件可靠性、網(wǎng)絡(luò)可靠性、傳輸效率等相同，如果目前有證據(jù)表明數(shù)據(jù)dk是不可用的，顯然，dm的不可用的可能性相當(dāng)高.像這種廣泛存在于數(shù)據(jù)間的數(shù)據(jù)可用性相互影響、相互制約的關(guān)系，稱之為可用性支持度.

一般來說，可以將數(shù)據(jù)間的可用性支持度分為4種類型：可用性支持、可用性抑制、不可用性支持和不可用性抑制，分別用+s，-s，+d和-d表示.

在數(shù)據(jù)生成關(guān)系圖的基礎(chǔ)上，增加數(shù)據(jù)之間的可用度支持關(guān)系即可得到帶數(shù)據(jù)可用性支持度的數(shù)據(jù)生成關(guān)系圖.

Fig. 2 Data generation graph with support degree圖2 帶數(shù)據(jù)可用性支持度的數(shù)據(jù)生成圖

定義4. 帶數(shù)據(jù)可用性支持度的數(shù)據(jù)生成關(guān)系圖.帶數(shù)據(jù)可用性支持度的數(shù)據(jù)生成關(guān)系圖G*是一個(gè)四元組(VD，ED，φ，ω)，其中，VD，ED，φ與定義3中的含義相同；ω是定義在VD上2個(gè)數(shù)據(jù)組成的數(shù)據(jù)對到{+s，-s，+d，-d}的可用性支持/抑制映射關(guān)系.

圖2給出了帶數(shù)據(jù)可用性支持度的數(shù)據(jù)生成關(guān)系圖.

3 數(shù)據(jù)可用性的定性描述與推理

為描述數(shù)據(jù)可用性及其推理關(guān)系，本節(jié)引入數(shù)據(jù)可用性定性描述模型，并描述數(shù)據(jù)間可用性/不可用性傳遞關(guān)系.

3.1 數(shù)據(jù)可用性模型

在生成關(guān)系基礎(chǔ)上，進(jìn)一步地，可以用4個(gè)謂詞描述對數(shù)據(jù)di的可用性認(rèn)知，即FS(di)，F(xiàn)D(di)，PS(di)，PD(di).

1)FS(di)：數(shù)據(jù)di一定是可用的(存在足夠的證據(jù)表明數(shù)據(jù)di的可用性)；

2)PS(di)：數(shù)據(jù)di可能是可用的(存在部分證據(jù)表明數(shù)據(jù)di的可用性)；

3)FD(di)：數(shù)據(jù)di一定是不可用的(存在足夠的證據(jù)表明數(shù)據(jù)di的不可用性)；

4)PD(di)：數(shù)據(jù)di可能是不可用的(存在部分證據(jù)表明di不可用).

為了能更加直觀地說明數(shù)據(jù)間的可用性關(guān)系，引入蘊(yùn)含算子“?”.P?Q當(dāng)且僅當(dāng)由條件謂詞定義的謂詞公式“P→Q”是一個(gè)永真式(重言式).

顯然，對同一個(gè)數(shù)據(jù)di滿足2個(gè)公理：

公理1.FS(di)?PS(di).

公理2.FD(di)?PD(di).

結(jié)合前面數(shù)據(jù)間的生成關(guān)系、數(shù)據(jù)間可用性描述以及公理1,2，數(shù)據(jù)之間的可用性關(guān)系存在以下性質(zhì).

1)FS(dj)∧FS(dk)?FS(di).

2)PS(dj)∧PS(dk)?PS(di).

3)FD(dj)?FD(di);

FD(dk)?FD(di).

4)PD(dj)?PD(di)；

PD(dk)?PD(di).

1)FS(dj)?FS(di)；

FS(dk)?FS(di).

2)PS(dj)?PS(di)；

PS(dk)?PS(di).

3)FD(dj)∧FD(dk)?FD(di).

4)PD(dj)∧PD(dk)?PD(di).

性質(zhì)3. 數(shù)據(jù)di和dj的可用性關(guān)系：

3.2 數(shù)據(jù)間可用性不可用性定性推理規(guī)則

為進(jìn)一步描述數(shù)據(jù)間可用性/不可用性傳遞關(guān)系，引入模糊謂詞Ava(di)和模糊謂詞Una(di)以度量數(shù)據(jù)的可用性情況.謂詞Ava(di)和謂詞Una(di)分別表示對數(shù)據(jù)di的可用性和不可用性的定性評價(jià)，并將數(shù)據(jù)di的可用性/不可用性程度劃分為3個(gè)等級{F，P，N}，其中F表示“完全”，P表示“部分”，N表示“未知”，并約定F>P>N.由此，模糊謂詞Ava(di)和模糊謂詞Una(di)可視作一個(gè)可比較大小值的三值邏輯.

基于模糊謂詞Ava(di)和模糊謂詞Una(di)的數(shù)據(jù)可用性/不可用性解釋如下：

1)Ava(di)=F表示有充足的證據(jù)表明數(shù)據(jù)di是可用的.

2)Ava(di)=P表示有部分證據(jù)表明數(shù)據(jù)di是可用的.

3)Ava(di)=N表示數(shù)據(jù)di可用性未知.

4)Una(di)=F表示有充足的證據(jù)表明數(shù)據(jù)di是不可用的.

5)Una(di)=P表示有部分證據(jù)表明數(shù)據(jù)di是不可用的.

6)Una(di)=N表示數(shù)據(jù)di不可用性未知.

1) 如果Ava(dj)=N，那么Ava(di)=N；

2) 如果Ava(dj)=P，那么Ava(di)=P；

3) 如果Ava(dj)=F，那么Ava(di)≥P.

基于上述約定和分析，可以得到表1所示的數(shù)據(jù)可用性/不可用性傳遞規(guī)則.

Table 1 Data Availability and Unavailability Propagation Rules in the Qualitative Reasoning 表1 數(shù)據(jù)可用性不可用性定性傳遞規(guī)則

Table 1 Data Availability and Unavailability Propagation Rules in the Qualitative Reasoning 表1 數(shù)據(jù)可用性不可用性定性傳遞規(guī)則

IndexDataRelationAvailabilityAva(di)UnavailabilityUna(di)1(dj，dk)and→dimin(Ava(dj)，Ava(dk))max(Una(dj)，Una(dk))2(dj，dk)or→dimax(Ava(dj)，Ava(dk))min(Una(dj)，Una(dk))3dj+s→dimin(Ava(dj)，P)N4dj-s→diNmin(Ava(dj)，P)5dj+d→diNmin(Una(dj)，P)6dj-d→dimin(Una(dj)，P)N

3.3 數(shù)據(jù)生成關(guān)系圖中可用性不可用性更新算法

在云科學(xué)工作流管理中，工作流任務(wù)往往運(yùn)行在一個(gè)服務(wù)動(dòng)態(tài)、多變的環(huán)境中，數(shù)據(jù)可用性也會(huì)隨著外界環(huán)境的變化而不斷變化.一旦一個(gè)數(shù)據(jù)的可用性發(fā)生變化，可能會(huì)對其他數(shù)據(jù)的可用性認(rèn)知產(chǎn)生影響，而這會(huì)直接關(guān)系到對工作流任務(wù)的完成情況的預(yù)測.比如某些中間數(shù)據(jù)被刪除，或者網(wǎng)絡(luò)擁塞等，會(huì)使得某些數(shù)據(jù)的不可用性提高，或者可以斷定某個(gè)數(shù)據(jù)是不可用的.因此，當(dāng)某些數(shù)據(jù)的可用性發(fā)生變化時(shí)，要及時(shí)更新帶支持度的數(shù)據(jù)生成關(guān)系圖中各數(shù)據(jù)的可用性.算法1給出了帶支持度的數(shù)據(jù)生成關(guān)系圖中數(shù)據(jù)可用性情況更新算法.

算法1. 數(shù)據(jù)可用性更新算法.

輸入：帶支持度的數(shù)據(jù)生成關(guān)系圖G*=(VD，ED，φ，ω)，數(shù)據(jù)可用性初始評價(jià)值Initial[]；

輸出：更新后的數(shù)據(jù)可用性評價(jià)值Current[].

① Begin

②Current[]=Initial[]；/*初始化*/

③ While(Current[]≠Old[]) Do

④Old[]=Current[]；

⑤ 對每一個(gè)di∈VDDo

⑥Current[i]=Update_Ava_Una(i，G*，Old)；

⑦ End while

⑧ ReturnCurrent[]；

⑨ End

其中，Update_Ava_Una()是數(shù)據(jù)可用性/不可用性更新函數(shù).

函數(shù)1.Update_Ava_Una(i，G*，Old)

① Begin

③ {Avai j=Apply_Rules_Ava(di，r，

Old)；

④Unai j=Apply_Rules_Una(di，r，

Old)；}

⑤ Return(max(maxj(Avai j)，

Old[i].ava)，max(maxj(Unai j)，

Old[i].una))；

⑥ End

算法1定義了數(shù)據(jù)結(jié)構(gòu)Initial[]，Current[]和Old[]，它們的值域均為{F，P，N}，分別用來存儲(chǔ)數(shù)據(jù)的初始可用性評價(jià)值、當(dāng)前可用性評價(jià)值和前一次可用性評價(jià)值，其中Old[]的初始值全為N.Apply_Rules_Ava()指的是應(yīng)用表1中的可用性傳遞規(guī)則；Apply_Rules_Una()指的是應(yīng)用表1中的不可用性傳遞規(guī)則.算法開始時(shí)，將數(shù)組Current[]置為Initial[]，在后面的每一步操作中，數(shù)據(jù)di的可用性/不可用性屬性Ava(di)/Una(di)都會(huì)通過函數(shù)Update_Ava_Una()得到更新，直到Current[]和Old[]中的值相等，循環(huán)結(jié)束.

定理1. 給定帶支持度的數(shù)據(jù)生成依賴圖G*及其可用性初始值Initial[]，算法1中的循環(huán)最多會(huì)執(zhí)行6|VD|+1次，|VD|表示圖G*中節(jié)點(diǎn)的個(gè)數(shù).

證明. 從算法1中的語句⑥以及函數(shù)1中語句⑤可以看出，對每一個(gè)數(shù)據(jù)di都有：

Current[i].ava=max(…，Old[i].ava)；
Current[i].una=max(…，Old[i].una).

所以，數(shù)據(jù)di的可用性/不可用性值是單調(diào)非遞減的.如果算法沒有結(jié)束，那么從循環(huán)條件(Current[]≠Old[])可知每一次循環(huán)至少有一個(gè)值會(huì)發(fā)生變化.關(guān)系圖G*共有|VD|個(gè)數(shù)據(jù)，每一個(gè)數(shù)據(jù)di有2個(gè)屬性：ava和una，而他們的可能取值只有3個(gè)，即{F，P，N}，所以每一次循環(huán)至少有一個(gè)值會(huì)增加，最多增加3次.因此，算法1最多會(huì)執(zhí)行6|VD|+1次.

證畢.

利用上述數(shù)據(jù)可用性推理及更新算法，基于數(shù)據(jù)可用性的任務(wù)可完成性以及不可完成性的定性描述如下.

定義5. 設(shè)有任務(wù)t，則基于數(shù)據(jù)可用性的任務(wù)可完成性定義為Pos_t=min(din1.ava，din2.ava，…，dinn.ava),不可完成性定義為Impos_t=max(din1.una，din2.una，…，dinn.una)，dini∈t.Din，i∈{1，2，…，n}.

4 數(shù)據(jù)可用性的定量描述與推理

從第3節(jié)的分析可以看出，數(shù)據(jù)之間在可用性方面存在一定程度上的支持/抑制影響，而這種可用性關(guān)系究竟會(huì)起多大的作用，則需要對它們進(jìn)行定量分析.

4.1 數(shù)據(jù)可用性定量描述

類似于3.1節(jié)的討論，為了能夠定量地描述數(shù)據(jù)的可用性，引入模糊謂詞Ava(di)和模糊謂詞Una(di)，分別用于對數(shù)據(jù)di的可用性和不可用性程度進(jìn)行定量度量，其中，0≤Ava(di)≤1，0≤Una(di)≤1.由于Ava(di)和Una(di)的值域是一個(gè)實(shí)值域，所以它們具有模糊函數(shù)的意義.

與數(shù)據(jù)可用性定性分析一樣，數(shù)據(jù)之間的可用性關(guān)系定量分析也具有相似的性質(zhì).為此，引入關(guān)系運(yùn)算符?和⊕，它們都是[0，1]×[0，1]→[0，1]上的二元函數(shù).對于任意x，y∈[0，1]，運(yùn)算符定義如下：

1)x?y=x×y；

2)x⊕y=x+y-x×y.

顯然，運(yùn)算符定義滿足關(guān)系：x?y≤x，y≤x⊕y.

1) (Ava(dj)≥x)∧(Ava(dk)≥y)?Ava(di)≥(x?y).

2) (Una(dj)≥x)∧(Una(dk)≥y)?Una(di)≥(x⊕y).

1) (Ava(dj)≥x)∧(Ava(dk)≥y)?Ava(di)≥(x⊕y).

2) (Una(dj)≥x)∧(Una(dk)≥y)?Una(di)≥(x?y).

性質(zhì)6. 數(shù)據(jù)di和dj的可用性關(guān)系：

其中，w是權(quán)值，可以將其解釋為條件概率，即p[di可用/dj可用]，也就是當(dāng)數(shù)據(jù)dj可用時(shí)di可用的概率.基于上述分析，數(shù)據(jù)之間的可用性/不可用性定量傳遞規(guī)則如表2所示:

Table 2 Data Availability and Unavailability Propagation Rules in the Quantitative Reasoning

表2 數(shù)據(jù)可用性不可用性定量傳遞規(guī)則

Table 2 Data Availability and Unavailability Propagation Rules in the Quantitative Reasoning

IndexDataRelationAvailabilityAva(di)UnavailabilityUna(di)1(dj，dk)and→diAva(dj)?Ava(dk)Una(dj) Una(dk)2(dj，dk)or→diAva(dj) Ava(dk)Una(dj)?Una(dk)3djw+s→diAva(dj)?wN4djw-s→diNAva(dj)?w5djw+d→diNUna(dj)?w6djw-d→diUna(dj)?wN

4.2 數(shù)據(jù)間可用性不可用性定量推理

給定帶支持度的數(shù)據(jù)生成關(guān)系圖G*及其可用性初始值Initial[]，可以利用算法1對生成關(guān)系圖中各數(shù)據(jù)的可用性進(jìn)行更新.盡管數(shù)據(jù)可用性狀態(tài)的度量值(Ava()和Una()的值)均為介于0～1之間的實(shí)數(shù)，算法1仍然是可終止的.

定理2. 給定帶支持度的數(shù)據(jù)生成關(guān)系圖G*及其可用性/不可用性初始值(Initial[])，可以利用算法1求得數(shù)據(jù)di(di∈VD)更新后的可用性/不可用性值，并且算法是可終止的.

① 一個(gè)無限序列an是柯西收斂的，當(dāng)且僅當(dāng)對于任意選定的正數(shù)ε，必存在一個(gè)整數(shù)N，使得對于任意正整數(shù)n(n≥N)都有|an+1-an|<ε；序列an是收斂的當(dāng)且僅當(dāng)它是柯西收斂的.

證明. 和定理1一樣，數(shù)據(jù)di的可用性/不可用性值是單調(diào)非遞減的.算法1中的循環(huán)終止條件Current[]=Old[]，可以變換為形式：

其中,ε是一個(gè)無限趨向于0的實(shí)數(shù).由于di.ava和di.una的上界是恒定的常數(shù)1.所以，序列Current[i]k.ava和Current[i]k.una都是收斂的(柯西收斂準(zhǔn)則)①.因此，算法1經(jīng)過有限次循環(huán)之后會(huì)終止.

證畢.

由此，與定義5相似，可得基于數(shù)據(jù)可用性的任務(wù)可完成性以及不可完成性的定量描述，用數(shù)據(jù)可用性的定量值替換其中的定性值即可.

5 實(shí)驗(yàn)分析

本節(jié)首先給出實(shí)驗(yàn)環(huán)境,然后進(jìn)行仿真實(shí)驗(yàn)并分析實(shí)驗(yàn)結(jié)果.

5.1 實(shí)驗(yàn)環(huán)境

為測試基于數(shù)據(jù)可用性的云科學(xué)工作流任務(wù)可完成性預(yù)測方法的有效性，在本單位云計(jì)算實(shí)驗(yàn)室的仿真環(huán)境中進(jìn)行實(shí)驗(yàn).該實(shí)驗(yàn)環(huán)境參照了澳大利亞斯文本科技大學(xué)信息與通訊學(xué)院的SwinDeW-C[5-7]體系結(jié)構(gòu)開發(fā)而成，其上安裝了VMWare②用于數(shù)據(jù)存儲(chǔ)服務(wù)；在數(shù)據(jù)中心部署了Hadoop③用于MapReduce系統(tǒng)開發(fā)與數(shù)據(jù)管理；其硬件配置為：Inter?CoreTMi5-3210M 2.5 GHz；RAM 4 GB；硬盤8 TB；100 MB網(wǎng)絡(luò)帶寬.仿真軟件在CloudSim[24]的基礎(chǔ)上進(jìn)行了擴(kuò)展開發(fā)，每個(gè)數(shù)據(jù)中心存放的原始數(shù)據(jù)個(gè)數(shù)為50～200個(gè)不等，數(shù)據(jù)大小規(guī)模為10～20 GB.每個(gè)任務(wù)所包含的輸入數(shù)據(jù)個(gè)數(shù)為10～100個(gè).本文采用模擬的、可定制的科學(xué)工作流來測試基于數(shù)據(jù)可用性的任務(wù)可完成性預(yù)測方法的有效性，通過分別改變科學(xué)工作流的輸入數(shù)據(jù)和任務(wù)的數(shù)量來控制科學(xué)工作流的復(fù)雜度.實(shí)驗(yàn)過程中，為了保證結(jié)果的可靠性，每一個(gè)科學(xué)工作流在保持配置和云平臺(tái)環(huán)境不變的情況下，運(yùn)行100次后取平均值作為測試結(jié)果.最后，以成功執(zhí)行的工作流任務(wù)比率與本文提出的數(shù)據(jù)可用性模型預(yù)測的比率作為評價(jià)指標(biāo)進(jìn)行比較，并分析實(shí)驗(yàn)結(jié)果.

5.2 實(shí)驗(yàn)結(jié)果及分析

仿真實(shí)驗(yàn)1主要是比較工作流任務(wù)可完成性與數(shù)據(jù)可用性之間的關(guān)系，即基于數(shù)據(jù)可用性的任務(wù)可完成性判定的可行性問題.圖3給出了不同工作流數(shù)目下，工作流任務(wù)實(shí)際完成率與數(shù)據(jù)可用率關(guān)系圖.從圖3中可以看出，在不同的工作流數(shù)目下，任務(wù)的完成率與數(shù)據(jù)可用率變化趨勢相似，反映了任務(wù)可完成性與數(shù)據(jù)可用性的密切關(guān)系；同時(shí)，任務(wù)的完成率略低于數(shù)據(jù)可用率的原因在于除了數(shù)據(jù)可用性之外，任務(wù)完成還受到數(shù)據(jù)中心、網(wǎng)絡(luò)等因素的影響.

Fig. 3 Relationship between cloud scientific task completion and data availability圖3 任務(wù)可完成性與數(shù)據(jù)可用性之間的關(guān)系

仿真實(shí)驗(yàn)2主要是從定性角度對工作流任務(wù)啟動(dòng)的預(yù)測結(jié)果與實(shí)際執(zhí)行結(jié)果進(jìn)行比較.實(shí)驗(yàn)時(shí)，工作流任務(wù)包含不同數(shù)據(jù)個(gè)數(shù)(Cnt)分別是20，50，80，預(yù)測任務(wù)可完成是指數(shù)據(jù)可用性為F或P的比率.圖4給出了云科學(xué)工作流任務(wù)成功執(zhí)行比率與定性預(yù)測比率比較.

Fig. 4 Comparisons of cloud scientific workflow tasks completion ratio and qualitative prediction ratio圖4 任務(wù)成功執(zhí)行比率與定性預(yù)測比率比較

整體上看，在不同的工作流數(shù)目時(shí)，工作流任務(wù)成功執(zhí)行比率與基于數(shù)據(jù)可用性的預(yù)測結(jié)果相差不大，并且實(shí)際成功執(zhí)行比率略低于預(yù)測值，主要原因是在于圖4中考慮的是數(shù)據(jù)可用性為F或P這2種情況的和，而對于數(shù)據(jù)可用性情況為P的數(shù)據(jù)來說，不一定是可用的.而整體執(zhí)行的效率逐漸降低的原因還在于受到科學(xué)工作流規(guī)模的影響，隨著工作流任務(wù)的增加，數(shù)據(jù)調(diào)用頻繁，導(dǎo)致整體上數(shù)據(jù)可用性降低.

仿真實(shí)驗(yàn)3主要是從定量角度對工作流任務(wù)啟動(dòng)的預(yù)測結(jié)果與實(shí)際執(zhí)行結(jié)果進(jìn)行比較.類似于實(shí)驗(yàn)2，工作流任務(wù)包含數(shù)據(jù)個(gè)數(shù)分別是20，50，80，預(yù)測任務(wù)可完成是指數(shù)據(jù)可用性大于等于60%的任務(wù)比率.

圖5給出了不同工作流任務(wù)數(shù)目時(shí)成功執(zhí)行的比率與數(shù)據(jù)可用性定量預(yù)測比率的比較.預(yù)測結(jié)果以數(shù)據(jù)可用性大于等于0.6作為任務(wù)可完成的標(biāo)準(zhǔn)。從圖5(b)中可以看出，當(dāng)包含數(shù)據(jù)為50且工作流任務(wù)數(shù)為210時(shí)，預(yù)測成功的概率與實(shí)際執(zhí)行的概率相差不大；在任務(wù)數(shù)為180時(shí)，二者相差稍大，原因在于有些生成數(shù)據(jù)沒有被長期保存，或者在調(diào)用時(shí)被其他任務(wù)占用等，總體上對任務(wù)成功執(zhí)行的認(rèn)知影響不大.

Fig. 5 Comparisons of cloud scientific workflow tasks completion ratio and quantitative prediction ratio圖5 任務(wù)成功執(zhí)行比率與定量預(yù)測比率比較

Fig. 6 Influence of data storage time with cloud scientific workflow tasks圖6 數(shù)據(jù)駐留時(shí)間對云科學(xué)工作流任務(wù)預(yù)測值影響

生成數(shù)據(jù)在數(shù)據(jù)中心上的存儲(chǔ)時(shí)間對任務(wù)可完成性預(yù)測具有一定影響，仿真實(shí)驗(yàn)4測試在不同工作流任務(wù)情況下，存儲(chǔ)時(shí)間分別在1，5，10個(gè)單位時(shí)間(1h)時(shí)，基于數(shù)據(jù)可用性的任務(wù)可完成性預(yù)測結(jié)果與實(shí)際執(zhí)行結(jié)果的比較.結(jié)果如圖6所示.從圖6中可以看出，不同的生成數(shù)據(jù)駐留時(shí)間情況下，任務(wù)完成率的預(yù)測值之間存在一定差異，隨著駐留時(shí)間延長，實(shí)際值與預(yù)測值之間愈來愈接近；而在駐留時(shí)間較短時(shí)，預(yù)測值與實(shí)際值差異較大，主要原因是盡管預(yù)測的生成數(shù)據(jù)可用，而實(shí)際執(zhí)行時(shí)，生成數(shù)據(jù)可能會(huì)被刪除.

實(shí)驗(yàn)表明：云科學(xué)工作流任務(wù)在啟動(dòng)工作流之前，通過對當(dāng)前環(huán)境中各數(shù)據(jù)可用性分析，在不同的工作流數(shù)目與輸入數(shù)據(jù)個(gè)數(shù)情況下，能夠基本預(yù)測工作流任務(wù)的完成情況，提高了系統(tǒng)的效率.利用該方法，如果數(shù)據(jù)可用性較高，則可以啟動(dòng)該工作流任務(wù)運(yùn)行；反之，當(dāng)數(shù)據(jù)可用性較低時(shí)，則需要調(diào)整任務(wù)，或者等待數(shù)據(jù)可用性較高時(shí)再啟動(dòng).

6 總 結(jié)

云計(jì)算環(huán)境的動(dòng)態(tài)與開放性、云服務(wù)的分布自治性和科學(xué)工作流業(yè)務(wù)邏輯的松散耦合性，使得云科學(xué)工作流系統(tǒng)可以充分發(fā)揮兩者的綜合優(yōu)勢；同時(shí)，也給云科學(xué)工作流任務(wù)的可完成性預(yù)測提出了更高要求.然而，據(jù)我們了解，目前有關(guān)云計(jì)算環(huán)境下科學(xué)工作流任務(wù)的可完成性預(yù)測的研究還非常少.

本文針對云科學(xué)工作流環(huán)境動(dòng)態(tài)變化、生成數(shù)據(jù)的可用性更新頻繁等特點(diǎn)，提出一種基于數(shù)據(jù)可用性的工作流任務(wù)可完成性預(yù)測方法：通過對數(shù)據(jù)間的可用性支持/抑制關(guān)系，分析預(yù)測任務(wù)的可完成性，盡可能地避免了任務(wù)早期的失敗對后續(xù)任務(wù)的影響，從而在工作流任務(wù)執(zhí)行前即可對任務(wù)的完成情況有所認(rèn)知，在有效提升云科學(xué)工作流系統(tǒng)執(zhí)行效率的同時(shí)，減少了云計(jì)算系統(tǒng)資源的浪費(fèi).實(shí)驗(yàn)結(jié)果表明了該方法的有效性和可靠性，對提高云科學(xué)工作流系統(tǒng)性能具有重要意義.未來的研究工作包括：

1) 本文給出的數(shù)據(jù)可用性/不可用性為靜態(tài)值，應(yīng)采用人工神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)等機(jī)器學(xué)習(xí)算法動(dòng)態(tài)修改它們的值，從而提高數(shù)據(jù)的可用性以及推理的實(shí)用性；

2) 本文針對的是單一云科學(xué)工作流任務(wù)的可完成性預(yù)測，還需要對多個(gè)工作流任務(wù)并行執(zhí)行時(shí)的任務(wù)可完成性預(yù)測進(jìn)行研究.

[1] Deldari A, Naghibzadeh M, Abrishami S. CCA: A deadline-constrained workflow scheduling algorithm for multicore resources on the cloud[J]. Journal of Supercomputing, 2016, 73(2): 756-781

[3] Zhang Weimin, Liu Cancan, Luo Zhigang. A review on scientific workflows[J]. Journal of National University of Defense Technology, 2011, 33(3): 56-65 (in Chinese)

(張衛(wèi)民, 劉燦燦, 駱志剛. 科學(xué)工作流技術(shù)研究綜述[J]. 國防科技大學(xué)學(xué)報(bào), 2011, 33(3): 56-65)

[4] Wu Zhangjun, Liu Xiao, Ni Zhiwei, et al. A market-oriented hierarchical scheduling strategy in cloud workflow systems[J]. The Journal of Supercomputing, 2013, 63(1): 256-293

[5] Yuan Dong, Yang Yun, Liu Xiao, et al. On-demand minimum cost benchmarking for intermediate dataset storage in scientific cloud workflow systems[J]. Journal of Parallel & Distributed Computing, 2011, 71(2): 316-332

[6] Wu Xiuguo. Migrating Workflow and Cloud Workflow[M]. Shanghai: Shanghai Jiaotong University Press, 2014 (in Chinese)

(吳修國. 遷移工作流與云工作流[M]. 上海: 上海交通大學(xué)出版社, 2014)

[7] Yuan Dong, Yang Yun, Liu Xiao, et al. A highly practical approach toward achieving minimum data sets storage cost in the cloud[J]. IEEE Trans on Parallel & Distributed Systems, 2013, 24(6): 1234-1244

[8] Li Xiu, Song Jingdong, Huang Biqing. A scientific workflow management system architecture and its scheduling based on cloud service platform for manufacturing big data analytics[J]. The International Journal of Advanced Manufacturing Technology, 2016, 84(1): 119-131

[9] Wu Zhangjun, Ni Zhiwei, Gu Lichuan, et al. A revised discrete particle swarm optimization for cloud workflow scheduling[C] //Proc of IEEE CIS 2010. Piscataway, NJ: IEEE, 2010: 184-188

[10] Yang Yuli, Peng Xinguang. Trust-based scheduling strategy for cloud workflow applications[C] //Proc of IEEE 3PGCIC 2013. Piscataway, NJ: IEEE, 2013: 316-320

[11] Wang Mingjun, Zhang Jinghui, Dong Fang, et al. Data placement and task scheduling optimization for data intensive scientific workflow in multiple data centers environment[C] //Proc of the 2nd Int Conf on Advanced Cloud and Big Data. Piscataway, NJ: IEEE, 2014: 77-84

[12] Liu Shaowei, Kong Lingmei, Ren Kaijun, et al. A two-step data placement and task scheduling strategy for optimizing scientific workflow performance on cloud computing platform[J]. Chinese Journal of Computers, 2011, 34(11): 2121-21305 (in Chinese)

(劉少偉, 孔令梅, 任開軍, 等. 云環(huán)境下優(yōu)化科學(xué)工作流執(zhí)行性能的兩階段數(shù)據(jù)放置與任務(wù)調(diào)度策略[J]. 計(jì)算機(jī)學(xué)報(bào), 2011, 34(11): 2121-2130)

[13] Simmhan Y, Barga R, Ingen C V, et al. Building the trident scientific workflow workbench for data management in the cloud[C] //Proc of IEEE ADVCOMP’09. Piscataway, NJ: IEEE, 2009: 41-50

[14] Lin Bing, Guo Wenzhong, Chen Guolong, et al. Cost-driven scheduling strategy for scientific workflow under multi-cloud environment[J], Pattern Recognition and Artificial Intelligence, 2015, 28(10): 865-875 (in Chinese)

(林兵, 郭文忠, 陳國龍, 等. 多云環(huán)境下基于代價(jià)驅(qū)動(dòng)的科學(xué)工作流調(diào)度策略[J]. 模式識別與人工智能, 2015,28(10): 865-875)

[15] Li Xuejun, Xu Jia, Zhu Erzhou, et al. A novel computation method for adaptive inertia weight of task scheduling algorithm[J]. Journal of Computer Research and Development, 2016, 53(9): 1990-1999 (in Chinese)

(李學(xué)俊, 徐佳, 朱二周, 等. 任務(wù)調(diào)度算法中新的自適應(yīng)慣性權(quán)重計(jì)算方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2016, 53(9): 1990-1999)

[16] Sun Xin, Li Qingzhou, Zhao Pu, et al. An optimized replica distribution method for peer-to-peer network[J]. Chinese Journal of Computers, 2014, 37(6): 1424-1434 (in Chinese)

(孫新, 李慶洲, 趙璞, 等. 對等網(wǎng)絡(luò)中一種優(yōu)化的副本分布方法[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(6): 1424-1434)

[17] Li Jianzhong, Liu Xianmin, An important aspect of big data: Data usability[J]. Journal of Computer Research and Development, 2013, 50(6): 1147-1162 (in Chinese)

(李建中, 劉顯敏. 大數(shù)據(jù)的一個(gè)重要方面: 數(shù)據(jù)可用性[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(6): 1147-1162)

[18] Cao Jie, Zeng Guosun, Niu Jun, et al. Availability-aware scheduling method for parallel task in cloud environment[J], Journal of Computer Research and Development, 2013, 50(7): 1563-1572 (in Chinese)

(曹潔, 曾國蓀, 鈕俊, 等. 云環(huán)境下可用性感知的并行任務(wù)調(diào)度方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(7): 1563-1572)

[19] Ocana K A C S, De Oliveira D, Dias J, et al. Optimizing phylogenetic analysis using SciHmm cloud-based scientific workflow[C] //Proc of the 7th IEEE Int Conf on eScience. Piscataway, NJ: IEEE, 2011: 62-69

[20] Zhou Jing, Wang Yijie, Ruan Wei, et al. Research on massive data oriented data consistency[J]. Computer Science, 2006, 33(4): 137-140 (in Chinese)

(周婧, 王意潔, 阮煒, 等. 面向海量數(shù)據(jù)的數(shù)據(jù)一致性研究[J]. 計(jì)算機(jī)科學(xué), 2006, 33(4): 137-140)

[21] Li Mohan, Li Jianzhong, Gao Hong, Evaluation of data currency[J]. Chinese Journal of Computers, 2012, 35(11): 2348-2360 (in Chinese)

(李默涵, 李建中, 高宏. 數(shù)據(jù)時(shí)效性判定問題的求解算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2012, 35(11): 2348-2360)

[22] Zhu Xiaomin, Wang Ji, Guo Hui, et al. Fault-tolerant scheduling for real-time scientific workflows with elastic resource provisioning in virtualized clouds[J]. IEEE Trans on Parallel & Distributed Systems, 2016, 27(12): 3501-3517

[23] Giorgini P, Mylopoulos J, Nicchiarelli E, et al. Reasoning with goal models[C] //Proc of Int Conf on Conceptual Modeling. Berlin: Springer, 2002: 167-181

[24] Calheiros R N, Ranjan R, Beloglazov A, et al. CloudSim: A toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J]. Software Practice & Experience, 2011, 41(1): 23-50