Spanner: what Google's globally-distributed database paper actually says

Reading Corbett et al. (Google, OSDI 2012) after a cross-region consistency bug in production.

The bug was subtle enough that it took a week to confirm. A user submitted a form. The write committed. They were redirected to a page that read their data back — and showed the old value. The write had landed in us-east1. The read came from eu-west1. Our replication lag was typically under 100ms, but it was asynchronous, and occasionally it wasn't under anything. The "fix" was to add a ?nocache=1 parameter that forced reads against the primary region. We shipped it. The real problem — that we were making consistency promises we couldn't keep — stayed.

Spanner — "Spanner: Google's Globally-Distributed Database", Corbett et al., OSDI 2012 — is Google's answer to that class of problem at planetary scale. It's the database backing Google Ads, Google Photos, and a substantial portion of Google's internal infrastructure. The paper's central claim is remarkable: a read-write transaction spanning multiple datacenters on different continents, committing in ~5-50ms, with a consistency guarantee stronger than most distributed systems offer. Not "eventually consistent." Not "read-your-writes within a session." Externally consistent: if transaction T1 commits before T2 starts, then T1's commit timestamp is strictly less than T2's commit timestamp. Globally. Across zones. Without coordination via a single master.

The mechanism is TrueTime, and it runs on GPS receivers and atomic clocks.

The problem with "consistent enough"

Before getting into TrueTime, it helps to understand what's actually hard about distributed consistency.

Most distributed databases — including well-designed ones — offer serializability: transactions appear to execute in some total order, even if they actually ran concurrently. Serializability is strong. It means you can't see anomalies like reading uncommitted data or phantom rows. But it says nothing about the relationship between transaction order and real time.

Specifically: if two transactions T1 and T2 run on separate clients with no direct coordination between them, serializability allows T2 to appear to have committed before T1 even if, in wall-clock time, T1 committed first. This is fine for internal application logic where the order is defined by dependencies, not the clock. It's not fine when external actors observe the system and care about real-world ordering.

The concrete failure mode: your bank debits an account at 10:00:00.500. A separate service, with no knowledge of that transaction, reads the balance at 10:00:00.501 from a different replica. Under pure serializability, the read can legally return the old balance — the transactions can be serialized with the read "before" the debit. Under external consistency, this is forbidden: T1 (the debit) committed before T2 (the read) started, so T2 must see the debit.

External consistency is also called "linearizability" when applied to individual operations, but Spanner achieves it for transactions — a substantially harder problem.

TrueTime: bounded uncertainty as a first-class primitive

The root of the distributed consistency problem is clocks. Two servers cannot agree on a global "now" without communicating, and communication takes time. NTP synchronizes clocks but leaves uncertainty on the order of milliseconds. If server A assigns timestamp t to a transaction, and server B assigns timestamp t to a different transaction, you have no way to determine which actually occurred first.

Spanner's solution is to stop pretending clocks are precise and make the uncertainty explicit.

TrueTime is an API that every Spanner server has access to. It provides one primary function:

TT.now() → TTinterval: [earliest, latest]

Instead of returning a single timestamp, TT.now() returns an interval [earliest, latest] such that the true current time is guaranteed to lie within it. The uncertainty — ε = (latest - earliest) / 2 — is typically under 7ms, with spikes up to ~10ms in the 99.9th percentile.

Two additional derived functions:

• TT.after(t) → true iff t has definitely passed (i.e., earliest > t)
• TT.before(t) → true iff t has definitely not yet occurred (i.e., latest < t)

To achieve this accuracy, Google deploys time master servers — physical machines equipped with GPS antennas and atomic clocks — in each datacenter. GPS provides global time reference; atomic clocks provide stability between GPS signal losses. Each server syncs its local clock against these masters every 30 seconds, using uncertainty bounds derived from the observed drift. If a sync is late or a master is unavailable, the uncertainty bound grows until the next successful sync.

The key property: ε is a hard bound, not a probabilistic one. If TT.now() says [t-ε, t+ε], the true current time is guaranteed to be in that interval.

How external consistency is achieved: commit wait

TrueTime alone doesn't give you external consistency. The mechanism that does is commit wait.

Here's the invariant Spanner needs to maintain:

If transaction T1 commits before transaction T2 starts, then commit_ts(T1) < commit_ts(T2).

To guarantee this, Spanner assigns timestamps to transactions as follows:

1. A read-write transaction's coordinator chooses a commit timestamp s that is at least TT.now().latest at the moment of committing. This ensures s is in the future relative to TrueTime — no other timestamp assigned before s can be greater than s.

2. The transaction waits until TT.after(s) is true — i.e., until TrueTime's earliest bound exceeds s — before releasing its locks and making the commit visible.

