Jump Consistent Hash是一个来自Google的快速, 几乎没有内存消耗的一致性哈希算法. 这篇文章是我的翻译和理解思路.

哈希算法的设计目标

  1. 平衡性, 把对象均匀地分布在所有桶(bucket)中.
  2. 单调性, 当桶的数量变化时, 只需要把一些对象从旧桶移动到新桶, 不需要做其它(例如旧桶之间的)移动.

比如一个分布式存储的系统, 按哈希分布带来优化的便利, 平衡性可以避免数据倾斜, 单调性则使得扩容和减容更快速.

算法的设计思路

我们用循序渐进的思路来设计, ch(key, num_buckets)为桶数为num_buckets时的hash函数, 为了满足设计目标, 需要:

  1. num_buckets为1时, 任意key, ch(key, 1)==0, 全落在第0个桶里.
  2. num_buckets由1变为2后, ch(key, 2)应该有1/2的结果保持为0, 有1/2变为1.
  3. …
  4. num_buckets由n变为n+1后, ch(key, n+1)应该有n/(n+1)的结果保持不变, 有1/(n+1)跳变为n+1.

因此, 只要我们用一个分布均匀的函数, 例如伪随机数生成器, 并且让这个伪随机数生成器的状态只依赖于key, 从0个桶开始推导, 变到第num_buckets个桶, 结果就是我们想要的hash值:

int ch(int key, int num_buckets) {
    random.seed(key);
    int b = 0;
    for (int j = 1; j < num_buckets; j++) {
        if (random.next() < 1.0 / (j + 1))
            b = j;
    }
    return b;
}

很显然, 这个算法是O(n)的, 而且随着j越来越大, b=j需要执行的概率也越来越低. Google最终的算法叫Jump Consistent Hash, Jump指的是j是跳跃的, 那他们是怎么让j跳跃, 并保持结果正确呢?

我们用概率的思路来想这个问题, 假设变化过程中的上一次结果是b, 下一次结果j大于等于一个大于b的数i的概率, 也就是可以跳到i的概率, 也就是从b+1到i的过程中, 桶序号都没有变的概率为:

P(j>=i) = P(ch(key, b+1)==ch(key, i))

这个概率也就是连续多次不变事件概率的乘积:

P(j>=i) = P(ch(key, b+1)==ch(k, b+2)) * P(ch(key, b+2)==ch(key, b+3)) * ... * P(ch(key, i-1)==ch(key, i))

由于单次不变的概率为:

P(ch(key, i)==ch(key, i+1)) = i/(i+1)

所以连续多次不变的概率为:

P(j>=i) = (b+1)/(b+2) * (b+2)/(b+3) * ... * (i-1)/i = (b+1)/i

基于之前的代码, 当随机结果r小于(b+1)/i时跳到i就可以保持概率不变, 也就是任意的r都可以跳到floor((b+1)/r):

int ch(int key, int num_buckets) {
    random.seed(key);
    int b = -1;
    int j = 0;
    while (j < num_buckets) {
        b = j;
        double r = random.next();
        j = floor((b + 1) / r);
    }
    return b;
}

最终的完整代码

最终代码里没有用random函数, 而是写了一个基于”线性同余方法”的伪随机数产生器, 意思是一样的.

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;
}