Database Replication

Chapter 1: Leaders and Followers

The simplest and most common replication strategy: designate one replica as the leader (also called primary or master). All writes go through the leader. The other replicas are followers (also called read replicas, secondaries, or slaves). They receive a stream of changes from the leader and apply them in the same order.

This is not a theoretical construct. It's how PostgreSQL, MySQL, MongoDB, SQL Server, Oracle, and most relational databases work by default. It's also how some message brokers (Kafka, RabbitMQ) and some non-relational databases (RethinkDB, Espresso) work.

Think of it like a newsroom. The editor-in-chief (leader) decides what goes into the newspaper. Correspondents (followers) receive the final copy and distribute it in their regions. Nobody else writes the headlines — that power is centralized. This makes coordination simple but creates a bottleneck at the top.

Synchronous vs. Asynchronous

When a client sends a write to the leader, the leader has a choice: does it wait for followers to confirm they received the change before telling the client "write succeeded"?

Synchronous replication: The leader waits until at least one follower confirms it has written the data to disk. Only then does the leader report success to the client. Advantage: the follower is guaranteed to have an up-to-date copy. If the leader dies, you know the follower has everything. Disadvantage: if the follower is slow or down, the write is blocked. One laggy follower can stall your entire write path.

Asynchronous replication: The leader writes locally and immediately tells the client "success." The change is sent to followers in the background. Advantage: writes are fast — the leader never blocks. Disadvantage: if the leader dies before the change reaches any follower, that write is permanently lost. The client got a "success" acknowledgment for data that no longer exists.

Setting Up a New Follower

You can't just copy the leader's data files while it's running — the data is constantly in flux, and you'd get a corrupted half-written snapshot. Here's the correct procedure:

Worked Example: Tracing a Write

Let's trace a single write through a leader-follower cluster with 1 leader and 2 followers, semi-synchronous replication.

The Replication Lag Equation

How much data could we lose in a leader failure? With asynchronous replication, the answer depends on replication lag — the delay between a write hitting the leader and that write being applied on the follower.

Hands-on: Setting Up Replication in PostgreSQL

Here's what the actual configuration looks like. These are the key parameters in postgresql.conf on the leader and recovery configuration on the follower:

bash
# === On the LEADER (primary) ===
# postgresql.conf
wal_level = replica              # Enable replication-grade WAL
max_wal_senders = 5             # Max concurrent replication connections
synchronous_standby_names = 'first 1 (follower1, follower2)'
                                 # Semi-sync: wait for 1 of these

# pg_hba.conf (authentication for replication)
host replication repl_user 10.0.0.0/8 md5

# === On the FOLLOWER ===
# Create base backup from leader:
pg_basebackup -h leader-host -U repl_user -D /var/lib/pgsql/data -P

# standby.signal (tells PG this is a follower)
# Just create an empty file:
touch /var/lib/pgsql/data/standby.signal

# postgresql.conf on follower
primary_conninfo = 'host=leader-host user=repl_user password=secret'
hot_standby = on                 # Allow read queries on follower

sql
-- Monitor replication lag (run on leader):
SELECT client_addr,
       state,
       sent_lsn,
       write_lsn,
       flush_lsn,
       replay_lsn,
       (sent_lsn - replay_lsn) AS replication_lag_bytes
FROM pg_stat_replication;

-- Example output:
--  client_addr  | state     | sent_lsn    | replay_lsn  | lag_bytes
--  10.0.1.2     | streaming | 0/16B3A40   | 0/16B3A40   | 0        (caught up)
--  10.0.1.3     | streaming | 0/16B3A40   | 0/16B2F20   | 2848     (2.8 KB behind)

Read Scaling: The Math Behind Adding Followers

Adding read replicas has diminishing returns. Here's why:

Chapter 2: Handling Node Outages

Nodes go down. Hardware fails, kernels panic, power grids hiccup, network cables get unplugged by overzealous cleaning crews. The entire point of replication is to keep the system running despite individual node failures. But the details of how you handle failure determine whether you get a smooth failover or a data-loss catastrophe.

Follower Failure: Catch-Up Recovery

A follower crashes and restarts. This is the easy case. The follower knows the last transaction it processed (recorded in its local log). It connects to the leader and requests all changes since that position. It applies them sequentially until it catches up. Then it resumes processing the live stream. No data loss. No downtime for the rest of the cluster. This "just works" in every major database.

Leader Failure: Failover

The leader crashes. This is the hard case. The system needs to:

What Can Go Wrong During Failover

Failover is one of the most dangerous operations in a database cluster. Here's a catalog of disasters:

Lost writes. If the old leader had accepted writes that weren't yet replicated to any follower (because replication was asynchronous), those writes are permanently lost when the new leader takes over. When the old leader comes back, it has writes that conflict with the new leader's history. Common resolution: discard the old leader's unreplicated writes. This violates the client's durability expectation — they got "OK" for writes that vanished.

Split brain. Both the old leader and the new leader think they're the leader. Both accept writes. Now you have two diverging histories of the same data. Merging them is often impossible without data loss. Prevention: use a fencing mechanism — when a new leader is elected, the old leader is forcibly shut down (via STONITH: "Shoot The Other Node In The Head") before the new leader starts accepting writes.

Autoincrement conflicts. The old leader assigned autoincrement IDs 1001-1005 to writes that weren't replicated. The new leader starts assigning IDs from 1001. Now you have two different rows with ID 1001. If a downstream system (like a Redis cache or a search index) processes both, it will overwrite one with the other.

Stale reads during failover. During the detection window (while the system is deciding whether the leader is actually dead), clients may be reading from followers that are serving increasingly stale data. If the detection timeout is 30 seconds, reads could be 30+ seconds stale before the failover even begins.

Cascading failures. The leader goes down because of high load (not hardware failure). The remaining followers suddenly get more read traffic (clients that were reading from the leader are redistributed). The increased load on followers causes them to slow down their WAL replay, increasing replication lag. If you then promote a lagging follower, you lose even more data. Meanwhile, the new leader is also under heavy load and might itself become unresponsive.

