本文重点描述Maglev一致性哈希算法，并提出使Maglev一致性哈希算法支持带权重候选节点的改进方式， 以及描述了一致性哈希下的动态负载均衡策略，并给出开源C++实现代码库。
一致性哈希
一致性哈希是一种将属于无限集的key稳定地映射到属于有限集的候选节点上的算法，它需要满足：
- 稳定：候选节点集合不变时，一个固定的key，会稳定不变地映射到某一个候选节点上；
- 最小扰动：当增加或减少候选节点时，只有少部分key需要重新映射，大部分key的映射结果不变；
- 均衡：不同key应该均匀地分散到各个候选节点上，即一个key映射到每一个候选节点上的概率是相等的。
常见一致性哈希算法
环形哈希，也叫割环法，经典的一致性哈希算法，作者Karger等人于1997年提出一致性哈希算法的概念， 然后提出了这个一致性哈希算法。 更新和查询时间复杂度都是O(log(n))，空间复杂度O(n)， 但是通常均衡性不好，需要加入较多虚拟节点，也就加倍了时间和空间复杂度。
Jump Consistent Hash。极简的一致性哈希算法，不到十行代码。 查询时间复杂度是O(log(n))，不需要更新操作，也不需要额外存储空间。 但是不能随机增删候选节点，只能在有序候选节点队列的尾部增删节点，实用性不强。
Maglev一致性哈希算法。 查询时间复杂度O(1)，更新时间复杂度O(m)，空间复杂度O(m)，m通常为至少比n大10倍以上的一个素数常量。 较为实用，效果较好，下面重点介绍。
Maglev一致性哈希算法描述
- 选取哈希槽长度，素数M，生成空哈希槽数组；
- 将候选节点列表排序；
- 对每一个候选节点哈希得到两个随机数A、B(模M-1再加1保证非0或M的倍数)，然后得到一个从0到M-1的排列：X[k] = (A + k*B)%M, k=0,1,…,M-1；
- 排列中每一个数字代表一个槽位，轮询每一个候选节点的排列，从左到右选择排列中的第一个空槽位填充进去，直到哈希槽填充完整为止；
- 对一个输入key，通过 key%M 映射到哈希槽中对应的候选节点。（这里的key通常需要哈希一下得到一个大随机数）
优缺点：
- 优点：分片均匀，均衡性好，查询速度快O(1)
- 缺点：增删节点后更新较慢O(n)，并且没有完全实现最小扰动。
一致性哈希支持带权重候选节点
通用做法：增加虚拟节点
通常一致性哈希算法都是不支持带权重候选节点的，也就是一个key映射到每一个候选节点的概率是相等的。 因此，想要实现带权重的一致性哈希的一个普遍思路是增加虚拟节点。将一个实际的候选节点拆成多个虚拟节点， 拆成的虚拟节点的多少，即代表了这个实际候选节点的权重的大小。
Maglev一致性哈希算法支持带权重候选节点的特殊做法：按权重正比概率阈值填充哈希槽位。
通常，增加虚拟节点的做法相当于增加了候选节点数n，如果时间空间复杂度与n有关，那么会相应增加复杂度。 其次，如果虚拟节点数增加的少，那么实际的权重比例会比较粗糙，即精度不够。
Maglev算法的查询时间复杂度与n无关，是O(1)，所以增加虚拟节点法不会影响Maglev的查询速度， 但是由于Maglev算法需要选取一个比候选节点数大很多的大素数M，且这个M关系到更新的时间复杂度和占用的空间复杂度， 因此采用增加虚拟节点法也会增加一些消耗。
观察Maglev算法哈希槽的填充过程可知，该算法是轮训每一个候选节点，让每一个候选节点占有一个哈希槽后才轮到下一个候选节点。 因此可以试想，只要让轮训到当前候选节点时，不一定完全占有一个候选节点，而是设定一个与该节点的权重成正比的概率阈值， 达到这个阈值后才占有一个哈希槽。这个概率阈值可以是：当前节点的权重除以所有节点的权重的最大值。 可以看出，无权重的情况，也就相当于每一个候选节点的权重都相等，因此对应的概率阈值也都相等，都是1。 另外，为了保证一致性哈希算法的稳定性，这里的概率生成要用稳定的伪随机概率，每一个候选节点用自己的固定信息， 比如节点ID，作为一个伪随机序列的种子，用这个伪随机序列称重的概率与对应的概率阈值相比较，来判断该节点在这一次轮训中要不要占有一个哈希槽位。
一致性哈希下的动态负载均衡
由开头对一致性哈希算法的描述中可以，输入的key是属于无限集的，是无法提前预知的，无法对其做任何分布性的要求。 因此，极有可能，输入的key就是极其不均衡的，而纯粹的一致性哈希又是要求结果必须是稳定的，所以不均衡的输入集， 最终会造成不均衡的映射结果。比如常见的热key问题，纯一致性哈希是无法解决的。
因此，为了在未知的不确定的任意的输入集上都保持良好的均衡性，需要动态的调整映射策略，需要统计感知每一个候选节点当前的负载情况， 如果负载过高，则应该将当前key用某种算法重新映射到另外一个节点上，而这个重新映射的算法最好也是稳定的。
对于Maglev算法来说，笔者提出一个简单的重新映射算法：(key + (key % C + 1) * retry_cnt) % M。
其中C是某一个常数，而retry_cnt是重新映射次数，可见当retry_cnt为0时，即首次映射时，该算法就退化到了Maglev算法描述第5步描述的
key % M的算法。
除了重新映射即重新选取候选节点外，对于动态负载均衡来说，另一个重点是，如何描述节点负载以及如何判断是否负载过高。
对于候选节点无权重的情况来说，任意一个候选节点每接收一个key，就增加这个key对应的负载值，如果所有的key对应的负载值都一样，即可记为1。 对于候选节点有权重的情况来说，不同的候选节点接收同一个key后对自身的负载影响是不同，需要乘以一个以自身权重为分母的负载归一化因子， 比如可以是：所有候选节点的权重的平均值除以当前节点的权重。这样，每一个候选节点接收一个key后，需要增加自身的负载归一化因子乘上这个key对应的负载值后， 这么多的负载增量。
有了每一个key对每一个候选节点的负载增量定量描述后，就可以计算所有候选节点的平均负载值，然后设定一个阈值，负载大于平均负载某一个倍数的节点， 即可认为是过载节点。例如，这个倍数可选1.2 ~ 1.5。
特别的，在RPC场景下，候选节点就相当于是远程服务器，每处理一个key就相当于一次远程服务请求。 因此，请求量、错误量、延时等信息也可用来描述候选节点的负载。错误数较多，延时过高时，即可认为当前节点负载过高。 但是为了避免全局的一致性哈希结果被大量破坏，可以对候选节点的每一项负载情况进行排名，然后限制只有该项负载排名很高的几个节点才能在这一负载项上被判定为过载。
最后，负载是动态变化的，负载的统计记录信息需要实时更新，通常需要一个滑动窗口，每隔固定几秒钟，就生成一个新的统计单元，并滑动滑动窗口， 丢弃窗口中最老的统计单元的数据，加入最新的统计单元的数据。
开源实现
以上所描述的Maglev一致性哈希算法，以及在此一致性哈希基础上的动态负载均衡策略，笔者已有一个完整的C++开源实现。 代码详见GitHub：cpp-maglev