1What distinguishes linearizability from sequential consistency?
Vetora📏Consistency & Transactions
Linearizability
Linearizability is the strongest single-object consistency model, requiring that every operation appears to take effect instantaneously at some point between its invocation and response. It makes a distributed system behave as if there is a single copy of the data, even though it is replicated across multiple nodes.
Overview
Linearizability, formalized by Maurice Herlihy and Jeannette Wing in 1990, is the gold standard of consistency for distributed systems. Informally, a system is linearizable if every operation appears to execute atomically at some instant between its start and finish. If client A completes a write before client B starts a read, B must see A's write (or a later one). There is no stale-data window: the moment a write is acknowledged, it is visible to the entire world.
Linearizability is a single-object guarantee -- it applies to individual registers, keys, or objects independently. It does not inherently address multi-object transactions (that is the domain of serializability). However, when combined with serializability, you get strict serializability -- the strongest possible guarantee for transactional systems, where transactions appear to execute in a serial order that is consistent with real-time ordering.
Achieving linearizability in a distributed system requires coordination. In a single-leader system, all reads and writes go through the leader; the leader serializes operations and responds only after the write is durably committed. In a quorum-based system, linearizable reads require either reading from a quorum with conflict resolution (e.g., read-repair in Cassandra with ALL consistency) or using a read protocol that confirms the leader has not changed (e.g., Raft's ReadIndex). In a multi-datacenter setup, linearizability requires cross-datacenter coordination on every write, adding 50-200ms latency.
The cost of linearizability is performance. Every read must either go through the leader or verify that its data is current -- there are no 'free' reads from local replicas. The CAP theorem proves that during a network partition, a system cannot be both linearizable and available. The PACELC theorem adds that even without partitions, linearizability trades off against latency. Google Spanner achieves linearizability globally using TrueTime (GPS + atomic clocks), but even Spanner pays 7-10ms per write for cross-zone Paxos consensus.
Key Points
- 1Linearizability means every operation appears to take effect at a single instant between invocation and response. If write W completes before read R begins, R must see W or a later write. There is no stale-read window.
- 2It is a recency guarantee: reads always return the most recently completed write. This is strictly stronger than sequential consistency (which preserves per-process ordering but allows stale reads) and causal consistency (which preserves causal ordering but allows concurrent reads to differ).
- 3Linearizability is the 'C' in the CAP theorem. During a network partition, a linearizable system must reject operations it cannot guarantee are current, sacrificing availability.
- 4Single-leader replication can provide linearizability if all reads go through the leader (or use a sync-read protocol like Raft's ReadIndex). But if the leader is partitioned, the system becomes unavailable for the duration.
- 5Quorum reads with read-repair (e.g., Cassandra with QUORUM read + QUORUM write) provide strong but not always linearizable consistency. True linearizability requires additional mechanisms like ABD protocol or wait-free reads.
- 6Strict serializability = serializability + linearizability. It means transactions execute in a serial order that respects real-time ordering. Spanner and CockroachDB provide this guarantee.
Simple Example
Alice and Bob Check a Shared Counter
A counter starts at 0. Alice writes counter=1, and the write completes at time T1. Bob starts reading the counter at time T2 > T1. With linearizability, Bob MUST see counter=1 (or a later value). Without linearizability, Bob might see counter=0 because his read is served by a stale replica that has not yet received Alice's write. Linearizability eliminates this possibility -- once a write is acknowledged, it is visible to every subsequent read, regardless of which replica serves it.
Real-World Examples
Google Spanner
Spanner provides external consistency (equivalent to strict serializability) for globally distributed transactions. Using TrueTime (GPS + atomic clocks), Spanner assigns globally ordered timestamps to transactions and uses commit-wait to ensure that if transaction T1 commits before T2 starts, T1's timestamp is lower. This provides linearizability across data centers at the cost of 7-15ms commit latency for cross-region writes.
etcd
etcd provides linearizable reads when using the default 'consistent' read option. The Raft leader confirms it is still the leader (via ReadIndex or lease-based reads) before responding to a read request. This ensures the read reflects all committed writes. etcd also offers 'serializable' reads that can be served by followers without leader confirmation, trading linearizability for lower latency.
CockroachDB
CockroachDB provides serializable isolation with a real-time ordering guarantee (equivalent to strict serializability) for single-region deployments. It uses hybrid logical clocks (HLC) to order transactions, with the physical clock component providing approximate real-time ordering and the logical component ensuring causal ordering. Cross-region transactions may require clock uncertainty waits similar to Spanner's commit-wait.
Trade-Offs
| Aspect | Description |
|---|---|
| Consistency vs Latency | Linearizable reads require confirmation from the leader or a quorum, adding at least one network round trip to every read. In a cross-datacenter deployment, this adds 50-200ms. Systems like DynamoDB offer eventually consistent reads at <5ms by reading from any local replica, vs. strongly consistent reads at higher latency from the leader. |
| Consistency vs Availability (CAP) | During a network partition, a linearizable system must refuse requests to nodes on the minority side of the partition, because those nodes cannot confirm their data is current. An AP system continues serving all requests but may return stale data. For systems that prioritize uptime (e.g., shopping carts), linearizability is typically too expensive. |
| Throughput Impact | All reads going through the leader creates a throughput bottleneck. The leader's network bandwidth and CPU limit the cluster's read capacity. Systems mitigate this with read replicas for non-linearizable reads, or with lease-based reads where followers serve reads during a valid leader lease (sacrificing linearizability if the lease assumption fails). |
| Implementation Complexity | Correctly implementing linearizability requires careful handling of leader failures, clock synchronization, and read protocols. Subtle bugs (serving reads from a deposed leader, not validating leader status) can violate linearizability intermittently -- making the system appear correct under normal conditions but fail under partitions or leader changes. |
Case Study
Herlihy and Wing's Linearizability Model
Scenario
In the late 1980s, concurrent programming on multiprocessor systems needed a formal correctness criterion for shared objects. Existing notions (sequential consistency, serializability) did not capture the real-time ordering requirement: if operation A completes before operation B begins, A should appear to happen first. Without this guarantee, building correct concurrent algorithms from shared objects was unreliable.
Solution
Herlihy and Wing formalized linearizability in their 1990 paper. They defined it as a safety property: a history of concurrent operations is linearizable if it can be reordered into a sequential history that (1) respects the real-time ordering of non-overlapping operations, and (2) satisfies the sequential specification of each object. The key insight is the 'linearization point' -- each operation appears to take effect instantaneously at some point during its execution.
Outcome
Linearizability became the de facto correctness criterion for concurrent data structures and distributed systems. It enabled compositional reasoning: if two objects are individually linearizable, their composition is also linearizable. The formalization influenced the design of consensus protocols (Raft, Paxos), distributed databases (Spanner, CockroachDB), and coordination services (ZooKeeper, etcd). Jepsen tests for distributed databases fundamentally test for linearizability violations.
Common Mistakes
- ⚠Confusing linearizability with serializability. Linearizability is a single-object, real-time guarantee. Serializability is a multi-object, transaction-level guarantee. They are orthogonal: a system can be serializable but not linearizable (transactions execute in some serial order, but not necessarily real-time order), or linearizable but not serializable (single-key operations are real-time ordered, but multi-key transactions are not atomic).
- ⚠Assuming quorum reads are always linearizable. Reading from a majority and writing to a majority does not guarantee linearizability unless additional mechanisms (read-repair, ABD protocol) are used. It is possible for a quorum read to miss a recently committed write if the read quorum does not overlap with the nodes that have applied the write.
- ⚠Believing linearizability is free with single-leader replication. If reads are served by followers (as in many default configurations), they may be stale. Only reads through the leader (or via ReadIndex/lease) are linearizable.
- ⚠Ignoring that linearizability is impossible during partitions (CAP). If your system must remain available during network issues, you cannot maintain linearizability. Many teams discover this in production when a partition causes their 'consistent' system to reject all requests.
Related Concepts
See Linearizability in action
Explore system design templates that use linearizability and run traffic simulations to see how these concepts perform under real load.
Browse TemplatesTest linearizable reads under concurrent writes
Metrics to watch
stale_read_pctwrite_latency_msthroughput_rpsconsistency_violations
Test Your Understanding
2Why is linearizability impossible to maintain during a network partition (CAP)?