一种基于改进遗传算法的动静态负载均衡算法

胡逸飞,包梓群,包晓安

(浙江理工大学 信息学院,浙江 杭州 310018)

Nginx服务器集群的负载均衡技术领域已出现较多传统静态调度算法,例如,Nginx已自行支持的轮询和加权轮询算法、最小连接数算法、IP_Hash算法等[1]。这些算法能够在简单的工作场景下发挥一定作用,但其在复杂的现代网络环境下已凸显各种问题,例如,其无法根据具体网络负载情况进行实时的负载策略再调整[2],点到点式的静态算法在实际网络环境中常会产生大量错误峰值点导致最佳结果的判定出错,因此在静态算法的基础上出现了根据服务器反馈的实际负载信息。通过实时变动负载的分配策略进行负载均衡调度的动态负载均衡算法[3]在一定程度上满足了根据负载情况实时进行算法调整的要求,但也存在一定程度的问题,例如低负载情况下的低负载均衡效率、对网络资源的占用和局部峰值导致整体分配未达到最佳情况等[4]。本文所提算法解决了动静态算法存在的问题,同时通过引入遗传算法解决了局部最优问题,具有一定的应用价值和研究意义。

1 负载均衡研究现状

目前,负载均衡普遍可分为静态算法和动态算法两个版本,动态负载平衡技术更受研究人员青睐。文献[5]对比了已有Web服务器集群的调度策略,包括随机法、循环法、加权循环法、最短队列算法以及扩散负载平衡法等,并提出了协作性自适应对称发起扩散策略。通过队列长度计算服务器的负载阈值并使得服务器通过广播知晓彼此的状态,从而进行负载均衡策略重定位,但该策略存在高并发状态下相应时间较长、系统吞吐量提升不明显等问题。文献[6]提出了基于约束测度的负载均衡技术,定时计算每个服务器的容量和负载。如果服务器的负载大于平衡阈值,则使用负载平衡算法分配任务,但该策略存在影响因子单一、提升效率不明显等问题。文献[7]通过在两个负载均衡服务器上分别对Nginx及HAProxy进行改进加权轮询算法的对比实验,获得了相关算法的性能评价参数,但其在低负载情况下的负载均衡效果不佳。

我国科研人员在负载均衡技术研究方面亦取得了不错的进展。文献[8]通过研究Nginx负载均衡的加权轮询算法原理和实现过程,提出了一种基于后端服务器实时负载信息和相应时间情况的动态反馈负载均衡算法,并通过实验论证了该算法在抗并发能力上的优势。但该算法存在低负载下无提升甚至负提升等问题,有待进一步改进优化。文献[9]提出了一种自适应负载指标权值的负载均衡算法,该算法在对服务器节点分类的基础上利用节点性能和综合负载信息分配任务,从而避免负载倾斜问题。但该算法仅在相同I/O和相近CPU服务器环境下进行测试,不能有效地反应复杂集群下的负载情况。文献[10]提出了一种基于动态反馈机制的负载均衡算法,通过自适应加权最小负载方法获取更优秀的辅助均衡效果,但其在低负载下分配效率较低。文献[11]提出了一种基于预测模型和独立训练节点的负载均衡算法。采用机器学习算法、朴素贝叶斯方法、决策树算法和支持向量机分别对实验数据进行训练从而获得响应时间预测模型。然而,由于朴素贝叶斯算法的缺陷,可能出现局部最优解的情况,从而影响算法整体的准确性,在高并发环境下表现不佳。

上述文献中的算法在实验环境的高负载情况大都有一定效率上的提升,但在低负载情况下,相比于传统算法并没有效率上的提升,甚至还会出现效率下降情况,同时亦存在由于局部负载计算最优解导致的整体分配不均等问题。为了推动解决当前负载均衡算法所存在的上述问题,本文提出了一种基于改进遗传算法的动静态结合的负载均衡算法。

2 算法分析与设计

2.1 服务器节点性评价指标

对于服务器集群的负载均衡来说,准确评估服务器性能是问题的关键所在,不同的指标对于负载均衡调度选择的判断具有较大影响。本文结合文献结论及实验反馈,采用各服务器节点CPU(C)、内存(M)、磁盘I/O(I)和网络带宽(N)作为综合性能评价指标。

当集群中存在n个节点时,对于每个节点Si∈{S1,S2,S3,…,Sn},n>1,服务器性能评价指标C(Si)∈{C(S1),C(S2),C(S3),…,C(Sn)},n>1,根据各项性能可设定评价指标为

