Consistent Hashing
You'll learn to
- -Explain why naive hashing breaks when nodes are added or removed
With a way to generate unique IDs across many machines, the next question is: which machine owns which piece of data? A naive answer (hash(key) % N) works until the moment N changes, at which point almost every key maps to a different machine than before. This is exactly the problem consistent hashing was invented to solve.
Instead of hash(key) % N, keys and servers both hash onto the same ring: a server only owns the keys in its arc.
A technique that minimizes data redistribution when nodes are added to or removed from a distributed cache or storage cluster.
Imagine a clock face (0-12). Your 3 servers sit at positions 12, 4, and 8. Each piece of data is hashed to a "time" on the clock, and is served by the next server clockwise. When you add a 4th server at position 2, only data between 12 and 2 moves - the rest stays put. With normal hashing, ALL data would move.
In a naive distributed cache with N nodes, you route a key by doing `hash(key) % N`. This works perfectly - until you add a node. Now you have N+1 nodes, and `hash(key) % (N+1)` gives entirely different results for almost every key. Every cached item is now on the wrong node. You've just invalidated ~100% of your cache in one go.
Consistent Hashing solves this by placing both servers and keys on a conceptual ring (a circular number line, e.g., 0 to 2^32). Each server owns an arc of the ring. A key is assigned to the first server clockwise from its position on the ring.
When you add a node, only keys in the arc that the new node takes over need to be moved. On average, only 1/N of the data moves (where N is the number of existing nodes).
When you remove a node, only the keys on that node's arc need to be redistributed to the next node clockwise.
Virtual nodes (vnodes): A real system assigns each physical server many positions on the ring (e.g., 150 virtual nodes per server). This ensures even distribution even when servers have different capacities or arrive/depart at different times. Cassandra uses 256 vnodes per server by default.
- -Only O(K/N) keys need remapping when a node joins or leaves (K = total keys, N = nodes).
- -Virtual nodes solve uneven distribution and make heterogeneous clusters work correctly.
- -Used by: Cassandra, DynamoDB, Memcached (via client-side hashing), Amazon S3, Chord.
- -The load balancing is only probabilistically even; vnodes improve this significantly.
Why is "hash(key) % N" a problem specifically when N changes, and not before?
"Modulo is just a bad hashing function."
"Modulo itself works fine; what breaks is that N is baked directly into every key's computed location. Change N from 4 to 5 servers, and almost every key's result of key % N changes too, meaning nearly all data has to move at once. Consistent hashing decouples a key's position from the total server count, so adding or removing one node only reshuffles the data in that node's arc of the ring, roughly 1/N of the data, not nearly all of it."