共计 1449 个字符，预计需要花费 4 分钟才能阅读完成。
一致性哈希算法
1. 基本场景
在电商服务中, 热点商品信息存储在 Redis 缓存中。数据量小的场景下，使用单个节点存储。随着数据量的增加，通常采用多节点集群模式管理。
2. 哈希取模
将请求均匀分配到各个服务器节点。假设有 4 个 Redis 服务节点，可以取商品对象 hash 值，通过算法 hash(object)/(4) 均匀映射到每个服务节点
3. 哈希取模的缺陷
扩容导致的灾难
当 Redis 服务器从 4 个扩容到 5 个，我们发现只有 4 个对象可以命中缓存（图中绿色的点），导致其他大量的请求穿透缓存，压力全部到数据库，后果不可预料。
解决方案：成倍扩容
我们发现 hash 分布的结果是关键，可以将 Redis 服务器从 4 个扩容到 8 个这样成倍的扩容。已经通过哈希分派到了相应的缓存，原有的映射才不会改变。
成倍的扩容似乎解决了扩容问题，但是成倍扩容会导致资源的浪费，而且集群的收缩性不是很好。更重要的是，Redis 服务器故障移除时，同样导致上述的穿透缓存问题。为了解决缓存服务器数量发生变化导致的问题，我们引入了一致性哈希算法
4. 一致性哈希算法
一致性哈希算法仍然是取模的算法。一致性 Hash 算法将整个哈希值空间组织成一个虚拟的圆环，通常哈希函数值空间为 0 -2^32-1.
假设我们有 4 台服务器，Redis-1（10.0.1.156），Redis-1（10.1.2.145），Redis-1（10.2.3.112），Redis-1（10.6.4.231）
我们使用一个简单的 hash 函数：hash(Redis-1) = 1001156，将服务器映射到哈希环。
可以看到，4 个节点将哈希环分为 4 个部分. 假设有个商品 A 的 Hash 值为 2157132，找到在 hash 环上的范围 1064231～1001156，然后顺时针查找第一个服务器节点 Redis-1，就是我们的缓存节点。以此类推图中 4 个商品存储在哪个缓存节点上。
5. 一致性哈希算法的优点
一致性哈希算法是否解决了缓存服务器数量发生变化导致的问题？
我们假设节点 Redis- 1 故障了，商品 A 的 Hash 值为 2157132，找到在 hash 环上的位置，然后顺时针查找第一个服务器节点 Redis-2.Hash 值落在其他区间的对象和服务器的映射关系没有收到影响。
我们新增节点 Redis-5（1072132），商品 A 的 Hash 值为 2157132，找到在 hash 环上的范围 1064231～1072132，然后顺时针查找第一个服务器节点 Redis-5. Hash 值落在其他区间的对象和服务器的映射关系没有收到影响。
当服务器节点发生变更，只有部分缓存失效，不会出现大范围缓存失效的问题。
6. Hash 倾斜
上文讲到节点 Redis- 1 故障时，所有缓存在节点 Redis- 1 的数据都会缓存到节点 Redis- 2 上，这样就会导致一个缓存分布不均衡的问题，大量缓存集中在某几个节点上。
从另一个角度来说，是 hash 环没有被平均的切分导致的散列不均衡。那么我们多创建几个节点就能解决这个问题。因为实际上物理服务器是固定的，那么我们创建虚拟节点做分布。
为每个 Redis 节点创建 3 个虚拟节点，虚拟节点自身关联到物理节点。
由于多个节点，整个 hash 环被分成 9 个区间，Redis-1 负责映射到区间 2，4，6 的对象，整体来看每个 Redis 服务器承担的区间压力更加均匀。
7. 总结
一致性哈希算法设计是为了解决分布式 Cache 中提出的，设计目标是为了解决在分布式服务节点变更，使用简单哈希算法带来的问题。在实际使用中，如何保证分布式服务的稳定性，是服务设计首先要考虑的问题。
