公平性好的Web服务器集群系统轮询调度负载均衡方法

摘要

本发明公开了一种公平性好的Web服务器集群系统轮询调度负载均衡方法。本发明每个轮次中都由服务器调度模块按活动服务器中的最小剩余权值为每一个服务器分配负载，由于最小剩余权值不是固定不变的，每个轮次开始前都要重新选取最小剩余权值，这样具有较好的公平性，可以实现更有效的负载均衡。本发明在保持轮询类调度方法实现简单的基础上，提高了Web服务器集群系统的公平性，特别是避免了权值低的服务器可能长时间得不到应用的情形，具有复杂度低、效率高、容易实现的优点。

说明书

技术领域

本发明属于集群服务器技术领域，具体来说涉及一种公平性好的Web服务器集群系统轮询调度负载均衡方法。

背景技术

随着网络技术的发展和计算机的普及，网络的规模不断扩大，大量的应用都在围绕着网络进行，促进了Internet用户数和流量的快速增长。同时，随着网络硬件设备的飞速进步，网络带宽的瓶颈效应日趋减弱，Web服务器的性能问题逐渐显现出来，由于单一的服务器系统处理客户请求的能力有限，当并发访问的人数越来越多时，就会造成Web服务器的负荷加重甚至崩溃，可见如何解决服务器的高负荷问题、处理快速增长的客户请求已经是无法回避的问题，Web服务的高性能、高可用问题已经成为Web服务领域研究的热点。从目前的研究方向看，服务器方向的研究可以归结为两个方面：通过单纯提升处理器等服务器硬件性能来提高服务器的负载能力是比较直接的解决方法，这是从实现机制上入手，主要研究Caching技术、预取技术等，另外对客户访问行为进行分析，研究可以缩小响应时间的方法，这些技术可以在现有服务器设备的基础上尽可能地提高系统的性能，但性能提高的程度有限，同时也会带来比较大的开销，包括昂贵的服务器硬件，无法保护已有的投资等方面，对于中小型企业来说是一个不小的负担。另一种解决方法是集群思想，这是从体系结构入手，将过去单一的服务器结构扩充为集群式服务器结构，使用多台服务器组成集群系统提供服务，通过一定机制使他们共同分担系统负载，这种结构对单一的服务器没有太高的性能要求，但可以显著提高服务器的总体性能。对用户而言，整个系统仿佛是一台单一的逻辑服务器，这样的系统能够提供较强的可扩展性、较好的吞吐性能和高可靠性。

    相比之下，Web服务器集群系统是解决当前Web服务性能问题的有效途径，它将用户的请求按照负载均衡策略分发到集群中的某台服务器上去，通过服务器之间的协同工作并行处理用户的请求，从而提高系统运行效率，提高整个系统的性能。不过，异构服务器集群系统比同构服务器集群系统更有实际意义，但实现起来困难要大得多。为实现一个高效的异构Web服务器集群系统，必须解决许多问题，负载均衡就是其中的关键问题之一，其他方面还包括请求分配、容错技术等。对于异构Web服务器集群系统，各台Web服务器性能不同，各种负载均衡方法将导致系统中各台Web服务器对外表现不同，同时，也实际上决定了Web服务器集群系统性能的高低，当Web服务器集群系统中各台Web服务器的负载处于均衡状态时，请求分配的效率是最高的。因此，可以通过负载均衡方法来控制负载的分布，使Web服务器集群系统的负载分配尽量达到均衡，提高请求分配的效率，使服务器资源得到充分利用，为用户提供更好的Web服务。

    对于如何实现Web服务器集群系统的负载均衡，目前己经提出了许多的算法和方法，轮询（Round-Robin）类调度方法就是其中最基本的方法之一。最简单的轮询调度方法就是分配器（Dispatcher）以轮询的方式依次选择Web集群系统中的服务器，将Web请求或网络连接分配给所选择的服务器进行处理。分配器对每个服务器都是平等对待，不考虑服务器的处理能力。另一种轮询调度方法称为加权的轮询（Weighted Round-Robin）调度方法，根据各台实际服务器的处理能力给它们分配不同的权重，用相应的权值表示服务器的处理性能，然后分配器根据服务器的权值来给服务器分配连接，权值高的服务器先收到连接，比权值低的服务器处理更多的连接，服务器处理的连接数与服务器的权值成正比。

    轮询类调度方法的优势在于实现起来很简单，但是也存在明显的不足：简单的轮询调度方法不考虑服务器的处理能力，显然不适用于Web服务器集群系统中服务器处理性能不一致的情况。加权的轮询调度方法考虑了服务器性能的不同，提高了调度的有效性，但存在公平性问题，有可能有的服务器负荷很重，而其他的服务器却是空闲的，从而导致服务器之间的负载并不均衡。因此，对于轮询类调度方法，除了要保持其实现简单的优点之外，还需要有相应的机制来保证它们的公平性，确保Web服务器之间的负载均衡。

