Consistency models, CAP and PACELC

What "consistent" means once data is copied

As soon as a system keeps more than one copy of a piece of data, on replicas in different zones, in caches or in other services, the copies can disagree for a while. A consistency model is the contract that says which disagreements clients may observe. It is a promise about what reads can return given the writes that have happened, and therefore a promise about which surprises application code must handle.

Beware the overloaded word. The C in ACID (Section 0.5) means a transaction moves the database from one valid state to another, respecting rules such as "a balance never goes below zero". The C in CAP means something different and narrower: every read behaves as if there were a single, up-to-date copy. Database isolation levels such as serialisable or read committed are a third family, about concurrent transactions; they are covered in transactions and isolation. This section is about the guarantees of replicated data.

Consistency models from strongest to weakest

Linearisability, defined by Maurice Herlihy and Jeannette Wing in 1990, is the strongest single-object model. Every operation appears to take effect instantaneously at some point between its start and its end, and all clients see the same order, which respects real time: once a write has completed, every read that starts afterwards sees it or something newer. The system behaves as though there were one copy. Food-delivery example: two customers try to claim the last discount code; with a linearisable store, exactly one succeeds and the other sees it gone, whichever replica they reach.

Sequential consistency, defined by Leslie Lamport in 1979 for multiprocessors, keeps the single global order and keeps each client's operations in the order that client issued them, but drops the real-time requirement. A client may read a value that is slightly out of date, as long as everyone agrees on the order of all writes. It is rarely offered by name in distributed databases but explains the gap between "one agreed order" and "one agreed order that matches the clock".

Causal consistency requires only that operations which are causally related are seen in the same order by everyone: if writing B depended on having seen A, nobody may see B without A. Concurrent, unrelated writes may be seen in different orders by different clients. Example: a restaurant replies "Yes, it is gluten-free" to a customer's question in the order chat; nobody should ever see the answer without the question. Causal consistency is attractive because Jepsen's widely used map of consistency models classifies it as achievable with sticky availability: it can keep working during a partition as long as each client stays with the same replica.

The session guarantees, described by Douglas Terry and colleagues in 1994, are weaker, per-client promises that remove the most confusing anomalies. Read-your-writes: after a customer changes the delivery address, that customer's next read shows the new address, even if other users see it later. Monotonic reads: once a client has seen the order status "out for delivery", it never later sees "preparing" because a later read hit a lagging replica. (Two further guarantees, monotonic writes and writes-follow-reads, constrain the order in which a client's writes are applied.)

Eventual consistency, popularised by Werner Vogels in 2008, is the weakest useful guarantee: if no new writes arrive, all replicas eventually converge on the same value. It says nothing about how long that takes or what may be read in the meantime, and a basic implementation that resolves conflicting writes by keeping the one with the latest timestamp, known as last write wins, silently discards the other. Stronger forms, such as strong eventual consistency with conflict-free replicated data types (CRDTs), guarantee that replicas which have received the same updates hold the same state, by using data types whose concurrent updates always merge, such as counters and sets.

CAP: what it actually says

Eric Brewer presented the CAP idea as a conjecture in his keynote at the ACM Symposium on Principles of Distributed Computing (PODC) in 2000. In 2002 Seth Gilbert and Nancy Lynch published a formal proof, making it a theorem for their precise definitions. Consistency meant linearisability. Availability meant that every request received by a node that has not failed must result in a response. Partition tolerance meant the system keeps its promises even when the network loses arbitrarily many messages between nodes.

Read carefully, the CAP theorem is narrow. It says that when a network partition occurs, so that some nodes cannot reach others, a replicated system must choose for each request between consistency and availability. A node cut off from the latest writes can either refuse to answer (or wait until the partition heals), preserving consistency, or answer with what it has, preserving availability at the risk of returning stale data or accepting conflicting writes. The diagram shows the dilemma for a ticketing system selling seat 14C.

