In plain terms, what does it mean for an operation on a single data item to be 'linearizable'?
answer
- single object, real-time order
- atomic point between invoke and return
- once acked, never stale after
- strongest single-copy illusion
- needs coordination via quorum or leader
basics
~10 sEvery read or write on that item behaves as if it happened instantly, at one moment, and once a write is confirmed, nobody sees an older value again.
solid answer
~40 sLinearizability is a consistency guarantee for operations on a single object: every operation appears to take effect atomically at some instant between its invocation and its response, and that instant must respect real (wall-clock) time -- if operation A finishes before operation B starts, A's effect must be visible to B. Equivalently, there is a total order of all operations on the object consistent with real-time order, and every read returns the value written by the most recent write in that order. It's the strongest single-object consistency model: once a write is acknowledged, no client can ever observe a value older than that write. This differs from weaker models like eventual or causal consistency, which allow temporary staleness or only order causally-related operations rather than all operations by wall-clock time.
go deeper
Should describe the intuitive 'one shared clock, instantly visible' idea and know it means no stale reads after a confirmed write. Doesn't need the formal invocation/response-interval definition.
Should state the formal idea: each operation takes effect atomically at some point in its call/return window, consistent with real-time order. Should connect it to guarantees like read-your-writes and monotonic reads being implied by it.
Should be able to reason about why it's expensive (coordination), name a mechanism that provides it (consensus, single leader, CAS), and give a concrete failure mode when it's faked or violated, such as stale replica reads or clock-based lock leases.
Should discuss where to spend this guarantee sparingly in a system design -- which subset of operations truly need it (locks, leader election, payment idempotency keys) versus where relaxing to eventual or causal consistency buys availability -- and how to verify it, e.g. with linearizability checkers like Jepsen/Knossos.
## What the guarantee says **Linearizability** is a correctness condition for a **single object** — a register, a key in a key-value store, a counter — shared by concurrent clients. Formally, every operation, a read or a write, carries two timestamps: - an **invocation time**, when the client issues it; - a **completion time**, when the client receives the response. Linearizability requires that there exists some instant between those two times, for every operation, at which the operation appears to take effect **atomically and instantaneously**. Crucially, the chosen instants across all operations must form a **total order** that is consistent with real (wall-clock) time: if operation A completes strictly before operation B is invoked, then A's effect point must come before B's in that order. The practical consequence is simple to state even though the definition is fussy: once a write returns success, every operation that starts afterward is guaranteed to see that write, or something even newer, but never something older. ## Why it exists This exists because distributed systems replicate data across multiple machines for **fault tolerance** and **throughput**, and replication naturally introduces the possibility that different replicas hold different, temporarily out-of-sync copies of the same value. Without a guarantee like linearizability, an application reading from one replica right after writing to another could see stale data, which breaks intuitive reasoning for anything that depends on a single, authoritative, up-to-date value: - a bank balance check before approving a withdrawal; - a lock's current holder; - a leader-election term number; - an idempotency key that must not be double-claimed. Linearizability gives programmers the illusion of a **single copy** of the data updated atomically, which is exactly the mental model most application code implicitly assumes. It is also the semantics required for a register to be safely used as the storage for higher-level coordination primitives, most notably **compare-and-set**, which is how distributed locks, leader election, and unique-claim operations are typically implemented on top of a linearizable store. ## The cost The cost is **coordination**, and coordination costs latency and availability. To guarantee that every client observes writes in the same real-time-consistent order, a system generally cannot let two replicas answer independently and disagree; it must funnel writes, and often reads, through a single point of authority, or run a consensus protocol such as `Raft` or `Paxos`, or a synchronous quorum handshake that requires a majority of nodes to agree before any operation is considered complete. That coordination shows up as: - **Latency.** That round-trip to a quorum, or to a single leader possibly located in a different datacenter, adds real latency to every operation compared to letting a nearby replica answer instantly. - **Availability.** Under a network partition, the **CAP theorem's** practical bite shows up here directly: a linearizable system must refuse to serve, or must delay, requests on the minority side of a partition, because answering from a replica that might be stale would break the guarantee, so linearizability and full availability during a partition are mutually exclusive. - **The dial.** Even without a partition, the **PACELC** extension applies: there is a latency-versus-consistency dial, and pushing toward strict linearizability pushes latency up. ## Failure modes Failure modes tend to appear at the seams where implementers try to fake linearizability cheaply. 1. **Synchronized wall clocks instead of proper coordination.** A common one is relying on them — for example, a lock service that grants a lease "valid until timestamp T" assuming all machines' clocks agree closely enough; clock skew or a paused virtual machine can let two clients believe they simultaneously hold the lock, silently violating the single-owner guarantee the system claimed to provide. 2. **Stale follower reads.** Another is serving reads from a follower replica for performance without a freshness check, such as a `Raft` read-index or a leader lease, which reintroduces stale reads exactly where the API contract promised none. 3. **The lack of a fencing token.** A third, subtler failure: even a correctly elected new lock holder can be undermined if the old, delayed holder's write finally lands after the new holder has already acted, unless every write carries a monotonically increasing token that downstream storage can reject if stale. ## Where it shows up A concrete real-world case: `etcd`, the coordination store behind Kubernetes, offers linearizable reads and writes by routing all operations through its `Raft` leader and a quorum commit. Kubernetes relies on that guarantee so that, for example, only one controller ever believes it holds a particular leader-election lock at a time — a correctness property the whole control plane depends on, paid for with the extra round-trip latency of `Raft` consensus on every write.
- Does linearizability say anything about the order of operations on two different objects?No -- linearizability is defined per object; it says nothing about cross-object ordering. That gap is exactly what serializability, and strict serializability, closes by ordering all operations across all objects as if from a single serial transaction schedule.
- Can a linearizable system still return stale data?Not for a completed operation acting alone -- once a write returns success, every subsequent read that starts after the write finished must reflect it. But a read that overlaps in time with a write is legal to return either the old or new value, since linearizability only fixes some point within each operation's own invocation-response interval.
- Is linearizability the same thing as what people casually call 'strong consistency'?Loosely yes, but 'strong consistency' is used inconsistently across the industry for anything from linearizability to plain synchronous replication. Linearizability is the precise, formally defined version, so in an interview it's worth naming the exact term when precision matters.
Think of a single analog wall clock everyone in a room can see: the instant someone moves the hands, anyone who glances at the clock afterward sees the new time -- never a moment frozen in the past, and never two different times shown to two different people at once.
saying these in an interview costs you the question
- Confuses linearizability with eventual consistency ('it converges eventually')
- Thinks linearizability only constrains reads, not writes
- Claims linearizability orders operations across different keys or objects
- Cannot explain why it costs latency
- Uses 'linearizable' and 'serializable' interchangeably without noting any difference