How Google Spanner Achieves Global Consistency

🧠 Achieving Global Consistency in Distributed Databases using Paxos and TrueTime

Getting a transaction onto enough machines is a solved problem. Getting the whole planet to agree on what order transactions happened in is the hard part, and it is the part Google Spanner actually solves.

Spanner splits that work between two mechanisms that are easy to confuse:

• Paxos replicates the write so it survives machines dying. It answers "is this data safe?"
• TrueTime stamps the write with an order that matches real wall-clock time. It answers "when did this happen, relative to everything else on earth?"

Keep those two jobs separate and Spanner stops being mysterious. Blur them together and nothing about it makes sense.

📌 The write path, start to finish

🔹 Step 1: The leader is already there

There is no proposal round, no vote for who is in charge, no three-phase handshake. Each split runs its own Paxos group, and that group's leader holds leadership on a long-lived lease. It was elected long before your write showed up.

This matters because the textbook description of Paxos (propose, promise, accept, learn) describes how a leader gets established. In steady state Spanner skips straight past it. A normal write is one round to a quorum, not three phases.

🔹 Step 2: Lock, then timestamp

The leader takes write locks on the rows you are touching, then picks the commit timestamp:

s = TrueTime.now().latest

TrueTime does not return a number. It returns an interval, something like [100ms, 105ms], and it promises the true time is somewhere inside it.

The width of that interval is the uncertainty, called ε. Spanner takes the latest edge of it, because picking the most pessimistic value is what makes the next step safe.

Note the ordering here: the timestamp is minted at the leader, before replication. It is not something the replicas negotiate or vote on.

🔹 Step 3: Paxos replicates to a quorum

The leader ships the commit record to the other replicas and waits for a majority to acknowledge. Replicas do not audit the timestamp, do not check it against their own clocks, and do not reject it for being too old. They accept based on the leader's Paxos term, and nothing else.

Once a majority has acknowledged, the write is durable. It will survive any minority of the replicas catching fire.

🔹 Step 4: Commit wait, and why it is nearly free

Durable is not the same as correctly ordered. The leader now waits until TrueTime is certain that s has passed:

wait until  TrueTime.now().earliest > s
duration    ≈ 2 × ε

Two things about this wait are usually taught wrong.

• Only the leader waits. Not the replicas. There is no all-replicas barrier that the transaction has to clear before it exists.
• It is mostly free. The leader was already blocked waiting on the Paxos quorum, and the two waits run at the same time. Google's own description is that commit wait "typically overlaps with the replica communication, so its actual latency cost is minimal." You are usually paying for the network anyway.

What the wait actually delays is the acknowledgement to the client and the release of the locks. That is worth saying plainly.

Spanner does not make the write slow. It makes telling you about the write slow, by exactly long enough that the timestamp cannot be a lie.

🔹 Step 5: Acknowledge and apply

Once the quorum is in and the wait is over, the leader releases its locks and tells the client the transaction committed. The mutations get applied in parallel with that reply, and replicas apply them as they learn about them.

🌍 So what makes it globally visible?

Here is the payoff, and it is smaller than people expect.

Because the leader refused to acknowledge the commit until real time had definitely passed s, any transaction that starts after yours finished is guaranteed to pick a timestamp higher than s. Its TrueTime.now().latest cannot be lower, because your commit wait already burned through that uncertainty.

That single property is what Spanner calls external consistency:

If T1 commits before T2 begins, anywhere on earth, in real time, then T1's timestamp is lower than T2's.

No global coordinator makes that true. No replica votes on it. It falls out of one node pausing for a few milliseconds.

🔍 Where MVCC comes in

Timestamps only buy you ordering. MVCC is what turns ordering into something you can read.

Spanner keeps multiple timestamped versions of every row, so a read at timestamp t just means "show me the versions as of t". That has two consequences worth knowing:

• Reads take no locks. A read-only transaction never blocks a writer and never gets blocked by one.
• Any caught-up replica can serve it. A replica that has applied everything up to t can answer a read at t on its own, with no leader involvement at all.

That last point is why Spanner scales reads globally, and it is why the strong-read-must-hit-the-leader folklore is wrong. A strong read can be served by any read-write or read-only replica.

If that replica is not the leader, it may check in with the leader to agree on a read timestamp, but the rows come from the local replica. Only the timestamp negotiation crosses the network, and read leases can remove even that.

🧩 The whole thing in one line

Paxos makes the write survive. TrueTime makes it ordered.

Commit wait makes the order honest, by delaying only the acknowledgement. MVCC makes that order readable from anywhere.

When to Choose Spanner