Linearizability

Linearizability guarantees two things: (1) every read returns the most recent write, and (2) every operation appears to take effect at a single instant between its invocation and completion.

This is what clients intuitively expect from a correct system. When you write a value and read it, you see what you wrote. When two people check a seat reservation simultaneously, at most one succeeds.

The cost is coordination. Every write needs majority acknowledgment. Every read must check the latest committed value. Across data centers with 100ms round-trip, that is 100-200ms per operation. Google Spanner achieves global linearizability using TrueTime atomic clocks, custom hardware in every data center.

Understanding when you actually need linearizability versus when a weaker model suffices is one of the most impactful architectural decisions in distributed systems.

Read, must return the value of the most recently completed write. Not the value on the local replica. Not a cached value. The latest globally committed value.

Write, must be visible to all subsequent reads by any client on any node. Once the write returns success, it is durably committed and visible.

Compare-and-swap (CAS), atomically check a value and modify it if it matches. Essential for distributed locks and leader election.

etcd provides linearizable reads and writes. By default, reads go through the Raft leader to ensure freshness. You can opt for serializable reads (from any node, might be stale) for lower latency.

Google Spanner provides global linearizability using TrueTime. Each operation is assigned a timestamp with bounded uncertainty. The system waits for uncertainty to resolve before committing, ensuring correct global ordering.