Designing a Safe Failover System

Here's what a production-grade failover system needs:

python
# Failover decision pseudocode (based on Patroni's approach)

def should_failover(leader_last_seen, followers):
    # 1. Don't failover too quickly (avoid false positives)
    if time.time() - leader_last_seen < DETECTION_TIMEOUT:
        return False, None

    # 2. Don't failover if we can't reach the DCS (split brain risk)
    if not can_reach_distributed_consensus_store():
        return False, None

    # 3. Find eligible candidates
    candidates = []
    for f in followers:
        lag = f.replication_lag_bytes()
        if lag <= MAX_LAG_FOR_FAILOVER:
            candidates.append((f, lag))

    if not candidates:
        alert("CRITICAL: No follower eligible for promotion!")
        return False, None

    # 4. Pick the most up-to-date candidate
    best = min(candidates, key=lambda x: x[1])
    return True, best[0]

def execute_failover(old_leader, new_leader, all_followers):
    # 1. FENCE the old leader (STONITH)
    # This is CRITICAL — must happen BEFORE promotion
    fence_node(old_leader)  # Power off, revoke network, etc.

    # 2. Wait for new leader to finish replaying its pending WAL
    new_leader.wait_for_replay_complete()

    # 3. Promote
    new_leader.promote()

    # 4. Reconfigure remaining followers
    for f in all_followers:
        if f != new_leader:
            f.follow(new_leader)

    # 5. Update DNS / service discovery / proxy config
    update_write_endpoint(new_leader.address)

    # 6. Verify
    assert new_leader.is_accepting_writes()
    log("Failover complete")

Worked Example: The Failover Timeline

Let's trace a real-world failover step by step. The cluster has Leader L, Follower F1 (1 second behind), and Follower F2 (3 seconds behind). Leader L crashes at t=0.

Those 10 lost writes are the price of asynchronous replication. If you need zero data loss, you must use synchronous replication — but then your write latency includes the round-trip to at least one follower, and a follower failure can block writes entirely.

Failover in Production: How Long Does It Take?

Chapter 3: Replication Logs

The leader needs to tell followers what changed. But how does it describe the change? This seemingly simple question has four distinct answers, each with different trade-offs. The choice of replication log format determines what you can and can't do with your replicas.

Method 1: Statement-Based Replication

The leader logs the actual SQL statement and sends it to followers. The follower re-executes the same statement.

Simple and intuitive. But broken in subtle ways:

MySQL used statement-based replication before version 5.1. It worked by replacing NOW() with a fixed timestamp value in the replicated statement. But the edge cases were endless, and MySQL eventually switched to row-based replication as the default.

Method 2: Write-Ahead Log (WAL) Shipping

Every write to a database first goes to an append-only log on disk before it modifies the actual data structures (B-trees, pages). This is the Write-Ahead Log — it ensures durability even if the process crashes mid-write. WAL shipping sends this raw log to followers.

The follower replays the same low-level disk operations. This is exactly what PostgreSQL streaming replication does.

Advantage: Byte-for-byte identical replicas. No ambiguity.

Disadvantage: The WAL is tightly coupled to the storage engine's internal format. If the leader runs PostgreSQL 15 and uses a specific B-tree page layout, the follower must run the exact same version. You cannot do a rolling upgrade (run the new version on followers first, then failover) because the new version's WAL format might be incompatible. This makes zero-downtime upgrades painful.

Method 3: Logical (Row-Based) Log Replication

Instead of the raw bytes, send a logical description of what changed at the row level:

This is what MySQL's binlog uses in row-based mode. It's also what PostgreSQL's logical replication (pgoutput) uses.

Advantage: Decoupled from storage engine internals. The leader and follower can run different versions, different storage engines, or even different database systems entirely. This is how you build change data capture (CDC) — streaming database changes to a data warehouse, search index, or cache.

Disadvantage: Slightly more data to transmit (row values vs. raw page diffs). But network bandwidth is rarely the bottleneck.

Method 4: Trigger-Based Replication

Database triggers fire custom application code when data changes. You can use triggers to write change records to a separate table, which an external process reads and applies to other databases.

Tools like Oracle GoldenGate and Bucardo use this approach. It's the most flexible — you can filter, transform, or route changes with arbitrary logic. But it's also the slowest (trigger overhead on every write) and most error-prone (your replication logic is application code that can have bugs).

Worked Example: Same Operation, Four Representations

Consider this simple operation on a table with schema users(id INT PK, name TEXT, email TEXT, updated_at TIMESTAMP):

Change Data Capture: Why Logical Logs Won

The logical (row-based) log has become the industry standard for modern data architectures because it enables Change Data Capture (CDC) — streaming every database change as an event to downstream systems.

python
# Reading PostgreSQL logical replication stream with psycopg2
# This is what tools like Debezium do internally
import psycopg2
from psycopg2.extras import LogicalReplicationConnection

conn = psycopg2.connect(
    "host=leader dbname=mydb",
    connection_factory=LogicalReplicationConnection
)
cur = conn.cursor()

# Create a replication slot (persistent position tracker)
cur.create_replication_slot('my_cdc_slot', output_plugin='pgoutput')

# Start consuming changes
cur.start_replication(
    slot_name='my_cdc_slot',
    options={'publication_names': 'my_publication'}
)

def consume(msg):
    # msg.payload contains the logical change record
    # Parse it and send to Elasticsearch, Kafka, data warehouse, etc.
    print(f"Change at LSN {msg.data_start}: {msg.payload}")
    msg.cursor.send_feedback(flush_lsn=msg.data_start)

cur.consume_stream(consume)

Chapter 4: Replication Lag Problems

Leader-follower replication works great for read-heavy workloads: send reads to followers, writes to the leader, and scale out your read capacity by adding followers. But followers are always at least slightly behind the leader. This delay is replication lag.

If you stop writing, the followers eventually catch up. All replicas converge to the same state. This guarantee is called eventual consistency — a deliberately vague promise. "Eventually" might mean 1 millisecond or 10 seconds, depending on network conditions, follower load, and the volume of writes.

