【一致哈希算法】

哈希算法的局限性

传统哈希算法（如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. 动态扩容：支持运行时添加节点，仅触发局部数据迁移。

性能优化示例

// 虚拟节点示例代码
type VirtualNode struct {
    HashKey uint32
    PhysicalNode string
}

func AddNode(ring *[]VirtualNode, nodeName string, replicaCount int) {
    for i := 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, j int) bool { return (*ring)[i].HashKey < (*ring)[j].HashKey })
}