一致性哈希

Hash取模

缺点

• 节点出现宕机，哈希需要重新调整，数据迁移较多，缓存场景会出现缓存击穿，甚至缓存雪崩
• 节点扩容，哈希需要重新调整，问题同上

一致性哈希算法

基本思想

固定N，避免了N的变动

• Karger的一致性哈希算法将N设置为2^32，形成了一个0~(2^32-1）的哈希环，也就是相当于普通Hash取模时N=2^32。
• 将服务器结点也作为一种key分发到哈希环上，顺时针方法实现结点对哈希环shard的归属
• 引入虚拟节点，解决一致性哈希的数据倾斜

增加节点

部分数据需要迁移到新增节点和其虚拟节点上

删除节点

删除节点及其虚拟节点，顺时针迁移到下一个实体结点或者虚拟结点。

应用

Redis cluster 拥有固定的16384个slot，slot是虚拟的且被分布到各个master中，当key 映射到某个master 负责slot时，就由对应的master为key 提供服务。

参考

https://zhuanlan.zhihu.com/p/92742908