PAPERS-15-006 · Paper — Spanner — Google's Globally-Distributed Database

The paper

Spanner – Google’s Globally-Distributed Database, authored by James C. Corbett, Jeffrey Dean, Michael K. K. M. K. K. K. et al., was published in 2012 at OSDI. It is a landmark because it proved that strong, externally‑consistent transactions can scale across data centers worldwide.

Before this paper

Before Spanner, systems forced a trade‑off: single‑region SQL databases gave easy consistency, while NoSQL stores achieved global scale only by abandoning transactions. Engineers could not have both strong ACID guarantees and worldwide distribution because clocks on different machines never agreed exactly. This gap left large‑scale applications either inconsistent or forced to manage complex sharding logic themselves. The field lacked a database that offered both strong transactions and global replication.

The key idea

The breakthrough was TrueTime, an API that represents the current time as a bounded interval rather than a single instant. By knowing the maximum possible error of each machine’s clock, Spanner can assign globally ordered timestamps to transactions. This lets the system provide externally‑consistent (linearizable) transactions across data centers, something previously thought impossible.

How it works

Each datacenter houses GPS receivers and atomic clocks that feed a local TrueTime service. TrueTime returns a time interval [earliest, latest] that is guaranteed to contain the true time. When a transaction commits, Spanner waits until the interval’s latest bound passes, ensuring no later transaction can obtain an earlier timestamp. Data is partitioned into shards, each replicated by a Paxos group for fault tolerance. Multi‑shard transactions are coordinated with a two‑phase commit that uses the globally ordered timestamps. The commit‑wait time is bounded by the measured clock uncertainty, keeping latency predictable.

See it — time as an interval

flowchart TD
  A["GPS + atomic<br/>clocks"] --> B["TrueTime:<br/>time as interval"]
  B --> C["Wait out the<br/>uncertainty"]
  C --> D["Globally consistent<br/>transactions"]

What they showed

Spanner demonstrated that SQL, strong ACID transactions, and global replication could coexist at scale. It showed that commit‑wait latencies are bounded by the clock uncertainty, proving that external consistency is achievable without unbounded delays.

What it changed

The paper reintroduced strong consistency to planet‑scale databases and sparked a new wave of NewSQL systems. It inspired open‑source projects such as CockroachDB and YugabyteDB, and led to the commercial managed service Cloud Spanner. By breaking the perceived trade‑off, it reshaped how engineers design globally distributed storage. Next: Conflict-free Replicated Data Types.

The one-line takeaway

TrueTime shows that precise time can turn the impossible—global strong consistency—into a practical reality.

Read it / meet it

Reading the original Spanner paper gives insight into how time can be turned into a coordination primitive. Its ideas live on in today’s distributed databases and cloud services that promise global ACID guarantees.