The CAP Theorem

The Three Properties

The CAP theorem identifies three desirable properties of distributed systems, any two of which can be guaranteed but not all three:

Consistency (C): Every read receives the most recent write or an error. In a strongly consistent system, once a write is acknowledged, all subsequent reads from any node will observe that write. This is the behavior of a single-machine database where you cannot read stale data. Achieving consistency across a distributed system requires coordination: nodes must synchronize before replying to requests, or readers must wait for all replicas to be updated. This synchronization cost is the penalty for guaranteeing freshness—the system must coordinate writes across replicas, introducing latency and potential unavailability if coordination fails.

Availability (A): Every request receives a (non-error) response without guarantee of freshness. A system is available if every node that is not partitioned can respond to read and write requests immediately. Availability favors responsiveness: the system prioritizes returning a result over ensuring that result is current. This is why eventually consistent systems like Cassandra and DynamoDB accept writes on any node without checking other replicas first. The trade-off is that clients may see stale or conflicting data, requiring application-level conflict resolution.

Partition Tolerance (P): The system continues to operate despite an arbitrary number of messages being dropped or delayed between nodes. A network partition means some nodes cannot communicate with others, yet the system as a whole remains operational. Modern networks experience partitions due to network failures, datacenter outages, BGP hijacking, or DNS inconsistencies, making partition tolerance practically unavoidable. In the real world, when your data is replicated across multiple nodes or datacenters, partitions happen—sometimes between your nodes, sometimes isolating entire regions.

Why Partitions Are Inevitable

Network partitions are not rare edge cases; they are a reality of distributed systems. TCP timeouts, switch failures, overloaded routers, and misconfigured firewalls can all cause message loss between nodes. Major cloud providers have publicly documented partitions affecting their systems. Since partitions can occur at any time, every distributed system must choose: partition tolerance is not optional in practice.

This simplifies the CAP trade-off to a binary choice: Consistency vs. Availability. When a partition occurs, a system must either:

• Sacrifice Availability (CP): Refuse requests and wait for network recovery, ensuring consistency is never violated.
• Sacrifice Consistency (AP): Accept requests on isolated nodes and reconcile state later when the partition heals.

There is no middle ground during a partition. A node either responds or it doesn't; a response is either fresh or it is stale.

The Fundamental Proof

The CAP theorem's truth becomes clear through a simple thought experiment. Imagine two nodes, A and B, separated by a network partition. A client writes data to node A and immediately reads from node B.

For consistency: node B must have the write. But the partition prevents A from sending the update to B. So either A refuses the write (violating availability), or B returns a stale read (violating consistency).

For availability: both nodes must respond. But if both respond, B might return data inconsistent with what A received. During a partition, you cannot have both nodes responding with consistent data.

This is not a limitation of current algorithms; it is a mathematical impossibility. No clever engineering or better networking can overcome it. The choice is baked into the problem itself.

CP Systems: Consistency Over Availability

A CP system prioritizes consistency, sacrificing availability during partitions. When a partition occurs, the system may become partially or wholly unavailable to maintain consistency guarantees.

Examples: Traditional SQL databases (PostgreSQL, MySQL with replication) operate in CP mode during failures. Many consensus-based systems like Zookeeper, Etcd, and Raft-based stores are CP by design. When a Raft cluster loses quorum, it stops accepting writes entirely, preferring to remain consistent rather than allow conflicting writes on different partitions.

Trade-offs: CP systems provide strong guarantees, making them ideal for financial systems, inventory management, and other domains where stale data is unacceptable. However, the cost is operational complexity: loss of quorum means the entire system may become unavailable, requiring careful cluster sizing and monitoring.

AP Systems: Availability Over Consistency

An AP system prioritizes availability, allowing inconsistent reads during partitions. When partitioned, different nodes may have different versions of the same data. Consistency is eventual: data converges over time after the partition heals.

Examples: Amazon's Dynamo, Google's Bigtable (in certain configurations), and Apache Cassandra are classic AP systems. They accept writes on any node, even during partitions, and use read-repair, hinted handoff, and merkle tree reconciliation to converge state afterward.

Trade-offs: AP systems tolerate network failures gracefully and distribute writes without a central bottleneck. However, clients must handle conflicting versions of data. E-commerce carts, user profiles, and metadata can tolerate eventual consistency; financial transactions usually cannot.

Real-World System Choices

MongoDB: Configurable consistency. With a single primary and synchronous replication to all secondaries, it behaves as CP (strong consistency). With asynchronous replication, it slides toward AP (availability).

DynamoDB: AP by default. Every request succeeds on any available replica, and DynamoDB merges updates via version numbers and last-write-wins semantics. Strong consistency is optional and incurs latency.

