CSE Roadmap

Core tier · about 3 hours · 8 parts

Part 6 of 8 · 2 min read

Hot keys that hashing cannot fix

When a single key is so busy that one partition is overloaded whatever the scheme.

Think of a shop where a celebrity walks in. However the queues are arranged, the crowd all wants the same till.

Hashing spreads different keys evenly. It cannot spread one key. The book states it: in the extreme case where all reads and writes are for the same key, all requests go to the same partition, and hashing does not help, since the hash of an identical id is still the same. A celebrity with millions of followers can cause a storm of activity on one key: the user id, or the id of the post that everyone comments on.

Most systems cannot compensate for this automatically, so the application must reduce the skew. The book's technique: add a random number to the start or end of the key of a hot item. A two-digit decimal number splits the writes over 100 different keys, which can then go to different partitions.

The cost: reads must now fetch from all 100 keys and combine the results. It also needs bookkeeping, since it only makes sense for the few hot keys. For the many keys with low write rates, appending a random number would be overhead. The application must keep track of which keys are split.

A worked example. A post gets 50,000 comment writes per second at its peak. A partition can take 5,000 writes per second.

  • Without splitting: 50,000 on one partition. It fails at ten times its limit.
  • Split into 20 sub-keys (post:77#00 to post:77#19), chosen at random per write: 2,500 per sub-key. If they land on different partitions, each is at half its limit.
  • Read the comment count: read 20 sub-keys and add them: 20 reads, not 1. For a counter, that is acceptable. For a page that is read 100,000 times a second, the extra reads could cost more than the writes did. In that case the combined result is cached (Level 3) and recomputed every second.

Common mistake

Believing that hash partitioning ends hot spots. It ends hot spots from the key pattern. One very popular key remains a hot spot.

Other fixes seen in practice (beyond the book): give hot items their own dedicated partition or machine, cache the hot reads, and queue and batch the writes.

Check yourself:

  • A hot key is split into 50 sub-keys. How many reads does a full read take?
  • Why is hashing the key no help for one very popular key?