Databases, Replication and Sharding

7 pages · ~5 min✓ Reviewed

Builds on Caching. Next up: Queues and Async Processing.

System DesignPage 1

Replication and Partitioning Mental Model

1. Two Different Tools

	Replication	Partitioning
Data	Same data copied on many nodes	Different slice on each node
Scales	Reads, availability	Writes, storage

Real systems combine both: every partition is replicated
So one node holds several partitions' replicas

2. What Each One Fixes

	Fixes	Does NOT fix
Replication	Read throughput, fault tolerance	Data or write rate beyond one machine
Partitioning	Dataset size, write throughput	Cross-partition joins, transactions, global secondary indexes

3. Pick by Bottleneck

Ask first

Name the bottleneck before naming a technique. Replicas never fix a write or size limit.

System DesignPage 2

Leader-Follower Replication

1. How Writes Flow

Client writeleader only
Leaderappends WAL / binlog
Log shippedto every follower
Followersapply in order

Followers apply the log in order, so they match the leader

2. Sync, Async, Semi-sync

	Ack when	Win	Risk
Sync	follower confirms	no data loss	one slow follower blocks writes
Async	leader commits	fast	acked writes lost on leader crash
Semi-sync	one sync follower, rest async	always one up-to-date copy	extra latency of one follower

3. Failover

1Detectleader dead (timeout)
2Electmost up-to-date follower
3Repointclients to new leader
4Rejoinold leader as follower

Lost async writes
Split brain: two nodes think they are leader
Timeout too low: needless failovers

Pick the freshest

Promote the most up-to-date follower to lose the fewest async writes.

System DesignPage 3

Read Replicas and Replication Lag

1. Replicas and Lag

Replicas serve SELECT only; writes go to the leader
Split reads and writes in a proxy or in app code
Replication lag = delay from leader commit to follower visibility
Async replicas give eventual consistency

App
Proxyread/write split
Leaderwrites
ReplicasSELECTs

2. Lag Anomalies

Anomaly	Symptom	Fix
Read-your-writes	Post, then read: nothing (lagging replica)	Read own recent writes from leader, or pin to a caught-up replica
Monotonic reads	Reads hit different replicas: time goes backward	Pin user to one replica

3. Monitor and Fall Back

sql

SELECT application_name, replay_lag
FROM pg_stat_replication;  -- Postgres
SHOW REPLICA STATUS;  -- MySQL: Seconds_Behind_Source

lag metrics to watch

Alert when lag crosses a threshold
Lag over threshold: fall back to the leader for reads

Remember

Replicas scale reads, not consistency. Async lag means stale reads, so pin users or read from the leader.

System DesignPage 4

Multi-Leader Replication

1. What and Why

Many nodes accept writes and replicate to each other
Used for multi-datacenter, offline-capable clients, collaborative editing
Benefit: local-latency writes per region; survives a datacenter outage
Cost: write conflicts

2. Write Conflicts

Leader Asets x=1
Leader Bsets x=2
Replicateeach to the other
Conflictsame key, two values

Avoid: route all writes for a record to one leader
Last-write-wins: simple, but silently drops data
Merge values or use CRDTs
Custom app logic on read or write

3. Three Models Compared

	Writes go to	Trade-off
Single leader	one leader	no conflicts, one write bottleneck
Multi-leader	a leader per region	regional writes, conflicts
Leaderless (Dynamo)	any replica	quorum: W + R > N

LWW loses writes

Last-write-wins raises no error: one of two concurrent writes just vanishes.

System DesignPage 5

Partitioning, Sharding and Consistent Hashing

1. Range vs Hash

	Range	Hash mod N
Layout	Contiguous key ranges	`hash(key) mod N`
Good	Fast range scans	Even load
Bad	Timestamps make a hot partition	No range queries; new N remaps almost every key

2. Consistent Hashing

1Ringnodes and keys hashed onto it
2Keywalks clockwise
3Ownernext node it meets

Add or remove a node: only about 1/N of keys move
Virtual nodes smooth uneven distribution
Use it instead of hash mod N when node count changes

3. Directory and Hot Keys

Directory sharding: a mapping table sends keys to shards
Flexible rebalancing, but the lookup service must stay available

Remember

hash mod N breaks when N changes. Use consistent hashing with virtual nodes.

System DesignPage 6

Replication and Sharding Cheat Sheet

1. Pick the Tool

Bottleneck	Pick
Reads	Add read replicas
Writes or data size	Shard (partition)
Multi-region writes	Multi-leader or leaderless, with conflict handling

2. Sync Modes and Lag

Mode	Acks after	Trade-off
Sync	follower confirms	durable, slow
Async	leader commits	fast, acked writes can be lost
Semi-sync	one sync follower	compromise

Read-your-writes: read own recent writes from the leader
Monotonic reads: pin a user to one replica

3. Shard Keys and Rings

High cardinality
Even distribution
Matches the main query pattern

Monotonic keys (timestamps) with range sharding: hot partition
hash mod N when node count changes: remaps almost every key

Use consistent hashing plus virtual nodes: adding a node moves ~1/N of keys
Hot keys: salting (key#0..key#k) or caching

Replicas do not scale writes

Replication fixes reads and failover only. If writes or data size outgrow one machine, shard.

System DesignPage 7

Check yourself

Async replication. The leader acks a write, then crashes before shipping it. A follower is promoted. Is the write there?

No: the write is lost, though the client was told it succeeded
Sync or semi-sync replication keeps one up-to-date copy

A user posts a comment, reloads, and it is missing. Another reload shows it. Name the anomaly and the fix.

Read-your-writes violation: the read hit a lagging replica
Read a user's own recent writes from the leader

Shards use hash(key) mod 4. You add a fifth node. Roughly what share of keys move?

About 80%: only keys with the same remainder mod 4 and mod 5 stay
Consistent hashing moves only about 1/N

One celebrity's key overloads its shard. Does adding shards help?

No: hashing sends one key to one shard
Salt the key (key#0..k) and merge on read, or cache it