分布式分片算法：一致性哈希与 Hash Slot

玩早年的网游，选服几乎是创建角色前的第一件事。角色、资产和好友跟着服务器走，想合服时，原本清楚的边界又成了迁移的难题。

数据库分片也会遇到类似问题：三台机器已经放满数据，现在增加第四台。新机器加进来了，哪些数据应该搬过去？客户端又怎么找到它们？

先不谈复杂的集群机制，我们拿 12 个 key，亲手算一次。

一、取模：加一台机器，怎么大半数据都搬家？

假设 12 个 key 的哈希值恰好是 0～11。这里只固定哈希结果，便于手算，并不是建议在生产中使用这种哈希函数。

原来有 A、B、C 三台机器，用 hash % 3 分配；增加 D 后，改成 hash % 4。

12 个 key 中，9 个换了位置。只有 3 个去了新机器 D，另外 6 个是在老机器之间搬家。

问题就在于节点数量参与了取模。分母一变，很多余数一起变了。

在哈希分布充分均匀、节点编号保持不变的假设下，从 N 台扩到 N+1 台，保持原映射的比例约为 1/(N+1)，重映射比例约为 N/(N+1)。这里的三扩四，正好是 75%。

对于缓存，这意味着大量原有条目突然找不到；对于持久化数据，则需要安排相应迁移。简单的公式，把成本留给了扩容。

二、一致性哈希：让新增节点只接走附近的数据

换一个规则：把 0～11 首尾连接成环，A、B、C 分别放在 3、7、11。每个 key 顺时针找第一个节点，恰好落在节点上时就归这个节点。

A 位于 3：接收 0、1、2、3
B 位于 7：接收 4、5、6、7
C 位于 11：接收 8、9、10、11

现在把 D 放在 5：

A：0、1、2、3
D：4、5
B：6、7
C：8、9、10、11

只有 4 和 5 从 B 搬到了 D，其他 key 不动。新增节点接管的是它与前驱之间的那段区间。

注意，这次 D 只分到两个 key，A 和 C 各有四个。少迁移与均衡分配，是两个不同的目标。

工程中常把一台物理机器映射成多个虚拟节点，让它分散地拥有多段区间，降低分配倾斜。这里展示的是一次具体布局；常说的“新增节点迁移约 1/(N+1)”是相应随机、均匀假设下的期望，不是每次加节点都精确成立。

哈希环也需要维护节点信息、虚拟节点和迁移状态。它并不会替系统完成数据复制、失败重试和新旧路由协调。

三、固定槽位：把 key 的位置和机器分开

还有一种办法：预先准备固定数量的槽位，再决定每个槽由谁负责。

仍用同样的 12 个 key。为了手算，先设 12 个槽：

slot = hash(key) % 12
node = owners[slot]

最初 A 负责 0～3，B 负责 4～7，C 负责 8～11。增加 D 后，我们明确选出槽 3、7、11 交给 D：

只有三个槽的数据迁移，key → slot 完全没变，改变的是 slot → node。

这一层间接映射，让“把哪些数据交给 D”变成了一份明确的槽位清单。代价是必须维护所有权表，并负责让实际数据和路由状态一起完成切换。

四、用代码复现三次扩容

from bisect import bisect_left


def ring_owner(value, ring):
    positions = sorted(ring)
    position = positions[bisect_left(positions, value) % len(positions)]
    return ring[position]


