CAP Theorem Explained

Sam Erickson
Updated yesterday
0

Key Takeaways

CAP forces a consistency-versus-availability trade-off during a network partition, not during every database operation.
CAP consistency means linearizability: operations behave like access to one authoritative copy, respecting real-time ordering.
CAP availability requires requests reaching non-failing nodes to complete; rejecting an operation because coordination is unavailable sacrifices that guarantee.
Evaluate specific operations, replication settings, and failure scenarios—not permanent SQL, NoSQL, CP, or AP labels.

CAP theorem says that a distributed data store cannot guarantee both linearizable consistency and availability when a network partition prevents its nodes from communicating. It does not mean that databases must permanently choose any two of three desirable features.

The practical question is narrower: during a communication failure, which operations should stop, and which may continue with potentially stale or conflicting data? The formal proof by Seth Gilbert and Nancy Lynch establishes the constraint; your application requirements determine the response.

What Is CAP Theorem?

CAP stands for consistency, availability, and partition tolerance. Each term has a specific meaning here.

Consistency: Linearizable Operations

CAP consistency means linearizability, also called atomic consistency. Each operation appears to execute at one instant between its invocation and completion, within a single order that respects real time.

A read that starts after an acknowledged write completes must return that write’s value or the value of a later write to the same object. A read overlapping a write can legally see the old or new value.

This is more precise than saying that every replica always contains identical data. Replicas can lag internally if the system prevents that lag from violating the behavior clients observe.

Availability: Operations Complete at Non-Failing Nodes

In the CAP model, every request received by a non-failing node must eventually complete with an operation result. Completion must occur in finite time, but the model does not impose a fixed latency deadline.

Returning “cannot reach quorum” instead of completing the requested read or write sacrifices availability; merely sending an error response does not satisfy the guarantee. Gilbert and Lynch’s Perspectives on the CAP Theorem explains this distinction between guaranteed completion and best-effort availability.

The guarantee is conditional on a request reaching a non-failing node. It is not a promise that a disconnected client can always reach the service.

Partition Tolerance: Account for Lost Communication

A network partition prevents groups of nodes from exchanging messages even though the nodes themselves may still be running. Partition tolerance means accounting for this failure condition when specifying the system’s guarantees.

It does not mean every operation must keep succeeding. A system can tolerate a partition by preserving consistency while refusing operations it cannot safely complete.

A CAP Theorem Example With Two Replicas

Suppose two replicas store a single counter, user_count = 100. They lose contact, but clients can still reach each replica. Client 1 asks replica A to set the counter to 101.

Client 1 -- write user_count = 101 --> [Replica A: 100]
                                                |
                                       network partition
                                                X
                                                |
Client 2 -- read user_count ---------> [Replica B: 100]

Preserve Consistency by Restricting Operations

One conservative policy requires both replicas to confirm a write before acknowledging it. During this partition, A cannot acknowledge the update, so the write must wait or fail.

Another design could allow an authoritative side to accept the write, but then B must not serve a supposedly linearizable read from its old state. Preserving consistency does not necessarily stop the entire system; it stops operations that cannot meet the guarantee.

Preserve Availability by Allowing Divergence

Alternatively, A acknowledges 101 without contacting B. After that acknowledgment, Client 2 reads B and receives 100. Both requests completed, but the read violated linearizability because it began after the write completed.

If both sides accept updates, those updates may also conflict. Recovery then needs a defined reconciliation policy—not just restored connectivity.

Behavior during this partition	CAP interpretation
Reject or indefinitely delay operations that require unreachable coordination.	Preserves consistency at the expense of availability.
Complete operations independently on both sides, allowing stale or divergent results.	Preserves availability at the expense of linearizable consistency.

These are outcomes for the illustrated operations, not permanent classifications of every feature in a database.

CAP Theorem Misconceptions

“Choose Two” Is Not a Database-Selection Rule

Without a partition, CAP does not force you to sacrifice consistency or availability. Nor can you eliminate the failure scenario by declaring a networked system “CA.” Once communication breaks, the affected operations still face the trade-off.

As Eric Brewer explains in CAP Twelve Years Later, the choice can differ by operation, data, or subsystem. “CP” and “AP” are useful shorthand only when you specify their scope.

CAP Theorem vs ACID and BASE

ACID describes transaction properties: atomicity, consistency, isolation, and durability. Its consistency property concerns preserving database rules and application invariants—conditions that must remain true—not CAP’s real-time ordering guarantee.

BASE—basically available, soft state, eventually consistent—is a broad design philosophy, not a precise alternative transaction contract. Neither SQL syntax nor a NoSQL label determines partition behavior.

