云環(huán)境下中間數(shù)據集存儲問題代價最小化算法研究

王瑩瑩 汪靜 涂韜

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

關鍵詞：中間數(shù)據集;存儲策略;代價最小化;云計算

DOI：10.11907/rjdk.192165

中圖分類號：TP312 文獻標識碼：A 文章編號：1672-7800（2019）012-0118-04

0引言

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

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

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

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

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

1.1算法概述

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

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

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

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

算法偽代碼如下所示。

算法：Linear_CTT-sP

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

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

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

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

3.建邊e

4.邊權值初始化為O

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

6.計算di和dk間邊的權值

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

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

1.2算法不足之處

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

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

2.1算法概述

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

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

2.4算法不足之處

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

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

3結語

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