一种改进的动态反馈负载均衡算法

陈泰安

（武汉科技大学 信息科学与工程学院，湖北 武汉 430081）

随着网络需求的不断增加，集群服务器技术将以其高可靠、高性能的优势逐步取代以前单一服务器的工作模式，它提供了一个负载性能易于扩展的、高效可靠地服务器性能解决方案。然而集群服务器经常出现负载不平衡的现象，这成了制约集群系统性能体现的一个关键因素。因此，有必要对现有的调度算法进行改进，以提高系统资源的利用率，使集群技术的效能得到更好的体现，从而有效的减少用户地等待时间[1]。（Dynamic Feed-Back）算法[4]等。下面将对加权最小连接算法和DFB算法做进一步的分析比较。

1）加权最小连接算法

加权最小连接算法在集群的实际使用中是最常用的负载调度算法[5]。加权最小连接算法的核心思想[6]：假设有 S0，S1，…，Sn-1台服务器，服务器 Si的权值用 W（Si）来表示，其当前连接数用 C（Si）来表示，则 Csum=∑C（Si）（i=0，1…，n-1）。 当服务器 Sm满足条件：，i=0，1，…，n-1，W（Si）≠0时，将新的连接请求发送到。而在此次计算中是常数，故上述条件可简化为：C（sm）/w（sm）=min{C（si）/W（si）}，i=0，1，…，n-1，w（Si）≠0。 各个服务器用相应的权值表示其处理性能。算法在调度新连接时尽可能使服务器的已建立连接数和其权值成比例。该算法通过仅通过服务器的连接数来判断节点的负载，并不准确，因为如服务的类别、CPU占用率、流量等也需要考虑[7]。

2）DFB 算法

DFB算法的基本思想是：首先设定一个阈值f，当有新的服务请求时，将负载量小于f的m个服务器选出来做为备选

1 常见的负载均衡算法

常见的负载均衡算法主要包括静态负载均衡算法和动态负载均衡算法两种。其中静态负载均衡算法不考虑各服务节点的负载情况，只按算法既定的方式分发服务请求；动态负载均衡算法如加权最小连接算法可根据系统当前的负载状况动态的分发服务请求。这类算法的问题在于：一段时间内将所有新到达的请求消息发送给请求量最小的后台服务器，如果在这段时间内新到达的请求较多则反而会破坏负载均衡[2]。另外，还有引入了随机性的Pick-KX算法[3]和DFB服务器集合。然后根据各服务器的性能指数C（Sx）来计算分配概率最后修改Sx的负载。

2 算法设计思想

2.1 各服务节点负载量计算

集群系统经过长时间的运行，调度器上记录的负载量将不能准确的反映各服务节点负载的实际情况。所以周期的采集服务节点的负载信息可以保证调度器中记载的数据的准确性。每隔一个时间T，各服务节点向调度器汇报该节点的CPU利用率、内存利用率、磁盘访问率、网络带宽占用率、进程数量占用率5项性能参数。该节点的负载量Load（Si）可如下计算：

Load （Si）=R1*Lcpu（Si） +R2*Lmemory（Si） +R3*Li0（Si）+R4*Lbandwidth（Si）+R5*process（Si）其中。

2.2 各服务节点处理能力计算

计算第i台服务器的最大处理能力时，一般考虑以下几个指标：CPU的数量ni，处理速率C （Ci），磁盘 I/O速率C（Di）， 内存容量 C （Mi）， 网络吞吐量 C （Ni）， 最大进程数 C（Pi）。 该节点的最大处理能力C（Si）可如下计算：

C（Si）=K1*niC（Ci）+K2*C（Di）+K3*C（Mi）+K4*C（Ni）+K5*C（Pi）

其中∑K=1，i=0，1…n-1。

2.3 算法具体步骤

1）各服务节点定时上报各项性能参数。

2）计算各节点负载量和处理能力。

3）设定一个阈值H。

4）当一个新的任务请求到来时，如果的负载量Load（Si）=min{Load（Sk）}，k=0，1…，n-1，则将此节点加入到候选集合 I中；如果其他节点满足 Load（Sm）＜Load（Si）+H，m=0，1…，n-1 则将此节点加入到集合I中。

