第3章面向混合云的资源管理

3．1混合云环境下面向安全的科学工作流数据布局策略

在当今数字化时代，科学工作流已成为科学研究进程中处理大规模数据的重要手段。随着数据复杂度的不断增加，传统网络和集群环境的资源已不足以满足科学工作流的部署需求。相比之下，混合云计算拥有强大的计算和存储资源，为科学工作流的部署提供了一种理想化平台。然而，现有的混合云环境下的科学工作流数据布局策略通常将隐私数据固定存储，而没有充分考虑数据在分布式环境中的安全性。针对该问题，本节构建了一种混合云环境下面向数据安全的科学工作流数据布局模型，并提出安全等级分级机制，其考虑数据的安全需求和数据中心所能提供的安全服务，旨在确保数据隐私安全的同时最大程度降低数据传输时延。另外还提出了一种基于自适应粒子群优化算法(Adaptive Particle Swarm Optimization Algorithm based on SA and GA，SAGAPSO)的数据布局策略。SAGAPSO基于粒子群优化算法框架，在粒子更新操作中引入遗传算法的交叉和变异算子，提高了种群进化的多样性； 在全局最优粒子替换中引入模拟退火算法的Metropolitan准则，有效避免算法陷入局部极值。相关实验结果表明，本节提出的基于SAGAPSO的数据布局策略在满足数据安全需求的同时能够有效降低传输时延。

3．1．1引言

随着云计算技术的广泛应用，越来越多的云服务提供商推出了各种类型的云存储服务，以满足用户对数据存储和管理的需求。云存储服务的出现为科学工作流的执行提供了新的选择，用户可以将数据存储在云端，通过云计算平台进行数据处理和分析，从而提高数据的处理效率和灵活性。混合云作为一种新兴的云计算模式，将私有云和公有云结合起来，既能享受公有云的便利，又能保证私有数据的安全性，因此被越来越多的科学机构所采用。然而，在大规模数据处理中，数据安全问题一直是备受关注的焦点，科学工作流的正确执行依赖于数据的安全性。若数据丢失、泄露或被篡改，则会导致科学工作流中断、秘密信息泄露和错误的执行结果。在混合云环境下，数据存储和传输安全问题更为复杂。因此，如何在混合云环境下保证科学工作流的数据安全，成了一个亟待解决的问题。

针对隐私数据的保护，需要依靠安全技术和合理的管理策略。作为存储数据的重要场所之一，数据中心必须满足隐私数据的安全要求。然而，由于不同类型数据的安全需求不同，数据中心的安全级别应该根据其所能提供的安全服务进行分级，以为隐私数据提供更高的安全保障。目前，在数据中心建设方面，行业通常采用等级划分的方式来评估数据中心的整体性能。例如，美国Uptime Institute提出的等级分类系统将数据中心分为Tier Ⅰ、Tier Ⅱ、Tier Ⅲ和Tier Ⅳ四个等级，现已被广泛采用。在国内，GB 50174—2017根据数据中心的使用性质、数据丢失或网络中断所造成的损坏和影响程度将数据中心定义为A、B、C级。

然而，传统的数据布局策略通常将隐私数据固定存储在单一数据中心中，这会导致一些安全问题，如单点故障等。不同的数据具有不同的安全需求，而且一些敏感的隐私数据必须存储在更加安全的数据中心中。因此，本节采用安全等级分级机制来确定数据需要的安全需求和数据中心所能提供的安全服务。这种方法可以确保隐私数据被妥善地保护，同时也能够使数据中心在保护隐私数据的同时，充分利用资源，提高数据传输效率。另外，当隐私数据集使用固定存储策略时，由于数据存储位置的限制，科学工作流任务只能从固定的数据中心中获取数据进行计算，而这些数据中心可能会因为网络拥堵或服务器负载高导致计算时间变长，从而影响整个科学工作流的执行时间。而采用安全等级分级机制存储方法可以将隐私数据存储在不同的安全等级数据中心中，这样一方面可以减轻单个数据中心的压力，另一方面可以在不同的数据中心中并行计算，从而提高科学工作流的执行效率。科学工作流执行过程中通常需要进行数据传输和处理，而这些数据通常存储在不同的数据中心中，其传输速度受到网络带宽、数据大小和传输协议等因素的影响。因此，通过减少数据传输时间可以大大缩短科学工作流的执行时间。

