负载均衡算法

一、算法扩展----哈希算法

1.基本概念

哈希算法也叫摘要算法，是一种用于加密的算法，其工作原理是对任意一组输入总能得到一个长度固定的计算结果，即将任意数据映射到具体数值。

2.特点

对于相同输入，hash后结果一定相同 ；对于不同输入，hash后结果大概率不同。

3、哈希碰撞（冲突）

即两个不同的输入，经过计算后得到了相同的结果。产生hash碰撞的原因：由于hash算法输出的字节长度是固定的，而输入的长度确实无限的，用无限的输入映射有限的输出，就会产生碰撞。

二、负载均衡算法

1、轮询法

将请求按顺序轮流地分配到每个节点上，不关心每个节点实际的连接数和当前的系统负载。

优点：简单高效，易于水平扩展，每个节点满足字面意义上的均衡；

缺点：没有考虑机器的性能问题，根据木桶最短木板理论，集群性能瓶颈更多的会受性能差的服务器影响。

2.随机法

将请求随机分配到各个节点。由概率统计理论得知，随着客户端调用服务端的次数增多，其实际效果越来越接近于平均分配，也就是轮询的结果。

优缺点和轮询相似。

3.加权轮询法

不同的后端服务器可能机器的配置和当前系统的负载并不相同，因此它们的抗压能力也不相同。给配置高、负载低的机器配置更高的权重，让其处理更多的请；而配置低、负载高的机器，给其分配较低的权重，降低其系统负载，加权轮询能很好地处理这一问题，并将请求顺序且按照权重分配到后端。

加权轮询算法要生成一个服务器序列，该序列中包含n个服务器。n是所有服务器的权重之和。在该序列中，每个服务器的出现的次数，等于其权重值。并且，生成的序列中，服务器的分布应该尽可能的均匀。比如序列{a, a, a, a, a, b, c}中，前五个请求都会分配给服务器a，这就是一种不均匀的分配方法，更好的序列应该是：{a, a, b, a, c, a, a}。

优点：可以将不同机器的性能问题纳入到考量范围，集群性能最优最大化；

缺点：生产环境复杂多变，服务器抗压能力也无法精确估算，静态算法导致无法实时动态调整节点权重，只能粗糙优化。

4.加权随机法

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

5.源地址哈希法（取模算法）

源地址哈希的思想是根据客户端的IP地址，通过哈希函数计算得到一个数值，用该数值对服务器节点数进行取模，得到的结果便是要访问节点序号。采用源地址哈希法进行负载均衡，同一IP地址的客户端，当后端服务器列表不变时，它每次都会落到到同一台服务器进行访问。

优点：相同的IP每次落在同一个节点，可以人为干预客户端请求方向，例如灰度发布；

缺点：如果某个节点出现故障，会导致这个节点上的客户端无法使用，无法保证高可用。当某一用户成为热点用户，那么会有巨大的流量涌向这个节点，导致冷热分布不均衡，无法有效利用起集群的性能。所以当热点事件出现时，一般会将源地址哈希法切换成轮询法。

 6.一致性哈希算法

一致性哈希算法主要应用在分布式缓存系统中，在增加或者删除服务器节点时，能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系，也就是系统中的大多数历史缓存的存储服务器节点可以不变，解决了普通 hash 算法带来的动态伸缩性问题。

虚拟节点：
一致性哈希通过引入虚拟节点解决了这个问题，每个实际节点映射多个虚拟节点，数据按照规则找到虚拟节点后，再储存到映射的实际节点上；因为虚拟节点可以在 hash 环上均匀分布，这意味着当一个真实节点失效退出后，它原来所承载的压力将会均匀地分散到其他节点上去，解决缓存雪崩问题。

哈希偏斜