一种改进加权最小连接算法及在CDN的负载均衡技术中的应用分析

(山东科技大学 计算机科学与工程学院，山东 青岛 266590)

内容分发网络[1]的内容路由技术一般由负载均衡系统来实现，是内容分发网络关键技术之一[2]。负载均衡的目的是运用多评估机制选择最佳节点并将用户路由到节点内合适的服务器上。内容路由决定了就近服务的思想能否实现，决定了整个内容分发网络系统的运行效率和性能，因此负载均衡是整个内容分发网络的基础[4]。常用的负载平衡算法有静态和动态两种。静态负载中，代表算法是轮询算法[5]和加权轮询算法[6]。静态负载平衡算法的优点是简单，缺点是由于不考虑服务器节点的性能和当前负载状态，长时间运行将导致负载不平衡。由于动态负载均衡算法[5]无需先验知识进行决策，可以根据实时服务器负载状况，自适应调整任务在各服务器中执行顺序，从而提高了系统整体性能，因此在系统中得到广泛应用。现有的动态负载均衡算法主要有一致性哈希法[7]、最小连接算法(least connection, LC)[8]和加权最小连接算法(weighted least connection, WLC)[9]等。其中最小连接算法能动态获取服务器负载情况，但只关注连接数，没有关注CPU和内存使用率等问题，会出现连接数小但服务器资源消耗较高的情况[10-11]；文献[12]提出一种异构集群负载索引和负载均衡算法，但对服务器负载情况的衡量只以任务数量为参考；文献[13]提出一种自适应权值最小负载实现负载均衡的算法，但没有考虑服务器所能承受的最大负载；文献[14]提出一种基于可变因子α的加权最小链接算法，根据各服务器的负载情况，对α的值进行调整并在一定程度上达到了负载均衡；文献[15]提出一种将终端连接数作为影响因子和各服务器参数进行综合分析的算法，没有考虑磁盘I/O且只应用于特定的场景中。上述文献对负载均衡算法都做了改进，但都有其片面性。本研究对最小连接算法进行改进得到一种IWLC(improved weighted leastconnection)算法，提出了针对动态权值的关键参数新的计算方法。IWLC算法通过动态获取服务器反馈性能指标与负载指标计算出当前集群中最优服务器进行任务的调度分配，可更好达到负载均衡效果，更好地解决CDN系统中大规模用户访问请求下的负载均衡问题。

1 算法介绍

1.1 典型负载均衡算法

1.1.1 最小连接算法

最小连接算法思想是：假设系统内各个服务器性能一致，当有新的任务到来时，总是将该任务分配给连接数最少的服务器[4,7]，即对于现有服务器集群S={S1，S2，…，Sn}，每个服务器连接数为C(Si),1≤i

1.1.2 加权最小连接算法(IWLC)

加权最小连接算法算法[3]思想是在LC算法基础上，考虑了不同服务器的性能差异，设置不同的权值来标识服务器性能指标，在任务调度时为权值较大的服务器分配较大比例的活动连接[8,10]。IWLC算法充分考量服务器性能指标及服务器动态负载指标，因此在负载均衡方面性能要优于最小连接算法；然而，现有的IWLC算法对性能指标的计算相对简单化，而系统实际运行过程中性能指标与负载指标更加复杂，因此IWLC算法仍有优化改进的空间。

1.2 改进加权最小连接算法(IWLC)

1.2.1 IWLC算法思路及流程

CDN应用系统中，负载均衡服务器实时接收各服务器节点的负载情况及资源使用状态，IWLC算法利用实时获取的参数来计算各服务器节点的综合性能指标并以此作为任务调度的依据，选择出最适合执行任务的服务器，从而完成任务的动态调度。

IWLC算法流程如下：

1) 集群中各真实服务器节点周期性计算各自的CPU空闲率、内存空闲率、磁盘I/O空闲负荷、负载连接数，并反馈给负载均衡调度器；

2) 负载均衡调度器根据各服务器节点反馈的信息，计算服务器的综合性能指标P(Si)、综合负载指标C(Si)以及综合评价指标参数F(Si)，并计算出各个结点的权值wi；

3) 负载均衡调度器根据计算出的权值修改原先的权重，将更新后的权重写入IPVS内核；

4) Linux内核启用LVS编译安装IPVS内核，IWLC算法根据新的权值选择最合适的服务器进行任务分配。

1.2.2 IWLC算法中关键参数计算

1) 集群S由n台服务器组成，S={S1,S2,…,Sn}；

(1)

(2)

(3)

(4)

(5)

(6)

其中w1、w2、w3、w4分别代表各服务器性能指标因素的权重。考虑到CPU空闲率和内存空闲率两个指标在描述服务器性能方面的重要性，因此对于4个权重的赋值分别是：w1=0.4、w2=0.4、w3=0.1、w4=0.1。若当前的系数w1、w2、w3、w4不能很好反映应用的负载，可以对系数进行不断的修改，直到找到一组贴近当前应用的系数。经过多次试验，判定系数w1=0.4、w2=0.4、w3=0.1、w4=0.1是最优的。

4) 为了更加有效预测每台服务器节点所能承受的负载能力，引入服务器的综合评价指标参数F(Si)，其计算方法如下：

(7)

F(Si)的变化规则为：若要使F(Si)取值最小，其对应的服务器Si要么满足服务器性能指标P(Si)最大，要么满足服务器负载指标C(Si)最小，或者同时满足这两个条件，此时Si便是集群中最合理的执行新任务的服务器。

