一种公平和效率均衡的虚拟机调度系统及方法

摘要

本发明公开了一种公平和效率均衡的虚拟机调度系统及方法，包括集群资源监控模块，任务请求处理模块，调度器核心模块和虚拟机开启模块，任务请求处理模块接收来自上一级中心调度器的任务请求，转发给调度器核心模块；调度器核心模块分别与集群资源监控模块、任务请求处理模块和虚拟机开启模块相连，调度器核心模块从集群资源监控和任务请求处理模块获取信息，完成处理后传递至虚拟机开启模块，虚拟机创建至物理节点，最终完成虚拟机调度过程。本发明综合考虑分配的公平性和任务通信要求，按照公平原理分配资源，对分配的中间结果按照任务通信要求进行状态合并，达到对分配结果的优化，获得更为合理的组态，实现任务执行效率和集群负载的综合优化。

说明书

技术领域

本发明涉及计算机科学与技术领域，更进一步涉及云计算中的IaaS(Infrastructure as a  Service，即基础设施即服务)领域，具体是一种公平和效率均衡的虚拟机调度方法。本发明 可以用于云计算平台的调度器组件中，为云计算平台提供更为合理的调度策略支持，获得更 为合理的虚拟机分配组态。

背景技术

计算技术的不断发展，以及用户应用需求的多样化，使得应用提供商给出越来越多样化 的解决方案，而这样会造成资源的浪费以及适应不同平台而造成的开销。云计算通过使用虚 拟化技术对底层的物理资源进行重组和虚拟化，形成了巨大的资源池，计算中心将这些资源 以弹性、动态的服务方式提供给用户，使得用户能够以一种极易的方式获得所需的计算服务 (计算，网络，存储，安全等)。

在云计算环境下，用户以租赁的形式购买所需的计算资源。通过SDN实现的虚拟路由 器和交换机，在隔离的网络环境下部署自己的私有云。或者与现有的计算环境通过安全隧道 连接，形成公私兼顾的混合云。

虚拟化使得物理资源得到了有效的隔离，使得不同的服务可以无干扰的运行在物理节点 上，最大化的复用物理资源。在某些特殊的任务中，如要求通信代价最低化，共享物理节点 的虚拟机分配方案将是一个很好的决策。因此，在保证SLA和QoS的前提下，如何保证整 个集群资源公平分配和任务高效执行一直是一个热点问题。

调度模块处于云计算控制中的核心位置，是云计算得以大规模应用和提高系统性能的关 键组件。用户的任务请求是一个随机的、弹性的过程，需要根据集群的当前状态和实际请求 以确定虚拟机的目标开启位置。在迁移和容灾部分，调度器也充当着重要的角色，当决策系 统判定某个虚拟机需要迁移时，请求调度器得到一个新的开启位置。

目前典型的调度方法如下：

1)过滤器静态策略。调度器在接收到系统的请求后按照主机的条件进行过滤，对满足请 求条件的主机进行权值排序，得到满足请求条件的主机集合。该方法从平台的负载角度考虑， 使整个集群的负载趋于均衡。

2)最大化集群利用率。对于请求，每次从集群队列里选择一个剩余资源最小的节点，如 果满足则放置在该节点，否则寻找下一个节点(First fit过程)。该方法使得集群中物理节点 的使用量少。

3)随机分配。对于请求，每次从满足条件的主机列表里随机挑选一个主机进行放置。

4)动态迁移。基于虚拟机迁移技术，用最佳适配算法宣召迁移目标主机，通过约束资源 利用率的方法，达到集群负载平衡和节能的目的。

上述方法在云计算环境下有各自的局限性：

1)静态策略使得调度策略没有动态特性，并且负载均衡仅仅从集群的角度考虑，忽略了 虚拟机之间的关联关系。调度器降低了有协同需求的虚拟机之间高效协作的可能性，从而影 响了需要协同计算的多个大型应用的服务质量。

2)最大化集群利用率减少了物理机使用的数量，但是物理集群偏负荷运行，如果某一物 理节点宕机将造成大量的虚拟机宕机。

3)随机分配增加了控制部分的不可控性，调度器无法关联分配，降低了高效协同的可能 性。由于随机行为的特性，容易造成某些极端情况，导致系统运行效率低下。

4)动态迁移技术为调度带来了动态特性，但是也带来了调度成本的增加，如虚拟机瞬时 运行状态的保存、虚拟镜像副本迁移等问题。

