-
Notifications
You must be signed in to change notification settings - Fork 101
/
consistenthash.go
154 lines (130 loc) · 3.6 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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
// Copyright 2019, Chef. All rights reserved.
// https://github.com/q191201771/naza
//
// Use of this source code is governed by a MIT-style license
// that can be found in the License file.
//
// Author: Chef (191201771@qq.com)
package consistenthash
import (
"errors"
"hash/crc32"
"math"
"sort"
"strconv"
)
var ErrIsEmpty = errors.New("naza.consistenthash: is empty")
type ConsistentHash interface {
Add(nodes ...string)
Del(nodes ...string)
Get(key string) (node string, err error)
// @return: 返回的 map 的
// key 为添加到内部的 node,
// value 为该 node 在环上所占的 point 个数。
// 我们可以通过各个 node 对应的 point 个数是否接近,来判断各 node 在环上的分布是否均衡。
// map 的所有 value 加起来应该等于 (math.MaxUint32 + 1)
Nodes() map[string]uint64
}
type HashFunc func([]byte) uint32
type Option struct {
hfn HashFunc
}
var defaultOption = Option{
hfn: crc32.ChecksumIEEE,
}
type ModOption func(option *Option)
// @param dups: 每个实际的 node 转变成多少个环上的节点,必须大于等于1
// @param modOptions: 可修改内部的哈希函数,比如替换成murmur32的开源实现,可以这样:
//
// import "github.com/spaolacci/murmur3"
// import "github.com/q191201771/naza/pkg/consistenthash"
//
// ch := consistenthash.New(1000, func(option *Option) {
// option.hfn = func(bytes []byte) uint32 {
// h := murmur3.New32()
// h.Write(bytes)
// return h.Sum32()
// }
// })
func New(dups int, modOptions ...ModOption) ConsistentHash {
option := defaultOption
for _, fn := range modOptions {
fn(&option)
}
return &consistentHash{
point2node: make(map[uint32]string),
dups: dups,
option: option,
}
}
type consistentHash struct {
point2node map[uint32]string
points []uint32
dups int
option Option
}
func (ch *consistentHash) Add(nodes ...string) {
for _, node := range nodes {
for i := 0; i < ch.dups; i++ {
point := ch.hash2point(virtualKey(node, i))
ch.point2node[point] = node
ch.points = append(ch.points, point)
}
}
sortSlice(ch.points)
}
func (ch *consistentHash) Del(nodes ...string) {
for _, node := range nodes {
for i := 0; i < ch.dups; i++ {
point := ch.hash2point(virtualKey(node, i))
delete(ch.point2node, point)
}
}
ch.points = nil
for k := range ch.point2node {
ch.points = append(ch.points, k)
}
sortSlice(ch.points)
}
func (ch *consistentHash) Get(key string) (node string, err error) {
if len(ch.points) == 0 {
return "", ErrIsEmpty
}
point := ch.hash2point(key)
// 从数组中找出满足 point 值 >= key 所对应 point 值的最小的元素
index := sort.Search(len(ch.points), func(i int) bool {
return ch.points[i] >= point
})
if index == len(ch.points) {
index = 0
}
return ch.point2node[ch.points[index]], nil
}
func (ch *consistentHash) Nodes() map[string]uint64 {
if len(ch.points) == 0 {
return nil
}
ret := make(map[string]uint64)
prev := uint64(0)
for _, point := range ch.points {
node := ch.point2node[point]
ret[node] = ret[node] + uint64(point) - prev
prev = uint64(point)
}
// 最后一个 node 到终点位置的 point 都归入第一个 node
point := ch.points[len(ch.points)-1]
node := ch.point2node[point]
ret[node] = ret[node] + uint64(math.MaxUint32-point+1)
return ret
}
func (ch *consistentHash) hash2point(key string) uint32 {
return ch.option.hfn([]byte(key))
}
func virtualKey(node string, index int) string {
return node + strconv.Itoa(index)
}
func sortSlice(a []uint32) {
sort.Slice(a, func(i, j int) bool {
return a[i] < a[j]
})
}