关于java:一致性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 个虚构节点

接下来就是把虚构节点放入到一致性 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/eCxGPqrfIeFY_E_CnFRfMw