When one key gets all the traffic (hot partition)

After you shard a database, the interviewer asks: "Now one shard is at 100% CPU and the others are at 30%. What happened, and what do you do?" This question tests whether you know that spreading keys evenly does not spread the requests evenly.

A weak answer says "add more shards" or "use a better hash". A strong answer says that one key gets most of the requests, and that a key lives on one shard. It then says how to find the key, and how to serve it from many places.

At SDE-1 level you should explain why one shard is busy. At SDE-2 level you should work out the load and give two fixes. At SDE-3 level you should say what each fix costs, and how to find the next hot key without a person.

Eight ticket windows serve a large crowd. A person is sent to a window by their ID number, so the crowd spreads evenly. One day a famous cricketer comes, and thousands of people want to see the one signed bat. The bat is kept at window 3. Window 3 has a huge line. The other seven windows are almost empty. Building eight more windows does not help, because the bat can be in only one of them.

In lesson 43, the shard key decides which shard owns a row, and a hash spreads the keys evenly. But a hash spreads keys, not requests. If one key gets very many requests, the shard that owns it gets all of them. A hot key is a key that gets far more requests than the others. A hot partition (also called a hot shard) is the shard that owns it. The celebrity problem is the common example. One account, one post that very many people open, one product in a sale, or one match page gets most of the requests.

Why do more shards not help? A key lives on exactly one shard. With 16 shards or 64 shards, the hot key is still on one of them. More shards give more room to the other keys, not to this one. Lesson 44 says the same about the ring: it spreads keys by count and does not look at requests per key. A directory (lesson 43) can put the hot key on a shard of its own, but that one shard still carries the whole key.

How to find a hot key

• Compare the shards. Divide the load of the busiest shard by the average load. A ratio near 1 is healthy. A ratio far above 1 means one shard has too much.
• Count requests per key. Look at 1 request in every 100 and count the keys. The hot key shows up at once.

Fixes when the hot key is mostly read

1. Cache it. Keep the value in a cache (lesson 31) with a short TTL. A cache inside the memory of each app server needs no network trip. With request coalescing (lesson 35), each app server asks the database at most once per TTL.
2. Copy it to followers. Reads of the hot shard go to its followers (lesson 39). The cost is more servers that are always on.
3. Copy the key under several names. Store "post:42#0", "post:42#1" and so on. Each read picks one name at random. With hash sharding, the copies land on different shards, because their names hash to different places. Writes must change every copy.

Fixes when the hot key is mostly written

A cache does not help writes. There are two fixes.

1. Split the key (salting). A salt is a random suffix. A counter "likes:42" becomes 16 counters "likes:42#0" to "likes:42#15". Each write adds to one counter chosen at random. To read the total, read all 16 and add them. The 16 counters spread over many shards. The cost is that a read now asks 16 rows (cache the total for a second to reduce this).
2. Count in memory, write in batches. Each app server counts likes in its own memory and writes the total once per second. This costs a delay of up to one second, and a crash loses the likes that were only in memory.

Why is one row the limit? Writes to one row happen one after another, because an update holds a lock on the row until the transaction ends (lesson 22). If an update holds the lock for 2 ms, one row takes 1,000 / 2 = 500 updates per second at most.

Treat only the hot keys specially

Splitting every key into 16 would make every read 16 times more work. So keep a short list of hot keys. The system adds a key to the list when its requests per second pass a limit, and removes it when it cools down. Only keys on the list are cached, copied or split. The same problem appears when a cache is spread over several servers: the server that holds the hot key is busy. The fix is the same: copies in many places.

SwadKart has a social page, and the posts are in 8 shards (lesson 43). A cricket star posts after the match.

Assumptions (made up to teach with, not real traffic):

• Each shard has 8 cores, which is 8,000 ms per second (lesson 15). We use at most 70% of it, which is 5,600 ms.
• Normal load: 16,000 reads per second, spread evenly. A read costs 2 ms.
• The star's post adds 6,000 reads per second, all for one key.
• There are 20 app servers. A like counter on the post gets 3,000 likes per second. An update holds the row lock for 2 ms.