Google Spanner: Attempts to transcend CAP by using TrueTime (atomic clocks) to provide strong consistency globally without sacrificing availability. It is expensive and specialized, not a universal solution.

Redis: Master-slave replication introduces a choice: synchronous writes to all replicas (CP, slow) or asynchronous propagation (AP, fast but risky on master failure).

Consistency Models Beyond CAP

The CAP theorem uses strong (linearizable) consistency as its definition. But distributed systems offer weaker models that make different trade-offs:

• Eventual Consistency: Replicas eventually agree without coordination. Used in DNS, email, and social networks.
• Causal Consistency: If A causes B, observers see them in that order. Stronger than eventual, weaker than strong. Facebook's Memcache uses causal consistency.
• Read-Your-Writes: A client always observes its own writes, but other clients may see stale data. Common in web applications.
• Bounded Staleness: Data is at most N seconds old. Used in Azure Cosmos DB and other geo-distributed systems.

These weaker models allow systems to recover some availability while maintaining useful consistency guarantees.

Design Implications and Strategy

Choosing between CA, CP, and AP is not purely theoretical; it shapes every aspect of system design:

Quorum Reads and Writes: CP systems often use quorum-based algorithms. A write succeeds only when written to a majority of replicas. A read requires reading from a quorum and taking the latest version. This ensures strong consistency at the cost of latency and availability during partitions.

Read Repair and Anti-Entropy: AP systems use background processes to detect and resolve inconsistencies. Read repair fixes stale data when clients access it; anti-entropy (merkle trees) periodically sync replicas. This keeps the system available but requires complex conflict resolution.

Hybrid Approaches: Modern systems often blend CA, CP, and AP behaviors. Cassandra can be tuned toward consistency with higher replication factors and quorum reads, or toward availability with single-node reads. This flexibility is powerful but demands operational understanding.

Partition Simulation: Teams cannot avoid network failures in testing. Tools like Chaos Engineering, Jepsen, and Gremlin deliberately inject partitions and measure system behavior, ensuring the chosen trade-off is actually respected in production.

PACELC: The CAP Theorem Extended

Daniel Abadi extended CAP with PACELC: If a Partition, then either Availability or Consistency; Else Latency or Consistency. PACELC acknowledges that even without partitions, systems must trade Latency against Consistency.

A strongly consistent system (like Spanner) adds latency because writes must coordinate across replicas. An eventually consistent system (like Cassandra) returns fast but client code must handle conflicts. PACELC gives a more complete picture of real-world trade-offs. It recognizes that most systems operate in the "normal" case (no partitions) far more often than in the partition case, making latency vs. consistency the primary concern for most deployments. Only during the rare partition event does the CAP trade-off become relevant. PACELC forces teams to think about both: how does the system behave normally, and what happens when things break?

Migration and Hybrid Strategies

Real-world systems rarely fit cleanly into CA, CP, or AP. Many start as one and migrate toward another as they scale. Pinterest began with MySQL (strongly consistent, not available during failures) but migrated to Cassandra (available, eventually consistent) as their data grew. Stripe uses a mix: strongly consistent ledgers for financial transactions (CP) but eventually consistent denormalized caches for search (AP).

A common pattern is using per-request tuning: read requests can ask for consistency levels, allowing clients to trade latency for freshness on-demand. DynamoDB offers strongly consistent reads (slower) and eventually consistent reads (fast). Cassandra lets applications specify the replication factor and quorum levels for each operation. MongoDB can be configured to wait for replication to a majority of nodes before acknowledging writes, shifting toward CP.

Another pattern is geographic separation: a CP system for hot data that requires strong consistency (user accounts, inventory counts) and an AP system for warm data that tolerates staleness (analytics, recommendation caches). This lets teams use the right tool for each problem rather than forcing one choice globally.

Testing and Failure Scenarios

The CAP theorem is useless without testing the actual trade-off under failure. Many teams discover their true position (C vs. A during partitions) only after an incident. That is where chaos engineering comes in: deliberately inject network partitions, latency, and packet loss in staging or production environments, then measure what breaks.

Jepsen is a formal testing framework that systematically partitions systems and checks whether their consistency claims hold. Jepsen tests of MongoDB, Redis, PostgreSQL, and Cassandra have revealed surprising behavior: systems that claim to be CP sometimes lose data during partitions, and systems claiming to be AP sometimes force unavailability. The CAP theorem is always true, but your implementation might not respect your choice.

Practical testing should cover: (1) What happens to client requests during a partition? (2) What is the recovery time after the partition heals? (3) Can data diverge, and if so, how is conflict resolution handled? (4) Do replicas re-synchronize correctly? Understanding these behaviors for your chosen CP, AP, or CA system is how you build reliability in practice.