Stop 20 · System DesignTopics · 12/15

Consistent Hashing

In short

Spread keys across 4 cache servers with hash % 4, add a fifth, and most keys suddenly map to a different server. Consistent hashing fixes that by moving only a small slice.

A hashing technique that minimizes data redistribution when nodes are added or removed from a distributed cache or database cluster — instead of remapping almost everything on every change.

The purple blob walks clockwise around a round dining table, placing plates at each chair.

Think of it like this

Plates around a round table

Picture a round table with chairs at fixed spots. Each guest walks clockwise from where they enter and sits at the first chair they reach. Add a new chair, and only the guests just before it move over. Everyone else stays put. That circle is the hash ring.

Watch it happen

A hash ring with 10 positions

1/5The ring has positions 0 to 9, and the end wraps to the start. Servers A, B and C hash to 1, 4 and 7.

The big ideas

What you need to know

A ring of hashes

Servers and keys are hashed onto the same circle. Each key belongs to the next server clockwise.

Small moves on change

Adding or removing a server moves only the keys next to it, roughly 1/N of them, not almost all.

Virtual nodes

Each server is placed at many points, so load evens out and a dead server's keys spread across all the others.

Used in real systems

Distributed caches and Dynamo-style databases like Cassandra use this idea to decide which node holds which data.

See it in code

Walk through the code

1import { createHash } from "node:crypto";2const hash = (s: string) => createHash("md5").update(s).digest().readUInt32BE(0);3 4class HashRing {5  private ring: { point: number; node: string }[] = [];6 7  add(node: string, vnodes = 100) {8    for (let i = 0; i < vnodes; i++) this.ring.push({ point: hash(`${node}#${i}`), node });9    this.ring.sort((a, b) => a.point - b.point);10  }11 12  get(key: string) {13    const h = hash(key);14    return (this.ring.find((p) => p.point >= h) ?? this.ring[0]).node;15  }16}

1/3Turn any string into a number on the ring, from 0 to about 4.29 billion.

MD5 is fine here because we only need even spreading, not security. Real rings use binary search instead of find for speed.

Save yourself the pain

Common mistakes

Oops

Using hash(key) % serverCount for a cache cluster that will grow.

Do this instead

Changing the count remaps most keys, causing a flood of cache misses. Use a hash ring.

Oops

Placing each server at just one point on the ring.

Do this instead

Load can end up very uneven. Give each server many virtual nodes.

Your mission

Measure the reshuffle

~30 min

Quick check

With consistent hashing and 5 servers, you add a 6th. Roughly what share of keys move?

Go deeper

1Read a visual explanation of consistent hashing — the 'hash ring' concept.
2Compare it to naive modulo hashing and see why the latter causes massive remapping on a resize.
3Recognize this concept in tools you may already use, like memcached client libraries.