基于动态反馈机制的服务器负载均衡算法研究

基于动态反馈机制的服务器负载均衡算法研究

李坤

(西安邮电大学 计算机学院,陕西 西安710061)

摘要针对当前已有负载均衡算法无法准确反映服务器负载的大小和手动设置服务器权值比较固定等方面所存在的不足,提出了一种基于动态反馈机制的服务器负载均衡算法。本算法综合考虑服务器各种性能因素,并根据当前负载动态调整权值,再依据算法调整服务器负载,使得服务器实现负载均衡。通过使用OPNET仿真软件证明该算法相对于传统算法能够减少服务器延迟,提高平均响应速率,并且有效地平衡了集群中服务器的负载。

关键词服务器集群;负载均衡;OPNET

收稿日期:2015-02-11

作者简介:李坤(1988—),男,硕士研究生。研究方向:面向服务的计算。E-mail:843789440@qq.com

doi:10.16180/j.cnki.issn1007-7820.2015.09.012

中图分类号TP301.6

Server Load Balancing Algorithm Based on Dynamic Feedback

LI Kun

(School of Computer Science,Xi’an University of Posts and Telecommunications,Xi’an 710061,China)

AbstractAiming at some existing disadvantages of load balance algorithm that the load balance algorithm can not reflect the situation of servers’ load correctly and that the manual weight setting is inflexible,this paper puts forward an improved and new load balancing algorithm named adaptive weighted least-load algorithm.Server performance factors are considered,and the weight is dynamically adjusted according to the load of each server to make sure that the load of the server cluster is balanced.Simulation by OPNET indicates that the new algorithm can reduce the service delay,improve the average response rate and balance servers’ load effectively compared with existing load balance algorithm.

Keywordsserver cluster;load balancing;OPNET

随着网络的飞速发展,各个网站的访问量急速增长,这就给网站的运营带来了新的挑战。如何提供稳定、不间断的高质量服务已成为网站管理者急需解决的问题。负载均衡技术正是处理这些状况的重要技术之一[1]。

负载均衡的目的是将大量的数据流量和并发访问均衡分摊到多个节点上进行分别处理以减少用户等待和用户响应时间,并将单个负载较重节点的运算分摊到多个节点上并行处理的过程[2]。每一节点将处理的结果汇集起来反馈给用户,这样一来,系统的处理能力将大幅地提高。

负载均衡通过响应的负载调度策略实现,也就是负载均衡算法。目前,常用的负载均衡算法包括:轮转调度(Round-Robin Scheduling,RR)[3]、最小连接调度(Least-Connection Scheduling,LC)、最快响应调度(Faster-Response Scheduling,FR)等。

RR算法使用简单的轮询实现服务器调度,简单、高效,但它并未考虑服务器的连接状态和不同服务器间性能的差异,若服务器的配置或者用户请求服务时间的变化比较大的情况下,不能达到服务器负载均衡的状态[4]。加权轮转调度(Weighted Round-Robin Scheduling,WRR)给不同服务器不同的权值,用以区分不同服务器的处理能力,考虑了不同服务器的性能差异。但WRR并未考虑服务器的当前状态以及用户请求连接数的影响[5]。加权最小连接调度(Weighted Least-Connection Scheduling,WLC)是在LC算法的基础上使用权值来描述服务器的性能,并综合考虑各个服务器性能差异和服务器的连接数对其负载影响的改进算法,它大幅提升了系统效率,但当请求服务的时间变化较大时,仍然比较容易导致集群间的服务器负载不均衡[5]。

本文在现有服务器负载均衡算法的基础上提出一种基于自适应加权最小负载的负载均衡算法来解决上述问题。实验证明,在相同的访问环境中,本文改进的负载均衡算法更有效。

1常见的负载均衡算法

负载均衡模块主要任务是接收请求,并分析服务器负载,而后使用相应的负载均衡算法进行负载均衡策略调整,将请求分发给相应的服务器,最终完成负载均衡。负载均衡的过程可分为[6]:数据包的分析、负载信息的收集、负载均衡以及请求转发4个过程。本文采用IP层的NAT技术和自适应加权最小负载的负载均衡算法,其整体功能结构如图1所示。

