服务器集群负载均衡算法分析

游灿虹

（四川大学网络空间安全学院，成都610065）

0 引言

在计算机技术的飞速发展的今天，互联网使用人群日益增长，网络业务请求数呈现爆炸式增长，这给传统的单一服务器带来巨大压力。虽然通过给服务器的硬件进行升级能够解决一定的问题，但是当硬件设备提升到一定程度后，继续提升所带来的的花费将呈几何式增加。这并不是所有企业都能负担得起的。而服务器集群化方案因为其高性价比和良好的拓展性，被广泛的使用。由此引出了一个新的问题，即如何合理地分配业务请求到各个服务器上，又能使得集群内部不出现因业务请求过多而导致的服务器节点过忙或者因业务请求过少而出现服务器节点闲置的情况，这个问题也就是常说的负载均衡问题。

本文将对服务器集群的负载均衡算法进行研究和总结，对常用的负载均衡算法进行介绍和分析，并对负载均衡算法的发展情况进行总结。

1 负载均衡分类

我们一般用负载来描述一个系统的忙闲程度。而所谓的负载均衡，就是指将负载合理地分摊到多个节点服务器上去并行执行，从而协同地完成系统的工作任务。它是构筑在原有网络架构之上的，提供了一种廉价有效的方法去扩展服务器和网络设备的带宽、加强处理网络数据的能力、提高了吞吐量、增强了网络的可靠性和灵活性[1]。根据负载均衡的不同特点可以将其分为多个类别，下面我们将从实现方式和地理结构上对其进行介绍。

1.1 根据实现方式进行分类

（1）软件负载均衡

软件负载均衡的解决方案是指在服务器相上安装附加软件来实现负载均衡，例如Nginx、DNS Load Balance 等，它拥有配置相对简单，使用起来灵活便捷，花费相对低廉等优点，可以满足一般情况下的负载均衡需求。但是该方案缺点也比较多，一方面服务器安装的三方软件在运行的时候也会消耗系统一定量的资源，而且越是功能复杂的模块，消耗的量越多，另一方面当并发连接请求数非常高时，这个软件反而可能会成为服务器工作的一个负担[1-2]。

（2）硬件负载均衡

硬件负载均衡的解决方案是直接把负载均衡设备（通常称之为负载均衡器）安装在服务器和外部网络之间，用特定的设备完成特定的任务，使得系统整体性能得到极大提升，可达到最佳的负载均衡需求。虽然该方案相对于软件方式，功能和性能都更强大，但是花费也相对较大，而且因为使用的单个负载均衡器，一旦出现问题将导致整个系统瘫痪。

1.2 根据地理结构进行分类

（1）本地负载均衡

本地负载均衡指的是对本地的服务器集群做负载均衡，它不需花费昂贵开支去购置高性能的服务器，只需充分利用现有的设备资源，就可有效地避免因服务器单点故障所造成的数据流量损失，它通常用来解决数据流量过大、网络负载过重的问题。即使是再给现有服务器进行扩充，也只需要在集群中简单地增加一个新的服务器即可，现有网络结构不需要去做改变，服务也不需要停止。

（2）全局负载均衡

全局负载均衡指的是对地理位置不同、网络结构不同的服务器集群间做负载均衡。该方案通过在多个区域部署自己的服务器站点，使得用户只需通过一个IP 或者域名就能迅速地访问到距离自己最近的区域服务器站点，从而获得最快的访问速度。同时这种方式也能够用于那些拥有多站点广区域子公司的大型公司通过企业内部网达到资源统一合理分配的需求。

2 常用经典负载均衡算法[3-5]

常用的经典负载均衡算法主要分为静态和动态两种。其中静态负载均衡算法不考虑服务器的实际状态，如轮询算法、加权轮询算法等，它以特定的概率去进行任务调度；动态负载均衡算法将服务器的实时负载状态信息考虑在算法之中，如最小连接法、加权最小连接法等，以此来动态决定任务调度。

2.1 静态负载均衡

（1）轮询法

