What it is
Sharding means splitting your data across several machines so each one only holds part of it. You reach for it when one machine can't keep up, even after you've added replicas and caches.
How it works
A shard key decides where each row goes. Plain modulo hashing works fine until the number of servers changes, and then nearly every key has to move. Consistent hashing fixes that.
In practice, each server shows up at lots of spots on the ring. These are called virtual nodes. They spread data out more evenly and share the load when a server goes away.
Trade-offs
| Split by | Good | Bad |
|---|---|---|
| Hash | Data spreads out evenly | Range queries have to hit every shard |
| Range | Range queries are fast | New data can all land on one shard |
| Region or customer | Related data stays together | A huge region or customer can overload a shard |
In an interview
- Use rough numbers to show why one machine won't cut it.
- Pick a shard key that fits your most common query.
- Call out your busiest key, like one huge city, and say what you'd do about it.
Worked example
Sharding a chat app's messages
A chat app stores 2 billion messages a day, and each message is about 500 bytes. That's around 1 TB a day, and reads are almost always 'the latest messages in this conversation'.
- One database can't hold years of this, and the write rate is around 25,000 a second on average with peaks much higher. So you shard.
- Shard by conversation ID. Every message in a conversation lives on one shard, so loading a conversation is a single query on a single machine.
- Sharding by user would split a group chat across many shards. Sharding by time would send all of today's writes to one shard. Conversation ID avoids both.
- Use consistent hashing so adding a shard only moves a slice of conversations, not most of them.
- A huge group chat with 100,000 members is a hot conversation. You might give it its own shard, or split its messages by time within it.
- 'Search all my messages' now has to ask every shard. That goes to a separate search index, built from the message stream.
Follow-up questions
Things interviewers tend to ask once you've brought this up.
- How do you add a shard without downtime?
- Copy the data that's moving to the new shard while the old one keeps serving, catch up on recent writes, then switch over. Consistent hashing or many small virtual shards keep the amount you move small.
- What about a query that doesn't include the shard key?
- Either send it to every shard and merge the results, which is slow, or keep a second index keyed the other way.
- How do you do a transaction across two shards?
- Try to design so you don't need one. If you must, use two-phase commit, which is slow and fragile, or a saga: a series of local steps with undo steps if something fails.
- How is sharding different from replication?
- Replication copies the same data to more machines, which helps reads and survives failures. Sharding splits data so each machine has less, which helps writes and storage. Most big systems do both.
Common mistakes
- Sharding before showing one machine isn't enough.
- Picking a key that sends all new writes to one shard, like a timestamp.
- Ignoring hot keys, like one celebrity or one city.
- Using modulo hashing and not mentioning what happens when shards are added.
- Forgetting queries that don't include the shard key.