How it works
Start with the problem: hash(key) % N spreads keys across N servers, but changing N remaps most keys. Consistent hashing instead places both keys and server positions in a shared hash space, usually drawn as a ring.
To find a key's owner, hash the key and walk clockwise to the first server position, wrapping around if needed. On a toy ring numbered 0–99, suppose servers A, B, and C sit at 10, 40, and 80. A key hashed to 25 belongs to B; a key hashed to 90 wraps around to A.
Adding server D at position 30 transfers ownership of keys in the interval (10, 30] from B to D. Other primary assignments stay unchanged. Removing D gives that interval back to B; the ring identifies the new owner, but it does not copy data or recover lost values.
One position per server can produce uneven ownership. Virtual nodes give each physical server many positions, such as hashes of server-A:1 and server-A:2, so its ownership is spread across the ring. More positions generally improve balance, and assigning more positions to larger servers can reflect capacity.
Clients or routing proxies use a shared membership configuration to compute ownership. During changes, they need a transition plan for stale routing and data transfer. If replication is required, the placement policy can continue clockwise to distinct physical servers, while also respecting rack or zone boundaries.
A worked example
Growing a distributed cache from 10 to 11 servers
Suppose a cache holds 100 million keys across 10 equal-capacity servers, each represented by many virtual nodes. Adding an eleventh server changes roughly 1/11 of primary assignments (about 9.1 million keys), assuming balanced placement and ignoring replicas. Most keys keep their existing owner. Routers receive a versioned membership update, and the new server begins receiving requests for its ranges. If those ranges start empty, misses can still create a large database spike. Limit refill concurrency, coalesce requests for the same missing key, and consider warming the new owner before cutover. The ring reduces the scope of disruption; it does not make expansion free.
Trade-offs to say out loud
- Less remapping, not zero migration
- With balanced equal-capacity servers, adding one server to N existing servers moves roughly 1/(N+1) of primary key assignments, but replica changes can add more work.
- Virtual nodes cost metadata
- More virtual nodes improve statistical balance but enlarge routing metadata and increase the number of ranges involved in transfers.
- Balanced keys do not mean balanced traffic
- A single popular key still has one primary owner, so hot keys need separate measures such as read replication or local caching.
- Membership changes need coordination
- Routers with different membership versions can disagree about ownership, requiring redirects, forwarding, retries, or an explicit handoff protocol.
- Placement is not durability or consistency
- Replication, write acknowledgments, failure detection, and conflict handling remain separate design decisions.
- A ring is not always the simplest choice
- A fixed set of logical partitions with an explicit ownership map can offer more direct control over placement and rebalancing.
When to reach for it
- You are designing a distributed cache whose server count changes, and widespread remapping would overwhelm the backing database.
- A key-value store must grow or replace failed nodes without redistributing most of its dataset.
- Requests need stable key-based routing to state owners rather than arbitrary distribution across stateless servers.
- A partitioned worker system needs stable ownership of keyed work, such as host-specific crawler queues, as workers join and leave.
How to bring it up in the interview
- State the motivation before drawing the ring: minimize ownership changes during scaling or failures, not merely spread requests evenly.
- Walk through one key lookup and one server addition, then explain virtual nodes and distinguish physical servers from ring positions.
- Name the routing authority: explain who publishes membership, how routers learn a new version, and what happens when a request reaches the old owner.
- Separate cache and durable-store handoffs: a cache may tolerate misses with controlled refill, while durable storage needs data transfer and concurrent-write handling before cutover.
- Expect probes about hot keys, unequal server capacity, replica placement, and node flapping; explain which problems the ring solves and which require separate mechanisms.
Common mistakes
- Claiming that adding a server moves no keys, or that consistent hashing eliminates rebalancing.
- Drawing one position per server and assuming ownership or request load will be evenly distributed.
- Treating adjacent virtual nodes as independent replicas even when they belong to the same physical server.
- Assuming that updating the ring automatically transfers data, preserves writes, or prevents stale routing.
- Using consistent hashing to solve a hot key, or confusing the word 'consistent' with strong consistency.
Where it comes up
Interview questions where consistent hashing is part of a strong answer, and why.
- Design a distributed cacheConsistent hashing directly addresses cache ownership and routing during membership changes while limiting miss amplification.
- Design a distributed key-value storeIt provides a concrete placement scheme for explaining ownership changes, replica selection, and data handoff as storage nodes join or leave.
- Design a web crawlerHashing by hostname can assign host-specific frontier queues to stable owners, keeping politeness enforcement together while limiting reassignment during worker changes.
Questions people ask
What is a consistent hashing ring?
It is a circular representation of a hash space containing key hashes and server positions. A key belongs to the first server position clockwise from its hash, wrapping around at the end. Adding or removing a position changes ownership only for the affected interval.
Why does consistent hashing use virtual nodes?
Randomly placing just one position per physical server can leave some servers owning much larger ranges than others. Virtual nodes spread each server across many positions, improving balance and spreading transfers among more peers. They do not split the load of a single hot key.
How is consistent hashing different from sharding?
Sharding is the broader practice of splitting data across storage nodes. Consistent hashing is one way to decide which node owns a key and limit reassignment when membership changes. Range partitioning and fixed logical partitions with an ownership map are other options.