Consistent hashing: why hash % N breaks and how to fix it

Key points

hash(key) % N bakes the server count into every lookup, so one server change remaps nearly all keys and storms the cache.
The ring maps servers and keys into one hash space; each key belongs to the first server clockwise from its position.
Virtual nodes give each server many small slices, cutting load spread to 5-10% at 100-200 replicas per server.

Outcomes

01Explain why hash(key) % N causes a cache miss storm when servers change.

02Trace key lookup on the hash ring: hash, land, walk clockwise to the first server.

03Use virtual nodes to even out partitions, and tune their count against memory cost.

Why hash % N breaks

With N fixed servers, serverIndex = hash(key) % N spreads keys evenly. But N sits inside the formula, so adding or removing one server changes the modulus for nearly every key. In the book's 8-key example, dropping from 4 servers to 3 redistributes most keys, and clients storm the wrong servers with misses.

hash % N, one server lost

~7 of 8 keys move

Consistent hashing, one server added

1 of 4 keys moves

Book's worked examples: 8 keys under hash % 3 vs 4 keys when a server joins the ring.

Interview tipInterviewers ask this to test whether you feel the pain before reaching for the solution. Name the storm: mass remapping, then cache misses, then database overload.

The hash ring

How to read: Follow arrows left to right: each box feeds the next until a server owns the key.

flowchart LR K["Key k0"] --> H["Position h = hash(k0)"] H --> R["Land on hash ring"] R --> S["Walk clockwise to first server"] S --> S0["Stored on server 0"]

Static structure of a lookup: hash the key, land on the ring, scan clockwise.

How to read: Watch the dots: the key lands on the ring, then a second dot walks clockwise to the first server.

Hash key0 into the SHA-1 space, positions 0 to 2^160 - 1.
Land on the ring between the existing servers.
Walk clockwise: the first server met owns the key.

One lookup travelling the ring: key0 hashes on, then walks clockwise to server 0.

Interview tipAdding server 4 only steals key0, the one key it precedes clockwise. Removing server 1 only remaps key1 to server 2. Everything else stays.

Virtual nodes even the load

Basic rings suffer two skews: partitions between adjacent servers differ wildly in size, and unlucky server placement strands keys on one machine. Virtual nodes fix both by giving each server many positions, so every server owns many small slices instead of one big arc.

100 virtual nodes

10% of mean

200 virtual nodes

5% of mean

Measured spread of load as replica count grows; more replicas cost more ring metadata.

GotchaMore virtual nodes always balance better but cost memory for ring state. Production systems tune the count: enough replicas for even load, few enough to store cheaply.

Q&A

Check yourself

Q1A cache server goes offline under hash(key) % N. What happens?

Most keys remap and clients hit the wrong servers
Only the removed server's keys move
Keys stay put until their TTL expires

✓ Most keys remap and clients hit the wrong servers — The modulus changes for nearly every key, so clients ask the wrong servers.

Q2On a consistent hash ring, which server stores a key?

The server with the fewest keys
The first server encountered going clockwise
A random server, then cache the answer

✓ The first server encountered going clockwise — Clockwise order on the ring is the whole lookup rule.

Q3What do virtual nodes fix?

They replace the hash function entirely
They remove the need for replication
They split each server into many ring positions for even load

✓ They split each server into many ring positions for even load — More replicas per server shrink the standard deviation of load.

Sources: System Design Interview Vol 1: Ch. 5, Consistent hashing (pp. 71-86)