利用负载均衡之LVS(五):加权调解算法的原理

加权调节算法是风流浪漫种很常见的调治算法。借使唯有七个后端,调治的次第相当的轻巧,不过假使后端多于2个,只怕就不像想象中那么的相继举办调整。

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

返回LVS种类小说:http://www.cnblogs.com/f-ck-need-u/p/7576137.html

 

故此,本文揭秘加权调解算法到底是怎么举办调解的。

  依照该算法完结的代码如下:

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。

  更相同的,当current_weight变为x之后,权重为x的服务器,在current_weight接下来的变迁历程中,每一遍都会被选中,因而,拥有x权重的服务器,会在类别中现身x/gcd次。所以,每一种服务器在结果连串中冒出的次数,是与其权重成正比的,那正是顺应加权轮询算法的渴求了。

 

  b:current_weight,服务器如今的权重。一最初为0,之后会动态调节。

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。

倘让你不想从算法公式里找规律,那么看下边。

豆蔻梢头:轮询算法(Round-罗布in)

  遍历完全部服务器之后,假若该服务器的current_weight是最大的,就选用那一个服务器管理这次乞求。最终把该服务器的current_weight减去total。

  初步时,index为-1,curweight为0,然后依次调用lb_wrr__getwrr函数,获得此次选拔的劳务器索引index。

  在介绍加权轮询算法(WeightedRound-罗布in)从前,首先介绍一下轮询算法(Round-罗布in)。

  该算法的规律如下:

  c:每经过7个诉求后,a、b、c的current_weight又重临开头值{0, 0,0},由此上述流程是继续不停循环的。

  算法的主旨绪想体未来lb_wrr__getwrr函数中。以例子表明更好通晓一些:对于服务器数组{a(1), b(2), c(4)}来讲,gcd为1,maxweight为4。

  具体在加权轮询算法中,当健检算法检测出某服务器的景色产生了转移,譬如从UP到DOWN,或然反之时,就能更新权重,重新总计结果类别。

  上边的代码中,算法的骨干部分便是wrr和lb_wrr__getwrr函数。在wrr函数中,首先总括有所服务器权重的最大合同数gcd,权重最大值max,以至权重之和sum。

1:普通加权轮询算法

三:健检

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

  

  上面介绍二种加权轮询算法:

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

 

  每种服务器都有多少个权重变量:

  轮询算法并不曾虚构每台服务器的处理本领,实际中也许实际不是这种境况。由于每台服务器的安排、安装的政工应用等不等,其管理本事会不等同。所以,加权轮询算法的原理便是:依据服务器的两样管理工科夫,给种种服务器分配分化的权值,使其能够担当相应权值数的劳务诉求。

 

  经过7(1+2+4卡塔 尔(阿拉伯语:قطر‎次调用之后,各类服务器被选中的次数刚巧是其权重值。上边程序的运作结果如下:

 

  算法的帮助和益处是其简洁性,它无需记下当前有所连接的情况,所以它是生机勃勃种无状态调解。

  在轮询服务器数组时,若是达到了数组末尾,则再次从头起初寻找,何况减小current_weight的值:current_weight -= gcd(S)。如果current_weight等于0,则将其重新复苏设置为max(S)。

  根据上述配置,Nginx每收到7个顾客端的呼吁,会把里面包车型大巴1个转载给后端a,把里面包车型客车2个转载给后端b,把内部的4个转载给后端c。

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

  第1次调用该函数时,i(index)为-1,cw(current_weight)为0,步向循环后,i首先被置为0,因而cw被置为maxweight。从i起先轮询服务器数组ss,第三个权重大于等于cw的服务器是c,因而,i被置为2,并赶回其值。

 

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

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

  该算法的落到实处代码如下:

  每一次当呼吁到来,接纳服务器时,会遍历数组中兼有服务器。对于每个服务器,让它的current_weight扩充它的weight;相同的时候丰富全数服务器的weight,并保留为total。

二:加权轮询算法(WeightedRound-罗布in)

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

         假使有新的乞请到来,第8次调用该函数时,i为2,cw为1。进入循环后,i首先被置为0,cw被置为cw-gcd,相当于0,因而cw被重新设置为maxweight。这种意况就跟首次调用该函数时相近了。由此,7次是二个巡回,7次以往,重复以前的历程。

参考:

  b:7个诉求中,a、b、c被增选的顺序为a, b,a, c, a, b, a,遍布均匀,权首要的后端a未有被连接选取。

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

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

图片 2

  轮询算法借使全体服务器的管理质量都无差异,不爱惜每台服务器的当前连接数和响应速度。当倡议服务间距时间变化非常的大时,轮询算法轻便招致服务器间的负荷不平衡。所以此种均衡算法切合于服务器组中的全体服务器都有相似的软硬件配置并且平均服务乞请相对均衡的气象。

 

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

本文由2020欧洲杯官方投注-2020欧洲杯官方投注网址发布于win7,转载请注明出处:利用负载均衡之LVS(五):加权调解算法的原理

相关阅读