【一致哈希算法】

哈希算法的局限性

传统哈希算法（如hash(key) % N）在集群扩容或缩容时，数据迁移成本极高。例如，3节点扩容至4节点需迁移75%的数据，10节点扩容至11节点需迁移90.9%的数据。这是由于取模运算的基数（节点数N）变化导致所有key的映射关系被破坏。

一致哈希的核心原理

一致哈希将哈希空间组织为环形结构（模数为2^32），节点和key均通过哈希函数映射到环上。key的寻址规则为：从key的位置顺时针查找，遇到的第一个节点即为目标节点。
优势：节点变化时仅影响相邻区间的数据。例如：

• 扩容时：仅需将新节点与前一节点之间的数据迁移至新节点。
• 缩容时：仅故障节点与前一节点之间的数据需重新分配。

数据迁移成本对比

• 3节点→4节点：迁移24.3%数据（传统哈希需75%）。
• 10节点→11节点：迁移6.48%数据（传统哈希需90.9%）。

虚拟节点解决负载不均

当物理节点较少时，可能出现数据分布倾斜（如80%请求集中在单个节点）。通过为每个物理节点创建多个虚拟节点（如"Node-A-01"、"Node-A-02"等），并将虚拟节点均匀映射到哈希环上，可实现：

• 更均匀的数据分布：虚拟节点分散后，物理节点承载的key趋于平衡。
• 动态权重调整：通过增减虚拟节点数量，可调整不同物理节点的负载比例。

实现建议

1. 哈希函数选择：使用CRC32、MD5等均匀性好的哈希算法。
2. 虚拟节点数量：通常设置为物理节点的100~200倍，具体数值需通过压测确定。
3. 异常处理：节点故障时自动跳过，并将请求路由至下一可用节点。
4. 动态扩容：支持运行时添加节点，仅触发局部数据迁移。

性能优化示例

// 虚拟节点示例代码typeVirtualNodestruct{HashKeyuint32PhysicalNodestring}funcAddNode(ring*[]VirtualNode,nodeNamestring,replicaCountint){fori:=0;i<replicaCount;i++{vnode:=VirtualNode{HashKey:crc32.ChecksumIEEE([]byte(fmt.Sprintf("%s-%d",nodeName,i))),PhysicalNode:nodeName,}*ring=append(*ring,vnode)}sort.Slice(*ring,func(i,jint)bool{return(*ring)[i].HashKey<(*ring)[j].HashKey})}