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

2020-12-25发布 1,012浏览

关键字：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数据库压缩

分布式 | 使用 Arthas 热更新 dble

分布式 | DBLE 网络模块源码解析（二）

2024-04-22 发布 636 浏览

爱可生携手OceanBase共建生态繁荣，2024开发者大会分享《ActionDB生态体系建设与实践经验》

2024-03-28 发布 783 浏览

36氪发布AIGC行业报告，爱可生荣登向量数据库领域代表企业榜单

2024-02-02 发布 1,039 浏览

爱可生荣获证券基金行业信息技术应用创新联盟年度优秀成员奖

2024-02-01 发布 1,330 浏览

爱可生获得OceanBase特别认可“客户第一”，2023年度重点项目交付合作再创佳绩

2024-01-31 发布 3,287 浏览

信通院云大所大数据和区块链部向爱可生致谢，共铸业内首个《向量数据库技术要求》