负载均衡之加权轮询算法,ip_vs实现分析

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

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

本文书档案的Copyleft归yfydz全部,使用GPL公布,能够肆意拷贝,转发,转载时请保持文书档案的完整性,严禁止使用于别的商业用途。
msn: yfydz_no1@hotmail.com
来源:http://yfydz.cublog.cn

级别: 初级

 

  

  1. 户均调整算法

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

加权调整算法是一种很常见的调节算法。若是独有五个后端,调解的各个很轻便,不过如果后端多于2个,大概就不像想象中那么的逐一进行调解。

一:轮询算法(Round-Robin)

5.1 算法表明

2002 年 5 月 20 日

于是,本文揭秘加权调整算法到底是怎么进行调解的。

  轮询算法是最简易的一种负载均衡算法。它的准绳是把来自客户的哀告轮流分配给个中的服务器:从服务器1起来,直到服务器N,然后再次先导循环。

平衡调节算法是IPVS落成户均功用的辩驳精髓,别的各样东西都只算是程序工夫,所以优先介绍。IPVS扶助8种静态平均算法,以下文字直接拷贝自IPVS网址:

正文首要描述了LVS集群的IP负载均衡软件IPVS在根本中完成的种种连接调整算法。针对央浼的服务时间变化异常的大,给出三个动态反馈负载均衡算法,它结合内核中的加权连接调整算法,根据动态反馈回来的载荷音信来调动服务器的权值,来更是制止服务器间的载重不平衡。

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

前言

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负载均衡技艺,它们主要消除系统的可伸缩性和透明性难点,怎么样通过负载调解器将呼吁高效地分发 到分歧的服务器实施,使得由多台独立Computer组成的集群系统成为一台虚构服务器;顾客端应用程序与集群系统互相时,就好像与一台高品质的服务器交互同样。

  尽管有N台服务器:S = {S1, S2, …, Sn},一个指令变量i表示上一回选取的服务器ID。变量i被早先化为N-1。该算法的伪代码如下:

IPVS在基础中的负载均衡调整是以三番两次为粒度的。在HTTP契约(非长久)中,每一个对象从WEB服务器上得到都亟需建构贰个TCP连接,同一客户的两样央求会被调解到差别的服务器上,所以这种细粒度的调治在早晚水准上可防止止单个客商访谈的突发性引起服务器间的载荷不平衡。

本 文将首要陈说在负载调整器上的载荷调整计策和算法,如何将恳求流动调查解到各台服务器,使得各台服务器尽恐怕地保持负载均衡。文章主要由多个部分构成。第一部 分描述IP负载均衡软件IPVS在基本中所达成的各样连接调节算法;第二片段交给二个动态反馈负载均衡算法(Dynamic-feedback load balancing),它结合内核中的加权连接调整算法,依据动态反馈回来的载荷新闻来调治服务器的权值,来进一步防止服务器间的负荷不平衡。

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数据包会被调解到平等台服务 器。

  轮询算法借使全部服务器的管理性能都一样,不关怀每台服务器的当前连接数和响应速度。当呼吁服务间距时间变化相当大时,轮询算法轻松形成服务器间的负荷不平衡。所以此种均衡算法吻合于服务器组中的全数服务器都有雷同的软硬件配置并且平均服务乞求绝对平均的场合。

轮叫调节(Round-Robin Scheduling) 
加权轮叫调节(Weighted Round-罗布in 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)


 

上面,大家先介绍那七种连接调整算法的行事原理和算法流程,会在后头的小说中汇报怎么用它们。



回页首

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

2.1. 轮叫调节

根本中的连接调解算法

  轮询算法并不曾设想每台服务器的拍卖技巧,实际中大概并非这种状态。由于每台服务器的计划、安装的作业使用等不等,其管理本领会分化等。所以,加权轮询算法的原理便是:依照服务器的不等处理技能,给各类服务器分配不相同的权值,使其能够承受相应权值数的劳务诉求。

