Replication Strategies

How to ensure consistency when multiple machines hold copies of the same data? Single-leader is simple but has a write bottleneck; multi-leader allows geo-distributed writes but suffers from conflicts; leaderless sacrifices consistency for availability. The trade-offs among consistency, latency, and fault tolerance in these three strategies represent the first major divergence in distributed storage.

Single Leader (Primary-Backup / Master-Slave)

All write operations must pass through the leader. The leader persists writes to its own Write-Ahead Log (WAL) and then propagates them to followers via replication (synchronous or asynchronous).

Client → Leader:   write(x=1)
Leader:             append to WAL → fsync → return OK to client (if synchronous)
                    → asynchronous or synchronous replication to followers
Followers:          receive new entries → apply to local state
Client → Follower:  read(x) → may return stale value (due to replication lag)

Replication Modes

Synchronous Replication: The leader waits for acknowledgment from at least one follower before returning a response to the client. This ensures that at least one follower has the latest data—if the leader crashes, that follower can take over without data loss. The cost is that write latency equals the slower of the two nodes' fsync times.

Asynchronous Replication: The leader does not wait for follower acknowledgment. Write latency is minimized, but unacknowledged writes are lost if the leader crashes (RPO > 0).

Semi-Synchronous (MySQL semisync): Waits for acknowledgment from at least one follower, but not all. This balances durability and latency.

Read-Your-Writes Problem

Under asynchronous replication, a client writes to the leader and immediately reads from a follower—potentially failing to see the just-written data. Solutions include: 1) Force reads to go to the leader for subsequent reads that have a causal relationship with the write; 2) Have followers return the current log position they have applied, and have the client specify a token in the next read request → the follower waits until it has applied >= token.

Multi-Leader (Multi-Master)

All nodes can accept write requests, replicating asynchronously to other nodes. Advantages: low write latency (no need to go through a leader) and continued write availability during network partitions (nodes within each partition can independently accept writes). Disadvantages: write conflicts.

Node A: write(x=1) → asynchronous replication → Node B
Node B: write(x=2) → asynchronous replication → Node A
→ Conflict! A sees (x=1 → x=2), B sees (x=2 → x=1)
→ Requires conflict resolution (LWW, Version Vectors, CRDTs — see 03-02)

Leaderless (Dynamo-style)

No leader role exists—writes are sent to multiple nodes, and reads also involve multiple nodes, with consistency guaranteed via quorums.

Dynamo (Amazon 2007) model:

• N: Total number of nodes to which data is replicated
• W: Number of nodes that must acknowledge a write (including the coordinator)
• R: Number of nodes that must participate in a read (including the coordinator)
• If R + W > N: Read and write quorums must overlap → at least one node has the latest data (ensuring linearizability)

Coordinator (arbitrary—client can connect directly or via load balancer to any node):
  write(key, value, context):
    1. Generate vector clock version
    2. Send concurrently to N replicas
    3. Wait for W-1 acknowledgments (plus self = W)
    4. Return OK to client

  read(key):
    1. Read concurrently from N replicas (send requests)
    2. Wait for R responses
    3. Select the value with the latest version (via vector clock comparison)
    4. If conflict detected (versions are incomparable) → return all conflicting siblings to client (application layer resolves)
    5. Asynchronous repair (read repair): coordinator writes the latest version back to lagging nodes

Hinted Handoff

If the coordinator cannot reach all N replicas, it temporarily stores the data in a "hint" on the coordinator's local node. When the target replica recovers, the coordinator forwards the hint. This ensures system availability continues during node failures.

Sloppy Quorum vs Strict Quorum

Strict quorum requires writes to be acknowledged by at least W of the N "target replicas." Sloppy quorum: availability is considered achieved as long as W nodes acknowledge in total (non-target nodes can step in)—this improves availability during node failures but may violate the consistency guarantees of R+W>N.

References

• Paper: "Dynamo: Amazon's Highly Available Key-value Store" (2007)
• Cassandra: cassandra.apache.org (a hybrid of Dynamo and BigTable)
• MySQL: Group Replication (based on Paxos, a single-leader variant)

Keywords: leader-based replication, multi-leader, leaderless, quorum, Dynamo, hinted handoff, read repair, sloppy quorum