苏命峰，陈文芳，李仁发

(1.湖南大学信息科学与工程学院，湖南 长沙 410082;2.湖南商务职业技术学院，湖南 长沙 410205;3.湖南安全技术职业学院，湖南 长沙 410151)

Linux Virtual Server，简称LVS，是Linux开放源代码的集群软件［1］，常应用于大型重负载站点.LVS集成在Linux内核中，将一组服务器(节点)构成一个虚拟服务器，对外提供一个虚拟IP地址，响应用户访问请求，可提供可伸缩、高可用、高性能的WEB、FTP、MAIL、视频等服务.它有网络地址转换(VS/NAT)、IP隧道 (VS/IP Tunneling)和直接路由(VS/DR)三种负载均衡模式.为快速响应客户请求，LVS系统将大量并发的访问请求，通过合理的策略调度到多个提供真实服务的节点.LVS系统应根据不同的网络应用环境，选择正确的负载调度算法.

1 负载调度算法介绍

LVS集群属于任务级负载均衡集群，采用以IP连接为粒度的集中式任务分配，支持多种不同的负载调度算法，在一定程度上解决大量用户突发性访问引起的负载不均问题.负载调度算法是整个集群系统的关键，直接决定集群系统的性能和效率.好的调度算法让整个集群系统的负载均匀分布，不发生倾斜，每台服务器充分发挥各自性能.反之，整个集群系统出现倾斜，有些服务器负载过轻，另一些则负载过重.按照负载调度算法的实现原理可分为静态调度算法、动态调度算法和自适应调度算法.

1.1 静态调度算法

静态调度算法根据事先定好的调度策略分发用户请求，不考虑集群系统运行时各真实服务器的负载情况.它简单、易实现，无节点负载情况检测和过载节点迁移等额外开销，但适应性不强，容易引起节点间的负载不平衡，特别是负载重时，集群系统性能变差.

1.2 动态调度算法

动态调度算法实时跟踪真实服务器的活动连接，结合具体策略将新的请求分发到合适的真实服务器.算法实现较为复杂，对任务的分配管理以及信息收集等会造成额外的系统开销，定期收集的信息也会有一定误差.不过调度得当，还是可以明显提高集群系统性能，是负载均衡研究的重点，应用广泛.

1.3 自适应调度算法［2］

自适应调度算法是一种智能的算法，为适应不断变化的系统状态和复杂的网络环境，可动态改变算法参数以及策略，来调整集群系统的负载调度行为，如动态反馈负载均衡算法等.它比动态调度算法更复杂，算法自身开销较大，负载轻时集群系统性能提升不明显，是负载均衡研究的热点，处于发展阶段，目前应用较少.

2 常用负载调度算法

目前基于IP层的IPVS软件提供10种调度算法［3］，适用不同的网络应用环境.

2.1 轮询(Round －Robin Scheduling，RR)

把新的连接请求按顺序调度到不同的服务器上，以实现负载均衡.每次负载调度执行i=(i+1)mod n运算，轮流选出第i台服务器.当服务器的权值为0时，表示其不可用而不被调度.算法简单，实现容易，执行效率高，是一种无状态的静态调度算法，它没有考虑服务器的连接情况，适合服务器性能相同的集群系统.否则容易造成服务器间的负载不均衡.

2.2 加权轮询(Weighted Round－ Robin Scheduling，WRR)

根据服务器的性能为其设定一个相应的权值，调度器根据权值的高低，采用轮询方式将用户的访问请求发送给服务器，为改进的RR算法.服务器的缺省权值为1，需要手工确认不同服务器的权值，权值高的服务器先收到连接请求，比权值低的服务器处理更多的请求.如果三个服务器A、B和C的权值分别为1、2和3，则在一个调度周期内调度序列依次为:CCBCBA.该算法继承RR算法的简易性，可在某种程度上解决服务器性能不一致的问题.但算法没有考虑服务器当前连接等负载情况，当请求的服务时间变化很大时，容易导致服务器之间的负载倾斜.

2.3 目标地址散列(Destination Hash Scheduling，DH)

将请求报文中的目的IP地址作为散列关键字，从调度器上事先设定好的静态哈希表中找出对应的服务器，若该服务器可用且未过载，就将请求发送到该服务器.在实现时可采用素数乘法Hash函数，使散列值均匀分布，以尽量避免出现Hash冲突情况.

2.4 源地址散列(Source Hash Scheduling，SH)

与DH算法正好相反，源地址散列算法将请求报文中的源IP地址作为散列关键字，从调度器上的静态哈希表中查找到对应的服务器，若服务器可用且未过载，就将请求发送过去，否则返回空.算法流程与DH算法相似，可一起使用，它们常应用于防火墙集群，都是静态调度算法.

2.5 最小连接(Least－ Connection Scheduling，LC)

把新的访问请求调度到当前连接数最少的服务器，是一种动态调度算法，当前连接数=256*活跃连接数+非活跃连接数.调度器需要记录每台服务器当前的活跃和非活跃连接数，用来估计服务器的负载情况.最少连接法没有考虑服务器之间性能的差异.当服务器性能相同时，该算法能将请求平滑分布到各服务器，否则算法的负载均衡性能不理想.

2.6 加权最小连接(Weighted Least－Connection Scheduling，WLC)

根据服务器的性能设定一个相应的权值，服务器默认权值为1，权值越大表示其处理能力越强.调度器根据服务器的权值与其活跃连接数的比值将新的用户请求发送到处理能力强的服务器.假设有一组服务器 S={S0，S1，…，Sn－1}，服务器Si的权值为W(Si)，当前连接数为C(Si).只有服务器Sm满足条件:

当前新用户请求才会发送到服务器Sm.算法考虑了服务器的当前连接情况和处理能力，是改进的LC算法.对于普通应用，算法调度效率高，应用比较广泛，是IPVS默认的调度算法.缺点是当前连接数表示服务器的综合负载不够精确和全面，服务器权重不能动态修改，当用户的访问方式相差比较大时，该算法也会引起服务器之间的负载不平衡.

2.7 基于局部性的最少链接(Locality－Based Least Connections Scheduling，LBLC)

调度器根据请求报文中的目的IP地址，找到最近响应该地址请求的服务器，如果服务器可用，就将请求发送给它;如果该服务器过载或不可用，则采用LC算法，从其他可用、不过载的服务器中选择一台服务器，再将请求发送过去.系统为请求报文中的目的IP地址与调度的服务器进行关联，设定一个存活期限，并定期回收过期的关联，有一定的灵活性.该算法为动态调度算法，考虑了局部性原理，可提高服务器的Cache命中率和处理效率，可应用于Cache集群.

2.8 带复制的基于局部性最少链接(Locality－Based Least Connections with Replication Scheduling，LBLCR)

根据请求报文中的目的IP地址，找到最近响应请求服务器所在的服务器组，采用LC算法从当前服务器组中选择一台连接数最少的服务器，若该服务器没有过载就将请求发送给它;如果该服务器过载，就从集群后台中选一台负载最轻的服务器加入到服务器组中，并将请求发送到该服务器.为降低对镜像的拷贝，提高系统性能，可以将一段时间内没有发生变化的服务器组中的最忙服务器删除.该算法为LBLC算法的补充和发展，也需要定期释放目的IP地址与服务器的关联，主要用于Cache集群.

2.9 最短期望延迟(Shortest Expected Delay Scheduling，SED)

一种期望最小化每个任务预期延时的动态算法，目的是找到预期任务量与处理速率比值最小的服务器.假设一组服务器 S={S0，S1，…，Sn－1}中，服务器 i的预期任务量为当前连接数C(Si)加1，处理速率为服务器权重W(Si)，权值越大处理速率越大.当服务器Sm满足以下条件:

新连接请求会被调度到Sm.最短期望延迟改进了WLC算法，考虑了连接的预期成本，即当前连接数加1，在某些情况下要比WLC算法好.例如:ABC三台服务器权重分别为1、2、3，连接数分别是 1、2、3.如使用 WLC 算法，一个新请求会分发给ABC中的任意一个.如果使用SED算法，通过进行［C(Si)+1］/W(Si)运算，新请求会分发给C.

2.10 无须队列等待(Never Queue Scheduling，NQ)