When comparing MongoDB and MySQL, ask about the actual replication topology and operation guarantees rather than treating ACID and CAP consistency as interchangeable.

Eventual Consistency Does Not Satisfy CAP Consistency

Eventual consistency permits replicas to diverge temporarily. If updates stop, communication recovers, and the system’s repair and conflict-resolution requirements are met, replicas eventually converge.

That is not linearizability: a read can still return an older value after a write has completed. Cassandra’s documented consistency guarantees distinguish eventual consistency from its separate linearizable lightweight transactions.

CAP Theorem Applied

Cassandra: Consistency Levels Change Which Operations Can Finish

Cassandra exposes per-operation consistency levels. For three replicas of a key in one datacenter, ordinary reads and writes at ONE can proceed on either side of a two-to-one split if each coordinator can reach a replica.

At QUORUM, each operation requires two replica responses, so the isolated single-replica side cannot satisfy the request. This changes availability for that operation; it does not remove the partition constraint.

The Cassandra replication documentation describes quorum overlap using R + W > N: read and write response sets intersect when their sizes sum to more than the replica count, for the same fixed replica group.

Use this operation-level distinction when evaluating the broader differences in HBase vs Cassandra.

MongoDB: Specify Both Read and Write Guarantees

For a single-document lookup by immutable _id on the primary, MongoDB’s read concern "linearizable", combined with write concern { w: "majority" }, provides linearizable behavior. Read concern "majority" alone is not a synonym for "linearizable".

MongoDB recommends setting maxTimeMS for these reads so they return an error rather than block indefinitely when a majority of data-bearing members is unavailable. See its linearizable read concern documentation for requirements and restrictions.

A primary isolated from a majority of voting members steps down when it detects that condition; an eligible member on the majority side can be elected. MongoDB’s replica-set election behavior therefore matters alongside read and write settings.

Choose Behavior per System Function

Consider a hypothetical storefront with separate browsing and reservation operations:

Browse product descriptions: permit a local cached copy during a partition, accepting that it may be stale.
Reserve the last item: require an atomic conditional reservation against authoritative stock; reject or defer the reservation when the required coordination is unavailable.
Display a user-count dashboard: permit a delayed replicated count rather than making the dashboard unavailable.

The point is to define different contracts, not silently weaken one contract when the network gets slow. A linearizable read alone also does not make a later, separate write an atomic reservation.

Cloud hosting does not change CAP. For a managed database, inspect regional replica placement, quorum requirements, client routing, and the behavior of each relevant operation during a regional or inter-region partition.

CAP Theorem vs PACELC

CAP describes a failure-time constraint, not every database trade-off. Daniel Abadi’s PACELC formulation adds the normal-operation question:

If there is a partition (P): how does the system trade availability (A) against consistency (C)?
Else (E): how does it trade latency (L) against consistency (C)?

For example, coordinating with remote replicas can increase operation latency even when the network is healthy. CAP alone does not tell you whether that latency is acceptable for your workload.

Production Checklist

Write down the contract: identify which operations require linearizability, which permit stale data, and which need multi-record transactions.
Test actual partitions: cut communication between running replicas instead of testing only process crashes. Exercise both sides of the split.
Check deadlines and fallbacks: set explicit time limits and avoid silently replacing a strong read with a weaker one.
Test recovery: verify repair, conflict resolution, and application invariants after connectivity returns.
Measure normal operation too: compare latency and failure rates under the exact consistency settings you intend to deploy.

Conclusion

Use CAP to specify failure behavior, not to assign a permanent letter to an entire database. Decide which functions may stop and which may return stale data: a storefront can keep browsing available while refusing a reservation it cannot safely confirm.

FAQ

Does CAP theorem mean a database must choose two out of three?

No. CAP says a distributed data store cannot guarantee both linearizable consistency and availability during a network partition. Without a partition, CAP does not force that choice.

What does consistency mean in the CAP theorem?

Consistency means linearizability: operations appear to execute against one copy in an order that respects real time. Eventual consistency permits temporary divergence and therefore does not provide this guarantee.

What does availability mean in CAP theorem?

Every request received by a non-failing node must eventually complete with an operation result, without a fixed latency bound. Rejecting a read or write because required replicas are unreachable sacrifices this availability guarantee.

Can a database switch between consistency and availability?

Some databases expose per-operation consistency levels or configurable quorum policies. These settings change an operation’s guarantees and ability to complete during a partition; they do not automatically escape CAP in response to latency or load.

How is CAP theorem different from PACELC?

CAP addresses consistency versus availability during partitions. PACELC also considers the latency-versus-consistency trade-off when no partition is present, making it useful for evaluating normal-operation behavior.