面试题：在 Redis 集群中，如何根据键定位到对应的节点？

在 Redis 集群中，数据被分片存储在多个节点上，每个节点负责一部分数据。为了根据键定位到对应的节点，Redis 集群使用了一种基于哈希槽（Hash Slot）的分布式算法。以下是具体的实现原理和步骤：

1. 哈希槽（Hash Slot）

Redis 集群将所有的键空间划分为 16384 个哈希槽（编号从 0 到 16383）。
每个键通过一个哈希函数映射到一个特定的哈希槽上。
哈希槽的分配是均匀的，每个节点负责一部分哈希槽。

2. 键到哈希槽的映射

对于一个给定的键，Redis 使用 CRC16 算法计算其哈希值，然后对 16384 取模，得到该键对应的哈希槽。
公式如下：slot = CRC16(key) % 16384
例如，键 user:123 的 CRC16 哈希值为 12345，那么它对应的哈希槽为：slot = 12345 % 16384 = 12345

3. 哈希槽到节点的映射

Redis 集群中的每个节点负责一部分哈希槽，集群通过配置信息（cluster nodes）来维护哈希槽与节点的映射关系。
当客户端连接到集群时，它会获取集群的配置信息，包括每个节点负责的哈希槽范围。
例如，假设集群有三个节点 A、B、C，它们负责的哈希槽范围如下：
- 节点 A：0 – 5460
- 节点 B：5461 – 10922
- 节点 C：10923 – 16383
客户端根据键计算出的哈希槽，查找对应的节点。

4. 客户端定位节点的过程

客户端首先计算键的哈希槽。
客户端根据哈希槽查找集群配置信息，确定负责该哈希槽的节点。
如果客户端已经缓存了集群配置信息，则直接向对应的节点发送命令。
如果客户端没有缓存集群配置信息，或者配置信息已过期，则向任意一个节点发送命令，该节点会返回 MOVED 重定向错误，包含正确的节点信息。
客户端根据 MOVED 错误中的信息，更新集群配置，并重新发送命令到正确的节点。

5. MOVED 重定向

当客户端向错误的节点发送命令时，该节点会返回一个 MOVED 错误，格式如下：MOVED <slot> <ip>:<port>
其中 <slot> 是键对应的哈希槽，<ip>:<port> 是负责该哈希槽的节点地址。
客户端根据 MOVED 错误中的信息，更新集群配置，并重新发送命令到正确的节点。

6. ASK 重定向

在集群进行重新分片（resharding）时，部分键可能正在迁移中，此时客户端可能会收到 ASK 重定向错误。
ASK 错误的格式如下：ASK <slot> <ip>:<port>
客户端根据 ASK 错误中的信息，临时向指定的节点发送命令，并在命令前加上 ASKING 指令。

总结

在 Redis 集群中，通过哈希槽的机制，键被均匀地分布到各个节点上。客户端通过计算键的哈希槽，并根据集群配置信息定位到对应的节点。如果客户端发送命令到错误的节点，集群会通过 MOVED 或 ASK 重定向错误，引导客户端找到正确的节点。这种设计使得 Redis 集群能够高效地处理大规模数据分布和请求路由。

THE END

Redis 面试题