混合云环境下成本与隐私感知的工作流调度方法

文一凭,王志斌, 刘建勋, 许小龙, 陈爱民,曹步清

(1.湖南科技大学 知识处理与网络化制造湖南省普通高校重点实验室,湖南 湘潭 411201；2.南京信息工程大学 计算机与软件学院,江苏 南京 210044；3.湘潭市大数据和产业创新发展中心,湖南 湘潭 411000)

0 引言

近年来，随着云计算技术的深入发展与大数据时代的到来，云计算正成为一种新的社会基础设施。从云平台的用途和工作方式看，云可分为公有云、私有云和混合云等类型。公有云由云计算服务提供商提供服务；私有云由企业或组织内部构建、维护和使用，在可控性和数据安全等方面更符合组织要求。但是，处理大规模的数据往往需要大量的计算资源，如果根据企业或组织的峰值应用需求配置私有云中的资源，将导致巨大的资源效费比，即资源利用率低而成本显著增加。因此，可整合公用云与私有云资源的混合云具有灵活性和成本相对适中等方面的优势，正日益受到企业与组织的青睐，越来越多的企业或组织应用混合云技术部署系统。RightScale近年来的云计算行业状况调研报告显示，混合云已成为用户首选。

云工作流调度是映射并管理一组相互依赖的任务在云资源中执行的过程。在混合云环境下，不同的公用云可提供不同类型与价格的云资源服务，私有云与公用云中的资源均可用于执行工作流任务，但这些资源分属于不同的安全与管理域，需要综合考虑与任务执行相关的可用时间、隐私数据保护、费用限制等问题，这对云工作流调度研究提出了新的要求。

为此，本文在现有云工作流调度研究的基础上，进一步考虑了在由私有云与多个公用云构成的混合云环境下，如何在满足用户对工作流截止时间与隐私保护需求的前提下，优化工作流执行费用。

1 相关研究

任务调度对云计算系统至关重要，且一直是云计算领域的研究热点之一，文献[1]对此进行了综述。近年来，混合云已逐渐成为云计算的主要使用形式，亚马逊、微软、IBM、VMware等国际知名IT企业纷纷推出了一系列混合云管理产品，混合云环境下的任务调度研究也吸引了越来越多学者的关注。目前，国内外学者已从不同角度展开了一些研究。文献[2]研究了在混合云环境下，如何根据服务质量约束及成本等因素将应用分配到私有云或者公有云中的在线任务调度策略。文献[3]研究了混合云环境下任务执行时间的预测问题，并基于排队论提出一种可提高私有云的利用率并减少混合云中执行成本的任务调度方法。文献[4]考虑了混合云环境下资源的异构性与任务的类型差异(I/O密集型任务与计算密集型任务)等特点，提出一种自适应调度策略。在此基础上，文献[5]从如何保证软件性能与可靠性的角度提出一种混合云环境下的自适应任务调度策略。

但是，关于混合云环境下的工作流调度研究目前相对较少，文献[6]针对混合云环境下持续提交的多个科学工作流应用，提出一个截止时间约束的科学工作流在线调度方法。该方法首先判断现有私有云中的资源是否可在满足截止时间约束的前提下执行工作流应用，如果不能，则选择价格最合适的公有云提供商来执行该工作流应用，以减少云资源的租赁成本。文献[7]考虑了执行科学工作流时的数据放置问题，并提出一种混合云环境下数据感知的科学工作流调度方法。该方法首先应用遗传算法以确定数据集的放置位置，然后根据任务的执行约束(如截止时间与所需要的中间数据存储空间)将其分配到私有云或公有云中执行。文献[8]提出一种混合云环境下工作流调度成本优化方法。该方法首先利用私有云中的资源生成一个初始调度方案，然后对该方案进行调整，为部分任务分配合适的公有云资源，以满足截止时间约束。但是，以上研究均未考虑混合云环境下工作流调度的安全需求。

