Hot keys and celebrities

Most keys get a little traffic. A few get a lot. A celebrity's account, a viral short link and a popular seat map each put the load on one key. Adding more machines does not help, because one key lives on one machine. You need to split the key, cache it, or change how its updates travel.

The big idea

Think of a single cashier at a busy counter. Adding more cashiers at other counters does not help this line. You must open a second counter for the same product, or send some customers to a different queue.

Salting does the second step for counters. Hybrid fan-out does it for feeds. Local caches and single-flight protect the source when a hot value expires.

Walking through it

Salted counter. Say one post gets 10,000 likes per second on one key. That single key is the bottleneck. Split it into 10 keys, each with a random suffix. Each salt gets 10,000 divided by 10, which is 1,000 writes per second. A read sums the 10 keys.

Write: pick a random salt 0..9, increment "post:9:likes:<salt>"
Read:  sum "post:9:likes:0" through "post:9:likes:9"
Load:  10,000 per second / 10 salts = 1,000 per second per key

Hybrid fan-out. A feed can push each new post into every follower's inbox, which is fast to read. But a celebrity with 50 million followers cannot push into 50 million inboxes on every post. So normal accounts push on write, and celebrity posts are pulled on read.

Local caches and single-flight. Keep the hottest keys in each app server's memory, for a short time. When the entry expires, one request fetches it, and the others wait for that answer. Without this, thousands of misses hit the source at once.

Common mistakes

• Sharding and expecting a hot key to spread. One key still lives on one shard.
• Salting without a read plan. Every read must now sum all salts.
• Caching without single-flight. An expiring hot value sends a stampede to the source.

Check yourself

1. With 10 salts, what is the write rate on each salted key in the example? 1,000 per second, because 10,000 writes spread across 10 keys.
2. Why use fan-out on read for celebrities? Writing one post into 50 million inboxes on every post is too much work. Pulling the celebrity's posts at read time avoids it.

Key takeaways

• A single hot key cannot be fixed by adding machines or shards.
• Salting splits a counter across keys. Reads then sum the parts.
• Hybrid fan-out pushes for normal users and pulls for celebrities.
• Caches with single-flight protect the source from stampedes.

Further learning

The news feed case study shows hybrid fan-out in full.

For caching tools in depth, see caching.

Next, see how many clients fighting over one scarce resource needs its own pattern, in contention and holds.