The word "eventually" hides three specific anomalies that will bite you in production. Each one has caused real outages at real companies.

Anomaly 1: Read-Your-Own-Writes

A user submits a comment on a blog post. Your application writes it to the leader. The user's browser immediately refreshes to show the page. This read request is load-balanced to a follower that hasn't yet received the new comment. The user sees the page without their comment. They click "submit" again, creating a duplicate. Or worse, they think the system is broken and leave.

Solutions:

• Read-from-leader for own data: When a user reads something they might have written (their profile, their comments, their orders), route that read to the leader. Other users' reads still go to followers.
• Track replication position: When the client writes, the response includes the leader's current replication log position (e.g., LSN=1042). Subsequent reads carry this position. The follower serving the read checks: "Am I at least at LSN 1042?" If not, it either waits or redirects to another replica.
• Time-based heuristic: After a write, serve all reads from the leader for the next N seconds. Crude but simple. N must exceed your typical replication lag.

Anomaly 2: Monotonic Reads

A user refreshes a page and sees 10 comments. They refresh again and see only 9 — the 10th comment disappeared. They refresh a third time and it's back. What happened? Their first read hit Follower-A (caught up), their second read hit Follower-B (lagging), and their third read hit Follower-A again.

Seeing data go backward in time is disorienting and feels like a bug. The guarantee we want is monotonic reads: once you've seen data at a certain point in time, you should never subsequently see older data.

Solution: Sticky sessions. Hash the user ID to a consistent follower. The same user always reads from the same follower. Their view of the data only moves forward. If that follower dies, they're reassigned to another, but since they start fresh, it feels like a reload rather than data disappearing.

Anomaly 3: Consistent Prefix Reads

Two users have a conversation:

A third user observes this conversation. But Partition B replicates faster than Partition A. The observer sees "It's $42" arrive before "How much is the item?" — the answer appears before the question. Causal ordering is violated.

This is the consistent prefix reads problem. It only occurs when data is spread across multiple partitions that replicate independently. If everything is on one partition, the replication log preserves order.

Solution: Ensure causally related writes go to the same partition (e.g., all messages in a conversation go to the same partition). Or use a global ordering mechanism like a logical timestamp.

Measuring Replication Lag in Production

You can't fix what you can't measure. Here's how to monitor lag in the major databases:

python
# Monitoring replication lag programmatically
import psycopg2
import time

def check_pg_replication_lag(leader_conn, follower_conn):
    """Check lag between PostgreSQL leader and follower."""
    # Method 1: Query pg_stat_replication on the leader
    with leader_conn.cursor() as cur:
        cur.execute("""
            SELECT client_addr,
                   pg_wal_lsn_diff(sent_lsn, replay_lsn) AS lag_bytes,
                   EXTRACT(EPOCH FROM replay_lag) AS lag_seconds
            FROM pg_stat_replication
        """)
        for row in cur.fetchall():
            addr, lag_bytes, lag_sec = row
            if lag_sec > 5.0:
                alert(f"Follower {addr}: {lag_sec:.1f}s behind!")

    # Method 2: Write a canary value and measure time-to-appear
    canary = str(time.time())
    with leader_conn.cursor() as cur:
        cur.execute("UPDATE canary SET val = %s", (canary,))
        leader_conn.commit()
        t0 = time.time()

    # Poll follower until canary appears
    while True:
        with follower_conn.cursor() as cur:
            cur.execute("SELECT val FROM canary")
            if cur.fetchone()[0] == canary:
                lag = time.time() - t0
                print(f"Measured lag: {lag*1000:.0f}ms")
                break
        time.sleep(0.01)

The "Replication Window" — How Long Is Dangerous?

Chapter 5: Multi-Leader Replication

Leader-follower replication has a fundamental limitation: every write must go through the single leader. If the leader is in Virginia and your user is in Tokyo, every write incurs a trans-Pacific round trip. If the leader goes down, writes stop until failover completes.

Multi-leader replication (also called master-master or active-active) allows more than one node to accept writes. Each leader processes writes locally and replicates changes to the other leaders asynchronously.

Use Cases

Multi-datacenter operation. One leader per datacenter. Users write to their local datacenter's leader. Replication between datacenters happens in the background. Each datacenter can operate independently if the network between datacenters goes down.

Offline-capable clients. Your calendar app, notes app, or document editor needs to work without internet. Each device is effectively a "leader" — it accepts writes locally and syncs when connectivity is restored. CouchDB was designed for exactly this model.

Collaborative editing. Google Docs lets multiple users edit the same document simultaneously. Each user's keystrokes are local writes that must be merged. This is multi-leader replication at the keystroke level.

The BIG Problem: Write Conflicts

Two users simultaneously edit the same row from different datacenters:

In single-leader replication, this can't happen — all writes go through one node, which serializes them. In multi-leader replication, conflicts are inevitable.

Conflict Resolution Strategies

Worked Example: Google Docs-Style Conflict Resolution

To understand why collaborative editing needs special treatment, consider this scenario. Two users are editing the string "HELLO" simultaneously:

Multi-Leader Topology

How do the leaders exchange changes? Three options:

Circular topology: Each leader sends its changes to the next in a ring. If one node fails, the ring breaks. MySQL supports this.

Star topology: One designated root leader forwards changes to all others. Simpler routing, but the root is a single point of failure.

All-to-all topology: Every leader sends to every other leader. Most fault-tolerant but requires more network connections. PostgreSQL BDR uses this.

Worked Example: Multi-Leader Conflict in an E-Commerce System

You run an e-commerce site with leaders in Virginia (VA) and Frankfurt (EU). A customer has a shipping address on record.

CRDT: The Mathematical Solution

For specific data types, Conflict-free Replicated Data Types (CRDTs) can automatically merge concurrent updates without any data loss. The most common CRDT is the G-Counter (grow-only counter):

