Consistent Hashing.

🧠Start with the mental model: a clock face

Imagine a circle numbered 0 to 2^32-1, wrapping around like a clock. You hash each SERVER (by name/IP) to a point on the ring. You hash each KEY to a point too. A key belongs to the first server you hit walking clockwise from the key's position. That's the whole idea: keys and servers live on the same ring.

🐞What it fixes

The naive way to shard N servers is: server = hash(key) % N. It's balanced and dead simple — until N changes. Add or remove ONE server and the modulus changes for almost every key, so nearly ALL keys remap. For a cache that means a near-total cache miss storm; for a DB it means moving almost all your data. Painful.

On the ring, adding/removing a server only touches the keys in ONE arc — the slice between the new/old server and its neighbor. Roughly K/N keys move instead of K. That's the headline: minimal disruption when the cluster resizes.

📺Walkthrough

Ring with servers A, B, C placed at points 10, 150, 300 (mod 360 for the picture).

• key "user:42" hashes to 120 -> walk clockwise -> hits B (150).
• Add server D at 130. Now "user:42" (120) hits D instead of B.
• Only keys in (10, 130] moved — A's and C's keys never budged. Remove a node and the same locality holds in reverse.

⚠️Where the simple model BREAKS down

With only a handful of nodes placed by a hash, the arcs are wildly uneven — one server can own a huge slice and get hammered while another sits idle. Hashing doesn't magically space points evenly. And when a node dies, its ENTIRE arc dumps onto the single next node, not the whole cluster.

🩹The fix that makes it real: virtual nodes

Place each physical server at MANY points on the ring (say 100–200 "vnodes" per server, each = hash(server + "#i")). Now each server owns many small scattered arcs. Benefits:

• Load evens out — law of large numbers smooths the slices.
• When a node dies, its many arcs spread across MANY successors, not one.
• Heterogeneous capacity is easy: give a beefier box more vnodes.

This is what Cassandra, DynamoDB, Riak, and consistent-hash load balancers actually do.

🪤Gotchas

• "Consistent hashing balances load" is only true WITH enough vnodes — without them it's lumpy.
• A hot KEY (one viral item) still overloads its owner; consistent hashing balances key DISTRIBUTION, not per-key traffic. Add replication for hotspots.
• Use a good hash (e.g. murmur/xxhash) — a weak one clusters points and ruins balance.

🏋️Exercise

You run a 4-node cache, ~1M keys, using hash(key) % 4. You need to add a 5th node. Estimate what fraction of keys remap under modulo vs under a consistent-hash ring. Then: how many virtual nodes per server would you pick, and what's the trade-off as that number goes up (hint: memory + lookup cost vs balance)?