Sharding

The problem: one database can't take the writes

Say your app makes about 6,000 writes a second at busy hours, and its database takes about 3,000 writes a second. Adding a read replica doesn't help: every write is made on the leader and then copied to every replica, so the leader still gets all 6,000 a second, twice what it takes. Replicas spread reads, not writes, and each holds all the data, which outgrows one machine's disks.

The fix is sharding: split the rows over several databases, called shards, so each holds part of the data and takes only the writes for its part. With 3 shards, each takes about 6,000 ÷ 3 = 2,000 writes a second, under the 3,000 one can take, and stores a third of the data.

The shard key is the field you split by, such as the user id. The router maps a key to its shard: a small service in front of the shards, or a library in the app servers. A load balancer can't do this job: a write for user 5 must reach the one shard that holds user 5, not any server.

Splitting by range

The simplest rule gives each shard a run of keys, like the volumes of an encyclopedia. With 12 users:

Shard 0: ids 1–3        users 1, 2, 3
Shard 1: ids 4–6        users 4, 5, 6
Shard 2: ids 7 and up   users 7, 8, 9, 10, 11, 12

Ranges keep neighbors together, so a query for a run of keys ("users 4 to 6", or last week's orders keyed by date) goes to one shard. A range that grows too big can be split in two, and many databases do that on their own.

The weak spot is a key that only grows. Ids from a counter, and timestamps, always land in the last range: users 9 to 12 all went to Shard 2, and so will every sign-up after them. That shard takes every new row's write while the others sit idle, and splitting it doesn't help for long: the newest range is always the busy one. Ranges can also be uneven from the start: far more names start with some letters than with others.

Splitting by hash

Hash sharding computes the shard from the key: hash the key to a number, then keep the remainder after dividing by the number of shards. To keep the example easy, let the hash be the id itself, so shard = id mod 3:

shard = id mod 3
Shard 0: users 3, 6, 9, 12
Shard 1: users 1, 4, 7, 10
Shard 2: users 2, 5, 8, 11

Neighboring ids land on different shards, so the shards stay even as ids grow, and any server finds a key's shard with one sum: user 20 is on Shard 2, because 20 = 6 × 3 + 2. Real systems use a proper hash function that scrambles the key, so keys that follow a pattern still spread out. The price: "the users who signed up today" now sit on every shard.

Adding a shard moves most keys

With a fourth shard the rule becomes id mod 4, and every row whose shard changes must be copied over while the app runs. Users 1 to 8:

user id    1     2     3     4     5     6     7     8
id mod 3   1     2     0     1     2     0     1     2
id mod 4   1     2     3     0     1     2     3     0
           stay  stay  move  move  move  move  move  move

Only users 1 and 2 stay put: 6 of the 8, three quarters, move. Going from N shards to N + 1 with mod moves about N/(N + 1) of all keys: 3/4 going from 3 to 4, 9/10 going from 9 to 10. Consistent hashing moves only about 1/(N + 1), the new shard's share. A lookup table of ranges also avoids it, at the price of one more service to depend on.

Hot keys

No split helps a key that gets far more traffic than the rest. Say user 7 is a celebrity and her new post gets about 3,000 likes a second. Every like is a write to her post, which lives on her shard, so Shard 1 takes about 5,000 writes a second while the others take 2,000. Add three more shards and the rule becomes id mod 6, but 7 mod 6 = 1: Shard 1 again. One key always lives on one shard. That's a hot key, and it needs its own plan:

• Cache it: most of her traffic is people opening the post, and the cache answers them from memory.
• Add read replicas to her shard, so the copies share its reads.
• Split the key: keep her like count in 10 keys, 7#0 to 7#9, spread over the shards. Each like adds 1 to one of them, picked at random: about 300 a second per key. Showing the total adds up 10 numbers.

More shards, another split rule or a better hash don't help: each still sends one key to one shard.

Queries across shards

Say posts are sharded by their author's user id, so all of Kim's posts sit on Kim's shard. A query that names the shard key goes to one shard: Kim's profile, Kim's posts newest first. Anything else must ask every shard and merge the answers, a scatter-gather. For "top 10 posts this hour", each shard finds its own top 10 and the router merges them. "Find users named Kim" asks every shard too: users are split by id, not name.

A scatter-gather costs N times the work and is as slow as the slowest shard. Choosing the shard key is choosing which queries stay cheap: pick the key your busiest queries name, and keep data used together (a user and their posts) on the same shard. Joins and transactions across shards get hard, because each shard is its own database.

When not to shard yet

Sharding makes everything after it harder: queries across shards, moving rows, more machines to run. First try an index for the slow query, a cache, read replicas, a bigger machine. Shard when the writes or the data outgrow one database.

Sharding in system design interviews

Sharding comes up in the scaling step, once the numbers show that one database can't take the writes or hold the data. A strong answer names the shard key and why ("posts by the author's user id, hashed, so a user's profile and posts stay on one shard"), how keys find their shard, the plan for hot keys, which queries cross shards, and when you wouldn't shard yet. Avoid the post's time as the key (every new post lands on the newest shard) and a random number (nothing can find a post again).

Common interview questions

What's the difference between sharding and replication?

Replication keeps full copies of the data: it spreads reads and survives a failed machine, but every copy applies every write. Sharding splits the data, so each machine holds and writes only its part. Large systems do both: each shard has its own replicas.

How do you choose a shard key?

List the busiest queries and pick the key they name, so they stay on one shard. It must also spread writes evenly: avoid keys that only grow, like timestamps.

How do you handle a celebrity?

Their key is hot whatever the split. Cache their posts, add read replicas to their shard, and split write-heavy counters into several keys.

Range or hash sharding?

Range when queries ask for runs of keys and the key doesn't only grow; hash when the load must be even and queries look up single keys. Many systems hash the main key and sort by a second one inside each shard: user id, then post time.

Summary

• Sharding: split the rows over databases; a router finds each key's shard.
• Range: neighbors stay together, but a key that only grows piles onto the last shard.
• Hash: keys spread evenly, but with mod a new shard moves most of them.
• Hot keys: cache them, add replicas, split them into several keys.
• The shard key: queries that name it stay on one shard; the rest ask every shard.
• Timing: don't shard before one database really can't keep up.