Pointer Walk

Sharding and Hot Keys

One shard drowns while the rest sit idle. Why adding servers does not help while one key owns the load.

System DesignIntermediate9 min read

Splitting data across machines

One database can only hold and serve so much. When it is full, the usual answer is sharding: split the data across several databases, called shards, each holding a part.

To find anything again, every key must map to exactly one shard. The standard way is to hash the key and use the result to pick a shard.

python
def shard_for(key, shard_count):
    return hash(key) % shard_count
  1. A request arrives for a key

    For example post:8141.

  2. Hash the key to pick a shard

    The same key always lands on the same shard, so reads find what writes stored.

  3. That shard does the work

    Each shard has its own limit on how many requests it can handle.

The promise of sharding is simple: twice the shards, twice the capacity. That promise depends on one assumption.

When it works

The assumption is that requests are spread evenly over the keys. Then the hash spreads them evenly over the shards.

Here are 6 shards. Each can handle 7 requests per tick and 24 arrive, spread over many keys.

6 shards · even trafficInteractive

Requests arriving at each shard this tick

1
2
3
4
5
6

The dashed line is what a shard can handle. A number above a bar is how many requests are waiting there.

24 requests arrive each tick. Together the 6 shards can handle 42, so there is plenty of room in total.

Requests
0
Each shard handles
7 per tick
Waiting
0

Every shard stays near 4. Nobody is close to the line.

One key gets half the traffic

Real traffic is rarely even. A post goes viral. A celebrity has fifty million followers. One customer is a hundred times bigger than the rest. Suddenly a single key receives a huge share of all requests. This is a hot key.

A key lives on exactly one shard. So everything aimed at that key lands on that one shard.

6 shards · one hot keyInteractive

Requests arriving at each shard this tick

1
2
3
4
5
6

The dashed line is what a shard can handle. A number above a bar is how many requests are waiting there. Pink shard numbers hold the hot key.

24 requests arrive each tick. Together the 6 shards can handle 42, so there is plenty of room in total.

Requests
0
Each shard handles
7 per tick
Waiting
0

The total is unchanged: still 24 requests per tick against room for 42. But one shard receives about 14 and can handle 7. Its queue grows every tick, while the other five do almost nothing.

Adding shards does not help

The natural reaction to an overloaded system is to add machines. Try it: double the shards from 6 to 12.

12 shards · one hot keyInteractive

Requests arriving at each shard this tick

1
2
3
4
5
6
7
8
9
10
11
12

The dashed line is what a shard can handle. A number above a bar is how many requests are waiting there. Pink shard numbers hold the hot key.

24 requests arrive each tick. Together the 12 shards can handle 84, so there is plenty of room in total.

Requests
0
Each shard handles
7 per tick
Waiting
0

Total capacity doubled. The hot shard is just as overloaded as before. The viral post is still one key, one key still lives on one shard, and that shard can still handle only 7.

The fix: split the hot key

If one key is too much for one shard, make it several keys.

  1. Store the hot item under several names

    Instead of post:viral, write it as post:viral#0, post:viral#1, post:viral#2 and post:viral#3.

  2. Each name hashes to a different shard

    They are different text, so they get different hashes.

  3. Readers pick one of the names at random

    Each copy now receives a quarter of the traffic.

python
import random

HOT_KEYS = {"post:viral": 4}          # key -> number of copies

def read(key):
    copies = HOT_KEYS.get(key)
    if copies:
        key = f"{key}#{random.randrange(copies)}"
    return shards[shard_for(key, len(shards))].get(key)

Back on 6 shards, with the hot key split into 4:

6 shards · hot key splitInteractive

Requests arriving at each shard this tick

1
2
3
4
5
6

The dashed line is what a shard can handle. A number above a bar is how many requests are waiting there. Pink shard numbers hold the hot key.

24 requests arrive each tick. Together the 6 shards can handle 42, so there is plenty of room in total.

Requests
0
Each shard handles
7 per tick
Waiting
0

Good at

  • The hot key's load is spread over several shards
  • Only the few hot keys need this treatment

Where it bites

  • Every write to the hot item must update all the copies
  • The app has to know which keys are hot, which means measuring

Other things that help

  • Put a cache in front. Hot keys are usually read far more than written. A cache answers most of those reads before they reach any shard.
  • Give a known giant its own shard. If one customer is permanently huge, route them to dedicated hardware instead of letting the hash decide.
  • Watch for hot keys. Count requests per key and alert when one key takes a large share. A hot shard with idle neighbours is the sign.

Try every combination

6 shards · one hot keyInteractive
Traffic
Shards
Hot key

Requests arriving at each shard this tick

1
2
3
4
5
6

The dashed line is what a shard can handle. A number above a bar is how many requests are waiting there. Pink shard numbers hold the hot key.

24 requests arrive each tick. Together the 6 shards can handle 42, so there is plenty of room in total.

Requests
0
Each shard handles
7 per tick
Waiting
0

Key takeaways

  • Sharding splits data across databases by hashing each key to one shard.
  • It scales well only while requests are spread evenly over the keys.
  • A hot key sends all of its traffic to one shard, however many shards there are.
  • Adding shards does not help: one key still lives in one place.
  • Splitting a hot key into several copies spreads its load. A cache in front helps too.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    7 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress