Consistent Hashing in System Design
On this page
Symptom: adding one cache server empties the cache
A cache cluster has 10 servers, and keys are assigned with hash(key) % 10. Traffic grows, so an 11th server goes in. Now hash(key) % 11 sends most keys to a different server than before. Almost every lookup misses at once, and the database behind the cache takes the full load (a stampede, Day 39). Adding capacity caused an outage.
How many keys move? With modulo hashing, going from N to N+1 nodes moves about N/(N+1) of keys: around 91 percent for 10 to 11. In a simulation of 100,000 keys growing from 3 to 4 nodes, modulo hashing moved 75 percent of them.
How consistent hashing works: the hash ring
Consistent hashing maps both nodes and keys onto the same circular range of hash values, the ring. A key belongs to the first node clockwise from its position.
When a node joins, it takes over only the keys between itself and the previous node. When a node leaves, only its keys move to the next node. Everything else stays put. In the same 3-to-4 simulation, consistent hashing moved 22 percent of keys, close to the ideal 25 percent, the new node's fair share. (The System Design Interview course includes the full simulation code.)
Virtual nodes for even load
With one point per node, the arcs between nodes are uneven, so one node may own twice the keys of another. And when a node leaves, all its keys go to a single neighbor, which may overload it.
Virtual nodes fix both: each physical node is placed at many points on the ring, often 100 or more. Its share becomes many small arcs spread around, so load evens out, and when it leaves, its keys spread across many other nodes. Virtual nodes also allow weighting: a larger server gets more points.
Placing replicas on the ring
To keep copies, store each key on the next N distinct physical nodes clockwise from its position, skipping extra virtual nodes of a node already chosen. That's how Dynamo-style stores such as Cassandra place replicas, and it combines naturally with quorums (Day 69).
Fixed hash slots: Redis Cluster's alternative
Instead of a ring, split the key space into a fixed number of slots and assign slots to nodes. Redis Cluster uses 16,384 slots with CRC16(key) mod 16384. Adding a node means moving some slots, and the keys in them, to it. The effect is the same, small and controlled movement, with an explicit, easy-to-inspect assignment table. Many sharded databases do the same with "logical shards" (Day 26).
Where consistent hashing is used
- Distributed caches: client libraries for Memcached use consistent hashing to pick servers.
- Dynamo-style databases: Cassandra and Riak. (The DynamoDB service, despite the name, manages partitions differently from the original Dynamo paper: it hashes keys into partitions and replicates each partition with consensus, and moves partitions for you.)
- Load balancers that keep a user or key on the same backend (cache affinity), for example Envoy's ring hash and Maglev.
- Sharded databases using logical shards mapped onto servers.
What consistent hashing doesn't fix: hot keys
Consistent hashing doesn't help with one very hot key. If a single product or celebrity account gets 50,000 requests a second, all of them hash to the same node, however evenly the other keys are spread. Hot keys need their own treatment: replicate the value to several nodes and read from any, add a local in-process cache in front (Day 40), or split the key, such as counter:42:0 to counter:42:15, and combine on read.
Check yourself
Changing N changes the result of the modulo for most keys, so they map to different nodes even though only one node was added.
They spread each node's share across many small arcs, evening out load, and spread a departing node's keys across many nodes instead of one neighbor.
One hot key maps to that node no matter how keys are spread. Cache it locally on app servers, replicate it to several nodes, or split it into several keys.
It hashes every key into one of 16,384 fixed slots and assigns ranges of slots to nodes. The slot for a key never changes, so adding a node means moving some whole slots to it, along with their keys, instead of rehashing every key. Only the keys in moved slots relocate.
A key's primary owner is the first node clockwise from the key's hash, and replicas go on the next distinct nodes clockwise, skipping virtual nodes of a server already chosen and ideally spreading across racks or zones. That keeps copies on different physical machines.