/
consistenthash.go
85 lines (73 loc) · 1.67 KB
/
consistenthash.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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
package consistenthash
import (
"hash/crc32"
"sort"
"strconv"
"strings"
)
// HashFunc defines function to generate hash code
type HashFunc func(data []byte) uint32
// Map stores nodes and you can pick node from Map
type Map struct {
hashFunc HashFunc
replicas int
keys []int // sorted
hashMap map[int]string
}
// New creates a new Map
func New(replicas int, fn HashFunc) *Map {
m := &Map{
replicas: replicas,
hashFunc: fn,
hashMap: make(map[int]string),
}
if m.hashFunc == nil {
m.hashFunc = crc32.ChecksumIEEE
}
return m
}
// IsEmpty returns if there is no node in Map
func (m *Map) IsEmpty() bool {
return len(m.keys) == 0
}
// AddNode add the given nodes into consistent hash circle
func (m *Map) AddNode(keys ...string) {
for _, key := range keys {
if key == "" {
continue
}
for i := 0; i < m.replicas; i++ {
hash := int(m.hashFunc([]byte(strconv.Itoa(i) + key)))
m.keys = append(m.keys, hash)
m.hashMap[hash] = key
}
}
sort.Ints(m.keys)
}
// support hash tag
func getPartitionKey(key string) string {
beg := strings.Index(key, "{")
if beg == -1 {
return key
}
end := strings.Index(key, "}")
if end == -1 || end == beg+1 {
return key
}
return key[beg+1 : end]
}
// PickNode gets the closest item in the hash to the provided key.
func (m *Map) PickNode(key string) string {
if m.IsEmpty() {
return ""
}
partitionKey := getPartitionKey(key)
hash := int(m.hashFunc([]byte(partitionKey)))
// Binary search for appropriate replica.
idx := sort.Search(len(m.keys), func(i int) bool { return m.keys[i] >= hash })
// Means we have cycled back to the first replica.
if idx == len(m.keys) {
idx = 0
}
return m.hashMap[m.keys[idx]]
}