Jump Consistent Hash是一个来自Google的快速, 几乎没有内存消耗的一致性哈希算法. 这篇文章是我的翻译和理解思路.
比如一个分布式存储的系统, 按哈希分布带来优化的便利, 平衡性可以避免数据倾斜, 单调性则使得扩容和减容更快速.
我们用循序渐进的思路来设计, ch(key, num_buckets)为桶数为num_buckets时的hash函数, 为了满足设计目标, 需要:
ch(key, 1)==0, 全落在第0个桶里.ch(key, 2)应该有1/2的结果保持为0, 有1/2变为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;
}