高效的一致性hash算法

问题介绍：给定总容量数(buckets)，给定大量key，通过hash算法把key分配到各buckets里。要求hash的算法满足：

1. 分配到各bucket的key数量大致数量平均；
2. 如果扩容(buckets数量增加)，保持key在原来的bucket或者放到扩容后的新bucket，而不会落到扩容前的其他bucket里；

如果用到object和server的实际应用场景，用bucket来表示server，用key来表示object，显示如下：

如果不用考虑效率，直接扩容后再重新算一遍hash，就可以了，似乎并不难。但这样需要记住扩容前和扩容后的bucket总数。这里介绍一种精妙的算法，不需要记住扩容前后的buckets。 算法在

A Fast, Minimal Memory, Consistent Hash Algorithm

https://arxiv.org/ftp/arxiv/papers/1406/1406.2294.pdf

最终的code只有短短几行，且不费内存

要理解这段code，需要先了解伪随机的原理。这里用了LCG (linear congruential generator)算法。这里就是

key = key * 2862933555777941757 + 1

不停生成key，近似于随机生成数。

再理解下随机数在这里的作用。想象一下 j 个 bucket 扩容到 j+1 个，每个key都有 1/(j+1) 的概率被分出去，因此可以在每个bucket的时候生成随机数，和 1/(j+1) 比较大小，决定是否要分走。

另一个精妙之处是不需要遍历每个bucket，因此有了遍历中跳跃jump的思路，可以根据随机数决定直接往后跳到那个bucket，不需要计算中间跳过的bucket，这样时间复杂度就可以大大降低。直观想，该bucket生成(0,1)之间的随机数rnd，则(0, rnd)的区间越小，概率越低，则可以往后跳得越远。

将上述随机数生成和jump过程结合，就有了完整的思路。不难理解，

current_j / next_j = random(0, 1)

如果next_j还没超过bucket总数，就跳到next_j，如果超过总数，就说明当前current_j已经是最终的bucket了。再直观理解下落到第一个bucket的概率，即一次生成比 1/max_j 小的数。

论文里还提供了另一种写法的code，便于理解

最后，用golang把最终code稍微改写了一下，如下

func jumpConsistentHash(key uint64, numBuckets int32) int32 {
 const param uint64 = 2862933555777941757
 const max32 float64 = 1 << 31
 b := int32(-1)
 for j := int32(0); j < numBuckets; {
  b = j
  // Linear Congruential Generator for pseudo-randomization
  key = key*param + 1
  // key>>33 makes 64-bit to 32-bit, so,
  // `scale` is actually 1/rnd where rnd is (0,1)
  scale := max32 / float64((key>>33)+1)
  j = int32(float64(b+1) * scale)
 }
return b
}