本节的主要贡献如下： 

(1) 构建了一种混合云环境下面向数据安全的科学工作流数据布局模型，并分析了数据集的安全需求和数据中心所能提供的安全服务，提出了安全等级分级机制。

(2) 引入遗传算法的交叉算子和变异算子，在全局最优粒子替换中结合模拟退火算法的Metropolitan准则，有效避免粒子群算法陷入局部最优，提高了算法的收敛速度和全局最优解的精度。

(3) 考虑云间的带宽速度和数据中心的存储容量，设计了一种适用于本模型的基于SAGAPSO的数据布局策略，从全局角度优化数据传输时延。

3．1．2相关工作

近年来，随着云计算技术的普及和云计算强大的并行计算能力，许多科研工作者开始着手研究科学工作流在云计算环境下的数据布局问题，科学工作流数据布局策略的优劣直接影响到整个系统的作业性能。

在混合云环境下，科学工作流可能涉及多个数据中心或存储设备，有效管理数据传输对于整体性能至关重要。Deng等提出了一种多级Kcut图分割算法，他将数据根据其依赖关系不断切割成子图，之后布局到对应数据中心中，在满足负载平衡和固定数据集约束的同时，最小化跨数据中心的数据传输总量。Liu等考虑了数据的相关度，提出了基于相关度的两阶段数据放置策略。该策略在数据布局阶段将关系紧密的数据放在同一数据中心，将关系松散的数据放在不同数据中心，在任务执行时将任务调度到相关性最大的数据中心，从而减少了数据中心间的数据移动次数和数据传输量。Wang等提出了一种基于动态计算相关性(DCC)的数据放置策略。该策略将具有高DCC的数据集放置在同一个数据中心，并在运行时动态地将新生成的数据集分布到最合适的数据中心，有效减少数据中心之间的数据调度数量。Kim等则基于任务的依赖性提出了一种数据放置策略。在构建阶段，该策略将数据中心中的初始数据集进行分组，并在运行时将新生成的数据集布局到最合适的数据中心，可有效减少数据移动。Li等研究者通过创建一个基于工作流的数据定位模型，引入了一个分为两步的数据分布方案。这个方案利用离散粒子群优化技术动态地将数据指派给合适的数据中心，以此达到相比于传统的基于任务的数据定位策略更高的成本效益。Liu等提出了一种智能数据放置策略，考虑数据中心的计算能力、存储预算、数据项相关性等因素将整个数据集划分为小的数据项，并在多个数据中心进行布局，在运行中生成中间数据时，采用线性判别分析将其放置在适当的数据中心上，最小化由数据移动引起的通信开销。

然而，现有研究聚焦于降低数据传输次数、数据传输时间和代价开销，在数据安全保护方面考虑不足，随着数据间交互越来越多，传统隐私数据进行单一固定的数据存储方案越发具有局限性，因此，需要采取更加有效的措施来保护隐私数据在科学工作流中的安全传输和存储。

3．1．3问题模型

本小节具体介绍关于混合云环境下面向数据安全的科学工作流问题模型，其主要涉及科学工作流、混合云环境和数据布局器三种角色。图31展示了布局系统的框架图。



图31混合云环境下面向数据安全的科学工作流布局框架


1． 科学工作流

科学工作流可以用有向无环图G=(T,E,S)表示，其中T={t1,t2,…,tn}为科学工作流中的任务集合； E={e12,e13,…,eij}为任务之间的控制依赖矩阵，eij=1表示ti是tj的前驱节点，eij=0表示tj是ti的后继节点； S={s1,s2,…,sn}为科学工作流中执行时所需的数据集合。

某个数据集si可表示为
si={zi,oi,ri,wi}(31)
式中，zi表示数据集si大小； oi表示数据集si的来源，若si为初始数据集Sini，oi记为0，若si为生成数据集Sgen，oi表示生成数据集si的任务； ri表示数据集si布局的数据中心位置； wi表示数据集si的安全等级。

