Linearizability vs Serializability: Recency vs Isolation

In distributed systems and database engineering, Linearizability and Serializability are the two most frequently conflated consistency guarantees.

Although they sound similar, they solve two fundamentally orthogonal problems:

---

1. Deep Dive: What is Linearizability?

Linearizability (also known as Atomic Consistency, Strong Consistency, or Immediate Consistency) is a recency guarantee applied to individual objects (single keys or registers).

The Linearizability Invariant:

1. Every read and write operation takes effect atomically at a specific instantaneous point in time between its invocation and its completion.
2. If Operation B starts after Operation A has finished in global physical time, Operation B must observe the state produced by Operation A (or a newer state).

Why Linearizability Matters:

• Distributed Locks & Leader Leases: If node election is not linearizable, two nodes can both read lock_owner == null at real-time $t_{25}$ and both claim leadership (causing split-brain).
• Uniqueness Constraints: If username registration is not linearizable, two users can simultaneously claim @alex in two different datacenters.

---

2. Deep Dive: What is Serializability?

Serializability is the "I" (Isolation) in ACID database transactions. It applies to multi-operation, multi-row transactions.

The Serializability Invariant:

A database provides serializability if the execution of concurrent transactions produces the exact same final database state as if the transactions were executed serially (one-by-one, in some sequential order) without any interleaving.

The Crucial Catch: Serializability Ignores Real-Time!

Serializability guarantees that an execution order exists, but it does not guarantee which order, nor does it enforce real-time recency.

A serializable database is mathematically allowed to execute your transaction against a snapshot of data from 10 minutes ago, as long as the transactions are internally consistent with each other!

---

3. The Comparison Matrix

---

4. The Ultimate Gold Standard: Strict Serializability

When an enterprise database combines both properties, it achieves Strict Serializability (also called External Consistency or Strong Serializable Snapshot Isolation).

$\text{Strict Serializability}=\text{Linearizability}+\text{Serializability}$

What Strict Serializability Guarantees:

1. Transactions execute as if in a serial one-by-one order (Zero race conditions, zero write skew).
2. If Transaction $T_2$ starts after Transaction $T_1$ commits in physical real time, $T_2$ is guaranteed to be ordered after $T_1$ in the serial order (Zero stale reads).

How Production Engines Implement It:

• Google Cloud Spanner: Uses the TrueTime API (atomic clocks and GPS receivers in every datacenter) to bound clock uncertainty ($ϵ\le 7\text{ms}$), ensuring physical time serialization.
• CockroachDB: Uses Hybrid Logical Clocks (HLC) combined with multi-raft consensus groups.

---

5. Code Deep-Dive: A Linearizability Trace Checker

---

6. Production Failure Postmortem: The Cryptocurrency Double-Withdrawal Race

Incident Overview:

In 2021, a European cryptocurrency exchange suffered a $1.2M loss due to concurrent withdrawal requests exploiting a serializable database running without linearizability.

What Happened:

1. The exchange used PostgreSQL with SERIALIZABLE isolation level across a primary master and two read replicas.
2. A malicious user with a balance of $10,000$ initiated two automated withdrawal requests simultaneously from two different IP addresses.
3. The first withdrawal hit the primary node, decremented the balance to $0$, and sent funds to the blockchain.
4. The second withdrawal hit an asynchronous read replica that was experiencing $250\text{ms}$ replication lag.
5. Because the read replica had not yet applied the first transaction's WAL segment, its serializable snapshot read the old balance ($10,000$) and approved the second withdrawal.
6. Both transactions were internally serializable on their respective nodes, but the lack of Linearizability across replicas allowed the double-spend.

Remediation:

• Enforced Linearizable Reads on all financial transactions: Mutating balance transactions must read exclusively from the leader or use SELECT ... FOR UPDATE with synchronous replication.

---

7. Chapter Summary & Invariant Cheat Sheet