python
class GCounter:
    """Grow-only counter CRDT. Each replica has its own counter.
    Global count = sum of all replicas' counters.
    Merge = component-wise maximum."""

    def __init__(self, replica_id, n_replicas):
        self.replica_id = replica_id
        self.counts = [0] * n_replicas

    def increment(self):
        # Only increment OUR counter
        self.counts[self.replica_id] += 1

    def value(self):
        return sum(self.counts)

    def merge(self, other):
        # Component-wise max — NEVER loses an increment
        for i in range(len(self.counts)):
            self.counts[i] = max(self.counts[i], other.counts[i])

# Demo: two replicas count page views independently
va = GCounter(replica_id=0, n_replicas=2)
eu = GCounter(replica_id=1, n_replicas=2)

# VA gets 5 page views, EU gets 3
for _ in range(5): va.increment()
for _ in range(3): eu.increment()

print(va.counts)  # [5, 0]
print(eu.counts)  # [0, 3]

# Merge: no conflicts, no data loss
va.merge(eu)
eu.merge(va)
print(va.value())  # 8 — correct!
print(eu.value())  # 8 — both replicas agree

Chapter 6: Leaderless Replication

What if we got rid of the leader entirely? No single node is special. Any replica can accept reads AND writes. The client sends each write to multiple replicas in parallel. This is leaderless replication, pioneered by Amazon's Dynamo paper (2007) and used by Cassandra, Riak, and Voldemort.

Quorum Reads and Writes

With N replicas, the client sends each write to W replicas and each read to R replicas. The key insight:

At least one of the R replicas you read from must have the latest write. This is a quorum.

Worked Example: The Quorum Math

What if W + R ≤ N?

You sacrifice the quorum guarantee. Reads might miss the latest write entirely. But you gain availability: you can tolerate more node failures. Some applications choose W=1, R=1 (fastest possible, no consistency guarantee) for use cases where stale data is acceptable (e.g., analytics counters).

Common Quorum Configurations

Repairing Stale Replicas

Even with quorums, replicas can diverge. Two mechanisms bring them back in sync:

Read repair: When a client reads from multiple replicas and discovers that one has stale data, it writes the fresh value back to the stale replica. Repairs happen on every read, but only for data that's actually being read. Cold data (rarely read) can remain stale forever.

Anti-entropy process: A background daemon constantly compares replicas and copies missing data. Unlike read repair, this catches all stale data eventually, not just data being read. But it adds background I/O.

Sloppy Quorums and Hinted Handoff

What happens when more than N-W nodes are down? Strict quorum writes fail. But if your priority is availability over consistency, you can use a sloppy quorum: accept writes on nodes that aren't the "home" replicas for this key. When the home nodes come back, the data is handed off to them. This is hinted handoff.

Sloppy quorums increase availability but weaken consistency — a read quorum might now miss a write that was stored on a "wrong" node.

Worked Example: Quorum Write and Read Repair

Let's trace a complete quorum write and read with N=3, W=2, R=2, showing exactly how read repair works.

The Limits of Quorums

Even with W + R > N, quorums do NOT guarantee linearizability (the strongest consistency model). Here's why:

Leaderless in the Wild: Cassandra Configuration

Here's what leaderless replication looks like in practice with Apache Cassandra:

sql
-- Create a keyspace with replication factor 3
CREATE KEYSPACE my_app
WITH replication = {
    'class': 'NetworkTopologyStrategy',
    'us-east': 3,     -- 3 replicas in US-East
    'eu-west': 3      -- 3 replicas in EU-West
};

-- Write with LOCAL_QUORUM (majority in the local datacenter)
-- This means W=2 out of 3 local replicas, plus async to remote DC
INSERT INTO users (id, name, email)
VALUES (uuid(), 'Alice', 'alice@example.com')
USING CONSISTENCY LOCAL_QUORUM;

-- Read with LOCAL_QUORUM
-- Reads from 2 out of 3 local replicas
-- Guarantees seeing local writes, but NOT writes from other DC
SELECT * FROM users WHERE id = ?
USING CONSISTENCY LOCAL_QUORUM;

Why Leaderless Databases Are Popular for Time-Series and IoT

Leaderless replication shines for append-heavy workloads where writes are far more frequent than reads, and eventual consistency is acceptable. Consider an IoT sensor network:

This is why Cassandra dominates in IoT, time-series, and event logging. The data model is append-only (sensor readings are never updated), conflicts don't apply (each timestamp is unique), and eventual consistency is fine (dashboards can be a few seconds behind).

Consistent Hashing: How Leaderless Systems Assign Data to Replicas

In a leaderless system, how does the coordinator know WHICH N replicas should store a given key? The answer is consistent hashing. Each replica is assigned a position on a hash ring. Each key is hashed to a position on the same ring. The N replicas responsible for a key are the first N nodes clockwise from the key's position.

Chapter 7: Detecting Concurrent Writes

This is where replication gets truly interesting. Two clients write to the same key at roughly the same time. Neither knows about the other's write. In distributed systems terminology, these writes are concurrent — there is no causal relationship between them (neither "happened before" the other).

How do you even detect that two writes are concurrent, as opposed to one happening after the other?

The Happens-Before Relationship

Two events A and B have one of three relationships:

You cannot use wall-clock timestamps to determine this ordering. Clocks are unreliable in distributed systems (NTP drift, leap seconds, VM clock pauses). Instead, we use version vectors.

Version Vectors: The Algorithm

Each replica maintains a version number for each key. When a client writes, it includes the version numbers it last read. The server can then tell whether the new write supersedes, is superseded by, or is concurrent with existing data.

The Shopping Cart Example (from the Dynamo Paper)

Amazon's Dynamo paper used a shopping cart as the motivating example. When two concurrent writes add different items to the same cart, the system stores both versions (siblings). When the client next reads, it receives all siblings and must merge them. For a shopping cart, merging means taking the union of all items.

But what about removing items? If one sibling has {milk, eggs, butter} and another has {milk, eggs} (butter was removed), taking the union puts butter back. The removed item resurrects. This is the "resurrection bug."

The fix: don't remove items, mark them as deleted with a tombstone. The merge function is: union all items, then remove items that have a tombstone in any sibling.

Version Vector Implementation

