Consistent Hashing

When you spread data (or load) across N machines, you need a rule that maps each key to a machine. The obvious rule, hash(key) % N, has a fatal flaw at scale: change N and almost every key moves. Consistent hashing is the fix — a mapping where adding or removing a node only reshuffles a small, local slice of keys.

Why modulo breaks

Say you cache across 4 servers with hash(key) % 4. Add a fifth server and the rule becomes % 5. Now the server for nearly every key changes, so nearly every cached entry is suddenly in the "wrong" place — effectively a full cache wipe at the worst possible moment. Remove a server and the same thing happens. For a system that adds and removes nodes routinely, that's unacceptable.

The ring

Consistent hashing arranges the output of the hash function into a ring — imagine the range of hash values bent into a circle. Then:

1. Place each node on the ring at hash(node_id).
2. Place each key on the ring at hash(key).
3. A key belongs to the first node clockwise from its position.

        [A]
     k1      k2
   ●            ●
 [C]            [B]
   ●            ●
     k4      k3
        (ring)

Now the magic: add a node D, and it only steals the keys that fall in the arc between D and the previous node — everything else stays put. Remove a node, and only its keys move, to the next node clockwise. The blast radius of a membership change is one node's worth of keys, not the whole dataset.

Virtual nodes even it out

Plain consistent hashing has a problem: with few nodes, the arcs are uneven, so some nodes own far more of the ring than others — a load imbalance. And when a node leaves, all its keys dump onto a single neighbour.

The fix is virtual nodes: place each physical node at many points on the ring (say 100–200 hashed positions) instead of one. Now each physical node owns many small arcs scattered around the ring. The distribution is much more even, and when a node fails, its load spreads across many neighbours instead of crushing one.

Where it shows up

• Distributed caches (so adding a cache node doesn't evict everything).
• Databases like Cassandra and DynamoDB, to assign partitions to nodes.
• Load balancers that want the same client to reach the same backend.
• Content delivery / sharded storage, to place objects on nodes.

You rarely implement it by hand — you reach for a system that already uses it. The point in an interview is to recognise the need: whenever nodes come and go and you want minimal reshuffling, consistent hashing (usually with virtual nodes) is the answer.

What to say in an interview

Name the problem it solves, not the ring mechanics:

"I'll distribute the cache keys with consistent hashing so that scaling the cache tier up or down only moves a fraction of the keys instead of invalidating everything. I'd use virtual nodes to keep the load even and to spread a failed node's keys across the rest rather than onto one neighbour."

Next up: CAP Theorem — the trade-off every distributed system has to make.