Consistent Hashing

You have 4 cache servers. You distribute keys using hash(key) % 4. Server 0 gets keys that hash to 0, server 1 gets keys that hash to 1, and so on. Everything works beautifully.

Then server 3 dies. You now have 3 servers, so the formula changes to hash(key) % 3. Run through the math and you'll discover that almost EVERY key now maps to a different server. Key "user:42" used to be on server 2 (hash("user:42") % 4 = 2), but now it maps to server 1 (hash("user:42") % 3 = 1). The cached data on server 2 is useless for this key.

With 4 servers going to 3, roughly 75% of keys get remapped. With 100 servers going to 99, about 99% of keys get remapped. Losing one server invalidates virtually your entire cache. Every request that hits a remapped key causes a cache miss that falls through to the database. Your database gets crushed by a thundering herd. This is what happened to Memcached users in the early days.

Consistent hashing solves this. When a node is added or removed, only ~1/N of the keys need to move (where N is the number of nodes). Remove 1 server from 100, and only ~1% of keys are affected. The other 99% stay exactly where they were.

This is why Amazon built DynamoDB on consistent hashing. It's why Cassandra, Riak, Akamai's CDN, and Discord's message routing all use it. And it's one of the most commonly asked topics in system design interviews.

Imagine a circle, a ring, with positions numbered 0 to 2^32 (about 4.3 billion). This is the hash ring.

Step 1: Place nodes on the ring. Hash each server's identifier (like its IP address) to get a position on the ring. Server A might hash to position 100, server B to position 800, server C to position 1500.

Step 2: Place keys on the ring. Hash each data key to get a position on the ring. Key "user:42" might hash to position 450.

Step 3: Find the owner. Walk clockwise from the key's position until you hit a server. The first server you encounter clockwise owns that key. Key "user:42" at position 450 walks clockwise and hits server B at position 800. Server B owns the key.

When a node leaves: Only the keys between the failed node and the previous node on the ring need to be reassigned to the next node clockwise. All other keys stay put.

When a node joins: The new node takes ownership of a range of keys from its clockwise neighbor. Only those keys move. Everything else stays.

This is the fundamental insight: node changes only affect the keys in the immediate neighborhood of the changed node on the ring. The rest of the ring is untouched.