一种Web服务器集群的动态反馈算法

蒋江波，徐志江

(浙江工业大学 省通信网技术应用研究重点实验室，浙江 杭州 310023)

一种Web服务器集群的动态反馈算法

蒋江波，徐志江

(浙江工业大学 省通信网技术应用研究重点实验室，浙江 杭州 310023)

介绍了Web服务器集群技术和负载均衡，针对静态的加权轮询算法和动态加权最小连接数算法的不足，提出一种基于动态反馈的加权最小连接数算法，该算法根据服务器的实时负载动态地改变权值的大小，再根据最小连接数算法来分配新的连接请求。通过网络仿真软件OPNET对这3种算法进行仿真、对比得出，新的算法能降低HTTP响应时间、提高负载均衡效率。

Web服务器集群；负载均衡；动态反馈；OPNET

0 引言

随着互联网的快速发展，用户数量不断增多，越来越多的网站在面对高并发数据请求时出现页面加载过慢和页面无响应的情况。对于服务器负载过大的情况有两类解决方式，一种是单个服务器的硬件优化，一种是采用集群的方式来实现。硬件优化是提高服务器的配置，这种方式往往价格比较高昂。集群是一组相互独立、通过高速网络互连且以单一系统的模式加以管理的计算机。通过负载均衡来合理分配任务，提高网络服务质量，充分利用服务器的各种资源[1]。

服务器集群下的负载均衡技术有多种实现算法，主要分为静态算法和动态算法[2-3]。静态算法主要是按固定的比例来分配任务，如加权轮询(WRR)算法。动态算法根据服务器的当前状态来分配任务，如加权最小连接数(WLC)算法[4]。

在实际场景中，服务器群组的性能差异比较大，静态方法无法得到一个准确的比值来反映实时的服务器状况。而且在负载变化较大时，动态方法用当前连接数来表示当前负载状况并不准确[5]。对此文献[6]提出了一种自适应权值的算法，当负载均衡器收到任务请求时动态更新节点权值，通过权值来反映实时负载，但是存在计算开销太大的问题。文献[7]提出了一种动态反馈算法，对实时负载量化，将量化的值与阈值比较，然后反馈新的权值，但是它的阈值是静态的，造成反馈的权值误差比较大。文献[8]提出了一种预测算法，使用线性方程来预测实时负载，但是存在一定的滞后性。

本文结合静态的权值轮询算法和动态的最小连接数算法提出一种动态反馈的加权最小链接算法，通过对服务器的性能和实现负载来动态调整节点的权值，再结合节点当前连接数来合理分配任务。

1 传统算法

1.1 加权轮询算法

加权轮询算法是对轮询算法的一种改进,它针对服务器性能不一致的情况，按照性能的高低给各个服务器分配不同的权值。性能高的服务器它的权值相对比较高，能接收的请求就比较多；性能低的服务器它的权值相对比较低，能接收的请求就少。

假设这n个服务器集群的集合用S=(S1，S2…Sn)来表示，第i台服务器的初始权值为W(Si) (1≤i≤n)，记录上一次负载均衡器接受到请求连接选择的节点i和当前权值cw。当前服务器的最大权值为max(S)。gcd(S)表示的是所有服务器权值的最大公约数[9]。算法执行前先将变量i和cw初始化为-1和0，流程如图1所示。

图1 加权轮询算法流程图

加权轮询算法特点：在轮询算法的基础上加入了权值的概念，使用权值来表示每台服务器之间的性能差异，但是没有考虑当前连接数和当前的服务器状态，不能实时反映服务器的状态，属于静态的负载均衡算法，具有局限性。

1.2 加权最小连接数算法

加权最小连接数算法使用权值表示各个服务器性能，当负载均衡器收到新的任务请求时，他会通过各个服务器当前的连接数和权值的比值大小来判断，选择比值最小的服务器来响应任务请求。

同加权轮询算法一样服务器集合为S=(S1，S2…Sn)，第i台服务器初始权值为W(Si) (1≤i≤n)，加权最小连接数算法还记录了各个节点的当前连接数C(Si)。

当负载均衡器收到一个新的连接请求时，它将根据以下规则选择服务器Sm：

C(Sm)/W(Sm)=min{C(Si)/W(Si)}

其中i∈[1，2，…，n]，W(Si)≠0。

考虑到除法所需的CPU周期比乘法多，所以判断条件C(Sm)/W(Sm)>C(Si)/W(Si)可以进一步表示为C(Sm)*W(Si)>C(Si)*W(Sm),当服务器的权值为零时，服务器不被调度[10]。流程图如图2所示。

图2 加权最小连接数算法流程图

