Consistent Hashing: A System Design Guide

If you remember five things

The whole concept in one glance. Everything below defends these five points.

Modulo is the villain. `hash(key) % N` moves about `1 - 1/N` of all keys when N changes, so going 4 to 5 nodes relocates roughly 80% and cold-starts your cache.
The ring caps the blast radius. Add or remove one node and only about `1/N` of keys move, and they move to or from a single neighbor, not scattered everywhere.
Virtual nodes buy even load. One point per server gives wildly uneven arcs. Place each server at ~100 to 256 points and the variance drops to a few percent.
Minimal movement is not zero. Moving `1/N` of a 10 TB store is still ~900 GB of live I/O, so you throttle the backfill or you hurt latency.
Placement, not popularity. The ring balances keys, not traffic. One scorching hot key still cooks its node. You fix that with replication or key splitting, separately.

1The core idea#

Start with the pain it solves, because that is what an interviewer actually wants to hear you reason about.

The naive scheme and why it detonates.

You have a cache fleet of 4 servers and shard with the obvious rule: server = hash(key) % 4. Works great.
Traffic grows, you add a 5th server, the rule becomes hash(key) % 5.
Almost every key now maps to a different server than before. Roughly 1 - 1/N of keys relocate when you change N.
Going from 4 to 5 servers moves about 80% of keys. In a cache that is a near-total miss storm. In a sharded database it is moving almost all your rows.

Put real numbers on it so the stakes are concrete.

Say the cache holds 100 million keys, serving 50,000 reads/second at a 95% hit rate, so the database behind it sees about 2,500 reads/second.
You add one server. With modulo, roughly 80 million of the 100 million keys now map to a different box, so 80% of reads miss.
The database read rate jumps from 2,500/second to around 40,000/second in the seconds after the resize.
Most databases fall over at that spike. That single % 4 to % 5 change is a self-inflicted outage.

What consistent hashing changes.

Add or remove one node from a cluster of N and only about 1/N of keys move, to or from a single neighbor.
Add a 5th server to 4 and roughly 20% of keys shift, not 80%.
Run the same math: about 20 million keys move, so the miss rate is around 20% for a brief window, pushing the database to roughly 10,000 reads/second instead of 40,000.
Still a bump, but survivable, and it decays as the cache refills.

40k vs 10k

Reads/second at the database after a resizeModulo spikes you to ~40,000 and takes the DB down. The ring holds you near ~10,000 and you survive. That gap is the entire reason this technique exists.

The mental model: a ring.

Imagine a circle numbered from 0 up to some huge number, say 2^32, that wraps back to 0 at the top.
Hash each server's ID and drop it onto a point on the ring. Hash each key and drop it onto a point too.
A key belongs to the first server you hit when you walk clockwise from the key's position.
Because servers and keys live in the same coordinate space, removing a server only orphans the keys in that one arc, picked up by the next server clockwise. Everyone else stays put.

The point of this section

Nobody is grading you on the circle picture. They are grading whether you can name the failure of modulo in numbers: 1 - 1/N keys move, the cache cold-starts, the DB spikes from thousands to tens of thousands of reads per second. Say that first, then draw the ring.

2How it works#

Walk the lookup out loud. A key hashes to some position. You move clockwise around the ring until you hit a server. That server owns the key.

flowchart LR A[Key] --> B[Hash to ring position] B --> C[Walk clockwise] C --> D[First node found] D --> E[(Cache node)]

The lookup in four steps. The only operation is "hash, then walk clockwise to the first node." Notice there is no central directory being consulted: placement is pure math over the key and the ring positions.

A toy ring makes the arithmetic readable. Use a 0 to 1000 space with three servers.

Servers hash to A at 100, B at 450, C at 800.
A key at 300 walks clockwise and hits B at 450, so B owns it.
A key at 820 walks clockwise past 1000, wraps to 0, and hits A at 100, so A owns it.
Add server D at 600. The only keys that change ownership are those in the arc from 450 to 600, which used to belong to C and now belong to D.
Keys owned by A and B do not move at all. That is the 1/N property in action: one new node, one disturbed arc, one neighbor affected.

Now the part that trips people up: naive placement is lumpy.

Put each physical server at exactly one point and the arcs between servers are wildly uneven.
With a handful of random points on a circle, some servers own a huge slice and others own a sliver. One box gets 40% of traffic, another gets 5%.
In the toy ring, A owns the arc from 800 wrapping to 100 (300 units wide) while the arc from 100 to 450 is 350 units.
Those gaps are random, and with only a few nodes they do not average out. That is a hot-spot problem baked into the design.

Pause before you read on: with single points per server, a node dies. Where does its load go, and why is that dangerous?

Reveal the answer

All of the dead node's keys land on the single node clockwise of it, which can instantly double that one survivor's load while the rest of the fleet sits idle. A cascading failure often starts right here: the overloaded successor dies too, and its load dumps onto the next node. Virtual nodes are the fix, and reaching for them unprompted is what earns the room.

The fix is virtual nodes (vnodes).

Instead of placing server A once, place it 150 or 200 times, using hashes like hash("A-0"), hash("A-1"), and so on.
Each physical server now owns many small arcs spread around the ring, so the law of large numbers evens out load.
With one point per server across 10 nodes, the busiest node can easily own 2x to 3x the share of the quietest.
With around 100 to 200 vnodes per server, load variance drops to a few percent, which is fine for production.

Vnodes buy you two more things for free.

Spread on failure. When a server dies, its many arcs get absorbed by many different neighbors. With 150 vnodes, B's share splits across roughly 150 successor arcs, so each survivor in a 10-node fleet picks up about one-ninth of B's former load instead of one box taking all of it.
Weighting. A machine with twice the RAM simply gets twice as many vnodes. Heterogeneous hardware handled with no extra machinery.

Here is what happens over time when a node joins:

sequenceDiagram participant C as Client participant R as Ring router participant N as New node participant O as Old owner C->>R: Write key R->>R: Compute ring position R->>N: Key now lands on new node N->>O: Pull affected key range O-->>N: Transfer keys N-->>C: Ack write

A node joining. The new node takes over one arc and pulls only that key range from the single old owner. The data transfer is bounded to that arc, which is the 1/N cost made physical.

Lookups are cheap and do not grow with key count.

To find the owning server for a position, binary-search the sorted list of vnode positions, so a lookup is O(log V) where V is the total number of vnodes.
With 10 nodes at 150 vnodes each, V is 1,500 and a lookup is about 11 comparisons.
Cheap, and it scales with fleet size, not with the number of keys.

3Trade-offs#

The honest trade-offs are where interviews are won. Consistent hashing is not free, and it is not always the right call.

Decision	Consistent hashing	Modulo / rehash	Range partitioning
Keys moved when fleet changes	~1/N	~all of them	depends on split points
Load distribution	even with vnodes, lumpy without	even until you resize	can skew badly on hot ranges
Range scans	poor, keys scattered	poor	excellent, keys adjacent
Rebalancing control	automatic, data-driven	manual full reshuffle	manual, you pick splits
Metadata overhead	ring with V entries	trivial	split table
Implementation complexity	moderate to high	trivial	moderate

A few things to call out explicitly, because each is a follow-up waiting to happen.

You lose locality.

Keys are hashed, so two keys that sit next to each other logically (user 1001 and user 1002) land in random spots on the ring.
If your workload does range queries ("give me all orders from March"), consistent hashing is the wrong tool.
That is exactly why systems that need range scans use range partitioning instead, and accept manual rebalancing as the cost.

Minimal movement is not zero movement.

Moving 1/N of the data is still a real transfer that competes with live traffic.
Take a 10-node store holding 1 TB per node. Adding one node means moving about 1/11 of 10 TB, roughly 900 GB, onto the new box.
Add a node during peak load and that backfill can saturate disk or network and hurt latency for live requests.
Good systems throttle it, capping the backfill at, say, 50 MB per second so it stretches over hours instead of crushing the fleet in minutes.

