多云工作流优化传输费用的数据布局策略

马飞

摘要：科学工作流应用是一种复杂且数据密集型的应用，常应用于结构生物学、高能物理学和神经学等涉及分布式数据源的学科。数据分散存储在基于互联网的云计算平台上，致使科学工作流在执行时伴随着大量的数据传输。云计算是一种按使用量付费的模式，数据传输产生传输费用，尤其在多个工作流相互协同的情况下，将产生更高的传输成本。该文从全局的角度建立基于多工作流数据依赖图的传输成本模型，研究基于二进制粒子群算法（BPSO）的数据布局优化策略，从而减少对云计算传输资源的租赁费用。

关键词：云计算；工作流系统；云工作流；数据布局；二进制粒子群算法

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2014）10-2418-03

Abstract：Scientific workflow is a complex and data-intensive application. It often used in disciplines related to distributed data sources， such as structural biology， highenergy physics and neurology. Data distribute in Internet-based cloud computing platform， resulting in transferring mass of data by scientific workflow running.Because cloud computing is a pay-per-use model，so data transfer costs incurred.Especiallyin the case of multiplecooperative workflows， datatransmissionwill produce higher costs.Firstly， this paper based on multiple workflow data dependence graphestablish transmissioncost model. Secondly， this paperproposed anew particle swarm optimization-based strategy for cost-effective data layout in multiple scientific cloud workflows.The experimental results show that the strategy is much better than its traditional counterparts.

Key words： cloud computing；workflow system；cloud workflow；data layout；binary particle swarm optimization algorithm

1 概述

科学工作流应用是一种复杂且数据密集型的应用，常应用于结构生物学、高能物理学和神经学等涉及分布式数据源的学科，这些学科通常都要处理海量的数据。因此，科学工作流的数据的表示和结构值得深入研究[1]。随着科学工作流的发展，越来越多的科学工作流研究者认识到在云环境中运行科学工作流比在其他分布式等环境中有更好的成本效益[2-3]。

云计算技术的出现提供了一种新的方式来部署科学工作流，云计算是分布式计算的新范式，以付费的方式向用户提供基础设施、平台和软件等服务[4-5]。当前已有一些部署在云计算环境上科学工作流项目，例如Nimbus[6]和Cumulus[7]项目。Deelman等人[8]提出云计算能为科学工作流提供一个十分经济的部署方案[9]。此外，云计算基于互联网Internet，因此全世界的科学家可以通过云计算在一起进行研究、分享数据。当科学工作流在执行任务时，需要将分布在互联网上不在本地的数据集传输到本地才能进行相应的计算，因云计算环境以付费的方式提供存储、传输、计算等服务，所以云计算环境下的工作流在执行过程中因会产生大量的传输费用，如何减少传输费用则成为了一个在云计算环境下部署科学工作流的挑战。

本文将提出一种基于二进制粒子群算法的多工作流数据布局策略，在全面考虑数据集大小，数据集之间的依赖关系，网络间的传输价格的基础，通过二进制粒子群算法对多工作流的数据布局进行优化，优化多工作流的传输成本。

2 相关工作

科学工作流的数据集按照来源可分为输入数据集和生成数据集，输入数据集作为工作流任务的输入，生成数据集作为工作流任务的输出，然后该生成数据集又作为另一个工作流任务的输入，所以工作流数据集之间存在着非常重要的依赖关系[10]。当前已有一些有关云计算环境下的数据布局研究，例如Google File System[11]和Hadoop[12]，都对用户隐藏了存储数据的基础设施，数据在Google File System或Hadoop系统内部的数据中心上移动不会产生费用，但是云计算环境下的科学工作流主要应用与跨学科的科学研究，意味着存在多个分布式的应用程序分布在不同的数据中心上执行，不同学科的数据在云环境下存放的位置也将不同。科学工作流在云计算环境下执行时，将会产生大量的数据移动，也将会产生很多的时间消耗以及大量的传输成本，所以通过合理科学的数据布局则显得尤为重要。

