佘 鹏

（武汉邮电科学研究院 武汉 430000）

1 引言

1.1 LVS集群系统及其相关算法

随着Internet的的飞速发展与普及，人们对网络的依赖与需求量呈现爆炸式的增长，随之而来的就是人们对网络服务需求的与质量的提高，为了满足大多数人能够正常地访问以及保证自身网络服务的稳定与高效，大多数网络服务商要采用集群技术。Web集群技术通常是指将分散的，独立的计算机通过一定的局域网或者广域网连接在一起完成单个计算机（服务器）节点不能完成的任务。负载均衡技术是Web服务器集群的关键技术之一，主要是用来将客户的服务请求按照规定的方法分发到服务器集群中的每一个服务器节点，这种规定的方法就是本文研究的负载均衡算法，主要分为静态调度算法、动态调度算法、自适应调度算法。

1.2 LVS集群系统

LVS是Linux Viual Server的缩写，是一个虚拟服务器集群系统，LVS集群通常是通过局域网或者广域网，将不同的服务器连接起来，外部用户无法直接访问每一台服务器节点，而是通过LVS集群提供的一个虚拟IP（VIP）来访问，这个虚拟IP是在LVS的前端负载均衡器上配置好的，负载均衡器也是一台服务器，但是它与其他服务器不同的地方在于它需要设置好负载均衡算法（调度算法）并且负责接收外部服务请求，然后通设定好的算法将这些请求分发到服务器集群中的一台服务器节点，自身并不处理请求。

1.3 LVS相关算法

LVS已经实现的调度算法算法有八种：1）轮叫；2）加权轮叫；3）最少链接；4）加权最少链接；5）基于局部的最少链接；6）带复制的基于局部性的最少链接；7）带复制的基于局部性的最少链接；8）源地址散列；9）最短期望延迟；10）无须队列等待。

LVS集群的已实现的这十种调度算法算法根据实现的特点可以分为两种：动态算法和静态算法。静态调度算法指的是事先设计好的调度策略，由负载均衡器来运行该算法策略，完成对客户请求的调度分配。动态调度算法是需要分析和获取服务器节点的相关信息，然后将这些信息带入调度算法中合理的分配请求。静态算法相对于动态算法的优势主要是静态算法的响应时间是最少的，因为它不需要考虑服务器节点与负载均衡之间的通信与获取服务器节点信息的额外开销，但是相对的，资源利用能力就比较差了，因为它分配任务的方式是固定的，这就意味着一些服务器可能会分配的任务过少，处于闲置状态，一些服务器分配的任务过多，处于过载状态。对于动态算法，服务器会根据服务器的负载信息来重新分配任务，所以有更好的资源利用能力。

2 WLC算法的分析与改进

2.1 WLC算法

在现有的LVS集群系统的八种负载均衡算法中，加权最少链接算法（WLC）是所有算法中相对来说效率与实用性比较高的，该算法是最小链接算法的改进，算法的核心是：为每个服务器设置一个权值Wi，这个值代表服务器的性能，权值越大的性能越好。当负载均衡器分配请求时，会在所有服务器链表中在寻找Wi不为零的情况下连接数与权值比值最小的服务器节点，如果找不到服务器节点，则会返回NULL。

算法的基本实现：假如一组服务器用｛S0，S1，S2…，Sn-1｝表示，W（Si）表示服务器节点 Si的权值，C（Si）表示服务器节点Si的当前连接数，那么服务器当前的链接总数为Csum= ∑C（Si），（i=0，1，2…，n-1），负载均衡器从集群中选择的节点为Sm，那么服务器节点应当满足下面条件：

公式中Csum是一个常量，所以公式可以简化为

由于服务器池中的每个服务器节点的权值都大于零，并且除法运算对性能的消耗要大于乘法运算，所以公式可以写成

负载均衡器接收到请求任务后，加权最小链接算法的节点选择过程如下：

图1 加权最小连接调度算法

2.2 WLC算法存在的问题

WLC算法虽然好处很多，但是也具有自身的局限性：1）权值的配置完全是由管理员配置的，不是由服务器节点的自身负载状况决定的，当系统管理员发现权值不合理时，必须要不断地调整权值。并且完全依赖管理员的经验配置权值有可能导致服务器的效率，进而影响整个服务器集群的效率。2）一旦一个服务器设定了一个权值，尽管权值是根据每个服务器节点的性能来分配的，但是随着随之权值大的服务器分配的任务增多，服务器的性能会有所下降，如果继续给权值大的服务器分配任务则有可能导致负载，所以权值应该随着服务器的性能改变而改变，本文提出了一种动态改变权值的的思想。

2.3 WLC算法的优化

