SD7.1 · LESSON 1 OF 6

Replication paths

Compare consistency contracts and distribute data while tracing stale reads, partitions and hot keys.

THE IDEA

Replication paths

Replicas protect data and spread reads, but when does a write count as done? With asynchronous replication the leader acknowledges after storing the write itself: fast (5 ms here) but only one copy exists, followers lag, and a leader crash can lose an acknowledged write. With synchronous replication to one follower the acknowledgement waits for a second copy (25 ms in the example), so a failover keeps the write. Say precisely which condition your "durable" refers to.

copies required before acknowledging1

leader: v1follower 1: behindfollower 2: behind

Step 1 of 4

1. client sends write v1 to the leader

What "persisted" or "replicated" means depends on when the write is acknowledged. Asynchronous replication is fast but followers lag and an acknowledged write can be lost; synchronous waiting makes it durable on more nodes at the price of latency.

Choose how many copies to wait for, and crash the leader.

Predict first. Can an asynchronous follower lag after a successful leader write?

Chapter context

Replication copies data for resilience or read capacity; partitioning assigns different data to different owners. Both introduce coordination and failure behavior that an application must explicitly account for.

TRY IT YOURSELF

Part 1. Do it hands-on

Count copies and latency by hand, then simulate a leader with followers.

copies required before acknowledging1

leader: v1follower 1: behindfollower 2: behind

Step 1 of 4

1. client sends write v1 to the leader

copies at ack, asynchronous copies at ack, 1 synchronous follower ack latency with it (ms) async followers can lag? (yes/no)

To do: One leader and two followers. With ASYNCHRONOUS replication the write is acknowledged once the leader has it. Copies of the write that exist at the moment of the acknowledgement?
To do: With SYNCHRONOUS replication to one follower (acknowledge after the leader and one follower have it), copies at the acknowledgement?
To do: The leader write takes 5 ms and the follower round trip 20 ms (done one after the other). Acknowledgement latency with one synchronous follower?
To do: Can an asynchronous follower lag after a successful leader write? Type yes or no

Part 2. Do it in code

class Cluster(n_followers): self.replicas is a list: index 0 is the leader, then the followers; each replica is {"value": None, "version": 0}.
write(value, acks): the leader applies the write first; then the first (acks − 1) followers apply it before the call returns (synchronous part). acks=1 is fully asynchronous. Return the number of copies that exist at the moment of return. ValueError if acks is below 1 or above the number of replicas. The version is the previous leader version + 1.
replicate_rest(): apply the latest write to every replica that is behind (the background replication catching up). Return how many replicas were updated.
lag(): the number of replicas whose version is below the leader's.
read(i): the value at replica i.
ack_latency_ms(leader_ms, follower_rtt_ms, acks): leader_ms + follower_rtt_ms if acks > 1 (one follower round trip, assumed sequential) else leader_ms.
survivors_after_leader_crash(): the values on replicas 1…n if the leader dies right now (the leader is not consulted).

class Cluster:
    def __init__(self, n_followers):
        self.replicas = [{"value": None, "version": 0} for _ in range(n_followers + 1)]

    def write(self, value, acks):
        pass

    def replicate_rest(self):
        pass

    def lag(self):
        pass

    def read(self, i):
        pass

    def survivors_after_leader_crash(self):
        pass

def ack_latency_ms(leader_ms, follower_rtt_ms, acks):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Can an asynchronous follower lag after a successful leader write?

AYesBNo

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

For fixed sets over N replicas, $|R\cap W|\ge |R|+|W|-N$ . Thus R=W=3 with N=5 forces at least one shared member. This is a set fact, not a complete consistency proof. Shard and replication counts describe different dimensions of the layout.

Worked example

Five replicas use read sets and write sets of size three. The lower bound on overlap is 3+3−5=1. Enumerating all three-member sets confirms every pair overlaps. A read still needs the right version-selection and concurrency rules; intersection alone does not tell which stored value is newest or committed.

Reference code

The following example uses the Python standard library and does not call a remote service.

from itertools import combinations
replicas=set(range(5))
sets=[set(x) for x in combinations(replicas,3)]
assert min(len(r&w) for r in sets for w in sets) == 1
assert 3+3-5 == 1
assert all(r&w for r in sets for w in sets)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Quorum arithmetic does not establish a full consistency contract. Sharding is not replication. CAP availability is a precise failure-model property, not the same as an ordinary monthly uptime percentage.