Designing a Spanner-Style Global Database: TrueTime and External Consistency

Distributed systems folklore says you cannot trust clocks, so you cannot order events across machines without communication. Spanner's heresy was to trust clocks a bounded amount: if every node knows its clock is wrong by at most ε, you can turn wall time back into a global ordering primitive — by deliberately waiting out the uncertainty. That one idea, TrueTime, is why Spanner can promise something almost no other planet-scale database does: external consistency.

What external consistency buys you

External consistency (strict serializability): if transaction T1 commits before T2 starts — in real time, as observed by the outside world — then T2 sees T1's effects, and every consistent read agrees. Eventual consistency cannot promise this; even many "strongly consistent" systems only promise it per key or per shard. For cross-shard invariants — move money between accounts on different continents, then audit the total — you need it globally.

The building blocks

Data layout: keyspace split into tablets; each tablet replicated across zones/regions by its own Paxos group (typically 5 replicas). Writes go through the group's leader; the leader holds a lease. This is the standard replicated-state-machine layer — Raft would do the same job.

Single-group transactions commit in one Paxos round. The interesting machinery is for transactions spanning groups:

Cross-group transactions: two-phase commit, but with every 2PC participant and the coordinator being a Paxos group, not a single node. Classic 2PC's fatal flaw — coordinator dies and locks hang forever — disappears because the coordinator is itself replicated and cannot "die" short of losing a quorum. 2PC's blocking problem was never about the protocol; it was about non-replicated participants. Say that sentence in an interview and you have earned the follow-up.

Concurrency control: two-phase locking for read-write transactions; lock-free snapshot reads for read-only transactions at a chosen timestamp.

TrueTime: clocks with error bars

Google equips datacenters with GPS receivers and atomic clocks. The TrueTime API never returns a timestamp — it returns an interval:

TT.now() -> [earliest, latest]   // guaranteed: true time is inside
ε = (latest - earliest) / 2      // typically 1-7ms

The commit protocol uses it in two places:

1. Timestamping: the coordinator assigns commit timestamp s = TT.now().latest.
2. Commit-wait: the leader holds the commit (locks held, result unreleased) until TT.now().earliest > s — i.e., until every clock in the fleet agrees that s is in the past.

def commit(txn):
    s = TT.now().latest          # assign timestamp
    paxos_replicate(txn, s)      # happens concurrently with the wait
    while TT.now().earliest <= s:
        sleep_briefly()          # commit-wait: ~2ε, overlapped with replication
    release_locks_and_ack(txn)

Why this yields external consistency: if T2 starts after T1 committed (real time), then T1's commit-wait guarantees T1's timestamp is already "in the past" everywhere — so T2's timestamp is strictly greater. Timestamp order now matches real-time order, globally, with no cross-shard coordination at read time. The cost is explicit: every read-write transaction pays ~2ε of latency. Keep ε small and the tax is a few milliseconds — which is why the atomic clocks matter; they are not decoration, they are the latency budget.

Snapshot reads are the payoff: a read-only transaction picks timestamp t, reads from the nearest replica that is caught up past t (each replica tracks a "safe time"), touches no locks, blocks no writers, and is still strictly serializable. Analytics against the live OLTP database without a replica lag apology.

Without atomic clocks: the alternatives

Interviewers will ask "and if I don't have GPS clocks?" The landscape:

System	Ordering trick	Trade-off
Spanner	TrueTime + commit-wait	Hardware; ~2ε write latency
CockroachDB	Hybrid logical clocks + NTP bound	Reads may hit "uncertainty restarts" instead of waiting
Calvin/FaunaDB	Pre-order all txns via a global log	Deterministic, but interactive txns are awkward
DynamoDB/Cassandra	Don't promise it	Per-item or eventual consistency only

CockroachDB is the instructive contrast: same architecture (ranges + Raft + 2PC), no clock hardware, so it moves the uncertainty cost from writers (commit-wait) to readers (retry when a value's timestamp falls inside your uncertainty window). Same physics, different victim.

Design summary

Shard into tablets → replicate each via Paxos → 2PC across replicated groups for cross-shard writes → timestamps from TrueTime → commit-wait to make timestamp order equal real-time order → snapshot reads at a timestamp for lock-free consistent reads. The deep insight to land: Spanner did not beat CAP — during a partition, the minority side is unavailable. It made C so cheap to consume (wait a few milliseconds, bounded by clock hardware) that choosing it became rational at global scale.