综上所述，目前典型的虚拟机调度方法仅仅从静态策略配置、单主机利用率、集群负载 等角度考虑，而忽略了任务的属性，降低了任务的执行效率。

发明内容

为了解决虚拟机调度的技术问题，弥补现有方案的不足，使得虚拟机请求得到合理的放 置，提高集群利用率，并考虑任务间相关性的特点，本发明提出了一种云计算环境下公平和 效率均衡的虚拟机调度系统及方法。

该方法综合考虑分配的公平性和任务通信要求，首先按照公平原理分配资源，然后对分 配的中间结果按照任务的通信要求进行状态合并，通过状态合并达到对分配结果的优化，以 获得更为合理的组态，实现任务执行效率和集群负载方面的综合优化。

调度器提供的是统一资源隔离，为不同框架的不同任务提供所需要的资源。调度器的运 行需要多个模块的相互配合。

本发明提供一种公平和效率均衡的虚拟机调度系统，包括：

集群资源监控模块，用于集群的资源监控信息，将该息存入控制节点的nova数据库中， 调度器和容灾模块调用这些信息获取集群的当前状态；

任务请求处理模块，用于接收上一级主控制中心调度器分发下来的任务请求，该请求由 JSON形式的任务描述文件表示；

调度器核心模块，用于解析任务请求处理模块的请求数据，并结合集群当前的状态完成 决策并合并结果集，产生最终的分配方案；

虚拟机开启模块，用于调度器核心模块产生的结果集形式为请求—目标主机，在原有API 的基础上通过指定availability_zone参数包装为新的API；该API完成虚拟机在指定位置的开 启，并通过临时模板机制实现分配集的精确匹配，最终完成对虚拟机的开启和模板移除；

所述任务请求处理模块与调度器核心模块相连，调度器核心模块分别与集群资源监控模 块、任务请求处理模块和虚拟机开启模块相连，调度器核心模块从集群资源监控和任务请求 处理模块获取信息，完成处理后传递至虚拟机开启模块。

进一步地，所述调度器核心模块包括：用于加载任务请求信息的loader模块、用于从监 控数据库获取当前的集群资源情况host_aux模块、于执行Packing DRF迭代过程schedule_first 模块和用于执行合并过程schedule_second模块。

进一步地，所述schedule_second模块包含了build_param、solu和merge方法，build_param 方法用于构造参数方程；solu方法用于求解状态合并方程；merge方法用于执行具体的虚拟机 合并过程。

本发明进而提供一种公平和效率均衡的虚拟机调度方法，包括下述步骤：

S1：集群资源监控模块定期收集系统的资源监控信息，并将信息存入数据库节点的 nova.compute_nodes表中；

S2：任务请求处理模块接收来自上一级主控制中心调度器的任务请求，转发给调度器核 心模块；

S3：调度器核心模块中的loader模块加载任务请求，包括memoryRequire、networkRequire 和CPURequire信息；

S4：调度器核心模块中的host_aux模块从监控信息数据库获取当前集群的资源情况，包 括memory_mb、memory_mb_used、vcpus、vcpus_used、network以及hypervisor_hostname信 息；

S5：将用户的资源请求作为要分配的资源池，当多个资源请求到来的时候将这些资源请 求作为分配给物理机的总资源，记为R；

S6：将集群的资源向量作为实际的请求向量，记为D；

S7：调度器核心的schedule_first模块执行资源的迭代计算，即Packing DRF过程，该过 程结束后返回分配结果T；

S8：调度器核心的schedule_second模块执行合并过程；

S9：调度器核心的schedule_second模块完成对初始分配集T的合并，得到最终结果集T’， 输出T’；

S10：执行虚拟机创建至物理节点，最终完成虚拟机调度过程。

进一步地，所述步骤S7中，执行资源的迭代计算，Packing DRF过程结束后返回分配结 果，具体过程如下：

S7a：调度器核心模块中的schedule_first模块按照公平性分配资源进行Packing DRF过程 执行资源的迭代计算，保证分配的公平特性；

S7b：Packing DRF过程结束后返回分配结果，结果集形式为T[{CPU:MEM:HOST}]，其 中A(j,i)为true代表j虚拟机被分配给i主机，代表请求配置为{CPU,MEM}的虚拟机被分配至 hypervisor_hostname为HOST的节点。

进一步地，所述步骤S8中，调度器核心模块执行合并过程，通过下述方法实现：

S8a：调度器核心模块中的schedule_second模块的输入为步骤S7b的输出，加载输入；

