如何理解一致性哈希
这篇文章主要讲解了“如何理解一致性哈希”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“如何理解一致性哈希”吧!
创新互联建站是一家专业提供青岛企业网站建设,专注与网站建设、成都网站建设、HTML5、小程序制作等业务。10年已为青岛众多企业、政府机构等服务。创新互联专业网站制作公司优惠进行中。
一技能:哈希算法
分组
韩信的一技能哈希算法:将士兵的编号 num 值当做一个哈希值,再和总做小组数 N 做取余操作,得出的结果在 0 到 N - 1 之间,这个士兵就属于那个组。
如下图所示,每来一个士兵都有一个六位的 hash 值(也可以称作编号),然后被韩信用除以 3 取余数的方式分配到三个组。比如第一组中的编号为 123456 的士兵,除以 3 之后,整除,余数为 0,所以分配到第一组。
哈希算法
查找士兵
现在已经分好组了,假如想找到编号为 666666 的士兵该怎么找?首先将 666666 除以 3,得到余数 0,说明在第一个组,然后去第一个组里面找就可以了。
这里有小伙伴可能会问,为什么不是把所有士兵放到一个组?
因为一个组太大了,影响行军速度。映射到互联网架构中,就是通过增加节点从而减小单节点的负载压力。
哈希分组弊端
刘邦看了这个一技能后,大呼:
韩将军真是厉害。
哈希算法看起来很完美,那我再给你五百士兵,需要分成四个组怎么办?
这时,韩信的副将说话了:
这还不简单,再用 4 取余不就好了吗?
刘邦摸着下巴思索片刻后,对副将说:
这个方案可行,但很多士兵都被重新分组了,刚刚建立的团队友情就被分解了。
我们来看下刘邦为什么觉得方案不可行。
比如原来分配到一组的编号为 3 的士兵,当分成四组的时候,通过公式计算:3%4=3,所以会分配到到第四组。
依次类推,会发现很多士兵进行了重新分配,只有小部分不会变换分组,比如 1,2,12 不会被重新分组。
韩信对着刘邦点点头,对着主公说道:
主公,您说得没错,这就是我的一技能的弱点所在。
不过我还有一个技能:一致性哈希。
二技能:一致性哈希哈希环
一致性哈希算法也用了取模运算,但是它与哈希算法不同的地方:
哈希算法:对节点的数量进行取模运算。
一致性哈希算法:对 2^32 进行取模运算。
可以想象一下,一致性哈希算法,是将整个哈希值空间组成了一个虚拟的圆环,也就是哈希环。
如下图,把 3 个组映射到固定大小为 2^32 的哈希环中。三个组一共将整个环分成了三个区域,C-A(第一组)、A-B(第二组)、B-C(第三组)。如下图所示:
分成三组
第一组负责存储落在 C-A 区间内的数据。
第二组负责存储落在 A-B 区间内的数据。
第三组负责存储落在 B-C 区间内的数据。
士兵分配
假定编号为 9527 的士兵,进行哈希运算后,落到 C-A 区域。如下图所示:
士兵所站位置
第二步,让这个士兵顺时针往前走,遇到的第一个节点 A 就是他所在的组了。如下图所示:
顺时针遇到第一个节点
增加分组
目前三个节点的时候,假定编号为 89757 的士兵经过哈希运算后,分配到了 B-C 区域(第三组),也就是属于 C 节点管控。如下图所示:
属于 C 节点
回到刘邦刚问的问题,如果分组变成四组,该怎么进行士兵分配。
如下图所示,增加一个节点 D,原来的区域 B-C 变成了区域 B-D(第三组) 和 D-C(第四组)。
增加 D 节点
那么这名士兵属于哪个节点管控呢?如下图所示,士兵顺时针往前走,先走到了 D 节点,所以属于 D 节点管控。虽然还是属于第三组,但是这名士兵的领导者已经变了:由 C 变成了 D。
领导者变了
从上面的变化来看,只有 B-C 区域中的部分数据会进行迁移:B-D 之间的数据会由 C 节点迁移到 D 节点。
而其他数据不受影响,也不用进行迁移。而且节点越多,需要迁移的数据就越少。这就是多多益善了~
刘邦看了后,大赞韩信:
不亏是大将军,萧何当时月下追你,值了!
哈希环缺陷
萧何看了韩信画的哈希环后,觉得有些不对劲,思索片刻后,对韩信说:
将军,你这个哈希环上的节点分布不太均匀啊,你看第三组和第四组的的区域好小啊。
萧何说得没错,确实存在这个问题,放到互联网架构中,就存在如下问题:
节点分布不均匀,导致业务对节点的访问冷热不均。
韩信眼中充满着赞赏,知我者莫若萧何。然后胸有成竹地说道:
你说得没错,不过我还有一个技能,虚拟节点映射。
三技能:虚拟节点
一般虚拟节点比物理节点要多,并相对均匀地分布在哈希环上。如下图所示,12 个虚拟节点 N1~N12,相对均匀地分布在虚拟节点上。如果有士兵属于 N2/N3/N4 中的某一个,都会重新映射到 A 节点,依次类推,N5/N6/N7 属于 B 节点的虚拟节点映射。
虚拟节点
我们来看下萧何的提出的问题,真实的 B-D 区域比较小,用虚拟节点后,N5/N6/N7 属于 B 节点,N8/N9/N10 属于 D 节点,他们分到的虚拟节点一样多,而且区域大致相等。所以士兵的分配也比较均匀。
感谢各位的阅读,以上就是“如何理解一致性哈希”的内容了,经过本文的学习后,相信大家对如何理解一致性哈希这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是创新互联,小编将为大家推送更多相关知识点的文章,欢迎关注!
新闻标题:如何理解一致性哈希
网站URL:http://scyanting.com/article/ppiojh.html