1

算法

CDN系统组网与安全

分布式缓存路由

一致性哈希算法如何实现节点增减时的最小数据迁移？

逐步推理：
1. 定义哈希环：将整个哈希空间 [0, 2^m-1] 视为一个首尾相接的环。
2. 节点映射：对每个物理节点计算哈希值 h(node)，将其放置在环上。
3. 数据映射：对每个数据键 key 计算哈希值 h(key)，顺时针找到第一个大于等于该值的节点作为归属。
4. 数学方程式：设节点集合为 N，数据键集合为 K，迁移比例 E = 1/

N

（当节点数远大于1时）。
- 推导：新加入节点 j 时，只有落在 j 与前驱节点之间的数据需要迁移，该区间长度占环的比例