Spanner and TrueTime

Every time you transfer money, book a flight, or post something online, a database somewhere must decide: did this happen before or after that? On a single machine, the CPU clock settles the question in nanoseconds. Across thousands of servers spanning continents, the question becomes surprisingly hard — clocks drift, networks lag, and no global "now" exists.

For decades, engineers accepted a tradeoff: either sacrifice consistency (accept that different servers might disagree on the order of events) or sacrifice availability (force every write to wait for a slow network round-trip). Distributed systems literature called this the CAP theorem — pick any two of Consistency, Availability, and Partition tolerance.

In 2012, Google published a paper describing Spanner, a production database that had been running for years inside Google — serving Gmail, Google Ads, and other critical services — while providing something previously considered impractical: external consistency (also called linearizability) at planetary scale. The secret was TrueTime, a system that uses GPS receivers and atomic clocks at every data center to bound the uncertainty in wall-clock time to a tight interval, typically under 7 milliseconds.

Spanner does not cheat physics. Light still takes ~67 ms to cross the Atlantic. Instead, Spanner uses the known uncertainty in clocks to make transactions wait long enough that causality is never violated — a technique called commit-wait. The result: a globally replicated, strongly consistent, ACID-compliant database that proved the CAP tradeoff is not as rigid as once thought, as long as you are willing to pay in latency.

TrueTime does not return a single timestamp — it returns an interval [earliest, latest] bounding the true wall-clock time. Spanner assigns every transaction a commit timestamp inside that interval, then waits until the interval has safely passed before releasing the commit. This guarantees that any transaction starting after this one gets a strictly larger timestamp.

<p class="hint">{{hint}}</p>
<div class="timeline-wrap">
  <div class="axis-label">{{axis_label}}</div>
  <canvas id="canvas" width="560" height="180"></canvas>
</div>
<div class="controls">
  <label>{{epsilon_label}} <input id="epsilon" type="range" min="2" max="20" value="7">
    <span id="epsilonVal">7</span> ms</label>
  <div class="btns">
    <button id="btnA" type="button">{{btn_a}}</button>
    <button id="btnB" type="button">{{btn_b}}</button>
    <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
</div>
<div id="status" class="status"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.5; }
.timeline-wrap { background: #f4f6f8; border-radius: 10px; padding: .5rem .6rem .2rem; margin-bottom: .7rem; }
.axis-label { font-size: .75rem; color: #888; margin-bottom: .2rem; }
canvas { display: block; width: 100%; max-width: 560px; }
.controls { display: flex; flex-direction: column; gap: .5rem; margin-bottom: .5rem; }
label { font-size: .88rem; display: flex; align-items: center; gap: .4rem; }
input[type=range] { width: 120px; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.4em; line-height: 1.5; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }

// Code not found

Notice the key insight: the uncertainty interval (shown in orange) is the enemy. A small interval means a short wait; a large interval means a long wait. Google's TrueTime keeps uncertainty under ~7 ms globally by combining GPS (accurate to ~100 ns) with atomic clocks (which maintain accuracy when GPS is briefly unavailable). The commit-wait ensures that by the time the commit is visible, wall-clock time has already advanced past the commit timestamp — so any later transaction will receive a later timestamp, making the global order unambiguous.

External consistency means that if transaction T1 commits before transaction T2 begins (in wall-clock time), then T1's commit timestamp is strictly less than T2's. This is a stronger guarantee than serializability (transactions appear to run one at a time) — it adds the requirement that the order matches real time.

Why is this hard? Three reasons:

• Clock drift: cheap quartz clocks drift by milliseconds per day. Without correction, two servers a continent apart might disagree on the time by hundreds of milliseconds.
• Network latency: consensus protocols (like Paxos, which Spanner uses) require multiple round-trips to replicate a write. Each replica is physically far away.
• The uncertainty gap: even GPS-disciplined clocks have a small error window. If two transactions' timestamp intervals overlap, you cannot know which came first from timestamps alone.

The Spanner/TrueTime solution (Corbett et al., OSDI 2012 — solved/deployed, not an open problem):

1. Every data center runs GPS receivers and atomic clocks, slaved to Google's time masters.
2. TrueTime exposes TT.now() → [earliest, latest] with a guaranteed bound $\epsilon$ (epsilon) on clock error, typically 1–7 ms.
3. When a transaction commits, Spanner picks a timestamp s ≥ TT.now().latest.
4. Commit-wait: the coordinator waits until TT.now().earliest > s before releasing the commit. At that point, true wall-clock time is provably past $s$.
5. Any later transaction that calls TT.now() will receive an interval entirely after $s$ — guaranteeing a strictly larger timestamp.

The formal proof in the paper shows this implies external consistency. The price is latency: every write pays at least $2\epsilon$ (twice the uncertainty). At $\epsilon = 7$ ms, writes take at least 14 ms extra — acceptable for most applications, especially cross-continental ones already paying 50–100 ms in network latency.

Compare this to consensus algorithms: Paxos gives agreement but not real-time ordering. TrueTime gives real-time ordering without requiring perfect clocks.

External consistency is not just a theoretical luxury — it eliminates entire classes of bugs that arise when the order of events is ambiguous:

• Financial systems: double-spend prevention and account balance correctness require that the database cannot "forget" a write that happened before the read. Spanner's consistency makes these guarantees formal.
• Ad auctions: Google Ads runs on Spanner. Every ad impression must be charged exactly once, and budget caps must be globally enforced across billions of auctions per day.
• Inventory management: when thousands of servers simultaneously decrement a product's stock count, external consistency prevents overselling — the writes form a provable total order.
• Multi-region replication: traditional databases require you to choose between read-your-writes consistency and low latency. Spanner's design allows strongly consistent reads from the nearest replica without a round-trip to the leader.
• Cloud databases: Google Cloud Spanner is a commercial product; CockroachDB, YugabyteDB, and others use similar ideas (hybrid logical clocks in place of GPS) to offer distributed ACID guarantees.

The deeper lesson is architectural: time is a first-class resource in distributed systems. Spanner showed that investing in accurate, bounded-uncertainty clocks at the infrastructure level makes the software layer dramatically simpler and safer — a tradeoff that has influenced every major globally distributed database built since 2012.

Spanner and TrueTime dismantled a widely held belief: that a globally replicated database could not be both strongly consistent and practically available. The trick was to treat time itself as an engineering problem. By deploying GPS receivers and atomic clocks in every data center, Google gave each server a tight, provable bound on clock error — and then designed the commit protocol to wait out that uncertainty.

The result is a proven system (deployed in production since 2012) that provides external consistency across continents at millisecond-scale extra latency. It did not repeal the laws of physics; it worked with them, paying a few milliseconds in commit-wait to buy a global, unambiguous ordering of every transaction.

If you want to learn more about the foundations, explore consensus algorithms — which Spanner uses at each shard — or P vs NP for the broader question of what distributed problems admit efficient solutions. Spanner's story is a reminder that sometimes the hardest-looking problems yield not to a clever algorithm, but to precise measurement and a willingness to wait.