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.
Adding and Removing Servers on a Hash Ring
12 keys, hashed once and fixed. Watch how few of them actually move when the server set changes.
Three servers on the ring, evenly spaced. Each owns the keys in the arc clockwise from the previous server up to itself.
Keys that moved this step: 0 / 12
Interview Signal is part of Pro
See a real weak answer next to a real strong one for this exact topic.
Quiz is part of Pro
Test what you just read with a short quiz, and bank the XP.