国云计算网描述云计算^[1]是一种集并行处理、网格计算和分布式处理等概念的新型计算，或是集并行处理、网格计算和分布式处理等概念的具体化、商业化形式.它伸缩性强，可靠性高并且廉价，能够为用户提供存储、服务器、应用等大量的IT资源.工作流^[2-3]指业务过程的部分或整体在计算机应用环境下的自动化，利用计算机将所有参与者之间遵循某种特定的规则自动传递信息，是一种抽象的流程操作步骤的描述.

随着云计算和工作流的不断发展，越来越多的研究事实证明了将两者结合应用具有广泛前景，将工作流部署到“云”上^[4-5]既能控制成本又能大大提高效率.然而，例如应急监控管理、供应链管理等流程业务通常具有大量工作流并发执行和隐私数据存在的特点.众所周知，大数据时代的到来使得隐私数据越来越被用户所重视，工作流实例在一般的云环境下，客户的隐私数据不能够得到很好的保护.显而易见，怎样最优地存放这些数据，以及在任务执行时怎样减少数据传输时间成为了云工作流发展的阻碍.为此，云计算环境下的工作流应用不仅要考虑到非隐私数据的分配布局，更要考虑到包括商业机密、个人信息等在内的隐私数据的布局.

“云”可以由“公有云”和“私有云”共同组成^[6]，如果将隐私数据存放在私有云中，那么数据的安全性得以保证.但是在工作流执行任务的时候，需要将分布在云端的数据集传输到本地才能进行计算，这必然会产生大量的数据传输时间.于是，一个问题由此而生，怎么样最大限度地减少传输时间呢？本文将就该问题进行研究阐述.

本节主要简述了几种目前关于工作流数据分配的方法.在硬件层面上Hardavellas等人^[7]提出了依靠减少数据访问延迟的方法来减少访问时间.Cope等人^[8]则从任务对资源的平衡角度考虑，解决了在应急计算环境下的工作流数据分配问题.值得一提的是，Pegasus工作流系统^[9]是预先调度数据到执行该任务的计算资源上，然后在执行过程中不断地删除无用数据，减少存储使用量，可惜略有不足的是该策略较少地考虑隐私数据的存放.

山东大学以降低数据移动传输时间为主要目的，提出了三阶段的布局策略^[10]，第一阶段利用遗传算法得到降低跨节点的数据传输时间的数据分配方法，第二、第三阶段从数据依赖和负载均衡的角度依次过滤出最优的方案.国外也有些人就科学工作流的数据布局问题^[11-13]提出了不少解决方案，例如基于K-Means算法的数据分配策略等，该策略主要运用到了键能算法对数据集之间进行聚类变换，然后再进行聚类划分，最后根据划分结果调整数据到依赖程度最高的节点上，达到减少了数据传输的目的.

张鹏等人^[14]给出崭新的“云端+客户端”的工作流架构，该架构的优势在于能够依据数据的隐私性分别将数据存放在客户端和云端，同时在任务执行时动态地调整数据分布以减少数据传输时间.但实验表明，传输时间仍然可以进一步减少.

可以考虑下面一个场景.换季之前，某较大规模服装公司的服饰门面准备上架换新.首先，市场调研部门要进行市场调研，根据该公司门面在不同地域的分布情况，以及不同地域的往年销售和不同样式服装的人群消费倾向得出调研报告; 然后根据调研报告制定上市计划，若仓库里有足够的上架服饰，那么运输部门直接运送到门店，否则采购部门就要制定采购计划进行补货; 再由运输部门将采购物资运输到各个服装门店，整个工作流程如图 1所示^[14].此时，应当考虑2个问题.

图 1(Figure 1)

图 1 数据存放的挑战 Figure 1 The data placement challenges

第1个问题是隐私数据的存放.在进行采购的过程中，采购部门是根据调研报告来进行采购的，报告中必然存在包括被调研群众的个人信息、消费习惯等在内的隐私数据，这些数据绝大多数情况下是服装公司不愿意被别人所知道的商业机密.然而，在工作流程的执行过程中，若将这些数据全部输入到公有云数据中心，则有可能会造成隐私数据的泄露.

第2个问题是怎样最大限度地减少数据在数据中心之间传输的时间.调研部门的工作结束后，根据investigation report输出listing plan，它被存放在数据中心1，仓库物资管理部门根据输出的调研报告分配服饰到门店，若不足则输出shopping order，该订货单被存放在数据中心3，并且运输部门工作流的delivery任务的启动需要调用listing plan和shopping order.但是该公司旗下有众多门店，运输部门势必需要在同一时间启动100次，甚至更高次数的运输工作流实例.因为在数据中心调度任务比数据自身盲目地向数据中心移动要简单快捷，所以在任务执行之前就要保证所需的输入数据在执行位置上.由上文可知，数据被存放在不同的数据中心，所以在工作流实例大量并发的情况下，必定会发生数据的跨数据中心传输，也就意味着产生大量时间花费.

