一致性哈希机器在分布式中的作用

▲点击蓝字,轻松关注 公众号回复“1”,拉你进区块链技术讨论微信群
https://mmbiz.qpic.cn/mmbiz_png/9ltY7SLLaAFj4DNGChrNicYwvjLicTT6Nib5k01Oa6gxXmfBosr8VBNJibnqVILrd4WGvQeaAtVFBfE5XD8WXK5JyA/640?wx_fmt=png
作者:佚名 来源:CSDN 原文链接:http://tinyurl.com/ycqtmhgt 著权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 本文约1500字+,阅读(观看)需要9分钟 哈希算法是根据hash值将不同的value映射到相应的位置的过程。 那么在分布式中,【比如memcached】,需要将不同的缓存对象按照相应的hash算法映射到相应的机器上去,那么当添加一台机器或者是其中某一台机器宕机之后,如果按照最原始的key%n的形式来做hash的话,需要将缓存清空,然后重新将内容映射到所有的机器上,这样的代价是巨大的。 于是粗线了一致性哈希。简单来说,一致性哈希将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数H的值空间为0~2^32-1,整个空间按顺时针方向组织。0和232-1在零点中方向重合。 下一步将服务器使用H【hash算法】进行哈希(具体可以选择服务器的ip或主机名作为关键字进行哈希),映射到哈希环上的某个位置,这里假设将三台服务器使用ip地址哈希后在环空间的位置如下:
https://mmbiz.qpic.cn/mmbiz_png/9ltY7SLLaAFj4DNGChrNicYwvjLicTT6NibYQF184oXCyaBcdick7ic3SAXHXG4bhOzGphW8umZbIia3t13TevWiaAQeA/640?wx_fmt=png
服务器布置好之后,就要映射数据了。 使用如下算法映射数据到相应服务器:将数据key使用相同的函数H【hash算法】计算出哈希值h【根据h确定此数据在环上的位置】。从此位置沿环顺时针“行走”,第一台遇到的服务器就是其应该映射到的服务器。 例如我们有A、B、C、D四个数据对象,经过哈希计算后,在环空间上的位置如下:
https://mmbiz.qpic.cn/mmbiz_png/9ltY7SLLaAFj4DNGChrNicYwvjLicTT6NibZAXvpKmESa5Q2WsWCWibOGedOOtuIjoyHXOv1hdD6jAQpYUVjI68Lng/640?wx_fmt=png
根据一致性哈希算法,数据A会被定为到Server 1上,D被定为到Server 3上,而B、C分别被定为到Server 2上。 上面是讲一致性哈希的服务器布置和key-value的映射过程。 下面说一致性哈希的扩展性和容错性。 现假设Server 3宕机了:
https://mmbiz.qpic.cn/mmbiz_png/9ltY7SLLaAFj4DNGChrNicYwvjLicTT6Nibly7NUpSeezfqlN37N0NfFM0zfJvRganUgTxMHnN1G6eUuMlzo7TI4Q/640?wx_fmt=png
可以看到此时A、C、B不会受到影响,只有D节点被重定位到Server 2【这在分布式中是很好定位的,比如说server3宕机了,那么根据一致性哈希算反,查找的时候,会发现D在server2上,但是在server3刚刚宕机的时候,server2上并没有D,此时应用会把数据缓存到server2上,此时,D就被hash到server2上了】。 下面考虑另外一种情况,如果我们在系统中增加一台服务器Memcached Server 4:
https://mmbiz.qpic.cn/mmbiz_png/9ltY7SLLaAFj4DNGChrNicYwvjLicTT6NibfU1SIJwVxmab7m1HwhrDz8VPS7tXcTzIia3kFibRaEVZ1oeEuLdYldzA/640?wx_fmt=png
此时,B不会去server2查找数据了,而会在server4上查找,如果B此时不存在于server4上,那么会缓存从数据库取回来的B在server4上。而server2上的数据,会因为时间太久没有被访问或者是因为超时而被memcached清理掉了。综上所述,一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据,具有较好的容错性和可扩展性。 当然,万物都是有两面性的。 一致性哈希算法在服务节点太少时,容易因为节点分部不均匀而造成数据倾斜问题。例如我们的系统中有两台服务器,其环分布如下:
https://mmbiz.qpic.cn/mmbiz_png/9ltY7SLLaAFj4DNGChrNicYwvjLicTT6NibIKhWicM7EVwXPYWJnZSuDEqKnfySKibv6dxK6Vt2P3wBBR5ibNofeGVXg/640?wx_fmt=png
那么此时数据大部分会存到server1中,而2中会因为距离1太近而有很少的数据。为了解决这种数据倾斜问题,一致性哈希算法引入了虚拟节点机制,即对每一个服务节点计算多个哈希【具体可以这么做:根据服务器的名字或者是ip计算节点hash的时候,可以加上编号,然后再计算哈希值】,在每个计算的结果位置都放置一个服务节点,称为虚拟节点。这样,数据再被存储的时候,就不会因为服务器在环上的间距太大而导致“数据倾斜”了。 至于Memcached 的分布式,则完全由客户端实现。这种分布式是Memcached最大的特点。 目前一致性哈希是分布式的标准配置。 文章发布只为分享区块链技术内容,版权归原作者所有,观点仅代表作者本人,绝不代表区块链兄弟赞同其观点或证实其描述。 猜猜你喜欢 3月24日“链接未来”区块链专场招聘会,等你来撩! “超级账本面对面”系列 Meetup 之 Hyperledger 与区块链技术应用落地研讨会 报名开启! 关于Hyperledger Fabric 1.0网络节点的分类汇总 [h3]未来的分布式账本技术:不是区块链,会是哈希图? [/h3] 一图流 | 你不可不知的177个区块链应用项目汇总 区块链从业者DE狗年求职指南
https://mmbiz.qpic.cn/mmbiz_jpg/9ltY7SLLaAEjs6bdHbQrByiaGfohf66PXlMxxKyrYIhnyu171QMfN0IRGKsAVic6gH2RIhDpc7rmxiahKlUwiaahMQ/640?wx_fmt=jpeg
点击“阅读原文”参与3月24日Hyperledger 与区块链技术应用落地研讨会,和大咖一起畅谈区块链。

0 个评论

要回复文章请先登录注册