负载均衡算法

常用的6种负载均衡算法：

1、轮询法

将请求按顺序轮流地分配到后端服务器上，它均衡地对待后端的每一台服务器，而不关心服务器实际的连接数和当前的系统负载。

2、加权轮询法

不同的后端服务器可能机器的配置和当前系统的负载并不相同，因此它们的抗压能力也不相同。

给配置高、负载低的机器配置更高的权重，让其处理更多的请；而配置低、负载高的机器，给其分配较低的权重，降低其系统负载，加权轮询能很好地处理这一问题，并将请求顺序且按照权重分配到后端。

3、随机法

通过系统的随机算法，根据后端服务器的列表大小值来随机选取其中的一台服务器进行访问。由概率统计理论可以得知，随着客户端调用服务端的次数增多，其实际效果越来越接近于平均分配调用量到后端的每一台服务器，也就是轮询的结果。

4、加权随机法

与加权轮询法一样，加权随机法也根据后端机器的配置，系统的负载分配不同的权重。不同的是，它是按照权重随机请求后端服务器，而非顺序。

5、源IP地址哈希法

源IP地址哈希的思想是根据获取客户端的IP地址，通过哈希函数计算得到的一个数值，用该数值对服务器列表的大小进行取模运算，得到的结果便是客服端要访问服务器的序号。采用源地址哈希法进行负载均衡，同一IP地址的客户端，当后端服务器列表不变时，它每次都会映射到同一台后端服务器进行访问(若后端服务器列表改变,需要一致性哈希算法来优化,见下文)。

6、最小连接数法

最小连接数算法比较灵活和智能，由于后端服务器的配置不尽相同，对于请求的处理有快有慢，它是根据后端服务器当前的连接情况，动态地选取其中当前积压连接数最少的一台服务器来处理当前的请求，尽可能地提高后端服务的利用效率，将负责合理地分流到每一台服务器。

一致性哈希(Consistent Hashing)

在上面的源地址hash算法中,存在以下的2个问题

当一台服务器宕机了或者新添加一台机器之后,这个时候hashCode % servers.size()需要重新计算hash值, 如果在缓存的环境中,所有的请求都会涌向数据库服务器,给数据库服务器带来巨大的压力,可能导致整个系统不可用,形成雪崩效应.
当新增了一台性能强的机器后,利用上述的hash算法无法让新增的性能强的服务器多承担压力.

基于上面的2个问题,提出了hash算法的改进,即Consistent Hashing算法.Consistent Hashing也是一种 hash 算法，简单的说，在移除 / 添加操作，它能够尽可能小的改变已存在 key 映射关系.

Consistent Hashing算法的原理是它将hash函数的值域组织成一个环形,整个空间按照顺时针的方式进行组织,将对应的服务器节点进行hash,将他们映射到hash环上,假设有四台机器node1-4,hash之后如图所示:

接下来使用相同的hash函数,计算出对应的key值和hash值,按照顺时针的方式,分布在node1和node2的key,访问时被定位在node2,分布在node2和node4的key被定位在node4上,以此类推.假设现在新增一个node5,假设hash之后在node2和node4之间,如图所示:

那么受影响的节点只有node2和node5,他们将会从新hash,而其他的key的映射将不会变化.

当然,上面描绘了一种很理想的情况,即各个节点在环上分布的十分均匀.正常情况下,当节点数量少的时候,节点分布并不均匀,这时需要引入虚拟节点机制.

部分转载自常见的一些负载均衡算法总结