针对以上两个问题，本文首先分析最常见的基于负载均衡划分模型的不足之处，以及工作流在云环境下的数据分配特点; 然后得出产生巨大数据传输时间开销的原因; 最后提出了一种混合公有云和私有云的多云环境下工作流数据分配方法，该方法能够根据隐私要求将数据分别存放在私有云数据中心和公有云数据中心，并且能够在保证工作流程完整性的同时有效减少任务执行时的数据传输时间.

根据上文的案例，给出一个工作流实例，如图 2所示.

图 2(Figure 2)

图 2 工作流实例 Figure 2 Workflow

定义1  工作流W=＜T, D＞，其中T表示所有任务的集合，即T={t₁, t₂, t₃, …, t_n}，D表示所有数据的集合，即D={d₁, d₂, d₃, …, d_n}.

定义2  数据中心集合C={C_prt， C_pub}，其中C_prt是私有云数据中心的集合，C_pub表示公有云数据中心的集合，每个数据中心可以表示为c_i, c_j∈ C.

定义3  协同关系.假设R为D×T的笛卡儿积，并且满足R={＜d, T＞|d∈T, D}，则称R为D到T上的协同关系，用R表示.

定义4  数据协同矩阵.已知D是数据集合，n是集合中单个数据的个数，T是任务集合，E是一个n×n阶矩阵，E=(e_ij)，其中

则称E为D与T的数据协同矩阵.引入公式(1):

其中T.d_i表示以d_i作为输入数据的任务集合，T.d_j表示以d_j作为输入数据的任务集合，T.d_i∩ T.d_j表示同时以d_i、d_j作为输入数据的任务集合，Count为计算它们的个数.

张鹏等人提出的在“云端+客户端”的工作流架构^[14]下的数据分配策略CCDP4WF可以这样描述：

(1) 依据式(1) 计算图 1中的每个T.d_n，T.d₁={ t₁, t₂}，T.d₂={t₂, t₃, t₄, t₅}，T.d₃={t₁, t₂}，T.d₄={t₃, t₄}，T.d₅={t₂, t₅, }，T.d₆={t₅, t₆}，然后得到数据协同矩阵，如图 3所示.

图 3(Figure 3)

图 3 建立数据协同矩阵 Figure 3 Building of data collaboration matrix

(2) 使用键能算法(BEA)交换行列转换数据协同矩阵，如图 4(a)所示.

图 4(Figure 4)

图 4 数据划分过程图 Figure 4 Data partitioning process

(3) 划分数据，其中划分点x通过式(2) 得到:

CU表示任务只用到矩阵中右下方数据块里面所有数据的次数，CL表示任务只用到矩阵的左上方数据块里面的所有数据的次数，CI表示任务同时用到矩阵的左上方和右下方数据块中全部数据的次数，易知划分点必在对角线上.例如，x₂=8×22－16=160为最大的x值，划分后的数据协同矩阵, 如图 4(b)所示.

(4) 将划分之后的数据块分别分配到不同的数据中心，得到数据分配方案.

通过上节对CCDP4WF策略的介绍之后，接下来本文将从工作流执行的初始阶段和运行阶段两方面来对数据分配方法进行描述和分析，提出一种新的基于数据协同破坏度的数据分配策略NDCDD.

定义5  将工作流描述W=＜T, D＞中的单个任务集用一个二元组表示，即t_i=＜I_i, O_i＞, i=1, 2, …,|C|，其中I_i为任务t_i需要用到的输入数据，O_i为任务t_i输出的数据.

定义6  将工作流描述W=＜T, D＞中数据集D的单个数据集用一个五元组表示, 即d_i=＜t_i, s_i, c_i, ptl_i, gt_i＞, i=1, 2, …,|c|.其中，t_i表示用到数据集d_i的任务集，s_i表示d_i的大小，c_i表示d_i存放在数据中心c_i上，ptl_i表示d_i是否为隐私数据，若d_i为非隐私数据，则ptl_i=0，若d_i为隐私数据，则ptl_i=!0，gt_i表示生成的数据集的个数，若gt_i=0, 则表示该数据集是初始数据集，由本地输入，若gt_i=!0，则表示为生成数据集.

定义7  将私有云数据中心表示成一个二元组，即

