哪种一致性哈希算法才是解决分布式缓存问题的王者？

简介

一致性哈希是由Karger等人于1997年提出的一种特殊的哈希算法，目的是解决分布式缓存的问题，现在在分布式系统中有着广泛的应用。本文将对ketama、jump consistent hash、rendezvous hash和maglev hash四种算法进行对比分析。

• 平衡性

不同key通过算法映射后，可以比较均衡地分布到所有的后端节点上。

• 单调性

当有新的节点上线后，系统中原有的key要么还是映射到原来的节点上，要么映射到新加入的节点上，不会出现从一个老节点重新映射到另一个老节点。

• 稳定性

当服务发生扩缩容的时候，发生迁移的数据量尽可能少。

二、问题背景

假设我们有N个cache服务器节点，那如何将数据映射到这N个节点上呢，最简单的方法就是用数据计算出一个hash值，然后用hash值对N取模，如：hash(data) % N，这样只要计算出来的hash值比较均匀，那数据也就能比较均匀地映射到N个节点上了。但这带来的问题就是，如果发生扩缩容，节点的数量发生了变化，那很多数据的映射关系都会发生变化。显然这种方法虽然简单，但并不太能解决我们的需求。

经典的一致性哈希

经典的一致性哈希算法也就是我们常说的割环法 ，大家应该都比较熟悉。简单来说就是，我们把节点通过hash的方式，映射到一个范围是[0，2^32]的环上，同理，把数据也通过hash的方式映射到环上，然后按顺时针方向查找第一个hash值大于等于数据的hash值的节点，该节点即为数据所分配到的节点。而更好点的做法是带虚拟节点的方法，我们可以为每个物理节点分配若干个虚拟节点，然后把虚拟节点映射到hash环，分配给每个物理节点虚拟节点数量对应每个物理节点的权重，如下图1所示。这样还是按顺时针的方法查找数据所落到的虚拟节点，再看该虚拟节点是属于哪个物理节点就可以知道数据是分配给哪个物理节点了。

Ketama hash

Ketama hash的实现简单来说分成以下几步

1. 从配置文件中读取服务器节点列表,包括节点的地址内存,其中内存参数用来衡量一个节点的权重
2. 对每个节点按权重计算需要生成几个虚拟节点，基准是每个节点160个虚拟节点，每个节点会生成10.0.1.1:11211-1、10.0.1.1:11211-2到10.0.1.1:11211-40共40个字符串，并以此算出40个16字节的hash值(其中hash算法采用的md5)，每个hash值生成4个4字节的hash值，总共40*4=160个hash值，对应160个虚拟节点；
3. 把所有的hash值及对应的节点地址存到一个continuum存组中按hash值排序方便后续二分查找计算数据所属节点

这种割环法的平衡性在虚拟节点数较多且搭配较好的hash函数的情况下，可以具备较好的平衡性和稳定性 ，实际应用中可以采用比Ketama算法默认160更多的虚拟节点数，hash算法也可以采用其他的算法。在算法的复杂度方面，Ketama算法的复杂度是O(log(vn))，其中n是节点数，v是节点的虚拟节点数。Ketama算法也能很好地满足单调性，当发生节点数量发生伸缩的时候，相当于只是在环上增加或者去掉相应的虚拟节点，也就只会导致变化的节点上的数据发生重新映射，因些能很好满足单调性。

Rendezvous hash

当发生扩缩的时候，相当于增加了一次计算hash的机会，如果计算出来的hash值超过原来的最大值，则该部分key分配到新的节点，缩容的时候则相当于把该节点上的key迁移到该key原本计算出来的hash值次高的节点上。可见，当节点变化的时候，rendezvous hash只会影响到最大权重值落到变化的节点的key，也就是说只有变化的节点上的数据需要重新映射，因些也很符合单调性的要求。 而Rendezvous hash算法的平衡性和稳定性则取决于哈希函数的随机特性 。

在wiki上还提供了优化方法（Skeleton-based variant）来降低算法的复杂度，如下图2所示，把原始节点分成若干个虚拟组，虚拟组一层一层组成一个“骨架”，然后在虚拟组中按照Rendezvous hash一样的方法计算出最大的节点，从而得到下一层的虚拟组，再在下一层的虚拟组中按同样的方法计算，直到找到最下方的真实节点，最终可以把算法复杂度降低到O(log n)。

Jump consistent hash

Jump consistent hash是Google于2014年发表的论文中提出的一种一致性哈希算法， 它占用内存小且速度很快，并且只有大概5行代码，比较适合用在分shard的分布式存储系统中 。其完整的代码如下，其输入是一个64位的key及桶的数量，输出是返回这个key被分配到的桶的编号。

下面根据论文内容简单介绍下其原理：

• 记ch(key, num_buckets)为桶数量为num_buckets时的hash函数
• 当num_buckets = 1时，显而易见，所有key都会分配给仅有的一个桶，即ch(key, 1) == 0
• 当num_buckets = 2时，为了使用key分布均匀，应该有1/2的key保留在0号桶中，而有1/2的key应该迁移到1号桶中
• 由此可以发现，当num_buckets由n变为n+1时，ch(key, n+1)的结果中应该有n/n+1结果保持不变，而有1/n+1的结果发生怕了跳变，变成了n

Jump consistent hash的这种思路看上去其实挺简单，就是num_buckets变化的时候，有些key的计算结果会发生变化。假如这里我们取一个随机数来决定每次要不要跳变，并且这个随机数只跟key有关，那么我们得到的初步算法如下：