Step 1: the normal load. 16,000 / 8 = 2,000 reads per shard. 2,000 x 2 ms = 4,000 ms, which is 4,000 / 8,000 = 50%.

Step 2: the hot post. The post needs 6,000 x 2 ms = 12,000 ms per second.

• Hot shard: 4,000 + 12,000 = 16,000 ms. That is 16,000 / 8,000 = 200%.
• The other 7 shards: 50%.
• Whole cluster: 7 x 4,000 + 16,000 = 44,000 ms of 64,000 ms, which is 69% on average.

So the cluster has enough power in total, but one shard is at 200%. The average hides it. The busiest shard divided by the average: 16,000 / 5,500 = 2.9. Sampling 1 read in 100 shows the post at about 60 reads per second. A normal key shows almost nothing.

Step 3: more shards.

• 16 shards: each has 1,000 normal reads = 2,000 ms. Hot shard = 2,000 + 12,000 = 14,000 ms = 175%.
• 64 shards: 250 normal reads = 500 ms. Hot shard = 500 + 12,000 = 12,500 ms = 156%.

The post alone needs 12,000 ms, and a shard has 8,000 ms. No number of shards makes it fit. This answers the predict box: no.

Step 4: cache in each app server. TTL of 2 seconds, with coalescing. Each of the 20 app servers asks the database at most once per 2 seconds: 20 / 2 = 10 reads per second. That costs 10 x 2 = 20 ms. The hot shard now uses 4,000 + 20 = 4,020 ms, which is 50%. The cost: a user can see the post up to 2 seconds old.

Step 5: copies on followers instead. The hot reads need 12,000 ms. At 5,600 ms per server, 12,000 / 5,600 = 2.1, so 3 followers (4,000 ms each, 50%). The cost: 3 more servers that are always on, and the followers can be a little behind (lesson 40).

Step 6: the like counter. One row takes 1,000 / 2 = 500 updates per second. The post gets 3,000 likes per second, which is 3,000 / 500 = 6 times too many. Two fixes:

• Split into 16 counters: 3,000 / 16 = 187.5 updates per counter per second. The lock is busy 187.5 x 2 = 375 ms per second, which is 37.5%.
• Count in memory: 20 app servers each write once per second. That is 20 updates per second on one row, 20 x 2 = 40 ms, which is 4%. Each server holds about 3,000 / 20 = 150 likes in memory at any moment.

• Caching the hot key solves read load. It costs a stale value (up to 2 seconds in the example) and a short list of hot keys to manage.
• Followers solve read load without a list of hot keys. They cost always-on servers (3 in the example), and they can be a little behind.
• Splitting a counter solves write load. It costs a read of 16 rows instead of 1.
• Counting in memory solves write load with the least work (4% of the row lock). It costs a delay of up to 1 second and the likes lost in a crash.
• More shards do not solve a hot key: 175% with 16 shards, 156% with 64.
• I would change it when the hot key must show the newest value every time. Then I would copy the key under several names and update every copy on each write. I would not use a cache with a long TTL.

"The shard is full, so add more shards." A key lives on one shard. In the example the hot shard was at 175% with 16 shards and 156% with 64.

"A good hash or consistent hashing prevents hot keys." They spread keys evenly, not requests. The post was one key, so it went to one shard.

"A cache fixes a hot key." Only for reads. The like counter had 3,000 writes per second, and one row takes 500. Writes need a split key or counting in memory.

1. What is a hot key? Why do more shards not help? Name two fixes for reads and one for writes.
2. A shard has 4 cores (4,000 ms per second). One key gets 3,000 reads per second at 1.5 ms each. (a) How much work does the key need, as a share of the shard? (b) 50 app servers cache the key for 5 seconds with coalescing. How many database reads per second does the key cause now, and how many ms?
3. A counter row gets 2,000 updates per second. Each update holds the row lock for 2 ms. A teammate says "add a cache". What do you say?