Lesson 23 · Consistency models · Module 3

One Copy, One Instant

Lesson 01 gave you a user who could not see their own write, and a name for the narrow fix. This lesson gives the formal name for the strongest thing you could have asked for instead — the guarantee that the whole fleet of replicas behaves as if it were a single variable, updated at single instants. It is the most useful word in distributed systems, and the most expensive property to buy.

The win in this lesson: you will be able to take a picture of concurrent operations, point at it, and say "this history is linearizable" or "this one is not, and here is the operation that breaks it" — and then state exactly what the property costs that weaker models do not charge you.

1. The problem: "consistent" is not a word

Every database markets itself as consistent. The word is worthless on its own, because it names a whole family of promises of wildly different strength and price. Jepsen's reference guide starts by making the term mean something precise:

"A consistency model is a safety property which declares what a system can do. Formally, a consistency model defines a set of histories that a system can legally execute."
Jepsen, Consistency

That reframing is the whole lesson in one move. A consistency model is not an adjective about a system; it is a filter over observed behaviour. You record what the clients actually saw — a history — and the model says legal or illegal. That makes it checkable, which is exactly why Jepsen exists.

Here is a history that a great many production systems will happily produce, and that reads wrong to every human who sees it. Three clients, three replicas, quorum reads and quorum writes throughout.

The shaded band is the window in which the system serves a read that has already been contradicted. Nothing here is a bug in the usual sense — no message was lost, no replica crashed, no clock went wrong. The write simply reached A before it reached B and C, and the two readers happened to pick different quorums. Kleppmann's version of this exact exchange is Slide 132 of the Cambridge notes.

"Slide 132 […] shows an example of a system that uses quorum reads and writes, but is nevertheless non-linearizable. […] client 3 observes an older value than client 2, even though the real-time order of operations would require client 3's read to return a value that is no older than client 2's result."
Kleppmann, Distributed Systems notes, University of Cambridge, §7.2

Callback: this is the dial from lesson 05

In lesson 05 you turned R and W until R + W > N and the read quorum was guaranteed to overlap the write quorum. Look at the diagram again: the quorums did overlap. B was in both. Overlap only guarantees that a reader can see the newest value it is told about; it says nothing about what the next reader, using a different quorum, will see. R + W > N is not linearizability, and this lesson is the proof.

2. The one-copy illusion, defined

Linearizability is the model that outlaws the history above. The informal definition is two lines, and both lines matter:

"Informally: every operation takes effect atomically sometime after it started and before it finished […] All operations behave as if executed on a single copy of the data (even if there are in fact multiple replicas)"
Kleppmann, §7.2, Slide 128

The right-hand box is a lie, and that is the point. Linearizability is the contract that the lie is never detectable from outside. The whole cost of the model is the machinery needed to keep the left-hand picture from ever leaking through.

Why "recency", and why real time

The reason to want this property is narrower than "correctness". It is freshness:

"The main purpose of linearizability is to guarantee that nodes observe the system in an 'up-to-date' state; that is, they do not read stale (outdated) values."
Kleppmann, §7.2

And the ordering it uses is wall-clock ordering, not causality. This is the distinction that catches people who have just learned about happens-before:

"linearizability is defined in terms of real time […] a hypothetical global observer who can instantaneously see the state of all nodes […] determines the start and finish times of each operation."
Kleppmann, §7.2

The definition to memorise

A history is linearizable if you can choose one instant inside each operation's invocation-to-response window — its linearization point — such that executing the operations in the order of those instants, one at a time, against a single copy of the data, produces exactly the results the clients actually saw.

3. Reading a history: one legal, one not

This is the skill. Draw each operation as a horizontal bar from the moment the client issued it to the moment the client got an answer. Then try to place one dot inside each bar so the story makes sense on a single variable. If you can, the history is linearizable. If no placement works, it is not.

This diagram is the lesson. A bar is a window of uncertainty, not an event; the client knows only that the operation happened somewhere inside it. A history is legal when some choice of instants inside the bars tells a consistent single-copy story. In history B the crosses mark every candidate instant for client 3's read: all of them lie after the register became v1, so all of them would have to return v1. The system returned v0, so no linearization exists.

Two rules fall straight out of the picture, and they are all you need in a design review:

Overlapping operations are free. "Client 2's get operation overlaps in time with client 1's set operation […] Either outcome is fine in this case." Concurrency is where the model declines to have an opinion.
Non-overlapping operations are binding. "Client 2's operation finishes before client 3's operation starts […] Linearizability therefore requires client 3's operation to observe a state no older than client 2's operation." Once an answer has been handed to somebody, time cannot run backwards for anybody.

Jepsen states the same rule as a one-line test you can apply to any pair of operations:

"Linearizability is one of the strongest single-object consistency models, and implies that every operation appears to take place atomically, in some order, consistent with the real-time ordering of those operations: e.g., if operation A completes before operation B begins, then B should logically take effect after A."
Jepsen, Linearizability

4. Linearizable is not serializable — they are different axes

These two words are confused constantly, including in vendor documentation. They are not points on one scale. They answer different questions, and a system can have either, both, or neither.

