Consistent Hashing

You are designing a distributed cache, a sharded database, or a fleet of workers that own different keys. At some point the interviewer asks the question that breaks simple hash partitioning:

"What happens when you add another node?"

If your answer is hash(key) % number_of_nodes, almost every key moves when the node count changes. That is fine for a toy system. It is a disaster for a real one. You would invalidate most of your cache, migrate most of your database rows, or reshuffle most of your worker assignments just because capacity changed.

Consistent hashing is the standard answer. It gives you a stable way to map keys to nodes so adding or removing a node moves only a bounded slice of the keyspace.

Modulo hashing looks attractive because it is simple:

node = hash(key) % node_count

With three nodes, keys map to node 0, 1, or 2. Add a fourth node and the formula changes:

before: hash(key) % 3
after:  hash(key) % 4

The same key now lands on a different node for most hash values. If you have 1 billion cache keys, a large majority of them are suddenly on the wrong machine.

That causes three practical problems:

• Cache clusters lose most of their hit rate after scaling events.
• Databases need huge migrations before traffic can route safely.
• Stateful workers lose ownership of tasks, sessions, or connections.

The issue is not the hash function. The issue is that the node count is part of the routing formula.

Consistent hashing removes the direct dependency on node_count.

Imagine the hash space as a ring. The ring might represent all values from 0 to 2^32 - 1. Both nodes and keys are placed on that ring using a hash function.

To route a key:

1. Hash the key onto the ring.
2. Walk clockwise until you find the first node.
3. Store or serve the key from that node.

If user:123 hashes to position 80 and the next clockwise node is Node B at position 120, Node B owns that key. Each node owns the range between the previous node and itself.

The important property: the routing rule does not change when the number of nodes changes. The ring still means "walk clockwise to the next node."

When you add a node, it takes ownership of the range between itself and the previous node. Only keys in that range move.

Before:
  Node A owns 0-99
  Node B owns 100-199
  Node C owns 200-299

Add Node D at 150:
  Node A owns 0-99
  Node D owns 100-150
  Node B owns 151-199
  Node C owns 200-299

Only part of Node B's old range moves to Node D. Nodes A and C are untouched.

When a node is removed, its keys move to the next clockwise node. Again, only that node's range moves.

This is the entire value of consistent hashing: topology changes have local impact instead of global impact.

For N evenly balanced nodes, adding one node moves roughly 1 / N of the keys. With 100 nodes, that is about 1 percent of the keyspace. Modulo hashing can remap almost everything.

The basic ring has one problem: distribution can be uneven.

If each physical node appears once on the ring, one node might land in a huge gap and own too much traffic. Another might land close to its neighbor and own very little.

Virtual nodes fix this. Instead of placing each physical node once, place it many times:

Physical nodes:
  A, B, C

Virtual nodes:
  A-1, A-2, A-3, ... A-100
  B-1, B-2, B-3, ... B-100
  C-1, C-2, C-3, ... C-100

Each virtual node maps back to a physical node. Since every physical node owns many small ranges across the ring, load is smoother.

Virtual nodes also make rebalancing less painful. When you add Node D, it takes many small ranges from A, B, and C instead of one large range from a single unlucky neighbor.

Typical interview answer: use 100 to 200 virtual nodes per physical node, then tune based on observed load distribution.

Consistent hashing tells you the primary owner of a key. Production systems usually need replicas too.

A common strategy is to keep walking clockwise after the primary owner:

primary: first node clockwise from key
replica 1: next distinct physical node clockwise
replica 2: next distinct physical node clockwise

If Node B owns a key and the replication factor is 3, the key might live on B, C, and D. If B fails, reads can go to C while the cluster repairs or reassigns B's ranges.

With virtual nodes, make sure replicas land on distinct physical machines. Replicating from A-1 to A-2 does not help if both virtual nodes map to the same server.

For databases, node failure usually triggers hinted handoff, read repair, anti-entropy repair, or background streaming. For caches, the system may simply miss and refill from the source of truth.

Consistent hashing is not free.

You need membership management. Every client or router must know which nodes are in the ring. That usually comes from service discovery, a coordinator, or a small routing service.

You need a rebalance process. Adding a node changes ownership for some ranges, but data still has to move. During that window, the system needs a safe read/write policy:

• dual-read old and new owners during migration
• forward requests from old owners to new owners
• mark ranges as moving and route through a coordinator
• stream data first, then flip ownership

You also need observability. Track key distribution, request rate per node, hot ranges, replication lag, and migration progress. Consistent hashing reduces movement, but it does not eliminate hotspots caused by celebrity users, viral content, or skewed tenant traffic.

Consistent hashing appears anywhere ownership needs to survive topology changes.

Redis Cluster uses a related fixed-slot model. It hashes each key to one of 16,384 slots, then assigns slots to nodes. Moving slots between nodes gives similar operational benefits to moving virtual-node ranges.

Cassandra uses token ranges and virtual nodes. Dynamo-style systems popularized the ring plus replication pattern.

Mistake 1: Saying hash(key) % N and stopping.

Modulo hashing is fine until the cluster size changes. Always explain what happens during add/remove events.

Mistake 2: Forgetting virtual nodes.

A ring with one position per physical node can be badly imbalanced. Virtual nodes are the practical version.

Mistake 3: Ignoring replication.

The ring gives ownership. It does not automatically give availability. Mention replica placement and distinct physical nodes.

Mistake 4: Pretending rebalancing is instant.

Only some keys move, but those keys still move. Call out background streaming, safe routing during migration, and monitoring.

Mistake 5: Using it for range queries.

Consistent hashing is great for key lookups and even distribution. It destroys locality, so range queries become scatter-gather unless you add a separate index or choose a different sharding strategy.

Consistent hashing solves the resharding problem caused by hash(key) % N.

The core idea is simple: put keys and nodes on a hash ring, then route each key to the next clockwise node. Adding or removing a node only moves the adjacent range instead of remapping the whole keyspace.

In interviews, say the full production version:

• use a hash ring for stable ownership
• use virtual nodes for even distribution
• place replicas on distinct physical nodes
• handle rebalancing with safe routing and background data movement
• avoid it when range queries or data locality dominate the design

That answer works for distributed caches, sharded databases, WebSocket gateways, crawlers, and worker fleets.