副本技术作为一种提高系统可用性、负载均衡及访问效率的手段，目前已经广泛应用于各种云服务系统的性能保障^[1]。随着副本技术的不断发展，在云服务系统中部署组件服务副本已越来越普遍。组件服务副本在云服务系统中得到了广泛的应用，采用这种机制可以提升组件服务的可用性、提高云服务系统整体的性能。组件服务副本放置作为云服务系统中组建服务副本的一个关键问题，能否顺利解决，直接影响云服务系统的整体性能。

目前，针对如何进行副本放置问题开展了很多工作，在组件服务副本放置位置选择方面，目前的研究工作可以分为非云计算背景下的副本放置和云技术背景下的副本放置两类。

在非云计算背景下的副本放置研究中，文献[2]提出了一种图着色算法来放置副本；文献[3]介绍了基于层叠网的服务质量感知对象复制问题，并提出了GreedyMSC、CORE-SELECTON和TTL-BASED 3种算法，可在O(n3)的时间复杂度下得到副本放置策略；文献[4]给出了一种QoS感知的副本放置问题定义，提出了一类启发式算法L-Greedy-Insert，通过带回溯的循环试探寻求满足QoS约束的副本集合。在云计算背景下的副本放置研究中，文献[5]提出了一种志愿者计算框架；CloudRank^[6]是一种面向云计算的基于QoS的组件排名框架，通过将计算节点的QoS值从高到低进行排序，并从中选取QoS值的计算节点进行副本放置；文献[7]针对副本的负载均衡问题提出了副本放置算法；文献[8]通过对历史访问记录的分析，给计算节点赋予决策值，用以放置副本并平衡系统总体负载情况。

然而，上述研究工作大都没考虑组件服务副本与数据副本的区别，与传统分布式计算平台上的数据副本相比，云计算平台上的组件服务副本有着显著的区别，最主要的两个区别为：1) 云服务系统上的云应用大多由多个不同的组件服务构成，这些组件服务之间相互协作共同完成整个系统的服务，并可能具有较强的数据依赖关系，类似科学工作流当中的I/O密集型应用。2) 云计算平台上的用于放置副本的计算节点数量众多，各个计算节点性能各异。

基于以上分析，得知组件服务不同于单一的、独立的数据，在组件服务之间可能存在着紧密的数据依赖关系，即一个组件服务的输出是另一个组件服务的输入。如果在组件服务访问频繁的时候，还按照针对数据副本的放置方式来放置，将难以保证性能。一个完整的云应用程序大多是一个拓扑感知方式的^[9]，因此在放置组件服务副本时采取与计算节点拓扑结构相匹配的放置方式，对于提高云应用的执行效率是有益的。

为此，本文针对具有强数据依赖关系的组件服务副本放置这个关键问题进行分析，并提出基于拓扑匹配的组件服务副本放置算法。该算法包括3个主要的步骤：首先介绍了一种如何来获取各个组件服务之间的通信拓扑结构的方法；然后给出了一个获取计算节点拓扑结构的方法；最后提出了一个依据组件服务与计算节点的拓扑信息来进行组件服务副本放置的方法，并通过真实数据对本文提出的组件服务副本放置算法进行实验以证明其优越性和有效性。

2 组件服务副本放置算法 2.1 云服务逻辑拓扑结构探索算法

云应用中的各个组件服务之间的通信关系可以用一个通信矩阵来表示，矩阵当中的值表示两个组件服务之间通信的频繁程度，其值越大则表示两个组件服务之间的通信更紧密。

本文将通信拓扑探索归结为图聚类问题，即把通信矩阵进行结构的划分，使得通信紧密的组件服务处于一个结构当中。本文使用层次聚类算法来获取云应用中各个组件服务的通信拓扑结构。层次聚类算法事先并不需要假定分解成多少个聚类，而是通过对系统生成树的任意层次进行“cutting”操作来获得适合的聚类数。层次聚类算法得到的结果不一定是最优的，通常还需要对结果使用优化算法针对聚类的模块性^[10]进行改进。本文使用多规模优化算法来对聚类结果进行优化^{[11, 12]}。

假设G为通信矩阵生成的无向图，表示为(V，E)，其中V表示为节点的集合，E表示边的集合。边的权重可以通过函数f(x, y)来表示。其中，节点x的度表示为deg(x)，即该节点所有边的权重之和。一个节点集合的度表示为deg(V)；为每对不同的聚类(A,B)分配一个实数值，称之为融合优先度(mergingpriority)，如式(1)。当不同的聚类需要进行合并操作时，它们之间的融合优先度决定它们的融合次序，融合优先度越高的，越优先进行融合。

