1 / 20
Sections
Slide 1
Module goal — design reliable replicated systems
Choose replication and consistency guarantees that protect application correctness while balancing latency, availability, and failures.
- Explain what a successful read or write guarantees across replicas.
- Predict stale reads, quorum behavior, and outcomes during network partitions.
- Use PostgreSQL, etcd, and CouchDB experiments to justify a consistency policy for your project.
- Try: python3 lab.py doctor
Open-source tools to try (1)
- Python setup
Read the linked section, then run the matching exercise in the classroom kit.
Slide 2
Replication in distributed systems
Replication maintains the same logical data on multiple networked nodes, which must propagate updates despite delays and failures.
- Replicas support failover, read scaling, and placing data near users.
- Propagation takes time; replicas can disagree temporarily or during a partition.
- Replication copies data; partitioning divides data. Replication does not replace backups.
- Try: python3 lab.py pg status
flowchart TD P[Primary accepts stock update] P -->|WAL records| R[Read replica] R -->|Possibly stale stock| C[Reader]
Writes go to the primary. The standby replays the log and may serve older state until it catches up.
Open-source tools to try (1)
- PostgreSQL replication
Read the linked section, then run the matching exercise in the classroom kit.
Slide 3
Log based replication
The primary records changes in a log. The replica receives that log and replays it into its own data pages.
- Open source: PostgreSQL streams write-ahead log (WAL) records to standbys.
- Commercial: Microsoft SQL Server Always On sends transaction log records to secondary replicas.
%%{init: {"flowchart": {"nodeSpacing": 16, "rankSpacing": 32, "padding": 6}, "themeVariables": {"fontSize": "22px"}}}%%
flowchart LR
C[Writer] -->|Write request| P
subgraph P[Primary]
direction TB
E[Transaction engine] -->|Generate WAL| L[Durable WAL log]
L -->|Log records| T[WAL sender]
E -->|Flush pages after WAL| D[Primary data pages]
end
P <-->|WAL to replica / progress to primary| S
subgraph S[Replica]
direction TB
R[WAL receiver] -->|Write and flush| W[Local WAL log]
W -->|Records in order| A[Replay process]
A -->|Apply changes| B[Replica data pages]
end
S -->|Read query result| Q[Reader] Inside each boundary, arrows show local work. The network carries WAL records to the receiver and progress feedback to the primary. Replica reads see replayed changes. Client acknowledgement depends on the replication mode shown next.
Open-source tools to try (3)
- SQL Server Always On replication
Compare SQL Server transaction log transport and replay with PostgreSQL WAL streaming.
- PostgreSQL replication components
Read Streaming Replication and Synchronous Replication. Match the WAL sender, receiver, and replay process to the diagram.
- PostgreSQL replication positions
Find pg_stat_replication. Compare sent_lsn, write_lsn, flush_lsn, and replay_lsn.
Slide 4
Asynchronous vs. synchronous replication
Compare when the primary acknowledges a commit and what waiting buys the application.
- Asynchronous — acknowledge after the primary commits; replica progress is not required.
- Synchronous — wait for the configured replica acknowledgement before reporting success.
- Pros — lower write latency; a slow or unreachable replica need not block primary writes.
- Pros — acknowledged writes reach the required replicas; remote_apply also waits for replay.
- Cons — stale replica reads; recent acknowledged writes may be lost if failover selects a lagging replica.
- Cons — extra network and replica latency; writes can block when required replicas are unreachable.
Open-source tools to try (1)
- PostgreSQL commit settings
Read the linked section, then run the matching exercise in the classroom kit.
Slide 5
Stale reads
A stale read returns an older version even though a newer write has completed elsewhere; acting on it can break application expectations.
- A saved profile appears unchanged; the user retries and may trigger duplicate side effects.
- Old stock can cause checkout to promise unavailable items if it skips an authoritative inventory check.
- Stale permissions can expose revoked access; authorize against the required current state.
- Pause replay, update the primary, and compare versions; choose freshness per operation.
- Try: python3 lab.py pg stale
Open-source tools to try (1)
- PostgreSQL replay controls
Read the linked section, then run the matching exercise in the classroom kit.
Slide 6
Eventual consistency with Apache Cassandra
Cassandra can accept a write before all replicas are current, then reconcile their state through delivery and repair.
- Example: replication factor 3 stores a profile on A, B, and C; C is temporarily unreachable.
- At write consistency ONE, A can acknowledge name=Sam while another replica still has name=Alex.
- A read at ONE from a stale replica can return Alex; ONE does not require read/write overlap.
- Hints, read repair, and scheduled anti-entropy repair help replicas converge after communication resumes.
- Cassandra offers tunable consistency; eventual consistency alone sets no freshness deadline.
Open-source tools to try (2)
- Cassandra replication and convergence
Read tunable consistency, timestamp reconciliation, and replica repair.
- PostgreSQL recovery
Read the linked section, then run the matching exercise in the classroom kit.
Slide 7
Read your writes — see your own saved changes
A session can require its next read to include its own completed update.
- Reading the primary is one option in this simple single-primary exercise.
- Another option waits for a replica to reach a known write position.
- Try: python3 lab.py pg stale
Open-source tools to try (1)
- PostgreSQL standby queries
Read the linked section, then run the matching exercise in the classroom kit.
Slide 8
Linearizable reads — respect completed writes across clients
A read started after a successful write must include that write or a later one.
- etcd uses linearizable reads by default.
- A concurrent write can still complete after the read’s logical point.
- Try: python3 lab.py etcd seed
Open-source tools to try (1)
- etcd read guarantees
Read the linked section, then run the matching exercise in the classroom kit.
Slide 9
Sequential and causal consistency
Sequential consistency orders all operations. Causal consistency preserves dependencies and can leave independent edits unordered.
- Sequential: preserve every client’s program order in one shared order.
- Causal: observing a reply requires observing the message it depends on.
- Try: python3 lab.py model histories; then python3 lab.py model causal
Open-source tools to try (2)
- Consistency and baseball
Read the linked section, then run the matching exercise in the classroom kit.
- Lamport on causal order
Read the linked section, then run the matching exercise in the classroom kit.
Slide 10
Quorums — why read and write sets must overlap
A quorum is the required number of replica responses for an operation to succeed; a majority quorum is more than half.
- N is the replica count; W is required write acknowledgements; R is required read responses.
- For N=3, W=2 stores the write on A and B; R=2 reading B and C intersects at B.
- R + W > N forces every read set to meet every completed write set in at least one replica.
- Without overlap, W=1 on A and R=1 on C can return an older value.
- The reader must reconcile versions; overlap alone does not ensure linearizability.
- Try: python3 lab.py model quorum
Open-source tools to try (1)
- Dynamo paper
Read the linked section, then run the matching exercise in the classroom kit.
Slide 11
etcd — coordination when the network partitions
etcd is a distributed key-value store for shared configuration and coordination; Kubernetes uses it to store cluster state.
- Raft replicates an ordered log so a majority can agree on committed state.
- The lab uses stock as a small key-value example; production etcd typically holds control-plane metadata.
- A partition blocks communication between live nodes; disconnect etcd3 while leaving it running.
- Two connected members can commit stock=9; the isolated member cannot commit writes or serve linearizable reads.
- Try: python3 lab.py etcd isolate
flowchart TD A[etcd1 accepts stock 9] <-->|Peer traffic| B[etcd2 stock 9] B -.->|Network disconnected| C[etcd3 local stock 10]
The majority can accept a new value. The isolated live member retains an older value and cannot satisfy a fresh linearizable read.
Open-source tools to try (2)
- What etcd does
See how etcd supports configuration, coordination, and Kubernetes cluster state.
- etcd cluster operations
Read the linked section, then run the matching exercise in the classroom kit.
Slide 12
CAP
During a partition, a replicated register cannot guarantee both linearizability and availability.
- C means one-copy behavior consistent with real-time order.
- A means every request to a non-failing node eventually completes successfully.
- Try: python3 lab.py model cap
Open-source tools to try (1)
- Gilbert and Lynch CAP proof
Read the linked section, then run the matching exercise in the classroom kit.
Slide 13
Availability choices
One operation can prefer fresh state while another tolerates older state.
- An isolated etcd member can serve a member-local read that may be stale.
- The same member cannot complete a fresh linearizable read without coordination.
- Try: python3 lab.py etcd reads
Open-source tools to try (1)
- etcd read modes
Read the linked section, then run the matching exercise in the classroom kit.
Slide 14
Recovery
Restoring connectivity allows replicas to catch up.
- Reconnect etcd3 and verify it now returns stock 9.
- Recovery needs evidence of convergence, not just a green process indicator.
- Try: python3 lab.py etcd heal
Open-source tools to try (1)
- etcd client recovery
Read the linked section, then run the matching exercise in the classroom kit.
Slide 15
PACELC
CAP focuses on partitions. PACELC also explains the tradeoff when the network is healthy.
- If a Partition occurs (P): choose between Availability (A) and Consistency (C).
- Else (E), during normal operation: choose between lower Latency (L) and stronger Consistency (C).
- Partition example: return older replica data, or wait/reject requests that require fresh data.
- Healthy network example: waiting for replica replay gives a stronger guarantee but can increase response time.
- Try: python3 lab.py pg latency
Open-source tools to try (1)
- Abadi explains PACELC
Read the linked section, then run the matching exercise in the classroom kit.
Slide 16
Conflicting writes
Two disconnected writers can create different children of the same document revision.
- Edit the cart independently on two CouchDB servers, then replicate.
- A default winning revision can hide another conflicting branch.
- Try: python3 lab.py couch conflict
flowchart TD S[Cart contains book] -->|Writer A adds pen| A[Branch A] S -->|Writer B adds notebook| B[Branch B] A -->|Replicate revision| C[CouchDB retains both branches] B -->|Replicate revision| C
Both writers start from the same revision. Replication preserves divergent revisions, so application logic must inspect and resolve the conflict.
Open-source tools to try (1)
- CouchDB conflicts
Read the linked section, then run the matching exercise in the classroom kit.
Slide 17
Conflict resolution
A merge rule must follow the meaning of the data.
- For this additions-only cart, union preserves both independent additions.
- Delete losing leaf revisions and replicate the resolved state.
- Try: python3 lab.py couch resolve
Open-source tools to try (1)
- CouchDB revision API
Read the linked section, then run the matching exercise in the classroom kit.
Slide 18
Mergeable state
Some data types have merge rules that tolerate repeats and reordering.
- A grow-only counter keeps one component per writer and merges using maximum.
- This rule preserves two independent increments without a shared read-modify-write.
- Try: python3 lab.py model merge
Open-source tools to try (1)
- CRDT introduction
Read the linked section, then run the matching exercise in the classroom kit.
Slide 19
Stale agent context
An AI agent can retrieve an old proposal even after a newer version receives approval.
- The vector index helps retrieval but does not authorize execution.
- The tool validates the exact version against authoritative approval state.
- Try: python3 lab.py model agent
Open-source tools to try (1)
- Milvus consistency options
Read the linked section, then run the matching exercise in the classroom kit.
Slide 20
Apply replication and consistency to your class project
Choose guarantees per operation, then demonstrate how your project behaves when a replica lags or a network link fails.
- Booking or commerce: protect no-double-booking or no-overselling with an atomic authoritative write; a fresh read alone is insufficient.
- Feeds or analytics: allow measured staleness where safe; show freshness and provide read-your-writes after edits.
- Collaborative apps: define how concurrent edits merge; document which changes could be lost.
- AI agents: recheck permissions and inventory before actions when retrieved context may be stale.
- Pick one operation; state its invariant, staleness budget, partition response, and recovery policy.
- Inject lag or a partition, record latency and correctness, and justify your choice in the consistency memo.
Open-source tools to try (1)
- PostgreSQL replication review
Read the linked section, then run the matching exercise in the classroom kit.