基于负反馈的负载均衡算法实现

陈 伟



基于负反馈的负载均衡算法实现

陈 伟*

(宿州职业技术学院 网络中心,安徽 宿州, 234101)

LVS现有的负载均衡算法在分配服务器请求时大多都是基于固定权值, 使得LVS集群系统在长时间高负荷运行后会出现负载倾斜. 为此, 给出了一种改进的负载均衡算法, 该算法通过引入负反馈机制, 充分考虑服务器权值的动态调节, 更准确地反映了各服务器的真实负载情况. 测试结果表明, 该算法优于原有算法.

集群; 负载均衡; 负反馈; LVS

随着站点服务日益多样化, 网络服务器的访问数量急剧增加. 为确保网络服务的正常提供, 构建高性能的WEB站点, 服务器集群系统应运而生. 把多台服务器通过局域网连接成集群系统, 以提高其整体性能和处理能力, 并具高可伸缩性、高可用性和高性价比[1].

集群系统的关键是实现集群内部服务器之间的负载均衡. 所谓负载均衡, 就是通过重新分配集群内每个服务器的负载, 使得各个服务器的负载相对均衡, 从而提高整体的服务性能并缩短客户请求的响应时间, 提高系统的资源利用率.

常用的LVS集群系统自带的调度算法是基于固定权值的静态算法, 无法根据服务器的实际负载情况进行动态调节, 易出现负载倾斜现象. 近年来对于动态负载均衡的研究成为热点. 文献[2]提出了一种集群系统的透明动态反馈负载均衡算法; 文献[3]提出了动态负载均衡算法理论模型; 文献[4]针对Web服务器集群系统中负载动态变化特性提出了一种临界加速递减动态请求负载分配算法. 在动态负载均衡理论基础上, 本文提出了一种基于负反馈的负载均衡算法, 该算法引入负反馈机制, 根据负载状况和节点处理能力动态分配请求, 有效地实现了集群负载均衡.

1 负反馈理论的引入

负反馈就是使输出起到对输入相反的作用, 使整个系统的输出与系统期望的误差逐渐减小, 整个系统趋于稳定[5]. 负反馈的本质在于设计一个目标差不断减小的过程, 在这种控制中, 系统把控制后的输出目标与控制目标相比较, 得到目标差这一反馈信息, 以此为据, 选择合适的参量值, 使得目标差在一次次控制中逐渐变小, 最后达到控制的目的[6].

LVS集群系统中节点服务器的权值是管理员进行输入的固定数值, 权值大的服务器具有更高的性能和请求处理能力. 服务器在固定的权值下, 处理负载请求时并不能够根据当前节点的实际负载情况进行自我调节, 这样节点服务器在长时间的高负荷下, 势必造成集群系统负载的倾斜.

因此, 引入负反馈的机制, 对高负载的服务器进行动态权值调整, 减少其任务的分配量. 相反, 对于负载较低的服务器, 它还能够在短时间内处理更多的请求, 故可适当增加任务分配量, 这样才能使集群系统的负载逐渐趋向于平衡.

2 负反馈模型

合理的调度算法是实现负载均衡的关键, 本文主要从研究调度算法入手, 来解决LVS负载均衡问题. 为防止负载倾斜的出现, 需要设计出动态的均衡算法, 该算法要能够根据实际负载情况和节点处理能力, 对节点权值进行动态调整, 从而选择合适的节点进行请求分配. 根据负反馈机制设计如图1控制模型.

图1 负反馈模型

其中为权值, 描述节点的处理能力,是负载量值, 描述节点的当前实际负载.(,)是运行在调度器上的权值调整模块, 用来动态调整节点权值. 客户机发出请求时, 负载均衡调度器LB向服务器发送请求报文, 服务器池中的每个服务器都要向LB反馈其当前负载量值, LB的(,)模块会根据反馈回来的负载量值和当前节点的权值重新计算出新权值′, 再根据′的值来分配用户请求. 当某个服务器负载量较大时,(,)模块会调减其权值, 新的权值′ ＜, 这样服务器只能分配较少的客户请求,较小时可增加其权值, 此时′＞, 说明可分配更多的请求给该服务器. 这样就避免了某些节点负载过高的情况发生, 提高了系统的吞吐量, 充分发挥了服务器的处理能力, 从而实现动态的负载均衡.

