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.

Also in: Consistency Models › Building linearizable systems

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 set maxTimeMS.
  • 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.

Recall

These cards are also in your review deck, scheduled with spaced repetition.