一致性Hash算法

一致性Hash算法，比如負責均衡時候，連接到哪個節點，除了一般的隨機算法，Round Robin算法外，還可以通過Hash映射到具體的ip上去

下面是golang版本的Hash一致性算法：

package main

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

const DEFAULT_REPLICAS = 160

type HashRing []uint32

func (c HashRing) Len() int {
    return len(c)
}

func (c HashRing) Less(i, j int) bool {
    return c[i] < c[j]
}

func (c HashRing) Swap(i, j int) {
    c[i], c[j] = c[j], c[i]
}

//Hash節點 ID IP Port HostName Weight
type Node struct {
    Id       int
    Ip       string
    Port     int
    HostName string
    Weight   int
}

// NewNode(i, "172.18.1."+si, 8080, "host_"+si, 1)
func NewNode(id int, ip string, port int, name string, weight int) *Node {
    return &Node{
        Id:       id,
        Ip:       ip,
        Port:     port,
        HostName: name,
        Weight:   weight,
    }
}

//一致性
type Consistent struct {
    Nodes     map[uint32]Node
    numReps   int
    Resources map[int]bool
    ring      HashRing //附帶存儲c.Nodes,方便排序之用
    sync.RWMutex
}

func NewConsistent() *Consistent {
    return &Consistent{
        Nodes:     make(map[uint32]Node),
        numReps:   DEFAULT_REPLICAS,
        Resources: make(map[int]bool),
        ring:      HashRing{},
    }
}

func (c *Consistent) Add(node *Node) bool {
    c.Lock()
    defer c.Unlock()

    if _, ok := c.Resources[node.Id]; ok {
        return false
    }

    count := c.numReps * node.Weight //權重高備份數據越多
    for i := 0; i < count; i++ {
        str := c.joinStr(i, node) //多備份
        c.Nodes[c.hashStr(str)] = *(node)
    }
    c.Resources[node.Id] = true
    c.sortHashRing()
    return true
}

func (c *Consistent) sortHashRing() {
    c.ring = HashRing{}
    for k := range c.Nodes { //這樣遍歷map只能返回key,uint32的hash key
        c.ring = append(c.ring, k)
    }
    sort.Sort(c.ring)
}

func (c *Consistent) joinStr(i int, node *Node) string {
    return node.Ip + "*" + strconv.Itoa(node.Weight) +
        "-" + strconv.Itoa(i) +
        "-" + strconv.Itoa(node.Id)
}

//最核心都是key映射成ID的算法
// 高運算性能,低碰撞率Hash算法-----MurMurHash算法 :https://github.com/spaolacci/murmur3
func (c *Consistent) hashStr(key string) uint32 {
    return crc32.ChecksumIEEE([]byte(key))
}

func (c *Consistent) Get(key string) Node {
    c.RLock()
    defer c.RUnlock()

    hash := c.hashStr(key)

    i := c.search(hash)

    return c.Nodes[c.ring[i]]
}

func (c *Consistent) search(hash uint32) int {

    i := sort.Search(len(c.ring), func(i int) bool { return c.ring[i] >= hash })
    if i < len(c.ring) {
        if i == len(c.ring)-1 {
            return 0
        } else {
            return i
        }
    } else {
        return len(c.ring) - 1
    }
}

func (c *Consistent) Remove(node *Node) {
    c.Lock()
    defer c.Unlock()

    if _, ok := c.Resources[node.Id]; !ok {
        return
    }

    delete(c.Resources, node.Id) //刪除標志

    count := c.numReps * node.Weight
    for i := 0; i < count; i++ {
        str := c.joinStr(i, node)
        delete(c.Nodes, c.hashStr(str)) //刪除內容
    }
    c.sortHashRing()
}

func main() {

    cHashRing := NewConsistent()

    for i := 0; i < 10; i++ {
        si := fmt.Sprintf("%d", i)
        cHashRing.Add(NewNode(i, "172.18.1."+si, 8080, "host_"+si, 1))
    }

    ipMap := make(map[string]int, 0)
    for i := 0; i < 1000; i++ {
        si := fmt.Sprintf("key%d", i)
        k := cHashRing.Get(si)
        if _, ok := ipMap[k.Ip]; ok {
            ipMap[k.Ip] += 1
        } else {
            ipMap[k.Ip] = 1
        }
    }

    for k, v := range ipMap {
        fmt.Println("Node IP:", k, " count:", v)
    }

}

總結：最核心就是MurMurHash算法，怎么把Hash的key映射成具體的ID

來自： http://studygolang.com/wr?u=http%3a%2f%2fblog.csdn.net%2fxcltapestry%2farticle%2fdetails%2f43898807