一致性哈希⚓︎

一致性哈希（Consistent Hashing）主要解决的是在节点数量变化时，如何尽量减少数据迁移的问题。它广泛应用于分布式缓存、对象存储、分布式 KV 系统及各种分片路由系统中。

简单哈希取模的局限性⚓︎

最基础的数据路由算法通常采用简单的哈希取模操作，其计算公式为：

其中：

• $o$ 为对象标识符
• $n$ 为集群内的物理节点总数
• $m$ 为目标机器的映射编号

假设现有 3 个节点，10 个数据对象的哈希值分别为 $1, 2, 3, \dots, 10$。经过取模计算后，数据的初始分布如下：

• 节点 0：$3, 6, 9$
• 节点 1：$1, 4, 7, 10$
• 节点 2：$2, 5, 8$

当集群因扩容增加 1 个节点，节点总数 $n$ 变为 4 后，映射结果将发生剧烈变化：

• 节点 0：$4, 8$
• 节点 1：$1, 5, 9$
• 节点 2：$2, 6, 10$
• 节点 3：$3, 7$

一致性哈希机制⚓︎

一致性哈希的提出旨在缩小集群扩缩容时影响的数据范围。其核心设计在于将散列值空间组织成一个封闭的环状结构，数据与节点实体均映射至该环上的固定位置，依靠位置的相对关系来裁定数据的归属。

2.1 构造哈希环空间⚓︎

通常将哈希空间设定为范围在 $0 \sim 2^{32} - 1$ 的整数域。在逻辑结构上，将最高值紧邻最低值，首尾相连形成一个闭合的环。

graph LR
    A[0] --> B[...]
    B --> C[2^32 - 1]
    C -. 首尾相连 .-> A

2.2 数据对象与节点映射⚓︎

利用特定的散列算法对对象的主键或唯一标识进行计算，得出对应哈希环上的具体位置。对于物理节点，同样选取其 IP 地址或全局唯一标识进行哈希计算，投影至同一环上。

graph TD
    O[数据对象] -->|Hash 计算| P1[哈希环位置]
    N[物理节点] -->|Hash 计算| P2[哈希环位置]

2.3 数据路由规则⚓︎

在确认对象与节点在哈希环上的坐标后，从对象所在的刻度出发，沿顺时针方向寻找，将寻得的第一个可用节点作为该数据的最终归属节点。

例如：

• 数据 object1 被分配至 NODE1
• 数据 object3 被分配至 NODE2
• 数据 object2、object4 被分配至 NODE3

graph TD
    O1[object1] --> N1[NODE1]
    O3[object3] --> N2[NODE2]
    O2[object2] --> N3[NODE3]
    O4[object4] --> N3[NODE3]

2.4 集群拓扑变更⚓︎

节点扩容⚓︎

若此时集群中新增节点 c4，且其哈希值落在 c2 与 c3 之间，依照顺时针寻址规则，仅有处于 c2 到 c4 区间内的数据需从原属的 c3 节点迁移至 c4，其余节点与数据映射关系保持不变。

graph LR
    D[c2 到新增位置数据] --> C3_Old[c3 节点]
    D --> C4[新增 c4 节点]
    C4 -. 顺时针接力 .-> C3_New[c3 节点]

节点缩容⚓︎

若因节点故障或主动缩容移除节点 c1，则原由 c1 负责管理的数据集合将被整体顺延迁移至其顺时针方向的直接后继节点。环内其他节点各自维护的数据集完全不受干扰。

graph LR
    D1[c1 数据] --> C1[c1 节点故障/移除]
    C1 -. 顺时针 .-> C2[c2 节点]
    D1 --> C2[c2 节点接管]

2.5 数据倾斜与虚拟节点⚓︎

当哈希环上的物理节点数目稀少时，节点在整数域上的投影极易呈现非均匀分布，引发哈希环偏斜。

如下图所示，节点 A 控制了极大的哈希区间，节点 B 覆盖范围极小，而节点 C 几乎无法分担负载：

pie title 节点负载分布 (数据倾斜)
    "Node A (过载)" : 80
    "Node B" : 15
    "Node C (空闲)" : 5

数据长期向个别节点集中会导致以下问题：

• 从宏观尺度看，集群负载极度不均衡，节点处理能力出现短板。
• 热点节点一旦崩溃，海量请求会瞬间转移至顺时针后继节点，可能引发链式故障（Cascading Failure）。

为了纠正环形偏斜，工程实践中普遍采用虚拟节点（Virtual Nodes）技术。该方法并不强行增加物理服务器，而是对单台伺服机器进行多重映射。

加入虚拟节点后的数据分布呈现出更高的均匀度，进一步摊薄了单点瓶颈风险：

pie title 虚拟节点介入后的负载分布
    "Node A (多虚拟节点)" : 33
    "Node B (多虚拟节点)" : 33
    "Node C (多虚拟节点)" : 34

以下 Mermaid 图表展示了包含虚拟节点的映射拓扑：

