Consistency Trade offs · Linearizability

Key Question

What’s the difference between linearizability (single-object) and serializability (multi-object transactions)?

Deep Dive

Linearizability and serializability are two of the most commonly confused consistency models. They sound similar, and they both involve “total orders,” but they solve different problems and guarantee different things.

Linearizability is about single-object operations with real-time ordering. It answers the question: “Did this write happen before that read?” It operates on individual read/write operations on a single register.

Serializability is about multi-operation transactions. It answers the question: “Did the database execute these transactions as if they were run one at a time?” It operates on entire transactions (which may contain multiple reads and writes to multiple objects).

The critical difference:

Property	Linearizability	Serializability
Unit of concern	Single operation	Multi-op transaction
Real-time guarantee	Yes	No
Compositional	Yes	No
Objects	Single object	Multiple objects

An Example

Consider two transactions T1 and T2:

T1: read X, write X+1, read Y, write Y+1
T2: read X, read Y

Under serializability, possible outcomes include:

T1 then T2: T2 sees (X+1, Y+1)
T2 then T1: T2 sees (X, Y)

Both are serializable. Now add timing:

Time: 10:00 ────────────────────────────── 10:05
T1:    [read X] [write X+1] [read Y] [write Y+1]
                          T2: [read X] [read Y]

T1 finishes at 10:03. T2 starts at 10:04 and finishes at 10:05. Under serializability, T2 could still see the PRE-T1 values of X and Y! Serializability only requires a total order — it doesn’t require that order to match real time. The “serial” order could be: T2 BEFORE T1, even though T2 started after T1 finished.

This would be: T2 sees (X, Y), then T1 runs — which is serializable but violates real time.

Strict Serializability = Serializability + Linearizability. This requires both: (1) transactions appear to execute in some serial order, AND (2) that order respects real time. If T1 commits before T2 starts, then T2 must see T1’s effects.

Time: 10:00 ────────────────────────────── 10:05
T1:    [───────commit────────]
                              T2: [─────start─────]
Under strict serializability: T2 MUST see T1's effects.
Under serializability: T2 MAY see T1's effects (but doesn't have to).

Google’s Spanner implements strict serializability using TrueTime (GPS + atomic clocks). When a transaction commits, Spanner assigns a timestamp from TrueTime, and later transactions are guaranteed to see it. This is equivalent to having a global wall clock.

Why This Confusion Matters

Most databases advertise “serializable isolation” — PostgreSQL, MySQL (with certain configurations), and many others. They guarantee serializability for their transactions, but they do NOT guarantee linearizability. A read of object X immediately after a write from another transaction might return the old value if the serial order places the read before the write.

If you need linearizable single-object operations (like a distributed lock or a compare-and-swap), you cannot rely on serializable transactions alone — you need a linearizable register underneath.

Check Your Understanding

A transaction T1 writes X=5 and commits at 10:00. Transaction T2 reads X at 10:01. Under serializability, what values can T2 see?
What does strict serializability add beyond regular serializability?
Is Spanner linearizable, serializable, or strictly serializable? How does TrueTime enable this?
Can a database provide linearizability without serializability? Provide an example.

The “So What?”

Knowing the difference is critical for system design. When a product claims “serializable,” check if they mean strict serializability or just serializability. Most databases mean the latter. If you’re building a payment system, you likely need strict serializability. If you’re building a social media feed, plain serializability (or even weaker models) is fine. The distinction determines whether you can trust the ordering of transactions relative to real-world time.

✏️ Exercises

Linearizability — Exercises

Exercise 1

A distributed system processes a write of X=7 at 10:00:00. The write completes (client receives ack) at 10:00:01. A read of X starts at 10:00:02 and returns X=0. Is this system linearizable? Explain why or why not.

Exercise 2

Register X and register Y are each individually linearizable. Client A transfers $50 from X to Y by doing: read X, write X−50, read Y, write Y+50. Client B reads X and Y concurrently. Is it guaranteed that Client B never sees a state where the money has vanished (e.g., X+Y decreased)? If not, describe a scenario where this could happen.

