王瑩瑩 汪靜 涂韜

摘要：云環(huán)境下科學(xué)工作流在運(yùn)行過程中會(huì)產(chǎn)生大量有價(jià)值的信息以組成中間數(shù)據(jù)集，但數(shù)據(jù)集存儲(chǔ)代價(jià)較大。因此通過闡述單云條件下線性工作流中間數(shù)據(jù)集存儲(chǔ)問題代價(jià)最小化算法過程，指出該問題基本概念，闡明多云條件下線性工作流中間數(shù)據(jù)集存儲(chǔ)問題代價(jià)最小化傳統(tǒng)算法并提出改進(jìn)算法，最后指出未來研究方向。

關(guān)鍵詞：中間數(shù)據(jù)集;存儲(chǔ)策略;代價(jià)最小化;云計(jì)算

DOI：10.11907/rjdk.192165

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2019）012-0118-04

0引言

科學(xué)工作流在科學(xué)計(jì)算時(shí)會(huì)產(chǎn)生大量中間數(shù)據(jù)集，研究人員可通過重新分析中間數(shù)據(jù)集得出有價(jià)值的信息用于預(yù)測(cè)，相關(guān)應(yīng)用場(chǎng)景包括天文學(xué)領(lǐng)域的天氣預(yù)測(cè)、高能物理學(xué)領(lǐng)域的微觀世界探索及生物信息學(xué)領(lǐng)域人類遺傳信息分析等。信息時(shí)代對(duì)科學(xué)計(jì)算的要求越來越高，傳統(tǒng)網(wǎng)格計(jì)算無法有效支撐海量數(shù)據(jù)分析，用戶可通過購(gòu)買功能更強(qiáng)大的硬件設(shè)施，建立一個(gè)存儲(chǔ)空間更大的網(wǎng)格系統(tǒng)，但因費(fèi)用過高，系統(tǒng)持續(xù)性差。云計(jì)算的興起打破了這個(gè)困局。云環(huán)境擁有大量虛擬空間，可以給用戶提供廉價(jià)的資源，用戶還可進(jìn)行擴(kuò)展，包括存儲(chǔ)、計(jì)算和傳輸資源，使用極為便利。但用戶在享受服務(wù)的同時(shí)也需要付出一定代價(jià)。在云環(huán)境下進(jìn)行數(shù)據(jù)分析時(shí)，首要問題是代價(jià)最小化問題，即應(yīng)如何處理科學(xué)計(jì)算產(chǎn)生的大量有價(jià)值的中間數(shù)據(jù)集，是存儲(chǔ)、計(jì)算還是轉(zhuǎn)至其它云，如何使研究者分析時(shí)有跡可循且付出代價(jià)最小，尋找中間數(shù)據(jù)集分配的最優(yōu)策略至關(guān)重要。

該問題被稱為中間數(shù)據(jù)集存儲(chǔ)問題，通過對(duì)該問題的研究，可讓用戶得到高效服務(wù)并節(jié)省資源和費(fèi)用。具體地說，單云下代價(jià)最小化算法可讓用戶消耗少量資源、付出最小代價(jià)得到最好服務(wù)。多云下最小化算法研究可讓用戶節(jié)省資源和費(fèi)用，同時(shí)獲得更高效的資源交流。

尋找中間數(shù)據(jù)集分配的最優(yōu)決策不僅需考慮算法代價(jià)模型，還需兼顧算法高效性。袁棟等將僅涉及存儲(chǔ)代價(jià)、重計(jì)算代價(jià)的簡(jiǎn)單代價(jià)模型改進(jìn)為添加用戶使用頻率的代價(jià)模型，讓該問題更具普適性;根據(jù)該思路，Li等對(duì)傳統(tǒng)代價(jià)模型進(jìn)行完善，建立了包含存儲(chǔ)代價(jià)、重計(jì)算代價(jià)、傳遞代價(jià)、用戶使用頻率及用戶延遲容忍度較完善的代價(jià)模型，并依據(jù)該模型設(shè)計(jì)算法得出最優(yōu)策略，但算法不夠高效;在處理多云條件下線性數(shù)據(jù)流的中間數(shù)據(jù)數(shù)據(jù)集存儲(chǔ)問題時(shí)，王瑩瑩等有效利用并行思想優(yōu)化傳統(tǒng)算法，使算法時(shí)間復(fù)雜度由O（m4n3）降到O（m3n3），其中m表示云個(gè)數(shù)，n表示中間數(shù)據(jù)集個(gè)數(shù);陳杰等在處理單云條件下線性數(shù)據(jù)流中間數(shù)據(jù)數(shù)據(jù)集存儲(chǔ)問題時(shí)，通過優(yōu)化存儲(chǔ)結(jié)構(gòu)，利用二叉樹優(yōu)化算法的存儲(chǔ)結(jié)構(gòu)，將時(shí)間復(fù)雜度由O（n2）降到O（nlgn）;而在處理多云條件下中間數(shù)據(jù)集存儲(chǔ)問題上，Xu等利用遺傳算法求解，盡量將代價(jià)最小化，但最優(yōu)代價(jià)準(zhǔn)確度有待提高;陳坤針對(duì)該問題利用微積分優(yōu)化算法，使最終結(jié)果更優(yōu)，但是算法效率有待加強(qiáng)。

綜上所述，云環(huán)境下中間數(shù)據(jù)集存儲(chǔ)問題存在算法效率不高、代價(jià)模型普適性不強(qiáng)的問題。本文針對(duì)這兩個(gè)問題的最典型解決辦法進(jìn)行闡述，并展望未來發(fā)展方向。

1單云條件下中間數(shù)據(jù)集存儲(chǔ)問題Dijkstra算法

1.1算法概述

