Kubernetes集群中多节点合作博弈负载均衡策略

李华东，张学亮，王晓磊，刘 惠，王鹏程，杜军朝

(1.西安电子科技大学 计算机科学与技术学院，陕西 西安 710071；2.中国电子科技集团公司 航天信息应用技术重点实验室，河北 石家庄 050081；3.中国电子科技集团公司 第五十四研究所，河北 石家庄 050081)

随着云计算技术的飞速发展，虚拟机技术将操作系统与硬件分离，实现了物理资源的按需分配，然而虚拟机不能很好地适应当今应用所需的轻量级、高敏捷、可迁移等需求[1]。Docker为代表的容器技术以其跨平台、可移植、易用性等特点被广泛接受，改变了现有分布式应用的架构、部署及管理方式[2]。由此催生了一系列的容器编排和管理工具：Flynn、Deis和Fleet等。Flynn和Deis由于主要参考了PaaS(Platform as Service)层的架构、功能和设计理念，对整个软件环境的控制力存在较大的限制，而单纯依靠Fleet编排部署系统不能很好地提供云计算服务。由Google公司开源的容器编排系统Kubernetes，因其优秀的容器部署、运维、管理能力而成为业界容器编排系统的首选[3]。

针对Kubernetes集群，已有一些工作围绕资源利用率、服务质量、资源成本、维护开销、节点性能展开[4-9]。虽然负载均衡的研究已经有大量工作[10-11]，但是针对Kubernetes集群资源负载均衡的研究工作较少，而在实际大规模Kubernetes集群中，往往会因为调度不均衡导致存在资源碎片现象，造成集群整体的成本损耗。因此，如何设计能确保集群资源负载均衡度这个指标的调度器，以降低集群资源碎片化程度和集群成本，具有实际重要意义。

对此，文献[12]和文献[13]设计了负载平衡器和多集群作业调度器，使集群间资源的平均利用率趋于平衡。但是它们属于静态资源调度算法，没有考虑服务请求资源与Pod实际使用资源可能会不一致这种在真实应用场景中存在的现象。文献[14]和文献[15]均提出了动态资源调度算法。该算法通过对节点资源使用情况进行实时监控并计算优先级，改进后的算法提高了集群资源的负载均衡程度。但是仅考虑了CPU和内存两种资源。同样地，文献[16]提出了一种领导者选举算法。该算法通过将领导者均匀分布在集群中的节点上来克服网络瓶颈问题。但是仅考虑了网络流量的负载均衡。上述工作只针对一两种资源间的负载均衡，在多资源负载均衡方面的研究还处于空白，而在真实应用统一调度场景中，这些资源之间不能孤立看待。所以笔者认为在实际调度中应考虑更多的必要因素。

综上所述，笔者对 Kube-scheduler 进行了优化和扩展，提出一种将合作博弈论与服务调度和集群资源负载均衡相结合的调度算法。主要贡献如下：

(1)设计了Kubernetes集群动态资源调度管理平台，通过监控组件实时获取服务资源使用情况，避免了服务请求资源与Pod实际使用资源不一致的问题。

(2)提出了一种基于合作博弈论的多资源负载均衡(Multi-resource load Balancing algorithm based on Cooperative Game Theory，MBCGT)算法，充分考虑CPU、内存、网络带宽以及磁盘IO资源之间的负载均衡，建立节点间的合作博弈模型，提高集整体负载均衡程度，减少了集群资源碎片，降低了集群成本。

(3)利用MBCGT算法对 Kube-scheduler 进行了优化和扩展，使其在不同场景下依然能稳定、高效地调度各种类型的复杂工作负载。

1 相关知识

Kubernetes Scheduler是Kubernetes系统的核心组件之一，负责整个集群Pod资源对象的调度。其根据内置或扩展的调度算法(预选与优选调度算法)，将待调度Pod资源对象调度到最优工作节点上，从而更加合理充分地利用集群的资源，同时提高应用运行效率。

BalancedResourceAllocation算法[17]是Kubernetes默认的负载均衡算法。该算法的目的是从候选节点中选出各项资源利用率最均衡的节点。其计算方法可表示为

(1)

