Consistent Hashing: Algorithmic Tradeoffs

 server := serverList[hash(key) % N]
  • When adding or removing servers, only 1/nth of the keys should move.
  • Don’t move any keys that don’t need to move.
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]]
}

A Brief Digression on Ketama

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)))

“Are we done?” OR “Why Is This Still a Research Topic?”

Jump Hash

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)
}

“Are we done?” OR “Why Is This Still a Research Topic?” (2)

Multi-Probe Consistent Hashing

Rendezvous Hashing

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]
}

Maglev Hashing

Replication

Weighted Hosts

Load Balancing

Benchmarks

Benchmarks for a single lookup with different node counts; timings in nanoseconds

Conclusion

Source Code

--

--

--

Gopher. https://buymeacoffee.com/dgryski

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Creating an environment with Airflow and DBT on AWS (part 1)

How classes and objects are used in Python

6 quick ways to cut cost on your Lambdas

Continuous Engineering with the Serverless Framework

Bringing the Cloud to your Laptop: Provisioning Fedora CoreOS VMs in minutes on Mac OSX with…

WebSocket and Socket.Io: A Practical Application

Blockchain Loyalty Program in One Day

Those materials have the goal to offer remarkable immunity to the people and that too with out…

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
Damian Gryski

Damian Gryski

Gopher. https://buymeacoffee.com/dgryski

More from Medium

3 ways to tackle the longest increasing subsequence problem(Golang)

Getting started with GO Programming Language — Part Two

Heap Sort is based on the Heapify algorithm using GO lang.

[Solution]Exercise: Maps | A Tour of Go