分布式 | Jump Consistent Hash 原理解析(下篇)

发布时间:2020-12-25 浏览次数:216

关键字:MySQL数据库容灾方案MySQL数据库数据备份MySQL数据库压缩

前言

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


关键字:MySQL数据库容灾方案MySQL数据库数据备份MySQL数据库压缩


上一篇: 分布式 | DBLE 网络模块源码解析(二)

下一篇: 分布式 | 使用 Arthas 热更新 dble

产品试用 产品试用
400-820-6580 免费电话