其中，Φcpu表示所有备选节点上运行的Pod和待调度Pod的总CPU占用量，Ωcpu为节点的CPU计算能力，Φmem表示所有备选节点上运行的Pod和待调度Pod的总内存占用量，Ωmem为节点的内存大小。该算法对节点打分所使用的CPU和内存占用量是根据待调度Pod的预请求量来计算的。然而，Pod的资源预请求量和实际运行时Pod对资源的使用情况并不一致，导致该打分方法存在较大的误差。因此节点资源均衡度调度算法有待改进。

2 系统建模

本节给出系统建模：集群资源建模针对Kubernetes集群中节点资源信息进行描述；任务建模针对每个任务所需资源信息进行建模；基于上述建模给出资源均衡度评估模型的建模和节点得分计算公式；最后整合各种任务调度场景抽象出集群资源负载均衡的问题定义，并给出该问题的解决算法。

2.1 Kubernetes集群资源建模

2.2 任务建模

2.3 节点资源均衡度评估模型建模

在给出Kubernetes集群资源建模和任务建模后，本节给出节点资源均衡度评估模型的建模，并计算出将Pod调度到相应节点上的得分。

定义资源均衡度这个物理量来衡量CPU、内存、网络、磁盘IO的资源使用率相差程度。资源均衡度越大，则资源碎片化程度越大；资源均衡度值越小，则资源碎片化程度越小。下面给出资源均衡度的计算公式：

(2)

其中，μij为任务j调度到节点i上时，节点i资源的总体均值：

(3)

(4)

其中，τij表示一个二进制决策变量，如果任务j调度到节点i上，则τij=1成立；否则，τij=0成立。

根据以上模型，节点i的打分公式定义如下：

(5)

2.4 基于合作博弈论的多资源负载均衡调度算法

2.3节给出了节点资源均衡度评估模型的建模。本节整合各种任务调度场景来抽象出集群资源负载均衡问题的定义，并给出该问题的解决算法。

问题定义：给定一个或多个独立任务P，通过自定义调度算法，求出每个任务最优的选择节点以及资源负载均衡度，在保证集群中单个节点资源使用负载均衡的同时，最大化集群整体资源负载均衡度。

针对上述问题，引入了合作博弈论模型[18]。博弈论被广泛应用于边缘卸载[19]、异构网络[20]以及车联网[21]等领域。合作博弈论，也称正和博弈，是指博弈双方的利益都有所增加，或者至少是一方的利益增加，而另一方的利益不受损害，从而达到整体利益增加。这十分切合文中的问题模型。

将集群中的节点N={n1，n2，n3，…，ni，…，nn}与待调度的任务P={p1，p2，p3，…，pj，…，pm}之间形式化为一个合作博弈。在该合作博弈中，博弈者是进行任务编排的节点。经过若干轮博弈后，n个博弈者将达成互赢，称为纳什讨价还价解决方案[22]。此时集群中每个节点间期望负载均衡的公平性达到最大，且集群整体负载均衡也达到最优。

一个合作博弈通常表示为最大化博弈者效用函数的乘积。在本节研究的问题中，节点ni的效用函数如式(5)所示，其表明一个节点的各资源利用率的方差越大，即节点中资源碎片化程度越大，则该节点的效用函数值越小。

因此，基于合作博弈论的多资源负载均衡调度算法的目标函数可以定义为

(6)

s.t.τij=0，1 ，

(7)

(8)

(9)

(10)

(11)

(12)

(13)

基于式(2)～(13)，笔者提出的MBCGT算法如下。

MBCGT算法：基于合作博弈论的多资源负载均衡算法。

输入：任务P={p1，p2，p3，…，pj，…，pm}，集群节点N={n1，n2，n3，…，ni，…，nn}。

forj=1 tondo

步骤2 求出满足约束式(9)～(12)的节点N°，如果没有满足约束的节点，则算法结束；反之，继续执行。

end for

在MBCGT算法中，步骤1利用监控组件可以求出集群中所有节点的剩余计算能力，为任务调度提供参考。步骤2用于检测节点是否符合任务部署的约束条件，即保证任务调度到相应节点上的可用性。步骤3根据目标函数求出最优的节点选择策略，在保证集群中单个节点资源使用负载均衡的同时，提高集群整体资源负载均衡的程度。步骤4根据最终的调度选择求出最终的资源负载均衡度。

