本文已被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算法由此而生~
一致性哈希算法
具体的算法过程
- 先结构一个长度为2^32-1的整数环（称为一致性hash环），而后给每组redis集群命名，依据名字的hash值计算出每组集群应该放在什么地位
- 依据缓存数据的key计算出hash值，计算出进去的hash值同样也散布在一致性hash环上; 如果当初有5个数据须要缓存对应的key别离为key1、key2、key3、key4、key5，计算hash值之后的分部如下图
- 而后顺着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
外围代码：
测试代码：
- 测试删除节点node3，比照命中率影响了多少 增加如下代码：
执行后果：
- 测试增加节点node5，比照命中率影响了多少 增加如下代码：
执行后果：
其余应用场景
看上图，在Nginx申请的散发过程中，为了让利用本地的缓存命中率最高，咱们心愿依据申请的URL或者URL参数将雷同的申请转发到同一个应用服务器中，这个时候也能够抉择应用一致性hash算法。具体配置能够参考官网文档:
https://www.nginx.com/resources/wiki/modules/consistent_hash/
写到最初（点关注，不迷路）
文中或者会存在或多或少的有余、谬误之处，有倡议或者意见也十分欢送大家在评论交换。
最初，白嫖不好，创作不易，心愿敌人们能够点赞评论关注三连，因为这些就是我分享的全副能源起源????
原创不易 转载请注明出处：https://mp.weixin.qq.com/s/eCxGPqrfIeFY_E_CnFRfMw
发表回复