分布式 | 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))。

相关推荐：

分布式 | dble 沿用 jumpstringhash，移除 Mycat 一致性 hash 原因解析

技术分享 | Jump Consistent Hash 原理解析（上篇）
分类： DBLE 分布式中间件
标签：

相关文章

DBLE 分布式中间件

分布式 | DBLE 3.23.08.0 版本发布！

以下对 DBLE 3.23.08.0 版本的 Release Note 阅读更多…

DBLE 分布式中间件

分布式 | 如何搭建 DBLE 的 JVM 指标监控系统

本篇文章采用 Docker 方式搭建 Grafana + Promet 阅读更多…

DBLE 分布式中间件

分布式 | DBLE 3.23.04.0 版本发布！

以下对 DBLE 3.23.04.0 版本的 Release Notes 进行详细解读。