${\rm{融合优先度}} = \frac{{f{\rm{(}}A{\rm{,}}B{\rm{)}}}}{{{\rm{deg(}}A{\rm{)deg(}}B{\rm{)}}}}$

(1)

是否具有良好的模块性是权衡图聚类质量的重要标志。文献[13]提出了一个评估n个分离的节点集之间模块性的方法，具体形式为：

$Q(\mathop V\nolimits_1 ,\mathop V\nolimits_2 , \cdots ,\mathop V\nolimits_k ) = \sum\limits_{i,j = 1}^k {\left( {\frac{{{\rm{cut}}(\mathop V\nolimits_i ,\mathop v\nolimits_j )}}{{\left| E \right|}} - \frac{{{\rm{deg}}{{(\mathop V\nolimits_i )}^2}}}{{{\rm{deg}}{{(V)}^2}}}} \right)} $

(2)

式中，丨E丨表示边的数目；${\rm{cut}}(\mathop V\nolimits_i ,\mathop v\nolimits_j )$表示被切断的所有边的权重之和^[14]。通过式(2)推断出，如果融合聚类A与聚类B将会改变模块性大小的值为：

$D\mathop Q\nolimits_{A{\rm{,}}B} {\rm{:}} = \frac{{{\rm{2}}f{\rm{(}}A{\rm{,}}B{\rm{)}}}}{{f{\rm{(}}V{\rm{,}}V{\rm{)}}}} - \frac{{{\rm{2deg(}}A{\rm{)deg(}}B{\rm{)}}}}{{{\rm{deg(}}V{{\rm{)}}^{\rm{2}}}}}$

(3)

此外，把属于聚类A的服务节点v移动到另一个聚类B中，会在一定程度上影响两个聚类之间的模块性，具体影响的大小又以式(4)来表示：

$\begin{array}{l} D{Q_{v \to B}}{\rm{:}} = \frac{{{\rm{2}}f{\rm{(}}v{\rm{,}}B{\rm{)}} - 2f{\rm{(}}v{\rm{,}}A - v{\rm{)}}}}{{f{\rm{(}}V{\rm{,}}V{\rm{)}}}} - \\ \frac{{{\rm{2deg(}}v{\rm{)deg(}}B{\rm{)}} - {\rm{2deg(}}v{\rm{)deg(}}A - v{\rm{)}}}}{{{\rm{deg(}}v{{\rm{)}}^{\rm{2}}}}} \end{array}$

(4)

本文提出的逻辑拓扑结构探索算法的具体步骤如算法1所示。

算法1：云服务逻辑拓扑结构探索算法。

输入：邻接矩阵M，边集E，点集N。

输出：k个不同聚类的拓扑结构。

1) 通过式(1)计算权重密度(weight density)，并对权重密度从高到低进行排序操作。

2) 如果某条边的起始节点与结束节点没有融合到一起，并且这条边的权重密度(weight density)大于atedges/atparis(atedges表示邻接矩阵M生成的无向图当中所有边的权重之和，而atparis表示无向图当中所有节点的权重和的平方)，那么就对这条边的起始节点和结束节点进行融化操作。融化完成后重新生成新的邻接矩阵M和新的边集E。重复该操作直至没有聚类可以进行融合操作。

3) d为系统生成树的高度，其值与步骤2)中的循环数相等，本算法通过使用式(4)计算移动一个聚类中的节点到另一个聚类里所得到的新的模块性，从中选择最优移动(v,B)，即新的模块性最高的一个移动。

4) 如果(v,B)是最优移动并且$D{Q_{v \to B}} > 0$，就把节点v移动到聚类B中，重复此操作直至$D{Q_{v \to B}} \le 0$。

2.2 云环境物理拓扑结构探索算法

在获取逻辑拓扑结构之后，本节将进一步介绍如何获取计算节点的拓扑结构，即物理拓扑结构。此物理拓扑结构发现算法是以计算节点之间的响应时间作为划分拓扑结构的依据，即一个相同拓扑结构的聚类里的计算节点之间有着更小的延迟，因此，如果把云环境中的各个计算节点之间响应时间用邻接矩阵的形式来表示的话，物理拓扑结构发现问题也可以归类为一个图聚类问题。

用$C = {\rm{\{ }}{c_i}|i = {\rm{1,2,}} \cdot \cdot \cdot {\rm{,}}n{\rm{\} }}$表示整个云服务系统，其中，c_i表示第i个计算节点，并且每个计算节点都有其极限带宽。计算节点之间的响应时间可以通过一个nxn的矩阵R来表示。为了解决这个问题，提出基于普聚类算法^[15]的云环境物理拓扑结构识别算法，把大量计算节点分解成多个不同的聚类，使得相同聚类里的各个计算节点之间的响应时间较短。为了方便计算，把响应时间矩阵R进行标准化操作，转化为一个带权矩阵W，有：