"Don't confuse linearizability with serializability, even though both words seem to mean something like 'can be arranged into a sequential order'. Serializability means that transactions have the same effect as if they had been executed in some serial order, but it does not define what that order should be. Linearizability defines the values that operations must return, depending on the concurrency and relative ordering of those operations."
Kleppmann, §7.2

Two axes, not one scale. Serializability buys you isolation across many objects and says nothing about when; linearizability buys you recency on one object and says nothing about grouping. The top-right corner is the expensive one you can only reach by paying for both.

Jepsen makes the gap concrete with a case that sounds absurd until you realise it is legal:

"However, it does not impose any real-time, or even per-process constraints. […] a serializable database can always return the empty state for any reads, by appearing to execute those reads at time 0."
Jepsen, Serializability

A perfectly serializable database may answer every read as though it ran before the world began, and it has broken no rule. That is what "it does not define what that order should be" cashes out to. Buy both and the combination has a name:

"You can think of strict serializability as serializability's total order of transactional multi-object operations, plus linearizability's real-time constraints."
Jepsen, Strong Serializability

5. What it costs

Performance and scalability are the obvious costs, and the smaller ones. Every operation is messages and waiting; a leader that sequences all updates becomes a throughput ceiling. The real bill is availability, and it is not negotiable by engineering effort:

"Perhaps the biggest problem with linearizability is that every operation requires communication with a quorum of replicas. If a node is temporarily unable to communicate with sufficiently many replicas, it cannot perform any operations. Even though the node may be running, such a communication failure makes it effectively unavailable."
Kleppmann, §7.2

Jepsen states it as a flat property of the model, not a property of any implementation:

"This model cannot be totally or sticky available; in the event of a network partition, some or all nodes will be unable to make progress."
Jepsen, Linearizability

The shaded band is the cost, drawn. Node E has not crashed — it is healthy, it has the data, and it is refusing to serve you, because the only way to be sure its copy is current is to ask a quorum it cannot reach. This is the CAP trade-off as a message exchange rather than a slogan: during a partition the two arrows at the bottom are the entire menu.

CAP, stated correctly

"Pick 2 of 3" is the wrong framing and it has cost the industry years of muddled design reviews. Kleppmann: "A system can be both linearizable and available as long as there is no network partition, and the choice is forced only in the presence of a partition." The question is never "are we CP or AP" in the abstract. It is: when the network splits, which of those two arrows do we want this endpoint to take? — and different endpoints in one product can answer differently.

Model	What it promises	Real-time order?	In a partition
Linearizable	One copy, one instant per operation. No stale reads, ever.	Yes — the defining feature	Nodes without a quorum must refuse
Sequential	Some total order all processes agree on, matching each process's own order	No — a process "may read arbitrarily stale state"	Also unavailable: "cannot be totally or sticky available"
Causal	Causally-related operations appear in the same order everywhere; independent ones may differ	No	Sticky available — keep talking to the same node and you make progress
Eventual	Replicas converge if the writes stop. Nothing about any individual read.	No	Fully available — every node answers from local state

The one idea to carry out of this lesson

Linearizability is a recency guarantee on a single object, defined by real time, and paid for with a quorum round trip on every operation. Every clause in that sentence is a place where a cheaper model is hiding: give up recency and you get eventual; give up real time and you get sequential; give up single-object and you are talking about transactions instead.

6. Residual risk

Suppose you buy it. Four things are still true, and each one has burned a real system.

It is per object. Two linearizable keys do not make a linearizable pair. Read key a, then key b, and you may observe a combination that never existed. If that matters, you wanted strict serializability, and nobody sold it to you.
Real time needs real clocks, or a substitute. The global observer in the definition does not exist. Kleppmann's note on Spanner is blunt about the consequence: "linearizability depends on real-time order, and logical clocks may not reflect this!" Systems that close the gap do it with bounded-uncertainty hardware clocks and by waiting out the bound — latency you pay on purpose.
The property is about the store, not your application. A linearizable database behind a cache, a CDN, or a client-side store is not a linearizable system. Lesson 01's stale read is back the moment there is a copy the model does not cover.
Availability is lost exactly when you are being watched. The unavailability arrives during a partition — the same moment your dashboards light up and your users are already unhappy. A correctness property that converts network trouble into downtime is a choice, and it should be a deliberate one.

7. Check yourself

Cover the page above this line. If you can redraw history B from memory and say which operation breaks it, you own this lesson.

8. Back to your world

Most systems you will work on are not linearizable, and should not be. The value of the word is that it gives you a fixed point to measure against, and a way to make a vague argument concrete in about thirty seconds.

Next time a design discussion stalls on whether something is "consistent enough", draw the bars. Put the write on one line, the two reads that worry you underneath, and ask whether an instant can be placed inside each. Then ask the second question, which is the one that actually decides the design: which endpoints must refuse to answer during a partition, and which may answer with something slightly old? That single sentence turns a philosophical argument into a product decision, and it is the reason this word is worth carrying.

Ask me things. "walk me through the ABD algorithm step by step" · "show me a history that is sequentially consistent but not linearizable" · "why is linearizable compare-and-swap equivalent to consensus?" · "how does a bounded-uncertainty clock buy back real-time order?" · "I think our system is linearizable because we use a single leader. Grill me."