图1　负载均衡过程

数据包分析用于记录外部请求的IP信息和端口信息,并进行业务类型的识别和转换;负载信息的收集模块主要用于收集服务器集群中的负载信息,并计算服务器的综合负载情况;负载均衡模块根据相应的负载均衡算法选择合适的服务器以响应用户请求;请求转发模块主要是将接收的外部请求数据包发送到通过负载均衡算法选中的服务器进行处理,然后向用户提供连接响应。

1.1　轮转算法

轮转算法(RR)将请求以简单的轮询方式依次分配给不同的服务器,其认为每台服务器均相同,无差异。当有新连接到达服务器“i=(i+1)modn”集群后,负载均衡模块选择服务器“”算法。选择对应的节点提供服务。RR算法实现简单,但并不符合实际情况,因而实际应用过程中并不能明显提高服务器集群效率。

1.2　加权轮转算法

加权轮转算法(WRR)是基于轮转算法的改进,该算法使用权值来描述不同服务器的处理能力,权值越大,服务器性能越好,连接到外部请求的优先度越高[5]。WRR同时按照服务器权值来分配连接数比例,对于具有相同权值的服务器,其按照RR算法进行轮询。加权轮转算法考虑了服务器性能的影响,但却未考虑不同服务器连接数的影响。因而仍具有一定的局限性。

1.3　最少连接算法

即最少连接算法(LC)就是优先选择连接数最少的服务器给外部请求提供服务[7]。LC算法动态地获取服务器的连接数来描述服务器的负载情况。简单地用连接数描述负载,并未考虑到服务器性能的影响,因而比较片面。

1.4　加权最少连接算法(WLC)

加权最少连接WLC算法是在最少连接LC算法的基础上,通过使用权值描述不同服务器的服务能力,并给不同服务能力的服务器分配不同的连接数量的负载均衡算法[8]。WLC算法并不是从服务器中选择权值较大的服务器提供请求响应,而是从集群的服务器中找出连接数和服务器权值比值最小的服务器,让其对外提供服务[9]。

2动态反馈机制

动态反馈是指,在集群运行期间,由于集群内不同服务器具有不同的处理性能,因此所承受的负载也不同,在任务处理过程中,每台服务器的处理性能和任务分配之前的处理性能已经出现偏差,这时就需要集群内的服务器将当前的自身状态动态的传递到负载均衡器,负载均衡器收到新的状态信息后便会更新已有信息,从而跟均衡地分配任务请求。动态反馈机制的模型如图2所示。

图2　动态反馈模型

其中,W表示每台服务器上一次处理能力的状态,W1表示当前处理能力的状态,后端服务器节点向调度器动态反馈服务器当前状态。通过算法F()计算出新的权值。

3改进的负载均衡算法

3.1　概念描述

3.1.1服务器负载剩余的计算

算法引入负载剩余概念,负载剩余是指集群内各台服务器还能承担负载的多少,从反面反映了各台服务器的负载状况。负载剩余的计算方法描述如下:设Ci为第i台服务器的CPU剩余利用率,Mi为第i台服务器的内存的剩余利用率,k1和k2分别为CPU和内存的常量系数,其中∑ki=1。则集群内每台服务器的负载剩余L计算公式表示如下

L=k1C+k2M

(1)

本算法只选用CPU和内用两个最主要性能指标来衡量集群内服务器的负载情况,是为了减少额外的开销。负载剩余L表示了服务器还能承受负载的多少,L越大,表示服务器上的负载越小,负载的剩余越大,还能承担更多的负载;反之,L越小,表示服务器的上的负载较大,负载的剩余越小,需要暂停或减缓为该服务器分配任务。

3.1.2权值的动态调整

在任务请求到达之前,系统管理员会根据集群内每台服务器的配置信息和通过估计每台服务器处理任务的能力预先为该台服务器设置一个权值,处理任务能力越强的服务器的权值设置越高;反之,处理能力稍弱的服务器的权值设置就相对较低。权值作为负载均衡调度策略中最重要的元素之一,体现了集群内服务器承担负载的能力各不相同。在本算法中,当集群内的各台服务处理任务时,随时间的不断增加,每台服务器的负载剩余能力也随之不断变化,通过对服务器权值的动态调整,并结合每台服务器的真实负载情况,使得权值较高的服务器相对接收更多的任务,而权值较低的服务接收较少的任务,以达到负载均衡器能够合理的分配任务。

