CMPE273 · Module 8

Replication, Consistency, CAP, and PACELC

Use PostgreSQL, etcd, and CouchDB to observe stale reads, quorum behavior, and write conflicts, then choose explicit consistency and availability guarantees.

Learning Objectives

  1. Trace a write through primary and replica acknowledgement points.
  2. Reproduce a stale read and explain read-your-writes and eventual convergence.
  3. Compare linearizable, sequential, and causal consistency using small histories.
  4. Explain quorum overlap and its limits.
  5. Apply CAP during a partition and PACELC during normal operation.
  6. Observe concurrent revision conflicts and apply an explicit merge policy.
  7. Select a consistency policy for one project operation using experimental evidence.

Core Concepts

Replication

Maintain copies of the same logical data on multiple nodes.

Stale read

A read that omits a relevant completed update.

Linearizability

An operation appears to occur at one point between its invocation and response, preserving real-time order.

Read your writes

A session observes its own completed writes in subsequent reads.

Eventual consistency

Replicas converge once updates stop and propagation and repair succeed.

Quorum

A required subset of replicas participating in an operation.

CAP

Under a partition, linearizability and availability cannot both be guaranteed for a replicated register.

PACELC

During partitions consider availability versus consistency; otherwise consider latency versus consistency.

Diagrams

A primary and a read replica

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.

The log connects the primary and the replica

%%{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.

Two connected members and one isolated member

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.

Two edits from a shared cart revision

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.

Examples, Discussions, and Project Ideas

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.

Exercise 1 and expected result

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
Open-source tools to try (1)

Exercise 2 and expected result

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.
Open-source tools to try (3)

Exercise 3 and expected result

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)

Exercise 4 and expected result

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)

Exercise 5 and expected result

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)

Exercise 6 and expected result

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)

Exercise 7 and expected result

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)

Exercise 8 and expected result

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)

Exercise 9 and expected result

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.

Exercise 10 and expected result

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
Open-source tools to try (2)

Exercise 11 and expected result

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)

Exercise 12 and expected result

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.

Exercise 13 and expected result

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)

Exercise 14 and expected result

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)

Exercise 15 and expected result

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
Open-source tools to try (1)
  • CouchDB conflicts

    Read the linked section, then run the matching exercise in the classroom kit.

Exercise 16 and expected result

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)

Exercise 17 and expected result

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.

Exercise 18 and expected result

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)

Exercise 19 and expected result

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)

Exercise 20 and expected result

Canvas remains the official source for project requirements, deadlines, submissions, and grading.

Key Takeaways

Lab Links