对数据集进行安全等级分级，需要综合考虑数据的保密性、完整性和可用性等方面的需求。首先，根据数据集的敏感程度，将其分为非隐私数据和隐私数据两类，这里规定非隐私数据的安全等级最低，设为0，而隐私数据具有不同的且高于非隐私数据的安全等级，如1、2、3等。数据集的安全等级越高，则说明该数据集的安全需求越高。

某个任务ti可表示为
ti={Ii,Oi,f(ti),mi}(32)
式中，Ii为任务ti的输入数据集合； Oi为任务ti的输出数据集合； f(ti)表示执行任务ti的数据中心位置； mi表示任务ti的安全等级。

任务的安全等级可以根据其所涉及的数据集的安全等级来进行设置。当任务需要输入和输出数据集时，其安全等级应不低于其输入和输出数据集中最高的安全等级，以确保与其关联的数据安全性。因此，将任务的安全等级取值为Ii和Oi中最高的安全等级。

2． 混合云环境

混合云环境C中包含公有云Cpub和私有云Cpri，二者均由多个数据中心组成，公有云Cpub={c1,c2,…,cn}包含n个数据中心，私有云Cpri={c1,c2,…,cm}包含m个数据中心。数据中心ci可表示为
ci={hi,vi,pi,li}(33)
式中，hi表示数据中心的存储容量上限，公有云的容量不设上限，私有云上的数据集大小不得超过该存储容量； vi表示数据中心ci当前已使用的存储容量，将已使用存储容量超出容量限制的数据中心称为超负荷数据中心； pi表示数据中心ci存储单位容量所需的代价； li表示该数据中心的安全等级。

数据中心的安全等级需要综合考虑数据中心的地理位置、安全措施、可靠性等方面的因素，不同云数据中心提供不同安全服务来保护存储在其上的数据集。根据数据中心提供的安全服务，将数据中心进行安全等级分级。由于用户与公有云服务商之间难以相互信任，且安全性问题一直是公有云端不可忽视的问题，而将数据存储在私有云上，用户对基础设施拥有更多控制权，可以通过局域网、防火墙等技术屏蔽外部访问。因此，定义公有云中数据中心安全等级最低，设为0，私有云中数据中心的安全等级高于公有云，如1、2、3等。

3． 数据布局器

科学工作流在执行前，由数据布局器将数据集放置到合适的数据中心中，生成数据布局方案。为避免数据的泄露和被篡改等安全威胁，将数据的安全需求和数据中心提供的安全服务进行量化，根据所提供的安全等级分级机制进行匹配，从而提高隐私数据的安全性。

1) 安全等级分级机制

安全等级分级机制如下： 当数据集si和任务tj放置或布局在数据中心ck中，必须满足
wi,mj≤lk(34)
即仅允许数据集和任务放置或布局在安全等级不低于它自身的数据中心中。同样地，数据中心仅允许存储或接受安全等级不高于它自身的数据集和任务。

综上所述，对于混合云环境C中的任务tj，任务tj放置在数据中心ck。当tj的输入数据集或输出数据集的集合{Ij,Oj}中包含数据集si，且wi=mj=L(L≥1)，ri=A(A∈［1,|C|］)，必须满足： 

① ri≡A； 

② 对于数据中心ck，总有lk≥L； 

③ 对于数据中心ck及任意的数据集sn∈{Ij,Oj}，总有lk≥wn。

对上述规则做如下解释： 对①，数据集存储在数据中心后，在后续任务进行中其存储位置不可改变； 对②，此时任务的安全等级为L，放置任务的数据中心的安全等级不低于任务的安全等级； 对③，由于lk≥L，且wi=L≥wn，所以lk≥wn。

2) 数据布局方案

