澳门新浦京娱乐场网站-www.146.net-新浦京娱乐场官网
做最好的网站

澳门新浦京娱乐场网站:Linux服务器集群系统,加

返回LVS系列文章:http://www.cnblogs.com/f-ck-need-u/p/7576137.html

  在介绍加权轮询算法(WeightedRound-Robin)之前,首先介绍一下轮询算法(Round-Robin)。

本文档的Copyleft归yfydz所有,使用GPL发布,可以自由拷贝,转载,转载时请保持文档的完整性,严禁用于任何商业用途。
msn: yfydz_no1@hotmail.com
来源:http://yfydz.cublog.cn

级别: 初级

距离小编将HA群集已经有一个多月啦,还记得小编在HA群集最后提出的一个小问题么,没有企业会拿HA来做一些普通业务的,HA一般都是来做一些关键性业务的,那么在这篇博客中小编就来讲讲LB群集(负载均衡群集)的原理以及实现啦 

 

  

  1. 均衡调度算法

章文嵩 (wensong@linux-vs.org),

一、负载均衡群集总体架构

加权调度算法是一种很常见的调度算法。如果只有两个后端,调度的顺序很容易,但是如果后端多于2个,可能就不像想象中那样的顺序进行调度。

一:轮询算法(Round-Robin)

5.1 算法说明

2002 年 5 月 20 日

使用负载均衡群集能实现综合业务的海量并发,在负载均衡架构中,Director(dispatcher)负责接收客户端请求,并将请求按照某种算法分发到后台真正提供服务的服务器上。按照层次来划分,有四层交换和七层交换。为了实现这种技术可以基于硬件来实现,常用的有F5(四层交换),也可以基于软件来实现ipvs(四层交换)、squid(七层交换)、nginx(七层交换) 

所以,本文揭秘加权调度算法到底是怎么进行调度的。

  轮询算法是最简单的一种负载均衡算法。它的原理是把来自用户的请求轮流分配给内部的服务器:从服务器1开始,直到服务器N,然后重新开始循环。

均衡调度算法是IPVS实现均衡功能的理论精髓,其他各种东西都只算是程序技巧,所以优先介绍。IPVS支持8种静态均衡算法,以下文字直接拷贝自IPVS网站:

本文主要讲述了LVS集群的IP负载均衡软件IPVS在内核中实现的各种连接调度算法。针对请求的服务时间变化很大,给出一个动态反馈负载均衡算法,它结合内核中的加权连接调度算法,根据动态反馈回来的负载信息来调整服务器的权值,来进一步避免服务器间的负载不平衡。

二、使用LVS(Linux Virtual Server)来实现负载均衡

1.加权调度算法公式

首先,给一个LVS官方手册给的加权调度算法公式:

假设有一组服务器S = {S0, S1, …, Sn-1},W(Si)表示服务器Si的权值,一个
指示变量i表示上一次选择的服务器,指示变量cw表示当前调度的权值,max(S)
表示集合S中所有服务器的最大权值,gcd(S)表示集合S中所有服务器权值的最大
公约数。变量i初始化为-1,cw初始化为零。

while (true) {
  i = (i   1) mod n;
    if (i == 0) {
        cw = cw - gcd(S); 
        if (cw <= 0) {
            cw = max(S);
        if (cw == 0)
            return NULL;
        }
    } 
  if (W(Si) >= cw) 
    return Si;
}

比如,A、B、C三个后端的权重比是2:3:4,那么一个调度循环内的调度顺序是CBCABCABC。

如果你不想从算法公式里找规律,那么看下面。

  算法的优点是其简洁性,它无需记录当前所有连接的状态,所以它是一种无状态调度。

************************quote start***********************************

前言

在linux的2.4之后的内核中有一种实现数据包请求处理的模块叫ipvs,并且提供了的相关客户端软件ipvsadm来实现规则的定义以完成对请求数据包的处理,小编的内核是2.6.18,看看它的内核配置文件可以发现IPVS的

2.加权调度通俗规律

记住三个权重调度规则:
1.先约分
2.从最大权重开始调度
3.同权重的后端,从前向后调度

例如,三台后端A:B:C=2:3:4。这里没法约分。

  1. 调度C
    调度之后,比率变成A:B:C=2:3:3,B和C权重相同,从B开始调度
  2. 调度B
    调度之后,比率变成A:B:C=2:2:3,所以下次调度C
  3. 调度C
    调度之后,比率变成A:B:C=2:2:2,下次从A开始
    当权重全部调整到相同值时,就按照先后顺序不断循环,直到调度完所有权重
  4. 调度A,调度之后,比率变成A:B:C=1:2:2
  5. 调度B,调度之后,比率变成A:B:C=1:1:2
  6. 调度C,调度之后,比率变成A:B:C=1:1:1
  7. 调度A,调度之后,比率变成A:B:C=0:1:1
  8. 调度B,调度之后,比率变成A:B:C=0:0:1
  9. 调度C,调度之后,比率变成A:B:C=0:0:0
  10. 进入下一个调度循环,顺序是:CBCABCABC

所以,每个调度循环的调度顺序为:CBCABCABC

调度过程如下图:

澳门新浦京娱乐场网站 1

再给个示例,A:B:C:D=2:4:6:8

首先约分,得到A:B:C:D=1:2:3:4

  1. 调度D
  2. 调度C
  3. 调度D
  4. 调度B
  5. 调度C
  6. 调度D
  7. 调度A
  8. 调度B
  9. 调度C
  10. 调度D

所以,调度顺序是DCDBCDABCD。

 

在上一篇文章中,我们主要讲述了LVS集群中实现的三种IP负载均衡技术,它们主要解决系统的可伸缩性和透明性问题,如何通过负载调度器将请求高效地分发 到不同的服务器执行,使得由多台独立计算机组成的集群系统成为一台虚拟服务器;客户端应用程序与集群系统交互时,就像与一台高性能的服务器交互一样。

澳门新浦京娱乐场网站 2

  假设有N台服务器:S = {S1, S2, …, Sn},一个指示变量i表示上一次选择的服务器ID。变量i被初始化为N-1。该算法的伪代码如下:

IPVS在内核中的负载均衡调度是以连接为粒度的。在HTTP协议(非持久)中,每个对象从WEB服务器上获取都需要建立一个TCP连接,同一用户的不同请求会被调度到不同的服务器上,所以这种细粒度的调度在一定程度上可以避免单个用户访问的突发性引起服务器间的负载不平衡。

本 文将主要讲述在负载调度器上的负载调度策略和算法,如何将请求流调度到各台服务器,使得各台服务器尽可能地保持负载均衡。文章主要由两个部分组成。第一部 分描述IP负载均衡软件IPVS在内核中所实现的各种连接调度算法;第二部分给出一个动态反馈负载均衡算法(Dynamic-feedback load balancing),它结合内核中的加权连接调度算法,根据动态反馈回来的负载信息来调整服务器的权值,来进一步避免服务器间的负载不平衡。

LVS的整体架构如图2-1所示:

j = i;
do
{
    j = (j   1) mod n;
    i = j;
    return Si;
} while (j != i);
return NULL;

在内核中的连接调度算法上,IPVS已实现了以下八种调度算法:

在 下面描述中,我们称客户的socket和服务器的socket之间的数据通讯为连接,无论它们是使用TCP还是UDP协议。对于UDP数据报文的调 度,IPVS调度器也会为之建立调度记录并设置超时值(如5分钟);在设定的时间内,来自同一地址(IP地址和端口)的UDP数据包会被调度到同一台服务 器。

澳门新浦京娱乐场网站 3

  轮询算法假设所有服务器的处理性能都相同,不关心每台服务器的当前连接数和响应速度。当请求服务间隔时间变化比较大时,轮询算法容易导致服务器间的负载不平衡。所以此种均衡算法适合于服务器组中的所有服务器都有相同的软硬件配置并且平均服务请求相对均衡的情况。

轮叫调度(Round-Robin Scheduling) 
加权轮叫调度(Weighted Round-Robin Scheduling) 
最小连接调度(Least-Connection Scheduling) 
加权最小连接调度(Weighted Least-Connection Scheduling) 
基于局部性的最少链接(Locality-Based Least Connections Scheduling) 
带复制的基于局部性最少链接(Locality-Based Least Connections with Replication Scheduling) 
目标地址散列调度(Destination Hashing Scheduling) 
源地址散列调度(Source Hashing Scheduling)


图2-1

 

下面,我们先介绍这八种连接调度算法的工作原理和算法流程,会在以后的文章中描述怎么用它们。



回页首

VIP(Virtual IP):Director对外呈现的IP地址,用户可以通过VIP来获取相关服务;

二:加权轮询算法(WeightedRound-Robin)

2.1. 轮叫调度

内核中的连接调度算法