Several popular readings are wrong. "Pick any two of three" suggests partition tolerance is optional, but in any system that communicates over a network, partitions happen whether or not you choose them; the only real choice is how to behave when they do. A so-called "CA" system is one that has not decided what to do when a partition occurs; that is defensible only where partitions are practically impossible, such as on a single node. "Our database is CP (or AP)" is usually imprecise: CAP availability is a very strong property that many systems marketed as highly available do not have, and many systems called CP are not linearisable either. Martin Kleppmann argued in 2015 that databases should not be labelled CP or AP at all, because most fit neither definition and their behaviour depends on configuration. "CAP explains our latency" is also wrong: CAP says nothing about what happens when there is no partition, which is most of the time.

CAP twelve years later

In 2012, in an IEEE Computer article titled "CAP Twelve Years Later: How the Rules Have Changed", Brewer himself explained that the two-of-three framing had misled people. Partitions are rare, so a system can offer both consistency and availability almost all of the time; the choice applies only during a partition, and only to the operations affected. The choice need not be global either: different operations and different data can make different choices.

Brewer recommended designing explicitly for partitions in three steps: detect the partition, enter an explicit partition mode in which some operations are limited (for example, accept orders but postpone refunds), and run a recovery process afterwards that merges state and compensates for mistakes made during the partition. He also noted that CAP's C is single-copy consistency, a stricter subset of what ACID's C protects, and that invariants such as "never oversell" may have to be repaired after the fact. This framing leads directly to the business-level compensations of sagas: an airline that oversells a flight compensates the passenger rather than refusing all bookings during a network fault.

PACELC: the trade-off you pay every day

Daniel Abadi pointed out in a 2010 blog post, and in a 2012 IEEE Computer article, "Consistency Tradeoffs in Modern Distributed Database System Design: CAP is Only Part of the Story", that CAP ignores the trade-off designers actually face most of the time. PACELC reads: if there is a Partition, choose between Availability and Consistency; Else, in normal operation, choose between Latency and Consistency.

The "else" half is the important addition. To make a read consistent, a replicated system must coordinate: send the write to other replicas and wait for acknowledgements, or route every read to a leader, or contact several replicas and compare. Every one of those costs network round trips, and across regions a round trip can cost tens or even hundreds of milliseconds. A system that answers from the nearest replica without coordinating is faster but may be stale. That trade-off is paid on every request, partition or not.

PACELC classifications are often quoted, such as PA/EL for systems tuned for speed and availability and PC/EC for systems that always prefer consistency. Treat them as descriptions of a configuration, not of a product: the same database can be PA/EL in one deployment and PC/EC in another, depending on settings chosen per table, per query or per request.

Quorums: tuning consistency with arithmetic

Leaderless replicated stores, in the style of Amazon's Dynamo paper (2007), let each operation choose how many replicas to involve. With N replicas of an item, a write is acknowledged when W replicas have stored it, and a read collects answers from R replicas and returns the newest version among them. If R + W > N, every read set overlaps every write set in at least one replica, so a read will include at least one copy of the latest acknowledged write.

The choice of R and W trades consistency, latency and availability. Lower values mean waiting for fewer, faster replicas and tolerating more failures, at the price of possible stale reads. Higher values mean the opposite. Writes are usually sent to all N replicas anyway; W only decides how many acknowledgements the client waits for.

Quorum overlap is necessary for fresh reads, but it is not, on its own, linearisability. Concurrent writes may be ordered by timestamps from clocks that disagree, so a later write can lose under last-write-wins. A write that failed after reaching some replicas may still be visible on them. "Sloppy" quorums, which accept writes on substitute nodes during failures, break the overlap. And two reads that overlap a write still in progress can see new then old values unless the reader repairs lagging replicas before returning. Stores that need true compare-and-set semantics add a consensus protocol, such as the Paxos-based lightweight transactions in Apache Cassandra, for those operations only.

How well-known databases can be configured

Real products rarely sit at a single point on the ladder. They expose settings, and the right description is "how this deployment is configured". Four common examples follow; check the current documentation of the version you run, because defaults change between releases.

Choosing consistency per use case

The most useful habit is to stop asking "is our system consistent?" and ask, for each piece of data and each operation, what goes wrong if a client sees a stale or reordered value, and how much does it cost? Money moving, unique resources and invariants usually justify strong consistency and its latency. Counters, feeds, recommendations and analytics usually do not. Many user-facing anomalies disappear with just the session guarantees, which are cheap: route a user's reads to the primary for a few seconds after that user writes, or carry a version token in the session and wait until the replica has caught up with it.