This wait is called commit wait. In practice it's the time until the clock uncertainty window "passes" the chosen timestamp, typically 1–7ms added to transaction latency.

The proof of correctness: suppose T1 commits at real time t_abs. The coordinator assigns s1 ≥ TT.now().latest at commit time, then waits until the real time exceeds s1. So s1 < t_abs for T1's visible commit. Now T2 starts at real time t_start > t_abs. T2's coordinator calls TT.now() at or after t_start, so TT.now().earliest > s1. Any timestamp T2 chooses must be ≥ TT.now().latest > TT.now().earliest > s1. Therefore s2 > s1. External consistency holds.

The elegance here is that this doesn't require any cross-datacenter communication during normal operation. Each server independently maintains the invariant using local TrueTime calls.

The data model and replication architecture

Spanner organizes data into tablets — sorted key-value ranges, similar to Bigtable. Each tablet is replicated via Paxos across multiple zones (typically 3 or 5). A Paxos group is the set of replicas for one tablet, with one elected leader that handles writes. This is single-shard consensus, which is Spanner's unit of consistent replication.

The schema layer adds a concept Bigtable doesn't have: table interleaving. Tables can declare a parent-child hierarchy:

CREATE TABLE Users (
  user_id INT64 NOT NULL,
  name STRING(100),
) PRIMARY KEY (user_id);
 
CREATE TABLE Albums (
  user_id INT64 NOT NULL,
  album_id INT64 NOT NULL,
  title STRING(100),
) PRIMARY KEY (user_id, album_id),
  INTERLEAVE IN PARENT Users ON DELETE CASCADE;

Rows with the same user_id are physically co-located in the same tablet regardless of which table they're in. A read of a user's albums is a local operation within one Paxos group. This is the schema-level answer to the distributed join problem: if you know you'll frequently access related rows together, declare them as parents and children, and they'll live on the same replica.

Read-write transactions: two-phase commit across Paxos groups

For transactions that touch rows in multiple Paxos groups — the hard case — Spanner uses two-phase commit (2PC) with Paxos groups as the participants and one Paxos group's leader as the coordinator.

The protocol:

1. The client reads from the Paxos leaders of each involved shard, acquiring read locks
2. The client sends writes to each shard's leader (prepare phase)
3. Each participant Paxos leader acquires write locks, logs a PREPARE record, and responds
4. The coordinator chooses a commit timestamp s ≥ max(all participant prepare timestamps), logs a COMMIT record, and performs commit wait
5. The coordinator notifies participants, which log their own commit records and release locks

The cross-shard coordination is the expensive part of multi-region read-write transactions. A two-continent round trip at the prepare phase adds 50–150ms. Single-region transactions (coordinator and all participants in the same zone) commit in ~5–10ms.

The critical observation in the paper's production data: most transactions at Google are single-site. The globally distributed capability exists for the cases that need it, but the hot path is intra-zone.

Read-only transactions: the cheap path

The most important performance optimization in Spanner is that read-only transactions require no locks and no two-phase commit.

A read-only transaction receives a timestamp t_read = TT.now().latest at the start. It can then read from any replica — not just leaders — as long as the replica's data is sufficiently up-to-date (its safe time exceeds t_read). A replica's safe time advances as it applies Paxos log entries; a replica is behind if it's still processing a backlog.

This enables follower reads: a client can send read-only queries to the nearest geographic replica and get consistent, non-stale results at the read timestamp, without touching the leader at all. For Google Ads reporting, where reads vastly outnumber writes, this matters enormously.

The tradeoff: if a replica is temporarily lagging, a read-only transaction may have to wait for the safe time to advance before serving. This is bounded by replication lag, not by clock uncertainty.

There's also a snapshot read mode: you can specify a timestamp in the past (e.g., READ AS OF SYSTEM_TIME AS OF INTERVAL '10s' in modern Spanner SQL). This is always served locally, never waits, and is useful for analytics and batch processing where absolute freshness isn't required.

Lessons that survived into production systems

The Spanner paper's ideas have propagated into commercial and open-source databases in ways worth recognizing:

CockroachDB implements a similar HLC (hybrid logical clock) approach to transaction ordering. It can't use atomic clocks (it's software you deploy yourself), so it uses NTP with larger uncertainty bounds and adds uncertainty restarts — if a read timestamp might overlap with a conflicting write's uncertainty window, it retries with a later timestamp. This is Spanner's commit wait made approximate.