发明内容

为了解决现有Web服务器集群系统的负载均衡存在的上述技术问题，本发明提供的一种公平性好的轮询调度负载均衡方法。采用本发明所提供的方法，在保持轮询类调度方法实现简单的基础上，提高了Web服务器集群系统的公平性，特别是避免了权值低的服务器可能长时间得不到应用的情形。

　　本发明解决上述技术问题的技术方案包括以下步骤：

（1）当Web请求服务队列为空时，即没有用户访问Web服务器集群系统，则服务器调度模块进入等待Web请求到达的状态；否则，继续；

（2）将活动服务器列表中每个服务器的Web请求计数器置为0；

（3）将活动服务器列表中服务器的个数置于访问服务器计数器；

（4）计算出活动服务器列表每个服务器的剩余权值，取其中的最小权值为W_min；

（5）选择活动服务器列表中的第一个服务器，从Web请求服务队列中分配一个Web请求给该服务器进行处理；服务器的Web请求计数器加1，剩余权值减少1；

（6）判断Web请求服务队列是否为空，如果是，执行步骤（1）；否则，继续；

（7）判断服务器的剩余权值是否为0，如果是，将服务器从活动服务器列表中删除，执行步骤（11）；否则，继续；

（8）判断Web请求计数器是否小于最小权值W_min，如果是，继续；否则，执行步骤（10）；

（9）继续从Web请求服务队列中分配一个Web请求给该服务器进行处理，服务器的Web请求计数器加1，剩余权值减少1；执行步骤（6）；

（10）将所选择的服务器移到活动服务器列表的尾部；

（11）访问服务器计数器减1；

（12）判断访问服务器计数器是否为0，如果是，继续；否则，执行步骤（5）；

（13）执行步骤（2）。

 

本发明的技术效果在于：本发明中每个轮次中都按活动服务器中的最小剩余权值为每一个服务器分配负载，从而具有较好的公平性，可以实现更有效的负载均衡。另外，最小剩余权值不是固定不变的，每个轮次开始前都要重新选取最小剩余权值，因此本发明是一种动态权值的轮询调度负载均衡方法，具有复杂度低、效率高、容易实现的优点。

下面结合附图和具体实施例对本发明作进一步的说明。

 

附图说明

图1本发明中Web请求、Web请求服务队列、服务器调度模块、服务器之间的关系示意图。

图2本发明实施例中，第1轮次的服务器调度情形示意图，左边部分是本轮次中分配给服务器处理的Web请求，右边部分是经过本轮次调度后，服务器的剩余权值。

图3本发明实施例中，第2轮次的服务器调度情形示意图。

图4本发明实施例中，第3轮次的服务器调度情形示意图。

图5本发明实施例中，第4轮次的服务器调度情形示意图。

图6本发明实施例中，经过4个轮次后，四个服务器所处理的Web请求以及剩余权值的示意图。

图7服务器调度过程流程图。

具体实施方式

本发明所提供的一种公平性好的Web服务器集群系统轮询调度负载均衡方法，其特征是它包括初始化过程、Web请求排队过程和服务器调度过程。初始化过程包括根据每个服务器的性能给定其一个权值；当有Web请求时，对服务器调度模块进行初始化。Web请求排队过程是指当一个新的访问请求到达时，进入到队列中排队，等候分配服务器对其进行处理。服务器调度过程描述的是怎样从Web服务器集群系统中选择一个服务器，然后将队列中的Web请求分配给所选取的服务器进行处理。

 

