返回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负载均衡技术,它们主要解决系统的可伸缩性和透明性难点,怎么样通过负载调度器将请求高效地分发
到不一样的服务器执行,使得由多台独立总计机组成的集群系统成为一台虚拟服务器;客户端应用程序与集群系统互相时,就好像与一台高质量的服务器交互一样。

  假设有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-罗布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)


 

上边,大家先介绍那多种连接调度算法的劳作规律和算法流程,会在后来的稿子中描述怎么用它们。

回页首

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

2.1. 轮叫调度

根本中的连接调度算法

  轮询算法并没有考虑每台服务器的拍卖能力,实际中或然并不是那种景色。由于每台服务器的安排、安装的政工使用等不一样,其拍卖能力会不雷同。所以,加权轮询算法的法则就是:依照服务器的不比处理能力,给逐个服务器分配区其余权值,使其可以承受相应权值数的服务请求。

轮叫调度(Round 罗布in
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-Robin
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,首个权重大于等于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,以下简称为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;
}

澳门金沙国际 2
图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文件的乞请被发到同一台服务器。所以说,有大概存在那样情形,有些服务器已经超(英文名:jīng chāo)负荷运转,而其它服务器基本是束之高阁着。同时,有些服务器
已经忙但是来,有不长的请求队列,还频频地选取新的哀求。反过来说,那会招致客户长日子的守候,觉得系统的劳务品质差。

  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 %d\n”,
    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 configuration\n”);
  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:%d\n”,
    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.%u\n”,
    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)的元老和严重性开发人员。他脚下做事于国家互相与分布式处理重大实验室,首要从事集群技术、操作系统、对象存储与数据库的商讨。他间接在自由软件的花费上开支多量岁月,并以此为乐。

相关文章