S8b：schedule_second模块中的build_param方法根据请求构造参数方程；

S8c：schedule_second模块中的solu方法完成求解状态合并方程，得到一条 E-F(Efficiency-Fairness)曲线，由曲线得到一个阈值α，在(0，α)区间的值将获得最大收益E， 即Max E，而在(α，1)之间将随着公平性的增加而导致收益的下降；

S8d：schedule_second模块中的merge方法维护一个优先级队列，根据阈值α将满足合并 条件的虚拟机合并；如果这个合并请求的并入带宽和原有带宽之和小于带宽容量，则合并这 两个节点(loopback的容量认为是极大值)，否则停止；或者该主机不再允许更多的虚拟机开 启，停止合并。

进一步地，所述步骤S10中，通过下述方法实现：

S10a：按照步骤S9产生的结果集T’开启虚拟机，调度器动态生成虚拟机模板P，以模板 P构造API参数；

S10b：步骤S10a成功后，删除临时模板P，否则，进入步骤S10c；

S10c：删除临时模板P，结束。

本发明与现有的技术方案相比，具有如下的有益效果：

1)本发明在考察公平性的基础上，通过反向迭代分配，执行Packing DRF过程保证分配 的公平特性。

2)本发明在考察任务相关性的基础上，通过分析虚拟机任务的属性，将任务的通信请求 因子作为合并状态的优化方向，从而提高了有协同需求的虚拟机之间高效协作的可能，提升 了任务执行的效率。

3)本发明由于采用了模块化的技术，保证系统的灵活可扩展性强，可灵活接入更多的算 法模块。

4)本发明可用于通用云计算平台下，提供瞬时的全局分配策略，可支持决策后并行开启 虚拟机的高并发需求。本发明可以为容灾组件提供定点开启虚拟机的支持，更好的服务于系 统其它组件。

5)本发明包含精确匹配模块，相比最邻近适配算法，降低了资源浪费，提高了系统的灵 活性。

附图说明

图1是本发明的系统架构图，

图2是本发明的执行流程图，

图3是本发明合并状态的一个示例模型图，

图4是本发明合并过程中求解E-F曲线的一个示例图，

图5是本发明合并虚拟机目标位置的示例图，

图6是本发明执行虚拟机创建至物理节点的流程图，

图7是本发明性能对比测试图，

图8是本发明计算任务部署测试对比图。

具体实施方式

下面结合附图对本发明做进一步详细说明。

如发明内容描述，本发明包括了下述两点：

1)一种虚拟机放置策略的系统；

2)基于公平与效率考虑的调度流程。

其中，调度方法是本发明的重点，即从当前集群中选择最满足策略的虚拟机放置方案。 本方法采用了一种两步调度机制，首先是基于集群资源考虑的公平性方案，产生满足公平特 性的分配初集T；其次是考虑节点间的通信要求，利用带宽模型寻找公平和效率的关系，得 到一条E-F曲线，构造优先级队列执行合并过程。本方法综合考虑集群和任务特性，通过状 态合并达到对分配结果的优化，以获得更为合理的组态。

如图1所示，本发明的系统构成包括：

1.集群资源监控模块

该模块负责定期收集物理机的集群的资源监控信息，包括CPU利用率、内存使用情况、 网络带宽信息，这些信息存入控制节点的nova数据库中，调度器和容灾模块调用这些信息获 取集群的当前状态。

2.任务请求处理模块

负责接收上一级主控制中心调度器分发下来的任务请求，该请求由JSON形式的任务描述 文件表示。

3.调度器核心模块

解析任务请求模块的请求数据，并结合集群当前的状态完成决策并合并结果集，产生最 终的分配方案。

4.虚拟机开启模块

调度器产生的结果集形式为{请求—目标主机}，为此在原有API的基础上通过指定 availability_zone参数包装为新的API。该API完成虚拟机在指定位置的开启，并通过临时模 板机制实现分配集的精确匹配，最终完成对虚拟机的开启和模板移除。

参见图1所示，任务请求处理模块与调度器核心模块相连，调度器核心模块分别与集群 资源监控模块、任务请求处理模块和虚拟机开启模块相连，调度器核心模块从集群资源监控 和任务请求处理模块获取信息，完成处理后传递至虚拟机开启模块。

其中，调度器核心模块包括：用于加载任务请求信息的loader模块、用于从监控数据库 获取当前的集群资源情况host_aux模块、于执行Packing DRF迭代过程schedule_first模块和 用于执行合并过程schedule_second模块。

