CAP Theorem

CAP Theorem (also known as Brewer's Theorem) states that a distributed data store can only guarantee two out of three properties simultaneously:

Proposed by Eric Brewer in 2000, formally proven by Seth Gilbert and Nancy Lynch in 2002.

The Three Properties

C - Consistency

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

In other words: All clients see the same data simultaneously, no matter which node they connect to.

Example: You update your profile picture on a social network. With strong consistency, all users immediately see your new picture, never the old one.

A - Availability

Definition: Every request receives a (non-error) response, without guarantee that it contains the most recent write.

In other words: The system is always operational and responsive, even if some nodes are down.

Example: You can always post on Twitter, even during peak traffic or if some servers are down. Your post might not immediately appear to everyone, but the system accepts it.

P - Partition Tolerance

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

In other words: The system works even when network failures prevent some nodes from communicating with each other.

Example: A data center in New York loses network connection to a data center in London. The system continues operating in both locations independently.

The Trade-offs

Key Insight: In a distributed system, network partitions are inevitable (hardware failures, network issues, etc.). Therefore, you must choose between Consistency and Availability when a partition occurs.

CP - Consistency + Partition Tolerance

Choose when: Data correctness is critical

Trade-off: System may become unavailable during partitions

Examples:

Behavior during partition: Nodes may refuse to respond to avoid returning stale data.

AP - Availability + Partition Tolerance

Choose when: System uptime is critical

Trade-off: May return stale data during partitions

Examples:

Behavior during partition: All nodes remain available but may return inconsistent data until partition heals.

CA - Consistency + Availability

Reality: Not possible in distributed systems with network partitions!

Only achievable in: Single-node systems or systems that don't tolerate partitions (not truly distributed)

Examples:

Real-World Database Examples

Database CAP Classification Use Case Consistency Model
MongoDB CP General purpose, document storage Strong consistency with primary reads
Cassandra AP (tunable) High write throughput, time-series data Eventual consistency (tunable)
DynamoDB AP (with CP option) Serverless, key-value store Eventual consistency (strong consistency available)
PostgreSQL CA (single node) ACID transactions, relational data Strong consistency
Riak AP Distributed key-value store Eventual consistency
HBase CP Large-scale structured data Strong consistency
CouchDB AP Mobile sync, offline-first apps Eventual consistency
Redis CP (with Redis Sentinel/Cluster) Caching, real-time analytics Strong consistency (configurable)

Consistency Models

Strong Consistency (Linearizability)

Once a write completes, all subsequent reads will see that write or a later value.

Example: Banking transactions - your account balance must be accurate immediately.

Eventual Consistency

If no new updates are made to an object, eventually all accesses will return the last updated value.

Example: DNS propagation - changes eventually reach all servers, but may take time.

Causal Consistency

Writes that are causally related must be seen by all processes in the same order.

Example: Comment replies - you always see the original post before its replies.

PACELC Theorem (Extended CAP)

PACELC extends CAP to address system behavior during normal operation (no partition):

Classifications:

Practical Decision Framework

Choose CP (Consistency + Partition Tolerance) when:

Choose AP (Availability + Partition Tolerance) when:

Choose CA (Consistency + Availability) when:

Common Misconceptions

Myth 1: "CAP means you only get 2 out of 3"

Reality: In distributed systems, partitions will happen, so you must choose between C and A during partitions. During normal operation, you can have all three.

Myth 2: "My database is CA"

Reality: If your system is distributed across multiple nodes, it's either CP or AP. True CA systems don't tolerate network partitions.

Myth 3: "Eventual consistency means eventually correct"

Reality: Eventual consistency means that if writes stop, reads will eventually converge. It doesn't specify how long "eventually" is.

Myth 4: "You must choose one permanently"

Reality: Many systems offer tunable consistency (e.g., Cassandra's consistency levels, DynamoDB's read/write settings).

Tunable Consistency (Cassandra Example)

# Cassandra allows tuning consistency per query # Strong consistency (CP behavior) session.execute(query, consistency_level=ConsistencyLevel.QUORUM) # High availability (AP behavior) session.execute(query, consistency_level=ConsistencyLevel.ONE) # Strongest consistency (requires all replicas) session.execute(query, consistency_level=ConsistencyLevel.ALL) # Eventual consistency session.execute(query, consistency_level=ConsistencyLevel.ANY)

Key Takeaways

  1. Partitions are inevitable in distributed systems (network failures, hardware issues)
  2. Choose based on requirements: CP for correctness, AP for uptime
  3. Modern systems offer tunability: Adjust consistency vs availability per operation
  4. Consider PACELC: Think about latency vs consistency during normal operation too
  5. No silver bullet: Different parts of your system may need different trade-offs
  6. Test partition scenarios: Simulate network failures to understand your system's behavior

Further Reading