一致性哈希

作者： /

为什么需要一致性哈希

分布式系统中，数据要按 key 分散到多个节点。传统做法 hash(key) % n 的问题在于：节点数 n 一变（扩容或宕机），几乎所有 key 都要重新映射，引发大规模数据迁移，这在缓存集群里等于全量缓存失效，代价极高。

一致性哈希（Consistent Hashing）解决的就是”节点增减时最小化数据迁移”：它只影响哈希环上相邻的一小段数据，把迁移量降到最低。

原理

  1. 哈希环：把哈希值空间（如 0 ~ 2³²-1）首尾相接成一个环；
  2. 节点上环：每个节点用哈希函数映射到环上的一个点；
  3. 数据定位：key 也哈希到环上，顺时针找到的第一个节点就是它的归属节点。

节点增减时，只有”该节点与逆时针前一个节点之间”的 key 需要迁移到新节点，其余数据位置不变——这就是迁移量小的原因。

虚拟节点

节点少时哈希落点可能分布不均，导致负载倾斜。解决办法：每个物理节点复制出 replicas 个虚拟节点分布在环上，让数据分布更均匀。真实系统中（如 Redis Cluster、Cassandra）虚拟节点是标配。

Golang 实现

package consistenthash

import (
    "hash/crc32"
    "sort"
    "strconv"
)

type Hash func(data []byte) uint32

// Map 一致性哈希环
type Map struct {
    hash     Hash
    replicas int            // 每个物理节点的虚拟节点数
    keys     []int          // 有序的哈希环
    hashMap  map[int]string // 虚拟节点哈希值 -> 物理节点
}

func New(replicas int, fn Hash) *Map {
    m := &Map{replicas: replicas, hash: fn, hashMap: make(map[int]string)}
    if m.hash == nil {
        m.hash = crc32.ChecksumIEEE
    }
    return m
}

// Add 添加节点：每个物理节点生成 replicas 个虚拟节点
func (m *Map) Add(keys ...string) {
    for _, key := range keys {
        for i := 0; i < m.replicas; i++ {
            h := int(m.hash([]byte(strconv.Itoa(i) + key)))
            m.keys = append(m.keys, h)
            m.hashMap[h] = key
        }
    }
    sort.Ints(m.keys)
}

// Get 顺时针找第一个节点
func (m *Map) Get(key string) string {
    if len(m.keys) == 0 {
        return ""
    }
    h := int(m.hash([]byte(key)))
    idx := sort.Search(len(m.keys), func(i int) bool { return m.keys[i] >= h })
    if idx == len(m.keys) { // 环尾绕回开头
        idx = 0
    }
    return m.hashMap[m.keys[idx]]
}

// Remove 移除节点
func (m *Map) Remove(key string) {
    for i := 0; i < m.replicas; i++ {
        h := int(m.hash([]byte(strconv.Itoa(i) + key)))
        idx := sort.SearchInts(m.keys, h)
        if idx < len(m.keys) && m.keys[idx] == h {
            m.keys = append(m.keys[:idx], m.keys[idx+1:]...)
        }
        delete(m.hashMap, h)
    }
}

使用示例：ch := consistenthash.New(3, nil) 后 ch.Add("Node1","Node2","Node3")，ch.Get("key1") 得到归属节点；新增/移除节点后，只有相邻区间的 key 会换节点。

复杂度

  • 添加节点：O(V log V)（V 为虚拟节点总数，排序主导）；
  • 查找节点：O(log V)（二分）；
  • 空间：O(V)。

应用场景

  • 分布式缓存：Memcached 集群、Redis 客户端分片——节点增减只迁移相邻数据，避免全局缓存失效；
  • 负载均衡 / 会话保持：Nginx、HAProxy 把用户 IP/Session 哈希到固定后端，实现 sticky session，后端增减影响最小；
  • CDN：边缘节点路由（Akamai、Cloudflare）；
  • 分布式计算：MapReduce 把相同 key 的数据固定送到同一节点，保证数据本地性。

注意事项

  • 虚拟节点倍数要权衡：太少分布不均，太多内存和排序开销上升（常见取值 100–200）；
  • 哈希函数建议用均匀性好的（如 MD5/一致性好的算法），CRC32 简单但分布一般，数据量大时建议替换；
  • 只解决”分布与迁移”，节点容量不均（如异构机器）还需要加权虚拟节点。
滚动至顶部