System Design Key Concepts
What is CAP Theorem?
When you store data across multiple servers (a distributed system), you run into a fundamental problem. The CAP Theorem says you can only guarantee two out of three properties at the same time:
- C - Consistency
- A - Availability
- P - Partition Tolerance
This was proposed by Eric Brewer in 2000 and formally proven in 2002. It applies to any system where data is replicated across multiple nodes.
Before we dig into the trade-off, let's understand what each property actually means. These words get thrown around a lot, but their precise meaning in CAP is specific.
What is Consistency?
Consistency means every read gets the most recent write. No matter which server you talk to, you see the same data.
Imagine you update your profile picture. With consistency, anyone who views your profile after that update will see the new picture. It doesn't matter if they're hitting a different server in a different data center. They all see the latest version.
Example: You have $500 in your bank account. You withdraw $100. Consistency means every ATM and every app will immediately show $400. No ATM will still show $500 after the withdrawal.
If a system is NOT consistent, one ATM might show $400 while another still shows $500. That's a problem if you try to withdraw from both.
Don't confuse with ACID
CAP consistency is not the same as ACID consistency. In ACID, consistency means the database moves from one valid state to another (no broken constraints). In CAP, consistency means all nodes see the same data at the same time. Different concepts, same word.
What is Availability?
Availability means every request gets a response. The system never refuses to answer. It might return slightly old data, but it never returns an error or times out.
Think of Google Search. Even if some of Google's servers are down, you still get search results. The results might be a few seconds stale, but you never see "Service Unavailable". That's availability.
Example: Your social media feed. If one server goes down, the system routes your request to another server. You might see a post that's 5 seconds old instead of the absolute latest, but the feed still loads. The alternative (showing an error page) would be much worse for the user.
What is Partition Tolerance?
A network partition happens when two servers can't talk to each other. The network cable between them breaks, a router fails, or there's a timeout. The servers are still running, but they can't communicate.
Partition tolerance means the system keeps working even when this happens. It doesn't crash or shut down just because some nodes are cut off from each other.
Example: You have servers in Mumbai and Singapore. An undersea cable gets damaged. The two data centers can't talk to each other. A partition-tolerant system keeps serving users from both locations, even though the two halves can't sync with each other.
A system that is NOT partition tolerant would just stop working entirely until the network is fixed.
P is not optional
In any distributed system, network failures WILL happen. Cables get cut, routers crash, packets get lost. You cannot prevent partitions. This means Partition Tolerance is not optional. You always need P.
So the real question is not "pick any two." It's: when a partition happens, do you choose Consistency or Availability?
The Real Trade-off: CP vs AP
Since partition tolerance is mandatory, every distributed system falls into one of two categories when a partition occurs:
CP (Consistency + Partition Tolerance): The system refuses to respond rather than return stale data. It might show an error, but it will never show wrong data.
AP (Availability + Partition Tolerance): The system always responds, even if the data might be slightly outdated. It prefers showing something over showing nothing.
CP Systems: Correctness Over Uptime
A CP system's philosophy: "I'd rather show an error than show wrong data."
When a partition happens, the system stops accepting requests until it can guarantee that all nodes are in sync. This means some users will see errors or timeouts during the partition, but nobody will see incorrect data.
How it works: Most CP systems use a quorum. Before confirming a write, the data must be replicated to a majority of nodes (e.g., 3 out of 5). If the system can't reach a majority because of a partition, it rejects the write.
Similarly, reads go to a majority of nodes to make sure you're reading the latest data. If a majority isn't reachable, the read fails.
When to choose CP:
- Banking and payments: You can't show a balance of $500 if the user just spent $400. Showing an error is better than showing wrong money.
- Inventory/ticketing: You can't sell the last concert ticket to two different people. Better to block purchases temporarily.
- Leader election: Coordination services like ZooKeeper and etcd must agree on exactly one leader. A wrong answer breaks the whole system.
Real CP databases: PostgreSQL (with synchronous replication), MongoDB (with majority write concern), HBase, ZooKeeper, etcd, Google Spanner.
AP Systems: Uptime Over Correctness
An AP system's philosophy: "I'd rather show old data than show nothing."
When a partition happens, every node keeps accepting reads and writes independently. The nodes might have different versions of the data temporarily, but the system never goes down. Once the partition heals, the nodes sync up.
How it works: Each node stores its own copy of the data and responds to requests on its own. When the partition is resolved, the system uses conflict resolution to merge the diverged data. Common strategies:
- Last-write-wins: The most recent write (by timestamp) is kept. Simple but can lose data.
- Vector clocks: Track the version history to detect and resolve conflicts.
- Application-level resolution: The application decides how to merge (e.g., merge shopping cart items).
When to choose AP:
- Social media feeds: If your feed is 5 seconds behind, nobody notices. If the feed doesn't load at all, users leave.
- Product catalogs: Showing a price that's a few seconds old is fine. Blocking all shoppers is not.
- Like/view counters: An approximate count is good enough. Exact real-time accuracy doesn't matter.
- DNS: The entire internet's domain name system is AP. DNS records propagate gradually, and stale entries are acceptable.
Real AP databases: Cassandra, DynamoDB, CouchDB, Riak, Redis (default mode).
CP vs AP at a Glance
| CP System | AP System | |
|---|---|---|
| During a partition | Rejects requests (error/timeout) | Keeps serving (maybe stale data) |
| Priority | Data correctness | System uptime |
| Risk | Downtime during partitions | Stale or conflicting data |
| Conflict handling | Prevents conflicts (quorum) | Resolves conflicts after the fact |
| Best for | Money, inventory, coordination | Feeds, caching, counters, search |
| Examples | PostgreSQL, ZooKeeper, HBase | Cassandra, DynamoDB, CouchDB |
What About CA (No Partition Tolerance)?
In theory, a CA system provides both consistency and availability but does not handle partitions. In practice, this only works on a single machine (like a standalone PostgreSQL or MySQL instance).
A single-node database is technically CA because there's no network between nodes, so partitions can't happen. But the moment you add a second node for replication or scaling, you're in a distributed system and partitions become possible. CA stops being an option.
Interview tip
If an interviewer asks about CA systems, the answer is: "CA only exists in single-node systems. Any distributed system must handle partitions, so the real choice is between CP and AP."
Eventual Consistency
Most AP systems use eventual consistency. This means: if no new writes happen, all nodes will eventually converge to the same value. The data isn't immediately consistent, but it gets there given enough time.
Think of it like this: you post a photo on Instagram. Your friend in another country might not see it for a few seconds because the data hasn't replicated to their nearest server yet. But after a short delay, they see it too. The system is eventually consistent.
How long is "eventually"? Usually milliseconds to a few seconds. In healthy systems with no partitions, replication is nearly instant. The delay only becomes noticeable during network issues or high load.
Levels of consistency (from strongest to weakest):
| Level | What it means | Example |
|---|---|---|
| Strong consistency | Every read sees the latest write. Always. | Bank balance after a transfer |
| Linearizability | Strong consistency + operations appear in real-time order | Distributed locks (ZooKeeper) |
| Causal consistency | If A caused B, everyone sees A before B. Unrelated writes may appear in any order. | Chat messages in a thread |
| Eventual consistency | Reads might return old data, but all nodes converge eventually | Social media likes, DNS |
| Weak consistency | No guarantee reads will ever see a specific write | Memcached, best-effort caching |
Real-World Example: What Happens During a Partition
Let's walk through a concrete scenario. You have two database nodes, Node A (Mumbai) and Node B (Singapore). A network cable between them gets cut.
User in Mumbai updates their address to "123 New Street" on Node A. User in Singapore reads the same profile from Node B.
If the system is CP: Node A accepts the write but can't replicate to Node B (partition). The system blocks the read from Node B because it can't confirm the data is up to date. The Singapore user sees a timeout or error. The Mumbai user's write may also be rejected if quorum isn't met.
If the system is AP: Node A accepts the write. Node B serves the old address to the Singapore user. Both users get a response, but they see different data. Once the network heals, the nodes sync up and everyone sees "123 New Street".
CAP in Practice: It's Per Feature, Not Per System
Real systems don't pick one CAP trade-off for everything. Different features have different needs. An e-commerce platform might use:
- CP for payments and inventory (can't oversell or lose money)
- AP for product catalog and search (stale results are fine)
- AP for user sessions and shopping carts (availability matters more)
In an interview, break the system into features and justify the trade-off for each one.
| Feature | Why this choice? | Trade-off | Database Example |
|---|---|---|---|
| Payment processing | Wrong balance = lost money | CP | PostgreSQL, Google Spanner |
| User feed / timeline | Downtime = users leave | AP | Cassandra, Redis |
| Shopping cart | Must not lose items, even if stale | AP | DynamoDB |
| Ticket booking | Double-selling = legal trouble | CP | PostgreSQL + distributed lock |
| Like / view counts | Approximate is fine | AP | Redis, Cassandra |
| User authentication | Must not grant wrong access | CP | PostgreSQL, Auth0 |
Common Misconceptions
"CAP means pick any two." Not quite. Since partitions are unavoidable, you always need P. The real choice is C vs A during a partition. When there's no partition, you can have both C and A.
"A database is either CP or AP, always." Many databases are tunable. Cassandra is AP by default but can be configured for strong consistency on specific queries. MongoDB can be CP or AP depending on write/read concern settings. It's a spectrum, not a binary.
"Eventual consistency means data loss." No. The data is written and safe. It just takes time to replicate to all nodes. Eventual consistency is about read staleness, not write durability.
"CP systems are always down during partitions." Not always. If the partition only affects a minority of nodes, a quorum-based CP system keeps working. It only becomes unavailable if the partition prevents reaching a majority.
Summary
| Concept | One-line summary |
|---|---|
| Consistency | Every read returns the latest write |
| Availability | Every request gets a response (never an error) |
| Partition Tolerance | System works even when nodes can't talk to each other |
| CP | Correct data or no data. Blocks during partitions. |
| AP | Always responds, even with stale data. Syncs later. |
| Eventual Consistency | All nodes converge to the same value, given enough time |
| The real question | When a partition happens, do you prefer errors (CP) or stale data (AP)? |