$R = \left[ {\begin{array}{*{20}{c}} 0&{\mathop b\nolimits_{12} }& \cdots &{\mathop b\nolimits_{1n} }\\ {\mathop b\nolimits_{21} }&0& \cdots &{\mathop b\nolimits_{2n} }\\ \vdots & \vdots & \ddots & \vdots \\ {\mathop b\nolimits_{n1} }&{\mathop b\nolimits_{n2} }& \cdots &0 \end{array}} \right]W = \left[ {\begin{array}{*{20}{c}} 0&{\mathop w\nolimits_{12} }& \cdots &{\mathop w\nolimits_{1n} }\\ {\mathop w\nolimits_{21} }&0& \cdots &{\mathop w\nolimits_{2n} }\\ \vdots & \vdots & \ddots & \vdots \\ {\mathop w\nolimits_{n1} }&{\mathop w\nolimits_{n2} }& \cdots &0 \end{array}} \right]$

式中，b_ij表示计算节点c_i和c_j之间的响应时间；w_ij表示两个计算节点之间通信能力的强弱，其值如式(5)所示，可以看出w_ij的值越大意味着更短的响应时间。

$\mathop w\nolimits_{ij} = 1 - \frac{{\mathop b\nolimits_{ij} - \min \mathop b\nolimits_{ij} }}{{\max \mathop b\nolimits_{ij} - \min \mathop b\nolimits_{ij} }}$

(5)

本文使用拉普拉斯矩阵(Laplacian matrix)作为谱聚类的方法，定义如下：

$L = D - W$

(6)

式中，D表示为矩阵W的度矩阵。

本文提出的物理拓扑结构探索算法的具体步骤如算法2所示。

算法2：云环境物理拓扑结构探索算法。

输入：响应时间矩阵R，需要分割成的聚类个数k。

输出：k个聚类。

1) 通过响应时间矩阵R计算出相似图矩阵W，再通过相似图矩阵W计算出带权矩阵D；

2) 通过式(6)计算出拉普拉斯矩阵L；

3) 计算拉普拉斯矩阵L的k个最小的特征值以及对应的特征向量${u_{\rm{1}}}{\rm{,}}{u_{\rm{2}}}{\rm{,}} \cdots {\rm{,}}{u_k}$；

4) 把特征向量${u_{\rm{1}}}{\rm{,}}{u_{\rm{2}}}{\rm{,}} \cdots {\rm{,}}{u_k}$作为k个列生成一个新的n行k列的矩阵U；

5) 令${({r_i})_{i = {\rm{1,2,}} \cdots {\rm{,}}n}}$表示矩阵U的第i行；

6) 使用k-means对${({r_i})_{i = {\rm{1,2,}} \cdots {\rm{,}}n}}$进行聚类操作，使之分解成$\{ {A_1},{A_2}, \cdots ,{A_k}\} $k个聚类；

2.3 组件服务副本放置

上文所述的两个聚类操作完成后，组件服务节点与计算节点均被分解到不同的聚类中。这时就可以依据逻辑拓扑结构和物理拓扑结构进行副本的放置。依据拓扑结构来放置副本实际就是一个映射操作。聚类完成后，计算节点分割成了多个不同的聚类，本文使用平均响应时间(ART)来表示每一个聚类的通信能力，如下述公式计算。

${\rm{AR}}{{\rm{T}}_i} = \frac{1}{n}\sum\limits_{j = 1}^n {\overline {\mathop C\nolimits_{ij} } } $

(7)

式中，ART_i表示第i个计算节点聚类的平均响应时间；C_i表示第i个聚类的质心；C_ij表示与节点j之间的响应时间；n表示计算节点聚类i当中的节点数。当放置组件服务副本时，可以依据组件服务聚类的权重以及计算节点聚类的ART来放置。使用I来表示计算节点聚类的集合，而每一个计算节点聚类又是许多计算节点的集合，计算节点之间的表现使用一个nxn矩阵φ来表示，n表示某个计算节点聚类当中 节点的数目，φ中元素的值使用$\varphi ({p_i},{\rm{ }}{p_j})$来表示，其表示计算节点${p_i}$和${p_j}$的亲和程度，具体定义为：

$\varphi (\mathop p\nolimits_i ,\mathop p\nolimits_j ) = \omega \times \mathop {{\rm{Comm}}}\nolimits_{ij} + (1 - \omega ) \times \mathop {{\rm{Comput}}}\nolimits_i $

(8)