当有空闲服务器(即当前连接数为0)时，不需要任何计算，调度器直接把请求分配给空闲服务器;当没有空闲服务器时，按照SED算法找到预期任务量与处理速率比值最小的服务器，并将请求调度过去，是对SED算法的一种改进.

以上调度算法均以IP连接数表示服务器负载，其中RR、WRR、DH、SH 属于静态调度算法，LC、WLC、LBLC、LBLCR、SED、NQ 属于动态调度算法.在 WRR、WLC、SED、NQ算法中体现服务器性能的权值W，一般根据服务器的CPU、内存、磁盘I/O和网络等使用率综合设定.SH和DH主要用于防火墙集群，LBLC、LBLCR主要用于 Cache集群，WRR、WLC、SED、NQ 常用于 WEB、FTP等集群.

3 LVS负载调度算法测试

测试平台见图1，采用VS－DR模式［3］搭建一个提供Web服务的LVS集群，在一台CPU为Intel酷睿i3(2.4G)、内存4GB的物理计算机上通过虚拟机软件VMware Workstation 8，同时运行4台内存为512MB的虚拟计算机，分别是负载均衡器(即调度器)和3台真实服务器.

图1 LVS负载调度算法测试平台

负载均衡器和3台真实服务器采用Redhat Enterprise Linux 6操作系统，都安装Apache组件，启动httpd进程.负载均衡器采用 LVS管理组件 ipvsadm，版本 1.2.1［4］.考虑到 3台服务器性能相同，其权值都设置为1，每台WEB服务器提供一个静态测试主页index.html，大小为20KB.测试客户端采用Windows XP SP3操作系统，运行WEB应用负载测试工具 Web Application Stress Tool［5］，通过设置不同的高并发连接数，模拟大量用户并发访问LVS集群系统.每次测试时间周期为5分钟，以发出足够的访问请求，避免产生失真的测试结果.主要参考Time To First Byte(TTFB)值，比较WRR、WLC、SED、NQ等负载调度算法和无集群系统的性能，TTFB指测试端收到真实服务器响应请求的第一个数据包所用的时间，值越小说明系统性能越好.

表1 不同调度算法与无集群系统的TTFB值(ms)

由表1的分析结果可得到采用不同调度算法与无集群系统在不同并发数下TTFB的变化曲线图，图2表明，在不同的并发数下，采用WRR、WLC、SED、NQ等调度算法的集群系统的 TTFB值远小于无集群系统，说明采用 WRR、WLC、SED、NQ等调度算法的集群系统性能相比较无集群系统，性能有明显提升，在这些调度算法中，以NQ性能最佳.

图2 不同调度算法与无集群系统TFFB的变化曲线图

4 结语

通常情况下，动态调度算法比静态调度算法更能反映系统的实际情况，实用性强，性能要高.常用的WLC和改进的SED、NQ等算法虽然能较好地用于集群系统的负载均衡调度，但也存在一些不足:没有考虑CPU、内存使用率等，仅以活动连接和非活动连接来表示真实服务器的综合负载并不精确，随着负载的增加，相应服务器的处理能力会发生变化，进而引起服务器间的负载不平衡，算法不能及时掌握真实服务器的运行情况.为此，可采用动态反馈负载均衡算法等自适应调度算法，在调度器运行Daemon进程，监视服务器的实时负载和响应情况，及时调整服务器的请求比例，以获得更高的吞吐率，但需修改Linux系统内核等，实现复杂.

［1］章文嵩.可伸缩网络服务的研究与实现［D］.长沙:国防科学技术大学博士学位论文，2000.

［2］王强.基于LVS集群负载均衡算法的研究与改进［D］.成都:电子科技大学硕士学位论文，2010.

［3］苏命峰.三种LVS负载均衡模式及性能研究［J］.自动化与信息工程，2011，(6):17 －21.

［4］Song W.IPVS［EB/OL］.http://www.linuxvirtualserver.org/software/ipvs.html，2011 －02 －08.

［5］Ching A，Silva P，Wagner A.利用 WebApplicationStressTool(WAS)做性能测试［EB/OL］.http://tech.ccidnet.com/art/1077/20040919/718477_1.html，2006 －08 －01.