Practic In Consistent Hash

普通的Hash是通过取模方式

这种hash对修改位置很敏感，前面的修改会直接影响后面的数据。比如删除节点2，则3、4将有1/2的面积发生变化，1有1/4变化，整个系统将有1/3的覆盖面积发生变化，如果删除节点1，那么直接有1/2的覆盖发生变化。而理想情况是只有1/4。

一致性hash的思想是打乱这种顺序，让节点均匀分布。当删除某个节点时，也可以做到均匀变化

打乱后带来了新问题，就是没办法通过取模来找到节点。实践中一般是用一个数组记录hash环上每个范围对应的节点。数组在建立时先排序，查找时用快速排序法找到对应位置。


package main

import (
    "crypto/sha1"
    "fmt"
    "sort"
    "strconv"

    "github.com/brianvoe/gofakeit/v7"
)

type HashInterface interface {
    AddNode(node string)
    RemoveNode(node string)
    GetNode(key string) string
}

type HashRing struct {
    nodes       []int
    nodeMap     map[int]string
    virtualNode int  // 虚拟节点倍数，虚拟节点数 = 虚拟节点倍数 * 节点数。这个越大分布越均匀，但是会占用更多内存
}

func NewHashRing(virtualNode int) *HashRing {
    return &HashRing{
        nodeMap:     make(map[int]string),
        virtualNode: virtualNode,
    }
}

func (h *HashRing) AddNode(node string) {
    for i := 0; i < h.virtualNode; i++ {
        virtualNodeKey := node + "#" + strconv.Itoa(i)
        hash := int(sha1Hash(virtualNodeKey))
        h.nodes = append(h.nodes, hash)
        h.nodeMap[hash] = node
    }
    sort.Ints(h.nodes)
}

func (h *HashRing) RemoveNode(node string) {
    for i := 0; i < h.virtualNode; i++ {
        virtualNodeKey := node + "#" + strconv.Itoa(i)
        hash := int(sha1Hash(virtualNodeKey))
        index := sort.SearchInts(h.nodes, hash)
        h.nodes = append(h.nodes[:index], h.nodes[index+1:]...)
        delete(h.nodeMap, hash)
    }
}

func (h *HashRing) GetNode(key string) string {
    hash := int(sha1Hash(key))
    index := sort.SearchInts(h.nodes, hash)
    if index >= len(h.nodes) {
        index = 0
    }
    return h.nodeMap[h.nodes[index]]
}

type ModHash struct {
    nodes []string
}

func NewModHash() *ModHash {
    return &ModHash{}
}

func (h *ModHash) AddNode(node string) {
    h.nodes = append(h.nodes, node)
}

func (h *ModHash) RemoveNode(node string) {
    i := sort.SearchStrings(h.nodes, node)
    h.nodes = append(h.nodes[:i], h.nodes[i+1:]...)
}

func (h *ModHash) GetNode(key string) string {
    hash := int(sha1Hash(key))
    index := hash % len(h.nodes)
    return h.nodes[index]
}

func sha1Hash(key string) uint32 {
    h := sha1.New()
    h.Write([]byte(key))
    bs := h.Sum(nil)
    return uint32((int(bs[0]) << 24) + (int(bs[1]) << 16) + (int(bs[2]) << 8) + int(bs[3]))
}

func test(h HashInterface) {
    h.AddNode("ServerA")
    h.AddNode("ServerB")
    h.AddNode("ServerC")
    h.AddNode("ServerD")
    keys := make(map[string]string, 1000)
    for i := 0; i < 1000; i++ {
        key := gofakeit.Word()
        keys[key] = h.GetNode(key)
    }
    h.RemoveNode("ServerB")
    fmt.Println("After removing ServerB")
    miss := 0
    for k, v := range keys {
        if h.GetNode(k) != v {
            miss += 1
        }
    }
    fmt.Println("miss rate:", float64(miss)/float64(len(keys)))
}

func main() {
    mod := NewModHash()
    ring := NewHashRing(8) // 一般来说越大越接近理论值

    test(mod)
    test(ring)
}

通过代码模拟。普通的hash算法，删除第二个节点ServerB后miss百分比为72%，而一致性算法为19%（比理论值还好，当然这个跟数据集有关）。

annidy / notes

Practic In Consistent Hash #301