一种实现加权最小连接分配的服务器负载均衡方法

1.一种实现加权最小连接数调度的服务器负载均衡方法，在新服务请求接入 时，包括如下步骤：
预先确定表示服务器组中各服务器的当前连接信息的状态，所述状 态由包括至少一个数据项的数据结构表示，所述数据项包括表示所述各 服务器的当前服务的负载状况的数据项，所述当前服务的负载状况由所 述至少一个数据项中的首数项近似地表示；
遍历所述各服务器的所述近似地表示当前服务的负载状况的所述状 态中的首数项；
比较所述首数项，
如果存在最小的首数项，选择该最小的首数项对应的服务 器接入；
如果不存在最小的首数项，选择任一服务器接入；
修改表示所述选择的服务器当前连接信息的状态的至少一个数 据项。
2.如权利要求1所述的实现加权最小连接数调度的服务器负载均衡方法， 其特征在于所述预先确定表示所述各服务器的当前连接信息的状态的步骤 还包括确定表示所述当前连接信息的尾数项的步骤，其中，所述尾数项表 示所述首数项表示的当前服务的负载状况的近似程度。
3.如权利要求2所述的实现加权最小连接数调度的服务器负载均衡方法， 其特征在于所述的方法还包括预先确定所述服务器组中各服务器的加权值 的步骤。
4.如权利要求3所述的实现加权最小连接数调度的服务器负载均衡方法，其 特征在于：所述修改表示所述选择的服务器当前连接信息的状态的至少一 个数据项的步骤包括：
将所述的尾数项增加一个小于所述加权值的步长；
比较所述的尾数项是否大于或等于所述的加权值，
如果所述的尾数项大于或等于所述的加权值，
将所述的首数项增加1，
将所述的尾数项减去所述的加权值；
以及
所述方法还包括所述的接入服务器断开一个连接时修改表示所述选择的 服务器当前连接信息的状态的至少一个数据项的步骤：
比较所述的尾数项是否小于所述的步长，
如果所述的尾数项不小于所述的步长，
将所述的尾数项减去所述的步长；
如果所述的尾数项小于所述的步长，
比较所述的首数项是否大于0，
如果所述的首数项不大于0，
返回出错信息，结束处理；
如果所述的首数项大于0，
将所述的首数项减去1，
将所述的尾数项增加一个所述的加权值，然后再减去 所述的步长。
5.如权利要求3所述的实现加权最小连接数调度的服务器负载均衡方法， 其特征在于所述预先确定表示所述各服务器的当前连接信息的状态的步骤 还包括确定表示所述当前连接信息的当前连接数项的步骤，其中，所述当 前连接数项精确表示所述当前服务的总数量；所述的修改表示所述选择的 服务器当前连接信息的状态的至少一个数据项的步骤包括：
将所述的当前连接数项增加一个小于所述的加权值的步长；
将所述的尾数项增加一个所述的步长；
比较所述的尾数项是否大于或等于所述的加权值，
如果所述的尾数项大于或等于所述的加权值，
将所述的首数项增加1，
将所述的尾数项减去所述的加权值；
以及
当所述的接入服务器断开一个连接时，还包括如下步骤：
将所述的当前连接数项减去一个所述的步长；
比较所述的尾数项是否小于所述的步长，
如果所述的尾数项不小于所述的步长，
将所述的尾数项减去所述的步长；
如果所述的尾数项小于所述的步长，
比较所述的首数项是否大于0，
如果所述的首数项不大于0，
返回出错信息，结束处理；
如果所述的首数项大于0，
将所述的首数项减去1，
将所述的尾数项增加一个所述的加权值，然后 再减去所述的步长。
6.如权利要求3所述的实现加权最小连接数调度的服务器负载均衡方法，其 特征在于所述确定所述各服务器的加权值的步骤包括步骤：
根据所述各服务器的性能，确定所述各服务器的原始加权值；
根据下式计算所述各服务器的加权值；
加权值＝INT(原始加权值/精度因子)，
其中，加权值表示负载调度运算时所使用的加权值，INT表示取整运 算，原始加权值为上述各服务器的原始加权值，精度因子根据不大于所述各 服务器的最大原始加权值，同时使所述原始加权值计算后得到的余数尽量 小，使所述的负载调度运算时所使用的加权值数值较小的原则选定。
7.如权利要求1所述的实现加权最小连接数调度的服务器负载均衡方法， 其特征在于所述方法还包括预先确定服务器组中各服务器遍历顺序的步 骤，所述的遍历所述首数项的步骤还包括随机选取遍历的起始地址，并按 照所述的顺序遍历的步骤。
8.如权利要求1所述的实现加权最小连接数调度的服务器负载均衡方法，其 特征在于所述的比较所述首数项，选择接入服务器的步骤还包括：存在多 个最小的首数项时，选择遍历最先访问到的最小的首数项所对应的服务器 或所述多个最小的首数项中的任一个所对应的服务器接入的步骤。
9.如权利要求1中所述的实现加权最小连接数调度的服务器负载均衡方法， 其特征在于所述方法在定点处理器上实现。
10.如权利要求1所述的实现加权最小连接数调度的服务器负载均衡方法， 其特征在于所述预先确定表示所述各服务器的当前连接信息的状态的步骤 包括在系统初始化前确定存储所述各服务器的当前连接信息的状态的数据 结构的步骤，和系统运行过程中所述接入服务器在前一个连接断开或接入 的时候确定所述接入服务器的当前连接信息的状态的步骤。

技术领域
本发明涉及多服务器的负载均衡技术，具体涉及一种实现加权最小连接 分配的服务器负载均衡方法。
背景技术
随着互联网技术的迅速发展，互联网用户急剧增加。同时互联网内容提 供商为满足互联网用户对互联网内容和形式的更高层次的要求，利用各种技 术和手段，尤其是多媒体技术，使网站的视觉效果更易吸引用户。用户访问 数量的增加以及用户单次访问流量的增加对服务器承受并发访问的能力提出 了更高的要求。由于单台服务器的负载能力总是有限的，面对日益增加的用 户访问数量和访问流量，单台服务器的中央处理器(CPU)和输入/输出 (I/O)很快会成为瓶颈。而这个问题不是单纯靠提高服务器硬件的性能就可 以解决的。通常的解决方法是采用由多台服务器构成的服务器组并对服务器 组实施负载均衡技术。在负载均衡技术中，比较关键的技术就是要通过不同 的负载均衡方案根据预定的策略对服务器组中的服务器实施调度。在诸多的 策略调度技术中，加权最小连接数调度方法是最常见的方法。加权最小连接 数调度可以通过根据服务器的性能(通过该服务器的加权值体现)以及当前 的传输控制协议(TCP)连接数，如计算TCP连接数与加权值的比值，选择最 佳的服务器的方法实现。但在定点处理器中，除法运算一般要通过软件方法 用加减指令来实现，其最大的缺点就是速度慢。而网络中大量的报文处理器 是定点处理器，通过定点除法来实现负载均衡计算会导致性能下降很多，所 以在定点处理器上实现加权最小连接的调度方案是十分重要的。
为解决上述问题，目前常见的一种方法是利用后台定时器的定时任务计 算出服务器组中负载最轻的服务器作为被调度的服务器，而前台的调度任务 直接将新的接入请求分配给该服务器进行处理。具体地说，在一个定时器刷 新时间间隔内，定时任务统计服务器组中各服务器的当前TCP连接数，并根 据各服务器的加权值，作定点除法运算，计算出各服务器的TCP连接数与加 权值的比值，然后通过比较运算选取比值最小的服务器即负载最轻的服务 器，作为该服务器组中被调度的服务器。而前台的调度任务直接使用这个计 算结果，即在定时器刷新时间间隔内，该服务器组始终选择该服务器作为被 调度的服务器，处理在该定时器刷新时间间隔内分配到该服务器组的所有新 的接入请求，包括从建立连接到断开连接的所有任务。本方法在每个定时器 刷新时间间隔内只计算一次各服务器的连接状况，而不是在新增或断开每个 连接时都进行计算，因此服务器组的计算结果不能及时刷新。在定时器刷新 时间间隔较大或者用户较多、流量较大的情况下，可能造成一个定时器刷新 时间间隔内某台服务器的负载急剧增加，甚至超过该服务器的负载能力而仍 然被该服务器组用作被调度的服务器，从而导致大量新的接入请求长时间等 待甚至因超时而被丢弃。这个问题虽然可以通过减小定时器刷新时间间隔得 到改善，但由于定点处理器进行除法运算的速度较慢，性能较差，定时器刷 新时间间隔的缩小是有限度的，从而不能从根本上解决问题。
发明内容
本发明的目的是克服现有技术的上述缺点，提供一种改进了的负载均衡 调度方法。利用本发明，能够不进行上述除法运算，并将部分运算分散到均 衡调度前进行，而使负载均衡调度的速度加快，同时负载的分配也较为均 衡。
本发明提供了一种实现加权最小连接数调度的服务器负载均衡方法，包 括以下步骤：
预先确定表示服务器组中各服务器的当前连接信息的状态，所述状 态由包括至少一个数据项的数据结构表示，所述数据项包括表示所述各 服务器的当前服务的负载状况的数据项，所述当前服务的负载状况由所 述至少一个数据项中的首数项近似地表示；
在新服务接入时，
遍历所述各服务器的所述近似地表示当前服务的负载状况的所述状 态中的首数项；
比较所述首数项，
如果存在最小的首数项，选择该最小的首数项对应的服务 器接入；
如果不存在最小的首数项，选择任一服务器接入；
修改表示所述选择的服务器当前连接信息的状态的至少一个数据 项。
优选地，本方法还包括预先确定所述服务器组中各服务器的加权值的步 骤。
可选地，该步骤包括以下步骤：
根据所述各服务器的性能，确定所述各服务器的原始加权值；
根据下式计算所述各服务器的加权值：
加权值＝INT(原始加权值/精度因子)。
其中，加权值表示负载调度运算时所使用的加权值，INT表示取整运 算，原始加权值为上述各服务器的原始加权值，精度因子根据不大于所述各 服务器最大原始加权值，同时使所述原始加权值计算后得到的余数尽量小， 使所述的负载调度运算时所使用的加权值数值较小的原则选定。
优选地，在所述预先确定表示所述各服务器的当前连接信息的状态的步 骤中还包括确定表示所述当前连接信息的尾数项的步骤，其中，所述尾数项 表示所述首数项表示的当前服务的负载状况的近似程度。所述修改表示所述 选择的服务器当前连接信息的状态的至少一个数据项的步骤包括：
将所述的尾数项增加一个小于所述加权值的步长；
比较所述的尾数项是否大于或等于所述的加权值，
如果所述的尾数项大于或等于所述的加权值，
将所述的首数项增加1，
将所述的尾数项减去所述的加权值；
以及
可选地，在所述的接入服务器断开一个连接时修改表示所述选择的服务 器当前连接信息的状态的至少一个数据项的步骤中包括步骤：
比较所述的尾数项是否小于所述的步长，
如果所述的尾数项不小于所述的步长，
将所述的尾数项减去所述的步长；
如果所述的尾数项小于所述的步长，
比较所述的首数项是否大于0，
如果所述的首数项不大于0，
返回出错信息，结束处理；
如果所述的首数项大于0，
将所述的首数项减去1，
将所述的尾数项增加一个所述的加权值，然后再减去 所述的步长。
优选地，本方法包括预先确定服务器组中各服务器遍历顺序的步骤，和 在所述的遍历所述首数项的步骤中还包括随机选取遍历的起始地址并按照所 述的顺序遍历的步骤。
可选地，在所述的比较所述首数项，选择接入服务器的步骤中还包括存 在多个最小的首数项时，选择遍历最先访问到的最小的首数项所对应的服务 器或所述多个最小的首数项中的任一个所对应的服务器接入的步骤。
优选地，所述预先确定表示所述各服务器的当前连接信息的状态的步骤 包括系统初始化前确定存储所述各服务器的当前连接信息的状态的数据结构 的步骤，和系统运行过程中所述接入服务器在前一个连接断开或接入的时候 确定所述接入服务器的当前连接信息的状态的步骤。
可选地，所述预先确定表示所述各服务器的当前连接信息的状态的步骤 还包括确定表示所述当前连接信息的当前连接数项的步骤，其中，所述当前 连接数项精确表示所述当前服务的总数量；所述的确定所述修改表示所述选 择的服务器当前连接信息的状态的至少一个数据项的步骤包括：
将所述的当前连接数项增加一个小于表示所述的加权值的步长；
将所述的尾数项增加一个所述的步长；
比较所述的尾数项是否大于或等于所述的加权值，
如果所述的尾数项大于或等于所述的加权值，
将所述的首数据项增加1，
将所述的尾数项减去所述的加权值；
以及
当所述的接入服务器断开一个连接时，还包括如下步骤：
将所述的当前连接数项减小一个所述的步长；
比较所述的尾数项是否小于所述的步长，
如果所述的尾数项不小于所述的步长，
将所述的尾数项减去所述的步长；
如果所述的尾数项小于所述的步长，
比较所述的首数项是否大于0，
如果所述的首数项不大于0，
返回出错信息，结束处理；
如果所述的首数项大于0，
将所述的首数项减去1，
将所述的尾数项增加一个所述的加权值，然后再减
去所述的步长。
可选地，本发明所述方法在定点处理器上实现。
由以上技术方案可以看出，本发明以空间换取时间，通过增加多个数据 项来记录所述各服务器的当前负载状况，在负载均衡调度时只需要作比较运 算，不必作除法运算，减少了调度的运算量，加快了负载均衡的调度速度， 而且方法简单，均衡度好，容易实现，即使在功能简单的定点处理器上也可 以有较好的调度。对新建立或断开的每个连接，表示所述服务器连接状况的 数据项作相应的改变，从而使表示所述服务器连接状况的数据项能实时地反 映服务器的负载状况，使负载调度的结果更为准确，使负载的分配更加均 衡。遍历起始地址的随机选取也减小了短时间内负载分配不均衡的可能性。 本发明还可以通过精度因子的选取来提高负载均衡调度的精度。
附图说明
图1表示本发明的一个实施例的运行过程的流程图；
图2表示存储服务器组中各服务器当前连接信息的数据项结构的示意 图；
图3表示服务器组遍历顺序线性表的数据结构示意图；
图4表示图1中实施负载均衡调度任务的流程框图；
图5表示服务器新增一个连接时修改图3所示数据项的流程框图；
图6表示服务器断开一个连接时修改图1所示数据项的流程框图。
具体实施方式
下面结合附图与具体实施方式对本发明作进一步详细说明。
本例是以定点处理器用作调度处理器实现加权最小连接数调度的服务器 负载均衡方法的。图1表示本发明的一个实施例的运行过程的流程图。首先在 图1所示的流程图的步骤30中，根据服务器的性能选取服务器组中各服务器 的加权值。加权值越大，获得连接的机会也越大。一般为负载能力强的服务 器选取较大的加权值。例如一个服务器组由5台服务器组成。服务器的负载能 力用该服务器的最大允许TCP连接数CMAXi(i＝1，...，5)表示，服务器的当前的 服务总数量用该服务器的当前TCP连接数Ci(i＝1，...，5)表示。为方便起见，下文 将当前TCP连接数简称为当前连接数。假设5台服务器的最大允许TCP连接数 分别为1500、2000、1000、2000、3000，为这5台服务器选取的加权值 wi(i＝1，...，5)分别为：0.15，0.21，0.09，0.18，0.271。本例中为提高计算精 度，还采用了精度因子p＝0.03对加权值进行了细化，细化的方法如下：
Wi＝INT(wi/p)(i＝1，...，5)，
从而得到细化后的加权值5，7，3，6，9。精度因子p的选取原则是该因 子不应大于Max(wi)(i＝1，...，5)，且要使得wi计算后得到的余数尽量小，同时使 得计算所得的Wi数值较小为宜。该精度因子可以不是整数。该精度因子是在 控制机上预先计算好后下发到调度所用的定点处理器的。按照加权最小连接 数调度原理，系统运行时的下一个TCP连接会发送给服务器j，服务器j满足如 下的要求：
Cj/Wj＝min{Ci/Wi}(i＝1，...，5)。
系统在运行前还需要预先确定包括存储服务器组中各服务器的当前连接 信息的状态的数据结构(未示于图1中)。
图2是本例中存储第i台服务器当前连接信息的数据项10的示意图，其中包 括作为第三预定的数据项的第i台服务器的当前连接数110(Ci)，作为第一预定 的数据项的第i台服务器的当前连接数的首数120(Hi)，作为第二预定的数据项 第i台服务器的当前连接数的尾数130(Ri)。为方便起见，下文简称当前连接数 首数120为首数120，简称当前连接数尾数130为尾数130。本例中系统在运行 前还需要预先确定服务器组中各服务器的遍历顺序。图3表示存储服务器组遍 历顺序的线性表20。其中包括服务器组中的服务器数量210，在本例中数值为 5。服务器数量210之后依次存储5台服务器的当前连接信息的数据项10的索引 地址，ID1表示第1台实际服务器对应的上述地址220，IDi表示第i台服务器对 应的上述地址2i0。由于本例是采用了随机选取遍历起始地址的策略，在遍历 实际服务器时，不是每次都从固定的ID1开始，而是选取一个随机值，根据此 随机值确定起始遍历地址，这样遍历开始的第1台实际服务器不一定是ID1对 应的实际服务器，有可能是ID2或ID3对应的服务器。随机数的选取是本领域 的公知技术，如可以选取0-100的随机数对服务器组中服务器台数求余后加1 得到服务器遍历的起始地址。采取随机选取遍历起始地址策略的优点见下文 所述。另外一个需要确定的数据是服务器每增加或断开一个连接，当前连接 数110和连接数尾数130所增加或减小的步长，一般取为1，但可以选取任意一 个不超过服务器组的最小加权值的数作步长。
系统开机后进入初始化状态，即图1所示步骤40，包括将存储5台服务器 当前连接信息的数据项的当前连接数110、首数120、尾数130清零，接收来自 控制器的各服务器的加权值等等。当第一个用户请求接入时，系统通过图1所 示的步骤50判断是否有新的接入请求，进入步骤60，即负载均衡调度。
图4示出了负载均衡调度任务的流程图。在步骤610中，执行调度的定点 处理器首先利用公知技术确定一个随机数，如可以选取0-100的随机数对服务 器组中服务器台数求余后加1得到一个随机数，假设得到的随机数为2。根据 步骤620，处理器从第2台服务器开始遍历各服务器的连接数首数120。根据步 骤630判断是否存在最小首数120，若存在则选择最小首数120对应的服务器接 入，否则任选一台服务器接入。由于目前所有的服务器连接数首数120均为 0，可以认为不存在最小首数120，可以根据公知技术任选一台服务器接入。 另一种处理办法是，认为5台服务器具有相同的最小首数120，选择最先访问 到的那台即ID2对应的服务器接入。本领域一般技术人员明白，两种处理办法 对发明的实现没有实质性的区别。本例中采用后一种处理方法，选择首先访 问的具有最小连接数首数120的第2台服务器作为被调度的服务器，将接入请 求转发至第2台服务器。同时处理器修改第2台服务器的当前连接信息。
图5表示服务器新增一个连接时修改图3所述的增加连接时的数据项的流 程框图。根据步骤810，第2台服务器的当前连接数110首先增加步长1。根据 步骤820，判断当前连接数110是否超过该服务器的最大连接数，若是则给出 出错信息，结束处理；否则转到尾数130加步长1的步骤830。因为目前当前连 接数110数值是1，远小于第2台服务器的最大允许连接数，所以进入步骤 830，即尾数130加步长1，数值变为1。根据步骤840，判断尾数130是否大于 或等于该服务器的加权值，若是，则转到步骤850执行首数120加步长1，尾数 130减去加权值的任务；否则结束处理。由前面所述，第2台服务器的加权值 为7，尾数130小于第2台服务器的加权值，所以跳转到步骤860结束处理，修 改数据项的流程结束。本次的均衡调度任务结束。本领域一般技术人员明 白，即使不采用随机选取遍历地址的策略，如采用固定遍历起始地址，或者 遍历起始地址依次后移的方法，也可实现本发明。采用随机选取遍历地址的 方法，更利于在短时间内的负载均衡。
为不失一般性，下面再以一个中间状态为例来说明本发明的调度过程。 随着用户访问量的增加和结束，各服务器的当前连接数110及其首数120和尾 数130在不断变化。假如某时刻5台服务器的当前连接数110分别为17、25、 13、23、37，各连接数首数120依次为3、3、4、3、4，各连接数尾数130依次 为2、4、1、5、1(连接数的首数120和尾数130根据下述的步骤确定)。当有 新的服务请求接入时，根据图1中步骤50的判断，进入负载均衡调度步骤60。 处理器按照前述步骤首先确定服务器遍历的起始地址，假设从第3台服务器开 始遍历，遍历结束后有最小连接数首数120的服务器按遍历顺序依次有3台： 第4台、第1台、第2台，选择首先访问到的具有最小连接数首数120的第4台服 务器作为被调度的服务器，将接入请求转发至第4台服务器，由第4台服务器 提供接入服务。同时处理器修改表示第4台服务器的当前连接信息。第4台服 务器的当前连接数110首先加1，此时该连接数为24，小于第4台服务器的最大 连接数，所以进入步骤830，即尾数130加1，数值变为6。根据步骤840的判 断，由前面所述，第4台服务器的加权值为6，尾数130等于第4台服务器的 加，跳转到步骤850，第4台服务器的首数110加1，数值变成4，尾数130减去 加权值，数值变为0。结果5台服务器的当前连接数110分别为17、25、13、 24、37，各连接数首数120依次为3、3、4、4、4，各连接数尾数130依次为 2、4、1、0、1，修改数据项的流程结束。
仍以上述的结果为例，假设第4台服务器的一个连接因网络问题而断开， 即发生图1步骤70判断结果为肯定的情况，处理器进入断开连接时修改数据项 的步骤80，即图6所示的服务器断开一个连接时修改数据项的流程。首先根据 步骤661，第4台服务器的当前连接数110减去步长1，数值变为23。根据步骤 662判断当前连接数尾数130是否小于步长1，如果是则转到步骤663，判断首 数120是否大于0，否则转到步骤665，直接执行尾数130减去步长1的步骤。因 为当前连接数尾数130数值为0，结果为肯定的，进入步骤663，判断连接数首 数120是否大于0，如果是则转到步骤664，执行首数120减去步长1，尾数130 加上加权值再减去步长1的任务，否则给出错误信息，结束处理。当前的首数 120为4，判断结果为肯定的，进入步骤664，首数120减去步长1，数值变为 3，尾数130加上加权值减去步长1，数值变为5。服务器断开连接时修改数据 项的流程结束。
以上的实施例介绍了如何使用本发明实现加权最小连接分配的服务器负 载均衡技术。本领域的技术人员可以理解，本发明的思想和方法还可以用于 其他的场合和环境中，如在浮点处理器上实现该发明。只要涉及采用连接数 首数和连接数尾数来避免除法运算的负载均衡调度技术，都在本发明的保护 范围内，具体保护范围见权利要求书。此外，上述实施例只是本发明的作为 示范的具体实施方式，并不用于限制本发明的保护范围。