文献[13]提出了一种减少数据集移动次数的数据布局策略，利用BEA算法对数据集之间的依赖矩阵进行聚类变换，再根据聚类变换得到的聚类矩阵进行K均值聚类划分得到数据局的布局方案。文献[14]提出了一种包含3个阶段的降低移动数据集传输时间的数据布局策略，但是减少移动数据集次数，降低移动数据集的传输时间并不代表降低传输成本，因为每次传输的数据集大小的不同，不同的数据中心之间的传输价格不同，导致传输的成本不同， 文献[15]提出了一种基于粒子群算法的启发算法来降低工作流执行的传输费用和计算费用的总和，该算法主要分为2个阶段，首先根据粒子群算法对数据集进行布局，接着任务调度算法根据粒子群算法提供的数据布局对工作流的任务进行调度，该算法在降低工作流执行的传输费用和计算费用总和的基础上，在均衡数据中心的负载，加快收敛速度等方面都有很好的效果。当多个工作流相互协同工作时，文献[15]仅从单个工作流的局部角度考虑降低工作流的传输成本和计算成本并没有从全局角度考虑。

3 多工作流数据布局问题建模

本节将对云计算环境下多科学工作流应用的数据布局问题的相关概念进行建模，具体包括云计算数据库、科学工作流应用、单次数据传输成本和全局数据传输成本.

定义1：在数据中心集合[DC=j=1，2，..，|DC|dcj]已知的云计算环境中，[G1]表示一个科学工作流，集合[DS=i=1，2，..，ndsi]表示多个工作流系统[MWS=G1，G2，…，Gn]中的数据集合。多个工作流系统[MWS]的数据布局可表示为[Mmulti=i=1，2，…，|DS|di→dcj]。对[?di∈DS]，存在唯一[dcj∈DC]与之对应。

定义2：在数据布局[Mmulti]中，单个任务[Tj]执行时的传输成本为：

[CostMmultiTj=mindck∈DCdi∈Tj.IDSCostdi ， Mmultidi，dck] （1）

其中[di]为任务[Tj]的输入数据集，[Tj.IDS]表示[Tj]的所有输入数据集，[Mmultidi]表示数据集[di]在数据布局[Mmulti]中的存放位置，[Costdi ， Mmultidi，dck]表示数据集[di]从布局位置[Mmultidi]传输到数据中心[dck]的费用。

定义3：多个工作流系统[MWS]在数据布局[Mmulti]中的全局传输费用为：

其中[Gi]表示多工作流系统[MWS]中编号为i的工作流，[Vi]表示工作流[Gi]中的所有任务。

4 基于BPSO的数据布局策略

本节提出了一个包含2个算法的数据布局策略，文献[16]所示的BPSO算法被CDP（Cost-effective Data placement）算法调用。BPSO算法对数据集和数据中心进行编码，并产生数据集和数据中心的映射。根据第3章的公式1和2计算全局传输费用。最后返回传输费用最小的数据布局方案。CDP算法根据返回的结果找到所有工作流的最优数据布局方案。

初始化设置输入数据集都准备好的任务队列[ExTask]为空（输入数据集都准备好的任务指该任务所需的输入数据集都布局好的任务），待调度的任务集合[SchTask]为空，设置待布局的数据集合[placeDS]为空，步骤3-14，遍历工作流系统[MWS=G1，G2，…，Gn]中的每一个工作流[Gi]，从[Gi]中获取工作流的第一个任务节点[t]，加入队列[ExTask]中，当[ExTask]不为空进入循环，从队列[ExTask]获取一个任务节点[t']，将[t']加入集合[SchTask]中，并将[t']的后继任务都加入队列[ExTask]中，获取[t']的输入数据集合[inputDS]和输出数据集合[outputDS]，将其加入待布局数据集合[placeDS]中，调用[BPSO]，对[placeDS]中的数据集进行布局。

