Replication and CAP

Replication keeps copies of the same data on several servers to survive failures, serve more reads, and place data near users. See also database replication.

Example 1: leader-follower replication

One leader (primary) accepts writes and streams changes to followers (replicas, standbys), which serve reads.

flowchart LR
    C["Clients (writes)"] --> L["Leader"]
    L -->|"WAL / binlog stream"| F1["Follower 1"]
    L -->|"WAL / binlog stream"| F2["Follower 2"]
    R["Clients (reads)"] --> F1
    R --> F2

Example 2: synchronous, asynchronous, semi-synchronous

The commit returns to the client after different events depending on the mode.

PostgreSQL controls this with synchronous_commit (off, local, remote_write, on, remote_apply) and synchronous_standby_names. MySQL has semi-synchronous replication as a plugin and Group Replication for consensus-based commit.

SELECT name, boot_val, short_desc
FROM pg_settings
WHERE name IN ('synchronous_commit', 'wal_level', 'max_wal_senders', 'hot_standby')
ORDER BY name;

        name        | boot_val |                               short_desc                                
--------------------+----------+-------------------------------------------------------------------------
 hot_standby        | on       | Allows connections and queries during recovery.
 max_wal_senders    | 10       | Sets the maximum number of simultaneously running WAL sender processes.
 synchronous_commit | on       | Sets the current transaction's synchronization level.
 wal_level          | replica  | Sets the level of information written to the WAL.
(4 rows)

Example 3: replication lag and read-your-writes

Asynchronous followers apply changes after the leader. A read from a follower right after a write can return old data.

sequenceDiagram
    participant U as User
    participant L as Leader
    participant F as Follower
    U->>L: UPDATE profile
    L-->>U: OK
    L-->>F: replicate (delayed)
    U->>F: SELECT profile
    F-->>U: old value

Lag in bytes is the difference between WAL positions (pg_lsn values subtract to a byte count):

SELECT '0/3000128'::pg_lsn - '0/3000000'::pg_lsn AS lag_bytes;

 lag_bytes 
-----------
       296
(1 row)

Example 4: monitoring replication in PostgreSQL

On a primary, pg_stat_replication has one row per connected standby. This server has no standby, so the view is empty; the column list shows what it reports.

SELECT count(*) AS connected_standbys FROM pg_stat_replication;

 connected_standbys 
--------------------
                  0
(1 row)

SELECT column_name
FROM information_schema.columns
WHERE table_name = 'pg_stat_replication'
  AND column_name IN ('client_addr', 'state', 'sent_lsn', 'write_lsn', 'flush_lsn',
                      'replay_lsn', 'write_lag', 'flush_lag', 'replay_lag', 'sync_state')
ORDER BY ordinal_position;

 column_name 
-------------
 client_addr
 state
 sent_lsn
 write_lsn
 flush_lsn
 replay_lsn
 write_lag
 flush_lag
 replay_lag
 sync_state
(10 rows)

On a standby, pg_is_in_recovery() returns true.

Example 5: failover

When the leader fails, a follower is promoted.

flowchart LR
    A["Detect failure (timeout)"] --> B["Choose the most up-to-date follower"]
    B --> C["Promote it to leader"]
    C --> D["Repoint clients and other followers"]
    D --> E["Old leader rejoins as follower (rewind if diverged)"]

Tools: Patroni, repmgr, and managed services for PostgreSQL; Orchestrator and Group Replication for MySQL. pg_rewind resynchronises a former leader.

Example 6: multi-leader and leaderless replication

Example 7: quorum reads and writes (W + R > N)

With N replicas, a write waits for W acknowledgements and a read queries R replicas. If W + R > N, every read set overlaps every write set in at least one replica, so a read sees the latest acknowledged write.

Worked case (N = 3, W = 2, R = 2): a write is stored on nodes A and B, node C misses it. Any 2 nodes read from {A,B}, {A,C}, or {B,C}. Each pair includes A or B, so the newest version is always returned and the coordinator returns the highest version. The query checks the overlap condition for several settings:

SELECT n, w, r, (w + r > n) AS overlap_guaranteed
FROM (VALUES (3,2,2), (3,1,1), (3,3,1), (5,3,3), (5,2,2)) AS q(n, w, r);

 n | w | r | overlap_guaranteed 
---+---+---+--------------------
 3 | 2 | 2 | t
 3 | 1 | 1 | f
 3 | 3 | 1 | t
 5 | 3 | 3 | t
 5 | 2 | 2 | f
(5 rows)

Example 8: physical vs logical replication, statement vs row-based

MySQL binlog formats:

Example 9: replica reads and connection pooling

Read replicas offload SELECT traffic. The application or a proxy routes writes to the leader and tolerant reads to followers.

A PostgreSQL connection is a separate process using several MB of memory, so thousands of direct connections degrade the server. PgBouncer (or a built-in pool such as RDS Proxy) multiplexes many client connections onto a small number of server connections.

Example 10: CAP, PACELC, and consistency models

CAP theorem: during a network partition (P) a distributed system must choose between consistency (C: every read sees the latest write) and availability (A: every request gets a non-error answer). Partitions cannot be ruled out in practice, so the real choice is CP or AP during a partition.

PACELC extends it: if there is a Partition choose A or C; Else (normal operation) choose Latency or Consistency.

Consistency models from strongest to weakest:

The consistency in CAP (linearizability) is different from the C in ACID (constraints hold).

Interview points

• Async replication can lose committed data on failover; sync replication costs latency and availability.
• Replication lag causes read-your-writes and monotonic-read anomalies.
• W + R > N gives overlapping quorums.
• Physical replication copies WAL; logical replication copies row changes and supports version upgrades.
• CAP applies only during partitions; PACELC covers the latency trade-off otherwise.
• Replicas scale reads, not writes; sharding scales writes.

Summary

• Leader-follower replication streams the WAL or binlog to followers; async is fast but can lose data, sync is safe but slower.
• Lag produces stale reads; route read-your-writes traffic to the leader.
• Failover needs failure detection, promotion, and fencing to avoid split brain.
• Leaderless systems use quorums: W + R > N ensures a read overlaps the latest write.
• CAP forces CP or AP during a partition; PACELC adds the latency vs consistency choice otherwise.