-
Notifications
You must be signed in to change notification settings - Fork 0
/
consistent_hash.go
71 lines (63 loc) · 1.52 KB
/
consistent_hash.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package gee_cache
import (
"fmt"
"hash/crc32"
"log"
"sort"
)
// hash 函数的形式
type HashFunc func(data []byte) uint32
type Map struct {
// hash 函数
hash HashFunc
// hash环,逻辑上的环,实际上存储的是虚拟节点在环上的 hash 值
keys []int
// 实际节点的虚拟节点倍数
replicas int
// 虚拟节点和实际节点的映射关系,虚拟节点hash -> 真实节点 name
hashMap map[uint32]string
}
func NewMap(hash HashFunc, replicas int) *Map {
m := new(Map)
m.hash = hash
if hash == nil {
m.hash = crc32.ChecksumIEEE
}
m.replicas = replicas
m.keys = make([]int, 0)
m.hashMap = make(map[uint32]string, 0)
return m
}
// Add 添加实际节点
func (m *Map) Add(nodes ...string) {
for _, node := range nodes {
if node == ""{
log.Println("skip the node: " + node)
continue
}
for i := 0; i < m.replicas; i++ {
// 创建虚拟节点
virtualKey := fmt.Sprintf("%v-%v", i, node)
h := m.hash([]byte(virtualKey))
m.keys = append(m.keys, int(h))
m.hashMap[h] = node
}
}
// 从小到大排序
sort.Ints(m.keys)
}
// Get 获取key实际应该到哪个节点获取,返回节点名称
func (m *Map) Get(key string) string {
h := m.hash([]byte(key))
if node, ok:= m.hashMap[h]; ok {
return node
}
hi := int(h)
l:= len(m.keys)
idx := sort.Search(l, func(i int) bool {
// 遍历环的值,如果出现大于或等于key的hash值就找到了虚拟节点
// 如果没找到会返回 l
return m.keys[i] >= hi
})
return m.hashMap[uint32(m.keys[(idx%l)])]
}