分布式缓存集群的访问模型现在通常使用Redis来做分布式缓存,下面我们就以Redis为例: 假如当前我们系统的业务发展很快,需要缓存的数据很多,所以我们做了一个由三组主从复制的redis组成的高可用的redis集群,如何将请求路由的不同的redis集群上,这是我们需要考虑的,常用的路由算法: 「随机算法」:每次将请求随机的发送到其中一组Redis集群中,这种算法的好处是请求会被均匀的分发到每组Redis集群上;缺点也很明显,由于随机分发请求,为了提高缓存的命中率,所以同一份数据需要在每组集群中都存在,这样就会造成了数据的冗余,浪费了存储空间 「Hash算法」:针对随机算法的问题,我们可以考虑Hash算法,举例:现在有三组redis集群,我们可以对每次缓存key的hash值取模,公式: 但是hash算法也有缺点:对于容错性和伸缩性支持很差,举例:当我们三组redis集群中其中一组节点宕机了,那么此时的redis集群中可用的数量变成了2,公式变成了 同理,当我们需要扩展一组新的redis机器,计算的公式 为了解决hash算法容错性和伸缩性的问题,一致性hash算法由此而生~ 一致性哈希算法具体的算法过程
最后所有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的第一个元素返回,如果不为空,那么取子集中的第一个元素。 ❝ 核心代码:测试代码:
执行结果:
执行结果: 其他使用场景看上图,在Nginx请求的分发过程中,为了让应用本地的缓存命中率最高,我们希望根据请求的URL或者URL参数将相同的请求转发到同一个应用服务器中,这个时候也可以选择使用一致性hash算法。具体配置可以参考官方文档:https://www./resources/wiki/modules/consistent_hash/ 源码地址:https://github.com/silently9527/JavaCore
|
|