Consistent Hashing: Scaling a Cache Across Many Servers
You'll learn to
- -Explain why naive hash(key) % N breaks when servers are added or removed
- -Describe how a hash ring with virtual nodes distributes keys and minimizes remapping
- -Reason about the fraction of keys that move when the ring changes size
A single LRU cache is great until your dataset outgrows one machine's memory, so real systems shard a cache across many servers. The obvious approach - server = hash(key) % num_servers - works fine right up until num_servers changes. Level 14 is about the algorithm that fixes that: consistent hashing.
The Naive Approach Falls Apart
With hash(key) % N, adding or removing even a single server changes N, which changes the modulus for every key - hash(key) % 4 and hash(key) % 5 send almost every key to a different server than before. In production that means a single server joining or leaving (scaling up, or a crash) triggers a near-total cache stampede: every client's next request is a miss, and your backing database gets hit with the full traffic all at once. That is precisely the kind of cascading failure a cache exists to prevent.
The Ring
Consistent hashing hashes both the servers and the keys into the same circular numeric space (imagine hash values arranged on a clock face). To find which server owns a key, hash the key and walk clockwise around the ring until you hit the first server. Adding a server only affects the keys between it and the previous server on the ring - everything else stays put. Removing a server only remaps the keys that were assigned to it, which now fall through to the next server clockwise. Instead of "almost everything moves," it becomes "on average, only 1/N of the keys move."
One more wrinkle: with only a handful of real servers placed at essentially random points on the ring, the arcs between them can be wildly uneven, so one server could end up owning most of the keys. The standard fix is virtual nodes: each physical server is hashed onto the ring many times (with a suffix like "serverA#0", "serverA#1", ... "serverA#150"), so its share of the ring is an average over many small arcs instead of one lucky or unlucky arc - smoothing out the load balance.
- -Adding a server: only the keys in the arc it now owns move to it - everything else is untouched.
- -Removing a server: only its keys move, falling through to the next server clockwise.
- -Virtual nodes: each real server gets many positions on the ring, smoothing out uneven load.
- -The hash ring is the same core idea behind DynamoDB, Cassandra, and most CDN edge-routing layers.
The headline number worth remembering for an interview: naive modulo hashing remaps close to 100% of keys on a resize; consistent hashing remaps roughly 1/N of them.
You need to shard a cache across servers that will be added and removed over time. Why not just use hash(key) % num_servers?
"That should be fine, mod is fast."
"Mod-based sharding is fine as long as the server count never changes, but the moment it does, the modulus changes and nearly every key remaps to a different server - that's a full cache stampede onto the database. I'd use consistent hashing instead: place servers and keys on a hash ring, walk clockwise to find ownership, and use virtual nodes so load stays balanced. That way a resize only moves about 1/N of the keys."
What is the core problem with hash(key) % num_servers as a sharding strategy?
Level 14: Consistent Hashing has you build the ring yourself: hashing servers onto it (with virtual nodes), routing a key to the correct server by walking clockwise, and handling dynamic add/remove so the ring only remaps the minimal set of keys - not the whole cache.