所述的轮询调度负载均衡方法，给Web服务器集群系统中每一个服务器分配一个权值（Weight），表示服务器的处理性能。当一个服务器的权值（即服务器的处理能力）没有用完时，即剩余的权值大于0，称服务器是活动的（Active）。将集群系统中所有活动的服务器放到一个列表中，称为“活动服务器列表”。当一个服务器的权值用完时，即剩余的权值已等于0，则服务器由活动的变成非活动的（Inactive），这时将该服务器从“活动服务器列表”中删除。如果一个服务器由非活动的变成活动的，则将该服务器加入到“活动服务器列表”的尾部。

所述的轮询调度负载均衡方法，将发往Web服务器集群系统的Web请求放在一个列队中，这个队列称为“Web请求服务队列”，调度模块将按先来先服务原则从队列中提取Web请求。

所述的轮询调度负载均衡方法，定义一个轮次（Round）是某一时刻T1（T1>0），“活动服务器列表”中所包含的服务器被服务器调度模块访问的过程。在本轮次执行过程中，重新成为活动的服务器可以加入到“活动服务器列表”的尾部，但将从下一轮次开始被访问。在一个轮次中，被访问服务器能够接受的Web请求负荷不超过本轮次中所有服务器剩余权值的最小值。

所述的轮询调度负载均衡方法，为了表示一个轮次中所需要访问的服务器的数目，引入一个计数器记录服务器的数目，这个计数器称为“访问服务器计数器”，表示在一个轮次开始时“活动服务器列表”中服务器的数量。每当服务器调度模块访问一个服务器，“访问服务器计数器”就减少1，当“访问服务器计数器”最终等于0时，就说明这个轮次结束。

所述的轮询调度负载均衡方法，用一个计数器记录一个服务器在一个轮次中总共接收的Web请求数，这个计数器称为“Web请求计数器”，每个服务器都有一个“Web请求计数器”。在一个轮次开始前，“Web请求计数器”的初值为0，然后每接收一个Web请求，就将 “Web请求计数器”加1。

       本发明所提供的Web服务器集群系统轮询调度负载均衡方法中，Web请求、Web请求服务队列、服务器调度模块、服务器之间的关系如图1所示。当一个Web请求1到达服务器集群系统时，首先进入到Web请求服务队列2中排队，等候处理。服务器调度模块3使用本发明的轮询调度负载均衡方法4来调度服务器，在n（n为大于0的自然数）个服务器5中选择一个服务器，对Web请求服务队列2中的Web请求进行处理，使服务器5的资源得到公平分配，实现高效的负载均衡。

为了表述更直观，用ActiveServerList表示“活动服务器列表”，是所有活动的服务器的列表。当一个服务器由活动的变成非活动的时，该服务器将从ActiveServerList中移走。当一个服务器由非活动的变成活动的时，该服务器将加入到ActiveServerList的尾部。

一个轮次中服务器的确定：现考虑轮次1的开始时间是T1，结束时间是T2（T2>T1）。在T1时刻，ActiveServerList中包含服务器-1、服务器-2、服务器-3等三个服务器，那么在轮次1，服务器调度模块将访问上述的三个服务器。在T1、T2之间，服务器-4变成活动的并加入到了ActiveServerList，但服务器调度模块不会在轮次1访问服务器-4，因为服务器-4在轮次1开始时刻T1不在ActiveServerList中。定义轮次2在T2时刻开始，在轮次2中，服务器调度模块将访问T2时刻ActiveServerList中的服务器，即访问服务器-1、服务器-2、服务器-3、服务器-4。另外，第几轮次是相对于某个服务器来讲的，如从T2开始的轮次，对于服务器-1、服务器-2、服务器-3来说，是第2轮次，但对于服务器-4来说，是第1轮次。

为了表述更直观，用VisitServerCount表示“访问服务器计数器”，是在一个轮次开始时ActiveServerList列表中服务器的数量。每当服务器调度模块完成对一个服务器的访问，VisitServerCount就减少1，当VisitServerCount最终等于0时，就说明这个轮次结束。

为了表述更直观，用RequestCount表示“Web请求计数器”，是一个服务器在一个轮次中所接收的Web请求数。用RequestCount_i表示服务器-i（1≤i≤n，i为自然数）的“Web请求计数器”；用RequestCount _i（r）表示在第r轮次中服务器-i所接收的Web请求数。

