一致性Hash

本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

转载声明:转载请注明出处,本技术博客是本人原创文章

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

原文链接:blog.ouyangsihai.cn >> 一致性Hash

来源:xy的技术圈

Hash算法

凡是涉及到分布式的系统,就会有负载均衡和数据分布的问题。为了让连接(或者数据)能够分布得更均匀,很多时候会使用到Hash算法。

那什么是Hash算法呢?

把任意长度的输入,通过Hash算法变换成固定长度的输出,这个输出就是Hash值。哈希值的空间远小于输入的空间,所以可能会发生“哈希碰撞”,即两个不同的输入,产生了同一个输出。

Hash算法只是一个定义,并没有规定具体的实现。

具体有什么应用场景?

Hash算法常用于消息摘要的场景,开发者们或多或少听说过的MD5、SHA都属于Hash算法的实现。

在Java语言里,每个Object对象都有一个hashCode方法,它默认是根据对象的内存地址计算的Hash值。当然我们可以覆盖这个方法,用自己的方法去计算得出一个Hash值。

Hash取模

先Hash再取模的场景,在负载均衡中十分常见。

hash(request) % n

假设我们现在有3个服务器,想要做负载均衡,就可以对请求的ip地址或者用户的id等使用Hash函数,然后将计算得出的Hash值对3取模,余数为几,就把请求分配到相应的服务器上。如图:

一致性Hash

这里为了演示方便,直接模拟用的hash后的值。

弊端?

那上述方法有什么弊端呢?

在分布式场景下,横向伸缩缩是一个很正常的需求。试想一下,当上述的3台服务器需要扩展到4台服务器时,那绝大多数请求基本上都需要重新映射到另一个节点。因为Hash值没变,除数变了,余数必然会变。如图:

一致性Hash

这种变动有时候是不能接受的。比如在Web负载均衡的场景下,session会保存在每个节点里。当然,如果你是“无状态”的服务,那不会存在这个问题。但如果是数据持久化场景,比如前面的文章里提到的MySQL分库分表,这样大的变动显然是不能接受的。因为如果增加或者删除了一个节点,就会导致几乎所有的数据都需要重新迁移。

无状态服务指的是,应用不保存任何状态。比如不用session,或者session保存在第三方缓存的节点里。

一致性Hash

使用一致性Hash可以解决因为横向伸缩导致的大规模数据变动。它是怎么解决的呢?

前面说到用节点的数量作为除数去求余。而一致性Hash的除数是2^32。从0到2^32 - 1,首尾相连构成了一个环。我们先对服务器节点的IP进行Hash,然后除以2^32得到服务器节点在这个Hash环中的位置:

一致性Hash

现在有请求进来了,同样进行Hash然后处于2^32求余。如果落在Hash环上,然后顺时针找到第一个节点,这个节点就负责处理这个请求。如图所示:

一致性Hash

一致性Hash分布不均匀的问题

细心的读者可能发现,一致性Hash算法在节点数量较少的时候,会出现分布不均匀的问题。如图所示:

一致性Hash

这个时候,绝大多数请求都分配到了A节点,而B节点和C节点分配到的请求很少。解决这个问题的方案就是在Hash环上增加虚拟节点。实现方式也有很多种,比如:

hash(“SERVER_IP_A#1”) % 2^32
hash(“SERVER_IP_A#2”) % 2^32
hash(“SERVER_IP_A#3”) % 2^32

hash(“SERVER_IP_A#2”) % 2^32

一致性Hash

一致性Hash的应用场景?

讲了这么多,一致性Hash到底有什么用?

除了前面提到的负载均衡、Web session和数据库分库分表可以应用外,其实一致性Hash应用得最多的领域是分布式缓存。

分布式缓存系统一般是对Key进行Hash的。试想一下,如果直接对节点数量取模,一旦节点数量发生变化,比如新增一个节点或者删除一个节点,那将使得几乎所有结点的缓存失效。而如果使用一致性Hash,就只有Hash环上相邻的节点缓存受到影响。

从Hash环和顺时针查找原理不难发现,在增加一个节点后,一些原来被分配到下一个节点的请求,被分配到了新的节点。在减少一个节点后,一些原来本分配到这个节点的请求,被分配到了下一个节点。

所以无论是增加还是减少一个节点,都只有下一个相邻的节点会被影响而已。

推荐阅读(点击即可跳转阅读)

1.SpringBoot内容聚合

2.面试题内容聚合

3.设计模式内容聚合

4.Mybatis内容聚合

5.多线程内容聚合

觉得不错?欢迎转发分享给更多人

一致性Hash

我知道你 “在看一致性Hash

原文始发于微信公众号(Java知音):一致性Hash

本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

转载声明:转载请注明出处,本技术博客是本人原创文章

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

原文链接:blog.ouyangsihai.cn >> 一致性Hash


  转载请注明: 好好学java 一致性Hash

 上一篇
LinkedList真的是查找慢增删快? LinkedList真的是查找慢增删快?
点击上方“Java知音”,选择“置顶公众号” 技术文章第一时间送达! 作者:你在我家门口 juejin.im/post/5c00987de51d451aa843b67b juejin.im/post/5
下一篇 
感受lambda之美,推荐收藏,需要时查阅 感受lambda之美,推荐收藏,需要时查阅
点击上方“Java知音”,选择“置顶公众号” 技术文章第一时间送达! 作者:9龙 juejin.im/post/5ce66801e51d455d850d3a4a juejin.im/post/5ce668