vlambda博客
学习文章列表

随机分析的两个基础场景

考虑两个简单的随机场景

随机场景1：有200个球，将每个球随机放到2个桶里，各个桶里球的个数均匀吗？

随机场景2：有200个球，将每个球随机放到200个桶里，各个桶里球的个数均匀么？

通过一个简短的仿真程序，场景1中各个桶里球的个数在100个左右小范围波动，可以认为随机场景1是均匀的。而场景2中，每次仿真都会有38%的桶里一个球没有，有25%的桶里超过1个球，因此可以认为随机场景2是不均匀的。可以看到，随机在不同的场景下，均匀性特征并不一样。

负载均衡算法的考虑因素

评价一个负载均衡算法，需要考虑以下方面

均衡性：能够将负载请求均匀的分布到各个服务器上

一致性：当出现服务器的添加或删除时，服务中的请求受影响最小，能够快速进入稳定状态

响应性能：能够快速计算出任意一个请求对应的服务器

随机性：各个请求和对应的服务器不应该有明显的规律

素数取模

素数取模并不是一个一致性哈希算法，但是几乎所有的一致性哈希算法都跟素数取模有非常紧密的关系。素数取模指将每个负载请求输入到一个随机函数，将随机函数的输出值对素数取模，然后分配到各个服务器上。素数取模算法具有很好的均衡性和很高的请求相应性能。但是它的一致性特别差，当出现服务器节点添加或删除时，较大一部分请求都要受影响。

Hash Ring

Hash Ring将所有负载请求Hash后的空间视作一个环，将各个服务器也Hash到这个环上。进行负载均衡时，先将负载请求Hash到这个环上，然后选择顺时针移动时遇到的第一个服务器节点，作为响应节点。Hash Ring的原理可以参考下图

当添加服务器时，直接将该服务器Hash到环上即可，受影响的请求仅限于新添加服务器节点Hash在环上和相邻服务器对应的区域，因此Hash Ring具有很好的一致性。

如果每个服务器Hash到环上仅仅一次，由随机场景2可知，各个服务器节点在环上对应的区域是不均匀的。因此，此时的Hash Ring算法均衡性存在问题。通过随机场景1可知，通过将每个服务器节点Hash到环上多次，可以缓解Hash Ring算法的均衡性问题。如下的开源代码中，将每一个服务器Hash到环上120次，达到了较好的均衡性。

但是，将每个服务器Hash到环上多次，一方面需要更多的存储空间来存储这些数据，另一方面，在对请求进行负载均衡计算时，需要在环上这么多节点中寻找对应的服务器节点，请求响应性能较低。

Hash Ring开源实现参考：https://github.com/Doist/hash_ring

Highest Random Weight

Highest Random Weight（HRW）算法较为简单，给每个服务器节点分配一个随机函数，对每一个请求，将其输入到各个节点的随机函数中，取随机函数输出值最大的服务器作为请求的分配节点。

HRW算法具有很好的一致性和均衡性，但是缺点也很明显，随着节点个数增多，请求的相应性能会越来越低。

Jump Hash

Google在2014年发布了一个请求响应性能较高的一致性哈希算法，Jump Hash。Jump Hash核心思想是当新增服务器节点时，以一定的概率从各个服务器节点对应的请求中随机选择一些请求分配到新节点中。核心思想参考代码如下。其中，key为请求，num_bucket为服务器节点个数。

Jump Hash算法示意图如下所示

上面展示的Jump Hash算法运行效率较低，O(n)，n为服务器节点个数。考虑到伪代码中b值更新的概率较小，可以将b值不更新时循环对应的那些j进行合并，根据随机值直接计算该负载请求下一次被分走（b变化）时对应的新增桶ID，代码如下

Jump Hash算法理论上能够提供基于概率的绝对均衡。对于尾部服务器节点的添加删除，Jump Hash算法能够保证一致性。但是对于非尾部服务器节点的变化，需要一个额外的映射才能够保证一致性。Jump Hash算法的请求响应性能时间复杂度为O(lg n)，n为服务器节点个数。

Maglev

在现有的查找算法中，Hash Table的查找性能最高。因此，负载请求想达到更高的响应性能，Hash算法最为合适。Google在2016年公开了自身使用多年的基于Hash的一致性哈希算法—Maglev。目前，Maglev算法已经应用到除Google之外的其他OTT企业。

图 Maglev Lookup Table和Permutation Table示例

Maglev负载请求查找对应服务器节点的过程颇为简单，将负载请求Hash运算后对Lookup Table Size（质数）取模，取Lookup Table对应位置存储的服务器节点为分配给该请求的服务节点。因此Maglev算法具有较高的请求响应性能。

出于均衡性考虑，Maglev算法要求各个服务器节点在Lookup Table中出现的个数严格相等。由于同时需要考虑到一致性，所以Maglev算法中的Lookup Table需要由另一个Table—Permutation Table来生成。Maglev算法并没有很好的处理均衡性和一致性带来的矛盾，因此丧失了一定的一致性。如上图所示，当服务器B1删除后，Lookup Table位置6处的负载请求由服务器B0变为了B2。在实际使用时，LookupTable的size为服务器个数的3-5倍就能有不错的均衡性。

在构造Lookup Table时，由随机场景2可知，想要保证均衡性，可以使用大一点的Lookup Table Size（比如，参考Hash Ring，Lookup Table size是服务器节点个数的120倍），此时Lookup Table对应的服务器ID随机选择也能保证很好的均衡性，此时只需要保证Lookup Table的一致性，这样也是一种处理思路。

总结

以上各种一致性哈希算法的总结对比如下（n为服务器节点个数）

在挑选一致性Hash算法时，可以根据业务场景对不同一致性哈希算法的考虑因素关注重要程度，选择合适的一致性哈希算法。

扎到跟，捅破天，计算软件架构创新LAB期待优秀博士（含天才少年）加入。这里有AI、HPC、大数据等高价值业务场景供研究成果落地，也有芯片、操作系统、基础软件平台等各层核心技术。欢迎发送邮件至[email protected]咨询交流！