python
class VersionVector:
    def __init__(self):
        self.clock = {}  # {replica_id: version_number}

    def increment(self, replica_id):
        self.clock[replica_id] = self.clock.get(replica_id, 0) + 1

    def dominates(self, other):
        """Does self happen-after other?"""
        # Every entry in other must be <= corresponding entry in self
        # AND at least one must be strictly less
        all_keys = set(self.clock) | set(other.clock)
        at_least_one_greater = False
        for k in all_keys:
            s = self.clock.get(k, 0)
            o = other.clock.get(k, 0)
            if s < o:
                return False  # other has a higher version somewhere
            if s > o:
                at_least_one_greater = True
        return at_least_one_greater

    def concurrent_with(self, other):
        """Neither dominates the other."""
        return not self.dominates(other) and not other.dominates(self)

    def merge(self, other):
        """Take component-wise max."""
        merged = VersionVector()
        all_keys = set(self.clock) | set(other.clock)
        for k in all_keys:
            merged.clock[k] = max(self.clock.get(k, 0),
                                  other.clock.get(k, 0))
        return merged

    def __repr__(self):
        return str(self.clock)

# Demo: detecting concurrent writes
vv_a = VersionVector()
vv_a.increment("A")         # {A:1}
vv_b = VersionVector()
vv_b.increment("B")         # {B:1}

print(vv_a.concurrent_with(vv_b))  # True — neither dominates

merged = vv_a.merge(vv_b)         # {A:1, B:1}
merged.increment("A")             # {A:2, B:1}
print(merged.dominates(vv_a))     # True — merged happened after vv_a
print(merged.dominates(vv_b))     # True — merged happened after vv_b

Complete Leaderless Key-Value Store with Version Vectors

Here's a complete implementation that ties version vectors to actual data storage — the same pattern used by Riak internally:

python
class DynamoStyleStore:
    """A single replica in a Dynamo-style leaderless system."""

    def __init__(self, replica_id):
        self.id = replica_id
        # key -> list of (value, VersionVector) pairs
        # Multiple entries = siblings (concurrent writes)
        self.data = {}

    def put(self, key, value, context=None):
        """Write a value. context = version vector from prior read."""
        if context is None:
            context = VersionVector()

        # Increment this replica's version
        new_vv = VersionVector()
        new_vv.clock = dict(context.clock)
        new_vv.increment(self.id)

        if key not in self.data:
            self.data[key] = [(value, new_vv)]
            return new_vv

        # Remove entries that the new write supersedes
        surviving = []
        for (v, vv) in self.data[key]:
            if not new_vv.dominates(vv):
                surviving.append((v, vv))  # keep as sibling
        surviving.append((value, new_vv))
        self.data[key] = surviving
        return new_vv

    def get(self, key):
        """Read all values (may return siblings)."""
        if key not in self.data:
            return [], VersionVector()
        entries = self.data[key]
        merged_vv = VersionVector()
        for (v, vv) in entries:
            merged_vv = merged_vv.merge(vv)
        values = [v for (v, vv) in entries]
        return values, merged_vv

# Demo: the shopping cart scenario
store_A = DynamoStyleStore("A")
store_B = DynamoStyleStore("B")

# Client X writes "milk" to store A
ctx1 = store_A.put("cart", ["milk"])
# store_A: cart = [(["milk"], {A:1})]

# Client Y writes "eggs" to store B (concurrent!)
ctx2 = store_B.put("cart", ["eggs"])
# store_B: cart = [(["eggs"], {B:1})]

# Anti-entropy: sync A's data to B.
# B sees {A:1} vs {B:1} — neither dominates → sibling!
# store_B: cart = [(["milk"],{A:1}), (["eggs"],{B:1})]

# Client reads from B, merges siblings
vals, ctx = store_B.get("cart")
# vals = [["milk"], ["eggs"]], ctx = {A:1, B:1}
merged_cart = list(set(item for v in vals for item in v))
# merged_cart = ["milk", "eggs"]

# Client writes merged value back with the merged context
store_B.put("cart", merged_cart, context=ctx)
# store_B: cart = [(["milk","eggs"], {A:1, B:2})]
# Sibling resolved! {A:1,B:2} dominates both {A:1} and {B:1}.

Hand-Worked Exercise: Version Vector Comparison

Practice determining the relationship between version vectors. For each pair, decide: does A dominate B? Does B dominate A? Or are they concurrent?

The Sibling Merge Problem: Deletes and Tombstones

Siblings (concurrent values stored together) must eventually be merged. For a shopping cart:

python
def merge_shopping_carts(siblings):
    """Merge concurrent shopping cart siblings using tombstones.
    Each sibling is a dict: {item: True/False} where False = tombstone."""
    all_items = set()
    tombstoned = set()

    for sibling in siblings:
        for item, alive in sibling.items():
            if alive:
                all_items.add(item)
            else:
                tombstoned.add(item)

    # Result: all items that appear alive in ANY sibling,
    # minus items tombstoned in ANY sibling.
    return all_items - tombstoned

# Example:
sibling_1 = {"milk": True, "eggs": True, "butter": True}
sibling_2 = {"milk": True, "eggs": True, "butter": False}  # tombstone

result = merge_shopping_carts([sibling_1, sibling_2])
print(result)  # {'milk', 'eggs'} — butter correctly removed

Last-Write-Wins: When It Works and When It Kills

LWW is the simplest conflict resolution strategy: attach a timestamp to each write, keep the highest. Many engineers default to it because it's easy to implement. But it has a fundamental problem: it silently discards writes. Here's a complete analysis:

The Happens-Before Partial Order: Visualizing Causality

Happens-before is a partial order, not a total order. In a total order, every pair of events can be compared (like numbers on a number line). In a partial order, some pairs are incomparable — that's what "concurrent" means. Think of it like a family tree: your parents are your ancestors (they "happened before" you), but two cousins are neither ancestor nor descendant of each other — they're concurrent.

Chapter 8: Replication in Practice

Theory is clean. Production is messy. Let's look at how real databases implement replication and what trade-offs they've made.

PostgreSQL: Leader-Follower with WAL Shipping

