Notes › System Design
Database Sharding and Replication
A single database server eventually runs out of CPU, RAM, disk or connections. Two tools scale it:
- Replication = copies of the same data on several machines → more reads, high availability.
- Sharding (partitioning) = split the data across machines → more writes and more storage.
The usual order of scaling
- Add indexes and fix slow queries (Indexing, B+ Trees and SQL vs NoSQL).
- Vertical scaling — a bigger machine.
- Caching (Redis) for hot reads.
- Read replicas.
- Sharding — last, because it adds the most complexity.
Replication
Leader–follower (primary–replica)
writes replicate (log)
App ───────────────► Leader ─────────────┬──► Follower 1 ◄── reads
└──► Follower 2 ◄── reads
- All writes go to the leader; it streams changes (the write-ahead log / binlog / oplog) to followers.
- Reads can be spread across followers.
- If the leader dies, a follower is promoted (failover).
- Used by MySQL, PostgreSQL, MongoDB replica sets.
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
- Multi-leader: several leaders (e.g. one per data centre) accept writes → good for multi-region, but write conflicts must be resolved (last-write-wins, merge, CRDTs).
- Leaderless (Dynamo, Cassandra): write to and read from several nodes. With N replicas, W write acks and R read responses, W + R > N guarantees a read sees the latest write (e.g. N=3, W=2, R=2).
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:
- has high cardinality (many distinct values),
- spreads reads and writes evenly,
- matches the most common query so it hits one shard.
For a chat app,
conversation_idkeeps one chat's messages together;user_idsuits a social profile service. A bad key:country(India would overload one shard), orcreated_at(every insert hits the newest shard).
Problems sharding brings
- Cross-shard queries and joins → scatter–gather (slow) or denormalise data.
- Cross-shard transactions → two-phase commit (slow) or the Saga pattern.
- Hot keys (a celebrity's account) → split that key further, cache it.
- Resharding when shards fill up → consistent hashing, or start with many logical shards (e.g. 1024) mapped to fewer physical servers and move logical shards later.
- Global unique IDs → UUIDs, or Snowflake-style IDs (timestamp + machine id + sequence).
- Backups, schema changes and monitoring × number of shards.
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
- Replicate for reads and availability; shard for writes and size.
- Async replication is fast but can lose recent writes and serve stale reads.
- W + R > N gives strong reads in quorum systems.
- The shard key is the most important sharding decision.
- Shard last — after indexes, caching and read replicas.
- Related: CAP Theorem and Consistency, Caching, CDN and Databases at Scale.