values = range(12)
old_ring = {3: 'A', 7: 'B', 11: 'C'}
new_ring = {**old_ring, 5: 'D'}
old_slots = {slot: 'ABC'[slot // 4] for slot in values}
new_slots = {**old_slots, 3: 'D', 7: 'D', 11: 'D'}

modulo_moves = [value for value in values if value % 3 != value % 4]
ring_moves = [
    value for value in values
    if ring_owner(value, old_ring) != ring_owner(value, new_ring)
]
slot_moves = [
    value for value in values
    if old_slots[value % 12] != new_slots[value % 12]
]

print('取模：', modulo_moves)
print('哈希环：', ring_moves)
print('槽位：', slot_moves)

输出：

取模： [3, 4, 5, 6, 7, 8, 9, 10, 11]
哈希环： [4, 5]
槽位： [3, 7, 11]

不要据此得出“哈希环永远比槽位少迁移”。本例中，哈希环扩容后并不均衡，而槽位方案恰好让每台机器拥有三个 key。比较算法时，必须一起看迁移量、负载分布和实现成本。

五、Redis 为什么选 16384 个槽？

Redis Cluster 使用固定槽位模型，基本映射为：

key → CRC16(key) % 16384 → slot → owner

增加节点时，key 的槽号不变，通过转移部分槽的所有权来分配数据。它不是在一个连续环上寻找后继节点。Redis 集群分片说明

16384 也不只是“一个方便取模的数字”。Redis 作者在设计讨论中解释过心跳消息里槽位位图的成本：16384 个槽需要 2048 字节，65536 个槽则需要 8192 字节，还要结合预期集群规模考虑。这个选择兼顾分配粒度和集群通信开销。Redis 作者的设计解释

有了固定槽位，可以明确计划“这次迁移 200 个槽”。但 200 个槽到底有多少字节、多少热 key，还要实际统计。只有在 key 均匀分布等假设下，槽数量比例才能近似代表 key 数量比例，不能直接代表流量比例。

六、跟着一条请求走过迁移过程

假设槽 8 原本属于 A，准备迁往 B。以下描述的是经典的 MIGRATING、IMPORTING 与逐 key 迁移流程。

先把 B 设置为导入、A 设置为迁出，再分批移动槽内数据。此时所有权还没有最终切换，客户端仍然先找 A。

如果请求的 key 还在 A，A 可以处理；如果已经不在 A，A 会返回 ASK，让客户端把这一次请求发给 B。客户端在同一连接上先发 ASKING，再重试原命令。

客户端 → A：GET 某个 key
A → 客户端：ASK，去 B 处理这一次请求
客户端 → B：ASKING
客户端 → B：GET 某个 key

为什么不直接永久改路由？因为槽里的另一个 key 可能还没搬走。此时“整个槽归 B”还不是事实。

等数据迁完、槽所有权正式切换以后，旧路由上的客户端再找 A，就会收到 MOVED，随后更新槽路由或刷新拓扑。MOVED 也可能只是纠正一个过期或错误的缓存，并不只出现在迁移刚结束的时候。Redis 重定向与迁移规范

这也是迁移比修改一张字典复杂的地方：中间状态必须有可执行的请求处理规则。

七、同槽、故障与热点，还有哪些边界？

Hash tag：让相关 key 明确共址

order:{1001}:meta 和 order:{1001}:items 可以通过共同的 hash tag 进入同一槽。这让需要同槽执行的多 key 操作具备条件。

同一台机器上的不同槽，仍不等于同一个槽。反过来，把大量不相关的数据都塞进同一个 tag，也可能制造热点。对于含多个或空花括号的 key，应遵循具体提取规则，不能自行猜测。Redis hash tag 规则

故障切换：接管者还需要数据

主节点故障后，并不是给任意空节点重新分配槽号就能恢复。副本需要已有复制数据，再经过故障检测和提升流程接管槽。

Redis Cluster 使用异步复制，在特定故障情形下可能丢失已确认写入。分片解决数据放哪里，复制与故障协议决定故障时还能保留和访问什么，二者不能混为一谈。Redis 写入安全说明

热 key：槽均匀不代表负载均匀

假设一个 key 占了全站一半请求，把它所在的槽搬到另一台机器，只是移动热点，并没有拆开热点。缓存、读副本或业务层拆分可能有帮助，但各自有一致性和实现代价。

八、再回答“加一台机器，谁搬家？”

三个方案都能分配 key，区别在于拓扑变化时哪些映射保持稳定，以及系统如何安排迁移。

Redis 的槽位设计让迁移单位变得明确，但数据仍然要搬，请求仍然会在途中到达，故障也仍然可能发生。理解了这三件事，ASK、MOVED 和槽位所有权就不再是一串需要死记的术语。