在本节中主要关注数据集跨数据中心产生的传输时延，科学工作流执行过程中数据存储、读取数据等时延与上述时延相比可以忽略不计。数据集sk布局到数据中心ci的映射y可表示为y=(sk,ci)，我们使用Y来表示所有数据集到数据中心的映射集合。数据集sk从数据中心ci传输到数据中心cj的单次数据传输可以表示为tran=(ci,sk,cj)，那么单次跨数据中心传输产生的传输时间可表示为： 
q(tran)=q(ci,sk,cj)=zkbij(35)
式中，bij为数据中心ci和数据中心cj之间的带宽，bij=bji。Tras={tra1,tra2，…，tran}，为所有数据集的跨数据中心传输集合。因此，q(tran)=q(ci,sk,cj)=zkbij总传输时间Q可表示为： 
Q=∑|Tras|n=1q(tran)(36)
综上所述，整个数据布局方案可定义为
N=(S,C,Y,Q)(37)
基于上述定义，混合云环境下面向数据安全的科学工作流数据布局方法可表示为式（38）和式（39），其核心目标为降低传输时延，即总传输时间Q最低，且同时满足以下两个条件约束： ①数据中心的存储容量约束； ②安全等级约束。在下文中这两个约束条件合称为“条件约束”。
min Q(38)
s．t．j,∑|S|i=1zi·uij≤hjs．t．i,j,wi·uij≤lj(39)
式中，uij={0,1}，表示数据集sj是否存储在数据中心ci上，如果是，则uij=1，否则uij=0。

3．1．4基于SAGAPSO的数据布局策略

下面首先介绍本节所使用的问题编码，然后给出算法的适应度函数，最后提出基于遗传算法和模拟退火算法的自适应粒子群优化算法(SAGAPSO)的科学工作流数据布局策略的具体描述，在满足条件约束的情况下，尽可能减少科学工作流的传输时间。

1． 问题编码

本小节采用离散型编码方式对数据的布局策略进行编码，每个粒子代表一种布局策略，粒子i在t次迭代的位置为
Xtik=(xti1,xti2,…,xtin)(310)
每个粒子由n个分位组成，n代表数据集数量。Xtik(k=1,2,…,n)表示第i个粒子在第t次迭代时第k个数据的存储位置，取值范围为［1,|C|］。
X72=(2,1,3,2,4,2,1,2)(311)


图32问题编码

式（311）为一个粒子的编码示例，该粒子的数据集数量n为8。图32表示该编码粒子对应的数据布局位置。从中可知： 编号4的数据放置在服务器2上。


2． 适应度函数


本节旨在优化数据传输时延，粒子对应数据布局结果的传输时间越短，该粒子质量越高，但是在编码过程中可能存在某些不可行解粒子，不可行解的原因是该粒子不满足条件约束。将导致粒子不可行的数据合称为非法数据集Sinf，因此对于可行解粒子和不可行解粒子的优劣比较主要分以下三种情况： 

(1) 两个粒子皆为可行解粒子，优先选择传输时间较短的粒子。粒子的适应度函数可定义为
fitness=Q(312)
(2) 两个粒子皆为不可行解粒子，同样选择传输时间低的粒子，因为该粒子在后续更新操作中更可能变为可行解粒子。适应度函数与式（312）一致。

(3) 两个粒子一个为可行解粒子，一个为不可行解粒子，选择可行解粒子。粒子适应度函数可定义为
fitness=0，满足条件约束的粒子1，其他(313)
3． 粒子的更新策略

PSO算法通过模拟鸟群在捕食区域内捕食唯一食物，建立粒子群模型，之后迭代收敛求最优解。在传统PSO算法中，Lin等结合遗传算法的变异算子和交叉算子思想进行改进(GAPSO)，为使该算法适应本模型，粒子i在第t次迭代进行如下更新： 定义变异操作的运算符如式（314）所示，定义交叉操作的运算符如式（315）和式（316）所示。
Ati=ωM(Xt-1i)=M(Xt-1i),r0<ωXt-1i,其他（314）
Bti=c1Cp(Ati,pt-1i)=Cp(Ati,pt-1i),r1<c1Ati,其他（315）
Cti=c2Cg(Bti,gt-1)=Cg(Bti,gt-1),r2<c2Bti,其他（316）
式中，r0,r1,r2∈(0,1)，为随机因子； M()为变异操作，随机选取编码粒子中的某个分位，改变该分位的数值； pi和g分别为个体最优粒子和全局最优粒子； Cp()和Cg()分别表示与个体最优粒子和全局最优粒子的交叉过程，随机选取Ati和Bti的起止位置，分别与pt-1i和gt-1相同分位之间的数值进行交叉。

