CAP Theorem: Understanding the Trade-offs

The CAP theorem, formulated by Eric Brewer in 2000, states that a distributed data store can only simultaneously provide two out of three guarantees: Consistency, Availability, and Partition Tolerance.

The Three Properties

Consistency (C)

Every read receives the most recent write or an error. All nodes see the same data at the same time. This is linearizability - not to be confused with ACID consistency.

Availability (A)

Every request receives a (non-error) response, without guarantee that it contains the most recent write. The system remains operational even if some nodes fail.

Partition Tolerance (P)

The system continues to operate despite an arbitrary number of messages being dropped or delayed by the network between nodes. Network partitions are inevitable in distributed systems.

The Trade-off Space

Since network partitions will happen, you must choose between CP and AP:

System Type	Characteristics	Examples
CP (Consistency + Partition Tolerance)	Sacrifices availability during partitions. Returns errors or times out if it can’t guarantee consistency.	MongoDB, Redis, HBase, ZooKeeper
AP (Availability + Partition Tolerance)	Sacrifices consistency during partitions. Always returns a response, but data may be stale.	Cassandra, DynamoDB, CouchDB, Riak
CA (Consistency + Availability)	Only possible in a single-node system. Not a practical choice for distributed systems.	Traditional RDBMS (single node)

PACELC Theorem

The CAP theorem only describes behavior during a partition. The PACELC theorem extends this:

If Partition (P) then Availability vs Consistency (A vs C); Else (E) Latency vs Consistency (L vs C)

Even without partitions, there’s a trade-off between latency and consistency. Strong consistency requires coordination, which adds latency.

# Example: Choosing consistency level in Cassandra
from cassandra.cluster import Cluster
from cassandra import ConsistencyLevel

cluster = Cluster()
session = cluster.connect()

# Strong consistency - wait for quorum
session.execute(
    "SELECT * FROM users WHERE id = ?",
    [user_id],
    consistency_level=ConsistencyLevel.QUORUM
)

# Eventual consistency - faster reads
session.execute(
    "SELECT * FROM users WHERE id = ?",
    [user_id],
    consistency_level=ConsistencyLevel.ONE
)

Practical Decision Framework

1. Financial transactions, inventory → CP (Consistency critical)
2. Social media feeds, recommendations → AP (Availability critical)
3. User profiles, sessions → Often AP with read-repair
4. Configuration, metadata → CP (Strong consistency needed)

Modern Perspectives

• Google Spanner: Claims to be CA using TrueTime (globally synchronized clocks)
• Cosmos DB: Offers 5 consistency levels from Strong to Eventual
• DynamoDB: Default eventual, supports strong consistent reads

The key insight: CAP is not a binary choice. Modern systems offer tunable consistency per operation.

Further Reading

• Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services - Gilbert & Lynch proof
• CAP Twelve Years Later: How the “Rules” Have Changed - Eric Brewer
• PACELC Theorem - Daniel Abadi