式中，Comm_ij表示计算节点${p_i}$和${p_j}$之间的通信能力；CommPut_ij表示两个计算节点的计算能力；ω表示通信能力和计算能力之间的一个权值；Comm_ij和CommPut_ij通过基础测试获取。通过式(8)可为每一对计算节点计算出它们的亲和度，从计算节点聚类中选取若干个彼此之间亲和度尽可能大的计算节点，记为ρ。为了获取ρ，一种可能的方法就是遍历所有节点来选取最优的节点集ρ。然而，这种方法在节点数目为n的前提下存在着$\mathop C\nolimits_n^{\left| \rho \right|} $种可能性，并且当n的数目非常大的情况下，这种方法的效率将会非常低下。为了解决这一问题，本文使用贪心选择算法来获取近优放置节点集合ρ，如算法3所示。

算法3：贪心选择算法。

输入：计算节点聚类C，矩阵φ，需要的用于放置组件服务副本的计算节点数m。

输出：近优放置节点集合ρ。

1) 对于每一个计算节点，分别计算它和其他计算节点之间的亲和值，并把所有亲和值相加作为该计算节点的总亲和值。

2) 节点的总亲和值越小，意味着该节点作为组件服务副本放置节点的可能性越低。找出总亲和值最小的节点并把它从组件服务副本放置候选节点集C中删除出去。删除完成后，需要为节点集C中剩余的每一个计算节点重新计算其总亲和值。重复该步骤直至C中剩余的计算节点数目与m相等。

3) 令ρ=C，则ρ就是近视最优解。

3 模拟实验与性能分析

为模拟本文的组件服务副本放置算法，实验建立了基于CloudSim^[16]的实验框架，根据实验需要，实验基于CloudSim仿真工具进行结果仿真之前需要对CloudSim内部的调度模块进行改写，因为CloudSim内部调度模块是按照全局并行的调度方式，即所有部署的组件服务同时调用执行。这种调度方式并不符合本算法的要求。所以需要对CloudSim内部的调度模块进行修改，使其调度方式可以按照某种用户自定义的规则进行，并在CloudSim内部加入代理模块来完成组件服务副本放置工作，从而有效的对本章的算法进行仿真。

实验对本文的基于拓扑匹配的组件服务副本放置算法与文献[17]的不考虑拓扑结构的组件服务副本随机放置算法以及文献[6]的组件排名放置框架CloudRank进行比较，验证了算法的有效性。实验使用执行周期(makespan)和延迟(latency)两个指标作为判断有效性的依据。其中，一个云应用的执行周期表示从其第一个组件服务开始执行，到其最后一个组件服务执行完成这一段时间；一个云应用的延迟表示该云应用从运行到结束这段时间内，每一对具有前后调用关系组件服务之间延迟的总和。

实验选取3种不同的云应用CA₁、CA₂、CA₃进行组件服务副本的放置，每个云应用均有各自不同的组件服务流程，分别为并行结构、选择结构及并行-选择混合结构。在正式进行仿真实验之前，需要通过查看日志文件获取云应用CA₁、CA₂、CA₃中各个组件服务之间的通信频繁程度以及各个组件服务的参数，即组件服务id、组件服务指令长度和组件服务输出文件大小。

通过使用算法1来获取组件服务的拓扑结构；通过使用算法2来获取计算节点的物理拓扑结构。本文实验将计算节点分成3个聚类，并使用算法3来进行组件服务副本放置，假设所有的副本数量均为1。使用CloudSim按照上文所述进行内容放置，对实验进行仿真。使用CloudSim进行10次仿真实验，仿真实验如图 1、图 2、图 3所示。实验最终结果如表 1、表 2所示。

表 1、表 2所反映出的10次实验的平均结果表明，采用本文所提出的组件服务副本放置算法即基于图拓扑匹配的组件服务副本放置算法，较之目前常用的副本随机放置算法，无论是在整个云应用的执行周期还是云应用的延迟时间上，都有比较明显的降低。图 3、图 4、图 5通过对CA₁、CA₂、CA₃3个不同结构的云应用来进行组件服务放置实验对比，说明本文提出的组件服务副本放置算法不仅适用于某一种特殊结构的云应用，而且对大部分结构的云应用都有一定的效果。

4 结 论

组件服务副本放置问题是部署组件服务副本的云服务系统上的一个关键问题，合理的组件服务副本分布可以有效提高系统的性能、可用性与可靠性。而组件服务副本不同于以往的数据副本，组件服务副本之间具有前后的依赖关系，放置时也必须根据组件服务副本之间的依赖关系来选取合适的计算节点进行放置。所以本文提出了基于图拓扑匹配的组件服务副本放置算法，通过匹配组件服务的拓扑关系与计算节点的拓扑关系来进行组件服务副本放置，使得云系统可以更加高效和可靠。通过实验的比较分析，验证了基于图拓扑匹配的组件服务副本放置算法的有效性。