Chapter 5: Replication
4 min readCore Concepts
Why Replication?
- High availability: Keep system running when nodes fail
- Latency: Serve users from geographically close replicas
- Read scalability: Distribute read load across replicas
- Fault tolerance: Survive node failures
Challenges
- Keeping copies consistent
- Handling concurrent writes
- Conflict resolution
- Replication lag
Leader-Based Replication
How It Works
- Leader receives all write requests
- Leader writes to local storage
- Leader sends change to followers (replication log)
- Followers apply changes in same order
- Clients read from any node (leader or followers)
Synchronous vs Asynchronous Replication
| Aspect | Synchronous | Asynchronous |
|---|---|---|
| Data loss risk | None (after write confirmed) | Possible |
| Performance | Slower (wait for follower) | Faster |
| Availability | Lower (follower failure blocks writes) | Higher |
| Consistency | Strong | Eventual |
Semi-Synchronous: One synchronous follower + async followers (compromise)
| Your priority | Best approach |
|---|---|
| Zero data loss, must be strongly consistent | Synchronous (or semi-synchronous with 1 sync follower) |
| High write throughput, can tolerate some data loss | Asynchronous |
| Geographically distributed users | Multi-leader (one leader per region) or Leaderless with CRDTs |
| Offline/mobile clients | Leaderless (Dynamo-style) with eventual consistency |
| Simple operations, tight budget | Leader-based — most databases support this out of the box |
| Complex conflict resolution needed | Multi-leader with application-level conflict handlers or CRDTs |
Setting Up New Followers
Steps:
- Take consistent snapshot of leader
- Copy snapshot to new follower
- Leader sends changes since snapshot
- Follower processes log of changes
Handling Node Failures
Follower Failure:
- Catch up via replication log
- Reconnect and resume
Leader Failure:
- Failover: Promote follower to leader
- Determine leader is dead
- Choose new leader
- Reconfigure system to use new leader
Failover Risks:
- Lost writes (async replication)
- Split brain (two leaders)
- Wrong timeout settings
Replication Logs
Implementations:
-
Statement-based: Send SQL statements
- Problems: Non-deterministic functions, order-dependent operations
-
Write-ahead log (WAL) shipping: Send log pages
- Tightly coupled to storage engine
-
Logical (row-based) log: Send row changes
- Decoupled from storage format
- Easier to parse
-
Trigger-based: Custom logic
- More flexible but complex
Multi-Leader Replication
Use Cases
- Multi-datacenter operation: Write locally, replicate globally
- Offline clients: Mobile apps that need to work offline
- Collaborative editing: Multiple users editing simultaneously
Conflict Resolution
Last Write Wins (LWW):
- Simple but loses data
- Requires synchronized clocks
Custom Conflict Resolution:
- Application-specific logic
- Convergent: Must reach same state
Conflict-Free Replicated Data Types (CRDTs):
- Data structures that automatically resolve conflicts
- Mathematically guaranteed to converge
Topologies
Star: One leader in center Ring: Each leader replicates to next All-to-All: Every leader replicates to all others
Problem: Circular dependencies in topologies Solution: Version vectors to track causality
Leaderless Replication
Concept
- No special leader node
- Clients write to multiple replicas
- Read from multiple replicas
Quorum Reads/Writes
Formula:
- W = write quorum (replicas that must acknowledge)
- R = read quorum (replicas that must respond)
- N = total replicas
- W + R > N → Consistent read (overlap)
Example: N=3, W=2, R=2
Sloppy Quorums and Hinted Handoff
Problem: Network partition may prevent reaching quorum
Solution: Sloppy quorum
- Accept writes from any available nodes
- "Hinted handoff": Forward to correct node when available
Read Repair and Anti-Entropy
Read Repair:
- Detect stale values during read
- Return most recent value
- Repair other replicas in background
Anti-Entropy:
- Background process compares replicas
- Sync missing data
- Use Merkle trees for efficiency
Replication Lag Problems
Reading Your Own Writes
Problem: Write to leader, read from follower, data not yet replicated
Solutions:
- Read from leader for recent writes
- Monitor replication lag, wait if needed
- Track write timestamps
- Use monotonic reads
Monotonic Reads
Problem: Read from different replicas, see data go backward
Solution: Stick to same replica per user/session
Consistent Prefix Reads
Problem: See data in wrong order due to replication lag
Solution: Guarantee writes in same order appear in same order
Key Takeaways
- Leader-based replication is most common, with trade-offs between sync/async
- Multi-leader replication adds complexity but enables offline/multi-datacenter
- Leaderless replication provides high availability but requires quorum logic
- Replication lag causes consistency problems that need careful handling
- Conflict resolution is a fundamental challenge in multi-leader systems