Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Notes › System Design

Database Sharding and Replication

A single database server eventually runs out of CPU, RAM, disk or connections. Two tools scale it:

The usual order of scaling

  1. Add indexes and fix slow queries (Indexing, B+ Trees and SQL vs NoSQL).
  2. Vertical scaling — a bigger machine.
  3. Caching (Redis) for hot reads.
  4. Read replicas.
  5. Sharding — last, because it adds the most complexity.

Replication

Leader–follower (primary–replica)

          writes                 replicate (log)
App ───────────────► Leader ─────────────┬──► Follower 1 ◄── reads
                                         └──► Follower 2 ◄── reads

Synchronous vs asynchronous

Synchronous Asynchronous
Leader confirms the write after followers have it only it has it
Data loss on leader crash none the last few writes may be lost
Write speed slower; a slow follower blocks writes fast
Common compromise: semi-synchronous — wait for at least one follower.

Replication lag problems (async)

Problem Example Fix
Read-your-own-writes you update your profile, refresh, see the old data (read hit a lagging replica) read your own data from the leader for a short time after writing
Monotonic reads refreshing shows newer, then older data stick each user to one replica
Consistent prefix you see an answer before its question keep related writes on one partition

Multi-leader and leaderless

Sharding (horizontal partitioning)

Each shard holds a subset of rows with the same schema. A shard key decides where each row lives.

users with id 1–1M     → shard A
users with id 1M–2M    → shard B
users with id 2M–3M    → shard C

(Vertical partitioning = splitting columns or tables onto different servers, e.g. moving user_photos to its own DB.)

Sharding strategies

Strategy How ✅ ❌
Range key ranges (A–F, G–M…; dates) range queries are easy hot spots (all new rows hit the last shard)
Hash hash(key) % N even spread range queries hit all shards; changing N moves most data
Consistent hashing hash ring + virtual nodes adding a shard moves ~1/N of data more complex
Directory / lookup a table maps key → shard fully flexible the directory is extra load & a failure point
Geo by region / country data near users, legal rules uneven regions

Choosing a shard key

A good shard key:

Problems sharding brings

Replication + sharding together

Real systems do both: every shard is itself a replica set.

Shard A: leader + 2 followers     Shard B: leader + 2 followers     Shard C: …

MongoDB: mongos router + config servers + sharded replica sets. Others: Vitess (MySQL), Citus (PostgreSQL), Cassandra, DynamoDB (automatic).

Quick comparison

Replication Sharding
Data on each node all a part
Scales reads reads and writes, storage
Helps availability ✅ not by itself
Complexity low–medium high

Interview one-liners

More System Design notes