共计 1492 个字符，预计需要花费 4 分钟才能阅读完成。
作者：傅同学
爱可生研发部成员，次要负责中间件产品开发，热衷技术原理。
本文起源：原创投稿
* 爱可生开源社区出品，原创内容未经受权不得随便应用，转载请分割小编并注明起源。
前言
之前爱可生开源社区公众号发表了《dble 沿用 jumpstringhash，移除 Mycat 一致性 hash 起因解析》。
随后又发表了 本文上篇 ，初步解释了 Jump Consistent Hash 的原理。
首先让咱们回顾一下：
-
扩容时，随机抉择要挪动的元素
- 从现有 n 节点扩容到 n+1 节点时，n 节点上每个元素有 1/(n+1) 的概率挪动到新节点
- 应用稳固的、可重现的随机数序列——以 key 为随机数种子
咱们遗留了一个问题，O(n) 的算法复杂度不够现实，如何优化？
优化复杂度
与其在 bucket 逐渐减少的过程中，每次随机地决定是否跳跃到新增的 bucket。咱们尝试随机决定下一次加到第几个 bucket 才跳跃。当然，这个随机选取的指标须要合乎肯定的概率分布。
假如上一次 k 的跳跃产生在减少第 b+1 个 bucket 时，即 ch(k,b) != ch(k,b+1) 且 ch(k,b+1) = b+1（本文 bucket 编号从 1 开始）。这一次跳跃，咱们随机抉择了一个地位 j+1，即 ch(k,j+1) != ch(k,j) 且 ch(k,j) = ch(k,b+1)。
作为单次抉择，跳跃产生在 b+2（间断跳）或者 INT_MAX（再也不跳了），都是可能的。但总体上，j 的抉择要满足肯定的法则。
定义事件：对于任意 i >= b+2，在减少第 b+2、b+3 … i 个 bucket 时，都没有产生跳跃。该事件当且仅当 j+1 > i，即 j >= i 时成立。
该事件的概率能够这么算：
- 从 b+1 减少到 b+2，不跳跃的概率是
(b+1)/(b+2) - 始终加到第 i 个 bucket，都不跳跃，其概率为
(b+1)/(b+2)*(b+2)/(b+3)*...*(i-1)/(-) = (b+1)/i - 即
P(j>=i) = (b+1)/i。该等式对于任意 i 都成立。
j 是咱们任选的，可能 j>=i，也可能 j<i。抉择形式待定，但要让概率 P(j>=i)等于 (b+1)/i。
每次要抉择 j 时，咱们生成一个 [0,1) 上均匀分布的随机数 r，显然，布尔表达式 r <= (b+1)/i 为 true 的概率是 (b+1)/i。咱们先变换一下表达式：r <= (b+1)/i 变换后可得 i <= (b+1)/r。因为 i 是整数，(b+1)/r 向下取整不等式仍然成立，表达式最初变换为 i <= floor((b+1)/r)。
当上述表达式为 true 时，咱们就选则大 j (j>=i)；否则，咱们就选则小 j (j<i)。这个抉择形式, 就使 P(j>=i) = (b+1)/i 成立。
i <= floor((b+1)/r)时，i 最大可为floor((b+1)/r)，则j>=floor((b+1)/r)i > floor((b+1)/r)时，i 最小可为floor((b+1)/r)+1，则j<=floor((b+1)/r)
综上 j = floor((b+1)/r)。计算有 num_buckets 时，key 该当所在的 bucket 编号（本文中从 1 开始）的代码为：
func ch2(key int, num_buckets int) int {r := rand.New(rand.NewSource(int64(key)))
b1 := -1
j := 0
for j < num_buckets {
b1 = j + 1
j = int(math.Floor(float64(b1)/r.Float64()))
}
return b1
}r 的平均值是 0.5，即跳跃均匀产生在 bucket 数量翻倍时。粗略的看，算法复杂度是 O(log(n))。
