一致性 Hash 算法 Java 版实现

本文已被 Github 仓库收录 https://github.com/silently9527/JavaCore

微信公众号：贝塔学 Java

前言

在之前写了两篇关于缓存的文章《万字长文聊缓存（上）- http 缓存》《万字长文聊缓存（下）- 应用级缓存》，谈到缓存不说一下一致性 Hash 算法那就是在耍流氓。

分布式缓存集群的访问模型

现在通常使用 Redis 来做分布式缓存，下面我们就以 Redis 为例：

假如当前我们系统的业务发展很快，需要缓存的数据很多，所以我们做了一个由三组主从复制的 redis 组成的高可用的 redis 集群，如何将请求路由的不同的 redis 集群上，这是我们需要考虑的，常用的路由算法：

随机算法：每次将请求随机的发送到其中一组 Redis 集群中，这种算法的好处是请求会被均匀的分发到每组 Redis 集群上；缺点也很明显，由于随机分发请求，为了提高缓存的命中率，所以同一份数据需要在每组集群中都存在，这样就会造成了数据的冗余，浪费了存储空间

Hash 算法：针对随机算法的问题，我们可以考虑 Hash 算法，举例：

现在有三组 redis 集群，我们可以对每次缓存 key 的 hash 值取模，公式：index=hash(key) % 3，index 的值就对应着 3 组集群，这样就可以保证同一个请求每次都被分发到同一个 redis 集群上，无需对数据做冗余，完美的解决了刚才随机算法的缺点；

但是 hash 算法也有缺点：对于容错性和伸缩性支持很差，举例：当我们三组 redis 集群中其中一组节点宕机了，那么此时的 redis 集群中可用的数量变成了 2，公式变成了index=hash(key) % 2， 所有数据缓存的节点位置就发生了变化，造成缓存的命中率直线下降；

同理，当我们需要扩展一组新的 redis 机器，计算的公式index=hash(key) % 4，大量的 key 会被重新定位到其他服务器，也会造成缓存的命中率下降。

为了解决 hash 算法容错性和伸缩性的问题，一致性 hash 算法由此而生~

一致性哈希算法

具体的算法过程

1. 先构造一个长度为 2^32-1 的整数环（称为一致性 hash 环），然后给每组 redis 集群命名，根据名字的 hash 值计算出每组集群应该放在什么位置

1. 根据缓存数据的 key 计算出 hash 值，计算出出来的 hash 值同样也分布在一致性 hash 环上; 假如现在有 5 个数据需要缓存对应的 key 分别为 key1、key2、key3、key4、key5，计算 hash 值之后的分部如下图

1. 然后顺着 hash 环顺时针方向查找 reids 集群，把数据存放到最近的集群上

最后所有 key4、key5 存放在了集群 2，key1、key3 存放在了集群 1，key2 存放在了集群 3

容错性

还是继续沿用上面的例子，我们来看下一致性哈希算法的容错性如何呢？假如其中 集群 1 跪了，那么影响的数据只有 key1 和 key3，其他数据存放的位置不受影响；当再次缓存 key1、key3 的时候根据顺时针查找，会把数据存放到集群 3 上面

伸缩性

如果我们需要在当前的基础上再添加一组 redis 集群 4，根据名字 hash 之后的位置在集群 1 和集群 2 之间

新加 redis 集群 4 之后影响的只有 key1 数据，其他数据不受影响。

数据倾斜问题

经过容错性、伸缩性的验证证明了一致性哈希算法确实能解决 Hash 算法的问题，但是现在的算法就是完美的吗？让我们继续来看刚才容错性的例子，加入集群 1 跪了，那么原来落在集群 1 上的所有数据会直接落在集群 3 上面，如果说每组 redis 集群的配置都是一样的，那么集群 3 的压力会增大，数据分布不均匀造成数据倾斜问题。

怎么搞呢？

歪果仁的脑子就是好使，给的解决方案就是加一层虚拟层，假如每组集群都分配了 2 个虚拟节点

集群 | 虚拟节点

---|---

集群 1 | vnode1, vnode2

集群 2 | vnode3, vnode4

集群 3 | vnode5, vnode6

接下来就是把虚拟节点放入到一致性 hash 环上，在缓存数据的时候根据顺时针查找虚拟节点，在根据虚拟节点的和实际集群的对应关系把数据存放到 redis 集群，这样数据就会均匀的分布到各组集群中。

这时候如果有一组 redis 集群出现了问题，那么这组集群上面的 key 会相对均匀的分摊到其他集群上。

从上面的结果来看，只要每组集群对应的虚拟节点越多，那么各个物理集群的数据分布越均匀，当新增加或者减少物理集群影响也会最小，但是如果虚拟节点太多会影响查找的性能，太少数据又会不均匀，那么多少合适呢？根据一些大神的经验给出的建议是 150 个虚拟节点。

一致性 Hash 算法 Java 版实现

实现思路：在每次添加物理节点的时候，根据物理节点的名字生成虚拟节点的名字，把虚拟节点的名字求 hash 值，然后把 hash 值作为 key，物理节点作为 value 存放到 Map 中；这里我们选择使用 TreeMap，因为需要 key 是顺序的存储；在计算数据 key 需要存放到哪个物理节点时，先计算出 key 的 hash 值，然后调用 TreeMap.tailMap()返回比 hash 值大的 map 子集，如果子集为空就需要把 TreeMap 的第一个元素返回，如果不为空，那么取子集中的第一个元素。

> 不扯废话，直接上代码，No BB . Show me the code

核心代码：

测试代码：

1. 测试删除节点 node3，对比命中率影响了多少 添加如下代码：

执行结果：

1. 测试添加节点 node5，对比命中率影响了多少 添加如下代码：

执行结果：

其他使用场景

看上图，在 Nginx 请求的分发过程中，为了让应用本地的缓存命中率最高，我们希望根据请求的 URL 或者 URL 参数将相同的请求转发到同一个应用服务器中，这个时候也可以选择使用一致性 hash 算法。具体配置可以参考官方文档:

https://www.nginx.com/resources/wiki/modules/consistent_hash/

写到最后（点关注，不迷路）

文中或许会存在或多或少的不足、错误之处，有建议或者意见也非常欢迎大家在评论交流。

最后，白嫖不好，创作不易，希望朋友们可以点赞评论关注三连，因为这些就是我分享的全部动力来源🙏

原创不易 转载请注明出处：https://mp.weixin.qq.com/s/eCxGPqrfIeFYECnFRfMw