案例库 · 软件与 IT · 技术决策 · 1997
一致性哈希分散缓存键，添加服务器时只移动约1/n的键
1997年，Karger的MIT团队将键和服务器哈希到环上，使得任何调整大小只重映射约1/n的键，Akamai的CDN基于此构建。
MIT · Akamai Technologies
那一手
用缓存服务器群服务网站时，需要决定哪个服务器存放哪个键。标准的取模哈希方法，在添加或删除服务器时几乎重新映射所有键，导致缓存风暴。
Karger的团队通过将键和服务器都放在一个环形空间，每个键顺时针分配给下一个服务器，解决了这个问题。添加或删除节点只影响其前一小段弧线上的键。
关键在于，成员资格是环上的一个位置，而非固定数量桶的划分。Akamai的创始人是共同作者，这个想法成为内容分发网络的基础。
为什么管用
- 调整大小时，只移动约1/n的键，而不是几乎所有键，避免了缓存风暴。
- 服务器与键位于同一哈希空间，归属关系局部且明确。
- 虚拟节点平滑了真实服务器之间不均匀的键分布。
- 成员可以任意顺序变化，不变式仍然成立。
值了多少环：键顺时针归于下一个服务器神来之笔
可以搬走什么
如果成员变化通常会破坏大部分系统，那么将每个单元映射到环上的下一个成员。这样，调整大小只影响新成员或消失成员周围的一小段。
后来呢
一致性哈希成为分布式系统中分片和缓存的标准方法，支撑了Akamai的CDN、分布式数据库、memcached集群以及点对点网络。它使得缓存集群增长时无需全面重新平衡。
资料来源
- Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web
- Consistent hashing
发现哪里写错了？告诉我们。