为了表述更直观，用UnusedW表示服务器的剩余权值，是一个服务器由于处理Web请求而剩余的处理能力，当服务器空闲时，它的剩余权值就是它的权值，即它的全部处理能力。用UnusedW _i表示服务器-i（1≤i≤n，i为自然数）还没有被使用的处理能力，即服务器-i的剩余权值。

 

下面结合实施例来说明本发明所提供的轮询调度负载均衡方法，实施例中有四个服务器：服务器-1、服务器-2、服务器-3、服务器-4；有20个Web请求需要Web服务器集群系统进行处理，分用R1、R2、R3、R4、R5、R6、R7、R8、R9、R10、R11、R12、R13、R14、R15、R16、R17、R18、R19、R20表示，其中R1最先到达，R20最后到达。

 

一、初始化过程

这是服务器调度模块进行初始化的过程，包括以下一些操作：

根据服务器的性能为每个服务器分配一个权值，服务器-i的权值用W_i（1≤i≤n，i为自然数）表示，本实施例中n=4，四个服务器的权值分别为W₁=10、W₂=7、W₃=3、W₄=2（本实施例中是以Web请求数作为权值和负载的衡量单位，如果权值、负载大小是以其他的度量值来衡量，本发明同样适用，亦属于本发明所涵盖范围之内）。由于四个服务器的权值都大于0，所以四个服务器都是活动的，于是，四个服务器都加入到ActiveServerList中，得到ActiveServerList={服务器-1，服务器-2，服务器-3，服务器-4}。

VisitServerCount的初值赋值为0。

RequestCount_i的初值赋值为0，1≤i≤n，本实施例中n=4； 

二、Web请求排队过程

本实施例中，有R1、R2、R3、R4、R5、R6、R7、R8、R9、R10、R11、R12、R13、R14、R15、R16、R17、R18、R19、R20等20个Web请求进入到了“Web请求服务队列”中，正在等候分配服务器对它们进行处理。

 

三、服务器调度过程

服务器调度模块开始对ActiveServerList中的服务器进行访问，选择一个服务器对“Web请求服务队列”中的Web请求进行处理。

开始时，首先判断“Web请求服务队列”是否为空，本实施例中，“Web请求服务队列”中有20个Web请求，非空。这时，ActiveServerList={服务器-1，服务器-2，服务器-3，服务器-4}，将ActiveServerList中每个服务器的RequstCount置为0，即RequestCount_i=0，1≤i≤4。VisitServerCount=ActiveServerList中服务器的个数=4，进入四个服务器的第1轮次：

四个服务器的剩余权值分别为：UnusedW₁=10、UnusedW₂=7、UnusedW₃=3、UnusedW₄=2，其中的最小权值W_min=2。

因为服务器-1是ActiveServerList中的第一个服务器，所以选择服务器-1对“Web请求服务队列”中的第一个Web请求R1进行处理。RequstCount₁=0+1=1，UnusedW₁=10-1=9。因为UnusedW₁>0, RequstCount₁<W_min，所以继续从“Web服务请求队列”中分配Web请求R2由服务器-1处理，这时，RequstCount₁=1+1=2，UnusedW₁=9-1=8。由于UnusedW₁>0, RequstCount₁=W_min，于是将服务器-1移到ActiveServerList的尾部，ActiveServerList={服务器-2，服务器-3，服务器-4，服务器-1}。VisitServerCount=4-1=3。

继续选择ActiveServerList中的第一个服务器即服务器-2，对“Web服务请求队列”中的Web请求R3进行处理，有RequstCount₂=0+1=1，UnusedW₂=7-1=6。因为UnusedW₂>0, RequstCount₂<W_min，所以继续从“Web服务请求队列”中分配Web请求R4由服务器-2处理，这时，RequstCount₂=1+1=2，UnusedW₂=6-1=5。由于UnusedW₂>0, RequstCount₂=W_min，于是将服务器-2移到ActiveServerList的尾部，ActiveServerList={服务器-3，服务器-4，服务器-1，服务器-2}。VisitServerCount=3-1=2。

