Design consistent hashing
Any system that spreads data across N machines must answer one question every request: which machine owns this key? The naive answer makes adding a machine a fleet-wide catastrophe. Consistent hashing is the data structure that turns "rebuild everything" into "move 1/N of it."
0. Interview hinge
The hinge is the moment the problem stops being generic and the design becomes forced. Here it is the question "why not just hash(key) % N?" — because the answer derives a near-total reshuffle on every membership change, and that single number forces the entire ring construction, virtual nodes, and consensus-backed membership that follow.
k, another thinks node C does — you get split-brain writes that no later reconciliation can untangle. The ring's topology (members + their token positions) must therefore live in a consensus-backed config store (lesson 10) and every routing decision must be tagged with the ring version it used.
1. Clarify the contract
Treat the prompt as a contract before drawing boxes. The mapping layer must:
- Map any key to an owning node with near-even load distribution.
- Move only ~1/N of keys when a node is added or removed — never the whole keyspace.
- Support heterogeneous nodes — a 2× larger machine should take ~2× the load.
- Return a replica set, not just one owner, so a single node failure does not lose the key.
- Resolve ownership fast — an O(log N) lookup at the client or a thin router tier, no central bottleneck.
And explicitly what it need not do: it is not a range index (you cannot scan "all keys between X and Y" — hashing destroys order, see the trade-off table), it does not store the data itself (it only decides where data lives), and it does not by itself guarantee replica durability or consistency — that is the replica layer's job (lesson 08).
2. Put numbers on the shape — the two load-bearing calculations
This whole topic lives or dies on two arithmetic facts. Memorise both; they are what an interviewer is listening for.
Calculation 1 — the remapping fraction
Modulo hashing. Owner is hash(key) mod N. With N = 4 nodes, key k lands on hash(k) mod 4. Add a 5th node and the divisor changes to 5: now the owner is hash(k) mod 5. A key stays put only if hash(k) mod 4 = hash(k) mod 5, which is rare. The fraction that keeps its owner is roughly N/(N{+}1) = 4/5 of remainders coinciding? No — work it out: as the modulus changes from 4 to 5, the residue almost always changes. Empirically the share of keys that keep their owner is about 1/(N{+}1) = 1/5 = 20%, so ~80% of all keys remap — a fleet-wide data shuffle just to add one machine.
Consistent hashing. Place nodes and keys on the same circular hash space. A key belongs to the first node found walking clockwise. Adding the (N+1)th node drops one new point on the ring; it steals only the arc between itself and the previous node — the keys in that one arc. With N evenly spread nodes each arc is about 1/(N{+}1) of the circle, so the new node captures 1/(N{+}1) = 1/5 = 20% of keys and every other key stays exactly where it was.
Calculation 2 — virtual nodes and load variance
The ring fixes remapping, but a fresh problem appears: with one point per physical node, the arcs are random and lumpy. Hashing N points onto a circle gives arc sizes that follow an exponential distribution; the coefficient of variation of per-node load is roughly ±40%, so one machine can hold 1.4× another's share — a built-in hot shard from nothing but bad luck. The fix is to explode each physical node into V virtual nodes (tokens), each hashed independently onto the ring. A node's load is now the sum of V independent arcs, and by the law of large numbers its relative std-dev shrinks as 1/√V. With V ≈ 200 vnodes per machine, std-dev ≈ 1/√200 ≈ 0.07 = 7% — balanced enough to forget about. Heterogeneous hardware falls out for free: give a 2× machine 2× the tokens and it takes 2× the load.
3. Define the surface area
Keep the API tiny. It expresses ownership and membership, nothing about how data is stored.
| API / operation | Why it exists |
|---|---|
owner(key) -> [node, replica2, replica3] | The core lookup: returns the primary plus the replica set walking clockwise (distinct failure domains). |
add_node(node, weight) | Inserts weight × V tokens; only the arcs those tokens claim are migrated. |
remove_node(node) | Removes its tokens; each orphaned arc falls to the next clockwise node. |
ring_version() -> epoch | Monotonic membership epoch from the config store, so stale routing is detectable. |
4. Model the data
The data model is the architecture. Two structures matter: the token ring (a sorted map from hash position → vnode → physical node) used for O(log N) lookups, and the membership record (physical node registry, weights, health, ring epoch) which must be strongly consistent.
5. Linearized design — follow a key onto the ring
- 1. Hash the key with a good uniform hash (e.g. a 64-bit hash) onto a large circular space [0, 2⁶⁴).
- 2. Hash each physical node into V ≈ 200 virtual positions (more for bigger nodes), and keep them in a sorted structure.
- 3. The owner is the first vnode clockwise from the key's hash — a binary search in the sorted token map, O(log(N·V)).
- 4. For replication factor RF, keep walking clockwise and collect the next RF−1 vnodes that map to distinct physical nodes in distinct failure domains (skip same-node and same-rack vnodes).
- 5. Store the ring topology in a consensus-backed config store (lesson 10) and cache it in every client/router; clients refresh on epoch change.
- 6. On a membership change, compute exactly which arcs changed owner and stream only those ranges; flip ownership only after data is copied and checksummed.
6. Deep dives
Why hash(key) % N is a catastrophe (the sharpest senior question)
This is the question that decides the interview, so derive it cleanly. Under hash(key) mod N the divisor is the cluster size. Change the cluster size and you change the divisor for every key simultaneously. Go from 4 nodes to 5 and a key that hashed to remainder 3 (owner node 3) is now hash(k) mod 5 — almost certainly a different remainder, hence a different node. Only the keys whose value happens to satisfy x mod 4 = x mod 5 stay put, which is about 1/(N{+}1) ≈ 20%; the other ~80% migrate. For a 4 TB cluster that is ~3.2 TB of cross-network copying triggered by adding a single box — during which cache hit rates collapse, the network saturates, and tail latency spikes. The ring's whole reason to exist is that its mapping is local: a new node disturbs only its immediate arc, so the blast radius is 1/(N{+}1), not N/(N{+}1).
Replication must target failure domains, not adjacent vnodes
The clockwise replica walk has a trap. "Next RF vnodes clockwise" can land on vnodes that all map to the same rack, the same power domain, or the same availability zone — because vnode placement is independent of physical topology. Then the ring's load chart looks perfectly balanced while your availability is a lie: one rack power-trips and all RF replicas of a range vanish together. The fix is to make the replica walk topology-aware: skip not just same-physical-node vnodes but vnodes in failure domains already chosen, so the RF replicas are guaranteed to span distinct racks/AZs. This is why Cassandra has NetworkTopologyStrategy and Dynamo-style systems track "preference lists." Balanced key-count is necessary but not sufficient; balanced survivability is the real goal (lesson 08's quorum durability assumes replicas fail independently).
The alternative: rendezvous (HRW) hashing
Consistent hashing is not the only scheme with low remapping. Rendezvous (Highest Random Weight) hashing computes hash(key, node) for every node and picks the node with the highest score; the top-RF scores give the replica set directly. It also moves only ~1/N of keys on a membership change and needs no vnode bookkeeping or ring structure to stay balanced. Its cost is O(N) per lookup (you score every node) versus the ring's O(log N), so HRW wins for small N or where you want effortless balance and a clean replica list, while the ring wins for large clusters where the log-time lookup matters. Naming HRW as the alternative — and knowing the O(N) vs O(log N) trade — is a strong senior signal.
7. Trade-offs
| Choice | Buys | Costs | Choose when |
|---|---|---|---|
| Client-side routing vs router tier | one less network hop; no router fleet | every client must cache & refresh ring metadata on epoch change | large internal fleets with controlled, trusted clients |
| More virtual nodes vs fewer | smoother balance (std-dev ↓ as 1/√V) | larger token map, more migration bookkeeping per change | heterogeneous clusters needing tight balance |
| Hash partitioning vs range partitioning | uniform load, no hot range | destroys key order — no efficient range scans | caches and point-lookup key-value access |
| Immediate ownership flip vs staged migration | fast, simple membership change | risk of serving from a node that hasn't received the data | stateless cache clusters where a miss is cheap |
| Consistent-hash ring vs rendezvous (HRW) | O(log N) lookup at large N | needs vnode tuning to stay balanced | large clusters; use HRW when N is small or you want a free replica list |
The sharpest trade is the last-but-one: immediate flip vs staged migration. For a stateless cache, flipping ownership the instant a node joins is fine — the new owner simply misses, fetches from origin, and warms up; the only cost is a brief dip in hit rate (lesson 06). For a stateful store the same flip is a correctness bug: if the new node accepts reads before its arc's data has been copied and checksummed, it serves "key not found" for live data. There the ring epoch must advance in two phases — "node is joining, still forward to old owner" then "data verified, now serve" — which is exactly why membership belongs in a consensus store that can carry that staged state.
8. Failure modes
| Failure | Mitigation |
|---|---|
| Ring split-brain | Single source of truth for membership in a consensus-backed config store (lesson 10); version every routing decision with the ring epoch and reject stale writes. |
| Hot key (one key, huge traffic) | vnodes balance key counts, not per-key heat. Replicate the hot key to extra nodes, coalesce duplicate reads (lesson 06), or split the logical key. |
| Fake availability (replicas share a failure domain) | Topology-aware replica walk so RF replicas span distinct racks/AZs, not just adjacent vnodes. |
| Rebalance overload | Throttle range copy, prioritise live serving traffic, and flip ownership only after checksum verification. |
| Uneven hardware | Weighted tokens (more vnodes for bigger machines) and observe actual load, not just key counts. |
9. Interview Q&A
- Why not just
hash(key) % N? (senior answer) Because the cluster size is the divisor, so changing N changes the owner of nearly every key at once — adding the 5th node to 4 remaps ~80% of keys (only ~1/(N+1) coincide), a fleet-wide data shuffle just to add a box. The ring makes the mapping local: a new node disturbs only its own arc, so the blast radius is 1/(N+1) ≈ 20%. - Where does the 1/(N+1) come from? (senior answer) A new node drops one point on the circle and steals only the arc between itself and the previous node clockwise. With N points roughly evenly spaced, each arc is ~1/(N+1) of the circle, so it captures ~1/(N+1) of keys and leaves everything else untouched.
- Why do you need virtual nodes? (senior answer) One point per node gives exponential, lumpy arc sizes — per-node load varies ±~40%, an instant hot shard. Splitting each node into V≈200 tokens averages V independent arcs, shrinking std-dev to ~1/√V ≈ 7%. As a bonus, weighting tokens handles heterogeneous hardware directly.
- How do you choose replicas, and what's the trap? (senior answer) Walk clockwise and take the next RF vnodes that map to distinct physical nodes — but they must also be in distinct failure domains. Naive adjacency can put all RF replicas in one rack, so the ring looks balanced while a single power trip loses the whole range. Make the walk topology-aware.
- What's the alternative to a ring? (senior answer) Rendezvous/HRW hashing: score hash(key,node) for every node and pick the top RF. Same ~1/N remapping, no vnode tuning, gives a clean replica list — but O(N) per lookup vs the ring's O(log N). Use HRW for small N, the ring for large clusters.
- Where does the ring topology live, and why does it matter? (senior answer) In a consensus-backed config store (lesson 10), versioned by epoch. If two routers disagree on membership you get split-brain writes no reconciliation can fix, so every routing decision carries the epoch it used and stale ones are rejected.
- Can you do range scans on a consistent-hash store? (senior answer) No — hashing deliberately destroys key order to spread load, so adjacent keys land on random nodes. If you need range scans you want range partitioning (DDIA Ch. 6) and accept its hot-range risk; the two goals trade off directly.
- How do you add a node safely to a stateful store? (senior answer) Two-phase: advance the epoch to "joining — still forward to old owner," stream and checksum the moved arcs, then advance to "verified — serve." Throttle the copy so it doesn't starve live traffic. An immediate flip is only safe for stateless caches where a miss just re-fetches.
Related foundation lessons & forward link
This case is the anchor for ring mechanics — later cases link here rather than re-derive. It rests on lesson 07 (partitioning) — consistent hashing is the canonical hash-partitioning scheme, and DDIA Ch. 6's "partition by hash of key," the badness of mod-N rebalancing, and fixed-partition-count rebalancing are the textbook grounding. The replica walk depends on lesson 08 (replication) for quorum durability across distinct failure domains. Membership in a consensus store is lesson 10 (consensus / coordination), which is DDIA Ch. 9 territory — the ring epoch is a consistency boundary. Hot keys and warm-up dips lean on lesson 06 (caching). Forward: C03 (key-value store) is where this ring gets used — it links back here for the mechanics and builds the storage, replication, and consistency layers on top.