算法

在分布式系统中，一个核心挑战是如何 将数据均匀分布到多个服务器上，并且在系统扩容或缩容时，尽量减少数据迁移。 一致性哈希（Consistent Hashing） 算法就是为了解决这个问题而提出的，它在缓存系统、负载均衡、分布式存储（如 Cassandra、Amazon Dynamo）中都有广泛应用。 传统哈希的局限性 设想这样一个场景：我们有 4 台缓存服务器 S1、S2、S3、S4，需要存储大量键值对。 一种常见的方式是对 key 取哈希值，然后用取模运算来决定放在哪台服务器上： server = hash(key) % N 其中 N 是服务器数量。 这种方法虽然简单，但有一个致命问题： 当服务器数量变化时，几乎所有数据都需要重新分布。 比如，当我们从 4 台扩容到 5 台服务器时： 原映射: server = hash(key) % 4 新映射: server = hash(key) % 5 几乎所有 key 的哈希值都会对应到新的服务器上，造成大量缓存失效和数据迁移。这在大规模系统中是不可接受的。 一致性哈希的核心思想 一致性哈希通过引入 哈希环（Hash Ring），巧妙地解决了这个问题。 哈希环的构建 一致性哈希将整个哈希空间（比如 0 到 2³²-1）首尾相连，形成一个 环形结构： 0 → 1 → 2 → ... → 2³²-1 → 回到 0 然后，将 服务器节点 通过 哈希函数 映射到环上的某个位置： hash(S1) → 环上的一个点 hash(S2) → 环上的另一个点 ... 同样，每个 key 也会被哈希映射到环上的某个点： hash(key) 数据的分配规则 数据的放置： 从 key 的位置开始，顺时针找到第一个服务器节点，该服务器就是 key 的归属节点。 例如, 如果 key1 的哈希值在 S2 和 S3 之间，那么它会被分配给 S3。 ...