Sharding and Partitioning
Split data across machines by range, hash or directory, pick a shard key, handle hot keys and cross-shard queries, and add shards without downtime.
On this page
A chat app stores 20 billion messages of about 400 bytes each: 20 × 109 × 400 B = 8 TB. At peak it writes 30,000 messages a second. Replicas do not help here: each replica holds all 8 TB and applies all 30,000 writes. Each machine needs a smaller share of the work.
Sharding gives each machine a slice. With 8 shards, each holds about 1 TB and takes about 30,000 ÷ 8 ≈ 3,750 writes a second.
The idea
A shard (or partition) is a subset of the rows, stored on its own machine. A shard key, one column such as chat_id, decides which shard each row lives on. A query that includes the shard key goes to one shard. A query that does not must ask all of them.
Sharding and replication combine: each shard is usually a small leader-follower group. Sharding splits the work; replication protects each piece.
The cost: joins and transactions across shards become hard, every query must think about the shard key, and moving data is a project. Shard when one machine cannot hold the data or take the writes, not before.
Three ways to map keys to shards
| Option | Good at | Bad at | Pick it when |
|---|---|---|---|
| Range | Keys next to each other live together, so range scans ("names A to F", "March orders") hit one or two shards. | Sequential keys pile up on the last shard: every new timestamp or auto-increment id writes to the same place. | Range queries matter and keys arrive spread out (usernames, not timestamps). |
| Hash Usual default | Spreads keys and load evenly, even sequential ones. | Range scans must ask every shard. A plain hash mod N moves most keys when N changes. | Lookups by key. The usual default, with many fixed partitions or consistent hashing. |
| Directory | A lookup table says where each key (or tenant) lives, so you can place and move anything individually. | The directory is on every request's path: it must be fast, cached and highly available. | Multi-tenant systems where big customers get their own shard. |
Why not hash(key) mod 8? Going from 8 to 9 shards, a key stays put only if its hash gives the same remainder for 8 and 9, which happens for 8 values in every 72. So 64 ÷ 72 ≈ 89% of the data moves. Two fixes: consistent hashing, or many fixed partitions. With the second, hash keys into 1,024 partitions once and for all, and give each shard 128 of them. A new shard takes whole partitions from the others, and only about 1 ÷ 9 ≈ 11% of the data moves.
Choosing the shard key
The checklist (worked through for a booking system in data modeling):
- The hottest queries include it. "Latest 50 messages in chat 8813" names the chat, so
chat_idputs the whole query on one shard. - Things that change together share it. A transaction inside one shard is ordinary; one across shards is not.
- Many distinct values, spread evenly.
countryhas a few hundred values and a handful of giants, so it makes a few huge shards.
For chat, shard by chat_id. A user's inbox, which lists chats across many shards, is a second table sharded by user_id and updated alongside each message (usually asynchronously).
Hot keys
A good key still has outliers. One group chat with 50,000 members may take 2,000 messages a second during an event, all on one shard. If that is a real requirement, split the key: write to chat:8813#0 to chat:8813#9 chosen at random, so each sub-key gets 200 a second, and have reads gather the 10 sub-keys and merge by time. Do it only for keys you know are hot, because every read of them now costs 10 lookups.
Cross-shard queries
A query without the shard key is sent to every shard and the answers are merged (scatter-gather). It is as slow as the slowest shard. If each shard is slow 1% of the time, a query that asks all 8 is slow 1 − 0.998 ≈ 7.7% of the time, and with 100 shards 1 − 0.99100 ≈ 63%. Keep such queries rare, or give them their own copy of the data sharded by the field they use, or a search index.
Adding a shard without downtime
The cluster has 8 shards and 1,024 partitions. Writes are growing, so a ninth shard joins and takes about 14 partitions from each of the 8. Step through one partition moving.
- p37 owner
- shard 1
1A message for chat 8813 arrives. Its hash falls in partition 37, and the router's cached map says partition 37 is on shard 1.
- p37 owner
- shard 1
2Shard 9 joins, empty. Nothing points at it yet, so traffic is unaffected.
- p37 owner
- shard 1
3Shard 1 streams a snapshot of partition 37 to shard 9, while it keeps serving reads and writes for it.
- p37 owner
- shard 1
4If shard 9 died now, nothing would be lost: shard 1 still owns partition 37. Retry the copy.
- p37 owner
- shard 1
5In the normal case the snapshot finishes. Writes made during the copy are then replayed from shard 1's change log until shard 9 is a few milliseconds behind.
- p37 owner
- shard 9
6Shard 1 pauses writes to partition 37 for well under a second, ships the last changes, and the map is updated: partition 37 now lives on shard 9.
- p37 owner
- shard 9
7A router with an old cached map still sends chat 8813 to shard 1. Shard 1 answers "moved", and the router refreshes its map and retries.
- p37 owner
- shard 9
- data moved
- ≈ 11%
8Messages for chat 8813 now go to shard 9. Shard 1 deletes its copy later. Repeat for about 112 partitions in total and shard 9 carries its ninth of the load.
Numbers worth remembering
- Plan shards for both limits: data per machine (often kept to about 1 TB or less so rebuilds and moves are quick) and writes per machine (thousands a second for a typical relational primary; a rough rule of thumb).
- Choose far more partitions than machines (hundreds to thousands), so growth moves whole partitions.
- Scatter-gather tail: 1 − 0.99n of queries hit a slow shard; 8 shards ≈ 8%, 100 shards ≈ 63%.
How many shards does the chat store need today?
- 20 billion messages, about 400 bytes each
- Keep each shard to about 1 TB
- 30,000 writes a second at peak; one shard comfortably takes 5,000
Show the working
- Storage: 20 × 109 × 400 B = 8 TB → 8 shards of 1 TB
- Writes: 30,000 ÷ 5,000 = 6 shards
- Take the larger: 8 shards (plus replicas for each)
Estimate 8 (anything from 4 to 20 is a good answer)
Whichever limit needs more shards decides. Here storage decides with no headroom, so start with more; the 1,024 partitions make that cheap.
In the interview
Bring up sharding when your estimate says one machine cannot hold the data or take the writes. Name the shard key, the query it serves, the query it hurts, and how you handle hot keys and growth.
8 TB and 30,000 writes a second. How do you store messages?
Shard by chat_id, hashed into 1,024 partitions spread over 8 shards. Loading a chat, the hottest query, hits one shard. The cost is that "all messages from user X" fans out to every shard, so the inbox gets its own table sharded by user_id.
One chat goes viral. Now what?
Its partition runs hot. If one chat can really take thousands of messages a second, I'd split that chat's key into 10 sub-keys for writes and merge them on read. I'd only do it for chats we flag as huge.
Follow-ups you should expect:
- "How do you keep a username unique across shards?" Shard the usernames table by username, so the uniqueness check is one shard.
- "How do you reshard?" Move whole partitions: copy, catch up from the change log, briefly pause, switch the map, as in the tracer.
- "Why not shard from day one?" Cross-shard pain is permanent. If the numbers fit one primary with replicas, that is simpler.
Common mistakes
Orders are range-sharded by created_at. What goes wrong?
A query asks all 20 shards. Each is slow 1% of the time, independently. About how often is the query slow?
A ride app shards trips by driver_id. Which query is cheapest?
What to practise next
The other way to place keys so that adding a node moves little is consistent hashing, next. Sharding by conversation is central to Design a Chat App.