Scaling: From Modulo Hashing to Consistent Hashing

In one line: the requirement was incremental scalability with minimal disruption. This lesson shows the naive approach failing that requirement badly, then fixes it — and the fix is one of the most reused ideas in distributed systems.

The naive approach: modulo hashing

For a system with 4 nodes we want 25% of requests on each. When a request arrives, hash its key and take the remainder modulo m, where m is the node count. The result determines which node handles it.

Number of nodes (m) = 4

Hash("Key 1") = 10
10 % 4 = 2          ->  Node 2 processes the request

It distributes evenly and it is trivial to compute. It also fails the requirement.

Why modular hashing breaks dynamic scaling

Adding or removing a node changes the divisor m, which alters the mapping for nearly all keys.

Remove node 2 from a 4-node cluster and a key that mapped there might now land on node 1, because 10 % 3 = 1. Since nodes cache data locally, this shift forces massive data migration — a reshuffle across the whole cluster, causing high latency and network congestion exactly when you were trying to grow capacity.

You wanted to add 25% more capacity and you triggered a cluster-wide migration to get it. That is the opposite of incremental.

Consistent hashing

Consistent hashing manages load effectively by minimizing data movement during scaling.

Visualize the hash space as a ring with values from 0 to n - 1, where n is the total number of available hash values.

The mechanism has three steps:

Each node ID is hashed to assign it a position on the ring.
Request keys are hashed with the same function to find their position on the ring.
The request is routed to the first node encountered when traversing clockwise from the key's position.

Ring (clockwise):   ... N1 ..... N2 ....... N3 ... N4 ...
Key R hashes here:        ^
Routed to:                N2      (first node clockwise)

The property that makes it work

When a new node joins the ring, it takes over a portion of the keys from its immediate successor. Every other node is unaffected.

That is the entire trick. Under modulo hashing, node count is an input to every key's placement, so changing it disturbs everything. Under consistent hashing, a node's position is independent of how many other nodes exist — so adding one only perturbs its immediate neighborhood.

Only a small subset of keys moves, which is what makes scaling efficient. And since hashes are randomly distributed, the load is expected to be even on average.

	Modulo hashing	Consistent hashing
Placement rule	`hash(key) % m`	First node clockwise on the ring
Depends on node count	Yes — `m` is in the formula	No — positions are independent
Keys moved when adding a node	Nearly all	Only the successor's share
Distribution	Even by construction	Even on average, not guaranteed
Suits incremental scaling

The problem consistent hashing does not solve

Read that "even on average" carefully — because in practice, random distribution does not guarantee equal load.

A server responsible for a large segment of the ring receives a disproportionate share of storage and retrieval requests. That creates a hotspot, which can bottleneck the entire system.

If the segment between nodes N4 and N1 is large, N1 handles significantly more requests than the others. This non-uniform distribution degrades performance.

Key takeaway

Consistent hashing replaces "recompute every key's home" with "perturb one neighborhood." That converts scaling from a migration event into a routine operation — which is precisely what incremental scalability requires.

Interview signal by level

Level	What a strong answer sounds like
L4	"We hash the key to pick a node."
L5	Rejects modulo: "not hash mod n — adding a node changes the divisor and remaps almost everything. Consistent hashing so only a neighbor's keys move."
Staff+	Names the residual problem: "consistent hashing fixes the migration cost but not the distribution — random ring positions leave uneven gaps, so one node owning a large arc becomes a hotspot. That needs virtual nodes."

Next: the fix for uneven ring segments.