Linearizability
Adapted from: Martin Kleppmann, Designing Data-Intensive Applications (O'Reilly, 2017), Chapter 9 — rewritten and condensed for teaching.
Everything in Faults, Partial Failures, and Unreliable Networks, Unreliable Clocks, and Knowledge, Truth, and Lies established the same theme: distributed systems face a genuinely wide range of ways to go wrong. The response isn't to hope faults don't happen — it's to find powerful, general-purpose abstractions that hide those faults from applications, the same way a database transaction lets application code pretend crashes, concurrent access, and unreliable disks simply don't exist. This lesson (and the three that follow) build up exactly that kind of abstraction for distributed systems — starting with linearizability, one of the strongest, most intuitive consistency guarantees a database can offer.
What Linearizability Actually Promises
Problems with Replication Lag already established that asking two replicas the same question at the same moment can produce two different answers — an inescapable consequence of replication lag, regardless of whether you're using single-leader, multi-leader, or leaderless replication. Linearizability (also called atomic consistency, strong consistency, or external consistency) is the guarantee that makes this problem disappear entirely from the application's point of view: it makes a system behave as if there were only a single copy of the data, with every operation on it taking effect atomically.
The concrete promise: the instant one client's write successfully completes, every subsequent read from any client is guaranteed to see that new value. Linearizability is, at its core, a recency guarantee — a read is guaranteed to reflect the most recent write, never a stale one.
A concrete non-example makes this vivid: Alice and Bob are in the same room, both checking their phones for the final score of a match. The instant the result is announced, Alice refreshes and sees it — and excitedly tells Bob out loud. Bob, hearing this, immediately refreshes his own phone — but his request happens to land on a lagging replica, and his phone still shows the match as ongoing. Bob's query is chronologically after Alice's (he only refreshed because he heard her), yet it returned older data. That's a linearizability violation — and it's jarring specifically because Bob has an independent, real-world reason to expect his own read to be at least as fresh as Alice's.
Check: what linearizability promises
The basic idea of linearizability
1 / 2What is the core, informal idea behind linearizability?
Pick an answer to see if you are right.
What Makes a System Linearizable, Precisely
To pin the idea down more precisely, consider a single value — called a register in the distributed systems literature (in practice: one key in a key-value store, one row, one document) — with three operations: read(x) ⇒ v (read register x, get back value v), write(x, v) ⇒ r (set x to v, get back a response r), and cas(x, v_old, v_new) ⇒ r (compare-and-set: atomically set x to v_new, but only if its current value is v_old; otherwise leave it unchanged and return an error).
Picture several clients concurrently reading and writing the same register, each request drawn as a bar from when it was sent to when the response arrived — since network delay is variable, a client genuinely doesn't know exactly when, within that window, the database actually processed its request. With x starting at 0 and one client writing 1:
- A read that completes before the write begins must return the old value,
0— no ambiguity possible. - A read that begins after the write completes must return the new value,
1, if the system is linearizable — by then the write is unambiguously done. - A read overlapping the write in time could legitimately return either
0or1— from the outside, you can't know exactly when, within the write's own window, it actually took effect.
That third rule alone isn't quite enough to fully specify linearizability, though — taken alone, it would still permit an overlapping read to flip back and forth between 0 and 1 several times while the write is in progress, which is obviously not what "acts like a single copy of the data" should mean. Linearizability adds one more constraint: once any read has returned the new value, every subsequent read — on any client — must also return the new value, even before the write operation has technically finished responding. Picture it as if there's some single, precise instant — somewhere between the write's start and end — where x atomically flips from 0 to 1; every read before that instant sees 0, every read after sees 1, with no going back.
This is exactly the same shape as the Alice-and-Bob example: once Alice has read the new score, Bob (reading later) must see it too — there's no valid execution where he legitimately sees the old one again. Formally, every operation can be marked with the single point in time it appears to have taken effect, and those markers — joined up across every operation, from every client — must form a valid, causally sensible sequence of reads and writes that only ever moves forward in time, never backward. That's linearizability's true defining rule: given a full log of a system's requests and responses, you could — in principle, if expensively — check it against this rule and mechanically verify whether the system actually behaved as if there were only one copy of the data throughout.
A subtlety worth internalizing: linearizability constrains the order operations appear to take effect, not the order clients happened to send their requests in. A read sent before two writes can still validly return the value from the second write, as long as all three operations genuinely overlap in time — the read might simply have been delayed slightly in the network, reaching the database after both writes had already landed. Similarly, a read can return a value before the writing client has even received its own "write succeeded" confirmation — that confirmation was just delayed on its way back. Neither case breaks linearizability; both are honest consequences of finite, variable network delay.
Check: precise linearizability
What precisely makes a system linearizable
1 / 2Why is it NOT sufficient for a linearizable system to simply say "a read concurrent with a write may return either the old or the new value"?
Pick an answer to see if you are right.
Linearizability vs. Serializability: Easy to Confuse, Genuinely Different
The names sound alike, and both roughly mean "can be arranged in a sequential order" — but they answer completely different questions:
| Serializability | Linearizability | |
|---|---|---|
| Scope | Transactions, each possibly touching multiple objects | A single register (one object) |
| Guarantee | Transactions behave as if run in some serial order — not necessarily the order they actually ran in | Reads/writes reflect the most recent state — a genuine recency guarantee |
| Prevents | Transaction-level races, like write skew | Nothing about multi-object transactions on its own |
A database can offer both at once — that combination is called strict serializability (or strong one-copy serializability). Implementations built on two-phase locking or genuine serial execution typically end up linearizable as a side effect of how they work. Serializable snapshot isolation, notably, is not linearizable — it deliberately reads from a fixed, slightly-in-the-past consistent snapshot specifically to avoid lock contention between readers and writers, and that's precisely what breaks the recency guarantee linearizability requires.
Where Linearizability Actually Matters
Viewing a slightly-stale sports score is low-stakes. A few real situations genuinely depend on linearizability to work correctly at all:
Locking and leader election. A system electing a single leader — to avoid split brain — commonly does it via a lock: every candidate node races to acquire it, and whoever succeeds becomes leader. That lock is useless unless every node unambiguously agrees on who holds it right now — which is exactly a linearizability requirement. Coordination services like ZooKeeper and etcd implement exactly this, backed internally by consensus algorithms (covered later in this series) specifically to make their operations linearizable and fault-tolerant at once.
Uniqueness constraints. A username, an email address, a file path — anything that must uniquely identify one thing — needs linearizability to enforce correctly at write time. This is structurally the same problem as a lock: creating a username is, in effect, "acquiring a lock" on that specific string — implementable as an atomic compare-and-set, claiming the username only if it isn't already taken. The identical requirement shows up anywhere a hard constraint needs everyone to agree on one current, correct value: an account balance that must never dip negative, inventory that must never oversell, a seat that can't be double-booked. (Some of these constraints can be relaxed in practice — an overbooked flight can bump a passenger to a later one and compensate them — in which case linearizability may not actually be necessary. But a genuine hard uniqueness constraint has no such escape hatch.)
Cross-channel timing dependencies. In the Alice-and-Bob example, the violation only became visible because a second, independent channel existed — Alice's voice reaching Bob's ears — alongside the database itself. The identical shape shows up in real systems: a web server writes a photo to file storage, then separately places a "resize this" instruction on a message queue for a background worker. If file storage isn't linearizable, the resizer might fetch the queued job faster than the storage system's own internal replication catches up — processing a stale (or entirely missing) version of the image, permanently desynchronizing the full-size and thumbnail versions. The race exists precisely because there are two separate communication channels (storage and the queue) with no ordering guarantee between them — linearizable storage is the simplest way to close that gap, though not the only one.
Check: where linearizability is actually needed
Real use cases for linearizability
1 / 3Why does implementing leader election via a distributed lock fundamentally require that lock to be linearizable?
Pick an answer to see if you are right.
Can Your Replication Method Actually Deliver Linearizability?
| Replication method | Linearizable? |
|---|---|
| Single-leader | Potentially — reads from the leader (or a synchronously-updated follower) can be linearizable, but only if you can be fully certain who the current leader actually is; a "delusional" node that still believes it's the leader (already covered in Knowledge, Truth, and Lies) can violate it, and asynchronous failover can lose already-confirmed writes outright |
| Consensus algorithms | Yes — despite structurally resembling single-leader replication, consensus protocols add explicit protections against split-brain and stale reads, which is exactly how ZooKeeper and etcd deliver genuinely linearizable storage |
| Multi-leader | No — writes are accepted independently, concurrently, on multiple nodes, and only reconciled asynchronously afterward, which is structurally incompatible with "one single, agreed-upon copy" |
| Leaderless (Dynamo-style) | Probably not, even with strict quorums (w + r > n) — "last write wins" conflict resolution based on physical clocks is essentially never linearizable (clock skew can't guarantee it lines up with true event order), and sloppy quorums break the guarantee outright |
Even Strict Quorums Aren't Automatically Linearizable
It's tempting to assume w + r > n alone guarantees linearizability in a Dynamo-style system — but variable network delay opens a genuine race. Picture n = 3, w = 3: a writer sends x = 1 to all three replicas. Concurrently, client A reads from a quorum of two nodes and happens to see the new value 1 on one of them. Also concurrently, client B — whose read genuinely starts after A's read has already completed — reads from a different pair of two nodes and gets back the old value 0 from both. The quorum condition (w + r > n) is technically satisfied — but this execution still isn't linearizable, because B's read, despite starting later, returned staler data than A's earlier one. The same Alice-and-Bob shape, again.
It is possible to make Dynamo-style quorums genuinely linearizable — but only at a real performance cost: a reader must perform synchronous read repair before ever returning a result, and a writer must first read the latest quorum state before it's allowed to write. Even then, only plain reads and writes can be made linearizable this way — a linearizable compare-and-set specifically cannot, because that operation is, provably, equivalent to solving consensus outright (a deep connection this series returns to in a later lesson). The safest working assumption: a leaderless Dynamo-style system does not provide linearizability, full stop.
Check: replication methods and linearizability
Which replication methods can deliver linearizability
1 / 3Why is multi-leader replication fundamentally incompatible with linearizability?
Pick an answer to see if you are right.
The Cost of Linearizability
Linearizability isn't free, and the trade-off shows up starkly in multi-datacenter deployments. Picture two datacenters, connected over an unreliable link, each internally healthy but temporarily cut off from each other. With multi-leader replication, each datacenter just keeps working independently, queuing up writes to exchange once the link recovers. With single-leader replication, the leader lives in exactly one datacenter — so any client stuck talking to the other datacenter can neither write, nor perform a linearizable read, until the network link is repaired. That client can still read from its local follower — just not with any recency guarantee.
The CAP Theorem, and Why It's Often Misunderstood
This trade-off generalizes far beyond multi-datacenter deployments — it applies to any linearizable database, on any unreliable network, even entirely within one datacenter. This is the real substance behind the famous CAP theorem (Eric Brewer, 2000): when a network partition occurs, you must choose between linearizability (some nodes become unavailable until the partition heals) and total availability (every node keeps serving, but the result isn't linearizable).
CAP is frequently — and misleadingly — summarized as "Consistency, Availability, Partition tolerance: pick two of three." That framing is broken, because network partitions are a kind of fault, not a design choice you get to opt out of — they will happen whether your architecture "picks" partition tolerance or not. A more honest phrasing: when partitioned, be either consistent or available; when the network is healthy, you can have both at once. CAP's formal definition is also narrower than its popular reputation suggests — it only ever considers one consistency model (linearizability specifically) and one kind of fault (network partitions) — it says nothing whatsoever about network delay, dead-but-not-partitioned nodes, or any of the many other trade-offs distributed systems actually have to navigate. CAP deserves real credit for kicking off a broader, valuable industry conversation about these trade-offs in the mid-2000s — but as a precise engineering tool for actually designing a system, it's mostly of historical interest today, superseded by more precise results.
It's Really About Performance, Not Just Fault Tolerance
Here's a genuinely surprising fact: even ordinary RAM on a modern multi-core CPU isn't linearizable. Each core keeps its own local cache; a write from one core isn't guaranteed to be visible to a read on a different core shortly afterward, unless you explicitly insert a memory barrier. Nobody would seriously invoke the CAP theorem to justify this — a single computer isn't dealing with network partitions at all. The real reason multi-core memory drops linearizability is pure performance: caches make memory access dramatically faster, and that's worth more, in this context, than perfect immediate consistency across cores.
The identical logic drives plenty of distributed databases that deliberately skip linearizability too — the primary motivation is very often speed, not fault tolerance. And there's a hard theoretical reason performance and linearizability are fundamentally in tension: Attiya and Welch proved that a linearizable read or write's response time is bounded below by the network's own delay uncertainty — in a network with genuinely variable delay (which, as Faults, Partial Failures, and Unreliable Networks established, is essentially every real network), linearizable operations are inescapably going to be slower than weaker-consistency alternatives. There is provably no cleverer algorithm that gets around this — which is exactly why weaker consistency models remain genuinely valuable for latency-sensitive systems, not merely a historical curiosity.
Practice: implement a linearizable username claim
The uniqueness-constraint use case, made concrete: implement the atomic compare-and-set logic a "claim this username" operation actually needs — succeeding only if the username is genuinely unclaimed at the moment of the attempt.
- Linearizability makes a distributed system behave as if there were a single copy of the data with atomic operations — a recency guarantee: once any client's read sees a new value, no subsequent read anywhere can see an older one.
- Linearizability is genuinely different from serializability — one is a recency guarantee on a single register, the other is an isolation guarantee across whole multi-object transactions; a database can offer both at once (strict serializability), or neither, or just one.
- Real uses of linearizability: leader election/locking (agreement on lock ownership), hard uniqueness constraints (usernames, inventory, seat booking), and closing race conditions across multiple independent communication channels.
- Only single-leader (carefully) and true consensus-based systems can reliably deliver linearizability; multi-leader cannot by construction, and leaderless/Dynamo-style systems generally cannot either, even with strict quorums.
- The CAP theorem, properly understood, says: when a network partition genuinely occurs, choose between linearizability and availability — not "pick 2 of 3" as it's popularly (and misleadingly) summarized. Beyond fault tolerance, linearizability has a real, unavoidable performance cost, provably tied to network delay uncertainty — which is exactly why many systems deliberately trade it away for speed.
Further Reading
- Martin Kleppmann — Designing Data-Intensive Applications (O'Reilly, 2017), Chapter 9
- Knowledge, Truth, and Lies — this series' previous lesson
- Ordering Guarantees — this series' next lesson: causality, total order broadcast, and Lamport timestamps
- Eric Brewer — "CAP Twelve Years Later: How the 'Rules' Have Changed"