Step 1 · The pattern
Hash each key to a shard
One cache server is not enough, so keys are split across three shards. A hash of the key decides which shard owns it. With many keys, load spreads evenly.
- request
- served
In short
Hot-key replication: how it works and how it breaks
A sharded cache spreads keys across servers by hashing each key. That balances load well when traffic is spread over many keys. It fails when one key is far more popular than the rest: a celebrity's profile, a viral post, a global config value. Every request for that key hashes to the same shard. That server saturates and times out while its neighbours sit idle, and adding shards changes nothing, because one key still lives in one place. The fixes all make the hot key live in more than one place. Store copies under several names, such as key#1 to key#N, and have clients pick one at random. Read from replicas. Or keep a short-lived copy inside each app server, so most reads never reach the cache. All three trade a little staleness for a lot of headroom.
How this comes up in interviews
"One shard in your cache cluster is saturated while the others are nearly idle. Adding shards did not help. What is going on?"
Then they ask
- How would you find out which key is responsible?
- You replicate the hot key under several names. What happens when its value changes?
- When would you choose an in-process copy on each app server over copies in the cache, and what does it cost?
A strong answer covers
- One key always hashes to one shard, so a single very popular key overloads that shard however many shards exist.
- Make the hot key live in more than one place: suffixed copies picked at random, replica reads, or a short-lived local copy.
- The cost is staleness: a write must reach every copy, and until it does some readers see the old value.
- It suits hot, read-heavy keys. It is a poor trade for data that changes constantly or must be exactly right.
- Sharding balances load across many keys. It cannot split the traffic of one key.
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: Discord: How Discord stores trillions of messages ↗ · 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.