Consistent Hashing: Algorithmic Tradeoffs

 server := serverList[hash(key) % N]
It scrolls on like this for a while
func (m *Map) Add(nodes ...string) {
for _, n := range nodes {
for i := 0; i < m.replicas; i++ {
hash := int(m.hash([]byte(strconv.Itoa(i) + " " + n)))
m.nodes = append(m.nodes, hash)
m.hashMap[hash] = n
}
}
sort.Ints(m.nodes)
}
func (m *Map) Get(key string) string {
hash := int(m.hash([]byte(key)))
idx := sort.Search(len(m.keys),
func(i int) bool { return m.keys[i] >= hash }
)
if idx == len(m.keys) {
idx = 0
}
return m.hashMap[m.keys[idx]]
}
unsigned int k_limit = floorf(pct * 40.0 * ketama->numbuckets);
float floorf(float x);
unsigned int numbuckets;
float pct;
limit := int(float32(float64(pct) * 40.0 * float64(numbuckets)))
func Hash(key uint64, numBuckets int) int32 {
var b int64 = -1
var j int64
for j < int64(numBuckets) {
b = j
key = key*2862933555777941757 + 1
j = int64(float64(b+1) *
(float64(int64(1)<<31) / float64((key>>33)+1)))
}
return int32(b)
}
func (r *Rendezvous) Lookup(k string) string {
khash := r.hash(k)

var midx int
var mhash = xorshiftMult64(khash ^ r.nhash[0])

for i, nhash := range r.nhash[1:] {
if h := xorshiftMult64(khash ^ nhash); h > mhash {
midx = i + 1
mhash = h
}
}

return r.nstr[midx]
}
Benchmarks for a single lookup with different node counts; timings in nanoseconds

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store