Jump一致性哈希算法

简介

Jump consistent hash是一种一致性哈希算法,

此算法零内存消耗，均匀分配，快速，并且只有5行代码。

这个算法是 Google 的 John Lamping 和 Eric Veach 创造的。
他们为这个算法写了一篇论文：《A Fast, Minimal Memory, Consistent Hash Algorithm》。

看了论文后，我才恍然大悟，原来是这样，果然是合理的。
如果你阅读原文论文，可以公众号后台回复“谷歌算法”获取论文。

算法原理

一致性哈希算法有两个目标：

1. 平衡性。即把数据平均的分布在所有节点中。
2. 单调性。即节点的数量变化时，只需要把一部分数据从旧节点移动到新节点，不需要做其他的移动。

我们根据这个单调性可以推算出一些性质来。
这里先另f(key, n)为一致性哈希算法，输出的为[0,n)之间的数字，代表数据在对应的节点上。

1. n=1 时，对于任意的key，输出应该都是0。
2. n=2 时，为了保持均匀，应该有1/2的结果保持为0，1/2的结果输出为1。
3. n=3 时，应该有1/3的结果保持为0，1/3的结果保持为1，1/3的结果保持为2。
4. 依次递推，节点数由n变为n+1时，f(key, n)里面应该有n/(n+1)的结果不变，有1/(n+1)的结果变为n。

这个使用概率公式来表示，就是这样的代码。

1
2
3
4
5
6
7
8
9

int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) { 
    int64_t b = -1, j = 0; 
    while (j < num_buckets) { 
        b = j; 
        key = key * 2862933555777941757ULL + 1; 
        j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1)); 
    } 
    return b;
}

算法优化

除了复杂度是O(n)外，我们还可以确定，循环越往后，结果改变的概率会越来越低。

结果改变指的是，增加一个节点后，一个固定的key输出的结果发生了改变。
如果我们能够快速计算出这个固定的key在哪些节点下发生了改变，就可以快速计算出最终答案。

假设某一次结果是b，经过若干次概率测试，下一次改变为a，则从b+1到a-1这中间，不管节点如何变化，这个key的结果都是不会变化的。
根据上一小节的到的概率变化公式，新增一个节点数字不变化的概率是n/(n+1)。
那从b+1到i不变化的概率就是(b+1)/i（中间的抵消了）。

如果我们有一个均匀的随机函数r，可以确定当r<(b+1)/i时，f(i)=f(b+1)。
那么i的上界就是(b+1)/r向上取整。
这个上限也是下一次key发生变化的节点数量。