一致性 Hash 原理

一致性哈希是啥?

引用百度百科的一段介绍:一致性哈希算法在1997年由麻省理工学院提出,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中真正得到应用。

什么情况下我们要用到一致性哈希?

一致性 hash 在分布式系统中应用较为广泛。例如,Redis 集群便是一个典型的例子。常见的生产环境中,为了提高 Redis 的读写性能以及高可用,最常见的方式就是做主从复制,组成 Master-MasterMaster-Slave 的形式,或者搭建 Redis 集群,进行数据读写分离,类似数据库的主从复制读写分离
同样,与数据库类似,单表数据过大时就需要对其进行分库。对于 Redis 也是一样的。数据量过大时,同样需要进行类似操作。但是,Redis 没有提供分库分表的功能。只能自己定义规则。常见的可以使用随机存储,随机存储就会有一个问题,存完之后你也不知道存在了那个服务器,假设现在有 8 台服务器,两两相对进行主从复制的方式成为 4 个节点的集群。如果需要在其中查询数据,则需要遍历 4 台服务器。显然,这样是不合理的。可能你就会想到,用键做 HASH,用 HASH 值取余获得固定的服务器。这样读写都在这台服务器进行。

Redis 怎么进行请求优化?

那么,接下来想一下在 Redis 中使用 HASH 的可行性。
举个栗子:现在有 5 台 Redis 服务器,对所有服务器进行编号,分别为0、1、2、3、4,现在要将图片存入 Redis 中,key 为图片名称,value 为图片 URL。存储与读取时,对 key 进行计算 hash(图片名称) % 5,取余因数视服务器个数而定。计算得到固定编号的服务器。取余 5 的结果必然就是 0~4 之间。
因此,要保证图片名称不会重复。所以,对同一个图片的 HASH 结果也就不变。则,不管是写入还是读取,访问的都是同一台服务器。

只使用 HASH 会出现什么问题?

使用 HASH 虽然提升了性能,但却并不完善。因为如果需要扩展添加服务器,或者有服务器故障退出。那么,因为取余因数改变。所有的存储位置都会改变,此时,就会出现大面积的 key 失效,从而导致 雪崩

一致性哈希是如何处理这种情况的?

前面提到了 HASH 的弊端,容易导致雪崩的出现,那么一致性哈希又是怎么处理的?下面看一下,一致性哈希的整体概念。我想你就会知道它是如何避免这个问题的了。
一致性哈希同样是使用取余的方式,只是取余的因数固定为 2^32。因为哈希的值为 32 位的整数值。这样就形成了一个 0~2^32-1 之间的闭环。这个闭环有个专业名称 哈希环。计算公式为:

1
HASH(serverIP) % 2^32

一致性哈希规定,这个哈希环以顺时针方式,依次排列。即原点为 0 然后顺时针排列在后面的为 2、3、4….2^32-1。
还是上面的栗子,5 台Redis服务器,依次将其进行哈希计算,然后再取余 2^32 就可以得到一个在环上的落点。如下:
图片加载失败...
那么,在一个客户端请求过来时,对其进行哈希取余。同样也可以获得一个对应的哈希环的落点。如下图:
图片加载失败...
计算出请求的落点之后,顺时针找到最近的一个服务器进行路由。如下图:
图片加载失败...
到这里可能会疑问为什么因数是 2的32次方,因为 int 占用 4 个字节,正负数都是在 2^31 之间。

一致性哈希的可扩展性与容错性

这个说白了就是:新增服务器时,或者有服务器因为故障退出时,对集群的影响程度。这也是分布式中需要解决的一个大问题。如果这两个方面处理不好,则也就不是一个好的解决方案。
然而,一致性哈希,在这方面解决的很好。
首先,在增加新机器的时候,只需要在计算之后在哈希环上新增一个落点即可。因为每次请求都会进行哈希计算,所以会自动的路由到新增的机器上。如下图:
图片加载失败...
如上,假设,有一个新的节点加入集群,则 Request2 的请求将会被分配到新的节点中。
其次,如果有机器因为故障退出,也会自动分配路由到其他机器处理,待修复重新加入集群之后则会自动路由到该机器。
图片加载失败...
如上,如果 IP4 节点因为故障退出集群,则 Request2 与 Request3 会被路由到 IP5 节点。这样改变的只有 IP5 上存储的数据,可以将影响降低到最低。

一致性哈希如何避免数据倾斜?

如果集群中的节点过少,则容易出现数据倾斜的问题,因为我们也无法保证 IP 经过哈希之后,在 哈希环 上落点位置的绝对平衡。就如下图一样:
图片加载失败...
如果出现这个问题,那么 IP1 将会处理大部分的请求,而 IP2 则在一边优哉游哉的坐山观虎斗。这样不能很好的运用两台机器的性能。要解决这个问题,就需要一个新的概念 虚拟节点
那么,何为 虚拟节点 呢?虚拟节点 简单的可以理解为,给机器起个别名,用别名哈希,加入 哈希环 中。路由到这个别名的请求也就是路由到真实的那台机器中。
既然不能确定请求的哈希落点,也不能确认服务器IP的哈希落点。那么就可以灵活的增加多个虚拟的节点,让整个哈希环更加的充实、均衡。具体效果如下图:
图片加载失败...
如上,真实的只有 IP1 与 IP2 两个节点,每个节点添加两个虚拟节点。这样整个哈希环就可以更加的充实。这里只是为了说明,每个节点只有两个虚拟节点。一般生产环境中,可以使用更多的虚拟节点,使你的哈希环更加充实。请求路由也更加的平衡。