Linearizability: The Promise Behind Fresh Reads

You save a change, refresh the page, and see the old value. The write succeeded. Your next request simply reached a database copy that had not caught up.

Replication helps a system survive failures, but it also creates several versions of what looks like one piece of data. Linearizability is a promise about how those copies behave: operations appear to act on one up-to-date copy, each taking effect at a single instant.

A later read must not go backwards

Once a write completes successfully, a read that starts afterward must see that value or a later write. A stale replica cannot return an earlier version.

The rule also applies when one reader has already seen a change, even if the writer is still waiting for confirmation. Assume nobody writes another value:

1. Alice reads the new value and receives her result.
2. Bob starts a read after Alice's read finishes.
3. Bob must not get the older value.

The football example in Designing Data-Intensive Applications makes this visible. Alice sees the final score and tells Bob. He refreshes afterward, but a lagging copy says the match is still playing.

sequenceDiagram
    participant A as Alice
    participant R1 as Copy 1
    participant B as Bob
    participant R2 as Copy 2
    Note over R1: Final score received
    Note over R2: Update delayed
    A->>R1: Read score
    R1-->>A: Match finished
    A->>B: The match is over
    B->>R2: Read score
    R2-->>B: Still playing (invalid)

Alice's message establishes the order: her read finished before Bob's began. If their reads overlapped, different results alone would not prove a violation. Overlapping operations can be ordered either way, provided the complete history still behaves like one copy.

This imagined instant when an operation takes effect is its linearization point. It must fall between sending the request and receiving the response. Network delays can hide that instant, but cannot erase the order between non-overlapping operations.

Eventual agreement is a weaker promise

Eventual consistency says that if writes stop and network faults are eventually repaired, replicas eventually agree. It gives no convergence deadline and does not, by itself, prevent stale reads before then.

That can be acceptable for some features. But when a later decision depends on a completed change, the application needs a stronger guarantee or an explicit way to coordinate that decision.

Why quorums are not enough

With n replicas, a system might wait for w write acknowledgements and read from r replicas. The condition w + r > n makes those sets overlap. It does not automatically make the system linearizable.

Consider three copies, initially holding 0. A writer is changing the value to 1, needs all three acknowledgements, and has reached only the third copy so far:

Alice reads Copies 2 and 3 and returns the newer value, 1. After she finishes, Bob reads Copies 1 and 2 and returns 0. Both reads overlap the unfinished write. The quorum equation holds, yet Bob has gone backwards.

The book describes additional coordination for linearizable quorum reads and writes: readers repair stale copies and wait for that repair before returning; writers first read the latest state from a quorum. These steps cost time. Clock-based last-write-wins rules can still break ordering when machine clocks disagree. A linearizable compare-and-set operation requires consensus.

A single leader can help, but reads must reach the current leader or appropriately synchronized followers. An old leader, lost acknowledged writes during failover, or reads from an older snapshot can break the promise. Consensus protocols add rules that can make linearizable storage safe. Independently accepting writes at multiple leaders and reconciling them later generally does not provide it.

Fresh reads do not make a transaction

Linearizability and serializability solve different problems:

Suppose two doctors are on call and at least one must stay. Each checks that the other is still on duty, then changes their own record to off duty. Both checks can happen before either change. Every individual operation could be linearizable, yet nobody remains on call.

This is write skew. A guarantee about individual operations does not protect the rule across both records. The application needs suitable transaction isolation or coordination for the whole decision.

Where the guarantee matters

A unique username needs one winner when two people claim it together. Checking availability and saving later leaves a race. An atomic claim combines the check and assignment into one operation.

Leader election has a similar requirement: all machines must agree who owns the leadership lock. The wider locking design still needs to prevent an old owner from making unsafe writes after losing that lock.

Another failure appears when a photo upload starts a background resizing job. The server waits for the image save to succeed before sending the job. Even so, the queue can outrun storage replication:

flowchart TD
    W[Web server] -->|1. Save photo and await success| A[Storage copy A: new photo]
    A -. Replication delayed .-> B[Storage copy B: old photo]
    W -->|2. Send resize job| Q[Queue]
    Q --> R[Resizer]
    B -->|3. Old photo returned| R
    R --> T[Wrong thumbnail]

The worker can resize an old image or find no image at all. A wrong thumbnail may remain wrong even after the full-size photo finishes replicating. Linearizable storage prevents this stale-read race because the worker's read starts after the save completes.

Other solutions can track which image version the job requires and make the worker wait until storage can provide it. That needs reliable version information and more application coordination.

The cost: waiting or accepting disagreement

If two datacenters are running but cannot communicate, they cannot keep every side serving requests while also preserving linearizability.

flowchart TD
    P[Running replicas cannot communicate] --> C[Preserve linearizability]
    P --> A[Keep every side serving requests]
    C --> W[Some operations must wait or fail]
    A --> D[Replicas may disagree]

This is the tradeoff behind CAP. Its consistency requirement is linearizability. Its availability requirement is that every request to a nonfailed node eventually receives a successful response. That differs from an ordinary uptime percentage.

"Pick two of three" is a poor explanation: network failures are not an optional feature. With a working network, both guarantees can be possible. During a partition, the system cannot guarantee both everywhere. Clients who can still reach a working leader may continue normally while clients isolated with followers cannot make linearizable reads or writes.

There is a speed cost even without failures. Keeping replicas coordinated means communication and waiting. Weaker guarantees can reduce that work, but the application must still preserve its own rules.

The useful design question is concrete: can this decision safely use an older value? If it cannot, decide where the required coordination will happen, in the database or in the application, and what the user should experience when that coordination is unavailable.

Reading notes on Martin Kleppmann's Designing Data-Intensive Applications