schedule_second模块包含了build_param、solu和merge方法，build_param方法用于构造 参数方程；solu方法用于求解状态合并方程；merge方法用于执行具体的虚拟机合并过程。

本方案的方法步骤包括：

一、集群资源监控

结合图1中的集群资源监控部分，本部分的具体实现如下：

S1：包括两部分：

1)集群资源监控模块定期收集系统的资源监控信息。

2)监控组件的slave monitor与主节点(Collector)数据库通信，并将监控数据信息存入 数据库节点的nova.compute_nodes表中。

二、任务请求解析

S2：任务请求处理模块接收来自上一级(中心调度器)的任务请求，转发给调度器核心 模块。

S3：调度器核心模块中的loader模块加载任务请求，解析请求JSON描述文件，提取包 括memoryRequire、networkRequire和CPURequire信息，维护请求队列信息。

三、调度器核心

结合图1的调度器核心部分，本部分的具体实现如下：

S4：调度器核心模块中的host_aux模块从监控信息数据库获取当前集群的资源情况，包 括memory_mb、memory_mb_used、vcpus、vcpus_used、network以及hypervisor_hostname信 息。

S5：将用户的资源请求作为要分配的资源池，当多个资源请求到来的时候将这些资源请 求作为分配给物理机的总资源，记为R。

S6：将集群的资源向量作为实际的请求向量，记为D。

S7：调度器核心的schedule_first模块执行资源的迭代计算，即Packing DRF过程，该过 程结束后返回分配结果，具体包括：

S7a：调度器核心的schedule_first模块执行Packing DRF(如伪代码Algorithm Packing  DRF所示)资源的迭代计算，该过程按照公平性分配资源，保证分配的公平特性，即Packing  DRF过程。

Packing DRF迭代计算由schedule_first模块完成，在计算过程中仅使用JSON请求中的两 个维度，即D[{CPU,MEM}]，其中CPU指的是所需要CPU的核数(如2，代表请求虚拟机 需要两个vCPU)，MEM是内存的大小(如1，代表1GB内存)。

S7b：Packing DRF过程结束后返回分配结果。Packing DRF算法基于公平性，考虑主机的 优势资源占比(即Dominant Share)作为选择依据。通常将调度算法施加于任务级的调度中， 为任务分配诸如带宽或者CPU时间等资源。而考虑到虚拟机放置策略方面，该问题却是一个 0-1背包问题。经过步骤III的角色变换以及0-1特性变换，Packing DRF过程将产生一个结果 集，其中A(j,i)为true代表j虚拟机被分配给i主机，结果集形式为T[{CPU:MEM:HOST}]， 代表请求配置为{CPU,MEM}的虚拟机被分配至hypervisor_hostname为HOST的物理节点。

Packing DRF的计算步骤如Algorithm Packing DRF所示：

参照图2所示，Packing DRF过程结束后的输出T为合并过程的输入。本步骤中的执行过 程如伪代码Algorithm Merge所示。

S8：调度器核心模块执行合并过程，具体包括：

S8a：调度器核心模块的schedule_second模块完成初始化，加载输入为步骤S7b的输出， 加载输入，执行合并过程。

S8b：schedule_second模块中的build_param方法根据请求构造参数方程。

其模型变量定义如下表所示：

那么节点i和j间的收益可以定义如式-1所示，

$R_{\mathrm{ij}}\times \underset{[m,n]\in {\mathrm{Link}}_{\mathrm{ij}}}{\Sigma }{P}_{\mathrm{ij}}(m,n)$  (式-1)

那么总的收益E如式-2所示，

$\underset{[i,j]\in \mathrm{Con}}{\Sigma }\underset{[m,n]\in {\mathrm{Link}}_{\mathrm{ij}}}{\Sigma }{P}_{\mathrm{ij}}(m,n)$  (式-2)

f(i,j)是步骤IV中经过Packing DRF过程计算的分配方案，而在上一步中由于考量的是 CPU和MEM，因此f(i,j)等价于步骤V中的请求向量。

定义式-3：

$\mathrm{MaxE}=\underset{[i,j]\in \mathrm{Con}}{\Sigma }\underset{[m,n]\in {\mathrm{Link}}_{\mathrm{ij}}}{\Sigma }{P}_{\mathrm{ij}}(m,n)$  (式-3)

其中,α代表公平因子，Capacity(m,n)代表总带宽容量，

R_ij＞αf(i,j)  (式-4)

