Foundations · Phase 1: Foundations
CAP Theorem & PACELC Framework
Formalize Gilbert & Lynch’s CAP proof, dissect why network partitions cannot be avoided, and adopt Daniel Abadi’s PACELC model for real-world databases.
Primary specification: Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services (Gilbert & Lynch)
Lesson 7 of 33
1d streakThe Architectural Question
System designers mistakenly treat CAP as "choose 2 of 3", believing they can choose Consistency and Availability by ignoring network partitions.
Core Engineering Objectives
- The formal proof: partitions (P) mandate choosing between Consistency (C) and Availability (A)
- PACELC extension: If Partition (P) choose A or C; Else (E) choose Latency (L) or Consistency (C)
- Real-world system categorization: Dynamo/Cassandra (PA/EL) vs MongoDB/HBase (PC/EC) vs Spanner
1. What is it & Why it Matters
The CAP theorem (Brewer, 2000) states that in any distributed data store connected across a network, you can simultaneously guarantee at most two of three properties: - Consistency (C): Every read receives the most recent write or an error. - Availability (A): Every non-failing node returns a non-error response. - Partition Tolerance (P): The system continues operating despite dropped or delayed messages between nodes.
The "Pick Any Two" Myth
1. 1. One write
A customer changes an account balance.
2. 2. Healthy link
Replica A and Replica B can coordinate, so both agree.
3. 3. Partition
The network link fails; A and B cannot confirm the same state.
4. 4. CP choice
Pause or reject the write so a read never lies.
5. 5. AP choice
Accept the write locally, then reconcile differences later.
The partition is the trigger. CAP is not “pick two features”; it is the behavior you choose while coordination is impossible.
2. CP vs. AP: What Happens When the Network Breaks
| Strategy | Node Behavior Under Partition | Primary Risk / Trade-Off | Representative Systems |
|---|---|---|---|
| CP (Consistency over Availability) | Nodes on the minority side refuse reads/writes to prevent stale updates. | Clients receive HTTP 500 errors or timeouts until the partition heals. | Google Spanner, CockroachDB, etcd, MongoDB (majority write) |
| AP (Availability over Consistency) | Nodes on both sides continue accepting reads and writes locally. | Replicas diverge (split-brain), requiring conflict resolution when healed. | Apache Cassandra, ScyllaDB, Amazon DynamoDB (default), CouchDB |
3. PACELC: What Happens in Normal Operation
CAP only describes database behavior when the network is broken. Daniel Abadi’s PACELC theorem completes the model by explaining what happens during normal operation: If Partition (P): Choose Availability or Consistency; Else (E): Choose Latency or Consistency.
| Database | PACELC Type | During Partition (P) | During Normal Operation (E) |
|---|---|---|---|
| Cassandra / DynamoDB | PA / EL | Available (accepts writes locally) | Latency (reads from nearest local replica without waiting) |
| MongoDB (majority write) | PC / EC | Consistent (pauses writes if primary isolated) | Consistency (waits for majority quorum acknowledgment) |
| Google Cloud Spanner | PC / EC | Consistent (aborts transactions if Paxos lost) | Consistency (synchronous multi-region Paxos commit) |
| PostgreSQL (Async Replica) | PA / EL | Available (replicas continue serving reads) | Latency (primary commits without waiting for replica WAL flush) |
Architectural Boundary · Do Not Confuse
PA / EL (Prioritize Availability & Low Latency)
PC / EC (Prioritize Correctness & Consistency)
PA/EL systems minimize latency on every request by avoiding cross-node synchronization rounds. PC/EC systems accept higher latency and partition downtime to ensure data is never lost or stale.
4. Decision Guide & Whiteboard Rule
- 01Choose CP / PC/EC when designing financial transactions, inventory reservation, authentication permissions, or distributed locks where stale reads lead to business loss.
- 02Choose AP / PA/EL when designing social feeds, video metadata, real-time chat presence, or high-volume IoT metrics where 100% uptime outweighs momentary data staleness.
Use it when
Classify databases using PACELC rather than CAP in interviews: it demonstrates you understand steady-state latency costs, not just disaster-state partition failures.
Reconsider when
Never describe an entire database product as purely "CP" or "AP" without specifying its configuration (e.g., Cassandra with QUORUM reads/writes behaves as CP; MongoDB with unacknowledged writes behaves as AP).
5. Active Recall Checkpoint
Active Recall Checkpoint
Why is it inaccurate to say a distributed database can choose "CA" (Consistency and Availability without Partition Tolerance)?
Hint: Think about physical network cables, switches, and what happens when two nodes cannot communicate.
Show answer & explanation
In any network connecting multiple physical machines, network partitions (dropped packets, severed links, switch crashes) are physical inevitabilities, not optional configurations. A system that cannot tolerate partitions is simply a single machine. The moment you distribute data across multiple servers, you must handle partitions by choosing between returning errors (CP) or returning potentially stale data (AP).
Production Postmortem & Verification
Production Incident Postmortem
- Trigger / Setup: An active-active multi-datacenter relational cluster chooses "CA" and continues accepting writes during an inter-DC fiber cut.
- Production Symptom: Split-brain disaster: both partitions accept conflicting updates to the same account balance, creating irrecoverable financial corruption.
- Root Cause & Fix: Network partitions are physical inevitabilities; systems must explicitly reject writes (CP) or accept reconciliation divergence (AP).
Acceptance Criteria & Outcomes
- Prove why "CA" is an impossible architecture across physical distributed networks.
- Define PACELC trade-offs across steady-state execution and split-network partitions.
- Categorize flagship open-source and cloud datastores according to their PACELC behavioral profile.
Architectural & Technical Interview Review
Core FAANG Interview Questions
Q01How do you justify introducing CAP Theorem & PACELC Framework into a high-scale production architecture?Click to reveal model answer →Hide answer ↑Requirements & Design Brief
Introduce CAP Theorem & PACELC Framework only when measured scale, data size, or failure boundaries exceed single-node capacity. State the exact bottleneck, evaluate operational overhead, and verify that the trade-offs justify the added moving parts.
Q02What is the primary trade-off and hidden operational cost of CAP Theorem & PACELC Framework?Click to reveal model answer →Hide answer ↑Architecture Trade-offs
It improves scalability and availability, but introduces network hops, serialization overhead, and eventual consistency or coordination complexity.
Q03How do you handle catastrophic failure or dependency degradation in CAP Theorem & PACELC Framework?Click to reveal model answer →Hide answer ↑Failure Review & Recovery
Implement connect/read timeouts, exponential backoff with jitter, and fallback defaults so downstream degradations do not cause cascading outages.
Production Pitfalls & Anti-Patterns
Critical Failure Anti-Patterns
Premature Distributed Complexity
Scattering distributed components before identifying concrete write, read, or storage limits creates accidental points of failure and operational debt.
Production Mitigation: Start with the simplest modular design that satisfies requirements, evolving it only as measured constraints dictate.
Unbounded Retries and Cascading Storms
When a dependency degrades, immediate synchronized retries multiply downstream traffic, turning a minor slowdown into a total fleet outage.
Production Mitigation: Enforce strict retry budgets, exponential backoff, and full randomized jitter on all client calls.
Neglecting Observability and Metrics
Deploying architecture without distributed tracing or p99 tail latency alerts leaves engineers blind when partial partitions occur.
Production Mitigation: Export metrics for request rate, error rate, p95/p99 duration, and saturation at every service boundary.