一致性哈希，Consistent Hashing，用于分布式系统的负载均衡，解决了传统哈希算法的节点扩缩容问题。
分布式系统
在分布式系统中，集群由多台服务器组成，数据采用分布式缓存，期望将数据尽量均匀地分配缓存到各个服务器，每个服务器上有着不同的缓存，以分担压力。请求数据时，再到相应的服务器获取缓存。这部分工作由负载均衡层 LB 来完成。
分布式系统应满足下面要求：
- 对于同一个数据的请求落在相同的服务器上
- 数据分配尽量均匀
- 当服务器数量增减时，尽量减小原有数据分配变化
传统哈希算法
传统哈希算法
哈希算法采用取模运算，基于下面的公式，将 hash 值对机器数量取余，将数据的 key 映射到节点。
扩缩容问题
服务器集群会因为业务量变化需求而扩缩容，增加或减少节点数，此时映射关系发生大量变化，缓存失效，需要进行数据迁移，以保证请求正常。数据迁移规模 O(M)，迁移成本极大，导致服务器瞬时压力巨大。
一致性哈希算法
哈希环
一致性哈希算法引入哈希环解决了扩缩容导致过多数据迁移问题。
一致性哈希算法同样采用了取模的方式，但与传统哈希不同，取模值固定为 $2^{32}$
可以把取模结果当做一个圆环，由 $2^{32}$ 个点组成，先将服务器取模映射到哈希环上，再将数据同样取模映射到环上，选择顺时针找到的第一个服务器存入。
此时添加一个节点，仅有少量的数据需要重新分配映射，大部分位置分配保持不变。
虚拟节点
如果采用节点直接映射，可能存在节点分布不均匀问题，也就是 hash 偏斜。大部分的缓存落在少数几台服务器上，如果该台服务器发生故障，会导致瞬时大量数据迁移。
为了解决 hash 偏斜问题，引入虚拟节点。
将每个服务器映射为多个虚拟节点，数量足够多，以保证均匀分布。数据映射时先找到虚拟节点，再对应到相应的真实节点。
