Jump Consistent Hash 算法

这篇文章我们讨论 Jump Consistent Hash 算法, 一个极简且高效的一致性哈希算法.

哈希与一致性哈希

哈希函数, 或者说散列函数, 能将一个较大定义域中的元素映射到一个较小的有限值域中. 值域中的元素有时也称为桶 (bucket), 值域的大小亦称为桶的数量.

MD5 就是一种常用的哈希函数, 它能将任意大小的数据 (较大的定义域) 映射成一个 16 字节的哈希值 (较小的有限值域). 最简单的哈希函数就是取模, 它能将全体整数 (较大的定义域) 映射到一个整数区间 (较小的有限值域) 中.

假设我们的服务器有 3 个工作进程, 同时为用户提供服务. 这些工作进程的功能是相同的, 并且会保存用户的状态数据. 那么如何决定一个用户由哪个工作进程提供服务呢? 最简单的办法是将用户 ID 对 3 取模, 结果是几就分配到哪个进程上.

hash

这样看似工作得很完美. 随着用户量不断增长, 3 个工作进程压力过大, 需要对服务器进行扩容. 我们需要增加一个工作进程, 由 4 个工作进程同时为用户提供服务. 这个时候问题便出现了.

rehash

假设扩容前服务器有 12 名用户在线, ID 为 1 至 12, 那么它们在 3 个进程中的分布如上图 (1) 所示. 现在我们增加一个工作进程, 这就需要将用户分配到 4 个进程中, 哈希函数应该改为对 4 求余, 这会导致客户端的分布转为上图 (2) 所示的情况. 前面提到, 服务器的各个进程会保存用户的状态数据; 而这次扩容会导致几乎所有用户的进程发生变化, 这就必须执行大量的数据迁移操作. 如果服务器有大量用户在线, 扩容操作的成本会变得难以接受.

为了解决这个问题, 人们提出了一致性哈希 (consistent hash). 一致性哈希是一类特殊的哈希函数, 它的特点是, 当桶的数量从 \(N-1\) 增加至 \(N\) 时, 平均只有 \(\frac{1}{N}\) 的映射结果发生改变. 观察上面的例子, 扩容时我们只需要在 p0, p1 和 p2 中各取一个用户迁移到 p4 即可, 也就是只改变 \(\frac{12}{4} = 3\) 个 ID 的映射结果.

一致性哈希算法有很多种. 最早的一致性哈希算法由 Karger 等人提出, 它将桶关联在一个顺时针排列的环中, Chord 算法中就用到了它. 本文介绍的是 2014 年 John Lamping 等人提出的 Jump Consistent Hash 算法. 它极其简洁, 仅有 7 行代码:

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

初看可能会一头雾水: 2862933555777941757ULL 是什么东西? 左移右移转浮点再相除是在做什么? 这么简单几行真的能实现只改变 \(\frac{1}{N}\) 的映射吗? 接下来我们便来逐步探究这个神奇的算法.

基于概率的哈希算法

前面提到, 当桶的数量从 \(N-1\) 增加至 \(N\) 时, 有 \(\frac{1}{N}\) 的映射结果发生改变. 也就是说, 假设哈希函数将 \(m\) 个元素映射到 1 个桶中, 此时所有元素都映射在 0 号桶中, 即哈希值都为 0; 若桶数变为 2, 则有 \(\frac{m}{2}\) 个元素从 0 号桶移动到 1 号桶, 即哈希值变为 1. 同理, 当桶数变为 3, 则有 \(\frac{m}{3}\) 个元素从前两个桶移动到 2 号桶中; 桶数变为 4, 则有 \(\frac{m}{4}\) 个元素从前三个桶移动到 3 号桶中, 以此类推.

buckets

从另一个角度考虑这个问题: 假设有一个元素, 当有 1 个桶时映射在 0 号桶中. 当桶数变为 2 时, 它有 \(\frac{1}{2}\) 当概率移动到 1 号桶中; 当桶数变为 3 时, 它有 \(\frac{1}{3}\) 当概率移动到 2 号桶中, 以此类推. 也就是说, 无论这个元素当前在哪个桶中, 只要当桶当数量从 \(N-1\) 变为 \(N\), 它都有 \(\frac{1}{N}\) 的概率移动到 \(N-1\) 号桶中. 这样, 我们就把这个问题转换成一个概率问题.

根据这个思路, 我们就能实现一个一致性哈希算法了. 由于算法是基于随机概率的, 为了让每次哈希结果一致, 我们将元素的值做随机种子.

int consistent_hash(int key, int num_buckets) {
    srand(key);
    int b = 0;
    for (int n = 2; n <= num_buckets; ++n) {
        if ((double)rand() / RAND_MAX < 1.0 / n)
            b = n - 1;
    }
    return b;
}

这个算法模拟了桶数量增长的情况. 当桶数量为 1 时, 元素必定在 0 号桶中, 因此有初始 b = 0. 之后桶依次增加, 每次增加到 n 时, 该元素都有 1 / n 的概率移动到 n - 1 号桶中, 也就是刚新增的桶中.

改进后的算法

这个算法虽然能实现一致性哈希, 但它有些慢, 时间复杂度为 \(\mathrm{O}(n)\). 有没有更快但方式呢? 我们注意到, 当桶增加时, 元素只有较小的概率移动到新增加的桶中, 大概率会原地不动. 如果我们能够只在元素移动时计算, 算法就会快很多.

注意到元素只会在桶增加时移动, 且每次移动都必然移动到最新的桶中. 即, 如果一个元素移动到 \(b\) 号桶中, 则必然是桶增加到 \(b+1\) 个导致了这次移动. 假设元素刚刚在桶增加到 \(b + 1\) 个时移动到了 \(b\) 号桶中, 那么我们能不能求出这个元素下次移动时的目标呢?

jump-probability

假设元素下次移动时的目标为 \(j\) 号桶, 意味着元素在桶增加到 \(j + 1\) 个时才会移动, 换句话说, 元素在桶增加到 \(b+2, b+3, \cdots, j\) 个时都不移动. 如果我们求出了最大的 \(j\) 使得元素在桶增加到 \(b+2, b+3, \cdots, j\) 个时都不移动, 我们就求出了下次移动的目标 \(j\).

而从概率上考虑, 元素下次移动的目标至少为 \(j\) 的概率 \(P_j\) 等于桶增加到 \(b+2, b+3, \cdots, j\) 个时不移动的概率. 我们知道当桶增加到 \(N\) 个时元素移动的概率为 \(\frac{1}{N}\), 所以不移动的概率为 \(\frac{N-1}{N}\). 因此有:

\[ \begin{align} P_j &= \frac{b+1}{b+2} \frac{b+2}{b+3} \frac{b+3}{b+4} \cdots \frac{j-1}{j} \\ &= \frac{b+1}{j} \end{align} \]

现在我们把思路逆转过来. 现在元素在桶增加到 \(b+1\) 个时移动到了 \(b\), 我们要确定这个元素下次移动的位置 \(j\). 我们完全可以生成一个 0 至 1 之间的随机数 \(r\), 令 \(P_j = r\). 然后我们就可以决定 \(j\) 了:

\[ j = \left\lfloor \frac{b + 1}{r} \right\rfloor \tag{1} \]

改进后的算法如下:

int consistent_hash(int key, int num_buckets) {
    srand(key);
    int b = 1, j = 0;
    while (j < num_buckets) {
        b = j;
        r = (double)rand() / RAND_MAX;
        j = floor((b + 1) / r);
    }
    return b;
}

上面的算法中, 每次迭代都用 (1) 式求出元素下一个移动的位置 j, 直到 j >= num_buckets.

线性同余发生器

进一步改进算法, 我们可以使用自己实现的随机函数, 而不是依赖于系统的. 这里我们使用线性同余发生器 (Linear congruential generator). 这是一个古老的随机数生成算法, 很容易实现. 它的随机数是迭代生成的, 迭代式如下:

\[ X_{n+1} = (aX_n + c) \mod m \]

\(a, c, m\) 都为常数. \(m\) 是一个正整数, 称为模数; \(a\) 称为乘数, \(0 \lt a \lt m\); \(c\) 称为增量, \(0 \le c \lt m\). 算法每次迭代根据一个旧的随机数 \(X_n\) , 生成一个新的随机数 \(X_{n+1}\). 迭代的初始值 \(X_0\) 称为种子, \(0 \le X_0 \lt m\).

Jump consistent hash 算法中, 每次迭代都是这样的:

key = key * 2862933555777941757ULL + 1;
j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));

随机算法的乘数为 2862933555777941757, 增量为 1, 模数为 0x10000000000000000. 不需要手动取模, 让整数自然溢出即可. 因此每次迭代都生成一个随机数, 随机数的范围是 0 至 0xffffffffffffffff. 这里 (key >> 33) + 1 取随机数的高 31 位再加一, 范围是 1 至 0x80000000. 再让 0x80000000 与之相除, 得到概率的倒数. 最后乘以 b + 1 便是元素下次移动的位置 j.

总结

所以说小代码里有大智慧. 这其中还一些内容本文还没深处展开, 比如说概率公式的严格证明; 比如说为什么乘数是 2862933555777941757, 增量为什么是 1. 随机数生成算法是一个不小的课题, 本文只能点到为止. 比起 Karger 的算法, Jump Consistent Hash 算法简洁, 快速, 不需要额外内存. 当然它也有缺点: 它的值域只能是小于 N 的非负整数集. 这意味着不能简单地把中间的桶去掉, 这会导致值域不连续.

---

参考资料: - A Fast, Minimal Memory, Consistent Hash Algorithm - Linear congruential generator