Exercise 3

A system provides non-linearizable behavior to the general case. However, all operations from a single client appear linearizable to that client. Is this possible? Explain how the system might achieve this (or why it’s impossible).

Exercise 4

Google Spanner provides strict serializability. Describe how TrueTime (GPS + atomic clocks) is used to:

Assign commit timestamps to transactions
Guarantee that a read that starts after a write commits will see the write’s effects
Handle clock uncertainty (the ε interval)

👁️ View Solutions

Linearizability — Solutions

Solution 1

No, this system is not linearizable.

The write completes (response received) at 10:00:01. The read starts (invokes) at 10:00:02 — a full second after the write completed. Since the read’s invocation is after the write’s response, real-time order requires the write to appear before the read. The write’s linearization point must be at or before 10:00:01, and the read’s linearization point must be at or after 10:00:02. Therefore, the read MUST see X=7 (or a newer value). Returning X=0 violates linearizability.

The only exception would be if the system had clock skew that placed the read “before” the write in real time, but the problem states the absolute times are accurate. The system is broken.

Solution 2

No, it’s not guaranteed. While each register (X and Y) is individually linearizable, the transfer operation involves four separate operations on two registers. There is no atomicity across the multi-step transfer.

Here’s the problematic scenario:

Client A: read X (gets 100), write X=50 (linearizes)
Client B: read X (gets 50), read Y (gets 0 — transfer hasn’t updated Y yet)
Client A: read Y (gets 0), write Y=50 (linearizes)

Client B sees X=50, Y=0 for a total of 50 — the money “disappeared” from B’s perspective. Both X and Y are individually linearizable, but the transfer as a whole is not atomic.

This is why real banking systems use transactions — they need serializability (or strict serializability) to make multi-step operations atomic. Or they use a single register approach (e.g., a ledger that tracks all accounts in one data structure).

Solution 3

Yes, this is possible — this is essentially what session guarantees (like read-your-writes) provide.

A system can be globally non-linearizable but present a linearizable view to each individual client. How?

Sticky sessions: Route a client to the same replica for all its operations. That replica maintains a consistent ordering, and the client never interacts with other replicas to observe inconsistency.
Client-side versioning: The client includes its last-seen timestamp/version with every request. The server ensures the response is at least as recent as that version.
Session tokens: The server issues a session token after each write. The client presents this token with reads, and the server uses it to route or coordinate the read to a replica that has seen the write.

This is how systems like Amazon DynamoDB (with consistent reads) and Apache Cassandra (with read-your-writes consistency) work. The system as a whole may not be linearizable for all clients, but each individual client experiences a linearizable view of their own data.

Solution 4

Spanner uses TrueTime to provide strict serializability through the following mechanism:

Assigning commit timestamps:

When a transaction commits, Spanner assigns it a timestamp s that is guaranteed to be greater than the current TrueTime value.
TrueTime returns an interval [earliest, latest] rather than a single time point. The commit timestamp is set to latest (or later) of the leader’s TrueTime interval at commit time.
This ensures no future transaction can be assigned an earlier timestamp.

Guaranteeing reads see writes:

A read transaction is assigned a timestamp s_read.
The read waits until TT.now().earliest > s_read (the “commit wait”) before returning.
This ensures that all transactions with timestamps <= s_read are fully committed and visible.
Any write that committed before the read started will have a timestamp < s_read, and the read wait guarantees the write’s effects are visible.

Handling clock uncertainty (ε):

TrueTime returns [now - ε, now + ε] — the true time is somewhere in this interval.
Spanner never assumes a precise time; it always uses the worst-case bound.
ε is typically 1-7ms (GPS) or higher (non-GPS data centers).
The commit wait ensures the read’s earliest time exceeds the write’s latest time, closing the window of uncertainty.

This is how Spanner achieves external consistency (equivalent to strict serializability) across globally distributed data centers without a centralized clock.