本文针对WLC算法存在的一些问题，提出了一种新的动态权值分配算法：即每个服务器子节点周期性获取自身的负载状况，并与负载机端建立udp连接发送这些负载信息，负载均衡器根据每个服务器节点的负载信息来动态调整权值。为了确保算法的准确性，需要根据服务器节点的一些性能参数来动态调整权值，在信息的采集和参数的处理中，必然的要产生额外的开销，如果对系统性能的改进不能优于带来的额外开销，会更容易导致服务器的过载。所以在优化算法中，尽量不要选择过多的参数，因此只采用CPU利用率，内存利用率，以及带宽利用率三个参数来确定服务器节点的真实负载情况。

优化算法中后端真实服务器获取到自身的性能参数后，计算出新的权值，并周期性地发送给负载均衡器，负载均衡器接收到新的权值后，根据服务器节点的IP用新的权值代替旧的权值。这种频繁的写入会影响负载均衡器的性能，进而影响任务的分配。通常而言，服务器节点的处理能力在短周期内不会变化很大，所以没有必要频繁写入权值，所以我们在优化算法中引入了一个权值变化最小值（边界值）B，当权值的变化大于最小值（边界值）B的时候，原始的权值才会被替换。

我们还是用S0，S1，S2，…，Sn-1来表示集群中的服务器节点，W（Si）表示权值，用 CPU_USE，MEM_USE，BAND_USE三个参数分别表示服务器节点的CPU利用率，内存利用率和网络带宽利用率。仅仅有了三个负载参数还不够，每个参数还应有不同的重要程度，所以根据它们对服务器的影响程度还要设置三个影响因子：Kcpu，Kmem，Kband，这三个因子应该是常量，实现就应该规定好，本文将他们的值设为 Kcpu=0.5，Kmem=0.3，Kband=0.2进行后面的测试。因此，新的权值表示式表达函数为：

公式中A是一个权值改变的调节参考系数，由于IPVS中权值不能分配成小数，否则系统会报ille⁃gal weight specific的错误，所以本文将它设置为10。这个数值可以根据系统的需要设置得更大，但是这样做会有一个不好的影响就是CPU利用率，或者内存利用率，网络带宽利用率只要有一点改变，整个权值的改变就会非常大，所以为了更加准确与合理，把A的值取10。

考虑新权值L的取值情况，当服务器的负载所占比重值都为1时，表示系统处于满载状态，根据公司计算出来的权值L为0，此时负载均衡器将不会分配任务给这台服务器。当服务器处于空闲状态，则每个参数值均为0，新的权值计算出来为10。所以以上公式中L的取值范围为［0，10］。

处于服务器的真是状况考虑，当影响服务器性能的三个参数 CPU_USE，MEM_USE，BAND_USE中任何一个参数达到了一定的繁忙程度，其他两项无论处于什么状态，都不应该继续给该服务器分配任务，否则将导致服务器无法有效的处理客户请求从而影响集群系统的整体性能。所以当这三个参数种任何一个大于0.9时，都需要将权值设置为0，以避免服务器节点过载甚至宕机。

本文将负载均衡器获与服务器端交互的周期T设置为10s，即服务器每10s都会根据自身的负载情况计算出新的权值发送到负载均衡器端，负载均衡器除了转发客户端的请求之外，还要每隔10s更新一次所有服务器的权值，这样无疑会使得负载均衡器的负担过重，不利于提高集群系统的性能。因此应当有一个边界值B来控制是否更新权值，此时将边界值B代入可以得到权值的式子为

显然，这个最小值B的取值代表着对改进算法的有效评估值，B的取值越小，新权值写入IPVS的频率越高，如果B的取值为零，那么每一次的服务器节点返回的权值都满足条件，那么每次服务器节点返回的权值都会写入到IPVS调度，如果B的取值为1，那么新的权值永远不满足条件，IPVS不会做出任何改变，保持原来的调度方式。本文中将B取值设为5。

所以，动态权值反应了当前服务器节点的负载情况与处理请求能力。本文命名这种改进的WLC算法为动态权值分配算法。

3 算法实现

3.1 LVS实验环境搭配

本文选取了两台Ubuntu虚拟机作为真实服务器提供网络服务，为了模拟不同的服务器子节点，给他们的核心数依次分配为3，4，核心内存也依次分配为2G，4G来显示性能的区别。负载均衡器也用的Ubantu虚拟机作为它的Linux系统。负载均衡器安装的操作系统是Ubantu8.04，内核版本是2.6，采用该版本的系统的一大好处是它已经集成了IPVS软件，剩下的就是安装配置管理软件ipvsadm，打开Linux的命令行输入指令：sudo apt-get install ipvsadm，然后等待软件安装成功。等安装完成后输入：sudo ipvsadm，看到版本号则说明安装成功。

