分布式 | Jump Consistent Hash 原理解析（下篇）

作者：傅同学

爱可生研发部成员，主要负责中间件产品开发，热衷技术原理。

本文来源：原创投稿

*爱可生开源社区出品，原创内容未经授权不得随意使用，转载请联系小编并注明来源。

前言

之前爱可生开源社区公众号发表了《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))。