常见几种负载均衡算法

轮询法

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

加权轮询

普通加权轮询

缺点是分配不均衡，有可能多个连续请求分配至统一服务器。

轮训所有节点，找到一个最大权重节点；
选中的节点权重-1；
直到减到0，恢复该节点原始权重，继续轮询；

这样的算法看起来简单，最终效果是：{a, a, a, a, a, b, c}，即前5次可能选中的都是a，这可能造成权重大的服务器造成过大压力的同时，小权重服务器还很闲。

平滑加权轮询

对普通加权轮询的改进。

概念解释，每个节点有三个权重变量，分别是：

(1) weight: 约定权重，即在配置文件或初始化时约定好的每个节点的权重。

(2) effectiveWeight: 有效权重，初始化为weight。

在通讯过程中发现节点异常，则-1；之后再次选取本节点，调用成功一次则+1，直达恢复到weight；此变量的作用主要是节点异常，降低其权重。

(3) currentWeight: 节点当前权重，初始化为0。

算法逻辑

(1) 轮询所有节点，计算当前状态下所有节点的effectiveWeight之和totalWeight；

(2) currentWeight = currentWeight + effectiveWeight; 选出所有节点中currentWeight中最大的一个节点作为选中节点；

(3) 选中节点的currentWeight = currentWeight - totalWeight；

基于以上算法，我们看一个例子：

这时有三个节点{a, b, c}，权重分别是{a=4, b=2, c=1}，共7次请求，初始currentWeight值为{0, 0, 0}，每次分配后的结果如下：

请求序号	请求前currentWeight值	选中节点	请求后currentWeight值
1	{c=1,b=2,a=4}	a	{c=1,b=2,a=-3}
2	{c=2,b=4,a=1}	b	{c=2,b=-3,a=1}
3	{c=3,b=-1,a=5}	a	{c=3,b=-1,a=-2}
4	{c=4,b=1,a=2}	c	{c=-3,b=1,a=2}
5	{c=-2,b=3,a=6}	a	{c=-2,b=3,a=-1}
6	{c=-1,b=5,a=3}	b	{c=-1,b=-2,a=3}
7	{c=0,b=0,a=7}	a	{c=0,b=0,a=0}

观察到七次调用选中的节点顺序为{a, b, a, c, a, b, a}，a节点选中4次，b节点选中2次，c节点选中1次，算法保持了currentWeight值从初始值{c=0,b=0,a=0}到7次调用后又回到{c=0,b=0,a=0}。

随机法

加权随机法

源地址哈希法

nginx负载均衡

轮询（默认）

weight

upstream bakend {  
  server 192.168.0.1 weight=4;  
  server 192.168.0.2 weight=1;  
}

ip_hash

同一ip分配至统一服务器，可以解决session问题

upstream bakend {  
  ip_hash;  
  server 192.168.0.1:80;  
  server 192.168.0.2:8080;  
}

fair

服务端响应时间短的优先分配

upstream backend {  
  server server1;  
  server server2;  
  fair;  
}

url_hash

对url进行hash

健康检查

负载均衡时又是需要检查服务器状态。

AIRobot quick note

负载均衡的几种算法