负载均衡算法

前言：本文记录常见的负载均衡算法。

1. Power of 2 random choice

P2C算法是一种工业中运用较多的负载均衡算法，它的原理很简单，它有两条基本定律：

• 若请求IP为空，P2C均衡器将随机选择两个代理主机节点，最后选择其中负载量较小的节点；
• 若请求IP不为空，P2C均衡器通过对IP地址以及对IP地址加盐进行CRC32哈希计算，则会得到两个32bit的值，将其对主机数量进行取模，即CRC32(IP) % len(hosts) 、CRC32(IP + salt) % len(hosts)， 最后选择其中负载量较小的节点；

2. Least Load

Least Load也就是最小负载算法，也是非常经典的负载均衡算法，在最小负载算法中，负载均衡器将请求定向到负载最小的目标主机中；

对于最小负载算法而言，如果把所有主机的负载值动态存入动态数组中，寻找负载最小节点的时间复杂度为O(N)，如果把主机的负载值维护成一个红黑树，那么寻找负载最小节点的时间复杂度为O(logN)，我们这里利用的数据结构叫做 斐波那契堆 ，寻找负载最小节点的时间复杂度为O(1)，感兴趣的小伙伴可以看看斐波那契堆的原理！

3. 传统一致性哈希

一致性哈希算法是一种特殊的哈希算法，当哈希表改变大小时，平均只需要重新映射n/m个键值，其中n为哈希表键值的数量，m为哈希表槽的数量。

在一致性哈希负载均衡器中，一个集群由多个代理节点所组成，通过CRC32散列算法对代理主机节点的UUID或节点的IP地址进行计算，即**CRC32(IP)或CRC32(UUID)，**则会得到一组散列值，而这组散列值连成的环，称为哈希环。

当收到请求时，负载均衡器将请求的IP进行CRC32哈希计算进而得到一个散列值。如图所示，将代理主机节点和请求IP的哈希值映射到哈希环后，沿着哈希环顺时针方向查找，找到的第一个节点，即请求所被调度的代理节点。

通过对代理节点的哈希值按升序建立动态数组，即可在O(logN)时间复杂度的情况下通过二分搜索可以找到被调度的代理节点。

当代理节点数量越少时，越容易出现节点的哈希值在哈希环上分布不均匀的情况。而通过引入虚拟节点的方式可以解决一致性哈希算法负载不平衡的问题 。通过对代理主机的IP外加虚拟序号的形式作哈希计算。

如192.168.1.1的虚拟节点可能是192.168.1.1#1、192.168.1.1#2、192.168.1.1#3，我们需要把虚拟节点计算得到的CRC32值也映射到哈希环中。

下图的三个节点H1、H2、H3均匀两个虚拟节点：

4. 有界负载一致性哈希

Google提出的有界负载一致性哈希通过限制节点负载上限的方式解决了工作节点负载过高的问题。当节点负载过高时，有界负载一致性哈希算法通过转移热点的方式来提升集群整体的负载平衡性。

在有界负载一致性哈希算法中R 表示代理主机节点的总负载量，Tw 表示代理主机节点的数量，L 表示当前所有代理主机的平均负载量，即：

α 表示代理主机所能执行的额外上限系数，M 则表示每个代理主机所能承受的最大负载量，即：

• 当α趋于0时，有界负载一致性哈希算法将会退化成最小负载算法
• 当α趋于正无穷时，算法会退化成普通性质的一致性哈希算法。

当请求IP的哈希值所调度的代理主机节点超过所能承受的最大负载量M 时，负载均衡器则会按顺时针选择第一个负载量小于M 值的代理主机节点：