PostgreSQL uses physical streaming replication by default. The leader streams its WAL (Write-Ahead Log) to followers, which replay the exact same disk operations.

MySQL: Leader-Follower with Binlog

MongoDB: Replica Sets with Raft-like Election

Cassandra: Leaderless with Tunable Quorums

How to Choose Between PostgreSQL and Cassandra: A Decision Framework

This is one of the most common system design decisions. Here's the structured way to think about it:

In practice, many systems use BOTH: PostgreSQL for transactional data (user accounts, orders, payments) and Cassandra for high-volume event data (clickstreams, sensor readings, logs). CDC pipes changes from PostgreSQL to Cassandra for full-text search or analytics.

Real Incident: Cassandra Tombstone Storms

A less-discussed but dangerous failure mode in Cassandra: tombstone accumulation. When you delete a row in Cassandra, it doesn't physically remove the data. Instead, it writes a tombstone — a marker that says "this row was deleted." Tombstones are necessary because the delete must propagate to all replicas, and without a tombstone, a replica that missed the delete would "resurrect" the row on the next read repair.

The problem: tombstones accumulate until Cassandra runs a compaction (merging SSTables). If your workload involves heavy deletes (e.g., a TTL-based cache, or a queue that dequeues by deleting), you can accumulate millions of tombstones. When a read query scans a range, it must read through all tombstones to find live rows. A query that should take 5ms now takes 30 seconds because it's scanning 2 million tombstones.

CockroachDB: Raft-Based, Strongly Consistent

Design Challenge: Global Chat App

System Design Deep Dive: Twitter's Timeline Replication

Twitter (now X) is a fascinating case study in replication strategy. The core challenge: when a user with 50 million followers tweets, that tweet must appear in 50 million timelines. How?

This is replication at the application level. The same concepts apply: fan-out-on-write is like synchronous replication (write is not "done" until all copies exist), fan-out-on-read is like lazy evaluation (compute the view on demand). The hybrid approach mirrors semi-synchronous replication: eagerly replicate to most targets, lazily handle the expensive ones.

Debug Scenarios

"Replication lag is growing steadily." Check: (1) Is the follower's disk I/O saturated? (long-running queries on the follower, vacuum, or compaction), (2) Is the network between leader and follower degraded? (packet loss, bandwidth saturation), (3) Is the write workload spiking? (large batch imports), (4) Is the follower CPU-bound on replay? (too many indexes to update per write).

"Reads return stale data intermittently." Check: (1) Are reads going to followers? (verify load balancer routing), (2) What's the current replication lag? (pg_stat_replication, SHOW SLAVE STATUS), (3) Is it always the same follower? (that follower might be unhealthy), (4) Is the application using connection pooling that routes some reads to followers? (PgBouncer config).

Testing Replication: Chaos Engineering

You can't trust your replication strategy until you've broken it deliberately. Here's how production teams validate their replication setup:

python
# Chaos engineering tests for replication
# Run these in staging, NOT production (unless you're Netflix)

class ReplicationChaosTests:

    def test_leader_failure(self):
        """Kill the leader and verify failover."""
        # 1. Write a canary value to the leader
        canary = f"chaos-test-{uuid.uuid4()}"
        leader.write("canary", canary)

        # 2. Wait for replication
        time.sleep(2)

        # 3. Kill the leader
        leader.kill()

        # 4. Wait for failover
        time.sleep(60)  # max expected failover time

        # 5. Verify: can we still read the canary?
        result = get_new_leader().read("canary")
        assert result == canary, "DATA LOSS during failover!"

        # 6. Verify: can we write?
        get_new_leader().write("post-failover", "alive")
        print("✓ Leader failover: PASS")

    def test_follower_failure(self):
        """Kill a follower and verify reads continue."""
        follower_1.kill()
        time.sleep(5)
        # Reads should still work (from remaining followers)
        result = read_from_cluster("any-key")
        assert result is not None
        print("✓ Follower failure: reads continue")

    def test_network_partition(self):
        """Simulate network partition between leader and followers."""
        # Use iptables or tc to block traffic
        block_traffic(leader, followers)

        # Leader should still accept writes
        leader.write("during-partition", "test")

        # Followers should serve (stale) reads
        # But NOT serve writes (no split brain)

        # Heal partition
        restore_traffic(leader, followers)
        time.sleep(10)

        # Followers should catch up
        result = follower_1.read("during-partition")
        assert result == "test"
        print("✓ Network partition recovery: PASS")

    def test_replication_lag_under_load(self):
        """Write heavily and measure lag increase."""
        initial_lag = measure_lag()
        # Write 100K rows rapidly
        for i in range(100000):
            leader.write(f"load-test-{i}", "x" * 1000)
        post_load_lag = measure_lag()
        print(f"Lag increase under load: {initial_lag}ms → {post_load_lag}ms")
        assert post_load_lag < 30000, "Lag exceeded 30s threshold!"

Full Design Walkthrough: Multi-Region E-Commerce

An interviewer says: "You're building an e-commerce platform with users in North America, Europe, and Asia. Design the database replication strategy."

This answer demonstrates staff-level thinking: different strategies for different data, clear trade-off reasoning, concrete numbers, and operational awareness.

Replication Anti-Patterns

Common mistakes that cause production incidents:

Capacity Planning: How Many Replicas?

Chapter 9: Interview Arsenal

Everything you've learned, condensed into the frameworks and talking points that win system design interviews.

The Replication Decision Tree

Cheat Sheet: All Strategies at a Glance

System Design Talking Points

"Design a multi-region database for a social network."

• User profiles: leader-follower per user's home region. Reads from nearest replica. Writes to home region leader.
• Posts/feed: leader-follower with async replication. Slight lag (seconds) is acceptable for feed items. Fan-out-on-write for friends list.
• Direct messages: per-conversation leader in the region of the conversation initiator. Consistent prefix reads within a conversation.
• Likes/counters: leaderless with CRDTs (G-Counter). Exact counts don't need strong consistency.

"Design a collaborative document editor."

