韩信大招,一致性哈希 (2)

那么这名士兵属于哪个节点管控呢?如下图所示,士兵顺时针往前走,先走到了 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 节点,他们分到的虚拟节点一样多,而且区域大致相等。所以士兵的分配也比较均匀。

萧何看了韩信的三技能后,直呼:妙哉妙哉!

总结

本篇通过韩信点兵的故事,然后从故事中衍生出刘邦、韩信、萧何的对话,来讲解士兵的分组的问题。现在对故事中的知识点做一个总结:

哈希算法会带来增加或删除节点时,数据迁移量太大的问题。

一致性哈希算法降低了数据迁移量。

节点较少,哈希环上每个节点实际占据的区间大小不一,最终导致业务对节点的访问冷热不均

引入虚拟节点映射解决了分布不均问题。

节点越多时,使用哈希算法时,需要迁移的数据就越多,而使用一致性哈希算法,迁移的数据就越少

一致性哈希算法本质上是一种路由寻址算法,适合简单的路由寻址场景。

一致性哈希算法常用在负载均衡的架构设计中。

封面图片来源王者荣耀。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wssgxp.html