System Design AI

Consistent Hashing in System Design Interviews: When to Use It and What to Say

Consistent hashing is a technique that maps keys to a circular hash space so that when a node joins or leaves, only a tiny slice of keys need to be moved. In an interview you can say it "spreads data across a dynamic set of servers while minimizing reshuffling when the cluster changes".

The Problem It Solves

Imagine a large key-value cache (e.g., a Redis cluster) that stores user session data. If you assign keys by simple modulo (key % N), adding a new cache node forces you to recompute the modulo for every key. With a million keys, that’s a massive data migration. The same issue appears in sharded databases and content-delivery networks that spread cached objects across the servers in an edge location. Consistent hashing solves two problems:

  1. Uneven load – keys may cluster on a few nodes if the hash function isn’t uniform.
  2. Resharding cost – adding or removing a node should not require moving most of the data.

How It Works – Step by Step

  1. Hash the nodes – Each server (or virtual node) is hashed into a 0-360° space using a stable hash function like MD5 or SHA-1.
  2. Hash the keys – Every request key (e.g., user123) is also hashed into the same space.
  3. Locate the key – Move clockwise on the ring until you hit the first node whose hash is greater than the key’s hash. That node owns the key.
  4. Wrap around – If the key’s hash is larger than any node’s hash, you wrap to the first node on the ring.
  5. Virtual nodes – To smooth out uneven distribution, each physical server is represented by multiple points (e.g., 100 virtual nodes). The more virtual nodes, the closer the load approaches uniform.

Small Worked Example

Assume three cache servers: S1, S2, S3. We create two virtual nodes per server.

Virtual NodeHash (0-359)
S1-v130
S1-v2210
S2-v190
S2-v2270
S3-v1150
S3-v2330

Now a request for key K = "order567" hashes to 120. Starting at 120 and moving clockwise, the first node with a larger hash is S3-v1 at 150, so S3 stores the key.

If we add a new server S4 with two virtual nodes at 45 and 225, only keys that hash between 30-45 and 210-225 need to move, and both slices come from S2. That is 30 of 360 positions, about 8 % of keys, not the roughly 75 % you’d see going from key % 3 to key % 4.

Classic Interview Questions Where It Appears

QuestionWhere Consistent Hashing Shows Up
Design a distributed cache (e.g., Memcached)Partitioning the key space across cache nodes.
Design a sharded NoSQL store (e.g., Dynamo-style)Mapping partitions to storage nodes and handling node churn.
Design a CDN edge-selection servicePicking which cache server inside an edge location holds an object (DNS or anycast picks the nearest edge), while handling server addition/removal.

In each case the ring lives in the routing / partitioning layer, right after the client request is parsed and before the request is forwarded to a storage or edge node.

Trade-offs and the Alternative Interviewer May Ask About

AspectConsistent HashingSimple Modulo (Hash(key) % N)
Node churn impactMoves only ~1/​N of keys (with virtual nodes)Moves almost all keys when N changes
Load balanceDepends on number of virtual nodes; can be tunedPerfectly even if hash is uniform
Implementation complexityRequires a sorted ring, virtual node managementOne line of code
Hot-spot handlingStill possible; needs additional techniques (e.g., re-hashing hot keys)No built-in mitigation

Interviewers often follow up with “What if the hash function is poor?” or “What other ways can you partition data?” The classic alternative is range hashing (splitting the key space into contiguous ranges) or directory-based mapping where a central lookup table tells you which node owns each key. Each alternative trades off scalability for simplicity or for deterministic range queries.

30-Second Pitch

"Consistent hashing puts both servers and keys on a logical ring. A key is stored on the first server you encounter moving clockwise. Adding or removing a server only reassigns the keys that fall in that server’s slice, so the reshuffling cost is tiny. We use virtual nodes to smooth load and can tune the number of them for the desired balance. It’s the go-to solution for distributed caches, sharded stores, and CDN edge routing."

Common Mistakes Candidates Make

  • Skipping virtual nodes – Claiming that a single hash per server yields uniform load. In practice the distribution can be very uneven.
  • Mis-describing the lookup – Saying you “pick the nearest node” without emphasizing the clockwise direction and wrap-around.
  • Overstating hot-spot elimination – Consistent hashing reduces, but does not erase, hot-spot problems; you still need techniques like key salting or adaptive re-hashing.
  • Confusing with rendezvous hashing – Some interviewers ask about the alternative; mixing the two concepts shows a lack of clarity.

How to Practice This

  1. Study a worked design – Open the System Design AI library, find the “Consistent Hashing” design, and walk through the step-by-step diagram.
  2. Draw your own ring – On the canvas, place three servers, add virtual nodes, and map a handful of sample keys. Verify how many keys move when you add a fourth server.
  3. Explain aloud – Use the 30-second pitch and then answer a mock interview question (e.g., “Design a cache”) while referencing the ring you just drew.

Questions people ask

When should I choose consistent hashing over simple modulo?

Pick consistent hashing when your cluster will grow or shrink often, or when you need to keep data movement low during scaling. Simple modulo works for a static set of nodes.

What are virtual nodes and why are they important?

Virtual nodes are multiple hash points for each physical server. They spread each server’s responsibility around the ring, making the load more even and reducing hot spots.

How does consistent hashing handle server failures?

If a node fails, the next clockwise node on the ring takes over its slice. Only the keys that were on the failed node need to be re-loaded, which is a small fraction of the total.

What is the main alternative interviewers ask about?

Rendezvous (or highest-random-weight) hashing. It also minimizes key movement but uses a different selection formula; be ready to discuss its pros and cons.