图2 负反馈算法的工作方式

3 负反馈算法设计

负反馈算法的工作方式如图2所示. 本文采用LVS中IP负载均衡的VS/DR模式构建集群体系. 负载均衡器安装在Linux操作系统上. Monitor进程运行均衡器用户空间, Agent监控进程运行在真实服务器上用于搜集服务器的负载信息并反馈给Monitor进程用来来计算负载量值[7], 根据负载量和当前权值重新计算出新权值′, 如果和′的差值超过设置的阀值, 则把新的′写入到ipVS调度中去, 否则继续保持原有调度.

3.1 负载量值L的计算

负载量值是服务器实际负载情况的体现. 负反馈均衡算法主要从服务器系统资源使用状况和对请求的响应时间两个方面入手来实现服务器节点负载量值的计算.

影响服务器性能的指标有很多, 本文主要选取CPU、内存、带宽、磁盘I/O占用4个指标[8]. 用CPU占用率CPU、内存占用率MEM、磁盘I/O占用率DISK和网络带宽占用率BW4个参数来描述服务器系统资源使用状况, 这4个参数值是通过服务器的Agent来获取的.

响应时间RES通过负载均衡器端获取. Monitor向服务器发送报文请求的时间点记为1, 得到服务器上Agent发回的负载信息时间点记为2, 通过1与2的差值作为参照条件计算出RES因此, 负载量值L可定义如下:

L=1×CPU+2×MEM+3×DISK+4×BW+5×RES.

其中R用来描述负载参数对服务器的重要程度,R越大说明此指标越重要, ΣR= 1.CPU、MEM、DISK、BW、RES和R取值区间均为[0, 1]. 假设认为CPU和RES较为重要可设置{0.3, 0.1, 0.1, 0.1, 0.3}, 在实际操作中可以对R不断修正以达到最适合的比例.

3.2 F(W, L)表达式

本文采用如下(,)表达式进行权值调整:

每个服务器在加入到集群系统时有一个初始权值W, IPVS调度也首先使用初始权值, 在计算新的权值W′时, 如果负载量L< 0.6时,说明服务器负载较轻, 还有足够的请求处理能力, 权值会增大; 当L大于0.6且小于0.75时, 服务器负载接近饱和, 但仍具有接纳新请求的能力, 权值继续增大; 当L大于0.75且小于0.9时, 表达式中0.75-L产生负数, 权值自动调减, 这样便避免了服务器负载过高的情况出现. 表达式中0.75是理想的负载程度,1和2都是可调系数, 缺省值分别设置为10和8.

由此可见,(,)表达式是一个负反馈公式, 通过它能够把权值调整到一个稳定点, 当系统达到理想的负载程度时, 权值是相对稳定不变的.

至此, 可以把负反馈均衡算法描述如下: (a) 负载均衡器定时向服务器发送请求报文, 服务器响应并反馈负载信息(CPU、MEM等参数, 不包括RES)和部分负载量值L(partly). (b) 负载均衡器对服务器反馈回的各项参数以及部分负载量L(partly)进行判断, 如果超过预设的阀值则W′置为0. (c) 负载均衡器计算响应时间RES的值. (d) 负载均衡器根据RES及服务器发回的L(partly)计算负载总量值L, 并根据L的值, 通过(,)函数计算出新的权值W′再写入到IPVS调度中. (e) 负载均衡器根据新权值W′, 选择适合的服务器响应请求.

由此可见, 负反馈均衡算法是在LVS原有的加权调度算法的基础上增加负反馈控制机制, 使得原有调度算法能够根据负反馈机制实现服务器权值的动态调节, 从而实现负载平衡.

