mirror of
https://github.com/mailgun/groupcache.git
synced 2024-11-16 23:10:53 +00:00
89ec0544ae
The binary search quickly out-paces the linear search, even for a small number of shards and replicas. benchmark old ns/op new ns/op delta BenchmarkGet8 122 122 +0.00% BenchmarkGet32 471 137 -70.91% BenchmarkGet128 5619 254 -95.48% BenchmarkGet512 90302 406 -99.55%
82 lines
1.8 KiB
Go
82 lines
1.8 KiB
Go
/*
|
|
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]]
|
|
}
|