加权最小连接数算法特点：考虑了服务器的性能和负载均衡过程中各个服务器，充分利用了服务器资源。但是仅凭当前连接数来反映服务器的负载状态显得不够合理，而且权值的设置是静态的，不能通过实时的调整来反映当前的负载能力。

2 算法改进

上述算法都没有考虑服务器的实时负载状态，存在权值设置过于主观等问题。为此提出如下改进：

(1)收集服务器的当前负载，这里选择了当前服务器的CPU利用率、内存利用率、网络带宽利用率这3个指标，在HTTP请求下服务器负载主要与这3个指标有关。

(2)计算出各个节点的实时负载，周期性地反馈到负载均衡器。

(3)将负载均衡器接收到的实时负载信息与阈值进行对比，然后动态地改变各个服务器的节点的权值，使更新的权值能准确地表示服务器的当前负载。

(4)将新的权值带入到加权最小连接数算法中以确定选择哪个服务器节点来接收新的任务请求。

2.1 服务器负载的计算

在HTTP请求中，影响负载的主要因素是服务器的CPU利用率、内存利用率和网络带宽利用率。节点Si的负载L(Si)主要由服务器CPU利用率Ci、内存利用率Mi和网络带宽利用率Bi来决定。使用式(1)来计算当前负载：

L(Si)=k1Ci+k2Mi+k3Bi，k1+k2+k3=1

(1)

其中k1，k2，k3分别表示了各自指标的所占权重，通过这种方式来更准确地反映服务器的当前负载。

2.2 周期性反馈

通过负载均衡器周期性地接收到服务器的当前负载，根据负载的大小与阈值对比来改变权值的大小。在这里阈值随着传过来的负载大小的改变而改变。将阈值用当前所有负载的均值来表示：

(2)

(3)

其中W(Si)表示第i台服务器的初始权值，C(Si)表示该台服务器的当前连接数，而且权值W(Si)不能为零。

节点新的权值就可以表示为：

(4)

周期性地获取节点的新权值W(i)′，选择当前连接数与更新后的权值的比值最小的服务器来接受新的连接请求。即服务器S(m)接受新的请求，此时要满足：

C(Sm)/W(Sm)′=min{C(Si)/W(Si)′}

(5)

3 通过OPNET软件对三种算法性能进行分析

OPNET是一款应用与网络仿真软件，它支持大量的网络通信协议和模拟系统分发，通过对离散事件的仿真来分析系统的行为和性能[11]。

OPNET网络仿真可以分为网络层、节点层、进程层[12]。集群负载均衡的3层建模设计如下：

图3 客户端拓扑结构图

(1)网络建模：为了测试加权轮询算法(WRR)、加权最小连接数算法(WLC)、改进后的动态反馈算法(DF)这3种算法的效果，选择了4台服务器集群，分别是server1、server2、server3、server4，通过100M线路连接负载均衡器。由6个子网组成客户端，cilent1～client5表示内部子网，client6表示外部子网，每个子网都包含45个用户终端，客户端拓扑结构如图3，整个负载均衡系统的网络拓扑结构如图4。

图4 网络拓扑结构图

(2)节点建模：这里最主要的是对负载均衡器建模，它遵循OSI的七层建模规则，从低到高分别是：物理层、数据链路层、网络层、传输层、会话层、表示层与应用层，由进程处理模型和队列模型组成，采用全双工的数据包进行连接，数据包传送按照7层机制来封装[13]。负载均衡器的节点模型如图5。

图5 负载均衡器的节点模型

(3)进程建模：进程层是最底层，它可以描述进程的逻辑，如通信协议、算法、统计量和操作系统等。通过状态转移图来描述进程模型的逻辑，通过连线来表示状态的转移[14]。在节点编辑器中载入加权轮询算法(WRR)、加权最小连接数算法(WLC)、改进的动态反馈算法(DF)。

为了检验算法在集群系统中的均衡效果，使用4台性能不一样的服务器组成集群，性能比例为4 ∶7 ∶10 ∶13。选择仿真设置Application_Config中的HTTP应用，模拟客户端向服务器发送HTTP请求[15]。选择HTTP场景为HTTP_IMAGE，模拟一种HTTP图片请求场景。客户端由270个节点组成，向负载均衡器发送相同请求。为了简化运算，参数k1,k2,k3的取值分别为0.5，0.3,0.2，仿真时间为35 min,更新时间设置为10 s。选取HTTP响应时间、CPU利用率为衡量算法负载均衡效果的统计量[16]。实验仿真效果如图6～9。

图6 HTTP响应时间

从图6可以看出在HTTP请求下，DF算法的HTTP平均响应时间在0.25 s左右，比WLC算法和WRR算法的效果好。

图7 WRR算法的CPU利用率