图33(a)表示粒子的变异操作，其中选取粒子的第4分位即f1位置进行变异，其存储的数据中心编号从2变异为4； 图33(b)表示粒子的交叉操作，该实例从第3分位（即f2）至第6分位（即f3）选择交叉，粒子的值从［3，4，4，2］变为［1，3，2，1］。



图33编码粒子的更新操作


需要注意的是，在粒子的初始化和变异过程中，数据布局后的数据集存储位置应满足安全等级约束。当粒子为不可行解粒子，优先选取存储在超负荷数据中心中的数据集分位进行变异，使其更有可能变异为可行解粒子。

综合上述分析，对粒子i在t时刻的更新操作可定义为
Xti=c2cg(c1Cp(ωM(Xt-1i),pt-1i),gt-1)(317)
GAPSO虽在一定程度上提高了种群进化的多样性，但当陷入局部极值时，仍采取原gt的更新策略，跳出局部极值的效率并不高，在迭代后期gt更是难以进行有效更新。因此，结合模拟退火算法概率接受更差解的思想对GAPSO进行改进，使其有效跳出局部最优，增大搜寻到更优解的概率。

在模拟退火算法(SA)中，使用Metropolitan准则以Me的概率接受比当前解更差的解。SA的接受概率Me的大小为
Me=ef(xn)-f(x0)T(318)
式中，T为当前模拟退火温度； f(xn)和f(x0)分别为新解和旧解的模拟退火算法适应度值。

在每次迭代过程中，对全局最优粒子gt进行如下更新操作： 所有个体最优粒子pti都将以fTF(pti)的概率替换全局最优粒子gt。fTF(pti)为模拟退火算法适应度值，其大小定义为
fTF(pti)=e-f(pti)-f(gt)T∑ni=1e-f(pti)-f(gt)T（319）
式中，f(pti)和f(gt)为个体最优粒子和全局最优粒子的粒子群优化算法适应度值。

在获得pti模拟退火算法适应度值后使用轮盘赌从所有pti中选择替换gt。在很大程度上避免了陷入局部最优，且在粒子向种群学习的过程中，扩大了解的搜索范围，在算法快速收敛的同时仍保持较高的种群多样性。

4． 粒子到数据布局方案的映射

算法3.1描述了粒子到数据布局方案的映射过程。输入为混合云环境C，科学工作流G={T,E,S}和编码粒子X，输出为数据布局方案N={S,C,Y,Q}。需要注意的是，在任务执行过程中，若某中间数据集后续不再被使用，那么该数据集可以被删除，以增大数据中心可使用容量，节约空间。






算法3.1编码粒子到数据布局方案的映射

输入： G，C，X

输出： N，Q

0: 初始化：Q←0，a∈［1，|C|］，va←0

1: for each Si of Sini do

2: 根据初始数据集Sini更新数据中心已使用容量

3: if 当前数据中心超负荷 then

4: 将当前粒子设为不可解粒子，更新Sini

5: end if

6: end for

7: for j←1 to j=|T| do 

8: 任务tj调度到安全等级约束下传输时间最小的数据中心ck

9: IOi=Ii+Oi

10: if IOi+vk>hk then

11: 将当前粒子设为不可解粒子，更新Dinf

12: end if

13: 将任务tj的输出数据集传输到对应数据中心cm

14: 更新数据中心cm已使用容量vm

15: for j←1 to j=|IOi|

16: 根据式(35)计算数据集sj在对应数据中心ca和cb的数据传输时间q(ca,sj,cb)

17: Q+=q(ca,sj,cb)

18: end for

19: for each Sl of Sgen

20: if Sl后续不再被使用 then

21: delete Sl

22: 更新存储Sl的数据中心已使用容量 

23: end for

24: end for

25: return N，Q

26: end procedure