安全是云计算与工作流应用的关键问题之一。文献[9]考虑了云计算环境下的安全需求及科学工作流应用中数据密集型、计算密集型与内存密集型任务的特点，提出一种安全与成本感知的科学工作流调度方法。文献[10]提出一种安全与成本预算感知的调度方法，该方法可在安全与成本预算约束下，最小化工作流完工时间。但是，这些研究均未考虑在混合云环境下调度工作流时的隐私保护需求，而私有云中的部分工作流任务可能涉及大量关于用户的健康、财务等的隐私信息，如果这些任务被转移到公有云中执行，相关隐私数据将存在被泄露的风险。因此，有必要在工作流调度时考虑相关的隐私保护约束。文献[11]考虑了大数据应用中任务在执行时与云数据中心相关的隐私保护约束，并提出一个多目标云工作流调度方法。文献[12]针对云工作流执行过程中的用户隐私保护需求，在粒子群优化算法及模拟退火智能优化算法的基础上，提出一种具有隐私与云资源使用成本感知能力的云工作流调度方法。但是，这两种方法不适用于混合云计算环境下的工作流调度。而且，这两种方法仅考虑了单个工作流内单个任务的隐私保护需求，并未考虑涉及同一工作流内或者不同工作流之间的多个任务的隐私保护需求，即单个任务不包含隐私数据，但将多个任务的相关数据合并后将包含隐私信息，若这些任务由同一公有云服务提供者执行将存在隐私暴露风险。为此，本文基于上述研究，进一步探讨了混合云环境下，如何实现考虑隐私暴露风险与截止时间约束的工作流调度成本优化方法。

2 问题描述

本文主要研究多个工作流在混合云环境下执行的过程中，如何在满足工作流截止时间和隐私保护需求的双重约束条件下，最小化所有工作流的执行成本的问题。为方便问题描述，首先对目标系统的模型进行描述，然后给出了本文所采用的隐私保护需求、完成时间以及执行成本模型。

2.1 系统模型

定义1一组工作流应用。一组工作流应用可用二元组WAS=(WS,PDSS)进行描述，其中：

(1)WS={W1,W2,…,Wi,…,Wn}为工作流应用集合。Wi为第i个工作流应用，Wi=(Ti,CEi,DEi,Di)，其中：Ti为一组工作流任务的集合，Ti={tij|tij=Iij,Wij,Oij}，Iij、Oij分别为任务tij的输入与输出数据集，Wij描述了任务tij的计算量大小；CEi为一组有向边的集合，用以描述工作流任务间的控制流依赖情况，CEi={tia,tib|tia,tib∈Ti×Ti}；DEi为工作流任务间传递数据的集合，DEi={dei,ab|tia,tib∈CEi},其中dei,ab为任务tia向tib传递的数据量大小；Di为工作流的截止时间。

(2)PDSS是与工作流应用中涉及的一组数据组合的隐私敏感度声明，PDSS={pdsr|pdsr=PDCr,svr,ivr}，其中：PDCr={pdr1,pdr2,…,pdrq}(q≥1)是涉及隐私信息的一个数据组合，其可能与一个或多个工作流任务相关；svr∈(0,1]表示PDCr的敏感程度，svr越大，表示敏感度越高；ivr∈(0,1]表示PDCr的影响程度，即确定特定用户个体的可能性程度，ivr=1则表示可以完全确定。

定义2一组云服务提供者。混合云环境中的一组云服务提供者可以描述为PROVIDER={providerm|providerm=VMm,tvm}，其中：

(1)tvm∈[0,1]为云服务提供者providerm所能达到的信誉度。具体可根据其所能满足用户隐私保护需求的能力等指标来计算，不在本文考虑范围之内。

(2)VMn表示服务提供者所提供的一组预定义虚拟机类型组合，VMm={vmm,k|vmm,k=cpm,k,cm,k,cm,k,ctm,k}，其中：cpm,k表示虚拟机的计算能力；cm,k表示虚拟机单位时间内的收费;ctm,k表示虚拟机的计价时间单元，单位：min。

此外，本文约定provider1为私有云服务提供者，其他providerm(m>1)则为公有云服务提供者。各服务提供者之间的通信带宽与传输价格用矩阵BW与TC表示，其中：BWab(1≤a≤M,1≤b≤M)表示providera与providerb之间的通信带宽，单位：MB/S；TCab(1≤a≤M,1≤b≤M)表示providera与providerb之间的传输价格，单位：$/MB。

2.2 隐私保护需求模型

隐私保护需求可分为单个任务执行时的隐私保护需求和多个任务执行时的隐私保护需求。单个任务执行时的隐私保护需求可表示为SP：T×PROVIDER→{0,1}，其中T={T1,T2,…,Ti,…,Tn}为所有工作流任务的集合；矩阵SP代表工作流中任务到云服务提供者的一个有效映射，如其中元素SPij,m=1，则表示任务tij中存在隐私数据需交由云服务提供者providerm中的虚拟机进行处理。

多任务执行时的隐私保护需求主要为避免将多个任务的相关数据合并后，将包含隐私信息，而这些任务若由同一公有云服务提供者执行，将存在一定的隐私暴露风险，若风险值高于提前设定的阈值，需要将这些任务分散给多个公有云服务提供者执行。