c_k=＜size, availisize＞, k=1, 2, …,|C_prt|, 其中size表示存储空间原始容量值，availsize表示现在可用容量值.

定义8  定将工作流描述W=＜T, D＞的数据分配方案表示为AP=∩_{i=1, 2, …,|D|}{ d_i→ c_j }, 即∀d_i∈ D，存在唯一的c_j∈ C与之一一对应，AP(d_i)表示d_i数据集所对应的数据分配方案中数据中心的编号.

定义9  数据协同破坏度DCD_ij=Count(T.d_i∩ T.d_j), AP(d_i)≠AP(d_j)表示∀d_i, d_j ∈ D，其中Count(T.d_i∩ T.d_j)≠0，并且PM(d_i)≠PM(d_j)；若AP(d_i)=AP(d_j)，则DCD_ij=0.

初始阶段，在工作流部署到系统上的时候就需要对输入数据进行存放.首先同CCDP4WF策略一样，根据数据与任务之间的关联关系得到数据协同矩阵，并且划分为CU、CL、CI 3大数据块; 然后在此基础上提出一种新的基于数据协同破坏度的数据划分方法(DCDDP)来进行数据分配，改进之处在于该方法在聚类划分时以隐私数据集为中心，只划分非隐私数据.具体过程如下：

(1) 从图 4(a)中得到(d₁, d₂, d₃, d₄, d₅)的非隐私数据协同矩阵M₂，然后使用键能算法交换行列得到图 5非隐私数据协同矩阵M₃.

图 5(Figure 5)

图 5 非隐私数据协同划分矩阵 Figure 5 Partition of non-privacy data collaboration matrix

(2) 将c_k中的隐私数据d₆加入到M₃中，得到M₄，如图 6(a)所示.

图 6(Figure 6)

图 6 包含隐私数据的数据划分图 Figure 6 Data partition containing privacy data

(3) 划分新矩阵M₄.划分点H满足min H=∑CI_ij，表示数据集被划分为CU、CL时对工作流造成的数据协同破坏度的值，即认为同时使用CU、CL数据块中所有数据次数总和最小，如图 6(b)所示.

到运行阶段，就数据模型而言，该阶段的数据分配就是数据协同矩阵不断更新数值和划分块的过程，例如，当工作流任务运行到T₅的时候，d₆就不再为T₅所用，同时它产生的新数据d₇被T₆所用，这个时候数据集与任务集之间的协同关系发生了变化.然而在此过程中，有些私有云数据中心会因新数据集的添加而产生负载的现象.针对该问题，下文阐述了运行阶段的数据分配策略，具体过程如下：

(1) 假设d₆是生成数据集，T.d_n是需要用到数据集d_n的任务集，经过重新计算将d_n加入到新的全局数据协同矩阵M₁′中.

