一致性Hash

分布式缓存

为了提高Redis缓存的读写能力，一般会建一个Redis集群，此时我们就需要通过hash算法将key存储到指定的一台节点中，这样每次取这个key的时候到key对应的节点中去获取即可

假如现在有10台Redis，计算key对应的节点的hash公式如下:

node = hash(key)%10

静态分配策略在集群节点数量固定的时候是没问题的，但是当集群节点数量进行动态扩缩的情况下就会出现 缓存雪崩 问题

比如现在新加了10个节点，那么上面的公式就变成了如下:

node = hash(key)%20

也就是说之前所有的key计算出的节点在集群扩大的时候再次计算时就可能不是同一个节点，那么就无法在对应节点中获取到key的缓存。如果这样的key数量很多的话就会造成缓存雪崩问题，那么后端数据库的压力就会在集群扩容的时候剧增

为了解决这个问题，于是就有了后面的 一致性Hash算法

​

一致性Hash算法

一致性hash算法将节点映射到这个环上，同时也将key映射到一个2^32大小的环上，并且沿着key所在的位置顺时针查找，找到的第一个节点就是这个key要保存的节点

如果加了一个node或则减少了一个node，那么只会影响环上的node顺时针对应的前一个node之间的数据

​

节点倾斜问题

当hash环上的节点数量较少时就可能造成节点倾斜问题，比如所有节点都被映射到了同一边的一个角落，那么就会有大量的key只存在一个node上，而其他node则没有多少key

为了解决节点倾斜问题，引入了 虚拟节点 。 就是在每个实际的节点下虚拟出几个不存在的节点将其映射到hash环上，让hash环上节点分布的比较均匀。如果key保存在虚拟节点上，则实际上是保存在这个虚拟节点对应的实际节点中。通过虚拟节点就解决了数据倾斜问题

​

参考

好刚: 7分钟视频详解一致性hash 算法

一致性hash