一致性哈希

基本介绍

对请求进行路由时，为了使同源请求可以路由到同一个服务节点上，一般使用 hash 算法进行请求分发（负载均衡）

如下 Nginx 模板配置，默认情况下使用一致性 hash 的负载均衡策略：

map $http_routingkey $hash_key { # 检查 http 请求头中的 http_routingkey 的 value
    default         $http_routingkey; # hash_key 赋值为 http_routingkey
    ""              $http_x_forwarded_for; # hash_key 赋值为客户端 IP
}

map $http_routingkey $route_strategy {
    default         hash; # route_strategy 为 hash
    ""              round-robin;
}

upstream svr {
    hash $hash_key consistent; # 基于 hash_key 的一致性 hash
    {{range service "svr"}}server {{.Address}}:{{.Port}} max_fails=2 fail_timeout=2s;
    {{else}}server 127.0.0.1:65535 down;
    keepalive 200;
}

一致性 hash 在保证了同一个 routing_key 下的请求可以路由到同一个 server，同时保证当 server 的可用节点发生增加或者下线情况时，不会发生大规模的请求重分配

在分布式缓存的场景下，如果不要求缓存节点间的同步，一致性哈希的缓存请求策略可以避免发生缓存雪崩，导致大量请求直接访问 DB

实现

请求的 key 和服务节点的标识采用同一种 hash 算法；通过一个环形数组来存储服务节点的 hash 值，请求会路由到顺时针下后面的第一个虚拟节点处（通过 map 存虚拟节点到服务节点的映射，引入虚拟节点的目的是为了使节点分散更均匀）

type HashFunc func(data []byte) uint32 // hash 环从 0 ~ 2^32 - 1

type Map struct {
    hash HashFunc
    replicas int // 一个真实节点对应的虚拟节点数
    ring []int
    mp map[int]string // 虚拟节点与真实节点的映射
}

func New(replicas int, f HashFunc) *Map {
    ret := &Map{
        replicas: replicas,
        hash: f,
        mp: make(map[int]string),
    }
    if ret.hash == nil {
        ret.hash = crc32.ChecksumIEEE
    }
    return ret
}


// node : "ip:port"
func (m *Map) Add(nodes ...string) {
    for _, node := range nodes {
        for i := 0; i < m.replicas; i++ {
            hash := m.hash([]byte(strconv.Itoa(i) + node))
            m.ring = append(m.ring, int(hash))
            m.mp[int(hash)] = node
        }
    }
    // sort.Slice(m.ring, func(i, j int) bool {
    //  return m.ring[i] < m.ring[j]
    // })
    sort.Ints(m.ring)
}

func (m *Map) Get(key string) string {
    target := int(m.hash([]byte(key)))
    l, r := 0, len(m.ring) - 1
    idx := len(m.ring)
    for l <= r {
        mid := (l + r) / 2
        if m.ring[mid] < target {
            l = mid + 1
        } else {
            idx = mid
            r = mid - 1
        }
    }

    idx = idx % len(m.ring)

    return m.mp[m.ring[idx]]
}

crc32.ChecksumIEEE 的计算方法为：

1. 将输入数据（[]byte）看作一个大的二进制数
2. 在数据末尾补32个0（左移32位）
3. 用 CRC-IEEE 多项式对这个数进行模2除法（基于亦或操作的竖式计算）
4. 余数就是CRC值

可以保证在 0 ~ 2^32 - 1 区间分布均匀