Day 06 · System Design
CAP & PACELC Theorems (Consistency vs. Availability)
What a distributed data store must give up during a network partition, and what it trades off the rest of the time.
01Overview & core concept
In distributed systems, physical networks are unreliable: packets drop, latency spikes, and switches fail. The CAP Theorem (formulated by Eric Brewer) states that a distributed data store can simultaneously provide at most two of three guarantees. Because network partitions (P) are an unavoidable physical reality, systems must trade off between Consistency (CP) and Availability (AP) whenever a partition occurs.
Consistency (Linearizability)
Every read receives the most recent write or an error. All nodes see the exact same data at the same time.
Availability
Every non-failing node returns a non-error response for every request (without guaranteeing it contains the most recent write).
Partition Tolerance
The system continues to operate despite arbitrary message loss or network partitions between nodes.
02Architecture & request flow
Network Partition Occurs (P)
│
┌───────────────┴───────────────┐
▼ ▼
Choose Consistency (CP) Choose Availability (AP)
- Reject writes/reads if - Accept reads/writes on both
nodes cannot sync. sides of the partition.
- Preserves strict accuracy. - Nodes return potentially stale data;
- Sacrifices availability. reconcile conflicts later.Quorum replication (N=3, W=2, R=2)
Client Write (W=2) Client Read (R=2)
┌────────────┐ ┌────────────┐
│ Node A (✓) │ │ Node A (✓) │
──────┼────────────┼───► Overlap ◄───────┼────────────┼─────
│ Node B (✓) │ Guarantees │ Node B (✓) │
│ Node C ( ) │ Strong Read │ Node C ( ) │
└────────────┘ (W + R > N) └────────────┘The PACELC extension (Daniel Abadi)
Why it exists
CAP only describes behavior during network partitions. PACELC covers normal operation too: if there is a Partition, choose between Availability and Consistency; Else, choose between Latency and Consistency.
PC/EC (e.g., Google Spanner, etcd)
Chooses Consistency during partitions and pays higher Latency during normal operations to guarantee strict consistency.
PA/EL (e.g., Cassandra, DynamoDB)
Chooses Availability during partitions and optimizes for low Latency during normal operations using eventual consistency.
Quorum consensus mechanics
N, W and R
In tunable (Dynamo-style) systems, N is the total replicas for a data item, W is the replicas that must acknowledge a write, and R is the replicas that must respond to a read.
Strong consistency quorum (W + R > N)
The read set and write set are guaranteed to overlap on at least one replica holding the latest version (e.g., N=3, W=2, R=2).
Weak / eventual consistency (W + R <= N)
Reads might query replicas that missed recent writes, trading consistency for lower latency and higher availability.
03Real-world example: Amazon Shopping Cart (Dynamo) vs. Financial Ledger (Spanner)
AP / PA/EL: Amazon Cart
Amazon prioritized availability over consistency. If a partition isolates a data center, customers can still add items to their cart. The system accepts writes on both sides and resolves discrepancies later using Vector Clocks or application-level merges (e.g., union of both carts).
CP / PC/EC: Google Spanner / Banking Systems
Financial transactions cannot tolerate eventual consistency or duplicate debits. Spanner uses hardware atomic clocks and GPS receivers (the TrueTime API) alongside Paxos consensus to guarantee external consistency (serializability) across globally distributed datacenters, failing or blocking operations if a quorum cannot be reached.
04Architectural trade-offs
| System Classification | Primary Guarantee | Latency Profile | Example Technologies | Primary Use Cases |
|---|---|---|---|---|
| CP / PC/EC | Strict linearizability | Higher (requires multi-node synchronous consensus / Paxos / Raft) | etcd, ZooKeeper, Google Spanner, CockroachDB | Distributed locks, financial balances, leader election |
| AP / PA/EL | High availability & low latency | Sub-millisecond (async writes, local node reads) | Apache Cassandra, Amazon DynamoDB, CouchDB | Metrics ingestion, social media feeds, session shopping carts |
Failure modes & mitigations
Split-Brain Writes in AP Systems
Two disconnected partitions accept concurrent writes for the same key. When the partition heals, conflicts must be resolved via Last-Write-Wins (LWW), which risks data loss due to clock drift, or Conflict-Free Replicated Data Types (CRDTs).
Cascading Timeouts in CP Systems
If a quorum of nodes is unreachable, requests queue up and block, potentially exhausting connection pools across upstream microservices.
05Interview question & approach
You are designing a global ticket booking platform (like Ticketmaster) for high-demand concert tours. How would you choose between CP and AP models for seat reservations versus browsing event catalogs?
Domain-Driven Storage Separation
Seat reservation and checkout must be strictly consistent (CP): two users cannot reserve the same seat. Use a relational database with strict serializable isolation, distributed locks (Redis/Redlock or etcd), or a CP distributed database (e.g., CockroachDB). Event details, artist bios, and seat map layouts can be eventually consistent (AP), served via CDNs, read replicas, or distributed caches.
Handling Flash-Crowd Concurrency
Buffer checkout attempts using a partitioned message queue (e.g., Kafka keyed by event_id) to serialize booking attempts before they hit the CP transaction engine, preventing database thread exhaustion.
Graceful Degradation During Partitions
If cross-region connectivity drops, let users keep viewing events (AP), but show an informative message or queue screen for seat checkout until the CP quorum confirms partition recovery.