DIP(Director's IP):Director用来和Real Server通信的IP;

  轮询算法并没有考虑每台服务器的处理能力,实际中可能并不是这种情况。由于每台服务器的配置、安装的业务应用等不同,其处理能力会不一样。所以,加权轮询算法的原理就是:根据服务器的不同处理能力,给每个服务器分配不同的权值,使其能够接受相应权值数的服务请求。

轮叫调度(Round Robin Scheduling)算法就是以轮叫的方式依次将请求调度不同的服务器,即每次调度执行i = (i 1) mod n,并选出第i台服务器。算法的优点是其简洁性,它无需记录当前所有连接的状态,所以它是一种无状态调度。

IPVS 在内核中的负载均衡调度是以连接为粒度的。在HTTP协议(非持久)中,每个对象从WEB服务器上获取都需要建立一个TCP连接,同一用户的不同请求会被 调度到不同的服务器上,所以这种细粒度的调度在一定程度上可以避免单个用户访问的突发性引起服务器间的负载不平衡。

RIP(Real IP):Real Server的IP;

 

在系统实现时,我们引入了一个额外条件,当服务器的权值为零时,表示该服务器不可用而不被调度。这样做的目的是将服务器切出服务(如屏蔽服务器故障和系统维护),同时与其他加权算法保持一致。所以,算法要作相应的改动,它的算法流程如下:

在内核中的连接调度算法上,IPVS已实现了以下八种调度算法:

 

  首先看一个简单的Nginx负载均衡配置。

轮叫调度算法流程 
假设有一组服务器S = {S0, S1, …, Sn-1},一个指示变量i表示上一次选择的
服务器,W(Si)表示服务器Si的权值。变量i被初始化为n-1,其中n > 0。

  • 轮叫调度(Round-Robin Scheduling)
  • 加权轮叫调度(Weighted Round-Robin Scheduling)
  • 最小连接调度(Least-Connection Scheduling)
  • 加权最小连接调度(Weighted Least-Connection Scheduling)
  • 基于局部性的最少链接(Locality-Based Least Connections Scheduling)
  • 带复制的基于局部性最少链接(Locality-Based Least Connections with Replication Scheduling)
  • 目标地址散列调度(Destination Hashing Scheduling)
  • 源地址散列调度(Source Hashing Scheduling)

三、LVS的模型分类

http {  
    upstream cluster {  
        server a weight=1;  
        server b weight=2;  
        server c weight=4;  
    }  
    ...
} 

j = i;
do {
 j = (j 1) mod n;
 if (W(Sj) > 0) {
  i = j;
  return Si;
 }
} while (j != i);
return NULL;  

下面,我们先介绍这八种连接调度算法的工作原理和算法流程,会在以后的文章中描述怎么用它们。

根据Director和后端服务器的通信方式,LVS大致可分为三类:Network Address Translation(LVS-NAT)、Director routing (LVS-DR )、IP tunneling (LVS-TUN ),小编就每一种分类做一下简要说明

  按照上述配置,Nginx每收到7个客户端的请求,会把其中的1个转发给后端a,把其中的2个转发给后端b,把其中的4个转发给后端c。

轮叫调度算法假设所有服务器处理性能均相同,不管服务器的当前连接数和响应速度。该算法相对简单,不适用于服务器组中处理性能不一的情况,而且当请求服务时间变化比较大时,轮叫调度算法容易导致服务器间的负载不平衡。

2.1. 轮叫调度

1、Virtual Server via Network Address Translation(LVS-NAT)

通过网络地址转换,Director重写请求报文的目标地址,根据预设的调度算法,将请求分派给后端的Real Server;Real Server的响应报文通过Director时,报文的源地址被重写,再返回给客户,完成整个负载调度过程。可以想象一下,所有的数据请求都经过Director,那实现Director的服务器压力三大啦;

2、Virtual Server via Direct Routing(LVS-DR)

为了解决LVS-NAT的的问题,便产生了LVS-DR,外界用户发送每次发送数据请求的时候是要经过Director的,Director通过一定得调度算法选择Real Server并将收到的客户端请求报文的目标MAC改写成为被选Real Server的MAC地址,而Real Server将响应客户端的时候并不经过Director了。

3、Virtual Server via IP Tunneling(LVS-TUN)

Director把请求报文通过IP隧道转发至Real Server,而Real Server将响应直接返回给客户,所以Director只处理请求报文。由于一般网络服务应答比请求报文大许多,采用 LVS-TUN技术后,集群系统的最大吞吐量可以提高10倍。

 

 

虽然Round-Robin DNS方法也是以轮叫调度的方式将一个域名解析到多个IP地址,但轮叫DNS方法的调度粒度是基于每个域名服务器的,域名服务器对域名解析的缓存会妨碍轮叫解析域名生效,这会导致服务器间负载的严重不平衡。这里,IPVS轮叫调度算法的粒度是基于每个连接的,同一用户的不同连接都会被调度到不同的服务器上,所以这种细粒度的轮叫调度要比DNS的轮叫调度优越很多。

轮叫调度(Round Robin Scheduling)算法就是以轮叫的方式依次将请求调度不同的服务器,即每次调度执行i = (i 1) mod n,并选出第i台服务器。算法的优点是其简洁性,它无需记录当前所有连接的状态,所以它是一种无状态调度。

四、Director采用的调度算法

  加权轮询算法的结果,就是要生成一个服务器序列。每当有请求到来时,就依次从该序列中取出下一个服务器用于处理该请求。比如针对上面的例子,加权轮询算法会生成序列{c, c, b, c, a, b, c}。这样,每收到7个客户端的请求,会把其中的1个转发给后端a,把其中的2个转发给后端b,把其中的4个转发给后端c。收到的第8个请求,重新从该序列的头部开始轮询。

2.2. 加权轮叫调度

在系统实现时,我们引入了一个额外条件,当服务器的权值为零时,表示该服务器不可用而不被调度。这样做的目的是将服务器切出服务(如屏蔽服务器故障和系统维护),同时与其他加权算法保持一致。所以,算法要作相应的改动,它的算法流程如下:

Director支持的调度算法可以直接从内核配置文件中看到的,如图4-1所示:

  总之,加权轮询算法要生成一个服务器序列,该序列中包含n个服务器。n是所有服务器的权重之和。在该序列中,每个服务器的出现的次数,等于其权重值。并且,生成的序列中,服务器的分布应该尽可能的均匀。比如序列{a, a, a, a, a, b, c}中,前五个请求都会分配给服务器a,这就是一种不均匀的分配方法,更好的序列应该是:{a, a, b, a, c, a, a}。

加权轮叫调度(Weighted Round-Robin Scheduling)算法可以解决服务器间性能不一的情况,它用相应的权值表示服务器的处理性能,服务器的缺省权值为1。假设服务器A的权值为1,B的权值为2,则表示服务器B的处理性能是A的两倍。加权轮叫调度算法是按权值的高低和轮叫方式分配请求到各服务器。权值高的服务器先收到的连接,权值高的服务器比权值低的服务器处理更多的连接,相同权值的服务器处理相同数目的连接数。加权轮叫调度算法流程如下:

轮叫调度算法流程

澳门新浦京娱乐场网站 4

  下面介绍两种加权轮询算法:

加权轮叫调度算法流程 
假设有一组服务器S = {S0, S1, …, Sn-1},W(Si)表示服务器Si的权值,一个
指示变量i表示上一次选择的服务器,指示变量cw表示当前调度的权值,max(S)
表示集合S中所有服务器的最大权值,gcd(S)表示集合S中所有服务器权值的最大
公约数。变量i初始化为-1,cw初始化为零。

假设有一组服务器S = {S0, S1, …, Sn-1},一个指示变量i表示上一次选择的
服务器,W(Si)表示服务器Si的权值。变量i被初始化为n-1,其中n > 0。
j = i;
do {
    j = (j   1) mod n;
 if (W(Sj) > 0) {
        i = j;
     return Si;
 }
} while (j != i);
return NULL;

图4-1

 

while (true) {
  i = (i 1) mod n;
if (i == 0) {
     cw = cw - gcd(S); 
     if (cw <= 0) {
       cw = max(S);
       if (cw == 0)
         return NULL;
     }
  } 
  if (W(Si) >= cw) 
    return Si;
}

轮叫调度算法假设所有服务器处理性能均相同,不管服务器的当前连接数和响应速度。该算法相对简单,不适用于服务器组中处理性能不一的情况,而且当请求服务时间变化比较大时,轮叫调度算法容易导致服务器间的负载不平衡。

当然这九种调度算法又可以分为两大类,分别是静态调度和动态调度啦,小编这里做一下解释:

1:普通加权轮询算法

例如,有三个服务器A、B和C分别有权值4、3和2,则在一个调度周期内(mod sum(W(Si)))调度序列为AABABCABC。加权轮叫调度算法还是比较简单和高效。当请求的服务时间变化很大,单独的加权轮叫调度算法依然会导致服务器间的负载不平衡。

虽 然Round-Robin DNS方法也是以轮叫调度的方式将一个域名解析到多个IP地址,但轮叫DNS方法的调度粒度是基于每个域名服务器的,域名服务器对域名解析的缓存会妨碍轮 叫解析域名生效,这会导致服务器间负载的严重不平衡。这里,IPVS轮叫调度算法的粒度是基于每个连接的,同一用户的不同连接都会被调度到不同的服务器 上,所以这种细粒度的轮叫调度要比DNS的轮叫调度优越很多。

1、固定调度算法

按照某种既定的算法,不考虑实时的连接数予以分配:

A、Round-robin(RR)轮循:将外部请求按顺序轮流分配到集群中的Real Server, 它均等地对待每一台服务器,而不管服务器上实际的连接数和系统负载;

B、Weighted round-robin(WRR)加权轮询:给每台Real Server分配一个权值,权值越大,分到的请求数越多;

C、Destination hashing (DH)目标散列:根据请求的目标IP地址,作为散列键(Hash Key)从静态分配的散列表找出对应的服务器,若该服务器是可用的且未超载,将请求发送到该服务器,否则返回空。来自于同一个IP地址的请求都被重定向到同一台Real Server上,保证目标地址不变;

D、Source hashing(SH)源地址散列:根据请求的源IP地址,作为散列键(Hash Key)从静态分配的散列表找出对应的服务器,若该服务器是可用的且未超载,将请求发送到该服务器,否则返回空。Director必须确保响应的数据包必须通过请求数据包所经过的路由器或者防火墙,保证源地址不变。

2、动态调度算法

通过检查服务器上当前连接的活动状态来重新决定下一步调度方式该如何实现:

A、Lease Connection (LC) 最少连接:哪一个Real Server上的连接数少就将下一个连接请求定向到那台Real Server上去。算法实现:连接数=活动连接数*256 非活动连接数;

B、Weight Least-Connection(WLC) 加权最少连接:在最少连接的基础上给每台Real Server分配一个权重。算法实现:连接数=(活动连接数*256 非活动连接数)÷权重,是一种比较理想的算法;

C、Shortest Expected Delay (SED) 最短期望延迟:不再考虑非活动连接数,算法实现:连接数=(活动连接数 1) *256 ÷权重;

D、Never Queue (NQ) 永不排队算法:对SED的改进,当新请求过来的时候不仅要取决于SED算法所得到的值,还要取决于Real Server上是否有活动连接;

E、Locality-Based Least-Connection (LBLC) 基于本地状态的最少连接:在DH算法的基础上还要考虑服务器上的活动连接数;

F、Locality-Based Least-Connection with Replication Scheduling (LBLCR) 带复制的基于本地的最少连接:是LBLC算法的改进。

         这种算法的原理是:在服务器数组S中,首先计算所有服务器权重的最大值max(S),以及所有服务器权重的最大公约数gcd(S)。

从上面的算法流程中,我们可以看出当服务器的权值为零时,该服务器不被被调度;当所有服务器的权值为零,即对于任意i有W(Si)=0,则没有任何服务器可用,算法返回NULL,所有的新连接都会被丢掉。加权轮叫调度也无需记录当前所有连接的状态,所以它也是一种无状态调度。

2.2. 加权轮叫调度

澳门新浦京娱乐场网站 5

         index表示本次请求到来时,选择的服务器的索引,初始值为-1;current_weight表示当前调度的权值,初始值为max(S)。

2.3. 最小连接调度

加 权轮叫调度(Weighted Round-Robin Scheduling)算法可以解决服务器间性能不一的情况,它用相应的权值表示服务器的处理性能,服务器的缺省权值为1。假设服务器A的权值为1,B的 权值为2,则表示服务器B的处理性能是A的两倍。加权轮叫调度算法是按权值的高低和轮叫方式分配请求到各服务器。权值高的服务器先收到的连接,权值高的服 务器比权值低的服务器处理更多的连接,相同权值的服务器处理相同数目的连接数。加权轮叫调度算法流程如下:

         当请求到来时,从index 1开始轮询服务器数组S,找到其中权重大于current_weight的第一个服务器,用于处理该请求。记录其索引到结果序列中。

最小连接调度(Least-Connection Scheduling)算法是把新的连接请求分配到当前连接数最小的服务器。最小连接调度是一种动态调度算法,它通过服务器当前所活跃的连接数来估计服务器的负载情况。调度器需要记录各个服务器已建立连接的数目,当一个请求被调度到某台服务器,其连接数加1;当连接中止或超时,其连接数减一。

加权轮叫调度算法流程

  在轮询服务器数组时,如果到达了数组末尾,则重新从头开始搜索,并且减小current_weight的值:current_weight -= gcd(S)。如果current_weight等于0,则将其重置为max(S)。

在系统实现时,我们也引入当服务器的权值为零时,表示该服务器不可用而不被调度,它的算法流程如下:

假设有一组服务器S = {S0, S1, …, Sn-1},W(Si)表示服务器Si的权值,一个
指示变量i表示上一次选择的服务器,指示变量cw表示当前调度的权值,max(S)
表示集合S中所有服务器的最大权值,gcd(S)表示集合S中所有服务器权值的最大
公约数。变量i和cw最初都被初始化为零。
while (true) {
    if (i == 0) {
      cw = cw - gcd(S);
      if (cw <= 0) {
      cw = max(S);
       if (cw == 0)
           return NULL;
       }
  } else i = (i   1) mod n;
  if (W(Si) >= cw)
        return Si;
}

 

最小连接调度算法流程 
假设有一组服务器S = {S0, S1, ..., Sn-1},W(Si)表示服务器Si的权值,
C(Si)表示服务器Si的当前连接数。

例如,有三个服务器A、B和C分别有权值4、3和2,则在一个调度周期内(mod sum(W(Si)))调度序列为AABABCABC。加权轮叫调度算法还是比较简单和高效。当请求的服务时间变化很大,单独的加权轮叫调度算法依然会导致服务器间的负载不平衡。

  该算法的实现代码如下:

for (m = 0; m < n; m ) {
 if (W(Sm) > 0) {
  for (i = m 1; i < n; i ) {
   if (W(Si) <= 0)
    continue;
   if (C(Si) < C(Sm))
    m = i;
  }
  return Sm;
 }
}
return NULL;  

从 上面的算法流程中,我们可以看出当服务器的权值为零时,该服务器不被被调度;当所有服务器的权值为零,即对于任意i有W(Si)=0,则没有任何服务器可 用,算法返回NULL,所有的新连接都会被丢掉。加权轮叫调度也无需记录当前所有连接的状态,所以它也是一种无状态调度。

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <string.h>

typedef struct
{
    int weight;
    char name[2];
}server;


int getsum(int *set, int size)
{
    int i = 0; 
    int res = 0;

    for (i = 0; i < size; i  )
        res  = set[i];

    return res;
}

int gcd(int a, int b)
{
    int c;
    while(b)
    {
        c = b;
        b = a % b;
        a = c;
    }

    return a;
}

int getgcd(int *set, int size)
{
    int i = 0; 
    int res = set[0];

    for (i = 1; i < size; i  )
        res = gcd(res, set[i]);

    return res;
}

int getmax(int *set, int size)
{
    int i = 0; 
    int res = set[0];

    for (i = 1; i < size; i  )
    {
        if (res < set[i]) res = set[i];
    }

    return res;
}


int lb_wrr__getwrr(server *ss, int size, int gcd, int maxweight, int *i, int *cw) 
{
    while (1) 
    {
        *i = (*i   1) % size;
        if (*i == 0) 
        {
            *cw = *cw - gcd;
            if (*cw <= 0) 
            {
                *cw = maxweight;
                if (*cw == 0) 
                {
                    return -1;
                }
            }
        }
        if (ss[*i].weight >= *cw) 
        {
            return *i;
        }
    }
}

void wrr(server *ss, int *weights, int size)
{
    int i = 0;

    int gcd = getgcd(weights, size);
    int max = getmax(weights, size);
    int sum = getsum(weights, size);


    int index = -1;
    int curweight = 0;

    for (i = 0; i < sum; i  ) 
    {
        lb_wrr__getwrr(ss, size, gcd, max, &(index), &(curweight));
        printf("%s(%d) ", ss[index].name, ss[index].weight);
    }

    printf("n");
    return;
}

server *initServers(char **names, int *weights, int size)
{
    int i = 0;
    server *ss = calloc(size, sizeof(server));


    for (i = 0; i < size; i  )
    {
        ss[i].weight = weights[i];
        memcpy(ss[i].name, names[i], 2);
    }

    return ss;
}

int main()
{
    int i = 0;

    int weights[] = {1, 2, 4};
    char *names[] = {"a", "b", "c"};
    int size = sizeof(weights) / sizeof(int);


    server *ss = initServers(names, weights, size);

    printf("server is ");
    for (i = 0; i < size; i  )
    {
        printf("%s(%d) ", ss[i].name, ss[i].weight);
    }
    printf("n");

    printf("nwrr sequence is ");
    wrr(ss, weights, size);

    return;
}

当各个服务器有相同的处理性能时,最小连接调度算法能把负载变化大的请求分布平滑到各个服务器上,所有处理时间比较长的请求不可能被发送到同一台服务器上。但是,当各个服务器的处理能力不同时,该算法并不理想,因为TCP连接处理请求后会进入TIME_WAIT状态,TCP的TIME_WAIT一般为2分钟,此时连接还占用服务器的资源,所以会出现这样情形,性能高的服务器已处理所收到的连接,连接处于TIME_WAIT状态,而性能低的服务器已经忙于处理所收到的连接,还不断地收到新的连接请求。

2.3. 最小连接调度

  上面的代码中,算法的核心部分就是wrr和lb_wrr__getwrr函数。在wrr函数中,首先计算所有服务器权重的最大公约数gcd,权重最大值max,以及权重之和sum。

2.4. 加权最小连接调度

最 小连接调度(Least-Connection Scheduling)算法是把新的连接请求分配到当前连接数最小的服务器。最小连接调度是一种动态调度算法,它通过服务器当前所活跃的连接数来估计服务 器的负载情况。调度器需要记录各个服务器已建立连接的数目,当一个请求被调度到某台服务器,其连接数加1;当连接中止或超时,其连接数减一。

  初始时,index为-1,curweight为0,然后依次调用lb_wrr__getwrr函数,得到本次选择的服务器索引index。

加权最小连接调度(Weighted Least-Connection Scheduling)算法是最小连接调度的超集,各个服务器用相应的权值表示其处理性能。服务器的缺省权值为1,系统管理员可以动态地设置服务器的权值。加权最小连接调度在调度新连接时尽可能使服务器的已建立连接数和其权值成比例。加权最小连接调度的算法流程如下:

在系统实现时,我们也引入当服务器的权值为零时,表示该服务器不可用而不被调度,它的算法流程如下:

 

加权最小连接调度的算法流程

最小连接调度算法流程

  算法的核心思想体现在lb_wrr__getwrr函数中。以例子说明更好理解一些:对于服务器数组{a(1), b(2), c(4)}而言,gcd为1,maxweight为4。

假设有一组服务器S = {S0, S1, ..., Sn-1},W(Si)表示服务器Si的权值,
C(Si)表示服务器Si的当前连接数。所有服务器当前连接数的总和为
CSUM = ΣC(Si)  (i=0, 1, .. , n-1)。当前的新连接请求会被发送服务器Sm,
当且仅当服务器Sm满足以下条件
  (C(Sm) / CSUM)/ W(Sm) = min { (C(Si) / CSUM) / W(Si)}  (i=0, 1, . , n-1)
  其中W(Si)不为零
因为CSUM在这一轮查找中是个常数,所以判断条件可以简化为
  C(Sm) / W(Sm) = min { C(Si) / W(Si)}  (i=0, 1, . , n-1)
  其中W(Si)不为零

假设有一组服务器S = {S0, S1, ..., Sn-1},W(Si)表示服务器Si的权值,
C(Si)表示服务器Si的当前连接数。
for (m = 0; m < n; m  ) {
   if (W(Sm) > 0) {
        for (i = m 1; i < n; i  ) {
         if (W(Si) <= 0)
             continue;
          if (C(Si) < C(Sm))
              m = i;
     }
      return Sm;
 }
}
return NULL;

  第1次调用该函数时,i(index)为-1,cw(current_weight)为0,进入循环后,i首先被置为0,因此cw被置为maxweight。从i开始轮询服务器数组ss,第一个权重大于等于cw的服务器是c,因此,i被置为2,并返回其值。

因为除法所需的CPU周期比乘法多,且在Linux内核中不允许浮点除法,服务器的
权值都大于零,所以判断条件C(Sm) / W(Sm) > C(Si) / W(Si) 可以进一步优化
为C(Sm)
W(Si) > C(Si)* W(Sm)。同时保证服务器的权值为零时,服务器不被调
度。所以,算法只要执行以下流程。*

当各个服务器有相同的处理性能时,最小连接调度算法能 把负载变化大的请求分布平滑到各个服务器上,所有处理时间比较长的请求不可能被发送到同一台服务器上。但是,当各个服务器的处理能力不同时,该算法并不理 想,因为TCP连接处理请求后会进入TIME_WAIT状态,TCP的TIME_WAIT一般为2分钟,此时连接还占用服务器的资源,所以会出现这样情 形,性能高的服务器已处理所收到的连接,连接处于TIME_WAIT状态,而性能低的服务器已经忙于处理所收到的连接,还不断地收到新的连接请求。

  第2次调用该函数时,i为2,cw为maxweight。进入循环后,i首先被置为0,因此cw被置为cw-gcd,也就是3。从i开始轮询服务器数组ss,第一个权重大于等于cw的服务器还是c,因此,i被置为2,并返回其值。

for (m = 0; m < n; m ) {
 if (W(Sm) > 0) {
  for (i = m 1; i < n; i ) {
   if (C(Sm)
W(Si) > C(Si)*W(Sm))
    m = i;
  }
  return Sm;
 }
}
return NULL;
 *

2.4. 加权最小连接调度

  第3次调用该函数时,i为2,cw为3。进入循环后,i首先被置为0,因此cw被置为cw-gcd,也就是2。从i开始轮询服务器数组ss,第一个权重大于等于cw的服务器是b,因此,i被置为1,并返回其值。

2.5. 基于局部性的最少链接调度

加 权最小连接调度(Weighted Least-Connection Scheduling)算法是最小连接调度的超集,各个服务器用相应的权值表示其处理性能。服务器的缺省权值为1,系统管理员可以动态地设置服务器的权 值。加权最小连接调度在调度新连接时尽可能使服务器的已建立连接数和其权值成比例。加权最小连接调度的算法流程如下:

  第4次调用该函数时,i为1,cw为2。进入循环后,i首先被置为2,从i开始轮询服务器数组ss,第一个权重大于等于cw的服务器是c,因此,i被置为2,并返回其值。

基于局部性的最少链接调度(Locality-Based Least Connections Scheduling,以下简称为LBLC)算法是针对请求报文的目标IP地址的负载均衡调度,目前主要用于Cache集群系统,因为在Cache集群中客户请求报文的目标IP地址是变化的。这里假设任何后端服务器都可以处理任一请求,算法的设计目标是在服务器的负载基本平衡情况下,将相同目标IP地址的请求调度到同一台服务器,来提高各台服务器的访问局部性和主存Cache命中率,从而整个集群系统的处理能力。

加权最小连接调度的算法流程

  第5次调用该函数时,i为2,cw为2。进入循环后,i首先被置为0,因此cw被置为cw-gcd,也就是1。从i开始轮询服务器数组ss,第一个权重大于等于cw的服务器是a,因此,i被置为0,并返回其值。

LBLC调度算法先根据请求的目标IP地址找出该目标IP地址最近使用的服务器,若该服务器是可用的且没有超载,将请求发送到该服务器;若服务器不存在,或者该服务器超载且有服务器处于其一半的工作负载,则用“最少链接”的原则选出一个可用的服务器,将请求发送到该服务器。该算法的详细流程如下:

假设有一组服务器S = {S0, S1, ..., Sn-1},W(Si)表示服务器Si的权值,
C(Si)表示服务器Si的当前连接数。所有服务器当前连接数的总和为
CSUM = ΣC(Si)  (i=0, 1, .. , n-1)。当前的新连接请求会被发送服务器Sm,
当且仅当服务器Sm满足以下条件
  (C(Sm) / CSUM)/ W(Sm) = min { (C(Si) / CSUM) / W(Si)}  (i=0, 1, . , n-1)
  其中W(Si)不为零
因为CSUM在这一轮查找中是个常数,所以判断条件可以简化为
  C(Sm) / W(Sm) = min { C(Si) / W(Si)}  (i=0, 1, . , n-1)
  其中W(Si)不为零
因为除法所需的CPU周期比乘法多,且在Linux内核中不允许浮点除法,服务器的
权值都大于零,所以判断条件C(Sm) / W(Sm) > C(Si) / W(Si) 可以进一步优化
为C(Sm)*W(Si) > C(Si)* W(Sm)。同时保证服务器的权值为零时,服务器不被调
度。所以,算法只要执行以下流程。
for (m = 0; m < n; m  ) {
  if (W(Sm) > 0) {
        for (i = m 1; i < n; i  ) {
         if (C(Sm)*W(Si) > C(Si)*W(Sm))
              m = i;
     }
      return Sm;
 }
}
return NULL;

  第6次调用该函数时,i为0,cw为1。进入循环后,i首先被置为1,从i开始轮询服务器数组ss,第一个权重大于等于cw的服务器是b,因此,i被置为1,并返回其值。

LBLC调度算法流程 
假设有一组服务器S = {S0, S1, ..., Sn-1},W(Si)表示服务器Si的权值,
C(Si)表示服务器Si的当前连接数。ServerNode[dest_ip]是一个关联变量,表示
目标IP地址所对应的服务器结点,一般来说它是通过Hash表实现的。WLC(S)表示
在集合S中的加权最小连接服务器,即前面的加权最小连接调度。Now为当前系统
时间。

2.5. 基于局部性的最少链接调度

  第7次调用该函数时,i为1,cw为1。进入循环后,i首先被置为2,从i开始轮询服务器数组ss,第一个权重大于等于cw的服务器是c,因此,i被置为2,并返回其值。

if (ServerNode[dest_ip] is NULL) then {
 n = WLC(S);
 if (n is NULL) then return NULL;
 ServerNode[dest_ip].server = n;
} else {
 n = ServerNode[澳门新浦京娱乐场网站:Linux服务器集群系统,加权调整算法的法则。dest_ip].server;
 if ((n is dead) OR
     (C(n) > W(n) AND
      there is a node m with C(m) < W(m)/2))) then {
  n = WLC(S);
  if (n is NULL) then return NULL;
  ServerNode[dest_ip].server = n;
 }
}
ServerNode[dest_ip].lastuse = Now;
return n;  