轮询法就是将任务请求按照固定的顺序从头到尾的循环分配给节点服务器，如图1 所示（圆圈内为任务序号），这种算法是严格按照节点服务器的序号进行分配的，大致流程是第一个请求发送到服务器1，下一个请求发送到服务器2，第三个请求发送到服务器3，后续请求重新从服务器1 开始继续按照这种方式分发。

这种算法比较简单，但并不一定合适的，因为一方面实际情况中可能出现节点服务器配置并不是完全一致的，所以可能出现某个处理能力较弱节点服务器过载的情况；另一方面每个用户请求给节点服务器带来的状态变化可能是不同的，即使集群服务器处理能力相同，也可能因为某个节点因为分配过多重任务而出现过载的情况。所以该算法比较适合于集群服务器处理能力相当且各个业务请求带来的负载差距不大的情况。

（2）加权轮询法

加权轮询法是针对轮询法的缺点进行优化后的一种算法，顾名思义它是先给每个节点服务器增加一个权值，服务器的处理能力越强该服务器的权值越大反之则越小。进行任务分配的时候就根据权值去轮询分配不同数量的任务给节点服务器。如图2 所示（圆圈内为任务序号），该网络中节点服务器的权重比为1:2:1，在分配任务时首先将请求发送到服务器1 上，第二个请求发送到服务器2 上，第三个请求因为服务器2 权重较高所以发送到服务器2 上，第四个请求发送到服务器3 上，后续请求依照这种方式继续从服务器1 上开始分配。

图2 加权轮询法

根据加权轮询法的分配流程可知，该算法考虑到了节点服务器处理能力可能不同的问题，并且给处理能力较高的节点服务器分配了更多的业务请求，一定程度上避免了业务堆积造成的过载问题。但是这种算法并未考虑到业务请求本身给服务器带来的负载差距较大时带来的问题，而且如何更加合理地选择权值的配比也是一个问题。

2.2 动态负载均衡

分析静态负载均衡算法可知，因其自身的考虑上的缺陷，依旧可能出现集群负载不均衡的问题。动态负载均衡正是为解决这些问题而出现的。

（1）最小连接法

最小连接法是将任务分配给集群中当前时刻具有最小连接数的节点服务器。当一个节点服务器收到一个任务请求后就将当前连接数加一，当节点服务器出现故障时就将该节点的权值设为0，不再分配任务给该节点服务器。如图3 所示（圆圈内数字为任务序号），节点服务器上数字为当前节点的连接数，此时三个节点服务器的连接数分别为300,235 和260。此时任务26 来时发现最小连接数为235，对应节点服务器2，就将该任务分配给给该服务器。

图3 最小连接法

分析可知，此方法会出现类似轮询法中的一个问题，即当服务器处理能力差距非常大的时候，负载分配的效果就比较差。主要是因为此时单纯的连接数已经无法准确表明服务器的处理能力了，例如可能出现自身处理能力很差的服务器虽然连接数小，但是本身已经无法再处理任务了，而自身处理能力极好的服务器虽然连接数大，但是依旧能够继续处理任务。在这个时候任务就会被被分配到前者，从而导致该服务器出现过载的情况。所以说该方法更适用于各个服务器处理能力相近时。

（2）加权最小连接法

加权最小连接法是针对最小连接法无法较好的解决处理能力差距较大的节点服务器之间的负载均衡问题而提出的。该算法将节点服务器的处理能力用权值表示，在进行任务调度时让节点的连接数和其权值尽可能成比例。如图4 所示（圆圈内数字为任务序号），该架构下节点服务器处理能的权重比为1:2:1，当前连接数分别为100,150,110。根据该算法最近两个任务都发送到了处理能力较高的服务器2 上。

图4 加权最小连接法

分析可知该算法考虑到了各台服务器的状态和处理能力，能比较好地进行任务的调度。不过它和静态负载均衡中的加权轮询法类似，都使用权值代表了服务器的处理能力，所以也会带来另一个问题，即如何合理的设置这个权值，如果只凭经验去选取往往会带来较大的误差。

3 改进的负载均衡算法