• Multi-leader by definition — each client is a leader that accepts local writes.
• Conflict resolution: OT (Google Docs) or CRDTs (Automerge, Yjs).
• Central server: acts as a coordination point for OT, or a sync hub for CRDTs.
• Offline support: CRDT approach naturally supports offline — merge when reconnected.

Coding Drill: Quorum Read/Write

python
import random
from concurrent.futures import ThreadPoolExecutor, as_completed

class Replica:
    def __init__(self, id):
        self.id = id
        self.store = {}  # key -> (value, version)

    def write(self, key, value, version):
        self.store[key] = (value, version)
        return True

    def read(self, key):
        return self.store.get(key, (None, 0))

class QuorumClient:
    def __init__(self, replicas, w, r):
        self.replicas = replicas  # list of Replica
        self.N = len(replicas)
        self.W = w
        self.R = r
        self.version = 0

    def quorum_write(self, key, value):
        self.version += 1
        # Send to all, wait for W ACKs
        acks = 0
        for replica in self.replicas:
            if replica.write(key, value, self.version):
                acks += 1
            if acks >= self.W:
                return True  # quorum met
        return False  # not enough ACKs

    def quorum_read(self, key):
        # Read from R replicas, return highest version
        results = []
        chosen = random.sample(self.replicas, self.R)
        for replica in chosen:
            val, ver = replica.read(key)
            results.append((val, ver, replica))

        # Pick the value with highest version
        best = max(results, key=lambda x: x[1])

        # Read repair: update stale replicas
        for val, ver, replica in results:
            if ver < best[1]:
                replica.write(key, best[0], best[1])

        return best[0]

# Demo
replicas = [Replica(i) for i in range(3)]
client = QuorumClient(replicas, w=2, r=2)
client.quorum_write("user:42", "Alice")
print(client.quorum_read("user:42"))  # "Alice"

System Design Template: Replication Section

In every system design interview, when you reach the database/storage section, use this framework:

Common Mistakes in System Design Interviews

Debug Scenario Drills

Coding Drill: Implementing Read-Your-Own-Writes

python
import time
from typing import Optional

class ReplicationAwareRouter:
    """Routes reads to leader or follower based on
    read-your-own-writes consistency requirement."""

    def __init__(self, leader, followers):
        self.leader = leader
        self.followers = followers
        # Track last write LSN per user
        self.user_write_lsn = {}  # user_id -> (lsn, timestamp)
        self.consistency_window = 5.0  # seconds

    def record_write(self, user_id, lsn):
        """Called after every write. Records the LSN for routing."""
        self.user_write_lsn[user_id] = (lsn, time.time())

    def route_read(self, user_id, key) -> "Connection":
        """Route a read to the best replica for this user."""
        entry = self.user_write_lsn.get(user_id)

        if entry:
            required_lsn, write_time = entry
            # If write was recent, ensure we read fresh data
            if time.time() - write_time < self.consistency_window:
                # Try to find a follower that's caught up
                for f in self.followers:
                    if f.current_lsn() >= required_lsn:
                        return f  # This follower has the user's write
                # No follower is caught up — fall back to leader
                return self.leader

        # No recent write — any follower is fine
        return random.choice(self.followers)

Coding Drill: Failover Health Check

python
import threading

class FailoverMonitor:
    """Monitors leader health and triggers failover."""

    def __init__(self, leader, followers, heartbeat_interval=1.0,
                 timeout=10.0, max_lag_for_promotion=1000):
        self.leader = leader
        self.followers = followers
        self.heartbeat_interval = heartbeat_interval
        self.timeout = timeout
        self.max_lag = max_lag_for_promotion  # max bytes behind
        self.last_heartbeat = time.time()
        self.is_leader_alive = True

    def check_heartbeat(self):
        try:
            self.leader.ping()
            self.last_heartbeat = time.time()
            self.is_leader_alive = True
        except ConnectionError:
            elapsed = time.time() - self.last_heartbeat
            if elapsed > self.timeout:
                self.trigger_failover()

    def trigger_failover(self):
        # 1. Fence old leader (STONITH)
        self.leader.fence()  # Prevent split-brain

        # 2. Find best candidate (most up-to-date, within lag limit)
        candidates = [
            (f, f.replication_lag_bytes())
            for f in self.followers
            if f.replication_lag_bytes() <= self.max_lag
        ]
        if not candidates:
            raise RuntimeError("No eligible follower for promotion!")

        # Pick the one with least lag
        new_leader, lag = min(candidates, key=lambda x: x[1])

        # 3. Promote
        new_leader.promote_to_leader()

        # 4. Reconfigure remaining followers
        for f in self.followers:
            if f != new_leader:
                f.set_replication_source(new_leader)

        print(f"Failover complete. New leader: {new_leader.id}, lag was {lag} bytes")

Recommended Reading

Coding Drill: Implementing a Simple Replication Stream

python
import time, threading, queue

class ReplicationLog:
    """Write-ahead log used for replication."""

    def __init__(self):
        self.entries = []     # [(lsn, operation)]
        self.lsn_counter = 0
        self.lock = threading.Lock()

    def append(self, operation):
        with self.lock:
            self.lsn_counter += 1
            self.entries.append((self.lsn_counter, operation))
            return self.lsn_counter

    def get_entries_since(self, from_lsn):
        """Return all entries with LSN > from_lsn."""
        return [(lsn, op) for (lsn, op) in self.entries if lsn > from_lsn]


class Leader:
    """Leader node that accepts writes and streams to followers."""

    def __init__(self):
        self.data = {}
        self.wal = ReplicationLog()
        self.followers = []

    def write(self, key, value):
        # 1. Write to WAL
        lsn = self.wal.append({"op": "SET", "key": key, "value": value})
        # 2. Apply to local state
        self.data[key] = value
        # 3. Stream to followers (async)
        for f in self.followers:
            f.receive(lsn, {"op": "SET", "key": key, "value": value})
        return lsn

    def read(self, key):
        return self.data.get(key)


