Linearizability

The guarantee that a replicated system behaves as if there were one copy of the data: what it promises, when you need it, how systems provide it, and what it costs.

Overview

Replication keeps several copies of the same data. Clients would like to ignore that and treat the system as if it held a single copy. Linearizability is the promise that makes this possible: every read and write appears to happen at one instant, and that instant falls between the moment the operation starts and the moment it returns.

Behave like one copy

Maurice Herlihy and Jeannette Wing defined linearizability in 1990. Jepsen's summary is a good working definition: every operation appears to take effect atomically, in some order that matches real time. If operation A finishes before operation B starts, B must see the effect of A.

The practical rule for a single value is simple. Once any read has returned a new value, no later read, by any client on any replica, may return the old one.

Without linearizability, Bob could see a score, a stock level or a lock owner that Alice has already seen replaced. With it, both behave as if they had talked to one machine.

Not the same as serializability

The two words sound alike and are often mixed up. They answer different questions.

About — Single reads and writes on one object — Transactions over many objects
Promise — Each operation takes effect at one instant, in real-time order — Transactions give the same result as some one-at-a-time order
Real time — Must be respected — Not required: the chosen order may differ from real time
Example of one without the other — A single register with no transactions — Snapshot reads that return an older consistent state

A system that gives both is strictly serializable. Google calls Spanner's version of this external consistency.

When you really need it

Most data does not need linearizability. A few jobs cannot be done correctly without it, because they depend on every node agreeing on one current value.

Leader election — Two nodes both read 'no leader' and both take over
A lock — Two clients both see the lock as free and both enter
A uniqueness rule, such as usernames — Two sign-ups both see the name as unused and both claim it
Data read through two channels — A worker gets a message from a queue, reads storage, and finds the old file the message refers to

The last row is easy to miss. The system has two paths: a message through a queue, and the data through storage. If the message arrives first and the storage read is not linearizable, the worker sees data older than the event it was told about.

Which replication methods can provide it

Single leader, reads from the leader — Can be — Only one copy decides, but a leader that wrongly thinks it is still leader can serve stale reads
Consensus (Raft, Paxos, ZAB) — Yes, if reads also go through the log or a leader check — A majority agrees on the order of every operation
Multi-leader — No — Two leaders accept conflicting writes at the same time
Leaderless with quorums — Not by default — Even with w + r > n, a later read can miss a write that an earlier read saw; reads and writes are linearizable only with synchronous read repair, and compare-and-set never is
Reads from asynchronous followers — No — Followers lag the leader

etcd, which uses Raft, makes reads linearizable by default. Its docs say this costs latency because each such read must go through Raft, and clients can choose 'serializable' reads that may be stale in exchange for lower latency. Watches in etcd are not linearizable.

ZooKeeper sends every update through one leader and gives each a zxid, so all updates have one total order. Its reads are served by whichever server the client is connected to and can be stale. The programmer's guide says it does not promise the same view to all clients at once, and that a client should call sync before a read that must be current.

Cassandra offers linearizable compare-and-set through lightweight transactions: INSERT ... IF NOT EXISTS and conditional UPDATE. Its guarantees page says these use Paxos to give linearizable consistency, and its CQL documentation warns that these use Paxos and have a real performance cost.

What it costs

Linearizability needs coordination, and coordination needs the network. The CAP theorem, proved by Seth Gilbert and Nancy Lynch in 2002, makes this precise: when the network splits, a replica that cannot reach the others must either refuse requests or risk answering with stale data. Jepsen puts it plainly: a linearizable system cannot be totally available; during a partition some nodes cannot make progress.

Eric Brewer, who first proposed CAP, wrote in 2012 that 'two of three' is misleading. Partitions are not something you can choose to avoid, so the real choice is what to do when one happens. The C in CAP means single-copy consistency, a much narrower idea than the C in ACID.

Even with no partition, linearizability is slower: every write, and every read that must be current, waits for a majority round trip. Across regions that round trip can be tens of milliseconds or more. This is why many systems offer it only where it is asked for.

What you will be able to do

Define linearizability in one sentence and spot a history that breaks it.
Explain how it differs from serializability and what strict serializability means.
Name the jobs that need it: leader election, locks, uniqueness, two-channel reads.
Say which replication methods and which systems can provide it, and at what cost.

Key concepts

Linearizability: Every operation appears to take effect at one instant between its start and its end, in an order that matches real time. The system behaves like one copy.
Recency guarantee: Once any read returns a new value, no later read by anyone may return an older one.
Serializability: A property of transactions: they give the same result as some one-at-a-time order, which need not match real time.
Strict serializability: Serializability plus linearizability. Spanner provides it and Google calls it external consistency.
Sequential consistency: All processes see operations in one order that respects each process's own order, but not necessarily real time. Weaker than linearizability.
CAP theorem: During a network partition, a replicated system must choose between linearizable answers and answering every request.
Lightweight transaction: Cassandra's conditional write (IF NOT EXISTS, IF col = value), which uses Paxos to give a linearizable compare-and-set.

When to use it

Choosing a store for leader election, locks or unique constraints
Explaining the CAP theorem and what a system gives up during a partition
Justifying ZooKeeper or etcd for coordination instead of a general database
Deciding which reads in a design must be current and which can be stale

Interview questions

What is linearizability, in one or two sentences?
When do you actually need linearizability?
What is the difference between linearizability and serializability?
Are quorum reads and writes (W + R > N) linearizable?
How do etcd and ZooKeeper differ on read consistency?