Scaling: From Modulo Hashing to Consistent Hashing

Why this matters: 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.

Key takeaway

Scalability requires distributing data across storage nodes and adding or removing them dynamically. Modulo hashing distributes evenly but remaps nearly every key when the node count changes. Consistent hashing minimizes data movement during scaling.

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.

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)

	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.