Consistent Hashing

The problem with hash(key) % N

Modulo hashing is simple and wrong at scale: with 4 cache servers, hash(key) % 4 sends each key to a server. Add a 5th server for more capacity, and % 5 relocates almost every key — a cache that was 95% full of useful data goes cold all at once, and every backing database takes the full read load until it refills. The problem isn't hashing — it's that one number (N) decides everyone's home.

The ring

Consistent hashing places both servers and keys on the same hash ring (imagine hash values 0 to 2^32-1 wrapped into a circle). A key belongs to the first server found walking clockwise from its position. Add a server: it only takes over the keys between itself and the previous server on the ring — everyone else's assignment is untouched. Remove a server: only its keys move, to its clockwise neighbor. One server joining or leaving reshuffles a small slice of the ring, not the whole thing.

Virtual nodes fix the lumpy-ring problem

A handful of real servers placed randomly on a ring can create uneven gaps — one server ends up owning way more of the ring than another. The fix: give each real server many virtual nodes (hundreds of points on the ring instead of one), spreading its share evenly and making load balance predictable even with few physical servers.

Where this actually shows up

Distributed caches (Memcached clients implement this client-side), DynamoDB-style key-value stores, CDN request routing, and sharded databases all use some form of this idea. Any time you hear "minimal data movement on scale-out," consistent hashing (or a close relative) is almost certainly underneath it.

Remember this

• Modulo hashing reshuffles almost everything when the server count changes.
• A ring means only the keys between two neighbors move when one node joins or leaves.
• Virtual nodes spread one server's share evenly across the ring instead of leaving lumpy gaps.