S8c：schedule_second模块中的solu方法完成求解状态合并方程，得到一条 E-F(Efficiency-Fairness)曲线，由曲线我们可以得到一个阈值α，那么在(0，α)区间的值将获 得最大收益E，即Max E，而在(α，1)之间将随着公平性的增加而导致收益的下降。

S8d：schedule_second模块中的merge方法维护一个优先级队列，根据阈值α将满足合并 条件的虚拟机合并。如果这个合并请求的并入带宽和原有带宽之和小于带宽容量，则合并这 两个节点(loopback的容量认为是极大值)，否则停止；或者该主机不再允许更多的虚拟机开 启，停止合并。

S9：步骤S8完成对初始分配集T的合并，得到最终结果集T’，输出T’。

图3是合并状态的一个示例模型图，其中VM节点之间的连接线代表虚拟机之间的通信 需求。

图4是合并过程中求解E-F曲线的一个示例图。如图4，在结果集T的基础上，得到步骤 V c的计算结果。其中α的值为0.33，那么在(0,0.33)区间的值将获得Max E，而在(0.33,1)之 间将随着公平性的增加而导致收益E的下降，0.33为阈值。

图5是合并虚拟机目标位置的示例图，该任务有3个虚拟机请求，经过步骤IV，分别被 分配至Host1、Host2和Host4。初始分配至Host4的虚拟机通过步骤V过程被合并至Host1。 最终的分配集T’即两台虚拟机被分配至Host1，一台虚拟机被分配至Host2。

四、虚拟机开启

S10：执行虚拟机开启，最终完成虚拟机调度过程。

参照图1的虚拟机开启部分和图6的流程，本部分的具体实现如下：

步骤T1，根据最终分配集T’生成临时模板P。

步骤T2a，模板P已经存在，直接调用模板P构造API调用，进入步骤T3；

步骤T2b，模板P生成成功，构造API调用，进入步骤T3；

步骤T2c，模板P生成失败，进入步骤TE。

步骤T3，是否继续创建，若是，删除临时模板P，进入步骤T2；否则跳转至步骤T4。

步骤T4，删除临时模板P，成功返回。

步骤TE，模板生成失败，异常。

五、性能测试

本发明的效果可以通过以下实验进一步说明：

1)测试条件

采用真实机器和仿真测试本发明的性能，采用Python语言实现了本发明的开发，编写 test_specific.py脚本测试时间开销。

2)测试任务

2a)测试本发明与默认调度器调度结果对任务运行时性能带来的开销对比

2b)测试本发明与默认调度器调度结果对虚拟机开启时延的开销对比

3)结果分析

图7是本发明对特定任务执行时间的测试。在虚拟机请求中，若各虚拟机节点间没有通 信要求，那么schedule_second过程将不改变schedule_first过程的结果，分配满足公平特性。 如果虚拟机节点拥有通信要求，则在满足约束的条件下执行状态的合并，将部分虚拟机合并 至同一台物理机，实验测试表明，拥有通信要求的任务主要性能损耗来自于通信时延。集群 的网络配置是百兆链路，千兆以太网接口卡，即不同位置的虚拟机通信通过百兆链路进行通 信，跨本地交换机或者通过IPv6网络进行广域通信，而处于同一物理机的虚拟机通信则通过 SDN组件的软件交换实现。对比图7测试数据，本发明的优化分配结果可以将任务的执行效 率提升7％左右。

图8主要针对调度结果对虚拟机开启的影响。目前的计算任务部署于Windows764位镜 像中，在制作镜像的时候选择安装的最小尺寸15GB。由于计算任务的特殊性质，目标程序被 封装至定制的镜像中,将定制镜像上传至镜像管理节点。部署阶段，镜像需要从管理节点下载 完整的镜像，这个时间将对任务执行效率带来严重的影响。镜像首次启动的时间主要来自于 获取镜像副本的耗时，在测试环境下，约68MB/s，而以缓存方式启动的虚拟机不受镜像大小 的限制，在28秒左右开启虚拟机。因此，合理的调度将大幅缩减传输镜像副本的时间消耗。 如图8所示，本发明在部署阶段减少了镜像副本获取的时间，缩减了虚拟机开启的时延，提 升了虚拟机内部署任务的执行效率。

从实验数据和仿真测试数据可以看出，考虑任务的通信带宽要求，并结合集群的状态分 配一个更为科学的组态是合理的。而且这种需求是现实存在的，我们可以通过在公平和效率 之间寻找一种权衡指标来达到整个系统性能的优化。