Golang的一致性哈希实现
一致性哈希的具体介绍，可以参考： http://www.cnblogs.com/haippy/archive/2011/12/10/2282943.html
import (
"hash/crc32"
"sort"
"strconv"
"sync"
)
const DEFAULT_REPLICAS = 100
type SortKeys []uint32
func (sk SortKeys) Len() int {
return len(sk)
}
func (sk SortKeys) Less(i, j int) bool {
return sk[i] < sk[j]
}
func (sk SortKeys) Swap(i, j int) {
sk[i], sk[j] = sk[j], sk[i]
}
type HashRing struct {
Nodes map[uint32]string
Keys SortKeys
sync.RWMutex
}
func (hr *HashRing)New(nodes []string) {
if nodes == nil {
return
}
hr.Nodes = make(map[uint32]string)
hr.Keys = SortKeys{}
for _, node := range(nodes) {
for i := 0; i < DEFAULT_REPLICAS; i++ {
str := node + strconv.Itoa(i)
hr.Nodes[hr.hashStr(str)] = node
hr.Keys = append(hr.Keys, hr.hashStr(str))
}
}
sort.Sort(hr.Keys)
}
func (hr *HashRing) hashStr(key string) uint32 {
return crc32.ChecksumIEEE([]byte(key))
}
func (hr *HashRing) GetNode(key string) string {
hr.RLock()
defer hr.RUnlock()
hash := hr.hashStr(key)
i := hr.get_position(hash)
return hr.Nodes[hr.Keys[i]]
}
func (hr *HashRing) get_position(hash uint32) int {
i := sort.Search(len(hr.Keys), func(i int) bool {
return hr.Keys[i] >= hash})
if i < len(hr.Keys) {
if i == len(hr.Keys) - 1 {
return 0
} else {
return i
}
} else {
return len(hr.Keys) - 1
}
}
