Replication in Distributed Databases

Knowing that you need replication is only the beginning. The critical question is: how should replicas be organized and coordinated? Should there be a single node accepting writes? Multiple? Should replicas be daisy-chained for efficiency or fully meshed for resilience? Should consensus protocols govern every write?

These questions define your replication strategy—the architectural pattern that determines how your distributed database behaves under normal operation and during failures. Each strategy makes specific trade-offs between consistency, availability, latency, and operational complexity.

Choosing the wrong strategy for your workload leads to systems that are either too slow (over-synchronized), too fragile (under-replicated), or too complex to operate (needlessly sophisticated). This page equips you to make informed architectural decisions.

The primary-replica strategy (also called leader-follower or master-slave) is the most common replication pattern. A single designated node—the primary—handles all write operations. One or more replica nodes receive copies of these writes and serve read traffic.

How It Works:

1. All writes go to primary: The primary is the single source of truth for data modifications.
2. Primary logs changes: Writes are recorded in a transaction log (WAL, binlog, oplog).
3. Replicas consume log: Replicas connect to the primary and continuously receive log entries.
4. Replicas apply changes: Each replica applies log entries to its local data, eventually matching the primary.
5. Reads distributed: Read queries can be served by any replica (with eventual consistency) or the primary (for strong consistency).

Conflict Resolution: None Required

Because only the primary accepts writes, there are no write conflicts. This is the fundamental simplification that makes primary-replica replication operationally manageable.

Failover Mechanics:

When the primary fails, a replica must be promoted:

1. Detection: Monitoring detects primary unresponsiveness (heartbeat failure, connection timeout).
2. Selection: A replica is chosen for promotion (most up-to-date, highest priority, consensus among replicas).
3. Promotion: The selected replica stops receiving replication and begins accepting writes.
4. Reconfiguration: Other replicas redirect to the new primary. Clients update connection endpoints.
5. Old primary handling: If the old primary recovers, it must become a replica (cannot accept writes).

Automatic vs. Manual Failover:

• Automatic: Tools like PostgreSQL Patroni, MySQL Orchestrator, or MongoDB replica sets handle failover automatically. Faster recovery but risk of split-brain.
• Manual: Operators decide when to failover. Slower but avoids premature promotion during transient issues.

The multi-primary strategy (also called multi-master or active-active) allows multiple nodes to accept writes simultaneously. Changes made on any primary are replicated to all other primaries. This eliminates the write bottleneck of single-primary but introduces significant complexity.

When Multi-Primary Is Needed:

1. Geographic distribution: Users in multiple regions need low-latency writes. Routing all writes to a single primary in one region adds 100-200ms latency for distant users.

2. High write availability: If the single primary fails, writes are blocked. Multi-primary allows writes to continue on surviving nodes.

3. Write throughput: Write-heavy workloads may exceed single-node capacity.

The Central Challenge: Conflict Resolution

When two primaries accept writes to the same data simultaneously, a conflict occurs. Unlike primary-replica, where conflicts are impossible, multi-primary must detect and resolve conflicts.

Conflict Resolution Strategies:

1. Last-Writer-Wins (LWW) Use timestamps to determine which write is "later." The later write overwrites the earlier one.

• Pros: Simple, deterministic, no manual intervention
• Cons: Silently loses data; clock synchronization is imperfect; "later" may not mean "correct"

2. Application-Level Resolution Present both values to the application and let business logic decide.

• Pros: Business-correct resolution; no data loss
• Cons: Application complexity; may require user intervention

3. Merge Functions Define data type-specific merge operations (e.g., union sets, merge counters).

• Pros: Automatic, semantically meaningful
• Cons: Only works for mergeable data types; complex implementation

4. CRDTs (Conflict-free Replicated Data Types) Data structures mathematically designed to merge without conflicts.

• Pros: Guaranteed convergence without coordination
• Cons: Limited data types; not suitable for all use cases

Chain replication is a specialized strategy that arranges nodes in a linear chain. Writes enter at the head of the chain and propagate through each node until reaching the tail. Reads are served exclusively by the tail. This design provides strong consistency with high throughput.

How Chain Replication Works:

1. Writes enter at head: The head node receives all write requests.
2. Sequential forwarding: The head forwards to the next node in the chain, which forwards to the next, and so on.
3. Tail acknowledges: Only when the write reaches the tail is it considered committed. The tail sends acknowledgment back to the client.
4. Reads from tail only: Since the tail has all committed writes, reads from the tail are strongly consistent.
5. No read from middle nodes: Middle nodes may have uncommitted writes; reading from them would violate consistency.

Why This Works:

The tail is guaranteed to have every committed write. Any write in the chain but not at the tail is "in flight"—not yet committed. By serving reads from the tail exclusively, you get linearizable (strongly consistent) reads without any coordination overhead.

Failure Handling in Chain Replication:

Head Failure: The next node in the chain becomes the new head. Pending writes that hadn't propagated past the old head are lost.

Middle Node Failure: The chain is "spliced"—the predecessor of the failed node connects directly to its successor. In-flight writes must be recovered from the predecessor.

