一致性哈希Consistent hashing
把键和节点位置关联，减少成员变化引起的重映射。
- 核心约束
- 在同一成员和规则下，映射是确定的。
- 适用问题
- 缓存分片、请求路由与数据归属。
- 边界与取舍
- 均衡性、权重、故障处理和虚拟点数量影响结果。
常见操作#
P 为包含虚拟节点的环点数量，L 为键长；以有序环点数组实现为例。
| 操作 | 时间复杂度 | 条件与说明 |
|---|---|---|
| 键映射到环点 | 先哈希键，再二分找顺时针第一个点；已缓存或固定宽度键可省去线性哈希项。 | |
| 构建环点数组 | 生成虚拟节点并排序，哈希单点按常数成本计算。 | |
| 成员变更 | 索引更新 + 受影响数据迁移 | 数组重建、树更新和实际复制的数据量是不同成本；不可把迁移完全省略。 |
时间与空间#
- 时间复杂度
- 有序数组查询 ，键哈希另计
- 辅助空间
- 环元数据，不含实际数据副本
减少成员变化时的映射扰动，不自动保证均匀热点、故障域隔离或每次请求负载均衡。
工程中的应用#
1 个案例 · 附源码nginx 的 consistent hash 将上游展开为有序哈希点，再用二分查找定位请求 key 的落点。
附源码片段 · 通信与流量
基础原理参考资料
nginx 1.26.3 · Consistent hashingngx_http_upstream_init_chash 的环构造和 find_chash_point 的二分查找。