第17章哈希表与一致性哈希

课程目录第17章哈希表与一致性哈希

一、从单机到分布式：哈希表为什么需要“升级”？

说实话，我刚开始做后端开发那会儿，哈希表就是个内存里的数据结构。键值对一存，O(1)查询，爽得很。但后来项目规模上来了，单机扛不住，数据得分散到多台机器上——这时候问题就来了：怎么决定一个 key 该放到哪台机器？

最简单的办法：hash(key) % N，N 是机器数量。嗯，这招在节点不变的时候挺好用。但一旦你加机器或者减机器……

⚠️ 注意：取模法最大的坑就是——节点变化会导致大量 key 的映射关系改变。我曾在线上遇到过，扩容一台机器，结果缓存雪崩，数据库被打爆。原因？取模后大部分 key 都落到了新位置，缓存全部失效。

所以，我们需要一种更聪明的方案。这就是一致性哈希登场的理由。

一致性哈希的思路其实很巧妙。它把整个哈希值空间组织成一个虚拟的圆环，范围通常是 0 到 2^32-1。每个节点（比如服务器）根据它的 IP 或名字计算哈希，放到环上。每个 key 也计算哈希，然后顺时针找到第一个节点，就是它该去的地方。

我画了一张图，帮你理解这个结构：

你看，key1 顺时针找到的第一个节点是 A，key2 找到 B，key3 找到 C。一切都很自然。

假设节点 C 挂了。那原来落在 C 上的 key，顺时针找下一个节点——也就是 D。只有 C 到 D 之间的 key 需要迁移。其他节点纹丝不动。

反过来，加一个节点 E，也只会影响 E 到它前一个节点之间的 key。这就是一致性哈希最牛的地方：节点变化时，只有少量 key 需要重新分布。

核心结论：一致性哈希把 rehash 的影响从 O(N) 降到了 O(1/N)。N 越大，收益越明显。

嗯，一致性哈希有个小毛病——节点在环上分布不均匀。比如你只有 4 台机器，哈希值一算，可能全挤在环的一侧。那另一侧的 key 全落到同一台机器上，负载就不均衡了。

我在项目中遇到过这种情况：一台机器 CPU 飙到 90%，另一台才 20%。查了半天，发现就是哈希分布不均匀导致的。

解决方案？虚拟节点。

说白了，就是给每个物理节点创建多个虚拟副本。比如节点 A 有 A0、A1、A2……每个虚拟节点都算一个哈希值，分布在环上。key 找到虚拟节点后，再映射回物理节点。

这样环上的节点数量变多了，分布自然更均匀。我一般建议每个物理节点分配 150~200 个虚拟节点，效果就很好了。

💡 我的经验：虚拟节点数量不是越多越好。太多会占用内存，而且查找时遍历成本增加。150 是个不错的起点，你可以根据实际负载做微调。

Redis 从 3.0 开始支持集群模式，它的核心就是一致性哈希 + 虚拟节点。不过 Redis 的实现有点不一样——它用了一个叫 hash slot 的概念。

Redis 集群把整个哈希空间分成 16384 个槽位（slot）。每个 key 通过 CRC16 算法算出一个值，然后对 16384 取模，决定它属于哪个槽。每个节点负责一部分槽。

举个例子：

// 计算 key 的槽位
slot = CRC16(key) % 16384

// 集群节点与槽位映射
// 节点 A: 0~5460
// 节点 B: 5461~10922
// 节点 C: 10923~16383

你可能会问：为什么是 16384？不是 2 的整数次幂？

嗯，Redis 作者 antirez 在 GitHub 上解释过：16384 个槽位，用 2KB 的位图就能表示（16384/8 = 2048 字节）。心跳消息里带上这个位图，网络开销很小。如果改成 65536 个槽，位图就变成 8KB，心跳包就大了。所以 16384 是个权衡后的选择。

当你要扩容时，只需要把一部分槽从老节点迁移到新节点。迁移过程中，key 还在老节点，但新节点会记录一个“导入中”的状态。客户端访问时，如果 key 还在老节点，老节点会返回一个 MOVED 重定向，告诉客户端去新节点找。

我曾经帮一个团队做 Redis 集群扩容，他们担心迁移过程中服务会中断。其实不会——Redis 的槽迁移是在线的，逐个 key 迁移，客户端无感知。只要你的客户端库支持集群协议（比如 Jedis、Lettuce），一切都很平滑。

⚠️ 注意：Redis 集群不支持多 key 操作（比如跨节点的 mget、事务），除非这些 key 在同一个槽里。你可以用 hash tag 强制让某些 key 落到同一个槽：{user:123}:name 和 {user:123}:age 会算到同一个槽。

一致性哈希不是什么高深的东西，说白了就是把节点和 key 都映射到一个环上，顺时针找归属。它解决了分布式系统中节点变化导致大量数据迁移的问题。

虚拟节点技术解决了数据倾斜，让负载更均衡。Redis 集群用 hash slot 的方式实现了类似的效果，而且更工程化——16384 个槽，位图表示，心跳轻量，迁移在线。

如果你正在设计自己的分布式缓存或存储系统，我建议你直接参考 Redis 的做法。毕竟，它已经在生产环境中被验证了十几年，踩过的坑比我们多得多。