一致性hash原理及解决方案

解决方案：环状 hash 法

思路

1.首先我们将各个节点映射到一个 2^32 的 hash 环上，计算的来源可以是 ip 地址，或者是唯一host名

2.然后计算缓存 key 的 hash 值，也映射到 hash 环上，再沿着环顺时针找到第一个节点 node，存进去。（这一步一般用 TreeMap 数据结构来实现，它自带的 ceilingEntry() 就是找距离目标 hash 值最近且大的节点 entry。）

3.发生节点扩容，缩容时，只需要调整一个区间内的 key

扩容：

如何解决固定节点下，使用上述 hash 算法分配可能导致的数据倾斜问题？

答：使用虚拟节点，虚拟节点均匀地分割整个 hash 环。当数据写入时，写入位置不在根据真实节点 hash 值去决定，而是根据虚拟节点 hash 值去决定。保证数据尽可能 均匀 地写入所有节点。

4.解决当存储节点较少且在 hash 环上分配不均匀时所造成的 热点 node 问题，可引入虚拟节点解决。具体方法是让所有节点都尽量映射到等量的虚拟节点上，且虚拟节点分布也呈现均匀趋势。