key: 53 title: Jump Consistent Hash 算法 math: true
这篇文章我们讨论 Jump Consistent Hash 算法, 一个极简且高效的一致性哈希算法.
哈希函数, 或者说散列函数, 能将一个较大定义域中的元素映射到一个较小的有限值域中. 值域中的元素有时也称为桶 (bucket), 值域的大小亦称为桶的数量.
MD5 就是一种常用的哈希函数, 它能将任意大小的数据 (较大的定义域) 映射成一个 16 字节的哈希值 (较小的有限值域). 最简单的哈希函数就是取模, 它能将全体整数 (较大的定义域) 映射到一个整数区间 (较小的有限值域) 中.
假设我们的服务器有 3 个工作进程, 同时为用户提供服务. 这些工作进程的功能是相同的, 并且会保存用户的状态数据. 那么如何决定一个用户由哪个工作进程提供服务呢? 最简单的办法是将用户 ID 对 3 取模, 结果是几就分配到哪个进程上.
这样看似工作得很完美. 随着用户量不断增长, 3 个工作进程压力过大, 需要对服务器进行扩容. 我们需要增加一个工作进程, 由 4 个工作进程同时为用户提供服务. 这个时候问题便出现了.
假设扩容前服务器有 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 号桶中, 以此类推.
从另一个角度考虑这个问题: 假设有一个元素, 当有 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$ 号桶中, 那么我们能不能求出这个元素下次移动时的目标呢?
假设元素下次移动时的目标为 $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$. 算法每次迭代根据一个旧的随机数 $Xn$ , 生成一个新的随机数 $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 的非负整数集. 这意味着不能简单地把中间的桶去掉, 这会导致值域不连续.
参考资料: