cap theorem
what you are actually choosing when the network splits, and why 'pick two' is the wrong frame.
“pick two. they will then argue about which two.”
what you are actually choosing when the network splits, and why 'pick two' is the wrong frame.
“pick two. they will then argue about which two.”
eric brewer put CAP forward as a conjecture in a 2000 PODC keynote. gilbert and lynch proved it in 2002 for the asynchronous network model. what survived into common usage is the summary, "pick two of consistency, availability, partition tolerance", and the summary is where the damage happens.
you never pick two. partition tolerance is not a menu item.
these are technical terms with narrower meanings than the english words suggest, and most CAP arguments are really vocabulary disagreements.
consistency in CAP means linearizability. every read returns the most recent committed write, as if there were a single copy of the data. this is much stronger than what a database marketing page means by "consistent", and it is not the C in ACID.
availability means every request to a non-failing node returns a non-error response. not "the service is mostly up". every request, every live node.
partition tolerance means the system keeps operating when the network drops arbitrarily many messages between nodes.
the framing "pick two" implies all three are optional. two of them are properties you design for. the third is a thing the network does to you.
networks drop packets, switches get misconfigured, BGP changes go wrong, a cloud provider reboots a rack. bailis and kingsbury collected the public evidence in the network is reliable, and the jepsen analyses are a long catalogue of databases discovering their own partition behavior in production. if your system spans more than one machine, partitions happen whether or not you planned for them.
so P is not something you trade away. the real theorem is narrower and more useful:
when a partition occurs, you must choose between consistency and availability.
everything else about CAP follows from that sentence.
five nodes. the network splits them three-and-two. the majority side can still form a quorum; the minority side cannot.
freshwriteacceptedfreshwriteacceptedfreshwriteacceptederrorwriterejectederrorwriterejectedthe two modes are named for what they keep, which is the part that gets misremembered:
CP keeps consistency and gives up availability. the minority side cannot confirm a write with a quorum, so it refuses to answer at all rather than serve data it cannot vouch for. two of five nodes stop serving. nothing diverges, so recovery is ordinary replication catch-up. this is etcd, ZooKeeper, HBase, and any database configured with quorum writes.
AP keeps availability and gives up consistency. every node answers. the minority side cannot see the majority's writes, so it returns stale reads and accepts writes that conflict with the other side. nobody gets an error, and when the partition heals you have two divergent histories to reconcile. this is Cassandra, Riak, and DynamoDB in its default mode.
the mnemonic worth keeping: the letter you keep is the letter in the name. CP keeps C. AP keeps A. the one that is missing is the one you sacrificed.
"CA" appears in a lot of diagrams and it is close to meaningless for a distributed system. dropping P means asserting that partitions never happen. they do. a system labelled CA is either a single node, where the question does not arise, or a distributed system that has simply not defined its partition behavior, which means it will improvise one during your next incident.
if you find yourself picking CA, you have not made a choice. you have deferred it to the network.
brewer revisited this in CAP twelve years later and made the point the original summary flattened: the granularity is wrong. a real system does not pick one letter and apply it everywhere.
the same deployment can hold a session cache that serves stale reads happily and a ledger that refuses writes without a quorum. those are an AP decision and a CP decision inside one product, chosen per operation based on what being wrong actually costs.
the useful question is never "is my database CP or AP". it is "what should this operation do when it cannot reach a quorum". a like counter and a debit have different answers and there is no reason to force them into one.
"eventually consistent" means replicas converge to the same state once writes stop. it is a real guarantee and it is weaker than most people read it as, because the word doing the work is unbounded.
nothing in the definition says how long. under normal operation it is often milliseconds. under partition it is "not until the partition heals", which could be hours. a system can satisfy eventual consistency and still serve you a value from last tuesday.
so the model tells you the endpoint, not the schedule. what you actually need from a specific system is the staleness bound and the conflict resolution strategy, and those are per-system facts you have to look up rather than derive from the label.
CAP only says anything during a partition. that is a small fraction of the time, which makes it a poor guide to the other 99.9%.
abadi's PACELC extends it: if there is a partition, choose availability or consistency; else, choose latency or consistency. the second half is where systems spend almost all their life. keeping replicas linearizable costs round trips on every operation on a perfectly healthy network. you pay for consistency continuously, not only during failures.
that steady-state cost is measurable, and performance vs correctness puts numbers on it.