Stackbook Logo
data-consistencyestablished · low operational burden

CAP Theorem

Also known as: brewers-theorem, cap

Intent

Reason about the unavoidable choice between consistency and availability when a network partition occurs in a replicated system.

Problem

Replicated data stores must keep working when links between nodes fail. Teams assume they can have perfect consistency and perfect availability simultaneously, then discover a partition forces a choice.

Forces

  • •Networks partition, so partition tolerance is not optional
  • •Linearizable reads require coordination across replicas
  • •Users expect responses even during failures
  • •Different operations in the same system need different guarantees

Solution

Overview

The CAP theorem, conjectured by Eric Brewer and proved by Gilbert and Lynch, states that a distributed data store cannot simultaneously guarantee linearizable consistency and availability of every request when the network is partitioned. Since partitions happen, the practical decision is what to give up while one is in progress.

How it works

Imagine two replicas that lose contact. A write arrives at one.

Client --write x=2--> [Replica A] ~~ partition ~~ [Replica B]  (x=1)

CP choice: A rejects or blocks the write   -> consistent, unavailable
AP choice: A accepts, B still serves x=1   -> available, inconsistent

CP systems typically require a quorum and refuse requests on the minority side. AP systems accept writes on both sides and reconcile later, using techniques such as last-write-wins, vector clocks, or CRDTs. Outside a partition, you can usually have both; the real costs show up as latency (see PACELC).

Pitfalls

  • Labeling products as CP or AP. Most are configurable per request or per table.
  • Reading "availability" loosely. In the theorem it means every non-failing node answers, which is stricter than typical uptime.
  • Believing "two out of three" is a free pick. Partition tolerance is not optional on real networks.
  • Forgetting the repair path. AP designs need a conflict-resolution and reconciliation plan.
  • Ignoring that consistency in CAP means linearizability, not the weaker guarantees many systems offer.

Key takeaways

  • CAP only constrains behavior during a partition.
  • Decide per operation which side you take and document it.
  • AP choices need conflict resolution and reconciliation.
  • Use PACELC to reason about the no-partition case.

✓ When to Use

  • •Choosing or configuring replicated datastores
  • •Designing multi-region write paths
  • •Explaining failure behavior to stakeholders

✗ When Not to Use

  • •Single-node systems with no replication
  • •Reasoning about normal-case latency (use PACELC)
  • •As a label to classify a database as simply CP or AP

Pros

  • +Gives a precise vocabulary for failure tradeoffs
  • +Forces explicit partition behavior decisions
  • +Prevents false promises of total consistency and availability

Cons

  • −Narrow: says nothing about latency without partitions
  • −Definitions are strict and often misapplied
  • −Real systems are tunable, not binary

Cost Profile

Infrastructure

None: conceptual

Operational

Low: documenting behavior

Cognitive

Medium: subtle definitions

Failure Modes

  • Assuming a system is CP or AP without reading its actual guarantees

  • Treating availability as uptime rather than every non-failing node responding

  • No reconciliation plan for AP writes after the partition heals

Real-World Examples

Alternatives

  • pacelc

Related Patterns

  • pacelc
  • consistency-model
  • eventual-consistency
  • quorum-reads-writes
  • multi-region-active-active

Competency Domains

data statedistribution communication