继续选择ActiveServerList中的服务器-3，对“Web服务请求队列”中的Web请求R5进行处理，有RequstCount₃=0+1=1，UnusedW₃=3-1=2。因为UnusedW₃>0, RequstCount₃<W_min，所以继续从“Web服务请求队列”中分配Web请求R6由服务器-3处理，这时，RequstCount₃=1+1=2，UnusedW₃=2-1=1。由于UnusedW₃>0, RequstCount₃=W_min，于是将服务器-3移到ActiveServerList的尾部，ActiveServerList={服务器-4，服务器-1，服务器-2，服务器-3}。VisitServerCount=2-1=1。

继续选择ActiveServerList中的服务器-4，对“Web服务请求队列”中的Web请求R7进行处理，有RequstCount₄=0+1=1，UnusedW₄=2-1=1。因为UnusedW₄>0, RequstCount₄<W_min，所以继续从“Web服务请求队列”中分配Web请求R8由服务器-4处理，这时，RequstCount₄=1+1=2，UnusedW₄=1-1=0。由于UnusedW₄=0,于是将服务器-4从ActiveServerList中删除，ActiveServerList={服务器-1，服务器-2，服务器-3}。VisitServerCount=1-1=0。

VisitServerCount=0说明轮次1已经结束，第1轮次的服务器调度情形如图2所示。

 

下面进入第2轮次：

ActiveServerList={服务器-1，服务器-2，服务器-3}，将ActiveServerList中每个服务器的RequstCount置为0，即RequestCount_i=0，1≤i≤3。VisitServerCount=ActiveServerList中服务器的个数=3，三个服务器的剩余权值分别为：UnusedW₁=8、UnusedW₂=5、UnusedW₃=1，其中的最小权值W_min=1。

因为服务器-1是ActiveServerList中的第一个服务器，所以选择服务器-1对“Web请求服务队列”中的Web请求R9进行处理。RequstCount₁=0+1=1，UnusedW₁=8-1=7。因为UnusedW₁>0, RequstCount₁=W_min，于是将服务器-1移到ActiveServerList的尾部，ActiveServerList={服务器-2，服务器-3，服务器-1}。VisitServerCount=3-1=2。

继续选择ActiveServerList中的第一个服务器即服务器-2，对“Web服务请求队列”中的Web请求R10进行处理，有RequstCount₂=0+1=1，UnusedW₂=5-1=4。因为UnusedW₂>0, RequstCount₂=W_min，于是将服务器-2移到ActiveServerList的尾部，ActiveServerList={服务器-3，服务器-1，服务器-2}。VisitServerCount=2-1=1。

继续选择ActiveServerList中的服务器-3，对“Web服务请求队列”中的Web请求R11进行处理，有RequstCount₃=0+1=1，UnusedW₃=1-1=0。由于UnusedW₃=0,于是将服务器-3从ActiveServerList中删除，ActiveServerList={服务器-1，服务器-2}。VisitServerCount=1-1=0。

VisitServerCount=0说明轮次2已经结束，第2轮次的服务器调度情形如图3所示。

 

下面进入第3轮次：

ActiveServerList={服务器-1，服务器-2}，将ActiveServerList中每个服务器的RequstCount置为0，即RequestCount_i=0，1≤i≤2。VisitServerCount=ActiveServerList中服务器的个数=2，两个服务器的剩余权值分别为：UnusedW₁=7、UnusedW₂=4，其中的最小权值W_min=4。

因为服务器-1是ActiveServerList中的第一个服务器，所以选择服务器-1对“Web请求服务队列”中的Web请求R12进行处理。RequstCount₁=0+1=1，UnusedW₁=7-1=6。因为UnusedW₁>0, RequstCount₁<W_min，所以继续从“Web服务请求队列”中分配Web请求R13由服务器-1处理，这时，RequstCount₁=1+1=2，UnusedW₁=6-1=5。因为UnusedW₁>0, RequstCount₁<W_min，所以继续从“Web服务请求队列”中分配Web请求R14由服务器-1处理，这时，RequstCount₁=2+1=3，UnusedW₁=5-1=4。因为UnusedW₁>0, RequstCount₁<W_min，所以继续从“Web服务请求队列”中分配Web请求R15由服务器-1处理，这时，RequstCount₁=3+1=4，UnusedW₁=4-1=3。由于UnusedW₁>0, RequstCount₁=W_min，于是将服务器-1移到ActiveServerList的尾部，ActiveServerList={服务器-2，服务器-1}。VisitServerCount=2-1=1。