5）计算候选集合中各节点的任务分配概率 P（Sk）。P（Sk）=Y（Sk）/∑Y（Si），k=0，1…，n-1，其中 Y（Sk）=C（Sk）/Load（Sk）。

6）根据候选节点的概率，将任务分配到I中的一个节点上。

7）修正该节点的负载量。

3 算法测试

测试采用平均应答延时和吞吐量作为算法性能的评价指标。平均应答延时即系统对服务请求的平均响应时间。吞吐量就是系统在单位时间内处理的数据量。实验所用测试的设备条件如表1所示。

表1 实验设备数据Tab.1 Experimental device data

在自行搭建的负载均衡平台上进行了测试。系统由4台由以太网连接的PC组成，操作系统为CentOS 5.7，运行Apache 2.4提供 Web服务。测试中设参数 R={0.3，0.3，0.2，0.1，0.1}，K={0.3，0.3，0.2，0.1，0.1}。 周期设为 20 s，f设为0.25。测试的用户请求由4台PC提供，运行请求发生程序。图1给出了3种算法的平均应答延时的结果对比。图2给出了3种算法的吞吐量的测试结果对比。其中黑框代表加权最小连接算法，白框代表DFB算法，阴影框代表改进的动态反馈算法。

图1 3种算法平均应答延时对比Fig.1 Three algorithms average response delay comparison

图2 3种算法吞吐量对比Fig.2 Three algorithms throughput comparison

从图1和图2可以看出：当连接数较少时，3种算法的性能相似；当连接数增多后，改进的动态反馈算法逐渐体现出性能优势。相比较于最小连接算法和DFB算法，新算法能有效的减少平均应答延时、增大吞吐量。

4 结束语

新算法对每台服务器的处理能力和当前负载进行综合考虑，并且在DFB算法的基础上对其节点的分配算法作了进一步的优化。通过实验结果可知，新算法取得了比最小连接算法和DFB算法更好的负载均衡效果。

[1]许海成，傅锦伟.服务器集群负载均衡的建模与仿真研究[J].计算机仿真，2012，29（3）:180-183.XU Hai-cheng，FU Jin-wei.Research on model and simulation of load balance for server cluster[J].Computer Simulation，2012，29（3）:180-183.

[2]张昊，廖建新，朱晓民.增强型动态反馈随机分发负载均衡算法[J].计算机工程，2007，33（4）:97-99.ZHANG Hao，LIAO Jian-xin，ZHU Xiao-min.Advanced dynamic feedback and random dispatch load-balance algorithm[J].Computer engineering，2007，33（4）:97-99.

[3]Genova Z，Christensen K J.Challenges in URL Switching for Implementing Globally Distributed Web Sites[C]//Proc.of the Workshop on Scalable Web Services，2000:89-94.

[4]刘建，徐磊，张维明.基于动态反馈的负载均衡算法[J].计算机工程与科学，2003，25（5）:65-68.LIU Jian，XU Lei，ZHANG Wei-ming.A load balancing algorithm based on dynamic feed-back[J].Computer engineering&Science，2003，25（5）:65-68.

[5]周松泉.一种改进的集群动态负载均衡算法[J].计算机与现代化，2012，（1）:135-139.ZHOU Song-quan.An improved dynamic load-balancing algorithm for cluster[J].Computer and Modernization，2012（1）:135-139.

[6]王春娟，董丽丽，贾丽.Web集群系统的负载均衡算法[J].计算机工程，2010，36（2）:102-104.WANG Chun-juan，DONG Li-li，JIA Li.Load balance algorithm for web cluster system[J].Computer Engineering，2010，36（2）:102-104.

[7]刘斌，徐精明，代素环，等.基于Linux虚拟服务器的负载均衡算法[J].计算机工程，2011，37（23）:279-287.LIU Bin，XU Jing-ming，DAI Su-huan，et al.Load balancing algorithmbasedonLinuxvirtualserver[J].ComputerEngineering，