(1)

其中,σi为各个服务器性能的权值参数,和值为1。本文根据文献[12]及实验数据反馈,标定服务器性能的评价指标为

(2)

其中,每个服务器节点各性能评价权值为

(3)

其中,j∈{C,M,I,N},为各性能集合中的一项;Wi(Si)为服务器集群中节点Si的一项初始性能数值。

2.2 自适应动态负载均衡算法

本文通过改进概率择优算法[13]提出了一种适用于高负载状态下的新的自适应动态负载均衡算法,其算法流程描述如下:对不同的业务服务器集群进行初始化。根据客户端不同的请求类型或请求处理需求将服务器集群进行分组,对于一些泛用节点或无法根据请求区分的服务器节点则先根据式(2)计算器初始性能评价指标,并对各服务器节点初始性能评价指标进行排序后再根据节点数量尽可能地进行均匀分组。例如对于拥有N个服务器节点的服务器集群,在先根据请求类型将其中的M个节点(M

对于将请求分配至服务器组中某个节点的分配算法,需根据自适应动态负载均衡算法的特点,基于各节点的实时负载情况进行分配算法逻辑更新。本文采用服务器节点负载信息收集模块来收集各节点的实时负载信息,但其为一种需要消耗网络资源及传输时间的收集方法。当后端服务器集群数量较大且某些服务器节点在时间段T内的负载信息情况未发生明显变化时,为了节省集群网络资源,本文根据负载评价指标变化率ΔD来判断某节点Si在t1～t2时间段内的负载信息是否上传,其计算式如式(4)所示。

(4)

其中,Di为根据式(2)计算的节点Si在对应时间点的实时负载性能评价指标。本文根据服务器集群的实际运行环境对其设定一个预设上报阈值Δd,当服务器本次计算的负载变化率ΔD小于该阈值时,说明该时间段内该节点的负载信息变化过小,本次负载信息将不会上报,只在本节点负载收集模块中更新本次收集数据,以用于下一次的本地负载变化率计算。而负载均衡服务器在时间段T内未收到对应节点的负载信息上报,则沿用之前的负载信息,以此来节省节点负载信息的频繁上报所导致的网络资源消耗。

在收集到对应服务器组的各节点的实时负载信息后,本文根据节点的性能使用率L进行概率择优算法的动态分配概率调节,计算式如式(5)所示。

(5)

其中,Wi代表该节点某项性能的使用率,WC、WM、WI以及WN分别代表工作状态下的CPU使用率、内存利用率、磁盘I/O使用率和网络带宽使用率。性能使用率L准确反映了节点在每一时刻的负载情况,但存在使用率L与节点处理能力相反的问题,即使用率越高,当前节点处理能力越低。因此,本文引入一个变量λ来反映当前节点的负载情况,计算式如式(6)所示。

(6)

其中,λ(Si)代表当前节点使用率与所有节点使用率平均值的比值。当λ(Si)>1时,代表当前节点的使用率已超过平均值,需要适当减小该节点的分配概率,提高那些未达到平均使用率的节点分配概率,以达到更好的负载均衡效果。而基于服务器节点性能评价指标的概率择优算法,对于在服务器组中某节点Si的分配概率Pi的计算式如式(7)所示。

(7)

为了综合考虑服务器节点的评价指标及实时性能的使用率,本文将概率择优算法改进为自适应的动态加权轮询算法,将服务器组中的各节点分配概率改进为基于择优分配概率的分配权重。如式(8)所示,Q(Si)为对应服务器节点Si的分配权重。

(8)

其中,B为使得BP>1成立的权值常数。当负载变量λ(Si)>1时,表示当前节点的性能负载较重,超出了集群整体的平均负载情况,需通过实时减小其分配权重来降低新的客户端请求分配给该节点的概率;当λ(Si)<1时则相反。这种在高负载情况下的负载均衡算法结合了当前节点的性能评价指标、实时性能使用率和分组概率择优的优势,使得其负载分配更加合理。

2.3 基于改进遗传算法的阈值计算

本文经过研究文献[14]及进行对比实验后得出结论,对于Nginx作为负载均衡服务器的后端服务器集群而言,在低负载状态下静态负载均衡算法因其简单的分配逻辑,对网络资源消耗较少,因而具有良好的分配效果;而在高负载状态下,动态负载均衡算法的优势则逐渐显著。找到由静态算法优势区间转为动态算法优势区间的负载值即并发请求数量的阈值,是更好地进行Nginx负载均衡算法研究的关键所在。本文在对标准遗传算法流程[15-16]进行研究分析后提出了一种改进的自适应遗传算法,并将其用于动静态算法优势区间阈值,其流程和计算方式如下所示。

首先与标准遗传算法相近,进行编码及产生初始种群,并通过适应度函数计算各染色体个体的适应度函数值,计算出平均适应度值Favg及最大适应度值Fmax。通过这两种适应度值计算本文算法的关键阈值即操作变换阈值,作为改变变异算子操作和交叉算子操作流程顺序的计算阈值。计算结束后优先判断算法整体是否满足终止条件,若不满足算法的终止条件,则进一步对算法设置的操作变换阈值进行判断,即判断sin(Favg/Fmin×π/2)≥1/2是否成立。当该条件满足时,说明此时种群的平均适应度值与最大适应度值接近,染色体个体间差异较小,则先以一定概率PB进行变异算子操作,再以概率PJ进行交叉算子操作,最后进行选择算子操作,可减小上述问题中变异操作所带来的破坏种群优异性的问题。当不满足该阈值条件时,则先以一定概率进行交叉算子操作,再进行变异算子操作,最后进行选择算子操作,可最大程度缓解算法进行无区分度迭代的问题,以加快收敛速度。其中,PJ和PB的计算式为如式(9)和式(10)所示。

(9)

(10)

当Favg/Fmin为较小值时,表明当前种群的染色体的适应度平均值与最大适应度值差值较大,种群适应度值分布较为分散,此时PJ的值相对增大,即提高了交叉算子操作的概率。以更大的概率对具有较大差异基因位的染色体个体进行交叉操作,进化出新的下一代优质个体的概率更大。与之相对应地,减小PB的值,即降低了变异算子操作的概率,使得优秀的个体更容易被保留,并同时加快了收敛的速度。当Favg/Fmin为较大值时,表明当前种群适应值的差异较小,较为集中,交叉算子操作已难以得到新的优质染色体,因此降低了交叉算子操作的概率,同时也对应地增加了变异算子操作的概率,使算法跳出局部最优解具有更大的可能性,以达到获得全局最优解的目的。

在遗传算法流程中,交叉算子操作和变异算子操作大都具有随机性和无方向性的特点,而选择算子操作作为人为可控的操作,通过选择合适的算子可使算法按照期望方向进行演化,因此具有一定重要性。本文基于适应度值非负的特点及对收敛性需求的考虑,选择了一种基于三角函数的自适应的选择算子操作概率的计算方法。如式(11)和(12)所示,该选择算子概率既满足了适应度值非负的要求,又避免了冗余参数的设置,在收敛性上也具有较好的效果。

(11)

(12)

对于某个染色体个体的选择概率Pi,其值由个体适应度函数值Fi、种群的最大适应度值Fmax和最小适应度值Fmin决定。当种群整体的适应度差异极值较高时,表明当前种群的适应度整体差异过大,则选择降低单独某个染色体个体的概率,整体选择分布更加均匀,能够提高选择的算子基因位的范围。同时选择某染色体个体的概率与其适应度值和最小适应度值的差值成正比,则选择适应度优秀的染色体个体,使得种群能够较快地向优秀进化方向演化。而通过三角函数这种非线性变化的方式自适应地调整选择算子的概率,使得变化的速率按照差异期望进行变化,在保持种群多样性方面具有良好的效果,使算法能以较快的收敛速度更大概率地获取全局最优解。

根据负载均衡算法及改进遗传算法确定适应度函数。本文采用章节3.1中的服务器节点性能评价指标作为适应度函数优化的选择标准,使用章节2.2中的自适应动态负载均衡计算方法作为对区间阈值的计算方法之一,并根据文献[17]引入基于最小熵增原理的适应度函数计算方法,最终确定本文算法的适应度函数如式(13)所示。

(13)

其中,Di为节点Si的节点性能评价指标;D0为服务器集群的初始硬件性能评价指标;k为热力学常量;Q(Si)为自适应动态负载均衡算法中节点Si的分配权值。

本文采用基本的适应度函数构造方法,将目标优化函数作为适应度函数,通过寻找该目标优化函数的零值解,在搜索空间内找到对应服务器集群的动静态算法区间划分的阈值。

本文通过改进的遗传算法对基于服务器性能指标的适应度函数值进行研究计算及各种遗传操作,不断地使种群朝全局最优解的方向演化,最终找到满足要求的全局最优解,即将所进行计算的服务器集群的静态负载均衡算法优势区转变为动态负载均衡算法优势区的阈值。

2.4 动静态结合的负载均衡算法

以上述研究进度及改进算法为铺垫,本文综合了全部研究成果,提出了一种基于改进遗传算法的Nginx动静态结合的负载均衡算法。其核心思想为在计算出动静态算法划分区间的阈值之后在负载均衡服务器上设置负载监控模块。当监控到当前服务器集群负载在阈值以内时,采用基于节点性能指标的静态加权轮询算法作为负载均衡策略,而当集群负载超过阈值后,将负载均衡策略动态调整为章节2.2中所提出的改进自概率择优算法的自适应动态负载均衡算法,并开始启用安装在各服务器节点上的负载信息收集模块。通过收集的实时节点负载信息动态调整算法中各节点分配的权值,以此获得更优秀的负载均衡效果。算法的整体流程如图1所示。

图1 算法整体流程 Figure 1. Overall flow of the proposed algorithm

3 算法分析与设计

3.1 实验环境

本文实验环境由虚拟机搭建的9台服务器组成。其中,1台服务器作为测试客户端,场景为某智慧宿管项目,1台作为反向代理服务器,剩下的7台作为后端服务器集群,分为3种不同请求的服务器集群。虚拟机操作系统均为CentOS7,其他参数如表1所示。

表1 实验环境参数Table 1. Experimental environment parameters

本文在实验过工程中设置了各后端服务器节点每隔3 s上传一次节点性能使用率情况,并利用Siege工具模拟多用户并发访问及数据实时收集。根据文献及实验反馈结果,本文选取服务器平均响应时间和实际并发连接数作为算法评价的性能指标。

3.2 实验结果与分析

由于本文算法是基于结合静态负载均衡算法和动态负载均衡算法的优势所提出的,因此本文选取了静态加权轮询算法和动态的概率择优算法作为对比实验的参考算法。为验证本文算法具有更优秀的负载均衡效果,选取了文献[18]的动态负载均衡算法(dnfs_conn)进行对比。通过将包含本文算法和上述算法的4种算法分别使用Nginx的第三方模块写入作为其负载均衡策略算法均,在实验环境中通过不断提高并发请求数量,每次运行30 min,获得对应的平均响应时间及实际并发连接数,并生成对比结果,如图2和图3所示。

图2 平均响应时间比较Figure 2. Average response time comparison

图3 实际并发连接数比较Figure 3. Comparison of the actual number of concurrent connections

由图2和图3可以看出,相比于Nginx自带的加权轮询算法、概率择优算法和dnfs_conn算法,本文提出的基于改进遗传算法的动静态负载均衡算法随着并发数量的增加(即服务器集群整体负载增大),对于请求的平均响应时间相对较短的优势越来越大,且在高并发情况下实际的并发连接数量优势更加明显。相比于dnfs_conn算法,本文算法在数值上具有15%左右的提升。这反映出在高并发环境下,本文算法相比于传统算法在负载均衡方面有着一定优势,能够更好地分配请求和服务器资源,在低负载状况下保留静态算法优势的同时最大化利用服务器集群的性能,具有更加优秀的负载均衡效果。

上述实验结果证明,本文提出的基于改进遗传算法的Nginx动静态负载均衡算法既保留了静态算法在低负载环境下平均响应时间较低的优势,又在高负载环境下具有相对更优秀的负载均衡效果,充分利用了服务器各节点的性能和资源,使得整个服务器集群的响应速度和承载能力都得到了进一步优化。在本文的模拟服务器集群环境下,本文算法相比于静态加权轮询算法、概率择优算法和dnfs_conn算法具有更优秀的负载均衡效果。

4 结束语

为了更好地在各种高并发情况下实现分布式服务器集群的负载均衡,本文基于综合CPU性能、内存性能、磁盘I/O和网络带宽等服务器性能的节点负载性能指标,结合静态负载均衡算法及动态负载均衡算法优点,并通过改进遗传算法解决阈值计算问题,提出了一种基于改进遗传算法的动静态负载均衡算法。为验证本文算法的正确性和有效性,通过Siege工具设计了网络集群的模拟实验,对加权轮询算法、概率择优算法、dnfs_conn算法和本文算法进行了对比实验,实验结果证明了本文算法在性能上的优势,对于推动Nginx负载均衡算法的研究具有一定意义。