图8 WLC算法的CPU利用率

图9 DF算法的CPU利用率

从图6可以看出在HTTP请求下，DF算法的HTTP平均响应时间在0.25 s左右，比WLC算法和WRR算法的效果好。

从图7～9可以看出，DF算法中4台服务器的CPU利用率保持在3.8%左右，但是WRR和WLC算法的CPU利用率比较分散，这表现动态反馈的算法对系统资源的利用比较均衡。

综上可看出DF算法相对于WRR算法和WLC算法，其负载均衡具有更好效果。

4 结束语

Web服务器集群的核心是负载均衡算法。本文提出的基于动态反馈的负载均衡算法与加权轮询算法和加权最小连接数算法相比，考虑了服务器实时负载对负载均衡的影响，引入了周期性反馈机制来动态地改变权值的大小，实时反映负载状况，并根据实时负载情况将新的权值带入最小连接数算法中来判断选择哪个服务器接受新的连接请求。根据仿真结果可以得到，该算法能有效地降低HTTP的响应时间，均衡各服务器的CPU利用率。

[1] 张玉芳, 魏钦磊, 赵膺. 基于负载权值的负载均衡算法[J]. 计算机应用研究, 2012, 29(12): 4711-4713.

[2] 胡志刚, 张艳平. 基于目标约束的分层动态负载均衡算法[J]. 计算机应用研究, 2011, 28(3): 1105-1107.

[3] BRYHNI H. A comparison of load balancing techniques for scalable Web servers[J]. IEEE Network, 2000, 14(4): 58-64.

[4] 张前进, 齐美彬, 李莉. 基于应用层负载均衡策略的分析与研究[J]. 计算机工程与应用, 2007, 43(32): 138-142.

[5] 买京京, 龚红艳, 宋纯贺. 集群系统中的动态反馈负载均衡策略[J]. 计算机工程, 2008, 34(16): 114-115.

[6] 耿强, 黄雪琴. 一种基于自适应权值的负载均衡算法[J]. 科学技术与工程, 2013, 13(14): 4079-4081.

[7] LI W Z, SHI H Y. Dynamic load balancing algorithm based on FCFS[C]. 4thInternational Conference on Innovative Computing, Information and Control, IEEE, 2009, 10(2): 75-80.

[8] Yu Ying, Yang Pin, Liang Gang. Load balancing algorithm based on prediction for parallel instrusion detection system[J]. Computer Engineering & Design, 2011, 32(8): 2565-2568.

[9] 庄晏轩. 服务器集群中基于动态反馈的负载均衡算法[D]. 大连: 大连理工大学, 2014.

[10] 王春娟, 董丽丽, 贾丽. Web集群系统的负载均衡算法[J]. 计算机工程, 2010, 36(2): 102-104.

[11] 陈敏. OPNET网络仿真[M]. 北京: 清华大学出版社， 2004.

[12] 陈海红. OPNET网络仿真及分析[J]. 赤峰学院学报, 2010, 26( 5): 23-25.

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

[14] 史鸿雁, 李海生. 基于OPNET的集群负载均衡仿真[J]. 北京工商大学学报, 2010, 28(1): 79-82.

[15] 操惊雷, 周建国, 秦磊华. 基于OPNET的网络压力仿真[J]. 计算机工程, 2009, 35(23): 115-117.

[16] 张晓艳,扈罗全,汪一鸣，等.基于OPNET的自组织认知无线网络建模[J].微型机与应用,2013,32(23):48-51,54.

A dynamic feedback algorithm for Web server cluster

Jiang Jiangbo，Xu Zhijiang

(Zhejiang Provincial Key Laboratory of Communtication Networks and Applications，Zhejiang University of Technology，Hangzhou 310023，China)

This paper describes the technology of Web server cluster and load balancing.Since the algorithm of Wighted Round Robin(WRR) and Weighted Least-Connection(WLC) have some shortages,this paper presented an algorithm of Weighted Least-Connection with dynamic feedback.The algorithm uses a dynamic weight to represent the current load,then brings the new weight in the algorithm of WLC to assign new request of connection.Comparing three algorithms by OPNET simulation software, the results show that this dynamic feedback algorithm can reduce the time of HTTP response and improve the efficiency of load balancing.

Web server cluster; load balancing; dynamic feedback; OPNET

TP393.0

A

1674-7720(2016)01-0012-04

蒋江波，徐志江.一种Web服务器集群的动态反馈算法[J].微型机与应用，2016，35(1)：12-15.

2015-09-08)

蒋江波(1991-)，男，在读硕士生，主要研究方向：多媒体数字通信。

徐志江(1972-)，男，博士，硕士生导师，主要研究方向：信道编译码和通信信号处理。