Database Replication & Sharding
Replication
Copy the same data onto multiple nodes.
Master-slave (primary-replica): writes go to the primary, reads distributed across replicas — increases read throughput and gives a failover target if the primary dies (replicas elect a new primary). The cost: replication lag — replicas can serve stale data for a window after a write, the eventual-consistency trade-off from [[CAP Theorem & Consistency Models]] showing up concretely.
flowchart LR
W[Write] --> P[(Primary)]
P -->|async replicate| R1[(Replica 1)]
P -->|async replicate| R2[(Replica 2)]
Read1[Read] --> R1
Read2[Read] --> R2
Partitioning vs. Sharding — a distinction worth stating precisely
- Horizontal partitioning: split one table into multiple tables within the same database instance. Same schema, disjoint rows, same box.
- Sharding: split data across multiple separate database instances (different machines). Same idea, but each shard is an independently running database — table names can even collide across shards since they're isolated.
Sharding Strategies
| Strategy | Mechanism | Trade-off |
|---|---|---|
| Range-based | Partition by key ranges (userID 0–199 → shard 1, etc.) | Simple, but easily skewed — a popular range creates a hot shard |
| Hash-based | hash(key) → shard. Even distribution | Naive hashing suffers the same remap-storm as simple load-balancer hashing when resharding — mitigate with consistent hashing (see [[Consistent Hashing]]) |
| Directory-based | A lookup table maps each key to its shard explicitly | Most flexible (can rebalance individual keys), but the lookup table itself is a new single point of failure |
Sharding Trade-offs (say these unprompted — this is the actual signal)
Gains: higher availability (one shard down ≠ whole DB down), smaller per-shard indexes → faster queries, higher aggregate read/write throughput, natural security boundary (restrict access per shard).
Costs:
- Cross-shard joins require pulling data over the network and joining in application code — expensive; avoid by picking a shard key that keeps related data together.
- No cross-shard transactions — a transfer between accounts on two different shards can't be atomic the way it would be on one DB.
- Added infra + routing complexity.
- Fixed shard count problem — resharding later is disruptive. Fix: hierarchical sharding (shard the shard itself when one grows too big) or consistent hashing to make resharding incremental instead of a full remap.
Interview Drill
Q: A shard is much hotter than the others under hash-based sharding. What are your options, in order of effort? A: First confirm it's a genuine hot key vs a hot shard (skewed key distribution vs a bad hash function). Mitigate a hot key with request collapsing/local caching (see [[Caching & Redis]]). Mitigate a structurally hot shard with a better key choice or hierarchical sharding. A hash-function issue may need re-hashing with consistent hashing to limit reshuffling cost.
Cross-links
[[CAP Theorem & Consistency Models]] · [[Consistent Hashing]] · [[Single Point of Failure]]