數(shù)據(jù)流中的數(shù)據(jù)集之間是單向關(guān)系，數(shù)據(jù)流依賴圖（Intermediate Dataset Dependence Graph，IDG）可用一個(gè)單向無環(huán)圖表示，如圖1所示。

數(shù)據(jù)流依賴圖經(jīng)過加輔助節(jié)點(diǎn)ds、de及加邊后，可構(gòu)成數(shù)據(jù)流代價(jià)傳遞圖（cost transitive tournament graph，CTG或CTT），如圖2所示。

其中，x表示數(shù)據(jù)集重計(jì)算代價(jià)，y表示數(shù)據(jù)集存儲(chǔ)代價(jià)，為已知數(shù)據(jù)。舉例說明邊權(quán)值計(jì)算過程：如ds和d2之間的邊權(quán)值為d1的計(jì)算代價(jià)和d2的存儲(chǔ)代價(jià)之和，即X1+y2，又比如ds和d3之間邊權(quán)值為d1、d2的計(jì)算代價(jià)與d3的存儲(chǔ)代價(jià)之和，即x1+x2+ys。

結(jié)合代價(jià)傳遞圖，利用Dijkstra算法找最小代價(jià)，算法過程為：①構(gòu)建代價(jià)傳遞圖;②利用Dijstra算法找開始節(jié)點(diǎn)到結(jié)束節(jié)點(diǎn)所需的最小代價(jià)及最短路徑;③輸出最短路徑對(duì)應(yīng)的數(shù)據(jù)集狀態(tài)序列（最短路徑經(jīng)過的點(diǎn)對(duì)應(yīng)數(shù)據(jù)集狀態(tài)為存儲(chǔ)狀態(tài)，跳過的點(diǎn)對(duì)應(yīng)數(shù)據(jù)集狀態(tài)為重計(jì)算狀態(tài)）。

算法偽代碼如下所示。

算法：Linear_CTT-sP

輸入：開始節(jié)點(diǎn)ds;結(jié)束節(jié)點(diǎn)de;線性數(shù)據(jù)流的依賴圖

輸出：數(shù)據(jù)集序列

1.遍歷依賴圖中的每個(gè)數(shù)據(jù)集di

2.遍歷di的后續(xù)節(jié)點(diǎn)dj

3.建邊e

4.邊權(quán)值初始化為O

5.遍歷di和dj間所有節(jié)點(diǎn)dk

6.計(jì)算di和dk間邊的權(quán)值

7.利用Dijkstra算法求最短路徑

8.輸出最短路徑對(duì)應(yīng)數(shù)據(jù)集狀態(tài)序列

1.2算法不足之處

通過算法步驟分析可知該算法時(shí)間復(fù)雜度為O（n4）;另外，在計(jì)算最小代價(jià)時(shí)，只涉及到存儲(chǔ)代價(jià)及重計(jì)算代價(jià)，并沒有考慮影響最小代價(jià)的其它因素，代價(jià)模型仍存在過于單一的問題。

2多云條件下中間數(shù)據(jù)集存儲(chǔ)問題算法概述

2.1算法概述

多云條件下的中間數(shù)據(jù)集存儲(chǔ)問題涉及的基本概念與單云條件下中間數(shù)據(jù)集存儲(chǔ)問題類似，本部分闡述在多云條件下，數(shù)據(jù)流依賴圖構(gòu)造代價(jià)傳遞圖的過程。

第一步：加點(diǎn)。在原依賴圖中根據(jù)云的個(gè)數(shù)加點(diǎn)。每個(gè)節(jié)點(diǎn)被拆分成多個(gè)節(jié)點(diǎn)，拆分成多少個(gè)點(diǎn)由云的個(gè)數(shù)決定。如圖3所示有m個(gè)云，每個(gè)節(jié)點(diǎn)被拆分成m個(gè)節(jié)點(diǎn)。

2.4算法不足之處

改進(jìn)后的算法通過先計(jì)算最長(zhǎng)邊權(quán)值并同時(shí)存儲(chǔ)中間結(jié)果的方式，有效避免了傳統(tǒng)算法的冗余計(jì)算。具體指通過分析5～27行代碼，可知計(jì)算每條邊的權(quán)值時(shí)間復(fù)雜度由0（m2n）降到O（mn），從而算法整體時(shí)間復(fù)雜度由O（m4n4）降到O（m3n3）。

然而，代價(jià)模型方面仍存在弊端，多云條件下中間數(shù)據(jù)集存儲(chǔ)問題代價(jià)最小化算法涉及的代價(jià)模型除了有存儲(chǔ)代價(jià)和重計(jì)算代價(jià)及云之間的傳遞代價(jià)外，并沒有考慮其它影響因素，如用戶容忍度與數(shù)據(jù)集使用頻率等，嚴(yán)重影響到算法模型普適性。

3結(jié)語

為解決云環(huán)境下中間數(shù)據(jù)集存儲(chǔ)代價(jià)最小化問題，本文通過介紹單云條件下中間數(shù)據(jù)集存儲(chǔ)代價(jià)最小化問題，引出該問題基本概念，并指出目前單云條件下線性數(shù)據(jù)流存儲(chǔ)問題解決方案中存在代價(jià)模型普適性較差的缺陷，闡述了在單云延伸到多云條件下線性數(shù)據(jù)流中間數(shù)據(jù)集存儲(chǔ)代價(jià)最小化問題，通過與傳統(tǒng)方法對(duì)比分析，設(shè)計(jì)出優(yōu)化算法并進(jìn)行了數(shù)學(xué)證明，但該算法缺乏實(shí)驗(yàn)數(shù)據(jù)支撐，下一步將致力于對(duì)算法的實(shí)踐驗(yàn)證。