当前访客身份:游客 [ 登录  | 注册加入尚学堂]
直播

helloworld

拥有积分:8266
莫问前路在何方!!!!

博客分类

笔记中心

课题中心

提问中心

答题中心

解答题中心

一致性哈希算法是分布式系统中常用的算法

helloworld 发表于 2年前 (2014-12-31 11:17:26)  |  评论(0)  |  阅读次数(586)| 0 人收藏此文章,   我要收藏   

  一致性哈希算法是分布式系统中常用的算法。比如,一个分布式的存储系统,要将数据存储到具体的节点上,如果采用普通的hash方法,将数据映射到具体的节点上,如key%Nkey是数据的keyN是机器节点数,如果有一个机器加入或退出这个集群,则所有的数据映射都无效了,如果是持久化存储则要做数据迁移,如果是分布式缓存,则其他缓存就失效了。

    因此,引入了一致性哈希算法:

http://hi.csdn.net/attachment/201112/11/0_1323584764ZUEE.gif

把数据用hash函数(如MD5),映射到一个很大的空间里,如图所示。数据的存储时,先得到一个hash值,对应到这个环中的每个位置,如k1对应到了图中所示的位置,然后沿顺时针找到一个机器节点B,将k1存储到B这个节点中。

如果B节点宕机了,则B上的数据就会落到C节点上,如下图所示:

http://hi.csdn.net/attachment/201112/11/0_1323584790SV6N.gif

这样,只会影响C节点,对其他的节点AD的数据不会造成影响。然而,这又会造成一个雪崩的情况,即C节点由于承担了B节点的数据,所以C节点的负载会变高,C节点很容易也宕机,这样依次下去,这样造成整个集群都挂了。

       为此,引入了虚拟节点的概念:即把想象在这个环上有很多虚拟节点,数据的存储是沿着环的顺时针方向找一个虚拟节点,每个虚拟节点都会关联到一个真实节点,如下图所使用:

http://hi.csdn.net/attachment/201112/11/0_1323584813E98e.gif

图中的A1A2B1B2C1C2D1D2都是虚拟节点,机器A负载存储A1A2的数据,机器B负载存储B1B2的数据,机器C负载存储C1C2的数据。由于这些虚拟节点数量很多,均匀分布,因此不会造成雪崩现象。

 

附件下载:

分享到:0
关注微信,跟着我们扩展技术视野。每天推送IT新技术文章,每周聚焦一门新技术。微信二维码如下:
微信公众账号:尚学堂(微信号:bjsxt-java)
声明:博客文章版权属于原创作者,受法律保护。如果侵犯了您的权利,请联系管理员,我们将及时删除!
(邮箱:webmaster#sxt.cn(#换为@))
北京总部地址:北京市海淀区西三旗桥东建材城西路85号神州科技园B座三层尚学堂 咨询电话:400-009-1906 010-56233821
Copyright 2007-2015 北京尚学堂科技有限公司 京ICP备13018289号-1 京公网安备11010802015183