面向私有云的业务迁移部署方法研究
2016-09-03郭静
郭 静
(中国电子科学研究院，北京 100041)
工程与应用
面向私有云的业务迁移部署方法研究
郭静
(中国电子科学研究院，北京100041)
业务合理迁移部署是私有云高效使用的前提与关键，然而，由于业务对资源需求突发增长、部署时业务之间存在约束等因素的存在使得业务合理部署困难。为解决上述问题，本文对业务迁移部署问题进行建模，充分考虑了业务系统的重要性差异和应用组件之间的约束关系，采用资源预留机制来保证业务稳定运行，并在理论分析的基础上设计了一种基于分组遗传算法的业务迁移部署方法。方法采用分组方式对迁移方案进行映射，首先，按照顺序部署的方式生成满足约束的初始方案，然后，综合根据方案中物理服务器的资源利用情况、应用组件的等级和其对资源的需求，交叉生成新的部署方案，其次，根据物理服务器的资源闲置情况，变异生成新的部署方案，并通过混合策略选择方案来迭代搜索，最后，迭代完成后输出最终结果。实验结果表明本方法能有效解决业务迁移部署问题。
业务迁移部署；私有云；资源预留；分组遗传算法；NP-Hard问题
TP393
A
1673-5692(2016)02-191-08
0 引 言
随着信息技术的不断发展，云计算技术[1]已经成为企事业单位实现应用系统集约化发展的重要手段。为满足自身业务发展的需要，提高基础设施资源(计算、存储等资源)的利用水平，降低系统运维的成本，许多单位已经开展了私有云[2]的建设。当私有云建成以后，业务系统需要迁移入云部署才能实现最终的预期效果。为此，业务合理的迁移部署已成为私有云高效使用的前提与关键。
在私有云中，业务系统对基础设施资源的需求主要由虚拟机来提供，多个虚拟机共同部署在一台物理服务器上。合理部署业务系统就是要将承载应用组件的虚拟机合理的映射到私有云中的物理服务器上，并保证业务系统稳定运行，同时提高私有云中资源的利用水平。
然而，由于业务对资源需求突发增长，迁移部署时业务之间存在约束等因素的存在，业务迁移部署常常面临下列挑战。
一方面，在私有云中，一台物理服务器通常会部署多个承载应用组件的虚拟机，所以当业务系统对资源需求突发增长时，同台机器中的业务系统之间会抢占资源，导致业务运行的稳定性和可靠性降低。另一方面，各个单位会根据自身业务的特点设计一些部署策略来保证业务整体运行最优，这些策略表现为承载不同应用组件的虚拟机之间的约束关系。目前，已有文献[3]给出了迁移入云的步骤和通用原则，但是缺少细化部署的方法，根据本文分析业务迁移部署问题是一个NP-Hard问题，为此如何从大量的可行部署方案中找出优秀的方案(即，确定承载应用组件虚拟机的部署位置)是一个挑战。虽然已有研究者针对虚拟机放置或调度问题提出了多种映射方法[4-9]，但是与传统的虚拟机放置或调度不同，业务迁移入云部署不仅需要考虑业务应用组件对基础设施资源需求可能会突发增长的情况，而且在部署时，还需要考虑业务应用组件之间的相互关系。因此，难以利用上述方法来对问题进行求解。
为解决上述问题，本文对业务迁移部署问题进行建模，在理论分析的基础上设计了一种基于分组遗传算法的业务迁移部署方法，并通过实验验证了方法的有效性。在建模上，本文充分考虑了业务系统的重要性差异和应用组件之间的约束关系，采用资源预留机制来保证业务稳定运行。在求解方法设计上，采用分组方式对迁移方案进行映射，首先，按照顺序部署的方式生成满足约束的初始方案，然后，综合根据方案中物理服务器的资源利用情况、应用组件的等级和其对资源的需求，交叉生成新的部署方案，其次，根据物理服务器的资源闲置情况，变异生成新的部署方案，并通过混合策略选择方案以迭代搜索，最后，迭代完成后输出最终结果。实验以资源利用率为评价指标，在多组业务系统上验证了本方法的有效性。
1 业务迁移部署建模与分析
1.1业务迁移部署的步骤
合理迁移部署系统是实现业务在私有云上稳定、可靠运行的前提与关键。为实现这一目标，业务系统的迁移部署可采用下列步骤来实现。
首先，对业务系统开展调研与分析。确定各个系统对基础设施资源的需求(如：对CPU、内存、I/O、存储的基本需求)，分析业务系统的重要程度，根据其重要性设计资源预留的大小，分析应用组件之间的相互关系，确定应用组件在部署时的策略(例如：为保证重要的业务系统拥有较高的可靠性，需要将高等级业务系统的应用组件部署在多台物理服务器上，以减少单台物理服务器故障对业务系统的影响。对于低等级业务系统的应用组件应尽量部署在同台物理服务器上，以减少对带宽资源的占用，保持网络稳定)。
然后，根据调研结果，设计具体部署方案。在方案设计时，需要满足分析确定的资源预留策略，并满足应用组件部署的约束，并保证部署方案不大于物理服务器所提供的资源能力上限，并尽可能提供私有云中的资源利用水平。
最后，采用人工部署或工具部署的方式将应用组件部署到私有云中，并对部署的业务应用进行测试优化。
从上述步骤可以看出，设计迁移部署方案是整个过程的核心与关键。为此，下面将主要对设计阶段的业务迁移入云部署问题进行建模分析。
1.2业务迁移部署问题建模
根据上述描述可知，在设计阶段业务迁移入云部署问题就是根据云中物理服务器的能力和各个应用组件之间的部署策略，以及资源预留方案，设计部署方案使得业务系统能够稳定运行，并实现云中的资源利用水平最大化。为此，该问题的建模描述如下。
业务迁移入云部署问题：已知有若干个业务应用系统需要迁移至私有云中，这些系统共需n台虚拟机来承载其应用组件。其中，业务系统对n台虚拟机的资源需求为{R1，R2，…，Ri,…,Rn}，Ri= (ri1,ri2,…,rit)是t维向量，代表承载应用组件的虚拟机i对t种资源的需求。假设云中共有M台同构的物理服务器用于虚拟机部署，每台物理服务器提供的资源能力为P=(p1，p2，…，pt)，则业务迁移入云部署问题就是计算一种合理的迁移部署方法，使得业务系统的应用组件在迁移入云后能够在虚拟机中稳定运行，且使得私有云中的资源利用具有较高水平，并满足下列约束条件。
约束条件1：资源预留约束
为防止应用组件对基础设施资源需求突发增长，物理服务器资源利用率过高影响业务运行的问题，物理服务器在部署承载应用组件的虚拟机时需要预留一定资源。根据业务系统的重要程度和其对运行稳定性要求的差异，业务系统可被划分成若干个等级，每个虚拟机的等级与其承载业务系统的应用组件等级相同。假设业务系统分为k个等级，则物理服务器需要预留资源分别为{L1,L2,…,Lk}。其中，Lk=(lk1,lk2,…,lkt)是t维向量，代表第k级应用组件对物理服务器t类资源的预留要求。当物理服务器同时部署了多个等级的虚拟机时，则其资源预留情况需按照这些虚拟机的最高等级进行预留。
约束条件2:容斥约束
根据业务系统入云部署的一些特殊要求，迁移部署通常会设计相应策略，它们表现为承载不同应用组件的虚拟机之间的容斥关系(即，虚拟机必须(或不能)部署在同一台物理服务器中)。例如：对某类资源需求较高的业务组件不能部署在同一物理服务器中，某些低等级业务系统的应用组件应尽量部署在同台物理服务器上。假设虚拟机之间的容斥关系由z条依赖约束D={d1,d2,…,dz}和v条冲突约束C={c1,c2,…,cv}组成，则可行的部署方案都要满足这些约束条件。其中，任意依赖约束关系dz由3维向量
根据上述描述，业务迁移部署问题的数学符号及物理意义的对应关系如表1所示。
表1 数学符号及物理意义
根据上述描述，求解业务迁移入云部署问题就是对下列数学模型进行求解。
问题的目标：业务迁移部署后，私有云中的资源利用水平最大化。
(1)
资源预留约束：
(2)
容斥约束：
(3)
(4)
1.3模型分析
根据业务迁移入云部署的数学建模可以看出，本问题是一个典型的组合优化问题。为更好的对模型进行求解，本文对问题的求解难度进行分析，发现业务迁移部署问题属于NP-Hard问题，模型的目标只与业务使用私有云中物理服务器数量相关，详细描述见定理1与定理2。
定理1 ：业务迁移入云部署问题是一个NP-Hard问题。
证明：已知虚拟机放置问题通常被建模成装箱问题，该问题无法在多项式时间内精确求解[10](即，该问题是NP-Hard问题)。该问题就是在物理服务器的能力约束下，寻找一种虚拟机放置方案使得资源利用最高。
与业务迁移入云问题相比，当本问题的资源预留策略为空，且承载应用组件的虚拟机不存在容斥约束关系时。虚拟机放置问题可以看作是本问题的一个特例。
假设业务迁移入云部署问题可以在多项式时间内精确求解，则虚拟机放置问题也可以在多项式时间内精确求解，所以假设条件不成立。为此，业务迁移入云部署问题无法在多项式时间内精确求解。即：业务迁移入云部署问题是NP-Hard问题，证明完毕。
定理2 ：业务入云部署后的资源利用率最高与云中使用的物理服务器数量最少等价。
证明：根据上述建模可知，当业务完成迁移部署后，云中资源利用率最高就是要最大化公式(1)的取值。
由于业务应用只能部署一次，所以等式(5)成立。即：
(5)
(6)
2 基于分组遗传算法的业务迁移部署方法
由于业务迁移入云部署问题是NP-Hard问题，所以难以给出精确的方法来对问题进行求解。为此，本文借鉴虚拟机调度的相关方法，结合本问题的特点设计一种基于分组遗传算法的业务迁移部署方法(AGroupingGeneticAlgorithmforSystemMigrationandDeployment，简称GGASMD)。
该方法的基本思想就是首先随机产生若干组迁移部署方案，然后，通过模拟自然进化的过程，利用选择、交叉、变异等操作迭代生成最终方案。考虑到承载虚拟机的数量多于物理服务器的数量，本算法采用分组方式对迁移方案进行映射，在算法设计上，本文不仅考虑了业务系统的等级和组件之间的容斥约束关系，还根据问题特点设计了交叉、选择等搜索操作，具体如下章节所述。
2.1虚拟机集合生成
由于部分承载应用组件的虚拟机需要放置在一台物理服务器中，所以为保证所有搜索方案满足依赖约束。算法根据依赖约束将必须部署在同一物理服务器的多个虚拟机看作一个超级虚拟机来进行部署。其中，超级虚拟机svo的组成可根据规则1来确定。超级虚拟机遵守其包含虚拟机的所有排斥约束，超级虚拟机的资源需求是其包含虚拟机需求的总和，超级虚拟机的等级为其包含虚拟机的最高等级。
规则1 ：∀a∈svo∧
其中，
于是按照规则1将满足依赖约束的虚拟机形成超级虚拟机，并构成新的虚拟机集合。这样业务迁移入云部署的方案将根据虚拟机集合搜索获得。
2.2方案编码映射
方案编码映射是算法搜索求解问题的前提，为更好的对业务迁移入云部署问题进行求解，本文采用分组方式[11]来对部署方案进行映射，以克服编码过长对问题求解的影响。本文将每个物理服务器映射为遗传算法的一个基因位，虚拟机(或超级虚拟机)在物理服务器上的部署方式构成了基因的信息(即，基因值)。具体如图1所示。
图1 方案编码映射
在上图中，物理服务器和虚拟机共同构成了分组遗传算法中个体的一个基因。
2.3适应度函数
适应度函数是评价部署方案优劣指标，为指导算法向最优的方案进行搜索，本文根据定理2采用公式(7)来评价方案的优劣。即：
(7)
在等式(7)中，X是业务迁移入云部署的方案，F(X)代表方案所用物理服务器的数量。
2.4初始部署方案生成
为有效求解业务迁移入云的部署方案，本文采用顺序部署的策略来生成初始方案。首先在虚拟机集合中随机生成虚拟机的部署顺序，然后，根据虚拟机的部署顺序，利用下列步骤对当前待部署的虚拟机或超级虚拟机进行部署，生成初始方案。
步骤1：对于当前待部署虚拟机i(或超级虚拟机svi)，判断当前物理服务器是否能够满足虚拟机(或超级虚拟机)对资源的需求，并满足资源预留约束和冲突约束。若满足则执行步骤2，否则执行步骤3。
步骤2：从满足约束的候选物理服务器中选择资源利用率最高的设备进行部署。其中，物理服务器j在部署虚拟机i(或超级虚拟机svi)后的综合利用率，可由公式(8)计算。
(8)
步骤3：选择一个新物理服务器来部署虚拟机或超级虚拟机。
2.5交叉操作
交叉操作是遗传算法进行全局搜索的重要步骤，本文利用交叉操作产生新的部署方案。为产生良好的部署方案，本文采用文献[12]的交叉框架，首先确定交叉点位置，然后对部分基因进行交换。为避免算法快速陷入局部最优解，根据问题的特点，本文根据物理服务器的资源利用水平来选择交叉的位置，并设计回填策略来产生新的部署方案。对于待交叉操作的部署方案，具体处理可由下列步骤完成。
步骤1：从部署方案中选择交叉操作的基因位。综合计算方案中物理服务器的资源利用率，并按概率方式选择部署片段(即，基因位)进行交叉操作。其中，部署方案中物理服务器j的资源综合利用率URj可利用公式(9)计算获得，每个物理服务器被选择的概率P(URj)由公式(10)计算获得。
(9)
(10)
步骤2：将基因位插入到另一部署方案中。首先，消除与交叉基因位相重复的虚拟机以及相应物理服务器，然后，对由删除而造成孤立的虚拟机进行重新部署。本文采用下列回填策略重新部署。先按照虚拟机承载应用的等级和资源需求情况进行排序，再按照2.3节的步骤对其进行部署。优先部署承载高等级应用组件的虚拟机，对于相同等级的虚拟机，则优先部署资源需求量高的虚拟机，其中，资源需求高低T(Ri)可利用公式(11)来衡量，取值越高则资源需求越高。
(11)
2.6变异操作
变异操作是遗传算法局部搜索的有效步骤。为更好的求解问题，该操作将对方案中某台物理服务器放置的虚拟机(或超级虚拟机)进行重新部署，部署方式与2.5节的回填方式相同。其中，被选择的物理服务器将由概率方式产生，方案中每台物理服务器被选择的概率将由其剩余的资源情况决定，具体如公式(13)所示。
(12)
(13)
其中，UUj表示物理服务器j的t类剩余资源的综合情况，P(UUj)代表物理服务器在变异操作中被选择的概率，其剩余资源越多，被选择的概率就越高。
2.7选择操作
为实现算法对问题方案的迭代搜索，选择操作将从上代种群中选择若干方案用于产生新部署方案。为了产生较好的新部署方案，本文采用混合策略来对部署方案进行选择。具体步骤如下：
首先，使用精英策略，按比例π来保留适应度值高的方案。假设算法的种群规模为N，则保留π×N个适应度最高的方案。
然后，在剩余的方案中，根据方案的适应度值计算其被选择的概率，并使用赌轮盘法进行选择。剩余方案Xo被选择的概率为P(Xo)，其计算方法如公式(14)所示。
(14)
其中，Rest代表剩余方案，Xg是剩余方案中的成员，F(Xg)是其适应度。
2.8算法的执行步骤
根据上述描述，本文算法采用下列步骤来对业务迁移部署问题进行求解。
步骤1：虚拟机集合生成。根据应用组件之间的依赖部署关系，按照依赖约束生成超级虚拟机，并与剩余虚拟机构成虚拟机集合。
步骤2：初始化设置。设置种群规模、最大迭代次数、变异概率、精英选择比例，输入物理服务器的能力、不同等级应用的资源预留要求、承载应用组件的虚拟机(或超级虚拟机)对资源的需求、虚拟机之间的冲突约束，并按照2.4节的方法生成初始部署方案，计算方案的适应度。
步骤3：交叉操作产生新的部署方案。根据方案中物理服务器的资源利用率，使用概率方式选择交叉基因，并按照2.5节的步骤生成新的部署方案，并计算方案的适应度。
步骤4：按照变异概率，利用变异操作产生新的部署方案。根据方案中每个物理服务器的剩余资源情况，按概率方式选择，并对其承载的虚拟机或(超级虚拟机)进行重新部署。
步骤5：采用混合策略从种群中选择方案进行下一次迭代搜索。首先根据精英选择比例选择适应度最高的方案，然后，利用赌轮盘法选择剩余的方案。
步骤6：判断算法是否满足停止条件，若满足则输出迁移部署方案，否则执行步骤3。
3 实验仿真
为验证本文所提方法的有效性，实验在多次仿真的基础上，以算法生成部署方案的资源利用率为评价指标综合分析算法的有效性。其中，业务系统的等级、数量、应用组件规模和对资源的需求情况将采用随机方式生成，资源利用率包括CPU、内存、I/O、存储以及综合利用率，综合利用率可由公式(1)计算获得，对比分析算法为贪婪业务迁移部署方法(GreedyAlgorithmforSystemMigrationandDeployment，简称GASMD)。该方法直接利用2.1.5节的回填策略进行部署，具体步骤是首先对虚拟机集合中的虚拟机或超级虚拟机进行排序，然后，采用2.1.4节的部署方法进行部署。
为验证本方法的有效性，本文随机生成四组数据来对比分析算法部署的效果。其中，每组数据中的业务等级都分为核心、重要、一般，业务系统对资源的需求包括CPU、内存、I/O和存储，数据规模情况及所需虚拟机的数量如表2所示。
表2 业务系统的规模及所需虚拟机的数量
为保证实验结果的可靠性，实验将分析算法执行多次的平均值，GGASMD和GASMD针对不同组业务系统生成的部署方案效果如图2-图6所示。其中，图2-图6分别是GGASMD和GASMD生成业务部署方案的CPU利用率、内存利用率、I/O使用率、存储利用率和对资源的综合利用率。
图2 算法生成部署方案的CPU利用率
从图2可以看出与GASMD相比，GGASMD生成的方案拥有较高的CPU利用率。
图3 算法生成部署方案的内存利用率
从图3可以看出与GASMD相比，GGASMD生成的方案拥有较高的内存利用率。
图4 算法生成部署方案的I/O使用率
从图4可以看出与GASMD相比，GGASMD生成的方案拥有较高的I/O使用率。
图5 算法生成部署方案的存储利用率
从图5可以看出与GASMD相比，GGASMD生成的方案拥有较高的存储利用率。
图6 算法生成部署方案对资源的综合利用率
从图6可以看出与GASMD相比，GGASMD生成的方案拥有较高的综合利用率。
综上所述GGASMD算法能更好的对业务系统进行部署，以满足业务迁移入云的要求。
4 结 语
针对私有云中的业务迁移部署问题，本文在考虑了业务对资源需求突发增长、业务系统的重要性和应用组件之间的约束关系的基础上，对该问题进行建模并进行理论分析，根据问题特点设计了一种基于分组遗传算法的业务迁移部署方法，并通过实验验证了本方法的有效性。
[1]王栋, 芮平亮. 云雾环绕的数据中心全景剖析[J]. 中国电子科学研究院学报, 2011, 06(3):324-327.
[2]李小宁,李磊,金连文,等.基于OpenStack构建私有云计算平台[J].电信科学,2012,28(9):1-8.
[3]尹乐杰. 基于云计算平台的应用系统迁移的研究与应用[D]. 厦门大学, 2012.
[4]Li,Bo,etal.EnaCloud:AnEnergy-SavingApplicationLivePlacementApproachforCloudComputingEnvironments[C].Proceedingsofthe2009IEEEInternationalConferenceonCloudComputingIEEEComputerSociety, 2009:17-24.
[5]Sun,Xin,etal.Multi-dimensionalResourceIntegratedSchedulinginaSharedDataCenter[C].DistributedComputingSystemsWorkshops(ICDCSW), 2011 31stInternationalConferenceonIEEE, 2011:7-13.
[6]Meng,Xiaoqiao,etal.EfficientresourceprovisioningincomputecloudsviaVMmultiplexing[C].Proceedingsofthe7thInternationalConferenceonAutonomicComputing, 2010:11-20.
[7]李强, 郝沁汾, 肖利民,等. 云计算中虚拟机放置的自适应管理与多目标优化[J]. 计算机学报, 2011,34(12):2253-2264.
[8]刘志飘, 王尚广, 孙其博,等. 一种能量感知的虚拟机放置智能优化算法[J]. 华中科技大学学报:自然科学版, 2012(S1):398-402.
[9]肖鹏, 刘洞波, 屈喜龙. 云计算中基于能耗比例模型的虚拟机调度算法[J]. 电子学报, 2015(2):305-311.
[10]AjiroY,TanakaA.ImprovingPackingAlgorithmsforServerConsolidation[C].InternationalComputerMeasurementGroupConference. 2007:399-406.
[11]FalkenauerE.Ahybridgroupinggeneticalgorithmforbinpacking[J].JournalofHeuristics, 2010, 2(1):5-30.
[12]FalkenauerE.TappingtheFullPowerofGeneticAlgorithmthroughSuitableRepresentationandLocalOptimization:ApplicationtoBinPacking.SpringerBerlinHeidelberg, 1995.P167-182.
郭静(1982—)，女，安徽省全椒人，博士，工程师，主要研究方向为云计算与大数据。
E-mail：itianmei@qq.com
Research on System Migration and Deployment Method for Private Cloud
GUOJing
(ChinaAcademyofElectronicsandInformationTechnology，Beijing，100041)
Migratinganddeployingthesystemsreasonableiscrucialforemployingprivatecloudefficiently.However，itisdifficulttodeploythesesystems,becausethefactorssuchasgrowthofemergencyresourcedemandandconstraintbetweenthedeployingsystems.Inthispaper，amodelwasbuiltbytakingaccountoftheimportanceofdifferentsystemsandtheconstraintbetweentheapplicationcomponents,andguaranteesbusinessstabilitybyreservingresource.Thenagroupinggeneticalgorithmforsystemmigrationanddeploymentisproposedbasedonproblemanalysis.First,itencodesthemigrationschemebygroup,andgenerateinitialsolutionbydeploytheapplicationonebyone.Then,itgeneratesthenewschemebycrossoveroperationaccordingtotheresourceutilization,levelofapplicationandresourcedemand.Next,itgeneratesthenewschemebymutationoperationaccordingtotheidleresourcesofphysicalserver,andchosenschemeforiterativesearchwithahybridselectoperation.Atlast，itoutputthefinialmigrationschemeafteriterativesearch.Theexperimentresultsshowtheeffectofthismethod.
systemmigrationanddeployment;privatecloud;resourcereservation;groupinggeneticalgorithm;NP-Hardproblem
10.3969/j.issn.1673-5692.2016.02.014
2016-02-21
2016-03-26