多个任务由同一公有云服务提供者执行时的隐私暴露风险可以表示为：

(1)

式中D(nt)为任务组合nt的数据项集。

2.3 工作流完成时间计算模型

假设tib是一个被类型为vmm,k的虚拟机执行的任务，ST(tib)为tib的开始时间，ET(tib)为tib的结束时间，分别表示为：

Twait(tia,tib)}+WTib，

(2)

ET(tib)=ST(tib)+Wib/cpm,k。

(3)

其中：WTib为tib处于等待状态的时间，当任务被分配的虚拟机正在执行其他任务时，任务将进入等待状态；Twait(tia,tib)为tia向tib传输数据所需的时间，

Twait(tia,tib)=dei,ab/BWcm。

(4)

式中tia由服务提供者providerc执行。

综上所述，工作流Wi的完成时间

makespani=ET(ti,exit)。

(5)

2.4 云资源使用成本模型

工作流任务tij的执行成本主要包括计算成本和传输成本两部分，可以表示为：

costij=costij,com+costij,tran。

(6)

在混合云环境中，按照公有云服务提供者的定价方式，一台类型为vmm,k的虚拟机执行任务tij的计算成本

costij,com=Trent(vmm,k,tij)/ctm,k×cm,k。

(7)

式中Trent(vmm,k,tij)表示任务tij租用类型为vmm,k的虚拟机时间。任务tij的传输成本只考虑tij接受其前驱任务集pre(tij)中任务的传输数据时产生的花费，可以表示为：

(8)

式中tia为tij的前驱任务且它由云服务提供者providerc执行。

因此，执行工作流所需云资源使用成本可以表示为：

(9)

3 隐私与成本感知的云工作流调度算法

在混合云环境下，任务在私有云中执行能够减少云资源使用成本及隐私暴露风险，但由于私有云资源有限，所有任务均交由私有云执行可能导致工作流的完成时间超出截止时间限制。为此，本文提出一种混合云环境下成本与隐私感知的工作流调度算法(Cost-aware and Privacy-aware workflow scheduling strategy in Hybrid Clouds，CPHC)，该算法的基本思想是根据截止时间与隐私保护需求的约束，将尽可能多的工作流任务分配到私有云中执行，从而降低工作流的执行成本。算法1描述了该算法的主要步骤。

算法1CPHC。

输入:SP:Privacy protection requirements，UT:The upper threshold of privacy exposure risk，VM:virtual machine resources，WS:Set of workflow applications，T:Set of tasks of WS；

输出:Resource scheduling policy。

1:schedule T to the private cloud;

2:foreach workflowWiin WS

3: calculate makespaniby Eq.(5);

4:end for

5:while∃WiinWSsatisfyingmakespani>Dido

6: select txwith max waiting time from T;

7: set the available public providers APxof task txaccording to SP;

8: foreach VM typein APx

9: calculate costxby Eq.(6);

10: end for

11: choose the VM type vmxwith lowest costxfrom APx, and assign it to tx;

12: nt=all the tasks which have the same service provider as tx;

13: while crisk(nt, providernt)>UT do

14: select tywith minimum workload and Size of(APy)>1 from nt;

15: APy= APy-{providery};

16: foreach VM typein APy

17: calculate costyby Eq.(6);

18: end for

19: choose the VM type vmywith the lowest costyfrom APy, and assign it to ty;

20: nt=all the tasks which have the same service provider as ty;

21: end while

22: recalculate each makespaniof WS by Eq.(5);

23:end while

算法1具体步骤描述如下：

步骤1(语句1～4)将所有任务按就绪的顺序分配到私有云当前可用资源中计算能力最强的虚拟机中执行。若任务就绪但无可用私有云资源分配，则进入等待状态直到资源可用。任务分配完成后计算各个工作流的完成时间。

步骤2(语句5)若任意工作流完成时间超过其截止时间，则不断执行循环体。

步骤3(语句6～7)从分配到私有云的任务中挑选出等待时间最长的任务tx，并根据其单个任务隐私保护需求设置tx的可分配公有云的范围APx。假设云环境中存在3个公有云providera，providerb，providerc，任务tx的单个任务隐私保护需求限制不能由providera执行，则tx的可分配公有云的范围为providerb和providerc。

步骤4(语句8～11)根据式(6)计算APx中各个虚拟机类型执行任务的执行成本，并从中选择出执行tx成本最少的虚拟机类型vmx分配给tx。

