Chapter 12: Database Replication

12.1 Why Replicate?

Replication serves multiple critical purposes in distributed systems:

Replication vs. Backup

12.2 Single-Leader Replication (Master-Slave)

The most common replication architecture. One node is the leader (master, primary); all writes go to it. Other nodes are followers (slaves, replicas, secondaries); they receive updates from the leader.

12.2.1 Synchronous vs. Asynchronous Replication

Synchronous Replication

Pros:

• Follower guaranteed to have up-to-date copy (durable)
• Failover to synchronous follower = zero data loss
• Strong consistency for reads from synchronous follower

Cons:

• Write latency increases (wait for follower ACK)
• If synchronous follower unavailable, writes block (or fail)
• Not scalable: adding followers doesn't help write latency

Asynchronous Replication

Pros:

• Low write latency (leader doesn't wait)
• Writes succeed even if all followers are down
• Scales well: can add many followers without impacting writes

Cons:

• Replication lag: followers may be seconds/minutes behind
• If leader fails, recent writes may be lost (not yet replicated)
• Reading from follower may return stale data

Semi-Synchronous (Hybrid)

Practical compromise: one follower is synchronous, others are asynchronous. If the synchronous follower becomes unavailable, another async follower is promoted to synchronous.

12.2.2 Replication Lag Problems

Asynchronous replication introduces eventual consistency: replicas will become consistent eventually, but there's a window where they're stale. This causes three classic problems:

Problem 1: Reading Your Own Writes

Solution: Read-After-Write Consistency

• Route user's reads to leader for data they may have modified (e.g., always read own profile from leader)
• Track last update timestamp: if user modified within last N seconds, read from leader
• Monotonic read token: include timestamp in response; client sends it back; route to replica that's caught up to that timestamp
• Sticky sessions: route all requests from a user to the same replica (less effective if user switches devices)

Problem 2: Monotonic Reads Violation

Solution: Monotonic Reads

• Sticky sessions: always route a user to the same replica
• Session affinity: hash user ID to consistent replica
• Replica lag tracking: client tracks max timestamp seen; only query replicas caught up to that timestamp

Problem 3: Consistent Prefix Reads Violation

Solution: Consistent Prefix Reads

• Write causally related data to same partition: conversation messages go to same shard (keyed by conversation ID)
• Version vectors / Lamport timestamps: track causality; only show writes that include all causal dependencies
• Read from leader for causal chains (expensive but guarantees ordering)

12.3 Replication Log Implementation

How does the leader transmit changes to followers? Four main approaches:

12.3.1 Statement-Based Replication

Leader logs every write statement (INSERT, UPDATE, DELETE) and sends it to followers.

-- Leader executes and logs:
UPDATE accounts SET balance = balance + 100 WHERE id = 42;

-- Followers replay the same statement

Problems:

• Non-deterministic functions: NOW(), RAND(), auto-incrementing columns produce different values on each replica
• Side effects: triggers, stored procedures may behave differently
• Execution order matters: UPDATE ... LIMIT 10 without ORDER BY is non-deterministic

Workarounds:

• Leader calculates NOW(), RAND() and includes fixed values in log
• Disallow non-deterministic functions in replicated statements
• Use row-based replication instead

12.3.2 Write-Ahead Log (WAL) Shipping

Database writes all changes to an append-only WAL before applying them. Leader sends raw WAL to followers.

-- WAL entry (low-level format):
Page 5, Offset 100: 0x4A3F... (binary data representing row)

Pros:

• Exact copy of leader's storage (byte-for-byte replication)
• Used by PostgreSQL, Oracle, SQL Server

Cons:

• Tightly coupled to storage engine: WAL format changes between database versions
• Zero-downtime upgrades impossible: can't run leader v10.1 with follower v10.2 (WAL incompatible)
• No cross-platform replication (can't replicate from Linux to Windows if byte order differs)

12.3.3 Logical (Row-Based) Replication

Leader logs changes at row level in a storage-engine-independent format.

-- Logical log entry (human-readable representation):
INSERT INTO users (id, name, email) VALUES (123, 'Alice', 'alice@ex.com');
UPDATE users SET email = 'alice2@ex.com' WHERE id = 123;
DELETE FROM users WHERE id = 456;

Pros:

• Decoupled from storage engine: can upgrade leader/follower independently
• Cross-database replication: MySQL → PostgreSQL, database → data warehouse
• External consumers: other systems (cache, search index, CDC) can parse log

Cons:

• Slightly more overhead than WAL (higher-level representation)

Examples: MySQL binlog (row-based mode), PostgreSQL logical decoding, MongoDB oplog

12.3.4 Trigger-Based Replication

Use database triggers to capture changes and write them to a separate table (replication log). Custom application reads log and replicates.

-- PostgreSQL example:
CREATE TRIGGER replicate_users
AFTER INSERT OR UPDATE OR DELETE ON users
FOR EACH ROW EXECUTE FUNCTION log_change();

Pros:

• Highly flexible: can filter, transform, or route data differently per table
• Selective replication: replicate subset of columns or rows (e.g., only active users)
• Cross-database: application handles replication logic

Cons:

• Performance overhead: triggers run on every write
• Bug-prone: application code handles replication (easy to introduce bugs)
• Complexity: conflicts, retries, failure modes handled by application

12.4 Multi-Leader Replication (Master-Master)

Multiple leaders can accept writes. Each leader replicates changes to all other leaders and their followers.

12.4.1 Use Cases

Multi-Datacenter Operation

Offline Clients (CRDTs, Mobile Apps)

Each device (laptop, phone) acts as a leader. When online, syncs with other "leaders" (other devices, server).

Examples: CouchDB, PouchDB, Google Docs (Operational Transformation), Figma, Git

Collaborative Editing

Google Docs, Figma: each user's browser is a "leader" making local edits, broadcasting to other users.

12.4.2 Conflict Detection and Resolution

Multi-leader's biggest challenge: write conflicts.

Conflict Avoidance (Best Strategy)

Design application so conflicts can't happen:

• Route user's writes to same leader: user ID → consistent datacenter (home datacenter)
• Partition data: each leader owns disjoint set of records (user 1-1000 → DC1, 1001-2000 → DC2)
• Single-leader per record: document has designated "master" datacenter

Conflict Resolution Strategies

1. Last-Write-Wins (LWW)

// Each write gets a timestamp (or unique ID)
Write 1: { title: "Final v1", timestamp: 1620000001000 }
Write 2: { title: "Final v2", timestamp: 1620000002000 }

// Keep write with highest timestamp
Result: "Final v2" wins

Pros: Simple, deterministic, eventual convergence

Cons: Data loss - discards one write entirely (users lose their changes)

2. Merge / Application-Level Resolution

// Conflict detected:
Version A: { tags: ['urgent', 'bug'] }
Version B: { tags: ['urgent', 'security'] }

// Application-level merge: union of tags
Result: { tags: ['urgent', 'bug', 'security'] }

Pros: No data loss, domain-specific logic

Cons: Requires custom code per data type

3. Prompt User to Resolve

Git-style: show both versions, ask user to pick.

Title:
<<<<<<< Leader US
Final v1
=======
Final v2
>>>>>>> Leader EU

Pros: Correct resolution (human decides)

Cons: Poor UX (interrupts workflow), not automatic

4. Keep All Versions (Siblings)

Store both conflicting values; application reads all siblings and decides.

// Riak, CouchDB approach:
GET /document/123
{
  "siblings": [
    { "title": "Final v1", "version": "abc123" },
    { "title": "Final v2", "version": "def456" }
  ]
}

Pros: No data loss, application has full context

Cons: Complexity pushed to application (every read must handle siblings)

5. CRDTs (Conflict-Free Replicated Data Types)

Data structures designed to merge automatically and deterministically.

Example: OR-Set (Add/Remove without conflicts)

// Replica 1: Add "apple" with unique ID
ORSet.add("apple", id=uuid1)

// Replica 2: Concurrently remove "apple" (different ID)
ORSet.remove("apple", id=uuid2)

// Merge: Add wins (uuid1 still in set, uuid2 not present to remove)

12.4.3 Replication Topologies

Infinite Loop Prevention

Tag each write with unique ID and originating leader. Replicas ignore writes they've already seen.

// Write originates at Leader 1
Write { id: uuid1, leader: 1, data: "value" }

// Leader 2 receives it, tags with leader=1, replicates to Leader 3
// Leader 3 receives it, sees leader=1, replicates to Leader 1
// Leader 1 receives it, sees own ID (leader=1), IGNORES (no loop)

12.4.4 Multi-Leader Trade-offs

12.5 Leaderless Replication

No designated leader. Clients write to multiple replicas in parallel. Popularized by Amazon Dynamo (2007), used by Cassandra, Riak, Voldemort.

12.5.1 Quorum Reads and Writes

Key parameters:

• N = number of replicas
• W = write quorum (number of replicas that must ACK a write)
• R = read quorum (number of replicas to query on read)

Quorum Condition: W + R > N

Guarantees: if W + R > N, at least one replica in the read quorum has the latest value.

Common Quorum Configurations

12.5.2 Handling Stale Replicas

Read Repair

Client reads from R replicas, detects version mismatch, writes latest version back to stale replicas.

// Client reads R=3 replicas:
R1: x=10, version=v5
R2: x=10, version=v5
R3: x=8,  version=v4  (stale!)

// Client detects R3 is stale, sends repair write:
Client → R3: Write(x=10, version=v5)

Pros: Low overhead (only repairs on read), works for frequently read data

Cons: Rarely read data stays stale indefinitely

Anti-Entropy Process

Background process continuously compares replicas and repairs differences.

// Anti-entropy daemon compares Merkle trees:
Replica 1 Merkle Root: 0xABCD1234
Replica 2 Merkle Root: 0xABCD1234
Replica 3 Merkle Root: 0xDEADBEEF  (mismatch!)

// Narrow down to specific keys and repair

Merkle Trees: Hash tree of data. Comparing roots quickly identifies mismatched ranges.

Pros: Repairs rarely-read data, comprehensive

Cons: High overhead (continuously comparing), repair lag (runs periodically)

12.5.3 Sloppy Quorums and Hinted Handoff

Problem: Network partition or replica failure → can't reach W replicas → write fails.

Sloppy Quorum: Allow writes to succeed by including nodes outside the "home" replica set.

Hinted Handoff: Temporary replica (R4) stores a "hint" that data belongs to R3. When R3 recovers, R4 hands off the data.

Pros: Increased write availability (writes succeed during failures)

Cons: No durability guarantee (W replicas ACKed, but not the "home" replicas; if temp replica fails, data lost)

12.5.4 Detecting Concurrent Writes

Two clients write to same key concurrently (no coordination). How to detect conflicts?

Version Vectors (Dotted Version Vectors)

Each replica tracks version number per client/replica. Captures causal relationships.

// Initial state: x=0, version={}

// Client A writes x=1:
Replica 1: x=1, version={A:1}
Replica 2: x=1, version={A:1}

// Client B writes x=2 (concurrent, hasn't seen A's write):
Replica 3: x=2, version={B:1}

// Replica 1 receives B's write:
// Versions {A:1} and {B:1} are concurrent (neither dominates)
// Store both as siblings: [{x=1, {A:1}}, {x=2, {B:1}}]

// Client C reads, sees siblings, merges, writes x=3:
Replica 1: x=3, version={A:1, B:1, C:1}

Domination: Version {A:2, B:1} dominates {A:1, B:1} (A advanced, B same or advanced).

Concurrent: {A:1, B:0} and {A:0, B:1} neither dominates (different clients advanced).

12.5.5 Leaderless Trade-offs

12.6 Replication Lag & Solutions (Revisited)

Replication lag is the time delta between leader's write and follower's update. In asynchronous replication, lag can range from milliseconds to minutes.

12.6.1 Read-After-Write Consistency

Guarantee: user sees their own writes immediately (no lag for own data).

Implementation Strategies

12.6.2 Monotonic Reads

Guarantee: user never sees data "go backward" (if read X, subsequent reads see X or newer).

Implementation: Hash user ID to consistent replica (session affinity).

12.6.3 Consistent Prefix Reads

Guarantee: if writes happened in order A → B → C, reads see them in that order (not B, A, C).

Problem: Partitioned/sharded databases replicate independently; shard 1 may lag differently than shard 2.

Solutions:

• Colocate causally related data: write conversation messages to same partition (keyed by conversation_id)
• Version vectors / Lamport clocks: track causality; only show writes that include all causal predecessors
• Global ordering: single leader for causal chains (sacrifices partition tolerance)

12.7 Failover

Failover is the process of promoting a follower to leader when the current leader fails.

12.7.1 Failover Process

Step 1: Detect Leader Failure

No foolproof way to detect failure (network partition vs. crashed node look identical).

Timeout Trade-off:

• Short timeout (e.g., 5s): Fast failover, but many false positives (unnecessary failovers)
• Long timeout (e.g., 60s): Fewer false positives, but longer downtime during real failures

Step 2: Elect New Leader

Step 3: Reconfigure Clients and Replicas

All clients and followers must learn about the new leader.

Configuration Service: Centralized registry (ZooKeeper, etcd, Consul) storing current leader. Clients query it to discover leader.

12.7.2 Failure Modes and Problems

Problem 1: Split-Brain

Old leader recovers, believes it's still the leader. Now two leaders accept writes → data divergence.

Solution: Fencing Tokens

Each leader gets a monotonically increasing epoch number (or generation ID). Storage rejects writes from leaders with stale epoch numbers.

// New leader elected with epoch=5
NewLeader: Write(x=10, epoch=5)
Storage: Accept (epoch=5 is highest seen)

// Old leader recovers, still has epoch=4
OldLeader: Write(x=20, epoch=4)
Storage: Reject (epoch=4 < current epoch=5)

// Old leader queries config service, learns it's demoted
OldLeader: Step down, become follower

Problem 2: Data Loss During Failover

If old leader had asynchronous followers, recent writes may not have replicated. New leader is missing those writes.

// Leader receives write:
Leader: Write(x=100) at time T0

// Leader crashes at T0 + 1ms (before replicating to followers)

// Follower promoted to leader:
NewLeader: Latest value: x=50 (old value)

// x=100 is lost forever

Solutions:

• Synchronous replication: Wait for at least one follower to ACK before responding to client (trade-off: higher latency)
• Semi-synchronous: One follower synchronous, others async (MySQL semi-sync)
• Accept data loss: Document RPO (Recovery Point Objective) - "we may lose last N seconds of writes" (often acceptable for non-critical systems)

Problem 3: False Positive Failover

Leader is actually fine, but network partition prevents followers from reaching it. Followers elect new leader → now two leaders (split-brain).

Solution: Quorum-Based Failure Detection

Require majority of nodes to agree leader is down before triggering failover.

// 5-node cluster: Leader, Follower1, Follower2, Follower3, Follower4

// Network partition: Followers 1 & 2 can't reach Leader
Follower1: Leader timeout!
Follower2: Leader timeout!

// Followers 3 & 4 can still reach Leader
Follower3: Leader is fine
Follower4: Leader is fine

// Vote: 2/5 say down, 2/5 say up
// No majority → NO FAILOVER (avoid false positive)

12.7.3 Automatic vs. Manual Failover

12.8 Conflict Resolution Deep Dive

12.8.1 Operational Transformation (OT)

Used by Google Docs, Etherpad. Transform concurrent operations so they can be applied in any order and converge to same result.

Example: Collaborative Text Editing

// Initial document: "Hello"

// User A: Insert "!" at position 5
Operation A: Insert("!", 5)  →  "Hello!"

// User B: (concurrent) Delete character at position 0
Operation B: Delete(0)  →  "ello"

// Problem: Applying in different orders gives different results:
// A then B: "Hello!" → "ello!"  (delete "H")
// B then A: "ello" → "ello!"     (delete "H", insert "!")
// SAME RESULT ✓

// But what if B's operation is at position 5?
// User A: Insert("!", 5)  →  "Hello!"
// User B: Insert("?", 5)  →  "Hello?"

// Applying A then B:
// "Hello" → "Hello!" → "Hello?!"  (B's position transformed to 6)

// Applying B then A:
// "Hello" → "Hello?" → "Hello?!"  (A's position transformed to 6)

// Transform function:
// Transform(Insert("!", 5), Insert("?", 5)):
//   If concurrent inserts at same position, use tie-breaker (user ID)
//   User A < User B → A's insert goes first → B's position becomes 6

OT Challenges:

• Complex transform functions (must handle all operation pairs)
• Requires central server to sequence operations (doesn't work peer-to-peer)
• Bug-prone (subtle edge cases in transform logic)

12.8.2 CRDTs (Conflict-Free Replicated Data Types)

Data structures designed to merge automatically without conflicts. Two variants:

State-Based CRDTs (Convergent)

Replicas send full state; merge function is commutative, associative, idempotent.

// G-Counter (Grow-only counter)
type GCounter = map[replicaID]int

// Increment on replica 1:
replica1 = {1: 5, 2: 3, 3: 2}  (replica 1 incremented 5 times)

// Increment on replica 2:
replica2 = {1: 5, 2: 4, 3: 2}  (replica 2 incremented once)

// Merge: element-wise max
merge(replica1, replica2) = {1: max(5,5), 2: max(3,4), 3: max(2,2)}
                          = {1: 5, 2: 4, 3: 2}

// Total count: sum(5 + 4 + 2) = 11

Operation-Based CRDTs (Commutative)

Replicas send operations; operations are commutative (order doesn't matter).

// OR-Set (Observed-Remove Set)
type ORSet = {
  adds: set of (element, uniqueID)
  removes: set of uniqueID
}

// Replica 1: Add "apple"
adds: {("apple", uuid1)}
removes: {}

// Replica 2: (concurrent) Remove "apple"
// But Replica 2 doesn't know about uuid1 (hasn't synced yet)
// Can't remove what it hasn't observed → remove is no-op

// After sync, Replica 2 sees ("apple", uuid1), can now remove it
removes: {uuid1}

// Merge: "apple" is in set if any add UUID not in removes
Result: "apple" is in set (uuid1 in adds, not in removes)

CRDT Examples

12.8.3 Application-Level Conflict Resolution

Custom logic in application code to resolve conflicts.

Example: Shopping Cart Merge

// User adds item on phone (offline):
CartPhone: ["Laptop", "Mouse"]

// User adds item on laptop (offline):
CartLaptop: ["Laptop", "Keyboard"]

// Sync: Detect conflict (both modified cart)

// Resolution: Union merge (keep all items)
CartMerged: ["Laptop", "Mouse", "Keyboard"]

// With quantities (more complex):
CartPhone: [{"Laptop": 1}, {"Mouse": 2}]
CartLaptop: [{"Laptop": 1}, {"Keyboard": 1}]

// Resolution: Sum quantities for same item
CartMerged: [{"Laptop": 2}, {"Mouse": 2}, {"Keyboard": 1}]

Example: Calendar Event Merge

// User edits event on phone: title="Meeting with Alice", time=2pm
// User edits event on laptop: title="Meeting", location="Room 101"

// Conflict: Both edited same event

// Resolution: Field-level merge (keep latest per field)
// Title: "Meeting with Alice" (phone edited after laptop)
// Time: 2pm (phone edited)
// Location: "Room 101" (laptop edited)

// Result: {title: "Meeting with Alice", time: 2pm, location: "Room 101"}

12.8.4 Conflict-Free by Design

Architect system to avoid conflicts entirely.

12.9 Change Data Capture (CDC)

Change Data Capture: capture database changes (inserts, updates, deletes) as a stream of events. Enables derived data systems (caches, search indexes, analytics) to stay in sync.

12.9.1 CDC Approaches

Log-Based CDC (Best Practice)

Parse database's replication log (WAL, binlog, oplog).

-- PostgreSQL WAL entry:
BEGIN;
INSERT INTO users (id, name, email) VALUES (123, 'Alice', 'alice@ex.com');
COMMIT;

-- Debezium captures and emits to Kafka:
{
  "before": null,
  "after": {"id": 123, "name": "Alice", "email": "alice@ex.com"},
  "op": "c",  // create
  "ts_ms": 1620000000000
}

Pros:

• Low overhead (replication log already exists)
• Captures all changes (no application changes needed)
• Ordered (log preserves order)

Cons:

• Database-specific (MySQL binlog ≠ PostgreSQL WAL)
• Schema changes require careful handling

Trigger-Based CDC

Database triggers write changes to a separate "changelog" table.

-- Trigger on users table:
CREATE TRIGGER cdc_users
AFTER INSERT OR UPDATE OR DELETE ON users
FOR EACH ROW EXECUTE FUNCTION log_change();

-- Changelog table:
CREATE TABLE changelog (
  id SERIAL PRIMARY KEY,
  table_name TEXT,
  operation TEXT,  -- INSERT, UPDATE, DELETE
  old_data JSONB,
  new_data JSONB,
  timestamp TIMESTAMP
);

Pros:

• Database-agnostic (works with any DB supporting triggers)
• Can add custom logic (filtering, transformation)

Cons:

• High overhead (triggers run on every write)
• Complex to maintain (triggers per table)

Application-Level CDC

Application writes to DB and emits change event.

// Application code:
function createUser(user) {
  db.insert('users', user);
  kafka.emit('user.created', user);  // Dual write
}

Pros:

• Full control (application decides what to emit)

Cons:

• Dual-write problem: DB write succeeds but Kafka emit fails (or vice versa) → inconsistency
• Requires application changes for every table

12.9.2 Outbox Pattern

Solve dual-write problem: write to DB and "outbox" table in same transaction. CDC reads outbox and emits to Kafka.

-- Outbox table:
CREATE TABLE outbox (
  id SERIAL PRIMARY KEY,
  aggregate_type TEXT,  -- 'user', 'order', etc.
  aggregate_id TEXT,
  event_type TEXT,      -- 'created', 'updated', 'deleted'
  payload JSONB,
  created_at TIMESTAMP
);

-- Application writes:
BEGIN;
INSERT INTO users (id, name) VALUES (123, 'Alice');
INSERT INTO outbox (aggregate_type, aggregate_id, event_type, payload)
VALUES ('user', '123', 'created', '{"name": "Alice"}');
COMMIT;

-- CDC process polls outbox and emits to Kafka

Pros:

• Atomicity (DB + event emission guaranteed together)
• No dual-write problem

Cons:

• Slight latency (CDC polls outbox)
• Outbox table grows (needs cleanup of processed events)

12.9.3 CDC Tools

12.9.4 CDC Use Cases

12.10 Replication in Real Systems

12.10.1 PostgreSQL Streaming Replication

Single-leader, asynchronous (or synchronous) replication using WAL shipping.

-- Primary server (leader):
wal_level = replica
max_wal_senders = 5

-- Standby server (follower):
primary_conninfo = 'host=primary-db port=5432'
hot_standby = on  (allow reads on standby)

-- Synchronous replication (wait for one standby):
synchronous_standby_names = 'standby1'
synchronous_commit = on

12.10.2 MySQL Group Replication

Multi-leader replication with consensus-based conflict resolution (Paxos-based).

-- Group Replication plugin:
INSTALL PLUGIN group_replication SONAME 'group_replication.so';

-- Configure group:
SET GLOBAL group_replication_bootstrap_group=ON;
START GROUP_REPLICATION;

-- Multi-primary mode: all nodes accept writes
group_replication_single_primary_mode = OFF

12.10.3 MongoDB Replica Sets

Single-leader replication with automatic failover (Raft-like election).

// Initialize replica set:
rs.initiate({
  _id: "myReplicaSet",
  members: [
    { _id: 0, host: "mongo1:27017" },
    { _id: 1, host: "mongo2:27017" },
    { _id: 2, host: "mongo3:27017" }
  ]
})

// Read preference (route reads to secondaries):
db.collection.find().readPref("secondary")

12.10.4 Cassandra (Leaderless)

Leaderless replication with tunable consistency (quorum-based).

-- Write with consistency level QUORUM (W = (N+1)/2):
INSERT INTO users (id, name) VALUES (123, 'Alice');
  USING CONSISTENCY QUORUM;

-- Read with consistency level QUORUM (R = (N+1)/2):
SELECT * FROM users WHERE id = 123;
  USING CONSISTENCY QUORUM;

-- Eventual consistency (fast, no guarantee):
USING CONSISTENCY ONE;

12.10.5 CockroachDB (Raft-per-Range)

Distributed SQL with Raft consensus per data range (shard). Strong consistency by default.

-- Raft replication automatically managed:
CREATE TABLE users (id INT PRIMARY KEY, name TEXT);

-- Each range (64MB by default) is a Raft group:
-- Range 1: keys 0-1000 → Raft group (nodes 1, 2, 3)
-- Range 2: keys 1001-2000 → Raft group (nodes 2, 3, 4)

-- Reads/writes go through Raft leader for that range
INSERT INTO users (id, name) VALUES (123, 'Alice');
-- Leader for range containing id=123 replicates via Raft

12.10.6 Comparison Table

12.11 Summary