3.2 客户端模拟压力测试配置

完成了LVS实验环境的搭配后，我们还需要在客户端机器上安装模拟压力测试的相关软件。本文选择的是微软公司提供的免费测试软件WAS（Web Application Stress）来对集群系统做高负载，多用户请求并发的压力测试。在WAS客户端配置好向集群提交请求服务，会生成一份集群系统的数据吞吐量（Bytes Recv Rate）和平均响应时间（TTFB Avg）报告。本文主要采用TTFB Avg的值来对比分析原来算法与优化算法的性能好坏。

3.3 服务器负载参数的获取

本文的实验环境是基于node.js语言来测试的，在node.js提供好的API中，有可以直接获取这些参数的方法，具体如下：

1）CPU和MEM的参数获取

根据node.js提供的api，cpu利用率可以用os.cpus（）来获取，该方法返回一个对象数组，包含安装的每个CPU/CPU核的信息：具体的属性分别有user（CPU花费在用户模式下的毫秒时间数），nice（CPU花费在良好模式下的毫秒数），sys（CPU花费在系统模式下的毫秒时间数），idle（CPU花费在空闲模式下的毫秒时间数），irq（CPU花费在中断请求模式下的毫秒时间数），通过这四个属性可以得出cpu的利用率公式：CPU_USE=（user+nice+sys）/（user+nice+sys+idle）。

内存利用率的获取则要使用os.totalmem（），os.freemem（）这两个函数，os.totalmem（）方法会以整数的形式返回所有系统内存的字节数，freemem（）方法则是以整数的形式返回空闲系统内存的字节数，因此服务器的内存利用率MEM_USE=1-os.freemem（）/os.totalmem（）。

2）网络带宽利用率的获取

Linux系统中提供了命令“netstat-e”查看系统以太网的统计数据。通过网卡接收和发送的数据数值相加，我们可以得到当前时刻的数据总流量，然后通过相同的方法继续获取了下一个时刻的数据总流量，用下一时刻的总流量减去当前时刻的总流量再除以时间间隔，得到的就是实际的网速，接下来在用实际的网速除以网卡的速度，得到的就是网络带宽利用率。具体的实现公式如下：

本文将ΔT取值为1，即每隔1s对网络进行一次统计数据流量，通过nodejs获取网络的相关信息要用到exec（）函数，exec（）函数一般可以接受一个回调函数作为参数，回调函数中有三个参数它们通常是err，stdout和stderr，获取到的网络信息就在stdout中。

3.4 服务器与负载均衡器端的通信

服务器端通过收集自身的系统参数，并计算出新的权值，改权值需要传递到负载均衡器端，然后通过负载均衡器把新的权值设定到负载均衡算法中实现。通常传输层的协议有TCP、UDP两种，由于传输的数据很少，而基于UDP协议的正好是无连接模式通讯，占用资源少，响应速度比较迅速，延时低，所以本文采用的基于UDP协议的传输数据方式。

同时，node.js采用UDP编程也非常容易实现，在服务器端编写一段发送权值程序，每隔10s执行一次，具体代码如下：

图2 服务器与负载均衡器端的通信

3.5 实验结果与分析

测试运行结束后，将WLC算法与优化后算法的平均响应时间（TTFB Avg）转化成折线图形式，可以更加直观地看出两种算法的差异。表中横坐标为请求任务连接数，纵坐标为TTFB（ms）。

图3 客户端用户任务请求响应时间

从图3中我们可以看出，当用户的访问请求不太多时，WLC算法的等待响应时间要比优化算法要稍短，主要是因为权值的写入，读取等一系列操作造成了额外开销，影响了服务器与负载均衡器的性能。但是随着用户的访问请求不断地增加，优化算法的响应时间会明显优于WLC算法，整个服务器集群的性能会得到一定程度的提升。需要注意的是，无论是优化算法还是WLC算法，随着请求任务不断的增多，当达到一定的数量后整个集群系统会临近一个饱和的状态，因为每台服务器的性能有限，无论怎么分配都会使得各个服务器节点的资源利用率达到饱和。出现这种情况时，我们应该考虑增加服务器来扩展集群，而不是担心算法自身的问题。

4 结语

本文主要通过研究LVS集群的加权最小链接算法，发现算法中只考虑服务器节点的当前链接数作为节点的负载情况的参考标准是不太合理的，并提出一种采用CPU利用率，内存利用率，以及网络带宽利用率三个参数来描述服务器节点的负载情况的动态权值分配算法。并通过实验证明了该算法相对于原来的WLCS算法在一定程度上提高了LVS集群的性能。