Linearizability is the strongest consistency guarantee, meaning that any operation appears to have executed atomically at a single point in time.
Let’s see this in action. Imagine two clients, C1 and C2, interacting with a shared key-value store.
Client C1 writes key1 = "valueA" at time t1.
Client C2 reads key1 at time t2.
Client C1 writes key1 = "valueB" at time t3.
Client C2 reads key1 at time t4.
In a linearizable system, if t2 is before t3, C2 must read "valueA". If t2 is after t3, C2 must read "valueB". There’s no in-between state where C2 sees a partial write or a value that was never actually written. The system behaves as if there’s only one copy of the data and operations happen in a strict, global order.
The core problem linearizability solves is the ambiguity of concurrent operations in distributed systems. Without it, when multiple clients access shared data simultaneously, you can end up with unpredictable results. A read might return a stale value, a value from an operation that hasn’t technically "committed" yet, or even a value that was never valid. This makes it incredibly difficult to reason about application state. Linearizability eliminates this ambiguity by providing a single, global timeline for all operations.
Internally, achieving linearizability typically involves a consensus protocol (like Raft or Paxos) or a distributed transaction manager. For a write operation, the system must ensure that the write is agreed upon by a majority of replicas before acknowledging it to the client. For a read operation, it’s trickier: a read must either be aware of the latest committed write or, in some protocols, it might involve a brief write-like quorum to ensure it sees the most up-to-date state. This often means reads can be as expensive as writes, or even more so.
The key levers you control are often related to the underlying consensus protocol or the transaction management system. In systems like FoundationDB, you might configure the number of acknowledged replicas for writes, or the read consistency level. In databases using Raft, you might tune the election timeouts or the frequency of heartbeats, though these are more about the availability of the consensus group than directly about linearizability itself. The critical insight is that every read must, in some way, participate in the decision of what the "current" state is, which inherently involves communication and agreement among nodes.
The cost of linearizability is primarily performance. To guarantee that operations appear to happen at a single point in time, every operation, especially reads, must often coordinate with multiple nodes. A read might need to consult a quorum of nodes to ensure it’s seeing the latest committed value, or it might even need to perform a lightweight write to acquire a timestamp or lock. This coordination introduces latency and reduces throughput compared to weaker consistency models like eventual consistency, where reads might return stale data for a period.
A common misconception is that linearizability is simply about having all replicas eventually agree. While agreement is necessary, linearizability is stricter; it demands that the order of operations is globally consistent and that each operation appears to complete instantaneously between its invocation and its response. This means a read that finishes after a write has completed must see the effect of that write, even if the read request was sent before the write request.
The next hurdle after achieving linearizability is often dealing with the trade-offs in availability, particularly during network partitions or node failures.