一种基于评价变量的物理机虚拟化最优排布方法与流程

1.本发明涉及物理机虚拟化调度排布领域，具体而言是一种基于评价变量的物理机虚拟化最优排布方法。


背景技术：

2.在对大批量的虚拟机进行实例化的过程中，如何得出虚拟机实例化排布的最优解往往是人们所关心的重点。现有的虚拟机实例化技术主要可分为直接排布的首次适应算法和使用各种优化算法对排布解进行优化以求得目标变量最优解，进而得到最优排布解两种。
3.两种技术各有优缺点，其中首次适应算法对刚性约束的处理较好，但难以解决含有复杂条件的软性约束问题，对较难以逻辑流图表示的复合约束也难以实施；以模拟退火算法、遗传算法等非解析解算法为主的优化算法在无约束条件的情况下可以很好的求得目标变量的最优值，但在存在刚性约束的条件下难以部署，且存在初态序列解不易求得、随机化方式不统一、目标变量难以确定等问题。


技术实现要素：

4.本发明要解决的技术问题是克服现有技术的不足，提供一种能在硬性约束和复杂软性约束并存的情况下时，以首次适应算法的输出作为优化算法的输入值，得出大批量虚拟机实例化排布最优解的排布方法。
5.为了实现上述目的，设计一种基于评价变量的物理机虚拟化最优排布方法，所述方法如下：s1.执行约束-首次适应算法给出一个初始排布解；s2.以约束-首次适应算法的初始排布解输出作为优化算法的输入值；s3.采用优化算法，根据业务所需的软性约束，计算初始排布解的评价变量，并根据变量对虚拟机输入序列进行优化；s4.循环步骤s1-s3得到新的解，并最终根据评价变量的值或是总循环的次数结束上述的循环，得出本次虚拟机实例化排布的最优解。
6.本发明还具有如下优选的技术方案：1.所述约束-首次适应算法可分为如下的部分：获取可供分配的全部物理机列表及物理机自身条件的约束项，并将物理机按照自身约束条件进行分类；如果业务条件存在硬性约束，则根据约束内容选择出可用的物理机列表，根据全部可用物理机列表的资源余量，对物理机的虚拟化优先度进行排序。
7.2.所述约束-首次适应算法还包括根据首次适应算法，逐个对物理机排序后的序列进行遍历，若当前物理机允许实例化当前序列上的虚拟机，则对这一虚拟机进行实例化，以此遍历虚拟机序列，以对虚拟机序列进行实例化，给出一个初始排布解。
8.3.所述约束-首次适应算法还包括在遍历的过程中，需考虑业务上可能存在的其他硬性约束，如涉及到多台物理机，在选择物理机列表时无法排除的刚性约束；若虚拟机序列遍历结束时无未成功实例化的虚拟机，则将此时得出的排布解作为约束-首次适应算法
得出的初始排布解；若未成功实例化，可将原始的虚拟机序列进行随机化处理，然后再执行算法尝试求解；若一定次数尝试后仍无解，则可认定为该虚拟机序列无可用的排布解，报错。
9.4.所述优化算法可分为如下的部分：根据s1中得到的初始排布解，综合考虑业务场景下的软性约束条件，根据排布解与软性约束的符合度设计评价变量计算方式，从而计算出解的评价变量；根据具体的优化场景，选择合适的优化算法；根据软性约束条件，对评价变量进行设计，设计应考虑各个物理机及其所属变量间的相对权值关系，以及这些约束间的相对权值关系。
10.5.所述优化算法还包括根据优化算法，评价当前评价变量是否符合优化算法要求；若不符合要求，则依据上述流程更改原虚拟机序列，重新计算排布解与评价变量，直到评价变量的值满足相关要求；或是根据优化算法的迭代次数上限约束，结束循环；最终得出的排布解即为本最优排布方法下得出的最优排布解。
11.6.所述优化算法包括遗传算法、蚁群算法和模拟退火算法。
12.本发明同现有技术相比，其优点在于：1.一定程度上解决了现有虚拟机排布方法在硬性约束和复杂软性约束并存的情况下，难以设计求出软性约束最优解算法的问题。首先采用首次适应算法，保证得出的排布解满足刚性约束；然后再采用优化算法对软性约束问题进行求解，一定程度上避免了原有算法使用随机种子生成的解大量不符合刚性约束条件，以致影响算法求解速度的问题；2.具有较高的设计自由度。评价变量、优化算法的设计可以根据实际业务场景中的各项参数进行调整，具有较好的适配性和可移植性；3.处理刚性约束的首次适应-约束算法和优化算法独立为两个模块进行处理，降低了系统间的耦合度，有利于实际应用过程中二次开发和运行稳定性。例如，若一个系统想在原有刚性约束的基础上考虑对其部分业务变量的值进行优化，则可以考虑采用这一优化算法+评价变量的设计模式，而无需改动原有的处理模块；4.有利于优化机房、机柜的整体资源使用率，提高整个集群的运行稳定度。
附图说明
13.图1是本发明的约束-首次适应算法的流程图；图2是优化算法的流程图。
具体实施方式
14.下面结合附图对本发明作进一步说明，本发明的结构和原理对本专业的人来说是非常清楚的。应当理解，此处所描述的具体实施例仅用以解释本发明，并不用于限定本发明。
15.本发明提供了一种基于评价变量的物理机虚拟化最优排布方法，将约束-首次适应算法和优化算法相结合，以首次适应算法的输出作为优化算法的输入值，解决了初态序列解和二次随机化求解的问题；对于评价变量难以确定的问题，本算法采用了模糊层次分析法与评审-打分方式相结合，并综合考虑各个物理机状态和软性约束条件，对评价变量进行设计。
16.本算法用于计算物理机集群虚拟化时实例化排布的最优解。在以下实施方式中，在运营系统生产环境中进行，在配置管理数据库中部署。
17.图1和图2示出了该算法的流程示意图，该流程包括：用户提出新增虚拟机的工单。工单中的业务数据是一个列表，包括每台虚拟机的申请地点、申请逻辑柜、cpu核数、内存、磁盘占用空间，以及业务标记。业务标记包括该虚拟机所属的券商、软件商、使用lvs或直连等信息。这些业务数据主要决定算法中需考虑的刚性约束。
18.系统根据用户填写的工单，开始调用物理机虚拟化最优排布方法计算最优排布解。
19.如图1所示，首先执行首次适应-约束算法。
20.s101：用户提交需求后，计算的具体流程如下：s102：将同一批申请按照地点进行分类，并根据地点、逻辑柜、业务标记等信息，挑选出符合基本约束要求的可用物理机列表。在实际的筛选过程中，会根据不同的地点以及逻辑柜开始后续的算法流程。
21.s103：初始虚拟机序列为用户填写的序列顺序，每一地点、逻辑柜下的序列相互独立。
22.s104：选择一个地点下的某一逻辑柜作为算法处理的开始。遍历这一逻辑柜下的物理机列表，遵循一定的业务逻辑所规约的硬性约束，判断物理机是否符合约束要求；如此处的约束条件大致包括：物理机的cpu/内存/硬盘余量是否可容纳当前虚拟机实例化请求；放置后，物理机所在逻辑柜的总资源量和已使用空间量的比是否满足可用性要求；放置后，是否满足券商、软件商应用的“高可用”要求，做到分布式配置其应用实例。
23.s105：若本逻辑柜下的物理机均不符合要求，则可选择同一地点下的其他逻辑柜进行遍历。第一轮循环时，若所有逻辑柜均不符合要求，则对原始的虚拟机序列进行随机排布，重新求解。
24.s106：记最大容错重演次数为，则若经过了次重演后仍无法实例化所有虚拟机，就判定该请求无解。
25.s107：非第一轮循环时，选取最后一次接受的虚拟机序列重新进行s208中的随机调换过程。若经过了次调换后仍无解，则以最后一次接受的虚拟机序列所对应的排布解作为返回的解，并跳转到s204。
26.s108：若可求出排布解，则该排布解为该虚拟机序列的一个排布解。记此时的虚拟机序列为。
27.求出初始排布解后，根据软性约束条件，执行优化算法计算步骤。在这一实施例中，使用模拟退火算法作为优化算法。
28.如图2所示，计算的具体流程如下：s201：根据排布解，求出这一排布解的评价变量，这一变量为一个向量，每个该排布中所涉及的逻辑柜所属的所有物理机计算得出该向量中的一个分量，每个逻辑柜的值单独计算，其由如下的公式所生成：
其中，和为如下所述的两个部分分别计算而得。和是这两个部分评价变量的权重值，用于计算出总评价变量。这些值在本实施例中采用模糊层次分析法结合专家-用户打分的方式计算而得，因此权的值总满足和为1，求出所有评价变量的范围也总在0-1区间中。同理，最终的评价变量值也为各个逻辑柜加权平均计算而得的值。后续的计算过程中也将用到权值，其计算算法与此处一致，不再赘述。
29.在本实施例中，评价变量由预留资源量检验和各资源占用量一致性检验两个部分决定。评价变量的值越小，代表系统中符合预留资源要求的主机占比越高，各台物理机上各个资源的占用比例越均衡。这两个部分各自的计算方式如下：预留资源量检验部分为对每个物理机根据其业务标签所设置的内存、cpu及磁盘资源预留量限制，分别计算在当前排布解下有多少物理机在怎样的程度下满足限制。记该部分评价变量为 ，则有其中，对于的每个分量而言，其计算方式都是根据所对应的那一台物理机是否满足约束条件而定的。下式中， 为当前余量， 为约束条件中设置的预留量。
30.各资源占用量一致性检验代表同一台物理机上各资源占用的比例是否均衡。记该部分评价变量为 ，则有其中，其中，由于本实施例中每台物理机只有三个均衡性指标，因此 ， 由三个范围在[0,100]的变量求得。 这个值代表每台物理机上各资源占用比例的离散程度。
[0031]
s202：计算出排布解的评价变量后，设置模拟退火算法的初始温度 、目标温度两个参数变量。首次循环时，记当前最优变量 为 ，从而在首次循环时总是接受目前的虚拟机排布序列和其所对应的评价变量的值，并根据业务需求设置目标最优变量为。
[0032]
s203：根据本次循环的评价变量，记。若，,则接受本轮循环
所对应的虚拟机序列。
[0033]
否则，按照当前的退火温度，按照一定的概率接受当前序列，接受概率为其中k为目前已经过的循环轮数。
[0034]
之后，改变当前温度为 。
[0035]
s204：若温度已达到结束条件，则结束循环，并将当前的排布解和虚拟机序列作为用户需求的返回值。
[0036]
s205：否则，若接受新序列，则检验当前的评价变量是否已满足初态时所设置的目标最优变量的值。若已满足，则结束循环，并将当前的排布解和虚拟机序列作为用户需求的返回值。
[0037]
s206：若不接受当前序列，则取上一次记录的最后接受序列为下一轮循环的虚拟机序列。
[0038]
s207：若未满足最优变量的值，则取新序列为下一轮循环的虚拟机序列。
[0039]
s208：之后，根据初始化时所生成的随机种子，随机调换当前接受的虚拟机序列中至多2个目标的顺序。
[0040]
s209：跳转到s104再次对这一序列进行计算，直到流程返回解。
[0041]
需注意，本算法实施例仅为说明算法的一般工作流程而编写，流程中具体的实现方式可能因具体部署环境的不同而不同，如计算过程中分配的权值由具体工程中开发人员与专家的评估而定，优化算法可利用遗传算法、蚁群算法等而不局限于模拟退火算法，而算法实施具体过程中的评价变量设计、一致化方法、退火初温、速率等因素均可进行调整。
[0042]
以上所述，仅为此发明的具体实施方式，但本发明的保护范围不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，根据本发明的技术方案和新型的构思加于等同替换或改变，都应涵盖在本发明的保护范围之内。