int ch(int key, int num_buckets) {

    random.seed(key) ;

    int b = 0; // This will track ch(key, j +1) .

    for (int j = 1; j < num_buckets; j ++) {

        if (random.next() < 1.0/(j+1) ) b = j ; //这个不会经常执行

    }  

    return b;

}

从代码可以看出，算法的复杂度是O(n)，而且大家会发现，大多数情况下不会发生跳变，也就是b=j并不会执行，并且随着j越来越大，跳变的可能越来越小， 那么有没有什么办法来进行优化，让我们能通过一个随机数来直接得到下一次跳变的j，降低算法的复杂度呢？ 论文也在此基础上给出了优化后的算法并推理论证：

• 把ch(key, num_buckets)看做是一个随机变量，对于特定的key k，jump consistent hash跟踪了其桶编号的跳变
• 假设b是最后一次跳变的桶编号，也就是ch(k, b) != ch(k, b+1) 且ch(k, b+1) = b
• 假设下一次跳变的结果是j，也就是(b, j)之间每一次增加桶的结果都不应该发生跳变，对于(b,j)区间内的任意的i，j是下一次跳变的概率可以记为：P(j ≥ i) = P( ch(k, i) = ch(k, b+1) )
• 幸运的是P( ch(k, i) = ch(k, b+1) )的结果很好算，我们注意到P( ch(k, 10) = ch(k, 11) ) = 10/11, P( ch(k, 11) = ch(k, 12) ) = 11/12, P( ch(k, 10) = ch(k, 12) ) = 10/11 * 11/12 = 10/12。总的来说，如果n ≥ m, P( ch(k, n) = ch(k, m) ) = m / n. 因此对于任意的 i > b有：P(j ≥ i) = P( ch(k, i) = ch(k, b+1) ) = (b+1) / i，也就是j ≥ i的概率是(b+1) / i。
• 此时我们取一个[0，1]区间的随机数r，规定r < (b+1) / i就有j ≥ i，也就是i ≤ (b+1) / r，这样我们就得到了i的上界是(b+1) / r，而对于任意的i都有j ≥ i，所以j = floor((b+1) / r)，这样我们就用一个随机数r来算出了j。

所以上面的算法可以优化成以下实现：

int ch(int key, int num_buckets) {

    random. seed(key) ;

    int b = -1; //  bucket number before the previous jump

    int j = 0; // bucket number before the current jump

    while(j<num_buckets){

        b=j;

        double r=random.next(); //  0<r<1.0< span="">

        j = floor( (b+1) /r);

    }

    return b;

}</r<1.0<>

这里算法的复杂度变成了O(ln n)，代码里的随机函数需要是一个均匀的随机数生成器，论文中这里采用了一个64位的线性同余随机数生成器，所以对于key本来就是64位整数的，也不需要再对key进行hash计算了。Jump consistent hash的平衡性也取决于线性同余随机数生成器，因此也有着比较好的平衡性，论文中也与Karger经典的一致性哈希算法进行了对比，下图3为其对比结果，从标准差来看，jump consistent hash的平衡性比经典的一致性哈希算法好很多。而当节点数量发生变化的时候，jump consistent hash会发生跳变的key的数量已经是理论上的最小值1/n了。但jump consistent hash也有一个比较明显的缺点，它只能在尾部增删节点，而不太好在中间增删，对于那种节点随机故障需要剔除的情况，如果用这个算法就需要再采用其他方法来处理了。

Maglev hash

Maglev hash是Google于2016年发表的一篇论文中提出来的一种新的一致性哈希算法。Maglev hash的基本思路是建立一张一维的查找表，如图4所示，一个长度为M的列表，记录着每个位置所属的节点编号B0...BN，当需要判断某个key被分配到哪个节点的时候，只需对key计算hash，然后对M取模看所落到的位置属于哪个节点。

如何查找看上去很简单，问题是如何产生这个查找表 。接下来以图5为例介绍下如何生成查找表，假设我们有三个节点，B0、B1、B2，我们为每个节点生成长度为M(图5中M=7)的permutation list(偏好序列)，序列是(0，M-1)的随机数(如何生成这个序列我们下面解释)，如图5所示，B0的偏好序列是[3,0,4,1,5,2,6]。另外我们准备一个长度为M的待填充的查找表Entry。然后我们按B0、B1、B2的顺序，根据每个节点的偏好序列中的数字来填充查找表Entry。我们把偏好序列中的数字作为查找表中的目标位置，把该序列的节点编号填充到查找表的目标位置上，如果目标位置已经被占用，则继续往下查看偏好序列的下一个数字。以图5举例，具体步骤如下：

1）首先从B0的开始，B0偏好序列的第一个数字是3，所以查找表的3号位置填上B0

2）按顺序轮到B1，其偏好序列的第一个数字是0，所以查找表的0号位置填上B1

3）接着轮到B2，发现第一个数字是3，而查找表的3号位置已经被占用，那继续看B2的偏好序列的第二个数字是4，所以查找表的4号位置填上B2

4）然后又回到B0，这时发现B0的第二个数字是0已经被占用，往下看偏好序列的第三个数字是4，也被占用了，则继续往下看第四个数字是1，查找表的1号位置没被占用，所以查找表的1号位置填上B0

5）按此规则继续处理B1、B2，直到把查找表的所有位置都填满

总结

原文 哪种一致性哈希算法才是解决分布式缓存问题的王者？ (qq.com)