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.
def shard_for(key, shard_count):
return hash(key) % shard_countA request arrives for a key
For example
post:8141.Hash the key to pick a shard
The same key always lands on the same shard, so reads find what writes stored.
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.
Requests arriving at each shard this tick
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.
Requests arriving at each shard this tick
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.
Requests arriving at each shard this tick
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.
Store the hot item under several names
Instead of
post:viral, write it aspost:viral#0,post:viral#1,post:viral#2andpost:viral#3.Each name hashes to a different shard
They are different text, so they get different hashes.
Readers pick one of the names at random
Each copy now receives a quarter of the traffic.
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:
Requests arriving at each shard this tick
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
Requests arriving at each shard this tick
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.