文档章节

技术分享 | Jump Consistent Hash 原理解析(上篇)

爱可生
 爱可生
发布于 02/13 17:31
字数 1343
阅读 196
收藏 0

作者:傅文辉

之前爱可生开源社区公众号发表了dble 沿用 jumpstringhash,移除 Mycat 一致性 hash 原因解析, 阐述了跳跃法相对环割法的性能优势。很多读者表示对其中"跳跃法的原理"不是很理解,本文就来详细阐述一下。

一致性哈希

首先,我们的需求是,将数据(key-value pair)分布在多个节点上。这点可以简单的用取模实现,

节点 key
1 1 4 7 10
2 2 5 8 11
3 3 6 9 12

然而,当增加新节点时,数据将发生大规模转移:

节点 key
1 (1) 5 9
2 (2) 6 10
3 (3) 7 11
4 4 8 12

一致性哈希的主要目的是,在节点数量发生变更时,只需要在节点间移动少量数据,而不是"全部洗牌"。

除了经典的环割法一致性哈希外,Google 发表了另一种实现简洁且高效的跳跃法一致性哈希《A Fast, Minimal Memory, Consistent Hash Algorithm》(文末附链接)

在爱可生开源数据库中间件 dble 中,关于 jump consistent hash 的配置方法详见 dble 官方手册中"跳增字符串算法"的部分(文末附链接)。

基础实现

与原始论文不同, 本文节点(又称 bucket)从 1 开始编号,而非从 0 开始。

  • 先考虑只有一个节点的情况,显然所有数据都放在这个节点里, 即 ch(key,1)=1 (ch 为 consistent_hash 之缩写)。
  • 考虑增加一个节点,我们随机抽取 1/2 的数据移动到 2 号节点
  • 考虑再增加一个节点,需要从 1、2 号节点中,随机抽取共 1/3 的数据移动到 3 号节点
    • 为了均匀分配, 1、2号需要各出 1/6 的数据
    • 实际上,只要每个 key 都有 1/3 的概率被抽中,分配总是均匀的

可以看到,每增加一个节点,只需要移动总共 1/n 的数据,而不是取模法中的几乎所有数据。

所谓随机抽取,我们采用可重现的随机:首次调用 Rand() 之前将 key 作为随机数种子。因而对于一个 key,首次放入和后续取回使用的是相同的随机数序列。

例如有 k1,k2,k3 三个 key, 随着节点数量从 1 到 15 增长, 它们各自会在某一时刻“跳跃”,而后“稳定”一段时间。

1 2 3 4 5 6 7 8 9 10 11 12 13 14
k1 1 1 3 3 5 5 5 5 5 5 5 5 5 5
k2 1 2 2 2 2 2 2 8 8 8 8 8 8 8
k3 1 2 2 2 2 6 6 8 8 8 11 11 11 11

我们用数学归纳法来表达一下某个 key 在不同节点数时的位置:

  • 基础情况:只有一个节点,只能放在节点 1
  • 归纳情况:假设目前有 n 个节点,增加一个节点到 n+1 个。key 目前所在的位置由之前的跳跃情况决定。本轮该 key 有 1/(n+1) 的概率被移到 n+1 号节点
    • 即 n+1 节点时,key 所在的位置由 n 节点时的位置和一个随机变量 rand 决定, 如果 rand<1/(n+1), 它就会跳跃到 n+1 节点, 否则则和 n 节点时一样

结合基础情况和归纳情况,我们得出了 n 为任意正整数时的分配方法。数学归纳法的逻辑和递归代码直接对应:

  func ch(r *rand.Rand, k int, i int) int {
  	if i == 1 {
      	// 基础情况
      	return 1
      } else {
      	// 归纳情况
      	b := ch(k, i-1)
          if rand.Float() < 1.0/float64(i) {
  	        return i
          } else {
  	    	return b
          }
      }
  }

func ch_wrapper(k int, i int) int {
    r := rand.Seed(k) // 在计算之前, 将key作为随机数种子
    return ch(r, k, i)
}

注意,要先计算 ch(k, i-1) 再决定本轮是否跳转( if rand < 1.0/i )。不能因为本轮决定跳转就不计算上一轮的结果,否则会因节点数不同而产生不一样的随机序列。

工程代码中一般使用循环代替递归。本文不再赘述递归转循环的办法。

优化性能

我们看到,对于一个 key,我们要从 1~N(N 为节点数)循环一遍,即复杂度为节点数的线性关系. 原始论文中给出了一个巧妙的方法,使复杂度从线性降低到了对数:既然每一次是否跳跃的决策中我们随机决定,那么,与其一次次决定是否跳跃,我们是否能够直接随机地决定下一次跳跃的目标?当然,这个随机目标的取值符合一定的概率分布。

关于这个巧妙方法的具体内容和论证,敬请期待下篇。

文中相关资源链接: 《A Fast, Minimal Memory, Consistent Hash Algorithm》 https://arxiv.org/ftp/arxiv/papers/1406/1406.2294.pdf 《DBLE 手册中跳增字符算法部分》 https://actiontech.github.io/dble-docs-cn/1.config_file/1.01_rule.xml.html

© 著作权归作者所有

爱可生

爱可生

粉丝 16
博文 254
码字总数 450380
作品 1
徐汇
私信 提问
加载中

评论(0)

【翻译/介绍】jump Consistent hash:零内存消耗,均匀快速简洁,来自Google

简介 jump consistent hash是一种一致性哈希算法, 此算法零内存消耗,均匀分配,快速,并且只有5行代码。 此算法适合使用在分shard的分布式存储系统中 。 此算法的作者是 Google 的 John Lam...

天天顺利
2015/06/03
2.7K
0
聊聊jump consistent hash

序 本文主要简介一下jump Consistent hash。 jump consistent hash jump consistent hash是一致性哈希的一种实现,论文见A Fast, Minimal Memory, Consistent Hash Algorithm 经典的一致性哈...

xixicat
2017/11/11
0
0
memcached 分布式实现原理

本文作者:伯乐在线 -Float_Lu 。未经作者许可,禁止转载! 欢迎加入伯乐在线专栏作者。 摘要 在高并发环境下,大量的读、写请求涌向数据库,此时磁盘IO将成为瓶颈,从而导致过高的响应延迟,...

伯乐在线
2016/05/20
0
0
Nginx开发从入门到精通 学习目录分享学习 (阿里著作)

Nginx开发从入门到精通 缘起 nginx由于出色的性能,在世界范围内受到了越来越多人的关注,在淘宝内部它更是被广泛的使用,众多的开发以及运维同学都迫切的想要了解nginx模块的开发以及它的内...

lhj588
2014/06/16
0
0
深入一致性哈希(Consistent Hashing)算法原理

本文为实现分布式任务调度系统中用到的一些关键技术点分享——Consistent Hashing算法原理和Java实现,以及效果测试。(代码实现见:https://github.com/yaohonv/pingpong/tree/master/consi...

群星纪元
2019/04/11
26
0

没有更多内容

加载失败,请刷新页面

加载更多

上海哪里有开住宿费发票

电13564998196 陈生详情-项.目.齐.全 可先开验。-本报讯(劳动报记者陆燕婷)聚焦餐饮行业,58同城招聘研究院昨 发布数据显示,今年上半年,全国餐饮行业招聘需求增长46.18%,平均月薪6387元。...

漂迦徴fp2090
5分钟前
5
0
上海哪里有开住宿费发票

电13564998196 陈生详情-项.目.齐.全 可先开验。-本报讯(劳动报记者陆燕婷)聚焦餐饮行业,58同城招聘研究院昨 发布数据显示,今年上半年,全国餐饮行业招聘需求增长46.18%,平均月薪6387元。...

票迦徴fp2090
5分钟前
7
0
上海哪里有开住宿费发票

电13564998196 陈生幵真嘌 可先幵验。-本报讯(劳动报记者陆燕婷)聚焦餐饮行业,58同城招聘研究院昨 发布数据显示,今年上半年,全国餐饮行业招聘需求增长46.18%,平均月薪6387元。随着餐饮行...

嘌迦徴fp2090
6分钟前
7
0
上海哪里有开住宿费发票

电13564998196 陈生详情-项.目.齐.全 可先开验。-本报讯(劳动报记者陆燕婷)聚焦餐饮行业,58同城招聘研究院昨 发布数据显示,今年上半年,全国餐饮行业招聘需求增长46.18%,平均月薪6387元。...

嘌珈徴fp2090
7分钟前
7
0
上海哪里有开住宿费发票

电13564998196 陈生幵真嘌 可先幵验。-本报讯(劳动报记者陆燕婷)聚焦餐饮行业,58同城招聘研究院昨 发布数据显示,今年上半年,全国餐饮行业招聘需求增长46.18%,平均月薪6387元。随着餐饮行...

票加徴fp2090
8分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部