第 5 章设计一致性哈希

引言

本章探讨一致性哈希（Consistent Hashing），这是一种实现水平扩展的关键技术，它能把请求和数据高效地分布到各台服务器上。它能在增加或移除服务器时尽量减少数据的重新分布，并保证数据均匀分布，从而缓解服务器热点（hot spot）等问题。

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

服务器数量变化时，大多数键都要重新分布，这会导致效率低下和过载。

一致性哈希保证在增加或移除服务器时，只有一小部分键需要重新映射。这能把影响降到最低，并增强可扩展性。

哈希空间与哈希环： 哈希空间构成一个连续的环，哈希值分布在 0 到 2^160-1 之间（例如使用 SHA-1 这样的哈希函数）。把哈希空间的首尾连接起来，就得到了一个环。
使用同一个哈希函数 f，根据服务器 IP 或名称把服务器映射到环上。
服务器查找
从键所在的位置沿环顺时针方向查找，遇到的第一台服务器就是该键所属的服务器。
增加和移除服务器
增加一台服务器时，只有附近的键会被重新分布。只有一小部分键会被重新分配到新服务器上。
移除一台服务器时，只会影响其范围内的键。只有被移除服务器上的键会被重新分配到顺时针方向的下一台服务器。

当增加或移除服务器时：

增加服务器： 受影响的键是位于新服务器与其前驱服务器之间的键。在下面的例子中，服务器 4 被加入到环上。受影响的范围从 s4（新加入的节点）开始，沿环逆时针移动，直到遇到一台服务器（s3）为止。因此，位于 s3 和 s4 之间的键需要重新分布到 s4 上。
移除服务器： 受影响的键是位于被移除服务器与其前驱服务器之间的键。在下面的例子中，当一台服务器（s1）被移除时，受影响的范围从 s1（被移除的节点）开始，沿环逆时针移动，直到遇到一台服务器（s0）为止。因此，位于 s0 和 s1 之间的键必须重新分布到 s2 上。