基于遗传算法的容器集群调度算法研究摘要: 轻量级虚拟化技术Docker 及Docker 集群管理工具Swarm 的出现，为基于Linux 平台的集群资源虚拟化提供了一套简单高效的解决方案。
但是，能否充分发挥一个集群的整体性能，一个好的调度策略至关重要。
为了提升传统Docker 集群调度策略的负载均衡性能和增加多任务并发调度能力，文中提出了基于遗传算法的Docker 集群调度策略。
该策略将多个任务合并成一个调度组，并生成相应调度结果作为种群个体; 然后结合任务负载模式、节点当前负载状态及硬件性能计算集群负载均衡值并作为个体适应度; 最后利用遗传算法筛选出全局近似最优解作为调度结果．关键词: Docker; 容器技术; 调度策略; 遗传算法; 序关系;Research on container cluster scheduling algorithmbased on genetic algorithmAbstract: Docker, a lightweight virtualization technology, and Swarm, a Docker cluster management tool, emerged, providing a set of simple and efficient solutions for cluster resource virtualization based on Linux platform.However, a good scheduling strategy is crucial to give full play to the overall performance of a cluster.In order to improve the load balancing performance of traditional Docker cluster scheduling strategy and increase the concurrent multi-task scheduling capability, this paper proposes a Docker cluster scheduling strategy based on genetic algorithm.The strategy combines multiple tasks into a scheduling group and generates scheduling results as individuals.Then, the cluster load balancing value is calculated as individual fitness by combining the task load mode, current load state of nodes and hardware performance.Finally, the global approximate optimal solution is selected by genetic algorithm as the scheduling result.Key words: Docker;Container technology;Scheduling strategy;Genetic algorithm;Order relation;1 引言Docker Swarm是一个Dockerized化的分布式应用程序的本地集群，其主要作用是把若干台Docker主机抽象为一个整体，并且通过一个入口统一管理这些Docker主机上的各种Docker资源。
Swarm和Kubernetes比较类似，但是更加轻，具有的功能也较kubernetes更少一些。
它的默认调度策略是Spread ，它是根据没有被分配的内存量，以及节点CPU核心数来查看资源消耗最少的节点，然后在这个资源消耗最少的节点上运行容器。
卢胜林等提出的权值调度策略，使用节点的内存使用率、CPU 使用率、网络平均负载以及该节点已经为容器分配出去但未被使用的内存占比，再根据加权公式计算出节点的负载来进行调度。
但这两种策略存在如下问题:1）没有考虑资源需求类型。
如有的是计算密集型，有的是内存资源消耗型。
2）不支持多任务调度。
如今的时代急需多任务调度带给我们便利。
3）衡量节点负载状态的性能指标不全面，并且未考虑节点自身的硬件性能。
针对上述Docker 容器调度策略存在的不足，文中提出了基于遗传算法的Docker 集群调度策略。
为支持多任务调度，文中将多个任务合并成任务组，把任务组调度结果作为个体，通过遗传算法筛选出全局近似最优解;为了能更加准确地衡量集群负载均衡情况，文中将CPU、内存、硬盘I/O 以及网络流量的负载情况纳入考量范围。
2 模型及相关概念2.1策略核心思想文中策略的设计思路是:①在一个拥有有限节点的Docker集群上运行一组容器任务，必定存在一个最优的调度结果，使得若按此结果调度，集群负载最为均衡，这可以归结为一个背包问题;②容器在一个节点上运行时，其所占用的资源L 既与节点硬件性能P有关，又与容器本身对资源Ｒ的需求有关，它们之间存在着一个函数关系L = F(P，R)，由此可以预测出按某一给定方案调度后各节点各项资源的负载变化情况。
根据以上思路，文中将一组任务的调度结果抽象成个体的基因，预测出按此结果调度后集群总体负载情况，并将其作为个体适应度，利用遗传算法搜索全局解空间，找到全局近似最优解作为调度结果。
与之相比，传统调度策略缺乏全局性考虑。
在多任务调度时，传统策略只能进行串行化调度，效率低，而文中策略是对一组任务进行并发调度，提升了效率。
在衡量负载的指标上，传统调度策略往往只考虑CPU 和内存使用率，不够全面，而文中策略综合考虑内存利用率、 CPU 、硬盘 I/O 和网络负载的影响。
在策略执行过程中，根据一组任务 12(,,,)n T T T T =，收集任务i T 的资源需求，形成多个任务调度方案12(,,,)n S s s s =(S 为个体基因，i s 为处理任务i T 的物理节点编号)，此为种群初始化。
然后收集节点硬件性能信息P ，通过 L = F(P ，R)预测出以结果S 调度后节点资源负载的变化L ，再综合所有节点的L 计算出集群负载的均衡程度net IO CPU m em Q w Q w Q w Q w Q 4321+++=，其中 4321w w w w 、、、为每项资源均衡程度在衡量总体负载均衡时的权重，net IO CPU m em Q Q Q Q 、、、分别为节点的 CPU 利用率、内存利用率、硬盘 I/O 负载和网络负载的标准差。
将 1 /Q 作为个体S 的适应度 ( 标准差越大，说明节点间负载越不均衡，个体的适应度越小)，用遗传算法的选择操作淘汰不良个体，保留优秀个体，并通过交叉、变异等操作搜索整个解空间，最终获得全局近似最优解best S 。
2.2 容器任务资源参数设定1．内存利用率设定容器任务运行时需要的内存大小'M ，获取不同节点的内存总量M ，计算该容器任务在不同节点上运行时对节点内存资源的需求mem N :M M N mem '=2．CPU 利用率一个任务对CPU 资源的需求，不能直接设定一个固定的值代表该任务运行时对CPU 的利用率，因为一个程序运行时对CPU 的利用率与程序的机器指令数和CPU 的主频大小密切相关，所以对同一程序而言(指令数一定)，在不同主频的CPU 下运行，对CPU 的利用率是不同的(与主频成反比)。
又由于当前CPU 基本上是多核心的，实际对CPU 的整体利用率还和核心数目有关。
因此容器任务在不同节点上运行时对CPU 资源的需求是根据节点CPU 主频以及核心数目自适应变化的，计算公式为：''N H C H N ii CPU = 式中，CPU N 是任务对 CPU 资源的需求 ( CPU 利用率)，'N (由用户设定)是在主频为'H 的 CPU 上运行该任务时 CPU 的利用率，i C 和i H 分别是节点i 的CPU 核心数和主频。
3． I/O 负载每秒的输入输出量(或读写次数) IOPS 是衡量硬盘性能的主要指标之一． 它主要受硬盘的寻址时间、旋转延时、传输时间和等待时间的影响，其中寻址时间、旋转延时是硬盘出厂时的固定参数;传输时间则与硬盘最大传输速率和单次 I/O 数据块的大小有关;等待时间是在单次 I/O 操作中不进行 I/O 的时间。
因此在不同的节点上，容器任务对硬盘 I/O 资源的需求是随节点硬盘性能参数自适应变化的。
设定容器任务单次I/O 的等待时间w t (ms)和单次I/O 数据块的大小 c(MB)，进而可以获得该任务所需要的IOPS(IOPS N ):w s IOPS t mc r t N ++⨯+=21000601000 式中，s t 为硬盘的寻址时间，r 为硬盘的转速(r/min)，m 为硬盘最大传输速率。
w s t mc r t ++⨯+2100060为进行单次 I/O 所需的时间(ms)。
再计算进行单次I/O 数据块大小为c 的满负荷I / O 操作时最大的IOPS 值)(max,IOPS N :mc r t N s IOPS +⨯+=21000601000max, 即可获得该任务所需的 I/O 负载大小：IO PS IO PS IO N N N max,=4．网络负载在计算网络负载时，文中将容器运行需要的带宽大小B 作为网络资源需求参数，然后根据不同节点所拥有的总带宽total B 计算出该容器任务在不同节点运行时对节点网络资源的需求total net B B N =。
3基于遗传算法的调度策略3.1适应度函数先获取当前Docker 集群中节点 i 的负载情况),,,(,,,,net i IO i CPU i m em i i L L L L L =，然后依据种群中某个个体S 代表的调度方案将任务分配给具体的节点。
先计算出任务j T 在节点i 上运行所需要的各项资源),,,(,,,,net ij IO ij CPU ij m em ij ij N N N N N =，再计算出节点i 在运行任务j T 后的负载变化情况:∑∈+=Jj res i res ij res L N L ,,'式中，J 为节点i 被分配到的任务集合，res ij N ,为获取ij N 中某项资源的需求值，res i L ,为节点i 某项资源的初始负载值，',res i L 为节点i 执行了任务集合J 后某项资源的负载预测值。