Tail Failure: The predecessor of the tail becomes the new tail. Some committed writes (acked by old tail) may need re-acknowledgment.

CRAQ: Chain Replication with Apportioned Queries

A variant called CRAQ (Chain Replication with Apportioned Queries) allows reads from any node, not just the tail. Each node tracks which writes are "clean" (committed) vs. "dirty" (in-flight). Reads of clean data can be served locally; reads of dirty data are forwarded to the tail. This distributes read load while maintaining strong consistency.

Consensus-based replication uses distributed consensus protocols (Paxos, Raft, Zab) to ensure that all replicas agree on the order of writes. This provides the strongest consistency guarantees—linearizability—while tolerating failures of a minority of nodes.

The Core Idea:

Before a write is committed, a majority (quorum) of nodes must agree to accept it. This ensures:

• Any two quorums overlap by at least one node
• Committed writes are never lost (at least one surviving node has every commit)
• No two different values can be committed for the same slot

Common Consensus Protocols:

Raft

• Leader-based: a leader handles all client requests
• Log replication: leader appends entries to log, replicates to followers
• Leader election: if leader fails, majority elects a new leader
• Used by: etcd, CockroachDB, TiKV, Consul

Paxos

• More general and flexible than Raft
• Separates proposers, acceptors, and learners
• Multi-Paxos optimizes for sequences of values
• Used by: Google Spanner (variant), Chubby

Zab (Zookeeper Atomic Broadcast)

• Optimized for primary-backup with strong ordering
• Used by: Apache Zookeeper, Apache Kafka (for metadata)

Raft Protocol Deep Dive:

Leader Election:

1. Nodes start as followers with randomized election timeouts
2. If a follower receives no heartbeat, it becomes a candidate
3. Candidate requests votes from all nodes
4. Node receiving majority votes becomes leader
5. Leader sends periodic heartbeats to maintain authority

Log Replication:

1. Client sends write to leader
2. Leader appends entry to its log with a term number and index
3. Leader sends AppendEntries RPC to all followers in parallel
4. Followers append to their logs and acknowledge
5. When majority acknowledge, leader commits the entry
6. Leader notifies followers to commit

Safety Guarantees:

• Only one leader per term
• Leaders never overwrite their logs
• Only logs with committed entries can become leader
• Committed entries are durable across failures

Quorum-based replication (also called leaderless or Dynamo-style replication) eliminates the leader entirely. Clients can write to and read from any node. Consistency is achieved through quorum arithmetic: if you write to W nodes and read from R nodes, and W + R > N (total nodes), at least one node you read from has the latest write.

The Quorum Formula:

If W + R > N, reads will observe the latest write.

Where:
  N = Total number of replicas
  W = Number of nodes that must acknowledge a write
  R = Number of nodes that must respond to a read

Common Configurations:

Read Repair and Anti-Entropy:

Quorum replication requires mechanisms to ensure replicas eventually converge:

Read Repair: When a client reads from R nodes and receives different versions, it writes the newest version back to stale nodes. This piggy-backs consistency maintenance on read operations.

Anti-Entropy (Merkle Trees): Background processes compare data across replicas using hash trees. When differences are detected, the stale replica receives updates. This catches inconsistencies that read repair misses (data never read).

Hinted Handoff: If a node is temporarily unavailable during a write, another node stores the write temporarily (a "hint"). When the target node recovers, the hint is delivered. This maintains write availability during transient failures.

Selecting the right replication strategy requires matching your workload characteristics and requirements to strategy capabilities. Here's a decision framework:

Decision Tree:

1. Do you need multi-region writes with low latency?
   Yes → Multi-Primary (accept conflict resolution complexity)
   No → Continue

2. Is strong (linearizable) consistency required?
   Yes → Consensus-Based (Raft/Paxos)
   No → Continue

3. Is write availability more important than consistency?
   Yes → Quorum-Based (tunable W/R)
   No → Continue

4. Is read scalability the primary concern?
   Yes → Primary-Replica with Async (many replicas)
   No → Primary-Replica with Sync (simple, durable)

Real-world systems often combine multiple replication strategies to achieve complex requirements. Understanding these hybrid approaches reveals the flexibility of replication architecture:

Example: CockroachDB Architecture

CockroachDB demonstrates sophisticated hybrid replication:

1. Data is sharded into ranges (~64MB each)
2. Each range uses Raft consensus for strong consistency
3. Ranges have 3-5 replicas spread across failure domains
4. Leaseholder optimization: One replica per range holds a lease for serving reads without consensus
5. Multi-region: Ranges can span regions with geo-partitioning

This combines sharding, consensus, and lease-based optimization into a globally consistent yet locally fast system.

We've explored the major replication strategies and their trade-offs. Let's consolidate the key insights:

What's Next:

Now that we understand replication strategies, we'll dive into the most critical aspect of distributed database design: Consistency Trade-offs. We'll explore the spectrum from strong to eventual consistency, the CAP and PACELC theorems, and how to choose the right consistency model for your application's semantics.