Step 1 · The pattern
Spread keys across cache nodes
Short-link lookups are cached on three servers. A rule decides which server holds each key, so every app server looks in the same place and finds it.
- lookup
- cache hit
In short
Consistent hashing: how it works and how it breaks
To spread keys over several cache servers you need a rule that maps a key to a server. The obvious rule is hash(key) mod N, where N is the number of servers. It spreads keys evenly and has one terrible property: N is in the formula. Go from three servers to four and almost every key's answer changes, so about three quarters of requests look on a server that does not have their data. The cache is effectively empty and the database takes the full load at once. Consistent hashing removes N from the formula. Servers and keys are both hashed onto a ring, and each key belongs to the next server clockwise. A new server only takes over the arc just before it, roughly one Nth of the keys. Real systems place each server at many points on the ring, called virtual nodes, to keep shares even.
How this comes up in interviews
"You cache data across several servers and need to add one more. How do you decide which server holds each key, and what happens to the cache when the count changes?"
Then they ask
- Only about one Nth of the keys move. Is that always safe at peak traffic? How would you check and reduce the impact?
- The keys are spread evenly but one node still runs hot. What could explain it, and what would you do?
- Clients learn about a membership change at different times. What goes wrong in a cache, and how do you limit it?
A strong answer covers
- hash(key) mod N spreads keys evenly but has N in the formula, so changing the server count remaps almost every key.
- After that change most lookups go to a server without the data, so the cache is effectively empty and the database takes the full load.
- Consistent hashing places servers and keys on a ring, and a key belongs to the next server clockwise.
- A new server takes only the arc before it, roughly one Nth of the keys. A dead node's keys go to its neighbour.
- Real systems place each server at many points on the ring, called virtual nodes, to keep shares even.
Points to cover, not a script. Say them in your own words and tie them to a system you have worked on.
On one page: the track cheat sheet.
Sources: Dynamo: Amazon's highly available key-value store (SOSP 2007) ↗ · Scaling Memcache at Facebook (NSDI '13) ↗ · Redis docs: cluster specification ↗ · Report a problem
Diagrams are our own simulations: the timings, rates and counts in them are illustrative, not measurements. Captions are original wording.