一致性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