假设集群内的服务器数量为n,其中Si表示集群内第i台服务器,第i台服务器的权值表示为W(i),当前该台服务器的负载剩余为L(i),通过动态改变的新的权值为W’(i)。设集群内第i台服务器当前的负载剩余L(i)和权值W(i)的比值为ratio_LW,集群内所有服务器ratio_LW的平均值为AVG_ratio_LW,其计算公式为

(2)

(3)

通过计算出两者的值后,根据ratio_LW和AVG_ratio_LW两个值之间的关系来判断服务器Si当前的负载情况:

(1)当ratio_LW

(2)当ratio_LW>AVG_ratio_LW时,说明集群内该服务器的负载较大,应当调低该服务器的权值,为该服务器减少或暂缓任务分配,避免因此台服务器负载过大,导致服务延时,造成网络堵塞等后果。

(3)ratio_LW=AVG_ratio_LW时,说明集群内该服务器的负载属于平衡状态,服务器的权值保持不变。

因此,集群系统根据集群内服务器的负载剩余L(i)和任务请求分配前管理员为每台服务器设置的权值来动态的调整服务的新的权值W’(i),所以服务器的权值改变量为ΔW,其计算公式为

(4)

则新的权值W’(i)的计算公式为

W’(i)=W(i)+ΔW(i)

(5)

所以,通过动态的调整集群内服务器的权值,使得任务请求能够均衡、合理地分配到相应的服务器。

3.1.3动态算法与静态算法相结合的策略

基于动态反馈机制的负载均衡算法通过计算集群内服务器的负载剩余和动态的调整服务器的权值,能够相对准确地表示出服务器的实时状态信息,比主流的负载均衡算法有较大改进,但由于动态反馈机制只能周期的收集服务器的状态信息,使得算法存在不足。算法改进就是利用静态算法中的轮转算法的适用场景,适用动态算法和静态算法相结合的策略,改进算法存在缺陷。

首先将负载均衡调度器收集到的各台服务器的状态信息进行分组,将集群系统内服务器处理能力即权值大致相同的服务器分为一组。本算法将根据权值大小分为高、中、低3个组别。服务器的权值越高说明处理任务的能力越强,相反的,权值较低的服务器处理能相对比较弱。假定当权值>0.8时,说明此服务器出在高权值组,说明处理任务能力较强,应当更多的分配请求;当权值<0.5时,说明此服务器处在低权值组,处理性能较弱,应当减少或暂缓任务的分配;当权值介于0.5和0.8之间时,说明从服务器处于正常权值组,正常分配任务请求。

使用动态负载均衡算法和静态负载均衡算法相结合的好处就是在一个周期内负载均衡调度器会选择集群系统内服务器权值最大的一组节点进行任务分配,而不是选择负载器权值最大的一个进行任务分配,在权值最大的一组内以轮转调度策略进行分配避免了在一个周期内因任务请求大量增加,而导致集群内的某一台服务器因出现过度服务的状况,使得系统失去平衡。

3.2　算法流程

假设集群系统内服务器的数量为n,即:S1,S2,S3,…,Sn,服务器的配置和其性能不完全相同。W(i)表示服务器Si的初始权值,L(i)表示服务器Si的负载剩余,W(i)表示服务器Si的权值变化量,W’(i)表示服务器Si的新权值,算法具体流程如下:

(1)设置CPU和内存两个参数的剩余率阈值以及服务器的负载剩余率阈值。本文设定CPU剩余率阈值为5%,内存剩余率为8%,服务器的负载剩余率阈值为4%。

(2)负载均衡调度器每隔一个周期收集后端每台服务器的CPU剩余率和内存剩余率。

(3)通过收集每台服务器的CPU剩余率和内存剩余率,计算负载剩余L(i)。

(4)判断计算出的负载剩余是否大于已经设置的负载剩余率阈值:若大于,执行步骤(5);若小于则执行步骤(6)。

