Consistent Hashing

Build the hash ring as code: a sorted list of points, a binary search, virtual nodes for balance, and replication for failure. Know what moves when a node joins and why.

Overview

Consistent hashing answers one question: which node owns this key, in a way that barely changes when nodes come and go. The name comes from a 1997 paper by Karger, Lehman, Leighton, Levine, Lewin and Panigrahy, written to spread web cache load. Today it decides where a key lives in Dynamo-style stores, Cassandra, and most distributed caches.

The low-level interview is not about the idea; it is about the code. You are expected to build the ring from a sorted list and a binary search, explain why a node needs many points on the ring, show what happens when a node dies, and know the two main alternatives. This topic walks through each of those with a tiny ring you can trace by hand.

Why modulo fails

The obvious way to pick a node is hash(key) % n. It spreads keys evenly, but the moment n changes almost every key changes owner, because the remainder of nearly every hash changes. The table uses five keys with small hash values so you can check it.

k1 — 7 — 1 — 3 — yes
k2 — 30 — 0 — 2 — yes
k3 — 50 — 2 — 2 — no
k4 — 83 — 2 — 3 — yes
k5 — 99 — 0 — 3 — yes

Four of five keys move when a fourth node joins. In a cache that is a stampede of misses; in a database it is a mass migration.

The ring

Consistent hashing hashes both keys and nodes into the same range, drawn as a circle. A key belongs to the first node at or after its position, wrapping around at the end. The only data structure you need is a sorted list of node positions and a map from position to node.

A trace on a ring of size 100 with nodes A at 12, B at 45 and C at 78 shows the rule and the wrap. Then node D joins at 60.

k1 — 7 — A (first point at or after 7) — A — no
k2 — 30 — B — B — no
k3 — 50 — C — D (60 is now first after 50) — yes
k4 — 83 — A (wrap: nothing after 83) — A — no
k5 — 99 — A (wrap) — A — no

Only k3 moves, and it moves to the new node. That is the whole guarantee: a node that joins takes keys only from its clockwise neighbor, and a node that leaves gives its keys only to that neighbor. With K keys and N nodes, about K/N keys move.

The ring in Python

The implementation is a sorted list of positions plus bisect. Each node is placed on the ring vnodes times under different labels, which the next section explains. Lookup is O(log P) for P points on the ring.

The asserts are the interview answer in code form: every key that moved went to D, about a quarter of the keys moved (one of four nodes), and removing D restores the old ownership exactly.

> [!TIP] > hashlib.md5 is used here because it is stable across runs and machines. Python's built-in hash() of a string changes between processes (hash randomization), so a ring built on it would disagree with itself after a restart.

Why a node needs many points

With one point per node, the ring is split into a few arcs of random length, and the largest arc can be many times the smallest. The Dynamo paper names this problem (non-uniform load, and no way to give a bigger machine more keys) and solves it with virtual nodes: each physical node is placed on the ring many times. Cassandra does the same and calls the positions tokens.

The numbers below come from running the ring above with five nodes and 100,000 keys, changing only vnodes.

1 — 1.3% — 40.2%
10 — 9.6% — 32.7%
100 — 17.7% — 22.5%
1,000 — 19.4% — 21.1%

An even split would be 20% each. More points cost memory and a slightly slower search, and make a node join or leave touch many small arcs instead of one big one, which spreads the migration load across every other node. A bigger machine simply gets more points.

Replication and failure

One owner per key means one failure loses the key. Dynamo's rule is to store each key on the owner and the next N-1 distinct physical nodes clockwise, called the preference list; N=3 is the setting the paper describes. Virtual nodes make 'distinct physical nodes' matter: the next point on the ring may belong to the same machine, so the walk skips it.

Node joins — Its clockwise neighbor(s) — Hands over the arcs the new node now owns; nothing else moves
Node leaves cleanly — Its clockwise neighbor(s) — Absorb its arcs; with N replicas the data is already there
Node crashes — Its arcs' next replica — Reads and writes fall through to the remaining replicas; Dynamo stores hinted writes on a stand-in node and replays them when the node returns

Two alternatives

The ring is not the only consistent scheme. Rendezvous hashing (also called highest random weight) scores every node for a key and picks the highest score; jump consistent hash, from a 2014 paper by Lamping and Veach, computes a bucket number in a few lines with no state at all.

State — Sorted points, O(nodes × vnodes) — The node list only — None
Lookup — O(log points) — O(nodes) — O(log buckets), about 5 lines
Node removal — Any node, anytime — Any node, anytime — Only the last bucket; buckets are numbered 0 to n-1
Weighted nodes — More points — Scale the score — Not directly
Fits — Caches and stores with arbitrary membership — Few nodes, no memory to spare — Sharded storage where shards are numbered

What you will be able to do

Implement a hash ring with a sorted list and a binary search, and explain the wrap-around case.
Say what moves when a node joins or leaves, and prove it with a count.
Explain why one point per node is unbalanced and how many points fix it, with numbers.
Describe replication along the ring and what a crash does to reads and writes.
Choose between a ring, rendezvous hashing and jump hash from their trade-offs.

Interview questions

Implement consistent hashing. How do virtual nodes help?
What happens when a node fails in a consistent hashing ring?
Compare the ring to rendezvous hashing and jump consistent hash.
How would you make the ring safe to use from many threads, and how do clients agree on it?
How do you support nodes of different capacity?