云環境下中間數據集存儲問題代價最小化算法研究

王瑩瑩 汪靜 涂韜

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

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

DOI：10.11907/rjdk.192165

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

0引言

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

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

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

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

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

1.1算法概述

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

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

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

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

算法偽代碼如下所示。

算法：Linear_CTT-sP

輸入：開始節點ds;結束節點de;線性數據流的依賴圖

輸出：數據集序列

1.遍歷依賴圖中的每個數據集di

2.遍歷di的后續節點dj

3.建邊e

4.邊權值初始化為O

5.遍歷di和dj間所有節點dk

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

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

8.輸出最短路徑對應數據集狀態序列

1.2算法不足之處

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

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

2.1算法概述

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

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

2.4算法不足之處

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

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

3結語

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