System Design - Theory
CAP Theorem
The CAP theorem is one of the most fundamental results in distributed systems theory. It defines the inherent trade-offs every distributed system must make, and understanding it is essential for making informed architectural decisions.
- Consistency - Every read returns the most recent write
- Availability - Every request receives a response
- Partition Tolerance - System continues operating despite network failures
Distributed systems are not about choosing the right answer - they are about choosing the right trade-off.
The CAP Theorem
What Each Guarantee Means
Consistency
Availability
Every non-failing node must return a response. The system cannot refuse to serve requests, even if some nodes are down or unreachable.
Partition Tolerance
The system must continue to function when network partitions occur. Since networks are inherently unreliable, partition tolerance is not optional in practice.
Why You Cannot Have All Three
Real-World Systems by CAP Choice
CP Systems (Consistency + Partition Tolerance)
| System | Description |
|---|---|
| HBase | Distributed column-store, strong consistency |
| MongoDB (default) | Document database with majority write concern |
| ZooKeeper | Distributed coordination, consensus-based |
| etcd | Key-value store using Raft consensus |
| Google Spanner | Globally distributed, externally consistent |
AP Systems (Availability + Partition Tolerance)
| System | Description |
|---|---|
| Cassandra | Distributed wide-column, eventual consistency |
| DynamoDB | AWS key-value store, eventually consistent reads |
| CouchDB | Document database with multi-master replication |
| Riak | Distributed key-value, eventually consistent |
| DNS | Eventually consistent, highly available |
CA Systems (Consistency + Availability)
Consistency Models
Consistency Spectrum
| Model | Description | Systems |
|---|---|---|
| Linearizable | Strongest; reads return latest write | Spanner, ZooKeeper |
| Sequential | Operations appear in some sequential order | Raft, Paxos |
| Causal | Preserves causal relationships | MongoDB (causal sessions) |
| Eventual | All replicas converge eventually | Cassandra, DynamoDB |
| Weak | No ordering guarantees | DNS, some NoSQL defaults |
PACELC Theorem
The PACELC theorem extends CAP by considering what happens when there is no partition.
PACELC Classification
| System | Partition | Else | Classification |
|---|---|---|---|
| Cassandra | A | L (latency) | EL |
| DynamoDB | A | L | EL |
| MongoDB | C | C (strong consistency) | PC/EC |
| HBase | C | C | PC/EC |
| CockroachDB | C | C | PC/EC |
| Cosmos DB | Configurable | Configurable | Configurable |
Eventual Consistency
Convergence Time
Conflict Resolution
When replicas diverge, conflicts must be resolved:
| Strategy | Description | Trade-off |
|---|---|---|
| Last-Writer-Wins (LWW) | Timestamp-based, latest wins | Simple, may lose writes |
| Vector Clocks | Track causal ordering | Complex, requires metadata |
| CRDTs | Conflict-free replicated data types | Automatically convergent |
| Application logic | Business rules resolve conflicts | Flexible, but complex |
Practice Exercises
-
Analysis: For each of the following systems, classify as CP, AP, or CA and explain your reasoning: (a) a banking system, (b) a social media feed, (c) a DNS system, (d) a stock trading platform.
-
Trade-offs: You are designing a global user profile service. Users can update their profile from any region. Which CAP choice would you make? How does PACELC influence your decision?
-
Design: Design a distributed counter that supports concurrent increments from multiple regions. What consistency model would you use? How do you handle conflicts?
-
Theory: Prove that during a network partition, a system cannot simultaneously guarantee both consistency and availability. Use a two-node example.
What to Learn Next
-> Introduction to System Design Core principles, the design process, and trade-offs.
-> Databases SQL vs NoSQL, indexing, replication, and sharding.
-> Caching Strategies Redis, Memcached, cache invalidation, and write strategies.
-> Microservices Service decomposition, discovery, and API gateways.
-> Scalability Fundamentals Vertical vs horizontal scaling and capacity planning.
-> Load Balancing Algorithms, health checks, and L4 vs L7.