class Follower:
    """Follower node that replays changes from the leader."""

    def __init__(self, follower_id):
        self.id = follower_id
        self.data = {}
        self.applied_lsn = 0
        self.pending = queue.Queue()

    def receive(self, lsn, operation):
        """Receive a change from the leader (async)."""
        self.pending.put((lsn, operation))

    def apply_pending(self):
        """Apply pending changes (called by replay loop)."""
        while not self.pending.empty():
            lsn, op = self.pending.get()
            if lsn <= self.applied_lsn:
                continue  # Already applied (idempotent)
            if op["op"] == "SET":
                self.data[op["key"]] = op["value"]
            self.applied_lsn = lsn

    def read(self, key):
        self.apply_pending()  # Catch up before reading
        return self.data.get(key)

    def lag_behind(self, leader):
        """How many LSNs behind the leader?"""
        return leader.wal.lsn_counter - self.applied_lsn


# Demo: trace writes through the replication stream
leader = Leader()
f1 = Follower("follower-1")
f2 = Follower("follower-2")
leader.followers = [f1, f2]

leader.write("user:1", "Alice")    # LSN=1
leader.write("user:2", "Bob")      # LSN=2

# Before followers apply:
print(f1.lag_behind(leader))     # 2 (two writes pending)
print(f1.read("user:1"))         # "Alice" (apply_pending runs first)
print(f1.lag_behind(leader))     # 0 (caught up after read)

Coding Drill: Consistent Hashing for Replica Assignment

python
import hashlib

class ConsistentHashRing:
    """Assigns keys to N replicas using consistent hashing.
    Used by Cassandra, DynamoDB, and Riak to determine which
    nodes store a given key."""

    def __init__(self, nodes, virtual_nodes=150, replication_factor=3):
        self.ring = {}          # hash_position -> node_id
        self.sorted_keys = []   # sorted hash positions
        self.rf = replication_factor
        self.nodes = set(nodes)

        # Each physical node gets multiple positions on the ring
        # (virtual nodes) for better distribution
        for node in nodes:
            for i in range(virtual_nodes):
                key = f"{node}:{i}"
                h = self._hash(key)
                self.ring[h] = node
                self.sorted_keys.append(h)
        self.sorted_keys.sort()

    def _hash(self, key):
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def get_replicas(self, key):
        """Return the N replica nodes responsible for this key."""
        if not self.sorted_keys:
            return []

        h = self._hash(key)
        replicas = []
        seen_nodes = set()

        # Walk clockwise from the key's hash position
        idx = self._find_start(h)
        while len(replicas) < self.rf and len(seen_nodes) < len(self.nodes):
            pos = self.sorted_keys[idx % len(self.sorted_keys)]
            node = self.ring[pos]
            if node not in seen_nodes:
                replicas.append(node)
                seen_nodes.add(node)
            idx += 1
        return replicas

    def _find_start(self, h):
        """Binary search for first position >= h."""
        lo, hi = 0, len(self.sorted_keys) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if self.sorted_keys[mid] < h:
                lo = mid + 1
            else:
                hi = mid
        return lo

    def add_node(self, node):
        """Add a node — only keys assigned to this node need to move."""
        self.nodes.add(node)
        for i in range(150):
            key = f"{node}:{i}"
            h = self._hash(key)
            self.ring[h] = node
            self.sorted_keys.append(h)
        self.sorted_keys.sort()

# Demo
ring = ConsistentHashRing(["nodeA", "nodeB", "nodeC", "nodeD", "nodeE"])
print(ring.get_replicas("user:42"))   # e.g., ['nodeC', 'nodeA', 'nodeE']
print(ring.get_replicas("user:99"))   # e.g., ['nodeB', 'nodeD', 'nodeA']

# Add a new node — minimal key redistribution
ring.add_node("nodeF")
print(ring.get_replicas("user:42"))   # May or may not change

Interview Rapid-Fire: 10 Questions, 10 One-Line Answers

The Five Dimensions of Replication Knowledge

Every interview question about replication tests one of these dimensions. For each, here's a question you should be able to answer without hesitation:

Chapter 10: Connections

Replication is one of three pillars of distributed data systems. Here's how it connects to the other DDIA chapters and the broader landscape.

Where Replication Fits

The Bigger Picture

Replication sits at the heart of the CAP/PACELC trade-off space:

What This Lesson Did NOT Cover

The Replication Landscape: A Visual Summary

Replication in Managed Cloud Services

If you're using a cloud provider, you don't configure replication from scratch — but you still need to understand the trade-offs behind the options:

The Cost of Replication

When NOT to Replicate

Replication is not always the answer. Consider these alternatives:

How to Think About CAP in Practice

The CAP theorem is often misunderstood. Here's the nuanced version:

In practice, network partitions are rare (minutes per year in a well-run datacenter). So the PACELC extension is more useful day-to-day: even without partitions, you're constantly trading Latency vs. Consistency. Every time you choose async replication for speed, you're making a PACELC trade-off.

Key Takeaway

There is no "best" replication strategy. There are only trade-offs. Every system you build or evaluate sits somewhere in this space:

The engineer who understands WHERE a system sits in this space, and WHY it was designed that way, is the one who gets the staff-level offer.

The Local-First Movement: Replication Without Servers

A fascinating frontier in replication: what if there is no server at all? Local-first software runs entirely on the user's device, stores data locally, and uses CRDTs to sync between devices peer-to-peer.

In this model, every user's device is effectively a "leader" in a multi-leader replication system. CRDTs ensure that all devices converge to the same state regardless of the order in which changes are applied. The challenge: CRDTs work well for text, counters, and sets, but poorly for structured data like relational tables or complex business objects.

How Replication Evolved: A Brief History

What to Read Next

If this lesson gave you the conceptual foundation, here's the path to deeper mastery:

One More Design Challenge

"Design the replication strategy for a global payments system."

This is arguably the hardest replication design challenge because financial data has the strictest consistency requirements:

This answer demonstrates the key insight: even in a "zero data loss" system, you sometimes accept async replication for cross-region operations. The trick is designing the business logic to handle the async window gracefully (saga pattern, pending states, idempotent operations).