Module 02 · Lesson 09
Consistent hashing
Adding a cache node should not invalidate almost everything.
What you will be able to do
- Show why modulo hashing remaps most keys when the node count changes
- Explain the hash ring and ownership of key ranges
- Describe how virtual nodes fix uneven distribution
- Recognise where consistent hashing is and is not the right tool
The problem with modulo
node = hash(key) % 4 // keys spread across 4 nodes add a node, now there are 5: node = hash(key) % 5 // about 80% of keys change owner with 4 nodes, moving to 5 remaps ~4/5 of the keyspace. For a cache, that is an instant mass miss and a database stampede.
This is why resizing a cache cluster used to be terrifying. The data is still there on old nodes, but every client now asks the wrong node. The load lands on the database, which was only ever sized for misses.
The ring
Map the space to a circle
Hash both node names and keys into the same numeric space, say 0 to 2^32, and treat it as a circle.
Each node owns the arc before it
A key belongs to the first node clockwise from its hash. Adding a node takes over only the arc between it and its predecessor.
Only neighbours move
Adding a fifth node to four moves about 1/5 of the keys — the ones it now owns — instead of 4/5. Removing a node hands its arc to the next node only.
Add virtual nodes for fairness
One position per physical node produces wildly uneven arcs. Give each node 100 to 200 virtual positions; the arcs average out, and a bigger machine can be given more of them.
Say the property, not the algorithm
"Consistent hashing means adding a node moves about 1/N of the keys rather than almost all of them, so a cache resize costs a brief partial miss instead of a database stampede." That sentence is the answer; the ring is just the mechanism.
Where it is used, and where it is not
- Used: distributed caches (Memcached clients), Dynamo-style stores, search sharding, and load balancers that need session affinity.
- Used for routing, not storage: many systems keep the ring in a coordination service so every client agrees on ownership.
- Not a fix for hot keys: consistent hashing balances key counts, and one overwhelmingly popular key still lands on one node.
- Not always needed: with a managed database, range or hash partitioning by tenant may be simpler and give better locality for queries.
Q. Why not just use rendezvous (highest random weight) hashing?
It is a fine alternative: score each node per key and pick the highest, which gives similar movement properties with less bookkeeping and no ring to maintain. Consistent hashing is the better-known answer; saying "I would consider rendezvous hashing because it needs no ring state" is a depth signal.
Q. What happens when a node fails and comes back with a cold cache?
Its share of keys misses at once and hits the backing store. Mitigations: hand its arc to the next node so cached data is not wasted, warm the node gradually, and cap the request rate to the database so a cold cache degrades latency instead of causing an outage.
Worth remembering
- Modulo hashing moves almost every key when nodes change: N to N+1 remaps about N/(N+1) of them.
- A hash ring moves only the keys owned by the changed node — about 1/N of the keyspace.
- Virtual nodes give each physical node many ring positions, which evens out distribution.
- Consistent hashing balances load across nodes; it does not make a hot key stop being hot.
Checkpoint
Answer all 2 questions to finish the lesson.
1. With 4 cache nodes, going to 5 with plain modulo hashing remaps roughly what fraction of keys?
Changing the modulus changes almost every key's owner — roughly 80% here. That mass miss is what consistent hashing exists to prevent.
2. Why do consistent-hashing rings use virtual nodes?
A single position per node produces uneven arcs, so some nodes get far more keys. Many virtual positions per node average out the load and let capacity be weighted.