技术特征：
1.一种基于评价变量的物理机虚拟化最优排布方法，其特征在于所述方法如下：s1.执行约束-首次适应算法给出一个初始排布解；s2.以约束-首次适应算法的初始排布解输出作为优化算法的输入值；s3.采用优化算法，根据业务所需的软性约束，计算初始排布解的评价变量，并根据变量对虚拟机输入序列进行优化；s4.循环步骤s1-s3得到新的解，并最终根据评价变量的值或是总循环的次数结束上述的循环，得出本次虚拟机实例化排布的最优解。2.如权利要求1所述的一种基于评价变量的物理机虚拟化最优排布方法，其特征在于所述约束-首次适应算法分为如下的部分：获取可供分配的全部物理机列表及物理机自身条件的约束项，并将物理机按照自身约束条件进行分类；如果业务条件存在硬性约束，则根据约束内容选择出可用的物理机列表，根据全部可用物理机列表的资源余量，对物理机的虚拟化优先度进行排序。3.如权利要求2所述的一种基于评价变量的物理机虚拟化最优排布方法，其特征在于所述约束-首次适应算法还包括根据首次适应算法，逐个对物理机排序后的序列进行遍历，若当前物理机允许实例化当前序列上的虚拟机，则对这一虚拟机进行实例化，以此遍历虚拟机序列，以对虚拟机序列进行实例化，给出一个初始排布解。4.如权利要求3所述的一种基于评价变量的物理机虚拟化最优排布方法，其特征在于所述约束-首次适应算法还包括在遍历的过程中，需考虑业务上可能存在的其他硬性约束，如涉及到多台物理机，在选择物理机列表时无法排除的刚性约束；若虚拟机序列遍历结束时无未成功实例化的虚拟机，则将此时得出的排布解作为约束-首次适应算法得出的初始排布解；若未成功实例化，可将原始的虚拟机序列进行随机化处理，然后再执行算法尝试求解；若一定次数尝试后仍无解，则可认定为该虚拟机序列无可用的排布解，报错。5.如权利要求1或4所述的一种基于评价变量的物理机虚拟化最优排布方法，其特征在于所述优化算法分为如下的部分：根据s1中得到的初始排布解，综合考虑业务场景下的软性约束条件，根据排布解与软性约束的符合度设计评价变量计算方式，从而计算出解的评价变量；根据具体的优化场景，选择合适的优化算法；根据软性约束条件，对评价变量进行设计，设计应考虑各个物理机及其所属变量间的相对权值关系，以及这些约束间的相对权值关系。6.如权利要求5所述的一种基于评价变量的物理机虚拟化最优排布方法，其特征在于所述优化算法还包括根据优化算法，评价当前评价变量是否符合优化算法要求；若不符合要求，则依据上述流程更改原虚拟机序列，重新计算排布解与评价变量，直到评价变量的值满足相关要求；或是根据优化算法的迭代次数上限约束，结束循环；最终得出的排布解即为本最优排布方法下得出的最优排布解。7.如权利要求5或6所述的一种基于评价变量的物理机虚拟化最优排布方法，其特征在于所述优化算法包括遗传算法、蚁群算法和模拟退火算法。

技术总结
本发明涉及物理机虚拟化调度排布领域，具体而言是一种基于评价变量的物理机虚拟化最优排布方法。所述方法如下：S1.执行约束-首次适应算法给出一个初始排布解；S2.以约束-首次适应算法的初始排布解输出作为优化算法的输入值；S3.采用优化算法，根据业务所需的软性约束，计算初始排布解的评价变量，并根据变量对虚拟机输入序列进行优化；S4.循环步骤S1-S3得到新的解，并最终根据评价变量的值或是总循环的次数结束上述的循环，得出本次虚拟机实例化排布的最优解。本发明同现有技术相比，其优点在于：一定程度上解决了现有虚拟机排布方法在硬性约束和复杂软性约束并存的情况下，难以设计求出软性约束最优解算法的问题。计求出软性约束最优解算法的问题。计求出软性约束最优解算法的问题。


技术研发人员：田秋实 赵洋明 王波 裘岱 张晓军 何帅兵 孙志峰
受保护的技术使用者：上证所信息网络有限公司
技术研发日：2023.04.25
技术公布日：2023/8/13