-
Notifications
You must be signed in to change notification settings - Fork 2
/
consistent.go
140 lines (121 loc) · 3.2 KB
/
consistent.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
// Package consistent borrows ideas from "stathat.com/c/consistent"
// simplify it for performance, no concurrence guarantee any more!
package consistent
import (
"errors"
"hash/crc32"
"sort"
"strconv"
)
// Consistent holds the information about the members of the consistent hash circle.
type Consistent struct {
circle map[uint32]string
sortedHashes uints
state state
}
type uints []uint32
// Len returns the length of the uints array.
func (x uints) Len() int { return len(x) }
// Less returns true if element i is less than element j.
func (x uints) Less(i, j int) bool { return x[i] < x[j] }
// Swap exchanges elements i and j.
func (x uints) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
// state : state machine of Consistent
type state int
const (
// stateBad Before New, or in Sorting
stateBad state = iota
// stateAdding After New, Before Sorting
stateAdding
// stateSorted After Sorting
stateSorted
)
var (
// ErrEmptyCircle is the error returned when trying to get an element when nothing has been added to hash.
ErrEmptyCircle = errors.New("empty circle")
// ErrNotSorted is the error returned when trying to get an element when the consistent circle is not sorted.
ErrNotSorted = errors.New("not sorted")
)
// New creates a new Consistent object.
func New() *Consistent {
c := new(Consistent)
c.circle = make(map[uint32]string)
c.state = stateAdding
return c
}
// eltKey generates a string key for an element with an index.
func (c *Consistent) eltKey(elt string, idx int) string {
return strconv.Itoa(idx) + elt
}
// Add inserts a string element in the consistent hash numOfReplicas times.
func (c *Consistent) Add(elt string, numOfReplicas int) {
if c.state != stateAdding {
panic("state not stateAdding")
}
for i := 0; i < numOfReplicas; i++ {
c.circle[c.hashKey(c.eltKey(elt, i))] = elt
}
}
// Get returns an element close to where name hashes to in the circle.
func (c *Consistent) Get(name string) (string, error) {
if c.state != stateSorted {
return "", ErrNotSorted
}
if len(c.circle) == 0 {
return "", ErrEmptyCircle
}
key := c.hashKey(name)
i := c.search(key)
return c.circle[c.sortedHashes[i]], nil
}
func (c *Consistent) GetTwo(name string) (string, string, error) {
if c.state != stateSorted {
return "", "", ErrNotSorted
}
if len(c.circle) == 0 {
return "", "", ErrEmptyCircle
}
key := c.hashKey(name)
i := c.search(key)
a := c.circle[c.sortedHashes[i]]
if len(c.circle) == 1 {
return a, "", nil
}
start := i
var b string
for i = start + 1; i != start; i++ {
if i >= len(c.sortedHashes) {
i = 0
}
b = c.circle[c.sortedHashes[i]]
if b != a {
break
}
}
return a, b, nil
}
func (c *Consistent) search(key uint32) (i int) {
f := func(x int) bool {
return c.sortedHashes[x] > key
}
i = sort.Search(len(c.sortedHashes), f)
if i >= len(c.sortedHashes) {
i = 0
}
return
}
func (c *Consistent) hashKey(key string) uint32 {
return crc32.ChecksumIEEE([]byte(key))
}
// SortHashes before get
func (c *Consistent) SortHashes() {
c.state = stateBad
defer func() {
c.state = stateSorted
}()
c.sortedHashes = make(uints, 0, len(c.circle))
for k := range c.circle {
c.sortedHashes = append(c.sortedHashes, k)
}
sort.Sort(c.sortedHashes)
}