Please stop calling databases CP or AP

Martin Kleppmann posted this on his blog on 11 May 2015 please-stop-calling-databases-cp-or-ap, while he was writing the first edition of designing-data-intensive-applications; the post's linearizability diagram is a preview from an unreleased chapter of that book. The trigger was Jeff Hodges' "Notes on Distributed Systems for Young Bloods", which recommends using the CAP theorem to critique systems. Kleppmann agrees with everything else in Hodges' post and disagrees here. CAP is too simplistic and too widely misunderstood to characterize systems, he argues, so people should stop sorting datastores into CP and AP and describe their trade-offs in more precise terms. He admits the irony of writing a post about the topic he wants people to stop writing about, and says the point is to have a URL to hand out. His later paper, A Critique of the CAP Theorem, develops the argument and proposes an alternative.

The theorem is narrower than its reputation

A theorem holds only under the definitions its proof uses, and the proof by Seth Gilbert and Nancy Lynch (2002) uses narrow ones.

Consistency means linearizability, a specific and very strong model that has nothing to do with the C in ACID. Availability means every request received by a non-failing node must result in a non-error response. It is not enough that some node can handle the request, and many systems called highly available, in the low-downtime sense, don't meet the definition. Partition tolerance, which Kleppmann calls terribly misnamed, means communicating over an asynchronous network that may delay or drop messages. The internet and every datacenter have that property, so nobody gets to choose it.

The system model is narrow too. It is a single read-write register, so transactions touching several objects are outside the theorem. The only fault is a network partition, while real systems also lose nodes to crashes, run out of disk, and hit software bugs. And it says nothing about latency, which people care about more than availability, so a system that takes two minutes to load a page still counts as available.

If your meaning of consistency or availability is different, CAP doesn't apply to you. Redefining words doesn't make impossible things possible. It means you can't use CAP to justify your position, and a theorem you prove about your own definitions needs another name, because that one is taken.

The proof fits in one example

Two datacenters replicate to each other, and the network link between them breaks. One option is to keep accepting writes in both, so a client in one datacenter can miss a write already acknowledged in the other, which is not linearizable. The other is to route all reads and writes to one leader datacenter, and have the other stop serving until the partition heals, so its nodes are up but not CAP-available. Kleppmann says that is essentially the whole proof, and that it applies equally to a partition inside one datacenter.

The second option doesn't have to be an outage. If clients can be shifted to the leader datacenter, they see no downtime at all. An SLA such as 99.9% of well-formed requests succeeding within one second can be met by CAP-available and CAP-unavailable systems alike. When multi-datacenter systems do replicate asynchronously and give up linearizability, the reason is often wide-area latency rather than a wish to tolerate failures.

Real systems fit neither bucket

Single-leader replication, the standard setup for relational databases, is not CAP-available, since a client partitioned from the leader can't write. It isn't CP either once the application reads from asynchronously replicated followers, because those reads can be stale. Databases with snapshot isolation or MVCC are non-linearizable by design, since linearizability would cut concurrency. PostgreSQL's serializable snapshot isolation provides serializability without linearizability, and Oracle, according to the paper he cites, provides neither. A database branded ACID doesn't thereby meet CAP's definition of consistency.

MongoDB has a single leader per shard, so it isn't CAP-available, and Kyle Kingsbury had just shown non-linearizable reads at its highest consistency setting, so it isn't CAP-consistent. Dynamo derivatives such as Riak, Cassandra and Voldemort depend on configuration: with R=W=1 they are CAP-available, and with quorum reads and writes the minority side of a partition can't reach a quorum. Quorums don't guarantee linearizability either. Sloppy quorums and read repair produce edge cases where deleted data comes back or the replica count drifts away from the configured W and N.

Such systems are "just P", which the two-out-of-three slogan technically allows. Kleppmann stresses that they are not bad systems and people run them in production successfully. They simply can't be rigorously classified, because the answer depends on the operation or configuration, or because they meet neither strict definition.

ZooKeeper, the supposed clear case

ZooKeeper runs a consensus protocol, so it is usually filed as a clear-cut CP system. By its own documentation its reads are not linearizable by default: each client talks to one server and sees that server's data, even when newer writes exist elsewhere. Preceding a read with sync makes it linearizable at a performance cost. Writes need a majority quorum, so nodes on the minority side of a partition can't write even though they are up. Since 3.4.0 a read-only mode lets those minority nodes keep serving reads without a quorum, which is CAP-available. So ZooKeeper by default is just P, it becomes CP if you call sync, and for reads it is AP if you turn on the right option.

Kleppmann calls this verdict irritating, because it badly misrepresents a system with excellent consistency. ZooKeeper provides atomic broadcast, which is reducible to consensus, combined with causal consistency as a session guarantee, and that is stronger than read-your-writes, monotonic reads and consistent prefix reads put together. Its documentation claims only sequential consistency and undersells it. Under Abadi's PACELC framework it would be PC/EL, which he doesn't find any more enlightening than CAP.

Why the labels should go

Since not even one datastore has been classified unambiguously as CP or AP, he takes that as a sign the labels are wrong. Operations within one piece of software can have different consistency characteristics. Many systems are neither, and nobody calls theirs "P" because it looks bad, though it may be a perfectly reasonable design. People who force a system into a bucket anyway end up changing what consistency or availability means to suit them, and once the words change the theorem no longer applies and the distinction is meaningless. One bit can't encode fault tolerance, latency, simplicity of the programming model and operability: ZooKeeper's "AP" read-only mode still totally orders historical writes, a much stronger guarantee than the "AP" in Riak or Cassandra. And Eric Brewer himself wrote in 2012 that CAP is misleading and oversimplified. In 2000 he meant it to start a discussion about trade-offs in distributed data systems. It did that well, and Kleppmann adds that it was never intended as a breakthrough formal result or a classification scheme for data systems.

What to read instead

Kleppmann offers no replacement label and says there is no one right answer. His reading list starts with Doug Terry's paper explaining levels of eventual consistency through baseball, then his own Hermitage project on transaction isolation, then Peter Bailis et al. on Highly Available Transactions, which connects replica consistency, isolation and availability. After that come the papers linked throughout the post, his book as a last resort for anyone who won't read the papers, and Flavio Junqueira and Benjamin Reed's book for using ZooKeeper correctly.

Connections

• linearizability — the C in CAP, with the post's example of what it forbids and why it costs
• designing-data-intensive-applications — the book this post was written alongside; the vault's page tracks the second edition
• meerkat-introduction — Cloudflare specifies its consensus service in the terms Kleppmann asks for: linearizability plus an exact availability condition (a client reaching any machine connected to a live majority), with no CP or AP label
• distributed-consensus — the majority-quorum algorithms behind ZooKeeper's write behaviour under partition
• redis-cost-of-ambition — Kingsbury's stale-read findings against Redis-Raft, the same kind of evidence the post cites against MongoDB
• on-transactional-concurrency-control — snapshot isolation and serializability, the transaction-side guarantees the post keeps separate from replica consistency