一致性哈希

一致性哈希把节点和键放进同一个环形 token 空间。键属于顺时针遇到的第一个活动节点 token。增加或移除一个 token 只改变相邻区间的归属，相邻区间之外的键都保留原拥有者。一个物理节点若有多个虚拟 token，成员变化则影响这些 token 对应的多个区间。

本课的环有 360 个刻度，经过 359 就回到 0。键点位置由哈希决定，节点标记提供归属边界，环上没有最后一个桶。

一致性哈希如何工作

采用右端包含的后继规则：寻找第一个大于或等于键 token 的活动节点 token。键在 260，节点也在 260，就归该节点。若不存在更大或相等者，回到最小 token。

键 token 与拥有者要分开。K5 的哈希位置为 155，节点加入或离开不会重新哈希 K5；改变的只是从 155 开始遇到的第一个活动后继。

节点为 N1@20、N2@140、N3@280 时：

• N1 负责 (280,20]，跨越零点。
• N2 负责 (20,140]。
• N3 负责 (140,280]。

左开右闭让边界只有一个拥有者，也与大于等于的后继查找一致。

逐步演示

默认 Node joins 固定十二个键 token：10,35,60,95,125,155,185,205,235,260,310,345，按 K0–K11 编号。

1. 建三节点环，N1、N2、N3 分别拥有 3、4、5 个键。
2. 检查回绕边界 K11@345。没有活动 token≥345，跨过 359 和 0，后继是 N1@20。归属高亮，键点仍在 345。
3. 准备 N4@220，位于前驱 N2@140 与原后继 N3@280 之间，此时尚未改变归属。
4. 把 N4 插入环，增加一个边界。
5. N4 接管原属 N3 的 (140,220]。
6. 完整检查 K5：位置仍为 155，后继从 N3 变成 N4。
7. K6@185、K7@205 同处该区间，也转给 N4。
8. 检查补集：K0–K4、K8–K11 九个键在区间外，拥有者不变。
9. 负载从 N1=3,N2=4,N3=5 变为 N1=3,N2=4,N3=2,N4=3。移动三键、保留九键，所有哈希位置固定。

Node leaves 从 N1@20、N2@140、N4@220、N3@280 开始，移除 N2 后，它原来的 (20,140] 转给顺时针下一活动节点 N4。只有 K1、K2、K3、K4 移动。负载按环序由 N1/N2/N4/N3 的 3/4/3/2，变为剩余 N1/N4/N3 的 3/7/2，其余八键不变。

虚拟节点与负载偏斜

移动局部不代表负载均匀。Virtual nodes 初始为 N1@20、N2@80、N3@300。N3 独占长区间 (80,300]，取得十二键中的七个，N1=3、N2=2，最大最小差五键。

之后每个物理节点各有三个位置：

• N1：20、140、260。
• N2：80、200、320。
• N3：100、240、300。

九个标记把长区间切细。K4、K5、K6、K9、K10 五个键改变物理拥有者，最终 N1=4,N2=5,N3=3，负载差由五缩到二。

虚拟节点是环位置，不是新机器。N1 的三个 token 仍回到同一物理 N1。更多位置可减少随机大区间带来的方差，也可按数量表达容量权重，但有限样本不保证完全均分。

为什么比取模分片少搬键

把 V 个活动 token 排序，后继二分查找为 O(log V)；没有后继时回到首项是常数操作。这是给定键 token 后的查找成本，计算键哈希另有成本。成员更新插入或删除 token，并迁移相邻区间的键；排序数组的插入搬移与树结构更新成本不同，迁移量取决于区间中的键数。

在均匀独立哈希、等权节点、样本足够的假设下，给 N 个现有物理节点增加一个等权节点，平均约移动 1/(N+1) 键空间。默认固定样本只证明本次局部性，不声称每次都精确移动这个比例。

普通取模使用 hash(key)%serverCount，节点数一变，所有计算的除数都变。Modulo contrast 把相同十二个哈希从三服务器改成四台，十键换拥有者，只有 K2@60、K7@205 不变。一致性哈希加入 N4 只移动三键。

使用范围与替代方案

缓存集群、应用分片、对象存储和请求路由在成员变化频繁且移动昂贵时，可利用局部重映射。前提是稳定的键哈希、一致的成员视图，以及真正转移数据的过程。

环只选位置，不负责复制字节。副本、故障检测、环版本切换、向新节点流式搬迁都是独立协议。给大机器更多 token 可表达权重，但数量应结合键分布、元数据与移动成本测量。

热点键不能靠增加虚拟位置拆开：同一键仍归一主节点。复制、请求合并或应用拆分才可能分担它。若不想维护有序环，可用 rendezvous hashing 为各候选节点评分并选最高者；节点集合固定时取模更简单。数据库已有在线分片与复制机制时，应先利用现有管理能力。

边界情况

• K11@345 必须回绕到 N1@20，否则环尾无人负责。
• 虚拟节点预设的 K9@260 恰好归 N1@260，右端包含。
• 节点离开，其旧区间交给顺时针下一活动 token，不是前驱，也不是平均分给所有节点。
• token 间距不均可造成大区间，负载平衡与少迁移是两项性质。
• 热点键的请求量不会因虚拟节点数增加就被分成多个拥有者。
• 一个活动节点时所有键归它；两节点中失去一个后，剩余节点接管全部键。没有活动节点时则没有可用拥有者，生产系统需处理该状态。
• 节点 token 碰撞需要确定的排序与去重规则；键与节点相等由本课右端规则处理。画布除刻意展示的 K9 边界外使用固定不同位置。

常见错误

• 成员变化就重新哈希键。键 token 必须独立于活动节点列表，归属可变，点不移动。
• 逆时针找前驱，却仍使用顺时针区间定义。
• 把离开者区间交给前驱，破坏后继规则。
• 两端都闭合，[a,b] 与 [b,c] 会同时领取 b。这里使用 (a,b]。
• 把虚拟节点数当物理服务器数。
• 承诺完全均衡，忽略权重、token 数、哈希与实际样本。
• 把一致性哈希当复制协议。画布只选择一个拥有者，不处理副本一致性。

模型范围

0–359 环、固定节点位置、十二个固定键、每键一份。省略复制、容量权重的实际调配、并发成员变更、传输成本、故障检测、数据流迁移和热点治理。虚拟节点一次出现，不模拟成员协议。保留的约束是键哈希固定，token 边界变化只重分对应邻接区间。