Notesdistributed🌱 seedling
Linearizability
Also: Linearizable · Atomic Consistency · Strong Consistency · Linearizable Consistency
The system behaves as if there were one copy of the data, and every operation takes effect atomically at some instant between its request and its reply. If A completes before B starts, B sees A.
Why it exists
Locks, leader election, uniqueness constraints and anything coordinated through a side channel (write a file, then enqueue "process it") need reads to reflect every write that has already finished, wherever it landed.
How it works
- Checking a history: place one point inside each operation's interval so the points, in order, behave like a single register. If a placement exists, it's linearizable. Overlapping operations may take effect in either order. The classic violation: a read returns the new value, and a later read returns the old one.
- It's local: if every object is linearizable, the system of objects is.
- Building it: a single leader that confirms leadership with a majority per read (ReadIndex), routing reads through the replicated log, or a Lease with bounded clock drift. Compare-and-set and locks need Consensus; plain reads and writes can also use quorums whose reads write the newest value back before returning.
- Not enough on their own: Quorum reads with w + r > n and no write-back, and reads from a leader that may have been deposed.
Trade-offs
| Gains | Costs |
|---|---|
| one-copy semantics; easy reasoning | a majority round trip (or a lease) per operation |
| makes locks and uniqueness safe | minority side of a partition must stop |
| composes across objects | cross-region latency on every request |
In practice
- etcd: linearizable reads by default; Jepsen (2020) found its key-value operations strict serializable.
- MongoDB:
"linearizable"read concern, primary only, single document, "may be significantly slower"; always setmaxTimeMS. - Cassandra: linearizable compare-and-set via Paxos lightweight transactions.
Pitfalls
- Confusing it with Serializability, which is about transactions and has no real-time requirement (both together is strict serializability), or assuming "reads go to the leader" is enough.
Connections
- Part of
- Consistency Model
- Builds on this
- CAP Theorem
- Mentioned
- Lease
Recall
These cards are also in your review deck, scheduled with spaced repetition.