Skip to content
matthewcm.dev

    ↑ ↓ move · ↵ open · tab scopeopen graph →

    CAP Theorem

    When the network partitions, a distributed data store must choose between consistency and availability. PACELC adds the other half, that even without partitions you trade latency for consistency.

    Evergreentended planted 2 min read
    On this page

    The CAP theorem says a distributed data store can’t simultaneously guarantee all three of:

    • Consistency (C): every read sees the most recent write. All nodes agree.
    • Availability (A): every request gets a non-error response, even if it’s not the latest data.
    • Partition tolerance (P): the system keeps working when messages between nodes are lost.

    The honest reading

    “Pick two of three” is the slogan, and it’s misleading. Networks will partition (see the Fallacies of Distributed Computing), so P isn’t optional. The real statement is: when a partition happens, choose C or A.

    • CP: refuse or delay requests on the side that can’t confirm the latest state. You’ll get an error, never a stale answer. Typical of systems built on consensus (Raft, ZooKeeper, etcd) and of anything holding money or inventory.
    • AP: keep answering on both sides and reconcile later. You’ll always get an answer, possibly stale. Typical of Dynamo-style stores, DNS, caches and shopping baskets.

    PACELC: the part CAP leaves out

    Partitions are rare. Most of the time the network is fine, and you’re still making a trade-off. PACELC, from the database researcher Abadi, puts it as: if Partitioned, choose Availability or Consistency; Else, choose Latency or Consistency.

    Strong consistency means coordinating with other replicas before answering, and that costs round trips even on a good day. So:

    System stylePartitionNormal operation
    PA/EL (e.g. Dynamo-style stores)stay availableanswer fast from the nearest replica
    PC/EC (e.g. consensus-backed stores)stay consistentpay latency to coordinate
    PA/EC or PC/ELmixed, often tunable per query

    Many databases let you tune this per operation: read from any replica (fast, maybe stale) or require a quorum (slower, current).

    An example

    A trading screen’s order entry must be CP: showing a stale balance and accepting an order you can’t fill is worse than showing an error. The same screen’s news feed can happily be AP: a headline arriving two seconds late harms nobody. One product, two different answers. Decide per feature, not per company.

    In practice

    The most useful thing CAP gave me is a question to ask in design reviews: “What should the user see if this service can’t reach its peers?” If nobody has an answer, the system will pick one for you, usually badly. The broader study of what “correct” even means here is in The Consensus Problem.

    • #distributed-systems
    • #consistency
    • #availability
    • #databases
    • #system-design
    • Architecture Decision RecordsEvergreen
      …the three decisions people ask about most. It's also the natural place to record trade-offs like those in the CAP Theorem or the failure model a system assumes (Types of Failure). See also Design Review Readiness Checkli…
    • RaftGrowing
      …o failures; lose three and it stops accepting writes rather than risk divergence. That's the CP choice in the CAP Theorem.
    • The Consensus ProblemGrowing
      …loses its majority stops accepting writes rather than risk disagreeing. That last one is the CP choice in the CAP Theorem.
    • Two-Phase CommitGrowing
      Both trade immediate atomicity for availability and looser coupling, the same trade-off as in the CAP Theorem.

    ↪ Links to (3)