5) 设服务器的Si权重为wi，则令wi=1/F(Si)。F(Si)取值越小，服务器Si的动态权重取值越大，负载指标就越小，服务器Si的连接数就越小。

1.2.3 IWLC算法的代码及分析

IWLC算法只做一次for循环，依次比较各服务器综合指标参数F(Si)，F(Si)取值大的被舍弃，继续比较下一个，直到第n个服务器，选出F(Si)值最小的作为下一轮要执行新任务的服务器，算法时间复杂度为O(n)，可见对参数的改进并没有造成更高的时间复杂度。

Algorithm:Improved Weighted Least ConnectionInput:CPU idle rate Ci,Memory idle rate Mi,I/O rate Di,Bandwidth Ni,Number of load connectionsLi Number of server n, Weight w1,w2,w3,w4Output:The most weighted serverSiInitialize an Array of n-dimensions arr with 0fori=1;i≤n;i++()do R(i)cpu=Ci/maxC1,C2,…,Cn() R(i)mem=Mi/maxM1,M2,…,Mn() R(i)disk=Di/maxD1,D2,…,Dn() R(i)net=Ni/maxN1,N2,…,Nn() R(i)con=LiL(i)max,CSi()=R(i)con PSi()=w1∗R(i)cpu+w2∗R(i)mem+w3∗R(i)disk+w4∗R(i)net FSi()=CSi()/PSi(),Wi=1/FSi() W=Wi arri[]=W Write the weightWi to the IPVS kernel and make install the IPVS kernelend doWmax=arri[]maxreturn the most weighted server Si

IWLC算法通过本研究提出的动态权值计算方法得到服务器综合评价指标值，将新任务分配到F(Si)值最小的服务器Si上执行，此时Si是当前集群中最适合承担负载的服务器。

2 实验与分析

2.1 实验设计

实验模拟CDN应用系统中边缘服务器节点应对客户访问请求的负载均衡效果，本研究利用实验室现有设备，基于章文嵩博士[9]所提出的Linux虚拟服务器开源项目的集群体系结构技术搭建了一套模拟CDN应用系统边缘服务器节点系统。

为验证提出的IWLC算法在解决CDN应用系统中集群负载均衡问题方面的有效性，同时对比本算法与加权最小连接算法[5]在服务器响应时间与吞吐量两个评价指标上的实现效果，设计具体实验如下：

1) 在负载均衡服务器上通过IPVSADM管理软件部署本研究提出的IWLC算法，而IPVSADM自身已经配置了常用负载均衡算法，如加权轮询算法加权最小连接算法等；

2) 在测试客户机器上安装部署LoadRunner系统负载测试工具，用来记录模拟用户访问请求后台服务器内容过程中系统平均响应时间与吞吐量；

3) 分10组模拟用户访问过程，请求任务数以每组递增100的方式从100到1 000进行实验，利用LoadRunner记录系统平均响应时间与吞吐量指标，每组测三次，最终取平均值；

表1 10组平均响应时间对比实验结果表Tab.1 Experimental results of average response time

4)用MATLAB画图对比本研究所提IWLC算法与加权最小连接算法的系统平均响应时间和系统吞吐量。

2.2 实验结果分析

提出的IWLC算法与WLC算法的系统平均响应时间对比实验结果如表1和图1所示。可以看出：当任务请求数低于300时，IWLC算法对应的系统平均响应时间要长于WLC算法，原因在于IWLC算法需要实时获取各服务器传送过来的性能指标及负载指标以计算各服务器的综合性能指标，引起额外的资源消耗，在任务请求数量较低的情况下造成了系统响应时间延长；但是随着系统用户访问请求任务数的增加，由于IWLC算法能够充分利用系统资源，有效调度用户任务请求，IWLC算法优于WLC算法。

2) IWLC算法与WLC算法的系统吞吐量对比实验如图 2所示。由图可见：当任务数小于500时，IWLC算法测试出的系统吞吐量小于加权最小连接算法；当任务数为600～1 000时，IWLC算法测试出的系统吞吐量逐渐超过WLC算法测试出的系统吞吐量，大约提高了1 347 bytes/ms，随着任务请求数的增多，IWLC算法对于合理使用各服务器更加有优势。

图1 平均响应时间实验结果对比图Fig. 1 Comparison of Experimental Results of Average Response Time

图2 系统吞吐量实验结果对比图Fig. 2 Comparison of experimental results of throughput

综上，IWLC算法有效提高了系统平均吞吐量，尽可能避免服务器过载，将任务分配到具有最佳性能的服务器，加强系统资源的有效利用。

3 结论

本研究从CDN应用系统的本地负载均衡方面，针对边缘服务器如何应对大量用户访问请求而保障负载均衡的问题，基于加权最小连接算法，提出了一种改进加权最小连接的CDN负载均衡算法。

相比于WLC算法，IWLC算法充分考虑了服务器自身资源使用情况以及负载情况等因素，通过动态实时收集各服务器节点的资源性能指标及负载指标，综合计算出当前的最优节点，完成访问请求任务的分配，保证最大限度地利用系统资源，并对用户的访问请求更快地做出响应。但IWLC算法也存在不足，如任务请求数较少时，负载均衡调节器定时发送请求报文获取并处理真实服务器的各种信息带来的额外开销会影响整个系统的测试与评估。本工作没有考虑到当CPU空闲率、内存空闲率、磁盘I/O空闲负荷、网络带宽四个参数都不大于90%的服务器时的算法情况，比较理想化，需要进一步研究和细化算法来解决上述情况下的问题。