图3 负反馈下IPVS体系

4 负反馈算法实现

为了实现负反馈的负载均衡, 在LVS集群系统上安装5个功能模块: 信息收集模块(ICM), 信息发送模块(ISM), 时间探测模块(TDM), 权值计算模块(WCM), 权值写入模块(WWM), 其中ICM和ISM模块运行在真实服务器端, TDM、WCM和WWM模块运行在负载均衡器端, 是Monitor的组成部分, 如图3所示.

4.1 服务器端Agent的实现

Agent程序的功能是: (a) 采集服务器负载信息并计算部分负载值L(partly); (b) 发送服务器负载信息及L(partly)至负载均衡器; (c) 及时响应负载均衡器探测请求报文.

4.1.1 信息收集模块(ICM)

本文主要介绍Windows系统下负载信息的收集. 采用Windows提供的PDH库实现, 实现函数命名为CollectLoad, 该函数实现了用PDH库收集性能参数数据的全过程. 该函数包括4个形参和一个返回值. 4个形参就是要采集的服务器负载信息, 返回值用于判断收集数据是否成功.

上述过程获得了服务器的4个负载指标CPU、MEM、DISK和BW, 没有得到响应时间RES, 因此, 此时计算的是部分负载量值L(partly), 算法如下:

L(partly) =1×CPU+2×MEM+3×DISK+4×BW.

通过定义结构体来存放CPU、MEM、DISK、BW及(partly)用于提供给负载信息收集模块ISM发送给负载均衡器. 结构体如下:

Strcut RS_Loadinfo{

double cpu;

...

double load_partly;}

4.1.2 信息发送模块(ISM)

ISM在得到ICM模块收集的负载信息后发送至负载均衡器. 由于负载信息数据量较小, 故采用UDP协议建立socket套接字并进行监听, 当得到均衡器报文请求时, 调用ICM模块收集服务器负载信息, 然后把负载信息保存至RS_Loadinfo结构体中通过sendto函数从UDP套接字发送给均衡器权值计算模块WCM.

4.2 负载均衡器端Monitor的实现

Monitor主要工作如下: (a) 定时向服务器发送请求报文. (b) 根据服务器响应时间得出RES用于计算新的权值W′. (c) 把W′写到IPVS调度, 选择合适的服务器分配请求.

4.2.1 时间探测模块(TDM)

4.2.2 权值计算模块(WCM)

由上文可知, 服务器负载信息存放在结构体RS_Loadinfo中由ISM模块发送过来给WCM. 负载均衡器端将每个服务器的信息存放在数组RS_Loadinfo[]中, 当RS_Loadinfo[]中得到数据后先对各个负载参数及部分负载量进行判断. 如果各个负载参数小于阀值0.9,L(partly)小于0.7, 则按照(,)表达式计算新的权值W′并存放至数组New_[]中, 否则设置服务器新权值W′ = 0.

其中服务器的原权值W是由IPVS的getsockopt()函数获取的,存放在本地Old_[]数组中. 由(,)表达式可知, 当前权值W下, 当服务器负载量值L＜0.75时, 新的权值会增大, 此时W′>W,当L≥0.75时,W′权值下降使W′≤W, 使负载量维持在0.75上下, 避免了长时间运行负载过高.

4.2.3 权值写入模块(WWM)

当新的权值数组New_[]中已得到数据, 权值写入模块WWM会把New_[]和Old_[]进行比较, 当两者差值超过预设的阀值时才能把新权值写到IPVS调度, 否则继续保持原有调度. 这里阀值设为1, 当∣New_[]-Old_[]∣≥1或者New_[] = 0时, 则把New_[]的值赋给Old_[], 再把新的Old_[]值]写进IPVS调度.

5 算法性能测试