通过对常用的动静态负载均衡算法的介绍和分析可知，动态负载均衡算法因为将服务器的处理能力和当前负载状况纳入计算中，所以实际效果更好。然而连接数并不能完全表征当前服务器的剩余处理能力，另外因为业务请求有多种类型，不同类型给节点服务器带来的负载也可能出现较大差距。最后随着并发请求数的增加，负载均衡调度器自身也可能成为任务调度的瓶颈。

为了解决前面所提到的一些问题，研究出新的或者改进的负载均衡算法已经成为了一个热点。本文接下来将对一些新提出的改进的负载均衡算法进行简单介绍和分析。

3.1 基于动态反馈的负载均衡算法

文献[6]中提出了一种基于动态反馈的负载均衡算法，算法是针对一般负载均衡算法无法适用于I/O 密集型任务的存储系统，不能动态实时地反应系统、网络的状态的问题所提出的。该算法考虑了每个连接的实时负载和响应能力，首先确定了四个影响系统负载均衡的因素：CPU 利用率、内存利用率、命令响应时间、命令队列长度。并对各个连接中的这些参数进行周期性地采集。并计算出实时的反馈值，结合历史反馈值对系统中任务进行分配以达到动态调整系统负载的功能。从测试结果上看，该算法的均衡效果要好于经典算法。不过该算法也有其局限性，即其主要针对的是I/O密集型任务系统，当I/O 任务较少时，计算反馈值的过程反倒会变成相对耗时的部分。

3.2 基于遗传算法的动态负载均衡算法

文献[7]中提出了一种基于遗传算法（GA）的网络GIS 集群服务器动态负载均衡算法，该算法同时考虑了基于服务器状态和基于内容的负载均衡算法，还能够灵活调整针对这两方面的权重。该系统集群由负载均衡器和应用服务器组成，其中负载均衡器使用滑动窗口技术，一次处理落在窗口中的任务组，同时窗口大小又正好和遗传算法中个体的基因数相等。另外针对满串窗口和未满窗口的情况采用不同的处理方案，其中满窗口使用遗传算法发送到应用服务器，未满窗口使用轮询的方式发送到应用服务器。

针对GA 无法处理问题空间参数的情况，将问题解的参数进行二维编码，分别表示系统中的应用服务器信息和每个处理器上待分配的若干个任务。仿真实验表明，该算法总能最快地返回用户请求的数据，因为它同时考虑了缓存利用率和服务器状态。不过该算法在未满窗口时依旧使用的轮询方式，所以当这种情况持续较长时间时，也会出现轮询方式所带来的一些问题。

3.3 基于神经网络反馈机制的负载均衡算法

文献[8]中提出了一种基于神经网络反馈机制的改进型的加权最小连接数算法。该算法使用了BP 神经网络来进行反馈控制。在集群中，由于各个节点服务器具有不同的处理能力，因此其所能承受的负载也是不一样的，在处理过程中，每台节点服务器的处理能力和任务分配情况会出现一定的偏差，这时就可以利用BP 神经网络反馈机制来修正权值和阈值。

该算法在一定的时间内收集节点服务器的CPU利用率和网络使用率，将其作为参数值，然后利用这些参数值去与初始化的阈值进行比较，从而得到节点的负载比率R（Si）（服务器节点的处理能力极值与实时负载比值之比），而服务器节点负载的分配结果取决于负载比率。实验结果表明，该算法能够较好地反映服务器的负载情况，从而能够更有效地应对大量用户请求，并降低响应时间。但是该算法在计算负载比率时存在一定波动，而负载比率又是影响计算流程的一个重要参数，因此需要稳定下来。

4 结语

负载均衡算法作为集群系统中的一个重要部分，影响着一个集群系统的正常运行。通过对传统和改进的负载均衡算法的分析可知，如何用实时且适当的方式反映节点服务器的CPU 利用情况、当前网络状况、I/O 情况、内存利用情况以及请求负载情况等是研究的主要方向，除此之外如何在处理过程中不增加较多额外的开销，也是我们需要去考虑的问题。