步骤5(语句12～13)找出与任务有相同云服务提供者的任务集合nt并计算其隐私信息暴露风险，若隐私信息暴露风险高于阈值UT则不断执行循环体。

步骤6(语句14～20)从nt中选取工作量最少且可分配公有云范围大于1的任务并重新设定其可分配公有云的范围。然后，再次执行步骤4和步骤5的过程，对选定的任务进行重新分配。

步骤7(语句22)按照当前资源分配方案，重新计算各工作流的完成时间。将多个工作流应用按就绪顺序调度到资源有限的私有云时，每个工作流应用执行过程中可能存在其他工作流任务优先执行。因此，当任意任务的资源分配方案发生变化，所有工作流完成时间需重新计算。

4 仿真实验

4.1 实验参数设置

为分析和评估隐私与成本感知算法的性能。本文在CloudSim[13]平台上参照Amazon EC2[14]、Microsoft Azure[15]、Google Compute Engine[16]中的按需实例，设置了3个公有云服务、共15种不同类型的虚拟机实例进行仿真实验，详细参数如表1～表3所示。本文还设置了1个私有云服务，其中包括6个计算核心为1的虚拟机以及4个计算核心为2的虚拟机。此外，本文采用的工作流任务的工作量服从范围[10 000,50 000]MFLOPS(每秒百万浮点指令)的均匀分布；输出数据的大小均匀分布范围为[10,100]MB；

表1 公有云服务1虚拟机实例参数设置

表2 公有云服务2虚拟机实例参数设置

表3 公有云服务3虚拟机实例参数设置

本文仿真采用以下3个算法来计算工作流的执行成本：

(1)PSO算法 本文对比著名的粒子群优化算法[17](Particle Swarm Optimization, PSO)。在粒子群优化算法迭代过程中，本文定义加速系数φ1=φ2=2.05；惯性系数ω=0.5；粒子的数量为50；算法迭代次数为500；粒子编码参考文献[12]中的方法；限制条件与本文相同。

(2)CPHC算法 本文提出的成本感知算法，目的是在满足工作流截止时间和隐私保护需求的约束下，最小化工作流执行花费。

(3)CHC算法 本文提出的CPHC算法考虑了隐私保护需求，并可有效处理隐私保护约束。为评价隐私保护需求对CPHC算法性能的影响，将该算法中隐私保护约束相关的处理逻辑去除后，得到CHC算法。

4.2 对比实验结果

如图1所示为在工作流截止时间变化的条件下，CPHC算法与PSO算法的性能比较实验结果。由图1a易知，随着截止时间的增大，两个算法的工作流执行成本逐渐减小，当截止时间超过一定值时趋于平缓。这是因为当截止时间较低时，较多任务需要被分配到计算能力更强的公有云中执行才能满足截止条件，导致执行工作流所需成本增高。

图1b为两算法隐私暴露风险对比，隐私暴露风险上限阈值设置为6。从结果可以看出，两算法均能满足隐私暴露风险阈值限制，且CPHC算法所调度的工作流隐私暴露风险小于PSO算法。这是因为CPHC算法尽可能将最多的工作流任务交由私有云服务执行，减少了由公有云服务执行任务时产生的隐私暴露风险。

如图2所示为在工作流截止时间变化的条件下，考虑隐私保护需求对CPHC算法的影响。从图2a可以看出，当截止时间小于一定值时，在相同参数设置下CHC算法的执行成本小于CPHC算法。当截止时间大于一定值时，所有任务在私有云执行，隐私保护需求对算法无影响。

图2b为考虑隐私保护需求对算法执行时间的影响，可以看出CHC算法的运行时间在截止时间低于一定值时低于CPHC算法，这是因为在时间较少时，大量任务被分配到公有云资源导致违反多任务隐私保护需求的任务增多，算法需要进行重新调度导致运行时间增加。

5 结束语

针对现有云工作流调度方法未考虑涉及同一工作流内或者不同工作流之间的多个任务的隐私保护需求的不足，本文在前期研究工作的基础上，建立了混合云环境下成本与隐私感知的工作流调度模型，并设计了一种具有成本与隐私感知能力的调度方法CPHC。通过在CloudSim平台上进行模拟实验，验证了该方法在执行成本、隐私暴露风险、运行时间等方面均优于所对比的PSO算法。但是，该方法仅考虑了云用户的需求，并未考虑云提供商的运营成本等需求。因此，在今后的工作中，将结合涉及多云数据中心的能耗优化研究以进一步研究工作流调度问题。