CAP Theorem

The CAP theorem states that a distributed system can only guarantee two of three properties simultaneously.

The Three Properties

        Consistency
           /\
          /  \
         /    \
        / CP   \
       /   AP   \
      /____CA____\
 Availability   Partition
                Tolerance

CA: Consistency + Availability (no partition tolerance)
CP: Consistency + Partition Tolerance
AP: Availability + Partition Tolerance

Definitions

Consistency:
Every read receives the most recent write or an error. All nodes see the same data at the same time.

Availability:
Every request receives a non-error response, without guaranteeing it contains the most recent write.

Partition Tolerance:
The system continues to operate despite network partitions (communication breaks between nodes).

Why You Can't Have All Three

Scenario: Network Partition

Node A ────X──── Node B
     (partition)

Client writes X = 1 to Node A
Client reads X from Node B

Option 1 (Consistency):
- Return error (can't guarantee latest value)
- Sacrifices Availability

Option 2 (Availability):
- Return old value (X = 0)
- Sacrifices Consistency

You must choose: Consistency OR Availability

The Reality: Partitions Happen

Network partitions are inevitable:
- Hardware failures
- Network congestion
- Rack failures
- Data center outages

Since partitions WILL happen, the real choice is:
- CP: Sacrifice availability during partitions
- AP: Sacrifice consistency during partitions

CA systems only work when there are no partitions.

Understanding CAP helps you choose the right technology for your use case.

CP Systems (Consistency + Partition Tolerance)

During partition:
- Reject writes to minority side
- Accept writes to majority side
- Ensure consistent data

Examples:
- ZooKeeper (leader election)
- etcd (distributed key-value)
- HBase (column-family store)
- MongoDB (with majority write concern)
- PostgreSQL (with synchronous replication)

AP Systems (Availability + Partition Tolerance)

During partition:
- Accept writes on both sides
- Allow inconsistent data temporarily
- Resolve conflicts later

Examples:
- Cassandra (eventual consistency)
- DynamoDB (eventual consistency)
- CouchDB (multi-master)
- Riak (eventual consistency)
- DNS (eventual propagation)

CA Systems (Consistency + Availability)

No partition tolerance:
- Only works in single-node or no-partition scenarios
- Not truly distributed

Examples:
- Single-node PostgreSQL
- Single-node MySQL
- Traditional RDBMS

Note: Real distributed systems must handle partitions,
so true CA systems are rare in distributed computing.

Real-World Examples

System	CAP Choice	Reason
Banking	CP	Must prevent double-spending
DNS	AP	Always resolve, may be stale
ZooKeeper	CP	Coordination requires consistency
Cassandra	AP	High availability for writes
Redis Cluster	CP	Data consistency important
S3	AP	Always available for uploads

Use CAP to guide your technology choices and design decisions.

Decision Framework

Step 1: Can you tolerate stale data?
├── Yes → Consider AP
└── No → Consider CP

Step 2: Is availability critical?
├── Yes → Consider AP
└── No → Consider CP

Step 3: What happens during failure?
├── Reject operations → CP
└── Accept operations → AP

CAP in System Design Interviews

When asked to design a system:

1. Identify components
2. For each component, determine:
   - Can it tolerate stale data?
   - Is availability critical?
   - What happens during failure?

3. Choose CP or AP for each component

Example: URL Shortener
- URL creation: AP (always accept, resolve later)
- URL redirect: AP (serve from cache, may be stale)
- Analytics: AP (eventual consistency OK)

Example: Inventory System
- Stock check: CP (must prevent overselling)
- Order placement: CP (must be consistent)
- Product browsing: AP (can show stale data)

Beyond CAP: Practical Considerations

CAP is a starting point, not the full picture:

1. Consistency Levels
   - Strong, Eventual, Read-your-writes

2. Performance
   - Latency and throughput requirements

3. Operational Complexity
   - How hard to manage and monitor

4. Cost
   - Infrastructure and operational costs

5. Data Model
   - Relational vs document vs key-value

Common Mistakes

1. Assuming CA is possible in distributed systems: Partitions happen
2. Ignoring the tradeoffs: Every choice has consequences
3. Over-engineering: Not every system needs strong consistency
4. Under-engineering: Some systems absolutely need consistency

Summary

CAP Theorem:
- Distributed systems can only guarantee 2 of 3
- Partitions are inevitable, so choose CP or AP
- CP: Sacrifice availability during partitions
- AP: Sacrifice consistency during partitions
- Choose based on business requirements