HLD · Theory
CAP Theorem & Consistency Models
Trade-offs when a distributed system faces network partitions.
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 practice P is mandatory (networks fail). So you choose CP or AP during a partition.
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 | Accept reads/writes; reconcile later | Cassandra, DynamoDB (configurable), DNS |
Bank balance: Prefer CP — better to error than show wrong balance. Social like count: AP acceptable — eventual consistency OK.
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.
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)
N replicas. Write succeeds if W nodes ack; read consistent if R nodes read and W + R > N.
Example: N=3, W=2, R=2 → tolerate 1 node failure with strong-ish consistency.
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).
- P is not optional in distributed systems.
- Models: Strong → eventual; know read-your-writes for UX.
- Quorum: W + R > N for read-write overlap.
- Match product: Money = CP; likes/views = AP/eventual.