本文主要从平均响应时间和吞吐量两方面对Web服务器集群系统进行压力测试, 所使用的测试工具为微软的Microsoft Web Application Stress Tool(简称WAS). 平均响应时间主要由TTFB(Time To First Byte)的值决定, TTFB是收到服务器回应的第1个字节所用时间, 其值越小性能越好. 吞吐量主要考察每秒收到数据量的大小即Bytes Recv Rate(KB·s-1), 值越大吞吐量越高.

表1 TTFB对比

通过在测试机上运行测试工具WAS分别对使用原有加权最小连接调度算法(WLC)的LVS集群系统和引入负反馈算法后的集群进行测试, 得到如表1所示数据.

为了更直观的描述, 可把表1的数据以图表的形式显示如图4所示. 将WAS生成的报告中Bytes Recv Rate项作为集群系统的吞吐量进行采集, 可得出如图5吞吐量的对比图.

从图4可以看出, 当连接数较少时两种算法的TTFB值比较接近, 甚至引入负反馈后的集群系统反而响应时间更长, 这是因为定时获取各台服务器系统资源信息和响应时间的额外开销影响了其性能, 但是随着连接数的增加, 负反馈算法的优势逐渐体现出来, 使用负反馈机制无论是在响应时间还是吞吐量方面都优于原有算法下的集群系统, 可见, 基于负反馈的负载均衡算法在提高集群系统整体性能上相对原有算法有了一定的改善和提高.

图4 TTFB对比

图5 吞吐量对比

6 总结

为了有效防止负载倾斜的出现, 更好的提高服务器集群系统的整体性能, 文中引入了负反馈的控制机制, 把原有的负载均衡调度算法进行改进, 形成了一种基于负反馈的负载均衡算法. 该算法通过负反馈机制实现动态的权值调整, 有效解决负载不均衡问题, 提高了集群系统的整体服务性能. 压力测试表明, 基于负反馈的均衡算法优于LVS原有算法, 在实现负载均衡和提高集群系统性能上有一定的价值.

[1] 田绍亮, 左明, 吴绍伟. 一种改进的基于动态反馈的负载均衡算法[J]. 计算机工程与设计, 2007, 28(3): 572—728.

[2] 龚梅, 王鹏, 吴跃. 一种集群系统的透明动态反馈负载均衡算法[J]. 计算机应用, 2007, 27(11): 2662—2665.

[3] 王霜, 修保新, 肖卫东. Web服务器集群的负载均衡算法研究[J]. 计算机工程与应用, 2004, 40(25): 78—80.

[4] 郭成城, 晏蒲柳. 一种异构Web服务器集群动态负载均衡算法[J]. 计算机学报, 2005, 28(2): 179—184.

[5] 程杨. 基于LVS负载均衡设计与实现[D]. 广州: 中山大学, 2011: 11—12.

[6] 谢欣. 试论负反馈控制理论在排球教学中的作用[J]. 山东体育科技, 2004, 26(4): 82—84.

[7] 申伟. 基于LVS集群的一种负载均衡改进算法的研究与实现[D]. 北京: 中国地质大学, 2010: 28—29.

[8] 万勇. 基于LVS的负载均衡策略算法的研究与改进[D]. 成都: 西南交通大学, 2010: 30—31.

Realization of the load balancing algorithm based on negative feedback

CHEN Wei

(Network Center, Suzhou Vocational and Technical College, Suzhou 234101, China)

The existing LVS load balancing algorithm is mostly decided by the fixed weights in the distribution of server requests, which makes the LVS cluster system show load skew in long time high load operation. Therefore, this paper presents an improved load balancing algorithm. This algorithm introduced by a negative feedback mecha-nism, giving full consideration to the dynamic regulation of the server weight, can more accurately reflect the real server load. Test results show that it is better than the original algorithm.

cluster; load-balancing; negative feedback; LVS

10.3969/j.issn.1672-6146.2013.01.011

TP 301.6

1672-6146(2013)01-0041-05

email: chenwei9737@163.com.

2012-11-27

安徽省高校优秀青年基金(2012SQRL263)

(责任编校:刘刚毅)