Hot partitions and celebrity keys

The problem: one link, one shard, all the traffic

Snip's codes are spread across 256 logical shards by hash, so each shard gets about 1/256 of the links. Then a celebrity posts a Snip link to forty million followers, and for ten minutes that one code gets 50,000 redirects a second. Hashing spread the keys evenly; it can't split one key. Every request for x7Kp goes to the same cache node and, on a miss, the same shard, while the other 255 sit idle.

That's a hot partition, and its cause here is a hot key (sometimes called a celebrity key). Hot partitions come from three directions:

The third is a choice of key, fixed by choosing a better one (05.01 Sharding: range, hash, directory). The first two exist in the data, and you need ways to cope with them.

Hot reads: copy the hot key

Reads are the easier half, because copies of a value can be served from many places.

• Cache it closer. Snip's Redis tier already absorbs most redirects. For the very hottest codes, each app server also keeps a tiny in-process cache of a few thousand entries for a few seconds. 50,000 requests a second spread over 40 app servers become 40 requests a second to Redis.
• Spread one key over several cache nodes. Store copies under x7Kp#1 … x7Kp#8, which hash to different nodes, and have each reader pick one at random. Writes must update every copy, so do it only for keys you've detected as hot.
• Coalesce. When a hot key's cache entry expires, a thousand requests can miss at once and all query the database. Let one request fetch it while the others wait for its answer (06.05 Stampedes and request coalescing).

Hot writes: split the key

Writes are harder, because they must end up in one correct value. Every click on the viral link increments total_clicks on one row (04.12 Denormalisation), and one row can only take so many updates a second before the transactions queue on its lock.

• Batch. Snip already does this: click events go to a queue, and workers turn thousands of clicks into one UPDATE every few seconds (02.06 Async workers and queues). This is the first fix to reach for.
• Split the counter. Keep N rows per hot counter, x7Kp:0 … x7Kp:15. Each write picks one at random; a read sums all N. Writes spread over N rows (or N shards, if the sub-keys hash differently); reads get a little more expensive.

-- a split counter: 16 rows for one link; the app picks a random slot, 0 to 15
UPDATE link_clicks SET clicks = clicks + 1
WHERE code = 'x7Kp' AND slot = $1;

SELECT sum(clicks) FROM link_clicks WHERE code = 'x7Kp';

Big tenants: give them their own home

When the hot partition is a tenant (all of one customer's data on one shard), the options are to move that tenant to a dedicated shard (easy with a directory, 05.01 Sharding: range, hash, directory), or to shard their data by a finer key, such as the channel or the link instead of the customer. That's what Slack did, below.

Find them before they find you

Hot keys are invisible in averages: 256 shards at 5% CPU and one at 100% averages to fine. Watch per-shard load, not just the total, and sample the busiest keys (a periodic "top 100 codes this minute" from the request log) so you can spot a viral link in seconds and turn on the hot-key handling for it.

Recap

Interview questions