graph TD
    O1[数据对象 1] -. Hash .-> VN1_A
    O2[数据对象 2] -. Hash .-> VN2_B
    O3[数据对象 3] -. Hash .-> VN3_C
    O4[数据对象 4] -. Hash .-> VN1_B
    O5[数据对象 5] -. Hash .-> VN2_A

    VN1_A(Node A 虚拟节点 1) --> NodeA[(物理节点 A)]
    VN2_A(Node A 虚拟节点 2) --> NodeA

    VN1_B(Node B 虚拟节点 1) --> NodeB[(物理节点 B)]
    VN2_B(Node B 虚拟节点 2) --> NodeB

    VN1_C(Node C 虚拟节点 1) --> NodeC[(物理节点 C)]
    VN2_C(Node C 虚拟节点 2) --> NodeC
    VN3_C(Node C 虚拟节点 3) --> NodeC

分布式散列表：Chord 协议⚓︎

在 P2P 分布式网络或者 DHT 架构下，资源定位算法的效率尤为重要。传统的中心化架构（如 Napster）具有极大单点故障隐患；而基于消息洪泛的机制（如 Gnutella）又面临着较高的全网广播开销，网络信令与节点总数紧密耦合。

graph TD
    C[中心化目录服务器] --> N1[节点 1]
    C --> N2[节点 2]
    C --> N3[节点 3]
    GN1[节点 1] <--> GN2[节点 2]
    GN2 <--> GN3[节点 3]
    GN3 <--> GN1

Chord 协议作为一致性哈希在去中心化网络中的一项工程实现，系统性地规划了资源寻找、路由表管理以及网络拓扑自愈问题。

3.1 空间模型构造⚓︎

Chord 常见以 SHA-1 用作底层散列算法，其理论环空间可达 $2^{160}$ 规模。在简化表述时，为便于说明内部逻辑常将其缩等至 6 位（$2^6 = 64$）空间，节点在 $[0, 63]$ 的环中闭合相接。

graph LR
    A[0] --> B[10]
    B --> C[20]
    C --> D[30]
    D --> E[40]
    E --> F[50]
    F --> G[63]
    G -. 回绕闭合 .-> A

3.2 资源定位算法⚓︎

数据查找在 Chord 体系结构中是最高频的操作。单纯沿后继节点链路穷举查询的算法时间复杂度为 $\mathcal{O}(N)$。这种线性时间成本在海量节点网络框架中代价极高。

graph LR
    N1 --> N2 --> N3 --> N4 --> N5
    note1[O_N 线性查找慢] -.-> N3

路由表 (Finger Table) 的引入⚓︎

为将查找过程提速至 $\mathcal{O}(\log N)$ 级别复杂度，Chord 为网络中每一个单一节点配置了基于当前哈希刻度由近及远分布的路由表项（Finger Table）。

其中，拥有 $m$ 项的路由表内，第 $i$ 条路由条目指向标识为 $(\text{hash}(node) + 2^{i-1}) \pmod{2^m}$ 的哈希节点后继位置。这允许查询请求以指数跨度形式跳跃前进。

graph LR
    F1[当前节点] -->|+2^0| F2[后继 +1]
    F1 -->|+2^1| F3[后继 +2]
    F1 -->|+2^2| F5[后继 +4]
    F1 -->|+2^3| F9[后继 +8]

查询路径追踪⚓︎

在节点 N8 尝试寻址资源 K54 时：

1. N8 判断自身后继不覆盖 54，随后扫描本地 Finger Table。
2. 查找不超过 54 且最接近目标的远端节点引用。在此例中，符合条件的条目是 N42。
3. 查询请求投递至 N42。N42 复用同样的匹配策略继续寻址。

graph LR
    N8[起点 N8] -- "Finger: N42 (<=54)" --> N42[跳跃至 N42]
    N42 -- "Finger: N51 (<=54)" --> N51[跳跃至 N51]
    N51 -- "后继即目标" --> N56[目标归属 N56]

由于每一次跳动都会将候选哈希距离缩减至少一半左右，该协议最终保证资源在经历最多 $\mathcal{O}(\log N)$ 步跳跃后成功解析至 N56。

3.3 路由表自维护与拓扑修复⚓︎

在动态网络中，节点状态随时间频繁波动。Chord 采取了后台探测任务以补偿后继断层及修正路由表滞后的缺陷。

当例如 N26 这类新节点主动挂载：

1. 新节点与现网通过基础查询确定其应当在 N21 与 N32 之间的间隙内挂载。
2. N26 指向 N32。
3. N26 向原后继宣告自身并篡改 N32 之直接前驱依赖关系。
4. 原定由 N32 保管的部分归属权重在校验完毕后向 N26 发生实质性块迁移。

graph TD
    N21[原前驱 N21] -. "断开旧连接" .-x N32[原后继 N32]
    N26[新挂载 N26] -->|1. 指向| N32
    N21 -->|2. 更新后继为| N26
    N32 -.->|3. 迁移数据块| N26

在随后的时间窗口里，由于 Chord 定期的全网一致性探测巡检机制，邻座节点的缓存路由表项也会依据探测到的当前状态自动收敛对齐。

sequenceDiagram
    participant N_other as 其他节点
    participant N26 as 新节点 N26
    N_other ->> N_other: 定期刊逻探测 (Fix Fingers)
    N_other ->> N26: Ping/Check 存活
    N26 -->> N_other: ACK响应
    N_other ->> N_other: 修正自身路由表指向 N26

graph LR
    Q[查询请求] --> N1[当前节点]
    N1 -.->|链接失效/超时| NX[已下线节点]
    N1 -->|回退并使用备用路由| N2[其他可用节点]
    N2 --> Target[完成剩余查询]

参考资料⚓︎

• 一致性哈希算法（consistent hashing） - 知乎

评论