基 于局部性的最少链接调度(Locality-Based Least Connections Scheduling,以下简称为LBLC)算法是针对请求报文的目标IP地址的负载均衡调度,目前主要用于Cache集群系统,因为在Cache集群中 客户请求报文的目标IP地址是变化的。这里假设任何后端服务器都可以处理任一请求,算法的设计目标是在服务器的负载基本平衡情况下,将相同目标IP地址的 请求调度到同一台服务器,来提高各台服务器的访问局部性和主存Cache命中率,从而整个集群系统的处理能力。

 

此外,对关联变量ServerNode[dest_ip]要进行周期性的垃圾回收(Garbage Collection),将过期的目标IP地址到服务器关联项进行回收。过期的关联项是指哪些当前时间(实现时采用系统时钟节拍数jiffies)减去最近使用时间超过设定过期时间的关联项,系统缺省的设定过期时间为24小时。

LBLC调度 算法先根据请求的目标IP地址找出该目标IP地址最近使用的服务器,若该服务器是可用的且没有超载,将请求发送到该服务器;若服务器不存在,或者该服务器 超载且有服务器处于其一半的工作负载,则用“最少链接”的原则选出一个可用的服务器,将请求发送到该服务器。该算法的详细流程如下:

  经过7(1 2 4)次调用之后,每个服务器被选中的次数正好是其权重值。上面程序的运行结果如下:

2.6. 带复制的基于局部性最少链接调度

LBLC调度算法流程

server is a(1) b(2) c(4) 

wrr sequence is c(4) c(4) b(2) c(4) a(1) b(2) c(4) 

带复制的基于局部性最少链接调度(Locality-Based Least Connections with Replication Scheduling,以下简称为LBLCR)算法也是针对目标IP地址的负载均衡,目前主要用于Cache集群系统。它与LBLC算法的不同之处是它要维护从一个目标IP地址到一组服务器的映射,而LBLC算法维护从一个目标IP地址到一台服务器的映射。对于一个“热门”站点的服务请求,一台Cache 服务器可能会忙不过来处理这些请求。这时,LBLC调度算法会从所有的Cache服务器中按“最小连接”原则选出一台Cache服务器,映射该“热门”站点到这台Cache服务器,很快这台Cache服务器也会超载,就会重复上述过程选出新的Cache服务器。这样,可能会导致该“热门”站点的映像会出现在所有的Cache服务器上,降低了Cache服务器的使用效率。LBLCR调度算法将“热门”站点映射到一组Cache服务器(服务器集合),当该“热门”站点的请求负载增加时,会增加集合里的Cache服务器,来处理不断增长的负载;当该“热门”站点的请求负载降低时,会减少集合里的Cache服务器数目。这样,该“热门”站点的映像不太可能出现在所有的Cache服务器上,从而提供Cache集群系统的使用效率。

假设有一组服务器S = {S0, S1, ..., Sn-1},W(Si)表示服务器Si的权值,
C(Si)表示服务器Si的当前连接数。ServerNode[dest_ip]是一个关联变量,表示
目标IP地址所对应的服务器结点,一般来说它是通过Hash表实现的。WLC(S)表示
在集合S中的加权最小连接服务器,即前面的加权最小连接调度。Now为当前系统
时间。
if (ServerNode[dest_ip] is NULL) then {
  n = WLC(S);
    if (n is NULL) then return NULL;
   ServerNode[dest_ip].server = n;
} else {
   n = ServerNode[dest_ip].server;
    if ((n is dead) OR
     (C(n) > W(n) AND
         there is a node m with C(m) < W(m)/2))) then {
     n = WLC(S);
        if (n is NULL) then return NULL;
       ServerNode[dest_ip].server = n;
    }
}
ServerNode[dest_ip].lastuse = Now;
return n;

         如果有新的请求到来,第8次调用该函数时,i为2,cw为1。进入循环后,i首先被置为0,cw被置为cw-gcd,也就是0,因此cw被重置为maxweight。这种情况就跟第一次调用该函数时一样了。因此,7次是一个轮回,7次之后,重复之前的过程。

LBLCR算法先根据请求的目标IP地址找出该目标IP地址对应的服务器组;按“最小连接”原则从该服务器组中选出一台服务器,若服务器没有超载,将请求发送到该服务器;若服务器超载;则按“最小连接”原则从整个集群中选出一台服务器,将该服务器加入到服务器组中,将请求发送到该服务器。同时,当该服务器组有一段时间没有被修改,将最忙的服务器从服务器组中删除,以降低复制的程度。LBLCR调度算法的流程如下:

此外,对关联变量 ServerNode[dest_ip]要进行周期性的垃圾回收(Garbage Collection),将过期的目标IP地址到服务器关联项进行回收。过期的关联项是指哪些当前时间(实现时采用系统时钟节拍数jiffies)减去最 近使用时间超过设定过期时间的关联项,系统缺省的设定过期时间为24小时。

 

LBLCR调度算法流程 
假设有一组服务器S = {S0, S1, ..., Sn-1},W(Si)表示服务器Si的权值,
C(Si)表示服务器Si的当前连接数。ServerSet[dest_ip]是一个关联变量,表示
目标IP地址所对应的服务器集合,一般来说它是通过Hash表实现的。WLC(S)表示
在集合S中的加权最小连接服务器,即前面的加权最小连接调度;WGC(S)表示在
集合S中的加权最大连接服务器。Now为当前系统时间,lastmod表示集合的最近
修改时间,T为对集合进行调整的设定时间。

2.6. 带复制的基于局部性最少链接调度

        这背后的数学原理,自己思考了一下,总结如下:

