一致性哈希

原理

一致性哈希算法将整个哈希值空间映射成一个虚拟的圆环，整个哈希空间的取值范围为0-2^32-1。整个空间按顺时针方向组织。0-2^32-1在零点中方向重合。接下来使用如下算法对服务请求进行映射，将服务请求使用哈希算法算出对应的hash值，然后根据hash值的位置沿圆环顺时针查找，第一台遇到的服务器就是所对应的处理请求服务器。

原理简单实现

type HashList []uint32


func (h HashList) Len() int {
    return len(h)
}


func (h HashList) Less(i, j int) bool {
    return h[i] < h[j]
}


func (h HashList) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}


type ConsistentHashBalancer struct {
    hashMap map[uint32]string
    hashList HashList
}


func (c *ConsistentHashBalancer) Add(addr string) {
    // 即0~2^32-1
    hash := crc32.ChecksumIEEE([]byte(addr))
    c.hashMap[hash] = addr
    c.hashList = append(c.hashList, hash)
    // 对哈希环排序
    sort.Sort(c.hashList)
}


func (c *ConsistentHashBalancer) Get(key string) (addr string) {
    hash := crc32.ChecksumIEEE([]byte(key))
    // 找到该key的hash落在哪个节点即 nodeHash <= hash < nextNodeHash
    targetNodeHashIndex := sort.Search(len(c.hashList), func(i int) bool {
        return c.hashList[i] >= hash
    })
    return c.hashMap[c.hashList[targetNodeHashIndex]]
}