(2) 计算d_n与c_i的协同值dc_col_ni= $ \sum\nolimits_{{\mathit{d}_\mathit{j}} \in {\mathit{c}_\mathit{i}}} {{{\mathit{M'}}_{\mathit{nj}}}} $, i=1, 2, …，k, 然后将d_n分配到协同值最大的上c_i, , dc_col_nm=max_i=1^k(dc_col_ni).

(3) 当其中有私有云数据中心c_m的可用存储空间availsize已满，则删除无用的数据集，也就是在数据协同矩阵中消除已经完成的任务，然后再进行行列变换，最后按照上文介绍的初始阶段的数据分配方法来调整，输出分配方案AP.

根据上文的具体案例来分析，针对该案例的工作流实例，CCDP4WF算法把d₁、d₃放在同一个数据中心c₁上，即c₁={d₁, d₃}，把d₂, d₄, d₅, d₆放在数据中心c₂上，即c₂={d₂, d_4，d₅, d₆}.任务t₁、t₂在数据中心c₁上执行，t₂所需要的d₂、d₅在数据中心c₂上，此时必定产生传输时间为2的数据传输，任务t₃、t_4，、t₅在数据中心c₂上执行，所需数据全部位于本地，不会产生数据传输，数据分配如图 7所示.NDCDD算法则是把d₁、d₂、d₃、d₄、d₅成一个数据块，并放在数据中心c₁上，即c₁={d₁, d₂, d₃, d₄, d₅}，d₆单独作为一个数据块放在数据中心c₂上，即c₂={d₆}，那么t₆在数据中心c₂上执行，只有t₅需要从c₂上传输数据d₆，传输时间就只为1，数据分配如图 7所示.

图 7(Figure 7)

图 7 数据分配图 Figure 7 Data placement

显而易见，改进后的策略传输时间更少，因为CCDP4WF算法是先划分数据集，然后再对划分得到的数据块分配存放位置.而NDCDD算法是以隐私数据集为中心来聚类划分数据块，并且同时对数据块进行存放位置的分配.这样做的原因在于工作流执行任务时，假如只需要分别单独使用CU、CL中的数据时并不会产生数据传输，但在需要同时使用CU、CL中的数据时，就会出现数据传输，破坏数据关联度.所以NDCDD算法比CCDP4WF算法更加具有优越性.

本节将对本文提出的多云环境下一种新的基于数据协同破坏度的数据分配策略NDCDD与张鹏等人^[14]提出的CCDP4WF数据分配策略进行对比实验.

由于实验需要“公有云”和“私有云”共同组成的环境，在现实当中，“公有云”有AmazonEC2、IBM的Blue Cloud、Googel的AppEngine等都可以被使用，“私有云”多为企业或为客户单独构建，再者本文生成工作流数据的总大小不会异常庞大，可以在matlab上设置1个存储容量为1 TB的数据中心作为公有云，以及10个100 GB的数据中心作为私有云来进行仿真实验，其中实验环境为Intel(R)core(Tm)i5-3317uCPU1.70GHz RAM 4GB，硬盘500 GB，数据中心的传输带宽设为10 Mb/s.

为了验证实验结果的客观性，首先利用matlab随机生成20个服务工作流，建立任务集与数据集之间的协同关系; 然后再从改变输入数据集的数量、数据集的大小、隐私数据集的百分占比这3个方面进行实验.

如图 8所示，在隐私数据占比和数据集大小固定的情况下，由于数据集个数的不断增加会导致需要不断移动的数据集数量的增加，因而传输时间也会不断增加.所以，CCDP4WF算法下的数据传输仅在前期数据集数量较少时略快，但随着数量越来越大，其增长十分迅速.而NDCDD算法下的数据传输时间虽然也在不断增长，却在时间上一直小于前者，并且时间开销的增长幅度较为平缓，速度不快.特别是在输入数据集个数达到70的时候，本文算法的传输时间只有2 000 s多一点，而CCDP4WF算法的传输时间为6 500 s多，达到了3倍的差距，并且呈现显著增大趋势.

图 8(Figure 8)

图 8 改变数据集个数对传输时间的影响 Figure 8 Influence of changing the number of dataset on the transmission time

如图 9所示，保持输入数据集数量不变，增加输入数据集的大小，虽然传输的数据集的数量没有改变，但数据集不断变大造成负载增加，耗时也就随之增加了.图 9中可以看出两种策略下的数据传输时间都呈现缓慢增加现象，并且两者差距不是很大.但总的来说，本文提出的NDCDD算法下的时间开销要稍少于CCDP4WF算法.

图 9(Figure 9)

图 9 改变数据集大小对传输时间的影响 Figure 9 Influence of changing the size of dataset on the transmission time

如图 10所示，保持输入数据集数量和大小不变，不断增大隐私数据集的百分占比，可以看到两种策略下的传输时间呈明显上升趋势.这是因为隐私数据百分占比的增大意味着因受保护而无法移动的数据集越来越多，所以在执行任务时，非隐私数据就不得不频繁地在不同数据中心之间移动，这势必会产生大量的时间花销.从图 10中可以看出本文提出的NDCDD算法下的传输时间大大少于CCDP4WF算法，并且增幅速度相对比较缓慢，但是当隐私数据达到70%以上的时候，两者的传输时间在逐渐靠近.这是因为在隐私数据过多时，对本文以隐私数据为中心的分配方法而言数据隐私与否变得没有太大区别，体现不了优势.但在实际中是极少可能出现隐私数据占比如此之高的情况，故本文的算法在此方面仍然优于CCDP4WF算法.

图 10(Figure 10)

图 10 改变隐私数据占比对传输时间的影响 Figure 10 Influence of changing the private dataset rate on the transmission time

综上所述，对于大量并发工作流程在跨数据中心进行数据传输所花费的时间来说，在数据集大小较大的情况下，本文策略与CCDP4WF策略相差不大，优势表现不够明显.但在输入数据集不断增加，特别是隐私数据占百分比较大的情况下，本文策略就要明显优于张鹏等人提出的CCDP4WF策略，并且优势呈现不断扩大趋势.

本文分析了目前云计算与工作流结合应用的背景下存在的问题，阐述了国内外在此方面的一些研究进展与成果.以某公司的服饰上市的简单案例为应用场景，提出了一种在云计算环境下新的基于数据协同破坏度的工作流数据分配方法.通过一系列的对比实验证明了此方法的可行性与有效性.