Chapter 5: Replication

Core 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

1. Leader receives all write requests
2. Leader writes to local storage
3. Leader sends change to followers (replication log)
4. Followers apply changes in same order
5. Clients read from any node (leader or followers)

Synchronous vs Asynchronous Replication

Semi-Synchronous: One synchronous follower + async followers (compromise)

Setting Up New Followers

Steps:

1. Take consistent snapshot of leader
2. Copy snapshot to new follower
3. Leader sends changes since snapshot
4. 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
  1. Determine leader is dead
  2. Choose new leader
  3. Reconfigure system to use new leader

Failover Risks:

• Lost writes (async replication)
• Split brain (two leaders)
• Wrong timeout settings

Replication Logs

Implementations:

1. Statement-based: Send SQL statements

   • Problems: Non-deterministic functions, order-dependent operations

2. Write-ahead log (WAL) shipping: Send log pages

   • Tightly coupled to storage engine

3. Logical (row-based) log: Send row changes

   • Decoupled from storage format
   • Easier to parse

4. 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:

1. Read from leader for recent writes
2. Monitor replication lag, wait if needed
3. Track write timestamps
4. 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

1. Leader-based replication is most common, with trade-offs between sync/async
2. Multi-leader replication adds complexity but enables offline/multi-datacenter
3. Leaderless replication provides high availability but requires quorum logic
4. Replication lag causes consistency problems that need careful handling
5. Conflict resolution is a fundamental challenge in multi-leader systems