Sharding and partitioning in system design

1. What sharding is

Sharding (horizontal partitioning) divides the rows or items of a data set into disjoint groups, called shards or partitions, and places each group on a different node. A routing step maps each key to its shard, so a request for one key goes to one machine. Every shard is usually also replicated, so a node failure loses no data. The difficulty is everything that does not fit one key: queries across many keys, transactions across shards, and moving data when the number of shards changes.

2. Why interviewers ask about it

Any prompt with large numbers eventually reaches the point where one database is not enough, and the interviewer wants to see how you split it. A good answer derives the need from the estimates, picks a shard key from the access pattern, and anticipates hot spots. A weak answer says "we shard the database" without a key, which leaves every hard question unanswered.

3. Partitioning, replication, and whether to shard at all

Sharding adds lasting complexity, so rule out the alternatives first: a larger machine, read replicas for read-heavy load, a cache for the hot set, archiving cold data, and moving unrelated tables into separate databases (functional partitioning). Shard when the estimates show one of these:

• Writes exceed one primary. Replicas do not help, because every replica still applies every write.
• The data outgrows one machine, or backups and restores of it take longer than you can tolerate.
• The working set no longer fits in memory and adding RAM to one server has stopped being practical.

For example, the URL shortener estimate reaches about 183 billion mappings and 90 TB over five years. That is a clear case. A service with 50 GB of data and 500 writes a second is not.

4. How keys map to shards

Going from 4 to 5 shards with shard = hash mod N:
  a key stays put only if hash mod 4 == hash mod 5
  in every 20 consecutive hash values, only 4 satisfy that (0, 1, 2, 3)
  so 80% of keys move

Going from 4 to 5 nodes with consistent hashing (even load):
  the new node takes over about 1/5 of the key space
  so about 20% of keys move, all of them to the new node

Consistent hashing places nodes and keys on the same hash ring; each key belongs to the first node clockwise from it. Adding or removing a node only affects the keys between it and its neighbor. With a single point per node the ring is uneven, so each physical node gets many points, called virtual nodes, often on the order of a hundred or more. Virtual nodes even out the load, let a more powerful machine take more points, and spread a failed node's keys across many survivors instead of dumping them on one neighbor.

A common practical alternative is a fixed number of logical partitions, far more than there are nodes. A key's partition never changes; rebalancing moves whole partitions between nodes. Redis Cluster, for instance, uses 16,384 hash slots. This gives the same small movement as consistent hashing with simpler bookkeeping, at the cost of choosing the partition count up front.

5. Choosing a shard key, and hot partitions

• High cardinality: many distinct values, so the data can spread across many shards. Country code is a poor key; user ID is a good one.
• Even load, not just even data: a key whose values are equally common but unequally busy still creates hot shards.
• Matches the main query: the dominant request should carry the key so it touches one shard.
• Keeps together what changes together: data updated in one transaction should share a shard.

Hot partitions and the celebrity problem. Even a good key has outliers: one account with tens of millions of followers, one viral post, one enormous customer. Partitioning by user ID puts all of that traffic on one shard. Remedies, roughly in order of effort:

• Cache and replicate the hot data so reads are spread over caches and replicas rather than one leader.
• Split the hot key. Write to post:9#0 to post:9#9 at random and sum or merge the ten on read. Use it only for keys known to be hot, because every read now touches ten entries.
• Treat outliers differently in the design, as feed systems do by not fanning out posts from very large accounts. See design Twitter.
• Isolate a huge tenant on its own shard, which a directory scheme makes straightforward.

6. Resharding, cross-shard work and secondary indexes

1. 1Prefer moving partitions to changing the schemeWith many logical partitions or virtual nodes, adding capacity means copying some partitions to the new node, catching up on changes, then switching ownership in the shard map.
2. 2For a new key or scheme, dual-writeWrite to both the old and new layout, backfill historical data into the new one, and compare reads from both (shadow reads) until they agree.
3. 3Switch reads, then stop old writesMove reads to the new layout behind a flag you can turn back, then stop writing the old one and remove it.
4. 4Throttle the copyMoving data competes with live traffic. Rate-limit it and avoid peak hours, and keep routing correct during the move, for example by redirecting requests for a partition in transit.

Cross-shard queries use scatter-gather: send the query to every shard and merge the results. Latency is set by the slowest shard, and that compounds: if each shard is slow 1% of the time, a query touching 100 shards meets at least one slow shard about 63% of the time (1 - 0.99^100 ≈ 0.63). Avoid scatter-gather on hot paths by choosing a key that matches the query, or by keeping a second copy of the data partitioned another way.

Cross-shard transactions. Two-phase commit makes a change on several shards atomic, but participants hold locks while they wait, and a coordinator failure at the wrong moment leaves them blocked. Distributed SQL systems run two-phase commit over consensus-replicated shards to reduce that risk, at a latency cost. Many designs avoid the problem: keep data that changes together on one shard, or use a saga, a series of local transactions with compensating steps if a later one fails, accepting that intermediate states are visible. The payment system walk-through covers this trade-off.

7. How it shows up in common prompts

8. Mistakes to avoid

• Sharding too early. If the numbers fit one primary with replicas, say so; it is a strength, not a gap.
• No shard key. "Shard the database" without a key and a reason is not an answer.
• hash mod N with no plan for growth. Say how you add shards without moving most of the data.
• Timestamps or auto-increment IDs as range keys. Every new write lands on one shard.
• Ignoring the second query. The main query hits one shard; check what the others cost.
• Cross-shard transactions on the hot path. Redesign the key or use a saga.
• Forgetting replication. Shards without replicas turn one disk failure into lost data.

9. How to talk about it in the interview

• Justify sharding with the estimate that forces it.
• Name the key, the scheme and the query it serves in one sentence.
• Say what crosses shards and how you handle it.
• Mention hot keys and how you would add capacity before you are asked.

Practicing with Natively

Sharding answers fall apart on the second follow-up, so rehearse past the first. In a mock interview, Natively transcribes the conversation live and can suggest talking points for each question as it comes in; comparing them with what you said is a quick way to spot gaps such as hot partitions or how you would reshard. It can explain a screenshot you capture of a partitioning diagram or a problem statement. Afterwards the transcript and notes are kept for review, so you can see whether you named a shard key and defended it.