if (ServerSet[dest_ip] is NULL) then {
 n = WLC(S);
 if (n is NULL) then return NULL;
 add n into ServerSet[dest_ip];
} else {
 n = WLC(ServerSet[dest_ip]);
 if ((n is NULL) OR
     (n is dead) OR
     (C(n) > W(n) AND
      there is a node m with C(m) < W(m)/2))) then {
  n = WLC(S);
  if (n is NULL) then return NULL;
  add n into ServerSet[dest_ip];
 } else
 if (|ServerSet[dest_ip]| > 1 AND
     Now - ServerSet[dest_ip].lastmod > T) then {
  m = WGC(ServerSet[dest_ip]);
  remove m from ServerSet[dest_ip];
 }
}
ServerSet[dest_ip].lastuse = Now;
if (ServerSet[dest_ip] changed) then
 ServerSet[dest_ip].lastmod = Now;
return n;  

带 复制的基于局部性最少链接调度(Locality-Based Least Connections with Replication Scheduling,以下简称为LBLCR)算法也是针对目标IP地址的负载均衡,目前主要用于Cache集群系统。它与LBLC算法的不同之处是它要 维护从一个目标IP地址到一组服务器的映射,而LBLC算法维护从一个目标IP地址到一台服务器的映射。对于一个“热门”站点的服务请求,一台Cache 服务器可能会忙不过来处理这些请求。这时,LBLC调度算法会从所有的Cache服务器中按“最小连接”原则选出一台Cache服务器,映射该“热门”站 点到这台Cache服务器,很快这台Cache服务器也会超载,就会重复上述过程选出新的Cache服务器。这样,可能会导致该“热门”站点的映像会出现 在所有的Cache服务器上,降低了Cache服务器的使用效率。LBLCR调度算法将“热门”站点映射到一组Cache服务器(服务器集合),当该“热 门”站点的请求负载增加时,会增加集合里的Cache服务器,来处理不断增长的负载;当该“热门”站点的请求负载降低时,会减少集合里的Cache服务器 数目。这样,该“热门”站点的映像不太可能出现在所有的Cache服务器上,从而提供Cache集群系统的使用效率。

  current_weight的值,其变化序列就是一个等差序列:max, max-gcd, max-2gcd, …, 0(max),将current_weight从max变为0的过程,称为一个轮回。

此外,对关联变量ServerSet[dest_ip]也要进行周期性的垃圾回收(Garbage Collection),将过期的目标IP地址到服务器关联项进行回收。过期的关联项是指哪些当前时间(实现时采用系统时钟节拍数jiffies)减去最近使用时间(lastuse)超过设定过期时间的关联项,系统缺省的设定过期时间为24小时。

LBLCR 算法先根据请求的目标IP地址找出该目标IP地址对应的服务器组;按“最小连接”原则从该服务器组中选出一台服务器,若服务器没有超载,将请求发送到该服 务器;若服务器超载;则按“最小连接”原则从整个集群中选出一台服务器,将该服务器加入到服务器组中,将请求发送到该服务器。同时,当该服务器组有一段时 间没有被修改,将最忙的服务器从服务器组中删除,以降低复制的程度。LBLCR调度算法的流程如下:

  针对每个current_weight,该算法就是要把服务器数组从头到尾扫描一遍,将其中权重大于等于current_weight的所有服务器填充到结果序列中。扫描完一遍服务器数组之后,将current_weight变为下一个值,再一次从头到尾扫描服务器数组。

2.7. 目标地址散列调度

LBLCR调度算法流程

  在current_weight变化过程中,不管current_weight当前为何值,具有max权重的服务器每次肯定会被选中。因此,具有max权重的服务器会在序列中出现max/gcd次(等差序列中的项数)。

目标地址散列调度(Destination Hashing Scheduling)算法也是针对目标IP地址的负载均衡,但它是一种静态映射算法,通过一个散列(Hash)函数将一个目标IP地址映射到一台服务器。

假设有一组服务器S = {S0, S1, ..., Sn-1},W(Si)表示服务器Si的权值,
C(Si)表示服务器Si的当前连接数。ServerSet[dest_ip]是一个关联变量,表示
目标IP地址所对应的服务器集合,一般来说它是通过Hash表实现的。WLC(S)表示
在集合S中的加权最小连接服务器,即前面的加权最小连接调度;WGC(S)表示在
集合S中的加权最大连接服务器。Now为当前系统时间,lastmod表示集合的最近
修改时间,T为对集合进行调整的设定时间。
if (ServerSet[dest_ip] is NULL) then {
    n = WLC(S);
    if (n is NULL) then return NULL;
   add n into ServerSet[dest_ip];
} else {
    n = WLC(ServerSet[dest_ip]);
   if ((n is NULL) OR
     (n is dead) OR
     (C(n) > W(n) AND
         there is a node m with C(m) < W(m)/2))) then {
     n = WLC(S);
        if (n is NULL) then return NULL;
       add n into ServerSet[dest_ip];
 } else
 if (|ServerSet[dest_ip]| > 1 AND
        Now - ServerSet[dest_ip].lastmod > T) then {
        m = WGC(ServerSet[dest_ip]);
       remove m from ServerSet[dest_ip];
  }
}
ServerSet[dest_ip].lastuse = Now;
if (ServerSet[dest_ip] changed) then
 ServerSet[dest_ip].lastmod = Now;
return n;

  更一般的,当current_weight变为x之后,权重为x的服务器,在current_weight接下来的变化过程中,每次都会被选中,因此,具有x权重的服务器,会在序列中出现x/gcd次。所以,每个服务器在结果序列中出现的次数,是与其权重成正比的,这就是符合加权轮询算法的要求了。

目标地址散列调度算法先根据请求的目标IP地址,作为散列键(Hash Key)从静态分配的散列表找出对应的服务器,若该服务器是可用的且未超载,将请求发送到该服务器,否则返回空。该算法的流程如下:

此外,对关联变量 ServerSet[dest_ip]也要进行周期性的垃圾回收(Garbage Collection),将过期的目标IP地址到服务器关联项进行回收。过期的关联项是指哪些当前时间(实现时采用系统时钟节拍数jiffies)减去最 近使用时间(lastuse)超过设定过期时间的关联项,系统缺省的设定过期时间为24小时。

 

目标地址散列调度算法流程 
假设有一组服务器S = {S0, S1, ..., Sn-1},W(Si)表示服务器Si的权值,
C(Si)表示服务器Si的当前连接数。ServerNode[]是一个有256个桶(Bucket)的
Hash表,一般来说服务器的数目会运小于256,当然表的大小也是可以调整的。
算法的初始化是将所有服务器顺序、循环地放置到ServerNode表中。若服务器的
连接数目大于2倍的权值,则表示服务器已超载。

2.7. 目标地址散列调度

2:平滑的加权轮询

n = ServerNode[hashkey(dest_ip)];
if ((n is dead) OR
 (W(n) == 0) OR
    (C(n) > 2
W(n))) then
 return NULL;
return n;
 *

目标地址散列调度(Destination Hashing Scheduling)算法也是针对目标IP地址的负载均衡,但它是一种静态映射算法,通过一个散列(Hash)函数将一个目标IP地址映射到一台服务器。

         上面的加权轮询算法有个缺陷,就是某些情况下生成的序列是不均匀的。比如针对这样的配置:

在实现时,我们采用素数乘法Hash函数,通过乘以素数使得散列键值尽可能地达到较均匀的分布。所采用的素数乘法Hash函数如下:

目标地址散列调度算法先根据请求的目标IP地址,作为散列键(Hash Key)从静态分配的散列表找出对应的服务器,若该服务器是可用的且未超载,将请求发送到该服务器,否则返回空。该算法的流程如下:

http {  
    upstream cluster {  
        server a weight=5;  
        server b weight=1;  
        server c weight=1;  
    }  
    ...
} 

素数乘法Hash函数 
static inline unsigned hashkey(unsigned int dest_ip)
{
    return (dest_ip
2654435761UL) & HASH_TAB_MASK;
}
其中,2654435761UL是2到2^32 (4294967296)间接近于黄金分割的素数,
  (sqrt(5) - 1) / 2 =  0.618033989
  2654435761 / 4294967296 = 0.618033987
 *

目标地址散列调度算法流程

         生成的序列是这样的:{a,a, a, a, a, c, b}。会有5个连续的请求落在后端a上,分布不太均匀。

2.8. 源地址散列调度

假设有一组服务器S = {S0, S1, ..., Sn-1},W(Si)表示服务器Si的权值,
C(Si)表示服务器Si的当前连接数。ServerNode[]是一个有256个桶(Bucket)的
Hash表,一般来说服务器的数目会运小于256,当然表的大小也是可以调整的。
算法的初始化是将所有服务器顺序、循环地放置到ServerNode表中。若服务器的
连接数目大于2倍的权值,则表示服务器已超载。
n = ServerNode[hashkey(dest_ip)];
if ((n is dead) OR
   (W(n) == 0) OR
    (C(n) > 2*W(n))) then
    return NULL;
return n;

 

源地址散列调度(Source Hashing Scheduling)算法正好与目标地址散列调度算法相反,它根据请求的源IP地址,作为散列键(Hash Key)从静态分配的散列表找出对应的服务器,若该服务器是可用的且未超载,将请求发送到该服务器,否则返回空。它采用的散列函数与目标地址散列调度算法的相同。它的算法流程与目标地址散列调度算法的基本相似,除了将请求的目标IP地址换成请求的源IP地址,所以这里不一一叙述。

在实现时,我们采用素数乘法Hash函数,通过乘以素数使得散列键值尽可能地达到较均匀的分布。所采用的素数乘法Hash函数如下:

  在Nginx源码中,实现了一种叫做平滑的加权轮询(smooth weighted round-robin balancing)的算法,它生成的序列更加均匀。比如前面的例子,它生成的序列为{ a, a, b, a, c, a, a},转发给后端a的5个请求现在分散开来,不再是连续的。

在实际应用中,源地址散列调度和目标地址散列调度可以结合使用在防火墙集群中,它们可以保证整个系统的唯一出入口。

素数乘法Hash函数

 

************************quote end***********************************

static inline unsigned hashkey(unsigned int dest_ip)
{
    return (dest_ip* 2654435761UL) & HASH_TAB_MASK;
}
其中,2654435761UL是2到2^32 (4294967296)间接近于黄金分割的素数,
  (sqrt(5) - 1) / 2 =  0.618033989
  2654435761 / 4294967296 = 0.618033987

  该算法的原理如下:

5.2 算法具体实现

2.8. 源地址散列调度

  每个服务器都有两个权重变量:

每个调度算法的实现就是填写一个ip_vs_scheduler结构,在IPVS服务ip_vs_service结构中指向它即可,这样在连接到达该服务时,通过调度算法选择具体的目的主机。每个算法作为一个单独的内核模块,可由内核配置是否包括该模块。

源 地址散列调度(Source Hashing Scheduling)算法正好与目标地址散列调度算法相反,它根据请求的源IP地址,作为散列键(Hash Key)从静态分配的散列表找出对应的服务器,若该服务器是可用的且未超载,将请求发送到该服务器,否则返回空。它采用的散列函数与目标地址散列调度算法 的相同。它的算法流程与目标地址散列调度算法的基本相似,除了将请求的目标IP地址换成请求的源IP地址,所以这里不一一叙述。

  a:weight,配置文件中指定的该服务器的权重,这个值是固定不变的;

以下以最简单的rr算法来说明,该算法在net/ipv4/ipvs/ip_vs_rr.c中定义。

在实际应用中,源地址散列调度和目标地址散列调度可以结合使用在防火墙集群中,它们可以保证整个系统的唯一出入口。

  b:current_weight,服务器目前的权重。一开始为0,之后会动态调整。

rr算法结构定义:


 

static struct ip_vs_scheduler ip_vs_rr_scheduler = {
 .name =   "rr",   /* name */
 .refcnt =  ATOMIC_INIT(0),
 .module =  THIS_MODULE,
 .init_service =  ip_vs_rr_init_svc,
 .done_service =  ip_vs_rr_done_svc,
 .update_service = ip_vs_rr_update_svc,
 .schedule =  ip_vs_rr_schedule,
};



回页首

  每次当请求到来,选取服务器时,会遍历数组中所有服务器。对于每个服务器,让它的current_weight增加它的weight;同时累加所有服务器的weight,并保存为total。

init_service()函数进行算法初始化,在虚拟服务ip_vs_service和调度器绑定时调用(ip_vs_bind_scheduler()函数);done_service()函数进行算法的清除,在虚拟服务ip_vs_service和调度器解除绑定时调用(ip_vs_unbind_scheduler()函数);update_service()函数在目的服务器变化时调用(如ip_vs_add_dest(), ip_vs_edit_dest()等函数);

动态反馈负载均衡算法

  遍历完所有服务器之后,如果该服务器的current_weight是最大的,就选择这个服务器处理本次请求。最后把该服务器的current_weight减去total。

在RR算法中,这三个函数都很简单:

动 态反馈负载均衡算法考虑服务器的实时负载和响应情况,不断调整服务器间处理请求的比例,来避免有些服务器超载时依然收到大量请求,从而提高整个系统的吞吐 率。图1显示了该算法的工作环境,在负载调度器上运行Monitor Daemon进程,Monitor Daemon来监视和收集各个服务器的负载信息。Monitor Daemon可根据多个负载信息算出一个综合负载值。Monitor Daemon将各个服务器的综合负载值和当前权值算出一组新的权值,若新权值和当前权值的差值大于设定的阀值,Monitor Daemon将该服务器的权值设置到内核中的IPVS调度中,而在内核中连接调度一般采用加权轮叫调度算法或者加权最小连接调度算法。

 

static int ip_vs_rr_init_svc(struct ip_vs_service *svc)
{
// 其实RR算法也没有什么专用调度数据,sched_data被初始化为目的服务器链表头
 svc->sched_data = &svc->destinations;
 return 0;
}

澳门新浦京娱乐场网站 6
图1:动态反馈负载均衡算法的工作环境

  上述描述可能不太直观,来看个例子。比如针对这样的配置:

static int ip_vs_rr_done_svc(struct ip_vs_service *svc)
{
// 空函数,因为对RR没什么可释放的
 return 0;
}

3.1. 连接调度

http {  
    upstream cluster {  
        server a weight=4;  
        server b weight=2;  
        server c weight=1;  
    }  
    ...
} 

static int ip_vs_rr_update_svc(struct ip_vs_service *svc)
{
// sched_data重新指向服务器链表头
 svc->sched_data = &svc->destinations;
 return 0;
}

当 客户通过TCP连接访问网络访问时,服务所需的时间和所要消耗的计算资源是千差万别的,它依赖于很多因素。例如,它依赖于请求的服务类型、当前网络带宽的 情况、以及当前服务器资源利用的情况。一些负载比较重的请求需要进行计算密集的查询、数据库访问、很长响应数据流;而负载比较轻的请求往往只需要读一个 HTML页面或者进行很简单的计算。

  按照这个配置,每7个客户端请求中,a会被选中4次、b会被选中2次、c会被选中1次,且分布平滑。我们来算算看是不是这样子的。

而算法核心函数schedule()则是在ip_vs_schedule()函数中在新建IPVS连接前调用,找到真正的服务器提供服务,建立IPVS连接。

请求处理时间的千差万别可能会导致服务器利用的倾斜(Skew),即服务器间的负载不平 衡。例如,有一个WEB页面有A、B、C和D文件,其中D是大图像文件,浏览器需要建立四个连接来取这些文件。当多个用户通过浏览器同时访问该页面时,最 极端的情况是所有D文件的请求被发到同一台服务器。所以说,有可能存在这样情况,有些服务器已经超负荷运行,而其他服务器基本是闲置着。同时,有些服务器 已经忙不过来,有很长的请求队列,还不断地收到新的请求。反过来说,这会导致客户长时间的等待,觉得系统的服务质量差。

  initial  current_weight  of a, b, c is {0, 0, 0}

/*
 * Round-Robin Scheduling
 */
static struct ip_vs_dest *
ip_vs_rr_schedule(struct ip_vs_service *svc, const struct sk_buff *skb)
{
 struct list_head *p, *q;
 struct ip_vs_dest *dest;

3.1.1. 简单连接调度

澳门新浦京娱乐场网站 7

 IP_VS_DBG(6, "ip_vs_rr_schedule(): Scheduling...n");

简单连接调度可能会使得服务器倾斜的发生。在上面的例子中,若采用轮叫调度算法,且集群中正好有四台服务器,必有一台服务器总是收到D文件的请求。这种调度策略会导致整个系统资源的低利用率,因为有些资源被用尽导致客户的长时间等待,而其他资源空闲着。

  通过上述过程,可得以下结论:

 write_lock(&svc->sched_lock);
// p实际就是实际目的服务器的链表中的某一个节点
// sched_data保存的是上一次调度时用到的节点
 p = (struct list_head *)svc->sched_data;
 p = p->next;
// q是p的下一项
 q = p;
 do {
  /* skip list head */
  if (q == &svc->destinations) {
   q = q->next;
   continue;
  }
// 只要当前链表目的服务器不是超载而且该服务器权重不为0,就返回该节点
  dest = list_entry(q, struct ip_vs_dest, n_list);
  if (!(dest->flags & IP_VS_DEST_F_OVERLOAD) &&
      atomic_read(&dest->weight) > 0)
   /* HIT */
   goto out;
  q = q->next;
 } while (q != p);
 write_unlock(&svc->sched_lock);
 return NULL;

3.1.2. 实际TCP/IP流量的特征

  a:7个请求中,a、b、c分别被选取了4、2、1次,符合它们的权重值。

  out:
// 保存要使用的节点到sched_data,下次调度时就会取下一个节点,实现轮询
 svc->sched_data = q;
 write_unlock(&svc->sched_lock);
 IP_VS_DBG(6, "RR: server %u.%u.%u.%u:%u "
    "activeconns %d refcnt %d weight %dn",
    NIPQUAD(dest->addr), ntohs(dest->port),
    atomic_read(&dest->activeconns),
    atomic_read(&dest->refcnt), atomic_read(&dest->weight));

文 献[1]说明网络流量是呈波浪型发生的,在一段较长时间的小流量后,会有一段大流量的访问,然后是小流量,这样跟波浪一样周期性地发生。文献 [2,3,4,5]揭示在WAN和LAN上网络流量存在自相似的特征,在WEB访问流也存在自相似性。这就需要一个动态反馈机制,利用服务器组的状态来应 对访问流的自相似性。

  b:7个请求中,a、b、c被选取的顺序为a, b,a, c, a, b, a,分布均匀,权重大的后端a没有被连续选取。

 return dest;
}

3.2. 动态反馈负载均衡机制

  c:每经过7个请求后,a、b、c的current_weight又回到初始值{0, 0,0},因此上述流程是不断循环的。

 

TCP/IP流量的特征通俗地说是有许多短事务和一些长事务组成,而长事务的工作量在整个工作量占有较高的比例。所以,我们要设计一种负载均衡算法,来避免长事务的请求总被分配到一些机器上,而是尽可能将带有毛刺(Burst)的分布分割成相对较均匀的分布。

 

5.3 系统调度

我 们提出基于动态反馈负载均衡机制,来控制新连接的分配,从而控制各个服务器的负载。例如,在IPVS调度器的内核中使用加权轮叫调度(Weighted Round-Robin Scheduling)算法来调度新的请求连接;在负载调度器的用户空间中运行Monitor Daemon。Monitor Daemon定时地监视和收集各个服务器的负载信息,根据多个负载信息算出一个综合负载值。Monitor Daemon将各个服务器的综合负载值和当前权值算出一组新的权值。当综合负载值表示服务器比较忙时,新算出的权值会比其当前权值要小,这样新分配到该服 务器的请求数就会少一些。当综合负载值表示服务器处于低利用率时,新算出的权值会比其当前权值要大,来增加新分配到该服务器的请求数。若新权值和当前权值 的差值大于设定的阀值,Monitor Daemon将该服务器的权值设置到内核中的IPVS调度中。过了一定的时间间隔(如2秒钟),Monitor Daemon再查询各个服务器的情况,并相应调整服务器的权值;这样周期性地进行。可以说,这是一个负反馈机制,使得服务器保持较好的利用率。

  根据该算法实现的代码如下:

系统基本调度函数为ip_vs_schedule(),在TCP、UDP的conn_shedule中调用,而AH、ESP协议不管:

在 加权轮叫调度算法中,当服务器的权值为零,已建立的连接会继续得到该服务器的服务,而新的连接不会分配到该服务器。系统管理员可以将一台服务器的权值设置 为零,使得该服务器安静下来,当已有的连接都结束后,他可以将该服务器切出,对其进行维护。维护工作对系统都是不可少的,比如硬件升级和软件更新等,零权 值使得服务器安静的功能很主要。所以,在动态反馈负载均衡机制中我们要保证该功能,当服务器的权值为零时,我们不对服务器的权值进行调整。

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <string.h>

typedef struct
{
    int weight;
    int cur_weight;
    char name[3];
}server;