轮叫调解(Round Robin Scheduling)算法便是以轮叫的情势挨个将呼吁调解不一样的服务器,即每趟调解执行i = (i 1) mod n,并选出第i台服务器。算法的帮助和益处是其简洁性,它没有供给记下当前享有连接的场馆,所以它是一种无状态调整。

IPVS 在基本中的负载均衡调治是以延续为粒度的。在HTTP协议(非长久)中,每种对象从WEB服务器上获得都必要建构三个TCP连接,同一客户的差别必要会被 调整到分化的服务器上,所以这种细粒度的调治在一定水平上得以制止单个客户访谈的神蹟引起服务器间的负荷不平衡。

 

在系统落到实处时,大家引入了一个杰出条件,当服务器的权值为零时,表示该服务器不可用而不被调解。那样做的指标是将服务器切出服务(如屏蔽服务器故障和种类保险),相同的时候与任何加权算法保持一致。所以,算法要作相应的更换,它的算法流程如下:

在根本中的连接调治算法上,IPVS已完结了以下多样调整算法:

  首先看三个轻易易行的Nginx负载均衡配置。

轮叫调节算法流程 
设若有一组服务器S = {S0, S1, …, Sn-1},三个提示变量i表示上一回采纳的
服务器,W(Si)表示服务器Si的权值。变量i被初叶化为n-1,个中n > 0。

  • 轮叫调节(Round-罗布in Scheduling)
  • 加权轮叫调治(Weighted Round-罗布in 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)
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;  

上面,大家先介绍那八种连接调节算法的干活规律和算法流程,会在后头的小说中描述怎么用它们。

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

轮叫调节算法假如全体服务器管理质量均一致,不管服务器的日前连接数和响应速度。该算法相对轻巧,不适用于劳动器组中拍卖品质不一的场地,并且当呼吁服务时间更动极大时,轮叫调解算法轻巧导致服务器间的负载不平衡。

2.1. 轮叫调解

 

即便Round-罗布in DNS方法也是以轮叫调治的方法将二个域名深入分析到八个IP地址,但轮叫DNS方法的调解粒度是依靠各类域名服务器的,域名服务器对域名解析的缓存会妨碍轮叫解析域名生效,那会促成服务器间负载的要紧不平衡。这里,IPVS轮叫调治算法的粒度是基于种种连接的,同一顾客的两样连接都会被调整到分化的服务器上,所以这种细粒度的轮叫调治要比DNS的轮叫调解优越比比较多。

轮叫调治(Round 罗布in Scheduling)算法便是以轮叫的点子挨个将呼吁调整不一样的服务器,即每趟调解推行i = (i 1) mod n,并选出第i台服务器。算法的独到之处是其简洁性,它无需记下当前怀有连接的气象,所以它是一种无状态调节。

  加权轮询算法的结果,正是要生成五个服务器种类。每当有必要到来时,就相继从该类别中收取下三个服务器用于拍卖该央求。比方对准地点的例证,加权轮询算法会生成种类{c, c, b, c, a, b, c}。那样,每收到7个客户端的乞求,会把里面包车型大巴1个转发给后端a,把内部的2个转载给后端b,把内部的4个转载给后端c。收到的第8个央求,重新从该系列的尾部开端轮询。

2.2. 加权轮叫调治

在系统得以落成时,大家引入了七个附加条件,当服务器的权值为零时,表示该服务器不可用而不被调解。那样做的指标是将服务器切出服务(如屏蔽服务器故障和系统爱护),同一时间与其余加权算法保持一致。所以,算法要作相应的改造,它的算法流程如下:

  同理可得,加权轮询算法要生成贰个服务器体系,该种类中蕴藏n个服务器。n是全部服务器的权重之和。在该系列中,各个服务器的产出的次数,等于其权重值。况兼,生成的种类中,服务器的布满应该尽量的动态平衡。例如体系{a, a, a, a, a, b, c}中,前多个央求都会分配给服务器a,那正是一种不均匀的分配格局,越来越好的行列应该是:{a, a, b, a, c, a, a}。

加权轮叫调节(Weighted Round-罗布in Scheduling)算法能够化解服务器间品质不一的动静,它用相应的权值表示服务器的处理质量,服务器的缺省权值为1。若是服务器A的权值为1,B的权值为2,则象克服务器B的管理品质是A的两倍。加权轮叫调治算法是按权值的轻重和轮叫格局分配央浼到各服务器。权值高的服务器先吸取的延续,权值高的服务器比权值低的服务器管理更加的多的连天,一样权值的服务器管理一样数量的连接数。加权轮叫调整算法流程如下:

轮叫调解算法流程

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

加权轮叫调整算法流程 
若果有一组服务器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;

 

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-罗布in DNS方法也是以轮叫调治的点子将四个域名分析到多个IP地址,但轮叫DNS方法的调治粒度是基于每种域名服务器的,域名服务器对域名分析的缓存会妨碍轮 叫剖析域名生效,这会招致服务器间负载的不得了不平衡。这里,IPVS轮叫调治算法的粒度是基于种种连接的,同一客商的不及连接都会被调整到差别的服务器 上,所以这种细粒度的轮叫调解要比DNS的轮叫调解优越比很多。

         这种算法的法规是:在劳务器数组S中,首先总括有所服务器权重的最大值max(S),以及全体服务器权重的最大公约数gcd(S)。

从上边包车型地铁算法流程中,大家能够见到当服务器的权值为零时,该服务器不被被调节;当全体服务器的权值为零,即对于大肆i有W(Si)=0,则并未有别的服务器可用,算法再次回到NULL,全体的新连接都会被放任。加权轮叫调节也不供给记下当前有着连接的情形,所以它也是一种无状态调整。

2.2. 加权轮叫调治

         index表示此次央求到来时,选用的服务器的目录,初叶值为-1;current_weight表示方今调节的权值,早先值为max(S)。

2.3. 眇小连接调解

加 权轮叫调整(Weighted Round-罗布in 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,第4个权重大于等于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[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,以下简单的称呼为LBLCRAV4)算法也是针对性对象IP地址的负载均衡,这几天任重先生而道远用以Cache集群系统。它与LBLC算法的不相同之处是它要尊崇从三个指标IP地址到一组服务器的照耀,而LBLC算法维护从二个目的IP地址到一台服务器的炫丽。对于二个“火热”站点的劳动央浼,一台Cache 服务器大概会忙然而来管理那些央求。那时,LBLC调整算法会从具备的Cache服务器中按“最小连接”原则选出一台Cache服务器,映射该“火热”站点到这台Cache服务器,非常的慢那台Cache服务器也会超载,就能另行上述进程选出新的Cache服务器。那样,恐怕会招致该“火爆”站点的影象会出现在全部的Cache服务器上,收缩了Cache服务器的行使频率。LBLC中华V调整算法将“紧俏”站点映射到一组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次未来,重复在此以前的进度。

LBLC途睿欧算法先依照央浼的靶子IP地址搜索该指标IP地址对应的劳动器组;按“最小连接”原则从该服务器组中选出一台服务器,若服务器并未有超载,将央求发送到该服务器;若服务器超载;则按“最小连接”原则从全部集群中选出一台服务器,将该服务器进入到服务器组中,将呼吁发送到该服务器。同有的时候候,当该服务器组有一段时间没有被修改,将最忙的服务器从服务器组中去除,以减低复制的等级次序。LBLC揽胜极光调节算法的流水线如下:

别的,对关联变量 ServerNode[dest_ip]要扩充周期性的废物回收(Garbage Collection),将过期的目的IP地址到服务器涉及项进行回收。过期的涉及项是指什么当昨日子(达成时利用系统石英钟节拍数jiffies)减去最近使用时间超越设定过期时光的涉嫌项,系统缺省的设定过期时间为24时辰。

 

LBLCEvoque调节算法流程 
如若有一组服务器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,以下简单称谓为LBLCWrangler)算法也是指向对象IP地址的载重均衡,前段时间重要用来Cache集群系统。它与LBLC算法的分歧之处是它要 维护从三个目的IP地址到一组服务器的炫丽,而LBLC算法维护从三个对象IP地址到一台服务器的投射。对于贰个“抢手”站点的劳必须要,一台Cache 服务器恐怕会忙然而来管理那么些央求。那时,LBLC调解算法会从全数的Cache服务器中按“最小连接”原则选出一台Cache服务器,映射该“销路好”站 点到这台Cache服务器,相当慢那台Cache服务器也会超载,就能够再度上述进程选出新的Cache服务器。这样,恐怕会促成该“热销”站点的影象会出现在有着的Cache服务器上,收缩了Cache服务器的使用频率。LBLC揽胜极光调整算法将“火热”站点映射到一组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小时。

