HLD · Theory

CAP Theorem & Consistency Models

Trade-offs when a distributed system faces network partitions.

In simple words: When database nodes cannot talk to each other, the system must either reject some requests or risk returning stale data. The correct choice depends on what the product can safely tolerate. Example: during a network split, an AP system may still show a $100 bank balance on one replica while another already recorded a $40 withdrawal; a CP system would reject the read instead of showing the wrong amount.

1. CAP theorem (correct framing)

During a network partition, a distributed data store cannot simultaneously provide all three:

C — Consistency: Every read sees the latest write (or fails).
A — Availability: Every request gets a non-error response (may be stale).
P — Partition tolerance: System continues despite dropped messages between nodes.

In a distributed system, network partitions can happen and must be handled. During a partition, the system chooses between preserving consistency (CP) and preserving availability (AP).

Interview correction: CAP is not “pick any two at all times.” The consistency-versus-availability choice appears when a partition exists.

2. CP vs AP examples

Choice	Behavior on partition	Example systems
CP	Reject writes/reads to avoid stale data	ZooKeeper, etcd, HBase, traditional RDBMS with sync replication
AP	Continue serving some requests; reconcile divergent data later	Cassandra with suitable consistency settings, Dynamo-style stores, DNS

Bank balance: Prefer CP — better to error than show wrong balance. Social like count: AP acceptable — eventual consistency OK.

2b. Partition timeline (simple example)

Two database replicas: Node A and Node B. Network split between them.

t0: Both in sync. Balance = $100.
t1: Partition happens. User writes on Node A: withdraw $40 → balance $60 on A.
t2: User reads from Node B (AP system) → still sees $100 (stale).
t3: Partition heals → replicas reconcile (merge / last-write-wins / conflict resolution).

CP system at t2 would reject the read or write on the minority side rather than return stale data.

3. Consistency models (spectrum)

Strong consistency: Read always returns latest write. Hard globally; often single leader.
Eventual consistency: Replicas converge if no new writes; window of staleness.
Read-your-writes: User always sees their own updates (session stickiness or routing to primary).
Monotonic reads: User never sees time go backward across reads.
Causal consistency: Causally related ops seen in order; unrelated ops may differ.

Concrete example: After changing a profile photo, read-your-writes consistency ensures that you see the new photo immediately in your own session, even if other users briefly see the old cached copy.

4. PACELC extension

If Partition → choose A or C. Else (normal operation), choose Latency or Consistency.

Example: DynamoDB — AP under partition; in normal ops tunable (strong vs eventual read).

5. Quorum reads/writes (Dynamo-style)

With N replicas, a write waits for W acknowledgements and a read asks R replicas. When W + R > N, the read and write sets overlap. The system still needs version handling to return the newest value.

Example: With N=3, W=2, and R=2, every successful read set overlaps the last successful write set by at least one replica.

6. Real interview scenario

Design a shopping cart across 2 data centers:

Cart is per-user — route user to home DC (geo-DNS) for read-your-writes
Cross-DC async replication for disaster recovery (eventual)
Checkout hits payment service with strong consistency on inventory (CP, single leader)

Quick revision

CAP: Under partition, choose CP (consistent) or AP (available).
Partitions: Distributed systems must define how they behave when nodes cannot communicate.
Models: Strong → eventual; know read-your-writes for UX.
Quorum: W + R > N creates read-write overlap; version handling is still needed.
Match product: Money = CP; likes/views = AP/eventual.