Skip to content

CONCEPT Cited by 1 source

Linearizability

Linearizability is the strongest possible consistency level for a distributed data system. Operations are ordered exactly as they occurred in real time — all reads after a write will see that write, regardless of which replica served the request.

Definition

A system is linearizable if every operation appears to take effect instantaneously at some point between its invocation and response, and the resulting order is consistent with real-time ordering.

In practical terms: if client A writes x = 7 and then client B (who knows A's write completed) reads x, B is guaranteed to see 7 — even if A and B contacted different replicas distributed across the world.

Why it matters

Linearizability relieves programmers from thinking about all the weird behaviors a distributed data system might exhibit. They can reason about the system like they reason about local memory on a single-threaded machine. For weaker consistency levels, writes can be reordered, reads can return stale values, or operations can appear to happen in different orders to different observers.

Cost

Linearizability requires coordination between replicas — typically via a consensus algorithm. This means:

  • Latency proportional to the network distance between a majority of replicas
  • Unavailability if a majority cannot communicate (CAP theorem's consistency vs. availability trade-off)

Cloudflare Meerkat instance

Meerkat guarantees linearizability by routing both reads and writes through its replicated log. A read must go through consensus to ensure it observes all prior writes — a replica that believes a slot is empty is forced to discover prior decisions before its read can proceed.

Seen in

Last updated · 573 distilled / 1,747 read