Consistency models

Ask three engineers what "consistent" means and you get three correct answers. In ACID, the C means every transaction leaves the database obeying its rules: no negative balance, no duplicate username. In the CAP theorem, C means linearizability, defined below. Consistent hashing is about which server stores a key and has nothing to do with either. This article is about a third meaning, replica consistency: what the copies of one piece of data may show a reader.

Why is there a question at all? Because the shop this article follows keeps one copy of its database in London and another in New York, and every change made in one city takes time to reach the other. During that gap the copies disagree, and whoever reads the wrong one sees the past.

Linearizable is the promise that the system behaves as if there were a single copy, and every operation took effect at one instant between the moment it started and the moment it returned. The instant is what matters: once a write has returned, every read that starts afterward, from any client in any city, must see it. This is what people usually mean by strong consistency, and it is the C in CAP.

The real-time requirement is the expensive part. The replica that answers must know it holds the latest write, so either every read goes to one leader or the replicas coordinate before answering. Both cost round trips, and neither works while the cities cannot talk. That bill is CAP & PACELC.

Databases advertise serializable as their strongest isolation level, and readers assume it implies freshness. It does not. Serializability only says transactions appear to run one at a time in some order, and that order may place a transaction that committed a minute ago after yours. Isolation levels have their own page (Transactions & isolation levels). The row to remember: serializable plus linearizable is strict serializable.

Sequential consistency keeps one half of linearizability and drops the other. Everyone still sees the same single order of operations, and each client's own operations keep their program order, but the shared order need not match the clock. A review posted in London at 12:00:00 and one posted in New York at 12:00:05 may be shown to everyone, in both cities, with New York's first. Nobody can tell, unless they compare wristwatches.

Causal consistency drops the shared order too and keeps only the order that matters: if one operation could have influenced another, everyone sees them in that order. It is the happens-before relation from Time, clocks & ordering, turned into a promise. A seller reads a question on a product page and writes the answer, so the answer depends on the question: no copy may show the answer without it. Two unrelated reviews, though, may appear in different orders in the two cities. That is what causal gives up.

Causal is a special rung. It has been proved that a strengthening of it, real-time causal, is the strongest model a system can offer while staying available to every client and still converging. A common practical version is causal+: causal order plus a rule that makes conflicting writes converge. Anything stronger means coordinating across the ocean.

Eventual consistency is the weakest promise still worth a name. The definition: if no new updates are made to the object, eventually all accesses will return the last updated value. Read it twice. It promises convergence and only convergence: no bound on how long, and nothing about what a read returns before then. Put bluntly, it only says something good will eventually happen. It never says something bad will not.

In practice the gap is usually short. Copies in one data center typically catch up within milliseconds, and copies in another region within about a second. Usually short is not always short: under load or during a partition the window stretches, and the promise gives you no number to plan around. Why timestamps are a poor merge rule is Time, clocks & ordering.

Most users never notice a stale copy. They notice when the system contradicts them. Four promises stop this. They are the session guarantees: promises about one client's own sequence of reads and writes rather than about the system as a whole.

All four are cheap. Pinning a session to one replica gives read-your-writes and monotonic reads at once; a version number carried by the client, which a replica waits to reach, covers the rest. Together they amount to causal consistency for one client, which is why they sit just below it on the ladder.

Which model? Wrong question, if asked once per system. Ask it per feature. The shop's gift-card balance, stock counts, wishlist counter, your profile and the sign-up form live in the same two copies and need different answers.

The price rises with each rung up. A linearizable operation waits for a round trip between the cities, about 70 ms between London and New York, and must refuse to answer while they cannot talk. An eventual one answers from the local copy and keeps answering through the outage. How that trade is forced, and what it costs when nothing is broken, is CAP & PACELC.