数据库 - 第 5 部分：一致性哈希

概览 (Overview)

什么是致性哈希（Consistent Hashing）？ 在了解它之前，首先可以将 hashing 理解为“切碎并混合”。Hash Map 是一种将数据映射到索引的数据结构。由于其复杂度为 O(1)，可以说是最高效的。通常，它以键值对（Key-Value pair）的形式进行存储。

关于哈希就先聊到这里，接下来我们讨论一下分布式哈希。

分布式哈希

假设有如下所示的哈希表。现在我们要将这些数据存储到分布式的存储系统中。

如果将数据分散存储在三台服务器上，整理如下。 每台服务器的索引分别为 A:0, B:1, C:2。

在运行良好的情况下，假设其中一台设备突然故障了。如果服务器 C 宕机，哈希表和服务器的数据分配将重新变为如下所示：

现在数据将存储在 A:0, B:1 这两台存储设备中，如下所示：

在这种情况下，原本存在于 C 的所有键位置都会发生变化。此时需要从原始数据进行重新哈希（re-hashing）操作，这会给原始服务器带来负载。而且在此过程中，客户端请求的数据将会丢失。

为了解决这个问题而提出的哈希技术就是一致性哈希（Consistent Hashing）。

一致性哈希 (Consistent Hashing)

上面的图片展示了我们要讨论的核心。 让我们尝试按照这张图片进行哈希处理。

服务器也会被放置在哈希环中。

在这里，查找每个键所在服务器的规则只有一个：

逆时针方向旋转时，最近的服务器就是该键所在的存储位置。

根据上述基准整理键所属的存储位置如下：

那么，这种技术到底有什么优势呢？

现在想象一下，如果设备 C 被移除。在传统技术中，所有的键都必须重新哈希。

而通过这种技术，我们可以发现只有分配给设备 C 的键需要重新哈希。

因为指向服务器 A 和 B 的键已经指向了最近的位置 A 或 B。即使 C 消失，这些键也不会发生变化。只有分配给服务器 C 的键需要进行 re-hashing。

反之，即使添加设备，也只需要进行 K/N（键的数量 / 设备数量）规模的 re-hashing，而不需要对所有键进行重新哈希。

例如，如果有 3 个键和 2 台设备。如果假设在这之间增加了一台设备。如果设计目标是让键均匀分布，那么最终 3/3 = 1 个键可能会发生 re-hashing，从而达到每台设备存储一个键的均衡状态。

一致性哈希也存在问题，即“键倾斜”。我们该如何缓解这个问题呢？

Ketama 一致性哈希 (Ketama Consistent Hashing)

最简单的方法是将一台服务器拆分为多个虚拟节点（Tokens），并放置在一致性哈希环中。 这就是 Ketama 一致性哈希技术。通过将服务器 A 分散为 A0 到 A10，使键的分配尽可能均匀。

思考

• 归根结底，重新哈希（re-hashing）是一个无法回避的问题。如何设计和构建系统，使重新哈希的发生率降至最低，是分布式处理的一项重要需求。

示例项目（简单实现了上述理论）

• Reduster

附录 (Appendix)

• Constant Hashing
• hashing, ketama