算法详细描述如下： 将所有数据中心的存储量初始化为0，总传输时间Q初始为0(第0行)。遍历初始数据集(第2~7行)，将初始数据集布局到其对应的数据中心，并更新该数据中心的存储量，若当前存储量超出数据中心的容量限制，则该编码粒子为不可行解粒子，将存放在该数据中心的数据集存入Dinf，方便后续变异。按任务执行顺序遍历任务(第8~25行)，在任务执行前，根据贪心策略，将任务调度到安全等级约束下传输时间花费最小的数据中心(第9行)，并判断该数据中心当前的存储量和该任务的输入/输出数据集大小之和是否超过该数据中心的容量hk(第10~13行)，若超过，则数据中心容量不足，该编码粒子为不可解粒子，将存放在该数据中心的数据集存入Dinf； 否则任务正常执行。将输出数据集进行输出，更新数据中心已使用容量(第14~15行)。遍历当前任务的输入/输出数据集IOi(第16~19行)，根据式(36)计算当前数据集sj跨数据中心ca和数据中心cb的传输时间q(ca,sj,cb)，累加即得总传输时间Q。遍历所有中间数据集(第20~24行)，如果该中间数据集Sl在后续任务中不再被使用，则删除Sl，并更新对应数据中心的已使用容量，输出数据布局方案N和总传输时间Q(第34行)。

5． 参数设置

惯性权重因子ω决定PSO算法的速度的变化情况。通过自适应调整机制，根据当前粒子优劣性即当前粒子与全局最优粒子之间的差异程度对ω进行自适应调整。ω可表示为
ω=ωmax-(ωmax-ωmin)×expd(Xt-1,gt-1)|S|d(Xt-1,gt-1)|S|-1．01（320）
式中，d(Xt-1,gt-1)表示Xt-1与gt-1在相同分位上取值不同的个数。

自身认知因子c1和种群认知因子c2分别设为
c1=cs1-(cs1-ce1)×(ic/im)（321）
c2=cs2-(cs2-ce2)×(ic/im)（322）
式中，cs1和ce1、cs2和ce2分别为自身认知因子c1和种群认知因子c2的设定初始值与最终值； ic和im为当前迭代次数和最大迭代次数。

退火操作降温公式为
T=T01+t（323）
式中，T0为初始温度； t为迭代次数。

6． 算法流程

基于前面所述，本节所提出的SAGAPSO算法的具体流程如图34所示。



图34SAGAPSO算法流程图


3．1．5实验

实验结果的讨论将在这一节进行，主要围绕以下研究问题(Research Question，RQ)进行讨论。

RQ1： 在条件约束下，和其他布局算法相比，SAGAPSO在降低科学工作流的传输时延方面是否具有优越性。

RQ2： 在相同实验环境下，仅改变私有云数据中心容量，观察分析不同算法在不同科学工作流执行后的实验结果。

RQ3： 在一致的实验设置中，通过仅调整私有云数据中心的数量，进行了对比分析，以观察不同算法在执行各种科学工作流之后的实验成效。

RQ4： 在相同实验环境下，仅改变数据中心间的带宽，观察分析不同算法在代表性科学工作流执行后的实验结果。

RQ5： 为探讨本节所提供的安全等级分级的重要性，分析比较隐私数据集固定存储与安全等级分级存储的不同算法在不同科学工作流执行后的实验结果。

1． 实验设置

本节实验都在16GB RAM和2．6GHz Intel i76700HQ CPU的Windows 10系统下运行，SAGAPSO和其他对比算法均在Python 3．8环境下实现。

本实验涉及SAGAPSO的相关参数如表31所示。科学工作流主要来源于3个不同科学领域的中型科学工作流模型： Montage、Inspiral、Epigenomics。规模大小为中型科学工作流(约50个任务数)和大型科学工作流(约100个任务数)，它们拥有其独特的任务依赖结构和计算需求。



表31SAGAPSO的相关参数


参数值


种群大小50

最大迭代次数1000

ωmax，ωmin0．9，0．4

cs1，ce10．9，0．2

cs2，ce20．9，0．4

T01000


特别地，为更好地观察不同影响因素对实验的影响，设置默认实验环境如下： 混合云环境中有4个数据中心{c0,c1,c2,c3}，其中c0为容量无限，安全等级为0的公有云数据中心； c1、c2、c3分别为安全等级为1、2、3的私有云数据中心。定义私有云数据中心基准容量为
h=δ·∑|S|i=1Zi|C|-1(324)