Sharding and CAP

Intuition: one archive can't keep up anymore

Picture a town records office where every resident's card is kept in one cabinet, looked after by one clerk. With a thousand residents, everything's fine. With a million, there's a line out the door and the cabinet won't close. The fix is obvious: set up several cabinets, each with its own clerk, and hang a sign at the entrance: "A–H go to the first, I–P to the second, Q–Z to the third."

That's sharding. We split the data into pieces (shards) and spread them across different servers. Each shard stores only its share of the data and handles only its share of the load.

When one database isn't enough

First you try the cheap fixes: indexes, caching, read replicas. Sharding makes sense when you hit a limit on writes or volume. Replicas won't help there: every replica still receives all the writes and stores all the data.

Parameter	What the system needs	What one node can handle	Conclusion
Writes per second	50,000	~10,000	at least 5 shards
Data volume	20 TB	~2–4 TB comfortably	5–10 shards
With 2× headroom for growth	—	—	~10–16 shards

Say it out loud in the interview: "Replicas scale reads; shards scale writes and volume." That one sentence shows right away that you understand the difference.

What the system looks like

The router knows the shard map: which key range lives on which server. The router can be a library in your code, a separate proxy (Vitess, mongos), or the distributed database itself (Cassandra, CockroachDB).

Three ways to split the data

Approach	How it works	Pros	Cons
By range	user_id 1–1M → shard 1, 1M–2M → shard 2	convenient range queries	new keys all hit the last shard
By hash	hash(key) % N	even distribution	changing N moves almost everything
Consistent hashing	keys and nodes sit on a ring; a key goes to the nearest node clockwise	adding a node moves ~1/N of the data	more complex, needs virtual nodes

The shard key is the most important decision. A good key spreads the load evenly and is present in almost every query. For a messenger, chat_id works well: all of a chat's messages end up on one shard.

Resharding: why % N hurts

You had 3 shards, and now you have 4. With hash % N, a key stays put only if h % 3 == h % 4. That's about 25% of keys; the other ~75% of the data moves. That's gigabytes of traffic and hours of degraded service.

Consistent hashing solves this: a new node joins the ring and takes some keys only from its neighbor. About 1/4 of the data moves instead of 3/4. To keep nodes from getting unequal slices of the ring, each physical server is placed on the ring 100–200 times. Those are virtual nodes.

Hot shards

Even with a perfect hash, you can get a hot key: a celebrity's account or a product from an ad campaign. All of its traffic goes to one shard. What you can do:

• a cache in front of the shard for hot reads;
• salt the key: celebrity_id#0..9 spreads writes over 10 shards, though you then have to gather them back up on read;
• move the hot key to a dedicated shard.

CAP in plain words

In a distributed system, the network between nodes will break sooner or later. That's P (partition), a network partition. You can't avoid it. While the link is down, the system has two options:

• C (consistency): refuse the request, but never return stale data. That's CP: a bank account, seat reservations.
• A (availability): answer even if the data might be stale. That's AP: likes, a feed, a shopping cart.

So CAP isn't "pick 2 out of 3"; it's "during a partition, pick C or A."

PACELC completes the picture: if Partition — A or C, Else — Latency or Consistency. Even when the network is healthy, you have to choose. You can wait for confirmation from every replica and get consistency at the cost of latency. Or you can answer right away and get speed at the cost of possible divergence.

System	During a partition	Normally
Cassandra, DynamoDB	A	L (configurable)
Spanner, CockroachDB	C	C
PostgreSQL + async replica	—	L

Eventual consistency

Eventual consistency means that if writes stop, all replicas will eventually converge to the same value. Usually that takes milliseconds or seconds. You like a post, your friend sees it a second later, and nobody gets hurt.

To keep users from getting confused, there are a few techniques:

• read-your-writes: you read your own changes from the leader;
• quorums: W + R > N (for example, N=3, W=2, R=2) gives you a fresh read.

What it sounds like in an interview

"Writes are bottlenecked on a single node: 50k RPS against a ceiling of about 10k. Replicas won't help here, so I'll shard by user_id using consistent hashing with virtual nodes. That way adding a shard moves roughly 1/N of the data. For hot keys I add a cache and salting. Eventual consistency is fine for the feed, so that's AP. Payments stay in a CP store."

Be sure to name the trade-offs: cross-shard JOINs and transactions get expensive, global queries turn into scatter-gather, and the whole design hinges on choosing a good key.

Common mistakes

• Sharding right away without trying indexes, caching, and replicas.
• Picking a key that's missing from most queries: then every query fans out to every shard.
• Saying "a CA system." There's no such thing as a distributed system without P.
• Using hash % N and forgetting about resharding.
• Not mentioning hot shards. The interviewer will almost certainly ask about them.

You've just worked through a topic that trips up a lot of candidates. Say the sample answer out loud a couple of times, and it'll be yours.