int getsum(int *set, int size)
{
    int i = 0; 
    int res = 0;

    for (i = 0; i < size; i  )
        res  = set[i];

    return res;
}

server *initServers(char **names, int *weights, int size)
{
    int i = 0;
    server *ss = calloc(size 1, sizeof(server));

    for (i = 0; i < size; i  )
    {
        ss[i].weight = weights[i];
        memcpy(ss[i].name, names[i], 3);
        ss[i].cur_weight = 0;
    }
    return ss;
}

int getNextServerIndex(server *ss, int size)
{
    int i ;
    int index = -1;
    int total = 0;

    for (i = 0; i < size; i  )
    {
        ss[i].cur_weight  = ss[i].weight;
        total  = ss[i].weight;

        if (index == -1 || ss[index].cur_weight < ss[i].cur_weight)
        {
            index = i;
        }
    }

    ss[index].cur_weight -= total;
    return index;
}

void wrr_nginx(server *ss, int *weights, int size)
{
    int i = 0;
    int index = -1;
    int sum = getsum(weights, size);

    for (i = 0; i < sum; i  ) 
    {
        index = getNextServerIndex(ss, size);
        printf("%s(%d) ", ss[index].name, ss[index].weight);
    }
    printf("n");
}

int main()
{
    int i = 0;
    int weights[] = {4, 2, 1};
    char *names[] = {"a", "b", "c"};
    int size = sizeof(weights) / sizeof(int);

    server *ss = initServers(names, weights, size);

    printf("server is ");
    for (i = 0; i < size; i  )
    {
        printf("%s(%d) ", ss[i].name, ss[i].weight);
    }
    printf("n");

    printf("nwrr_nginx sequence is ");
    wrr_nginx(ss, weights, size);

    return;
}

/* net/ipv4/ipv4/ip_vs_core.c */

3.3. 综合负载

         上述代码的运行结果如下:

/*
 *  IPVS main scheduling function
 *  It selects a server according to the virtual service, and
 *  creates a connection entry.
 *  Protocols supported: TCP, UDP
 */
struct ip_vs_conn *
ip_vs_schedule(struct ip_vs_service *svc, const struct sk_buff *skb)
{
 struct ip_vs_conn *cp = NULL;
 struct iphdr *iph = skb->nh.iph;
 struct ip_vs_dest *dest;
 __u16 _ports[2], *pptr;

在 计算综合负载时,我们主要使用两大类负载信息:输入指标和服务器指标。输入指标是在调度器上收集到的,而服务器指标是在服务器上的各种负载信息。我们用综 合负载来反映服务器当前的比较确切负载情况,对于不同的应用,会有不同的负载情况,这里我们引入各个负载信息的系数,来表示各个负载信息在综合负载中轻 重。系统管理员根据不同应用的需求,调整各个负载信息的系数。另外,系统管理员设置收集负载信息的时间间隔。

server is a(4) b(2) c(1) 

wrr_nginx sequence is a(4) b(2) a(4) c(1) a(4) b(2) a(4) 

// TCP/UDP头指针,[0]为源端口,[1]为目的端口
 pptr = skb_header_pointer(skb, iph->ihl*4,
      sizeof(_ports), _ports);
 if (pptr == NULL)
  return NULL;

输入指标主要是 在单位时间内服务器收到新连接数与平均连接数的比例,它是在调度器上收集到的,所以这个指标是对服务器负载情况的一个估计值。在调度器上有各个服务器收到 连接数的计数器,对于服务器Si,可以得到分别在时间T1和T2时的计数器值Ci1和Ci2,计算出在时间间隔T2-T1内服务器Si收到新连接数Ni = Ci2 - Ci1。这样,得到一组服务器在时间间隔T2-T1内服务器Si收到新连接数{Ni},服务器Si的输入指标INPUTi为其新连接数与n台服务器收到平 均连接数的比值,其公式为

         如果服务器配置为:{a(5),b(1), c(1)},则运行结果如下:

 /*
  *    Persistent service
  */
// 如果是固定服务,调用ip_vs_sched_persist()
 if (svc->flags & IP_VS_SVC_F_PERSISTENT)
  return ip_vs_sched_persist(svc, skb, pptr);

澳门新浦京娱乐场网站 8

server is a(5) b(1) c(1) 

wrr_nginx sequence is a(5) a(5) b(1) a(5) c(1) a(5) a(5) 

 /*
  *    Non-persistent service
  */
 if (!svc->fwmark && pptr[1] != svc->port) {
// 目的端口不等于服务端口,IPVS不处理该包
  if (!svc->port)
   IP_VS_ERR("Schedule: port zero only supported "
      "in persistent services, "
      "check your ipvs configurationn");
  return NULL;
 }
// 调用调度器的调度函数获取一个目的服务器指针
 dest = svc->scheduler->schedule(svc, skb);
 if (dest == NULL) {
  IP_VS_DBG(1, "Schedule: no dest found.n");
  return NULL;
 }

服 务器指标主要记录服务器各种负载信息,如服务器当前CPU负载LOADi、服务器当前磁盘使用情况Di、当前内存利用情况Mi和当前进程数目Pi。有两种 方法可以获得这些信息;一是在所有的服务器上运行着SNMP(Simple Network Management Protocol)服务进程,而在调度器上的Monitor Daemon通过SNMP向各个服务器查询获得这些信息;二是在服务器上实现和运行收集信息的Agent,由Agent定时地向Monitor Daemon报告负载信息。若服务器在设定的时间间隔内没有响应,Monitor Daemon认为服务器是不可达的,将服务器在调度器中的权值设置为零,不会有新的连接再被分配到该服务器;若在下一次服务器有响应,再对服务器的权值进 行调整。再对这些数据进行处理,使其落在[0, ∞)的区间内,1表示负载正好,大于1表示服务器超载,小于1表示服务器处于低负载状态。获得调整后的数据有DISKi、MEMORYi和 PROCESSi。

         可见,该算法生成的序列确实更加均匀。

 /*
  *    Create a connection entry.
  */
// 新建一个IPVS连接
 cp = ip_vs_conn_new(iph->protocol,
       iph->saddr, pptr[0],
       iph->daddr, pptr[1],
       dest->addr, dest->port?dest->port:pptr[1],
       0,
       dest);
 if (cp == NULL)
  return NULL;

另一个重要的服务器指标是服务器所提供服务的响应时间,它能比较好地反映服务器上请求等待队列的长度和请 求的处理时间。调度器上的Monitor Daemon作为客户访问服务器所提供的服务,测得其响应时间。例如,测试从WEB服务器取一个HTML页面的响应延时,Monitor Daemon只要发送一个“GET /”请求到每个服务器,然后记录响应时间。若服务器在设定的时间间隔内没有响应,Monitor Daemon认为服务器是不可达的,将服务器在调度器中的权值设置为零。同样,我们对响应时间进行如上调整,得到RESPONSEi。

 

 IP_VS_DBG(6, "Schedule fwd:%c c:%u.%u.%u.%u:%u v:%u.%u.%u.%u:%u "
    "d:%u.%u.%u.%u:%u conn->flags:%X conn->refcnt:%dn",
    ip_vs_fwd_tag(cp),
    NIPQUAD(cp->caddr), ntohs(cp->cport),
    NIPQUAD(cp->vaddr), ntohs(cp->vport),
    NIPQUAD(cp->daddr), ntohs(cp->dport),
    cp->flags, atomic_read(&cp->refcnt));
// 服务和连接相关计数器统计
 ip_vs_conn_stats(cp, svc);
 return cp;
}

这里,我们引入一组可以动态调整的系数Ri来表示各个负载参数的重要程度,其中ΣRi = 1。综合负载可以通过以下公式计算出:

         该算法背后的数学原理,实在没想出来,google也没查到相关论证……,等待后续查证了。

固定调度函数,用在多连接协议处理中将子连接与主连接挂钩:

澳门新浦京娱乐场网站 9

 

/*
 *  IPVS persistent scheduling function
 *  It creates a connection entry according to its template if exists,
 *  or selects a server and creates a connection entry plus a template.
 *  Locking: we are svc user (svc->refcnt), so we hold all dests too
 *  Protocols supported: TCP, UDP
 */
