用韩信三技能,讲清楚一致性哈希
刘邦:“你觉得我可以带兵多少?” 韩信:“最多十万。” 刘邦不解的问:“那你呢?” 韩信自豪地说:“越多越好,多多益善嘛!
刘邦:韩将军,你看这些士兵怎么分配好呢? 韩信:这还不简单,我的一技能就能搞定。
一技能:哈希算法
分组
哈希算法
:将士兵的编号 num 值当做一个哈希值,再和总做小组数 N 做取余操作,得出的结果在 0 到 N - 1 之间,这个士兵就属于那个组。
查找士兵
哈希分组弊端
韩将军真是厉害。 哈希算法看起来很完美,那我再给你五百士兵,需要分成四个组怎么办?
这还不简单,再用 4 取余不就好了吗?
这个方案可行,但很多士兵都被重新分组了,刚刚建立的团队友情就被分解了。
主公,您说得没错,这就是我的一技能的 弱点
所在。不过我还有一个技能: 一致性哈希
。
二技能:一致性哈希
哈希环
-
哈希算法:对节点的数量进行取模运算。 -
一致性哈希算法:对 2^32 进行取模运算。
哈希环
。
2^32
的哈希环中。三个组一共将整个环分成了三个区域,C-A(第一组)、A-B(第二组)、B-C(第三组)。如下图所示:
-
第一组负责存储落在 C-A 区间内的数据。 -
第二组负责存储落在 A-B 区间内的数据。 -
第三组负责存储落在 B-C 区间内的数据。
士兵分配
增加分组
迁移
到 D 节点。
不愧是大将军,萧何当时月下追你,值了!
哈希环缺陷
将军,你这个哈希环上的节点分布 不太均匀
啊,你看第三组和第四组的的区域好小啊。
你说得没错,不过我还有一个技能, 虚拟节点映射
。
三技能:虚拟节点
萧何看了韩信的三技能后,直呼:妙哉妙哉!
总结
-
哈希算法会带来增加或删除节点时,数据迁移量太大的问题。 -
一致性哈希算法降低了数据迁移量。 -
节点较少,哈希环上每个节点实际占据的区间大小不一,最终导致业务对节点的访问冷热不均。 -
引入虚拟节点映射解决了分布不均问题。 -
节点越多时,使用哈希算法时,需要迁移的数据就越多,而使用一致性哈希算法,迁移的数据就越少。
-
一致性哈希算法本质上是一种路由寻址算法,适合简单的路由寻址场景。
-
一致性哈希算法常用在负载均衡的架构设计中。
福 利
CSDN给大家发压岁钱啦!
2月4日到2月11日每天上午11点
价值198元的芒果TV年卡,价值99元的CSDN月卡!现金红包,CSDN电子书月卡等奖品大放送!百分百中奖!
更多精彩推荐
点分享 点收藏 点点赞 点在看