3 实验结果及分析

3.1 实验环境

实验基于x86架构的OpenStack集群创建6台虚拟机作为集群节点，其中包含1台master节点、1台监控节点和4台node节点。而虚拟主机配置主要参考了当今云服务器提供商(阿里云、华为云等)的主流云服务器硬件配置，具有代表性。集群节点的详细配置如表1所示。

表1 集群节点配置

实验使用版本为v1.18.0的Kubernetes和版本为v18.06.1-ce的Docker搭建实验基础平台。使用node_exporter-1.1.2软件实时采集集群中各节点的数据，然后用Prometheus-2.26.0将各节点采集的数据作进一步的汇总，最终用Grafana-7.3.5将汇总的数据进行可视化展示。本次实验使用Stress压力测试软件模拟真实应用，其镜像版本为polinux/stress：latest。

3.2 实验结果及分析

为了更好地验证MBCGT算法在实际生产环境下集群负载均衡度的提升，以及使用监控实时获取服务资源使用情况的优势，实验准备了12个测试应用。其中，涵盖了计算密集型任务、内存密集型任务、网络带宽以及磁盘IO密集型任务，分别启动12个Pod运行在Kubernetes集群中。测试Pod的资源请求量如表2所示。

表2 Pod资源请求量

使用所提出的MBCGT算法，设计了MBCGT算法调度器，为了更好地验证该调度器的优势，防止实验的偶然性，共进行了3组对比实验，每组实验按照不同的部署顺序各进行了5次实验。取5次实验结果的平均值作为每组实验负载均衡度的对比，使实验结果更具有说服力。每次实验分别与Kubernetes的默认调度器以及动态资源调度器[12]进行比较，其中动态资源调度器相较于文献[13]的调度器在服务部署时间以及节点资源负载均衡方面具有更好的效果。

实验统计了每次调度完成后集群最终的资源均衡度和资源利用率，并统计每5次实验集群负载均衡度的平均值作为每组实验的负载均衡度。3组实验的对比结果如表3所示。

表3 集群资源负载均衡度对比

从表3可以看出，使用MBCGT算法调度器，集群中各节点的平均负载均衡度相较于Kubernetes默认调度器分别提升了约8.15%、8.40%、6.31%；相较于动态资源调度器[12]分别提升了约7.41%、8.22%、5.88%，这说明CPU、内存、网络以及磁盘IO的资源利用率更均衡。由于Kubernetes默认调度器和动态资源调度器[12]只考虑CPU和内存两种资源进行任务调度，而实际的应用场景下，任务往往包含对网络带宽的访问以及磁盘IO的读写需求，所以在进行任务调度时，集群中4种资源的负载均衡度往往出现波动。而MBCGT算法调度器充分考虑4种资源，提升了算法的鲁棒性，使得该算法在实际应用场景中更具有稳定性。

根据实时监控，可得到各个测试Node节点在分别使用Kubernetes默认调度器、动态资源调度器[12]和MBCGT算法调度器时在资源利用率方面的对比图，如图1所示。

(a)node 1

图1中4个分图分别给出了3种调度器在调度完成后集群中4个节点(node)的CPU、内存、磁盘和网络的资源利用率。由图可以直观看出，采用MBCGT算法调度器使得集群中各个节点的各类资源的资源利用率更加均衡，负载均衡程度更高。

4 结束语

由于实际任务对各资源需求量相差很大，所以集群中节点往往由于单个资源耗竭而导致任务无法部署；此时集群中节点存在大量的资源碎片无法被充分利用，用户只能购买新的节点来满足任务需求。为此，针对当今Kubernetes负载均衡算法中所使用的CPU和内存占用量是根据待调度Pod的请求量计算求得，与Pod实际资源使用情况不相同的问题，以及仅考虑CPU和内存两种资源不充分的问题，笔者提出了MBCGT算法。通过监控组件实时获取服务资源使用情况，并且充分考虑CPU、内存、网络带宽以及磁盘IO资源之间的负载均衡，建立了节点之间的合作博弈模型，在保证集群中单个节点资源使用负载均衡的同时，最大化集群整体资源负载均衡的程度，从而最大化减少资源碎片化程度，使系统具有更加均衡的资源节点，去服务于创建的任务，减少资源成本损耗。