diff options
Diffstat (limited to 'vendor/github.com/golang/groupcache/consistenthash')
-rw-r--r-- | vendor/github.com/golang/groupcache/consistenthash/consistenthash.go | 81 | ||||
-rw-r--r-- | vendor/github.com/golang/groupcache/consistenthash/consistenthash_test.go | 110 |
2 files changed, 191 insertions, 0 deletions
diff --git a/vendor/github.com/golang/groupcache/consistenthash/consistenthash.go b/vendor/github.com/golang/groupcache/consistenthash/consistenthash.go new file mode 100644 index 000000000..a9c56f076 --- /dev/null +++ b/vendor/github.com/golang/groupcache/consistenthash/consistenthash.go @@ -0,0 +1,81 @@ +/* +Copyright 2013 Google Inc. + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. +*/ + +// Package consistenthash provides an implementation of a ring hash. +package consistenthash + +import ( + "hash/crc32" + "sort" + "strconv" +) + +type Hash func(data []byte) uint32 + +type Map struct { + hash Hash + replicas int + keys []int // Sorted + hashMap map[int]string +} + +func New(replicas int, fn Hash) *Map { + m := &Map{ + replicas: replicas, + hash: fn, + hashMap: make(map[int]string), + } + if m.hash == nil { + m.hash = crc32.ChecksumIEEE + } + return m +} + +// Returns true if there are no items available. +func (m *Map) IsEmpty() bool { + return len(m.keys) == 0 +} + +// Adds some keys to the hash. +func (m *Map) Add(keys ...string) { + for _, key := range keys { + for i := 0; i < m.replicas; i++ { + hash := int(m.hash([]byte(strconv.Itoa(i) + key))) + m.keys = append(m.keys, hash) + m.hashMap[hash] = key + } + } + sort.Ints(m.keys) +} + +// Gets the closest item in the hash to the provided key. +func (m *Map) Get(key string) string { + if m.IsEmpty() { + return "" + } + + hash := int(m.hash([]byte(key))) + + // 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]] +} diff --git a/vendor/github.com/golang/groupcache/consistenthash/consistenthash_test.go b/vendor/github.com/golang/groupcache/consistenthash/consistenthash_test.go new file mode 100644 index 000000000..1a37fd7ff --- /dev/null +++ b/vendor/github.com/golang/groupcache/consistenthash/consistenthash_test.go @@ -0,0 +1,110 @@ +/* +Copyright 2013 Google Inc. + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. +*/ + +package consistenthash + +import ( + "fmt" + "strconv" + "testing" +) + +func TestHashing(t *testing.T) { + + // Override the hash function to return easier to reason about values. Assumes + // the keys can be converted to an integer. + hash := New(3, func(key []byte) uint32 { + i, err := strconv.Atoi(string(key)) + if err != nil { + panic(err) + } + return uint32(i) + }) + + // Given the above hash function, this will give replicas with "hashes": + // 2, 4, 6, 12, 14, 16, 22, 24, 26 + hash.Add("6", "4", "2") + + testCases := map[string]string{ + "2": "2", + "11": "2", + "23": "4", + "27": "2", + } + + for k, v := range testCases { + if hash.Get(k) != v { + t.Errorf("Asking for %s, should have yielded %s", k, v) + } + } + + // Adds 8, 18, 28 + hash.Add("8") + + // 27 should now map to 8. + testCases["27"] = "8" + + for k, v := range testCases { + if hash.Get(k) != v { + t.Errorf("Asking for %s, should have yielded %s", k, v) + } + } + +} + +func TestConsistency(t *testing.T) { + hash1 := New(1, nil) + hash2 := New(1, nil) + + hash1.Add("Bill", "Bob", "Bonny") + hash2.Add("Bob", "Bonny", "Bill") + + if hash1.Get("Ben") != hash2.Get("Ben") { + t.Errorf("Fetching 'Ben' from both hashes should be the same") + } + + hash2.Add("Becky", "Ben", "Bobby") + + if hash1.Get("Ben") != hash2.Get("Ben") || + hash1.Get("Bob") != hash2.Get("Bob") || + hash1.Get("Bonny") != hash2.Get("Bonny") { + t.Errorf("Direct matches should always return the same entry") + } + +} + +func BenchmarkGet8(b *testing.B) { benchmarkGet(b, 8) } +func BenchmarkGet32(b *testing.B) { benchmarkGet(b, 32) } +func BenchmarkGet128(b *testing.B) { benchmarkGet(b, 128) } +func BenchmarkGet512(b *testing.B) { benchmarkGet(b, 512) } + +func benchmarkGet(b *testing.B, shards int) { + + hash := New(50, nil) + + var buckets []string + for i := 0; i < shards; i++ { + buckets = append(buckets, fmt.Sprintf("shard-%d", i)) + } + + hash.Add(buckets...) + + b.ResetTimer() + + for i := 0; i < b.N; i++ { + hash.Get(buckets[i&(shards-1)]) + } +} |