负载均衡之加权轮询算法【分分快三全天计划网

作者:电脑系统

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

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

2.1. 轮叫调度

 

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

 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));

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。

 

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

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

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

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;  

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

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

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

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。

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

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

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

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

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

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

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

 

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

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

2.8. 源地址散列调度

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

2.4. 加权最小连接调度

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

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

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

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

#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;
}

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

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

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

#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;
}

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

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

5.3 系统调度

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

  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;
   }

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

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

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

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

一:轮询算法(Round-Robin)

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

 

素数乘法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
 *

 

 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;
}

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

 /*
  * 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);

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

 

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

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

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

   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);

  

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

 

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()等函数);

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

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

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

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

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

   /*
    * 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;

 

2.2. 加权轮叫调度

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

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

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

/*
 * 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;

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

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

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

5.2 算法具体实现

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

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

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

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

 

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

2:平滑的加权轮询

  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));

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

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

1:普通加权轮询算法

/*
 *  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 */

 

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

  该算法的实现代码如下:

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;  

分分快三全天计划网站 2

 /*
  *    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;

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) 

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

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

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

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

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

 

轮叫调度(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)

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

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

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

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

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

 

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,
};

 

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;  

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

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

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

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;
 *

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

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

 

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

参考:

假设有一组服务器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)不为零

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

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

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

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

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

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

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

  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;
   }

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

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

  该算法的原理如下:

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

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

2.7. 目标地址散列调度

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

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

 

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

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

   /*
    * 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;

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

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

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

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

 

 /*
  *    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;
 }

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

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

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) 

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

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

5.1 算法说明

三:健康检查

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

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

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

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

2.3. 最小连接调度

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

rr算法结构定义:

 

  1. 均衡调度算法

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

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

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) 

 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;

 

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

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

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

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

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

 

 return dest;
}

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

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

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

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;
}

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

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

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

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

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

/*
 *  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;

 

 /*
  *    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;
 }

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

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

带复制的基于局部性最少链接调度(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集群系统的使用效率。

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

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为对集合进行调整的设定时间。

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

本文由分分快三计划发布,转载请注明来源

关键词: 分分快三计划 ipvs(lvs)