5 实验评价

本节将本文的全局数据布局策略和传统的局部数据布局策略进行对比试验，从2个方面阐述全局数据布局策略的优越性，我们将随机生成多工作流模型进行数据布局，然后记录上述2种数据布局策略的传输费用，进行对比评价。下图均是进行100组实验的平均结果。

图1所示是在数据集大小在700MB-800MB，数据中心个数为4，共享数据集百分比为30%的情况下随着数据集个数的增加，传统算法和本文算法的传输费用的变化趋势。可见本文算法的效果明显优于传统算法，随着数据集个数的增加差距越来越明显。

图2所示为在数据中心个数为4，和共享数据集百分比为25%的情况下的实验结果。可以发现，随着数据集大小的增加，传统算法和本文算法的传输成本都呈现上升的趋势。但本文算法比传统算法的传输成本低，且随着数据集大小的增加越来越低。

6 结论

云工作流数据布局问题关乎云工作流发展的核心问题。该文将提出的基于二进制粒子群算法的多工作流数据布局策略，在全面考虑数据集大小，数据集之间的依赖关系，网络间的传输价格的基础，通过二进制粒子群算法对多工作流的数据布局进行优化，优化多工作流的传输成本。

参考文献：

[1] Gil Y.Examining the challenges of scientific workflows. Ieee computer， 2007，40（12）： 26-34.

[2] Adams I F.Maximizing efficiency by trading storage for computation[C].Proceedings of the 2009 conference on Hot topics in cloud computing，2009.

[3] Yuan D，et al. A cost-effective strategy for intermediate data storage in scientific cloud workflow systems. in Parallel & Distributed Processing （IPDPS）[C].2010 IEEE International Symposium 2010.

[4] Fox A，et al.Above the clouds： A Berkeley view of cloud computing. Dept. Electrical Eng. and Comput. Sciences， University of California， Berkeley， Rep. UCB/EECS， 2009. 28： 13.

[5] Buyya R，Pandey S，Vecchiola C.Cloudbus toolkit for market-oriented cloud computing[J].Cloud Computing. 2009：24-44.

[6] Keahey K，et al. Science clouds： Early experiences in cloud computing for scientific applications[J].Cloud computing and applications， 2008：825-830.

[7] Wang L， et al. Scientific Cloud Computing： Early Definition and Experience[J].HPCC，2008.

[8] Deelman E， et al. The cost of doing science on the cloud： the montage example[C].Proceedings of the 2008 ACM/IEEE conference on Supercomputing. 2008.

[9] Hoffa C，et al. On the use of cloud computing for scientific workflow[C].eScience， 2008. eScience'08. IEEE Fourth International Conference on. 2008.

[10] Simmhan Y L， B. Plale， D. Gannon.A survey of data provenance in e-science[C].ACM Sigmod Record， 2005，34（3）： 31-36.

[11] Ghemawat S，H. Gobioff， S.-T. Leung. The Google file system[J].ACM SIGOPS Operating Systems Review，2003.

[12] White T.Hadoop： The Definitive Guide： The Definitive Guide[J].2009： O'Reilly Media.

[13] Yuan D，et al.A data placement strategy in scientific cloud workflows[J].Future Generation Computer Systems， 2010，26（8）： 1200-1214.

[14] 郑湃.云计算环境下面向数据密集型应用的数据布局策略与方法[J].计算机学报， 2010，33（8）：1472-1480.

[15] Pandey S，et al.A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments. in Advanced Information Networking and Applications （AINA） [C].2010 24th IEEE International Conference on. 2010.

[16] Kennedy J，R C Eberhart. A discrete binary version of the particle swarm algorithm[C].Systems， Man， and Cybernetics， 1997. Computational Cybernetics and Simulation， 1997 IEEE International Conference on. 1997. IEEE.