Consistent hashing最早是David Karger在MIT用于分布式缓存时提出的一个概念。对于分布式缓存系统来说，通常数据会分散地分布在不同的node上。而Consistent hashingh的作用就是来定位key->node的关系。本文主要是根据论文简单解释一下JumpConsistentHash的原理和实现。

为什么需要Consistent hashing

  通常来说，在线服务经常会因为请求量波动而需要去做扩缩容。如果用传统的hash方式去做，那就会导致数据分布会重排，那就意味着要做大规模的数据迁移，这显然对在线服务来说是不能接受的。新加一个node，通常只希望每一个node迁移少量一部分数据到新的node，删除一个node同样希望是删除的node重新均匀分配给其他node。而Consistent hashing就是为了解决这种动态数据分布均匀的问题。

JumpConsistentHash的实现

  标准的Consistent hashing实现的思路是把node和key同时hash映射到2^32的环上，再通过顺时针找到key最近的node。这个方式有个缺点是当node很少时，node在环上的分布不均匀，从而导致数据在node的分布不均匀。为了解决这个问题后来又引入了虚拟node的概念。

  传统的实现过于麻烦且复杂，在2014年Google发布了一篇《A Fast, Minimal Memory, Consistent Hash Algorithm》，在这篇论文中Google提出了一种纯数学的方式解决了这个问题，代码只需要仅仅几行。

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

它的时间复杂度小于ln(n) + 1，后面会给出证明。空间复杂度看代码很显然是O(1)。

JumpConsistentHash的原理

  设ch(key，num_buckets)为当有num_buckets个桶时key的Consistent hashing值。显然，对于任何key k，ch(k，1)为0，因为只有一个桶。为了使Consistent hashing函数平衡，ch(k，2)必须对于一半的k保持为0，另一半的k跳到1。一般来说，ch(k，n+1)必须对于n/(n+1)的key保持与ch(k，n)相同，而对于其他1/(n+1)的key则必须跳到n。

  根据这个思路，我们可以得出一个简单的算法。给定一个key和num_buckets，该算法考虑从1到num_buckets-1的每个连续的桶j，并使用ch(key，j)来计算ch(key，j+1)。在每个桶j处，它决定是否将ch(k，j+1)保持与ch(k，j)相同，或者将其值跳到j。为了跳跃1/(j+1)的key，它生成一个介于0.0和1.0之间的均匀随机数，如果该值小于1/(j+1)，则跳跃。代码如下：

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

  这里随着j的增加，跳跃的概率越来越低。所以论文里又想到了一种办法让key直接跳跃到下一个可跳跃的j。

  假设算法正在跟踪特定key的jump bucket。假设b是上一次跳跃的目的地，即ch(k，b)≠ch(k，b+1)，且ch(k，b+1)=b。现在，我们想找到下一个跳跃的目的地，即最小的j，使得ch(k，j+1)≠ch(k，b+1)，或者等价地算出最大的j，使得ch(k，j)=ch(k，b+1)。我们使用一个随机数j。为了得到对j的概率约束，对于任何i，当且仅当Consistent hashing的值没有改变i时，即当且仅当ch(k，i)=ch(k，b+1)时，我们有j≥i。因此，j的分布必须满足以下条件：

P(j ≥ i) = P(ch(k, i) = ch(k, b+1))

  这个概率P很容易计算。由于P(ch(k，10)=ch(k，11))为10/11，P(ch(k，11)=ch(k，12))为11/12，因此P(ch(k，10)=ch(k，12))为10/11 * 11/12 = 10/12。所以如果n≥m，则P(ch(k，n)=ch(k，m))=m/n。因此，对于任何i>b，有以下结论：

P(j ≥ i) = P(ch(k, i) = ch(k, b+1)) = (b+1) / i 

现在，我们生成一个随机变量r，它在0到1之间均匀分布。由于我们希望P(j≥i)=(b+1)/i，因此我们必须要让r<=(b+1)/i。解不等式得到：仅当i≤(b+1)/r。由于i是j的下限，因此，j=floor((b+1)/r)。使用这个公式，JumpConsistentHash可以通过选择跳跃的目的地来找到ch(key，num_buckets。代码如下：

int ch(int key, int num_buckets) {random.seed(key);int b = ­1; // bucket number before the previous jumpint j = 0; // bucket number before the current jumpwhile (j < num_buckets) {b = j;r = random.next();j = floor((b + 1) / r);}return = b;
}

最后再改成通过LCG来生成随机数就会变成本文开头的那段代码。

JumpConsistentHash的时间复杂度

  该算法的时间复杂度等于循环的执行次数。因为最后一次一定得跳出循环，也就是j >= num_buckets，故最少要执行一次。而每次跳跃的期望小于1/i，所以整体跳跃的期望=Σ 1/i (2 <= i <= n)，而这个数值是<ln(n)的，所以最终的复杂度大约是ln(n) + 1。

  论文中没有给出跳跃的期望的证明，可能是因为太简单了，笔者这里简单反证一下。

  假设当前在桶b，根据公式，如果要跳跃到b+1，则r需要在((b+1)/(b+2), 1)这个范围内。如果要跳跃到b+2，则r需要在((b+1)/(b+3), (b+1)/(b+2))这个范围内。以此类推，需要跳到b+n这个位置，则r需要在((b+1)/(b+n+1), (b+1)/(b+n))这个范围。

   故证明每次跳跃的期望小于1/i，等价于证明(b+1)/b+n - (b+1)/(b+n+1) < 1/(b+1)，令x=b+1,y=n-1可得：

   x/(x+y) - x/(x+y+1) < 1/x

  最后解得：

x*x < (x+y)(x+y+1)

  因为y=n-1，n>=2，故有y>=1。x=b+1>=1，所以显然上述不等式是成立的。

总结

  JumpConsistentHash提出了一种崭新的思路来解决这类问题。如果已经理解了原理，那不难看出想要增加或者删除node只能在末尾进行操作，这是和传统的实现不一样的地方。但笔者认为这个不是什么很大的缺点，它优秀的复杂度和实现完全可以覆盖掉这个缺点。笔者最近刚好要搭一套分布式缓存服务，直接拿这个上手非常好用。如果还想了解更多细节，比如benchmark，建议看原文。

参考

[1]《A Fast, Minimal Memory, Consistent Hash Algorithm》：https://arxiv.org/pdf/1406.2294.pdf

周公解梦