这个算法零内存、分布均匀、计算快速，全是优点了。但是。。。
一、背景
三年前在《一致性hash基础知识》文章中，曾提到 google 有一个算法简单的计算就做到了一致性哈希需要做到的事情。
上个月在《一致性HASH技术的困境》文章的留言中，也有小伙伴提到，有一个 Jump consistent hash 算法可以做到一致性哈希的事情。
其实这两个说的是一个事情，那就是 google 有一个 Jump consistent hash 算法，可以通过数学运算做到和一致性哈希效果一样好的平衡性。
那今天就来看看这个算法吧。
二、看代码
先看代码，下面就是全部的代码。
是不是感觉不可思议，这个代码的语法全部都懂，但是合在一起我们就看不懂了。
我第一眼看到这个代码的时候，也是一脸懵逼的。
这个算法是 Google 的 John Lamping 和 Eric Veach 创造的。
他们为这个算法写了一篇论文：《A Fast, Minimal Memory, Consistent Hash Algorithm》。
看了论文后，我才恍然大悟，原来是这样，果然是合理的。
如果你要阅读原文论文，可以公众号后台回复“谷歌算法”获取论文。
三、算法原理
一致性哈希算法有两个目标：
- 平衡性。即把数据平均的分布在所有节点中。
- 单调性。即节点的数量变化时，只需要把一部分数据从旧节点移动到新节点，不需要做其他的移动。
我们根据这个单调性可以推算出一些性质来。
这里先令
f(key, n)
为一致性哈希算法，输出的为
[0,n)
之间的数字，代表数据在对应的节点上。
-
n=1
key
-
n=2
1/2
1/2
1
-
n=3
1/3
1/3
1
1/3
2
- 依次递推，节点数由
n
n+1
f(key, n)
n/(n+1)
1/(n+1)
n
这个使用概率公式来表示，就是这样的代码。
关于这个算法直接看可能还是看不懂。
所以需要使用实际数据模拟一下，见下图。
关键在于
n=2
到
n=3
的过程，每个数字的概率从
1/2
转化到了
1/3
。
之后，我们可以得出一个规律：增加一个节点，数据不发生变化的概率是
n/(n+1)
再乘以之前每个数字的概率
1/n
，就可以得出每个数字最新的概率
1/(n+1)
由此，可以轻松计算出
n=4
各数字的概率为
1/4
。自此，我们可以确定这个算法确实是有效的。
这个算法唯一的缺点是复杂度太高，是
O(n)
的。
所以需要进行优化。
四、算法优化
在上一小节中，我们了解到
f(key, n)
算法的正确性。
除了复杂度是
O(n)
外，我们还可以确定，循环越往后，结果改变的概率会越来越低。
结果改变指的是，增加一个节点后，一个固定的
key
输出的结果发生了改变。
如果我们能够快速计算出这个固定的
key
在哪些节点下发生了改变，就可以快速计算出最终答案。
假设某一次结果是
b
，经过若干次概率测试，下一次改变为
a
，则从
b
到
a-1
这中间，不管节点如何变化，这个
key
的结果都是不会变化的。
根据上一小节的到的概率变化公式，新增一个节点数字不变化的概率是
n/(n+1)
。
那从
b
到
i
不变化的概率就是
b/i
（中间的抵消了）。
如果我们有一个均匀的随机函数
r
，当
r<b/i
时，
f(i)=f(b)
。
那么
i
的上界就是
(b+1)/r
。
这个上限也是下一次
key
发生变化的节点数量，由此可以得出下面的代码。
由于
r
是均匀的，所以期望是
1/2
。
这样，代码中
j
就是按照指数级增长的，平均复杂度就是
O(log(n))
了。
回头看看第一个代码，就可以看懂代码了。
第一个
key=key*x+1
算是一个伪随机生成器。
而
j=(b+1)*x/y
则是上面的求上界的公式，其中
y/x
通过浮点数运算来产生
(0,1)
内的一个随机数。
自此，这个代码就可以看懂了。
五、最后
谷歌能够创造这样一个算法确实了不起，但是从实际应用上来，这个算法也没有想象中的好。
如果你用过一致性哈希的话，会发现有很多问题。
因为我们实际使用时，节点往往是有权重的。
这里只有一个节点的最大值，那意味着，节点的扩散需要在外层实现。
也就是需要在外层来储存扩散后的节点列表。
既然外面储存了节点列表，按照 hash 值排序，就可以二分查找出符合要求的节点了。
如果使用 map 储存，也可以在
log
级别找到对应的节点。
由此，可以发现 谷歌的这个算法自身不需要内存了，但是内存需要业务自己维护，实际上还是需要的。
当然，如果你没使用过一致性哈希的话，你不知道我在说什么。
或者你可以看看之前我记录的一致性 HASH 文章，然后再回头看看这个小节。
-EOF-
上篇文章：《公有云、私有云、专有云的区别》
相关推荐：《一致性hash基础知识(二)》
本文公众号：天空的代码世界
个人微信号：tiankonguse
QQ算法群：165531769（不止算法）
知识星球：不止算法