10. Replication & Consistency Models

10.1 Three replication topologies

10.2 Quorums

With N replicas, a write waits for W acknowledgements and a read queries R replicas. If R + W > N, every read quorum overlaps every write quorum, so it sees at least one copy of the latest write.

N=3, W=2, R=2  → overlap guaranteed; tolerates 1 node down for both reads and writes
N=3, W=1, R=1  → fastest, may read stale data
N=3, W=3, R=1  → fast reads, but writes fail if any node is down

The caveats show depth: sloppy quorums with hinted handoff can break the overlap guarantee; concurrent writes still need conflict resolution; and "R+W>N" alone does not give linearizability without extra mechanisms (read repair before returning, etc.).

10.3 CAP and PACELC, stated correctly

CAP: during a network Partition, a system must choose between Consistency (refuse some requests) and Availability (answer with possibly stale or conflicting data). It is not "pick two of three": partitions aren't optional.

PACELC is more useful in practice: if Partitioned, choose A or C; Else (normal operation), choose Latency or Consistency.

10.4 The consistency spectrum

Strongest ──────────────────────────────────────────────────────────▶ Weakest
Linearizable → Sequential → Causal → Read-your-writes / Monotonic reads → Eventual
(single-copy     (global order   (cause before   (session guarantees)       (converges
 illusion,        but not real-   effect)                                     eventually)
 real-time)       time)

Pick per operation, not per system. In a social app:

• Username uniqueness, payments, inventory decrement: linearizable (or a serializable transaction).
• Seeing your own new post: read-your-writes.
• Comment replies appearing after the comment they reply to: causal.
• Like counts, view counts, follower counts: eventual.

10.5 Conflict resolution

10.6 🏗️ Flow: quorum write, stale read, and read repair (N=3, W=2, R=2)

 Write v2 (W=2)                          Read (R=2)
 ──────────────                          ──────────
 Coordinator ──v2──▶ A ✓                 Coordinator ──▶ A: v2 (ts 105)
             ──v2──▶ B ✓  → ack client               ──▶ C: v1 (ts 100)   (C missed the write)
             ──v2──▶ C ✗ (down → hint stored on D)    → return v2 (newest)
                                                      → READ REPAIR: send v2 to C
 Later: C returns → D replays hint (hinted handoff)
 Background: Merkle-tree anti-entropy finds remaining differences

Multi-leader conflict timeline:

 US region:  title="Q3 plan"  at t=100 ──┐
 EU region:  title="Q3 Plan v2" at t=101 ─┼─ async replication crosses ─▶ both regions see 2 versions
 LWW → keeps "Q3 Plan v2" (higher ts) — the US edit silently vanishes.
 If EU's clock is 5 s behind, the *older* edit may win. Clock skew = data loss under LWW.

10.7 🌍 In production

• Amazon Dynamo (2007): vector clocks and client-side merge for the cart. The paper openly says deleted items could reappear. That was a deliberate business trade-off.
• Azure Cosmos DB exposes five consistency levels: Strong, Bounded Staleness, Session (the default: read-your-writes within a session token), Consistent Prefix, and Eventual. It's a good real-world example that consistency is a per-workload product choice, priced and documented.
• Google Spanner: external consistency through TrueTime (§19.4). It's the "pay latency for strong consistency" end of PACELC.
• Facebook TAO (2013): a graph cache over MySQL with read-after-write consistency within a region (writes go through the cache tier) and eventual consistency across regions, which is enough for a social graph.
• Jepsen (Kyle Kingsbury) has tested many databases and found consistency claims that didn't hold under partitions. Use it as an interview reference: "I'd check the Jepsen analysis before trusting the documented guarantee."

10.8 ⚠️ Corner cases & deep details

• R + W > N is not linearizable by itself. Concurrent read and write can return new-then-old values to two readers. You need read repair before returning, or a consensus-based design.
• Sloppy quorums (writes accepted by substitute nodes during failures) keep you available, but the quorum overlap guarantee is gone until hints are delivered.
• Zombie data: a delete is a tombstone. If a replica is down longer than the tombstone grace period and repair never runs, the deleted data comes back when that replica returns.
• Session guarantees across devices: read-your-writes on a phone doesn't carry over to the laptop unless the session token or position is shared via the user account.
• Causality across services: a comment is stored in service A and the post it replies to in service B. A reader can see the comment before the post. Fix it by carrying causal metadata (a version or position) and making readers wait for, or filter on, missing dependencies.
• Uniqueness checks against replicas: "is this username taken?" checked on a lagging replica returns "free" for a name that was just taken. Uniqueness checks must hit the linearizable source (primary or uniqueness table).
• CRDT metadata growth: OR-Sets keep tombstones or unique tags, and text CRDTs keep per-character IDs. Without garbage collection, which itself needs coordination, documents grow without bound.