Sharding
- Lesson 13 of 40
- 11 min
- Intermediate
- 9 steps
At some point not even the biggest machine can hold your data or keep up with your writes. The way out is to cut them into pieces and spread them. Choosing how to cut is the hard part.
- Shards
- 4
- Writes on the busiest
- 10,000 req/s
- Busiest shard's share
- 25%
- Data per shard
- 5 TB
- request
- response
- slow request
- waiting in queue
- batch
Step 1 of 9
Problem
One machine is no longer enough
The users database holds 20 TB and takes 40,000 writes per second. Read replicas take load off queries, but every write still goes through a single leader, and all the data has to fit on its disks.
You already bought the biggest machine available and it runs at 98%. On top of that, any backup, restore or new replica takes most of a day to copy 20 TB. The figures in this lesson are an example scenario.
Step 2 of 9
Solution
Divide the data: sharding
Sharding cuts one big database into several smaller ones, the shards. Each one stores part of the rows and only takes the writes for that part.
The shard key decides where each row lives. Here we use user_id ranges: 1 to 25 million on A, 25 to 50 million on B, and so on. The app (or a router in front) looks up the range and sends each query to the right shard.
In this example each shard is a more modest machine that handles about 20,000 writes/s: at 10,000 it runs at 50%.
What changed
- 4 shards of 5 TB
- Shard key: user_id ranges
- Writes per shard: 40,000 → 10,000/s
Step 3 of 9
Problem
Ranges create hot spots
user_id values grow over time, so every new signup lands in the last range. And newcomers are the ones who write the most: shard D gets 78% of the writes (31,200/s) while A barely sees 6%.
D cannot keep up and writes start to queue. The same happens with any key that arrives in order: dates, order numbers, names in alphabetical order.
Some range-partitioned databases split an overloaded range in two automatically, but when every write goes to the end, the problem just moves to the last piece.
What changed
- Shard D: 78% of writes
- Shard A: 6%
- Write queue on D
Step 4 of 9
Solution
Run the key through a hash
Instead of ranges, hash the key and keep the remainder of dividing by the number of shards: shard = hash(user_id) % 4.
Consecutive ids give hashes that look nothing alike, so new users and their traffic spread evenly: each shard is back to 10,000 writes/s.
What changed
- Shard key: hash(user_id) % 4
- Busiest shard: 78% → 25%
Step 5 of 9
Problem
Case: the celebrity
Hashing spreads keys, not traffic. A singer with tens of millions of followers is user 42 and lives on shard C like anyone else. But every like on her posts writes to her row.
She alone generates 24,000 writes/s. Add C's 4,000 regular writes and that shard takes 28,000/s (70%) and cannot keep up, while A, B and D sit at 20%. This is called a hot key, or the celebrity problem.
What changed
- User 42: 24,000 writes/s
- Shard C: 70% of writes
Step 6 of 9
Solution
Cache it or split it
If the key is hot because of reads (everyone opens her profile), put a cache in front of the shard: most visits never reach the database.
If it is hot because of writes, like her like counter, split it: each like adds 1 to likes:42#n with n picked at random from 0 to 7. Those 8 sub-keys land on different shards (two per shard here), and reading the total means adding up all 8.
The 24,000 writes/s become 6,000 per shard; with the 4,000 regular ones, each shard is back to about 10,000/s.
What changed
- Hot reads served from a cache
- likes:42 split into 8 sub-keys
- Busiest shard: 70% → 25%
Step 7 of 9
Trade-off
Queries that visit every shard
Finding one user is fast: hash the id and ask a single shard. But «the 10 users with the most followers» is not keyed by user_id: the app has to ask all 4 shards and combine the answers.
These scatter-gather queries take as long as the slowest shard, and joins across shards are hard to get right.
What changed
- One query → all 4 shards
- The answer waits for the slowest
Step 8 of 9
Problem
Adding a shard moves almost everything
The shards fill up and you add a fifth. But hash % 4 becomes hash % 5, and for about 80% of users the remainder changes: their row has to move to another shard.
A key only stays put when its remainder is the same dividing by 4 and by 5: 4 values out of every 20. About 16 TB have to move between shards while the system keeps serving. Once done, each shard holds 4 TB and takes 8,000 writes/s.
What changed
- Shard E
- hash % 4 → hash % 5
- ≈ 80% of rows change shard
Step 9 of 9
Summary
Recap
Sharding spreads data and writes across several machines.
The shard key decides where each row lives and has to spread the load evenly.
Ranges create hot spots; hashing spreads the load but scatters range queries.
A single hot key gets cached (reads) or split into sub-keys (writes).
Queries that do not use the shard key touch every shard; changing N in hash % N moves almost all the data.
← → step · R replay · Space pause
You will learn
- Why replicas do not spread writes (covered)
- Shard keys: ranges or hashes (covered)
- Hot keys: the celebrity problem (covered)
- What a cross-shard query costs (covered)
- Why adding a shard hurts (covered)