第5章：设计一致性哈希

简介​

本章将探讨一致性哈希算法，这是一种通过在各台服务器间高效分配请求与数据来实现水平扩展的关键技术。它能够在增减服务器时最大限度地减少数据重分布，并确保数据的均匀分布，从而有效缓解服务器热点等问题。​

重新哈希问题​

Explanation​

在传统的哈希方法中，例如serverIndex = hash(key) % N, 当服务器数量发生变化时，数据重分布就会成为问题。例如：​

•

移除一台服务器会导致大部分键被重新分配，从而引发缓存未命中。​

•

增加一台服务器会导致不必要的键重新分布。​

​

​

•

当服务器池的规模固定时，这种方法效果良好。然而，当有新服务器加入或现有服务器被移除时，问题便随之而来。​

​

​

Key Issue​

当服务器数量发生变化时，对大部分键进行重新分布会导致效率低下并造成负载过重。​

一致性哈希​

Definition​

一致性哈希能够在增减服务器时仅重新映射一小部分键，从而最大限度地减少服务中断并提升系统的可扩展性。​

Key Concepts​

哈希空间与环：哈希空间构成一个连续的环，哈希值分布于0至2^160-1（例如，使用SHA-1等哈希函数）。通过将两端连接起来，就形成了一个环。​

​

​

•

我们使用相同的哈希函数f，根据服务器的IP地址或名称将服务器映射到环上。​

​

​

服务器查找​

•

通过在环上沿顺时针方向遍历，直到找到一台服务器，即可确定该键对应的服务器。​

​

​

添加与移除服务器​

•

添加服务器只会重新分配附近的键。只有少数键会被重新分配到新服务器上。​

​

​

•

移除一台服务器仅会影响其负责范围内的键。只有来自被移除服务器的键会被重新分配给顺时针方向的下一台服务器。​

​

​

挑战与解决方案​

Two Issues in Basic Approach​

分区大小不均：各服务器可能拥有大小不等的数据分区。​

键分布不均匀：某些服务器接收到的键数量可能远多于其他服务器。​

Solution: Virtual Nodes​

•

每台服务器在环上由多个虚拟节点表示，这些虚拟节点在环上均匀分布。​

•

虚拟节点能够改善密钥分布并实现负载均衡。随着虚拟节点数量的增加，密钥的分布会变得更加均衡。这是因为随着虚拟节点数量的增多，标准差逐渐减小，从而促使数据分布趋于均衡。​

​

​

受影响的键​

当服务器被添加或移除时：​

•

新增服务器：受影响的键范围是新服务器与其前驱服务器之间的所有键。在下图示例中，服务器4被添加到环上。受影响的范围从s4（新加入的节点）开始，沿环逆时针方向延伸，直到遇到下一个服务器（s3）为止。因此，位于s3和s4之间的键需要重新分配到s4。​

​

​

•

被移除的服务器：受影响的键范围是从被移除的服务器及其前一个服务器之间的所有键。在下图所示的例子中，当一台服务器（s1）被移除时，受影响的范围从s1（被移除的节点）开始，沿环逆时针方向向前遍历，直到找到另一台服务器（s0）为止。因此，位于 s0 和 s1 之间的键必须重新分布到 s2。​

​

​

一致性哈希的优势​

•

最小化重新分配：仅有一小部分键会被重新分配。​

•

可扩展性：支持水平扩展。​

•

缓解热点问题：均衡数据分布，避免服务器过载。​

实际应用​

•

亚马逊 DynamoDB​

•

Apache Cassandra​

•

Discord​

•

Akamai CDN​

•

Maglev 负载均衡器​