Case Study — Google Spanner

The problem Spanner was built for

Google arrived at Spanner holding both halves of the answer and neither of them together. Bigtable scaled enormously, but the OSDI 2012 paper says plainly that teams complained it was hard to use for applications with complex, evolving schemas, or wanting strong consistency under wide-area replication. Megastore offered a semi-relational model and synchronous replication, and teams picked it despite write throughput the paper itself calls relatively poor.

So the menu was: scale without transactions, or transactions without scale. Whichever you chose, the missing half got rebuilt inside the application — hand-rolled ordering, reconciliation, retry logic, and bugs, once per team, forever.

Spanner's bet was that this diffuse tax exceeded the cost of centralising it, even when centralising it meant GPS antennas and atomic clocks in every datacentre. The framing to carry into an interview is not is Spanner clever, but whose complexity budget is this coming out of.

TrueTime: an interval, not an instant

TT.now() does not return a timestamp. It returns a TTinterval — [earliest, latest] — guaranteed to contain the true absolute time at the moment of the call. Two helpers sit on top: TT.after(t) and TT.before(t), meaning t is definitely past and t is definitely future.

The interval's half-width is epsilon. Spanner keeps it small with time-master machines in every datacentre: most with GPS receivers, a minority with atomic clocks, deliberately chosen because atomic clocks fail in ways uncorrelated with GPS — antenna faults, radio interference, leap-second handling, spoofing, system outages. A daemon on every machine polls several masters, uses a variant of Marzullo's algorithm to reject liars, and machines whose frequency excursions exceed a worst-case bound are evicted from the fleet. The 2012 paper reports epsilon as a sawtooth of roughly 1 to 7 ms across each 30-second poll interval, derived from a conservatively applied drift rate of 200 microseconds per second plus network delay to the masters. Single-digit milliseconds, in other words.

Clocks & Ordering covers why wall-clock time is untrustworthy across machines. What TrueTime adds is not accuracy:

Commit-wait: converting uncertainty into latency

Read-write transactions use two-phase locking, so a timestamp can be assigned any time after all locks are held and before any are released. Two rules do all the work:

Start. The coordinator leader picks a commit timestamp s no smaller than TT.now().latest, evaluated when the commit request arrived.

Commit wait. No client may see the transaction's data until TT.after(s) is true — until s is certainly in the past according to every clock in the fleet.

Together these give external consistency in three lines: commit-wait puts s1 before T1's real commit instant, causality puts T1's commit before T2's start, and the start rule puts T2's start before s2. So s1 < s2 whenever T1 finished before T2 began. Timestamps stop being decoration and become the global serialisation order. That is strict serializability — serializable plus real-time order, the top of the ladder in the consistency spectrum.

The expected wait is about 2 × epsilon. The paper measures commit wait at roughly 5 ms in a single-replica microbenchmark where Paxos latency was about 9 ms, and notes it is typically overlapped with Paxos communication — you were already waiting on replicas, so the marginal cost is smaller than it looks.

The architecture underneath

Data is sharded into ranges; each range is replicated by a Paxos group; every group has a leader. That is consensus applied per shard, which is the only reason the write path scales — a thousand groups run a thousand independent Paxos instances.

Transactions touching more than one group need atomicity across them, so Spanner runs two-phase commit over the groups, with the client driving it to avoid shipping data twice over wide-area links. 2PC has been called the anti-availability protocol precisely because every member must be up for it to work — the classic objection from transactions.

The residual exposure is narrower but real: a transaction commits only if every touched group has a quorum-elected leader on the same side of a partition. Some transactions time out. None return a wrong answer.

Read-only transactions: the underappreciated payoff

Because timestamps are globally meaningful, a read-only transaction is two steps: pick a timestamp sread, then execute snapshot reads at it. No locks are taken, so incoming writes are never blocked, and the reads can run on any replica that is sufficiently up to date — each replica tracks a safe time and can answer any read at or below it.

For a read whose scope lives in one group, Spanner does better than TT.now().latest: with no prepared transactions outstanding it can use the timestamp of that group's last committed write, which is already safe everywhere.

This is why the economics work. Writes pay cross-region round trips plus commit-wait; reads pay neither, scale with replica count, and can be served from the nearest region. Most workloads are read-dominated, so the expensive half is the small half. Consistent backups, repeatable MapReduce runs, and atomic schema changes at a future timestamp all fall out of the same property for free.

The bill, stated honestly

• Write latency has a floor you cannot optimise away: cross-region consensus round trips plus commit-wait. Distance is priced at the speed of light and epsilon is priced in milliseconds. Placing replicas closer together reduces the former and buys less multi-region failure independence.
• Hardware almost nobody can deploy. GPS receivers and atomic clocks in every datacentre, plus the fleet monitoring that evicts drifting machines, is not a thing you retrofit.
• PC/EC in both branches. Consistency during partitions, consistency over latency otherwise.
• The availability numbers are Google's network, not Spanner's algorithm. Brewer's paper argues Spanner is effectively CA because it delivers better than five nines in practice — but that rests on controlling the whole wide-area network, which is rare, and even then outages happen and Spanner chooses consistency.

The 2017 follow-up is the sequel worth knowing exists: once the hard guarantee was solid, the work moved to making it a real SQL system — a shared SQL dialect, distributed query execution that hides transient failures via query restarts so clients need no retry loops, and a blockwise-columnar storage format (Ressi) for hybrid workloads.

What generalises

You will not build TrueTime. Two ideas transfer anyway.

Bounding an uncertainty is often worth more than reducing it. A system that is accurate to within an unknown amount gives you nothing to build on. A system that is accurate to within a known amount gives you an algorithm. This applies to clock skew, replication lag, queue depth, and cache staleness alike: publish the bound, then design against it.

Trade latency for a guarantee deliberately, not accidentally. Every strong-ordering system waits somewhere. Spanner's distinction is that the wait is explicit, measured, and on the commit path where you can see it — instead of hidden in a retry loop, a conflict resolver, or a support ticket six months later.

What to take away

• Spanner exists because teams were paying for the gap between scalable and consistent, one at a time.
• TrueTime returns an interval, not an instant; the bound is the product, not the accuracy.
• Commit-wait converts clock uncertainty into latency, yielding non-overlapping timestamps globally.
• It is PC/EC — the CAP and PACELC costs are paid on every commit, not avoided.
• 2PC over Paxos groups is far safer than 2PC over single nodes; each member is itself highly available.
• Timestamps that mean something globally make lock-free reads from any fresh replica possible.