TiDB (TiKV's SQL layer) uses a centralized Timestamp Oracle (TSO) — a single service that hands out monotonically increasing timestamps. Simpler than TrueTime, but creates a bottleneck and a SPOF that Spanner avoids.

YugabyteDB uses HLC similar to CockroachDB and borrows Spanner's tablet/Paxos-group architecture directly.

Cloud Spanner (Google's managed service) exposes TrueTime semantics through COMMIT TIMESTAMP columns and READ AS OF SYSTEM_TIME queries. If you're using it, you're using the exact mechanism from the paper.

What the paper gets right about multi-region databases

Before the Spanner paper, the conventional wisdom was that strong consistency and global distribution were fundamentally at odds — CAP theorem, you choose two, consistency requires a single-master that becomes your latency floor.

Spanner's reframing: the CAP constraint isn't about consistency vs. availability in some abstract sense. It's about what you do during partition, which is a rare event, not the steady state. On the steady state hot path — no partition, normal operation — you can have both consistency and high availability, if you're willing to pay the commit wait latency (7–14ms typical).

The CAP framing was causing teams to accept weaker consistency than they needed. The paper makes this argument explicitly: external consistency is achievable in practice, the cost is ~10ms per write, and many systems can afford that.

When NOT to use Spanner (or Spanner-like systems)

Single-region deployments. If all your replicas are in one datacenter, you don't need TrueTime and you don't want commit wait. PostgreSQL with synchronous replication or a simpler consensus-based database will have lower latency and no extra operational complexity. Spanner's value is the global distribution; without global distribution, it's overhead.

Very high-throughput single-row OLTP where <5ms is load-bearing. Commit wait is baked in. On Cloud Spanner, a simple read-write transaction against a single row commits in ~5ms in the same region, and that floor doesn't move. If your SLA requires p99 write latency under 5ms, Spanner is not the database. Redis, in-memory stores, or co-located PostgreSQL are better fits.

Mostly-read workloads that can tolerate stale data. If your access pattern is 99% reads and you can tolerate data that's a few seconds old, eventually consistent replication (Cassandra, DynamoDB global tables) will be simpler to operate and cheaper. You don't need external consistency for "show me the popular items from yesterday."

When you don't actually have global users. The engineering sophistication Spanner requires — interleaving schemas thoughtfully, understanding commit wait, managing Paxos groups, capacity planning by region — is substantial. If your users are geographically concentrated in one region, this complexity doesn't buy you anything. Start with a single-region database; add global distribution when users in other regions become a real problem.

Analytical workloads. Spanner's architecture is optimized for OLTP. For analytics — large scans, aggregations, window functions over historical data — BigQuery or dedicated OLAP systems are better. Spanner has a QUERY interface and can handle some analytics, but it's not its sweet spot.

The thing the paper glosses over

The paper is honest about performance but less detailed about operational complexity.

Managing interleaved table hierarchies is genuinely hard. Getting schema design right for Spanner requires thinking about access patterns before you've built the product, which is the opposite of how most teams work. Bad schema design — tables that aren't interleaved, keys that aren't co-located with their most common reads — turns an expensive cross-region transaction into a series of expensive cross-region transactions.

Debugging distributed transactions is also harder. When a read-write transaction involves three shards across two regions, the latency breakdown is not obvious. Commit wait is invisible in most client libraries. You need dedicated distributed tracing to distinguish "slow because cross-region" from "slow because contended lock" from "slow because commit wait."

The paper also doesn't discuss hotspot management in depth. Spanner automatically splits and moves tablets to balance load, but a monotonically increasing key (like an auto-increment ID or a timestamp primary key) concentrates writes on the latest tablet. This is a known footgun. The mitigation is hash-prefixed keys or UUID primary keys — a schema decision you cannot easily undo after launch.

What I actually changed after reading this

The bug I started with — stale reads after redirecting to a different region — is exactly the class of problem Spanner's external consistency prevents. But "adopt Spanner" was not the right answer for our team.

The right answer was to be explicit about what we were promising. Our system was eventually consistent, but our APIs behaved as if they were strongly consistent. We fixed the contract: reads after a write either go to the same region (sticky session routing) or include a session token that encodes the write's version (a poor-man's zookie, as Zanzibar calls it). Reads that can't see at least that version wait briefly or redirect.

Spanner's contribution isn't that every system should use atomic clocks. It's that consistency properties are precise, not just "strong" or "weak", and that the tradeoffs for achieving specific guarantees — 7ms commit wait for external consistency, follower reads for cheap consistency, snapshot reads for free analytics — are characterizable and manageable. Understanding the paper means you can make those tradeoffs deliberately instead of discovering them through bugs.

Reference: "Spanner: Google's Globally-Distributed Database," Corbett et al., Google, OSDI 2012. Follow-up: "Spanner: Becoming a SQL System," Bacon et al., SIGMOD 2017.