static struct ip_vs_conn *
ip_vs_sched_persist(struct ip_vs_service *svc,
      const struct sk_buff *skb,
      __u16 ports[2])
{
 struct ip_vs_conn *cp = NULL;
 struct iphdr *iph = skb->nh.iph;
 struct ip_vs_dest *dest;
 struct ip_vs_conn *ct;
 __u16  dport;  /* destination port to forward */
 __u32  snet;  /* source network of the client, after masking */

例 如,在WEB服务器集群中,我们采用以下系数{0.1, 0.3, 0.1, 0.1, 0.1, 0.3},认为服务器的CPU负载和请求响应时间较其他参数重要一些。若当前的系数Ri不能很好地反映应用的负载,系统管理员可以对系数不断地修正,直到 找到贴近当前应用的一组系数。

三:健康检查

 /* Mask saddr with the netmask to adjust template granularity */
// 网络部分地址
 snet = iph->saddr & svc->netmask;

另外,关于查询时间间隔的设置,虽然很短的间隔可以更确切地反映各个服务器的负载,但是很频繁 地查询(如1秒钟几次)会给调度器和服务器带来一定的负载,如频繁执行的Monitor Daemon在调度器会有一定的开销,同样频繁地查询服务器指标会服务器带来一定的开销。所以,这里要有个折衷(Tradeoff),我们一般建议将时间 间隔设置在5到20秒之间。

  负载均衡算法,一般要伴随健康检查算法一起使用。健康检查算法的作用就是对所有的服务器进行存活和健康检测,看是否需要提供给负载均衡做选择。如果一台机器的服务出现了问题,健康检查就会将这台机器从服务列表中去掉,让负载均衡算法看不到这台机器的存在。

 IP_VS_DBG(6, "p-schedule: src %u.%u.%u.%u:%u dest %u.%u.%u.%u:%u "
    "mnet %u.%u.%u.%un",
    NIPQUAD(iph->saddr), ntohs(ports[0]),
    NIPQUAD(iph->daddr), ntohs(ports[1]),
    NIPQUAD(snet));

3.4. 权值计算

  具体在加权轮询算法中,当健康检查算法检测出某服务器的状态发生了变化,比如从UP到DOWN,或者反之时,就会更新权重,重新计算结果序列。

 /*
  * As far as we know, FTP is a very complicated network protocol, and
  * it uses control connection and data connections. For active FTP,
  * FTP server initialize data connection to the client, its source port
  * is often 20. For passive FTP, FTP server tells the clients the port
  * that it passively listens to,  and the client issues the data
  * connection. In the tunneling or direct routing mode, the load
  * balancer is on the client-to-server half of connection, the port
  * number is unknown to the load balancer. So, a conn template like
  * <caddr, 0, vaddr, 0, daddr, 0> is created for persistent FTP
  * service, and a template like <caddr, 0, vaddr, vport, daddr, dport>
  * is created for other persistent services.
  */
 if (ports[1] == svc->port) {
// 数据包目的端口是服务端口,正向请求子连接
  /* Check if a template already exists */
// 查找连接模板, 专门区分了是否是FTP端口,所以程序在此没有扩展性
// 源地址用的是网络部分地址,源端口用0
// 所谓模板,应该就是指主连接,相当于netfilter跟踪子连接时端口部分不进行限制
// 不过这里IPVS跟踪子连接作的没有netfilter好
  if (svc->port != FTPPORT)
   ct = ip_vs_ct_in_get(iph->protocol, snet, 0,
            iph->daddr, ports[1]);
  else
   ct = ip_vs_ct_in_get(iph->protocol, snet, 0,
            iph->daddr, 0);

当 服务器投入集群系统中使用时,系统管理员对服务器都设定一个初始权值DEFAULT_WEIGHTi,在内核的IPVS调度中也先使用这个权值。然后,随 着服务器负载的变化,对权值进行调整。为了避免权值变成一个很大的值,我们对权值的范围作一个限制[DEFAULT_WEIGHTi, SCALE*DEFAULT_WEIGHTi],SCALE是可以调整的,它的缺省值为10。

 

  if (!ct || !ip_vs_check_template(ct)) {
// 找不到连接模板或者连接模板的目的服务器不可用
   /*
    * No template found or the dest of the connection
    * template is not available.
    */
// 使用调度器调度找一个服务器
   dest = svc->scheduler->schedule(svc, skb);
   if (dest == NULL) {
    IP_VS_DBG(1, "p-schedule: no dest found.n");
    return NULL;
   }

Monitor Daemon周期性地运行,若DEFAULT_WEIGHTi不为零,则查询该服务器的各负载参数,并计算出综合负载值AGGREGATE_LOADi。我们引入以下权值计算公式,根据服务器的综合负载值调整其权值。

参考:

   /*
    * Create a template like <protocol,caddr,0,
    * vaddr,vport,daddr,dport> for non-ftp service,
    * and <protocol,caddr,0,vaddr,0,daddr,0>
    * for ftp service.
    */
// 建立一个新连接模板,如果是FTP服务,目的端口不确定
   if (svc->port != FTPPORT)
    ct = ip_vs_conn_new(iph->protocol,
          snet, 0,
          iph->daddr,
          ports[1],
          dest->addr, dest->port,
          IP_VS_CONN_F_TEMPLATE,
          dest);
   else
    ct = ip_vs_conn_new(iph->protocol,
          snet, 0,
          iph->daddr, 0,
          dest->addr, 0,
          IP_VS_CONN_F_TEMPLATE,
          dest);
   if (ct == NULL)
    return NULL;

澳门新浦京娱乐场网站 10

http://kb.linuxvirtualserver.org/wiki/Weighted_Round-Robin_Scheduling

   ct->timeout = svc->timeout;
  } else {
   /* set destination with the found template */
// 找到连接模板,目的服务器用连接的目的服务器
   dest = ct->dest;
  }
// 目的端口为目的服务器端口
  dport = dest->port;
 } else {
// 数据包目的端口不是服务端口,可能是反向请求的子连接
  /*
   * Note: persistent fwmark-based services and persistent
   * port zero service are handled here.
   * fwmark template: <IPPROTO_IP,caddr,0,fwmark,0,daddr,0>
   * port zero template: <protocol,caddr,0,vaddr,0,daddr,0>
   */
// 找相关连接模板,此时用的端口都是0
  if (svc->fwmark)
   ct = ip_vs_ct_in_get(IPPROTO_IP, snet, 0,
            htonl(svc->fwmark), 0);
  else
   ct = ip_vs_ct_in_get(iph->protocol, snet, 0,
            iph->daddr, 0);

在 公式中,0.95是我们想要达到的系统利用率,A是一个可调整的系数(缺省值为5)。当综合负载值为0.95时,服务器权值不变;当综合负载值大于 0.95时,权值变小;当综合负载值小于0.95时,权值变大。若新权值大于SCALE*DEFAULT_WEIGHTi,我们将新权值设为 SCALE*DEFAULT_WEIGHTi。若新权值与当前权值的差异超过设定的阀值,则将新权值设置到内核中的IPVS调度参数中,否则避免打断 IPVS调度的开销。我们可以看出这是一个负反馈公式,会使得权值调整到一个稳定点,如系统达到理想利用率时,权值是不变的。

http://ialloc.org/posts/2014/11/14/ngx-notes-module-http-sticky/

  if (!ct || !ip_vs_check_template(ct)) {
// 没找到连接模板或连接模板目的服务不可用
   /*
    * If it is not persistent port zero, return NULL,
    * otherwise create a connection template.
    */
   if (svc->port)
    return NULL;
// 
// 使用调度器调度找一个服务器
   dest = svc->scheduler->schedule(svc, skb);
   if (dest == NULL) {
    IP_VS_DBG(1, "p-schedule: no dest found.n");
    return NULL;
   }

在 实际使用中,若发现所有服务器的权值都小于他们的DEFAULT_WEIGHT,则说明整个服务器集群处于超载状态,这时需要加入新的服务器结点到集群中 来处理部分负载;反之,若所有服务器的权值都接近于SCALE*DEFAULT_WEIGHT,则说明当前系统的负载都比较轻。

http://blog.csdn.net/zhangskd/article/details/50194069

   /*
    * Create a template according to the service
    */
// 建立一个新连接模板
   if (svc->fwmark)
    ct = ip_vs_conn_new(IPPROTO_IP,
          snet, 0,
          htonl(svc->fwmark), 0,
          dest->addr, 0,
          IP_VS_CONN_F_TEMPLATE,
          dest);
   else
    ct = ip_vs_conn_new(iph->protocol,
          snet, 0,
          iph->daddr, 0,
          dest->addr, 0,
          IP_VS_CONN_F_TEMPLATE,
          dest);
   if (ct == NULL)
    return NULL;

3.5. 一个实现例子

   ct->timeout = svc->timeout;
  } else {
   /* set destination with the found template */
// 找到连接模板,目的服务器用连接的目的服务器
   dest = ct->dest;
  }
  dport = ports[1];
 }

我们在RedHat集群管理工具Piranha[6]中实现了一个简单的动态反馈负载均衡算法。在综合负载上,它只考虑服务器的CPU负载(Load Average),使用以下公式进行权值调整:

 /*
  *    Create a new connection according to the template
  */
// 建立一个新连接
 cp = ip_vs_conn_new(iph->protocol,
       iph->saddr, ports[0],
       iph->daddr, ports[1],
       dest->addr, dport,
       0,
       dest);
 if (cp == NULL) {
  ip_vs_conn_put(ct);
  return NULL;
 }

澳门新浦京娱乐场网站 11

 /*
  *    Add its control
  */
// 将连接模块作为新连接的主连接
 ip_vs_control_add(cp, ct);
// get的时候增加了连接模板ct的引用计数,现在减少之
 ip_vs_conn_put(ct);

服 务器权值调整区间为[DEFAULT_WEIGHTi, 10*DEFAULT_WEIGHTi],A为DEFAULT_WEIGHTi /2,而权值调整的阀值为DEFAULT_WEIGHTi /4。1是所想要达到的系统利用率。Piranha每隔20秒查询各台服务器的CPU负载,进行权值计算和调整。

// 连接服务计数器统计
 ip_vs_conn_stats(cp, svc);
 return cp;
}




回页首

小结

本文主要讲述了IP虚拟服务器在内核中实现的八种连接调度算法:

  • 轮叫调度(Round-Robin Scheduling)
  • 加权轮叫调度(Weighted Round-Robin Scheduling)
  • 最小连接调度(Least-Connection Scheduling)
  • 加权最小连接调度(Weighted Least-Connection Scheduling)
  • 基于局部性的最少链接(Locality-Based Least Connections Scheduling)
  • 带复制的基于局部性最少链接(Locality-Based Least Connections with Replication Scheduling)
  • 目标地址散列调度(Destination Hashing Scheduling)
  • 源地址散列调度(Source Hashing Scheduling)

因 为请求的服务时间差异较大,内核中的连接调度算法容易使得服务器运行出现倾斜。为此,给出了一个动态反馈负载均衡算法,结合内核中的加权连接调度算法,根 据动态反馈回来的负载信息来调整服务器的权值,来调整服务器间处理请求数的比例,从而避免服务器间的负载不平衡。动态反馈负载算法可以较好地避免服务器的 倾斜,提高系统的资源使用效率,从而提高系统的吞吐率。

参考资料

  1. William Stalling, Viewpoint: Self-similarity upsets data traffic assumptions, IEEE Spectrum, January 1997.
  2. Kihong Park, Gitae Kim, Mark Crovella, "On the Effect of Traffic Self-similarity on Network Performance", In Proceedings of the 1997 SPIE International Conference on Performance and Control of Network Systems, 1997.
  3. Nicolas D. Georganas, Self-Similar ("Fractal") Traffic in ATM Networks, In Proceedings of the 2nd International Workshop on Advanced Teleservices and High-Speed Communications Architectures (IWACA'94), pages 1-7, Heidelberg, Germany, September 1994.
  4. Mark Crovella and Azer Besavros, Explaining World Wide Web Traffic Self-Similarity. Technical report, Boston University, October 1995, TR-95-015.
  5. Bruce A. Mah. An Empirical Model of HTTP Network Traffic. In Proceedings of INFOCOM 97, Kobe, Japan, April 1997.
  6. Red Hat High Availability Server Project,
  7. The Linux Virtual Server Project, http://www.LinuxVirtualServer.org/

关于作者

澳门新浦京娱乐场网站 12

澳门新浦京娱乐场网站 13

章文嵩博士,开放源码及Linux内核的开发者,著名的Linux集群项目--LVS(Linux Virtual Server)的创始人和主要开发人员。他目前工作于国家并行与分布式处理重点实验室,主要从事集群技术、操作系统、对象存储与数据库的研究。他一直在自由软件的开发上花费大量时间,并以此为乐。

本文由澳门新浦京娱乐场网站发布于澳门新浦京娱乐场网站,转载请注明出处:澳门新浦京娱乐场网站:Linux服务器集群系统,加