Even distribution needs enough vnodes, and vnodes cost memory and lookup time.

Set them too low and you get hot spots.
Set them absurdly high and the ring metadata and gossip chatter grow.
The usual range is 100 to 256 per node.

Plain consistent hashing can still create hot shards from hot keys.

The ring balances keys evenly, but if one key (a celebrity user's timeline) gets 100x the traffic of others, the node owning it burns.
Consistent hashing solves placement, not popularity skew.
You handle that separately, with replication or key splitting.

From the interviewer's chair

When I hear "only 1/N of the data moves, so it's fine," I lean in and ask how much that actually is. The candidates who impress me have already done the 900 GB arithmetic and bring up throttling before I can. Saying "minimal movement" without a number tells me you have read about this but never run it.

There is also a known refinement called bounded-load consistent hashing.

A node can refuse to be the owner if it is already over a load cap, spilling the key to the next node clockwise.
It caps the worst case at the cost of a bit more bookkeeping.
Worth naming if the interviewer pushes on tail-latency guarantees.

4Where it is used#

This pattern is everywhere once you know to look for it.

Distributed caches. The original motivation. Memcached client libraries have used ring hashing for years so that losing one cache box does not cold-start the entire tier.
Dynamo-style databases. Systems in the Dynamo lineage place data on a ring and replicate each key to the next few nodes clockwise. This is the canonical example and the one most interviewers have in mind.
Wide-column and partition-tolerant stores. Several well-known NoSQL stores assign token ranges to nodes with vnodes, which is consistent hashing by another name.
CDN and edge request routing. Mapping a request to the edge cache most likely to already hold the object, so a server coming online does not invalidate the whole edge tier.
Shard routers and connection poolers that spread keys across backends while surviving backend churn.

When would I reach for it?

Any time I have a fleet that scales up and down, keys with no need for range scans, and I care about not blowing up the whole cache or moving all the data on every membership change.
If the fleet is fixed size forever and never fails, plain modulo is simpler and I would use that.
Do not add machinery you do not need.

Reason from the problem (fleet churn, cache misses, data movement) to the ring. Memorizing the ring and reasoning backward is what interviewers catch.

5Common pitfalls and gotchas#

The failure modes, each one a place a sharp interviewer will poke.

Forgetting virtual nodes. The number one interview miss. Draw the ring with one point per server and say "done," and the next question is about load skew. Mention vnodes before they ask.
Assuming it gives you replication or consistency. Consistent hashing is a placement function. It tells you where a key lives. It says nothing about how many copies exist, how writes are made durable, or how conflicts resolve. Those are separate decisions (replication factor, quorums, conflict resolution).
Picking a weak hash function. You want uniform spread across the ring. A hash with poor distribution (or something like the Java default object hash) clusters vnodes and reintroduces skew. Use a solid non-cryptographic hash such as a well-tested 64 or 128 bit mixer.
Unthrottled rebalancing. Moving 1/N of the data on a membership change can crush a node if you let the backfill run flat out. Rate-limit it.
Ring metadata consistency. Every node and client needs a consistent-enough view of the ring. If two clients disagree about where a vnode sits, they route the same key to different servers. Real systems distribute ring state via gossip or a coordination service, and you should know where that state lives in your design.
Hot keys. Worth repeating: the ring does not save you from a single scorching key. Plan for replication of hot keys or splitting them.

Red flag that fails you here

Treating consistent hashing as a magic word. If you say the term, draw the circle, and stop, I know you memorized it. I can tell in one follow-up whether you understand the ring or just know its name. The candidates who pass volunteer the limits (no range scans, no hot-key relief) before I ask.

6How it shows up in interviews#

The classic prompts.

"Design a distributed cache."
"How do you shard this database so it scales?"
The moment scaling or node failure enters the conversation, consistent hashing is the expected answer.

What interviewers probe, weak answer versus strong answer.

Do you know why modulo fails? Weak: "I'll use consistent hashing because it's better." Strong: "Modulo moves 1 - 1/N of keys on resize, about 80% going 4 to 5 nodes, which cold-starts the cache and spikes the database from a few thousand reads per second to tens of thousands. Consistent hashing drops that to 1/N, around 20%."
Can you explain vnodes without prompting? Weak: silence until asked about skew. Strong: "One point per server gives uneven arcs and hot spots, where the busiest node can own 2x to 3x the quietest, so I place each server at about 150 virtual points to even out load and to spread a dead node's load across many survivors instead of one."
Do you understand the data-movement cost? Weak: "Only 1/N of the data moves, so it's fine." Strong: "Even 1/N is real I/O. On a 10-node, 1 TB-per-node store, adding a node moves roughly 900 GB, so I throttle the backfill to protect live latency, and I keep ring state in gossip or a coordination service so clients agree on placement."
Do you know its limits? Weak: treats the ring as a cure-all. Strong: volunteers that it kills range scans and does not fix hot keys, and says what to use instead: range partitioning for scans, replication or key splitting for hot keys.

How to show depth in one breath.

Sketch the lookup as O(log V) binary search over sorted vnode tokens.
Give a vnode count with a reason (100 to 256, balancing even load against metadata).
Mention bounded-load as a refinement for tail latency.
That combination of mechanics, numbers, and trade-offs separates an advanced answer from a memorized one.

Follow-ups the interviewer will ask (and your answers)

"Exactly how many keys move when I add the Nth node, and where do they go?"

About `1/N` of the keys, and they come from a single neighbor, not the whole fleet. The new node's vnodes slot into the ring and pull only the arcs they now own from the previous owners of those arcs. Everyone else's assignments are untouched. With modulo it would be roughly `1 - 1/N`, scattered across every node.

"Why virtual nodes? Isn't one point per server simpler?"

Simpler and badly skewed. With a few random points, arc sizes vary wildly, so the busiest node can own 2x to 3x the quietest, and a dead node dumps its entire load onto one unlucky successor. Placing each server at ~150 points evens load to a few percent and spreads a failure across many survivors. Vnodes also give free weighting: bigger box, more vnodes.

"Adding a node only moves 1/N of the data. So it's basically free, right?"

No. On a 10-node store with 1 TB per node, 1/N is about 900 GB moving onto the new box, and that transfer competes with live traffic. Run it flat out during peak and you saturate disk or network and spike latency. I throttle the backfill, say 50 MB per second, so it stretches over hours instead of crushing the fleet.

"A single celebrity key is getting hammered. Does the ring save me?"

No. The ring balances key placement, not traffic to a key. One key at 100x the load still cooks its owning node no matter how evenly the ring is spread. That is a popularity problem, handled separately: replicate the hot key across several nodes and read from any, or split it into sub-keys. Bounded-load consistent hashing also helps by capping per-node load.

"How do all the clients agree on where a vnode lives?"

They share ring state through gossip or a coordination service. If two clients disagree about a vnode position, they route the same key to different servers, which breaks the cache and corrupts reads. So the ring membership and token assignments are distributed with a consistent-enough protocol, and I would name where that state lives in the design rather than hand-waving it.

What you can now explain in the room

Why `hash(key) % N` moves about `1 - 1/N` of keys on resize and cold-starts a cache, with the DB read spike in real numbers.
How the ring caps key movement to `1/N` and confines it to a single neighbor.
Why one point per server is lumpy, and how 100 to 256 vnodes even out load and spread failures.
Why minimal movement still costs real I/O, and how throttling the backfill protects live latency.
Why the ring solves placement but not hot keys, and what you reach for instead (replication, key splitting, bounded-load).
Where ring state lives, why clients must agree on it, and when plain modulo or range partitioning is the better call.

For a full walkthrough, see the System Design Question "Design a Distributed Cache" where consistent hashing is the backbone of the sharding layer.

← Previous

ACID vs BASE

Database Indexing: B-Trees and LSM Trees

Get a prep plan built around your Consistent Hashing interview

Tell us the role and your interview date. We will send back a dated, day by day plan. Free.

Thanks. Check your inbox, your Consistent Hashing prep plan is on the way.