LBLC奥迪Q7算法先根据诉求的指标IP地址找寻该目的IP地址对应的劳务器组;按“最小连接”原则从该服务器组中选出一台服务器,若服务器并未有超载,将乞求发送到该服 务器;若服务器超载;则按“最小连接”原则从全方位集群中选出一台服务器,将该服务器进入到服务器组中,将呼吁发送到该服务器。同期,当该服务器组有一段时 间未有被修改,将最忙的服务器从服务器组中删去,以减低复制的水平。LBLC君越调节算法的流水生产线如下:

  针对种种current_weight,该算法正是要把服务器数组从头到尾扫描叁遍,将当中权重大于等于current_weight的持有服务器填充到结果系列中。扫描完二回服务器数组之后,将current_weight变为下二个值,再一回原原本本扫描服务器数组。

2.7. 对象地方散列调节

LBLCPRADO调治算法流程

  在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[]是一个有259个桶(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。

在XC60PAJERO算法中,那三个函数都很轻松:

动 态反馈负载均衡算法考虑服务器的实时负载和响应情状,不断调解服务器间管理需要的比例,来防止有个别服务器超载时还是收到大批量伸手,进而巩固全体类别的吞吐 率。图1出示了该算法的劳作情况,在负载调节器上运营Monitor Daemon进度,Monitor Daemon来监视和搜罗各类服务器的负荷信息。Monitor Daemon可依据多个负载新闻算出三个归纳负载值。Monitor Daemon将相继服务器的综合负载值和脚下放权力值算出一组新的权值,若新权值和这段时间权值的差值大于设定的阀值,Monitor Daemon将该服务器的权值设置到基本中的IPVS调整中,而在基础中三番两次调治通常选用加权轮叫调解算法恐怕加权最小连接调节算法。

 

static int ip_vs_rr_init_svc(struct ip_vs_service *svc)
{
// 其实Wrangler奥迪Q7算法也向来不什么专项使用调治数据,sched_data被伊始化为指标服务器链表头
 svc->sched_data = &svc->destinations;
 return 0;
}

图片 2
图1:动态反馈负载均衡算法的做事条件

  上述描述只怕不太直观,来看个例证。例如对准如此的布置:

static int ip_vs_rr_done_svc(struct ip_vs_service *svc)
{
// 空函数,因为对EscortKoleos没什么可自由的
 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. 大约连接调节

图片 3

 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-罗布in 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);

图片 4

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、MEMO奇骏Yi和 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也没查到有关论证……,等待后续调查了。

恒久调治函数,用在多连接公约管理少校子连接与主连接挂钩:

图片 5

 

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

图片 6

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

图片 7

 /*
  *    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-罗布in Scheduling)
  • 加权轮叫调解(Weighted Round-罗布in 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/

至于小编

图片 8

图片 9

章文嵩博士,开放源码及Linux内核的开采者,知名的Linux集群项目--LVS(Linux Virtual Server)的开山和主要开拓人士。他日前职业于国家相互与遍及式管理首要实验室,首要从事集群本领、操作系统、对象存款和储蓄与数据库的研商。他平素在自由软件的开采上海消防费多量时间,并以此为乐。

本文由星彩网app下载发布于星彩网app下载,转载请注明出处:负载均衡之加权轮询算法,ip_vs实现分析

TAG标签: 星彩网app下载
Ctrl+D 将本页面保存为书签,全面了解最新资讯,方便快捷。