继续选择ActiveServerList中的第一个服务器即服务器-2，对“Web服务请求队列”中的Web请求R16进行处理，有RequstCount₂=0+1=1，UnusedW₂=4-1=3。因为UnusedW₂>0, RequstCount₂<W_min，所以继续从“Web服务请求队列”中分配Web请求R17由服务器-2处理，这时，RequstCount₂=1+1=2，UnusedW₂=3-1=2。因为UnusedW₂>0, RequstCount₂<W_min，所以继续从“Web服务请求队列”中分配Web请求R18由服务器-2处理，这时，RequstCount₂=2+1=3，UnusedW₂=2-1=1。因为UnusedW₂>0, RequstCount₂<W_min，所以继续从“Web服务请求队列”中分配Web请求R19由服务器-2处理，这时，RequstCount₂=3+1=4，UnusedW₂=1-1=0。由于UnusedW₂=0，于是将服务器-2从ActiveServerList中删除，ActiveServerList={服务器-1}。VisitServerCount=1-1=0。

VisitServerCount=0说明轮次3已经结束，第3轮次的服务器调度情形如图4所示。

 

下面进入第4轮次：

ActiveServerList={服务器-1}，将ActiveServerList中每个服务器的RequstCount置为0，即RequestCount₁=0。VisitServerCount=ActiveServerList中服务器的个数=1，服务器-1的剩余权值为：UnusedW₁=3，最小权值W_min=3。

由服务器-1对“Web请求服务队列”中的Web请求R20进行处理。RequstCount₁=0+1=1，UnusedW₁=3-1=2。由于“Web请求服务队列”已经为空，说明已没有Web请求需要处理，于是，服务器调度模块进入到等待Web请求到达的状态。第4轮次的服务器调度情形如图5所示。

 

如上所述的实施例所实现的Web服务器集群系统调度过程，只是描述了在给定实施例的情况下，执行本发明所述的轮询调度负载均方法的开始的4个轮次，经过4个轮次后，四个服务器所处理Web请求以及剩余的权值如图6所示。本发明所述的服务器轮询调度负载均衡方法，对Web请求数量、服务器数量、轮次的多少是没有限制的，一旦有Web请求到达，服务器调度模块还将继续往下执行服务器调度，对Web请求进行处理。服务器调度过程的流程如图7所示。

 

以上实施例说明的就是本发明所提供的一种Web服务器集群系统轮询调度负载均衡方法的具体实施方式。本发明所提供的Web服务器负载均衡调度技术具有以下优点：（1）每个轮次都以活动服务器中的最小剩余权值来为服务器分配Web请求，相对于传统的加权轮询调度方法，具有更好的公平性，避免了有的服务器负载很重，而其他服务器有可能空闲的情形。如本发明中的实施例，如果按传统的轮询调度方法来调度服务器，结果是服务器-1、服务器-2和服务器-3都是满负荷运行，而服务器-4却是空闲的。因此，使用本发明所提供的负载均衡方法可以充分利用集群系统中每个服务器的资源，只要一个服务器在一个轮次中是活动的，至少都有一个Web请求分配给它进行处理，这样就避免了服务器长时间得不到使用的情况，因而具有更好的负载均衡效果。

（2）本发明所提供的是一种动态权值的轮询调度方法，每个轮次中所使用的最小权值不是固定不变的，而是根据服务器的负载情况而确定，当活动服务器的剩余权值都比较高时，就会给每个服务器分配更多Web请求，提高了调度的灵活性。

（3）在负载均衡方法的Web请求排队过程、服务器添加到ActiveServerList中、给变量赋初值等操作，都可以在O(1)的时间复杂度中完成。在服务器调度过程中，包括了从ActiveServerList的首部移出一个服务器、在ActiveServerList的尾部添加一个服务器、更新变量（VisitServerCount、RequesCount_i、UnusedW_i）的值等操作，这些操作都可以在常数时间内完成。因此，本发明所提供的Web服务器集群系统轮询调度负载均衡方法，保持了轮询类调度方法的优点，复杂度低、效率高、容易实现。