(5)将该台服务器的CPU剩余率和内存使用剩余率分别和先前设置好的阈值相比较,若有其中的任何一个参数小于阈值,执行步骤(6);否则,执行步骤(7)。

(6)令该服务器的负载剩余为0,执行步骤8。

(7)计算各个满足条件的服务器的负载剩余,计算权值变量ΔW,新的权值W’(i)。

(8)计算出新的动态权值W’(i),将其根据划分组别的要求分配到相应的组别。

(9)选出权值最高的一组服务器,通过静态算法中的轮转算法,将更多的任务请求分配到权值较高的服务器组。

4仿真实验与结果分析

本文使用OPNET 14.5构建仿真环境,服务器集群由3台Web服务器构成,使用100 Mbit·s-1的双工通信线100 BaseT与负载均衡器相连接。负载均衡技术采用网络地址转换。集群网络模型如图3所示。

图3　服务器集群网络示意图

本文使用WRR算法、WLC算法和本算法实现负载均衡的仿真。图4为3种算法的对比结果。

图4　3种算法仿真结果对比

从图4(a)中可以看出:(1)本算法的情况下,服务延迟时间最短,说明该负载均衡算法对服务延时改善较为明显。(2)图4(b)～图4(d)说明,相同情况下使用改进的负载均衡算法后,该服务器CPU利用率、负载以及任务请求的速率都相应下降,这说明改进的负载均衡算法相对其他两种算法更能实现负载均衡的目的。

本文通过使用不同负载均衡算法对不同服务器的CPU利用率影响进行对比,结果如图5所示。

由图5可知,使用WRR算法实现服务器负载均衡,服务器存在过于忙碌和过于空闲的状态。如Server4的CPU利用率较高,说明它过于忙碌,该服务器将会成为集群的瓶颈,浪费了很多系统资源。WLC算法对服务器负载均衡的效果,使得CPU利用率基本接近,达到较好的负载均衡效果。使用本算法实现负载均衡能使集群服务器的CPU利用率均低于WLC算法,该算法大幅地减少了服务器的负载。

图5　3种算法对各服务器CPU利用率的影响

综上所述,改进的负载均衡算法具有更好的性能,能提升集群的效率,充分利用集群资源。

5结束语

本文对各种负载均衡算法进行深入研究,综合分析了服务器负载均衡的影响因素。并针对目前负载均衡算法的不足进行改进,提出了一种基于自适应加权最小负载的服务器负载均衡算法。使用OPNET软件进行仿真,实验结果表明,与WRR算法和WLC算法相比,该方法具有较好的效率。

参考文献

[1]王颐帅.基于LVS的服务器负载均衡技术[J].计算机系统应用,2014,23(7):252-255.

[2]罗拥军,李晓乐,孙如祥.负载均衡算法综述[J].科技情报开发与经济,2008,18(23):134-136.

[3]许少华,夏智伟.基于轮转周期的动态反馈负载均衡算法[J].计算机技术与发展,2013,23(6):63-66.

[4]Issam Jabri,Nicolas Krommenacker,Adel Soudani,et al.Load balancing approach for wireless IEEE 802.11 QoS enhancement[P].USA:PWC2006,LNCS4217:88-99,2009.

[5]刘玉艳.LVS 负载均衡技术在网络服务中应用研究[D].合肥:合肥工业大学,2007.

[6]Waraich S S.Classification of dynamic load balancing strategies in a network of workstations[C].New Generations:Fifth International Conference on Information Technology IEEE,2008:1263-1265.

[7]吴松涛,韩宗芬,卜胜贤.集群Web服务器的预测最小连接请求调度算法设计[J].长沙电力学院学报:自然科学版,2002(3):7-9.

[8]张慧芳.基于动态反馈的加权最小连接数服务器负载均衡算法研究[D].上海:华东理工大学,2013.

[9]刘玉艳,沈玉明.一种LVS负载均衡调度算法WLC的改进[J].制造业自动化,2010(9):187-191.

[10]廖艳达.基于OPNET的Web集群负载均衡仿真研究[D].桂林:广西师范大学,2007.