CS PAPERS DEEP-READ · PAPER 24
Corbett et al. · Google · OSDI 2012
In 2012 Google built Spanner — a database that spreads its data across data centers on several continents, yet still behaves like one ledger whose ordering everyone agrees on. It runs Google's most critical services (like the advertising backend) and is the intellectual source of later "global databases" such as Google Cloud Spanner, CockroachDB, and TiDB. Its most famous trick is an "honest clock" called TrueTime.
To be both fast and durable, a database has to copy its data several times and scatter the copies across cities. But once the data is spread out, a nasty question appears: which happened first? An order placed in Beijing, a price edited in New York — which takes effect first? Judge by each data center's own clock? Every machine's clock runs a little fast or slow, and none can swear its time is exactly right. So global databases of the day had to choose one of two: huddle in one region and keep a clean ordering, or spread worldwide and live with occasional stale reads and scrambled ordering. Spanner insisted on having both.
An ordinary clock's flaw is pretending to be precise — it tells you "it's exactly 3:00," while secretly it isn't sure. Spanner does the opposite: it makes every machine's clock own up to its error, reporting not a point but a small interval — "it's somewhere within a few milliseconds around 3:00, and the true time is definitely inside this range." That "time with an honest margin of error" is TrueTime.
An honest interval alone isn't enough; the key is to "wait a beat" when finalizing. Every time a change is about to become final, Spanner first stamps it with a timestamp, then deliberately waits a few milliseconds — until even the fuzziest clock admits "that timestamp is now in the past" — before revealing the change to anyone. That wait guarantees one thing: any change that starts after it will get a strictly larger timestamp. So every data center worldwide, even without ever consulting one another, gives the exact same answer to "which came first" — that ledger's ordering is one everyone accepts. For fault tolerance, Spanner keeps a copy of each piece of data in several data centers and uses a round of "voting" to keep the copies in agreement, so losing a machine or two doesn't stop it.
Spanner was the first to prove that "span the globe" and "strongly consistent transactions" can coexist — you don't have to pick one. On data straddling continents, you can transfer money, place orders, and update inventory as confidently as on a single-machine database, and the system guarantees the ordering never scrambles and what you read is always the latest, sensible state. To be honest about the cost: this "wait a beat" adds a few milliseconds of latency to every write, and it relies on real GPS antennas and atomic clocks installed in every data center — hardware not everyone can afford to build.
Stop pretending the world's clocks all agree to the microsecond — have each clock honestly report "the time is somewhere in this small interval," then wait a short beat at every commit until that error has been "waited out," and the whole world will give one and the same answer to "which came first." So a database blanketing the planet feels, in use, like one single-machine ledger with an ordering everyone accepts.
Want the TrueTime interval and commit-wait timeline, the Paxos-group + two-phase-commit diagram, and the numbers? → switch to the deep read
Spanner is the first database to distribute data at global scale while still supporting externally-consistent distributed transactions. Its core innovation is TrueTime — an API that exposes clock uncertainty explicitly as a time interval; with it, Spanner gives every transaction a global timestamp that respects real-time ordering, enabling strongly consistent read-write transactions and lock-free snapshot reads over data replicated across continents, and powering Google's advertising backend F1.
The authors are James Corbett, Jeffrey Dean, Wilson Hsieh and a large team at Google; the paper appeared at OSDI 2012 (best paper). It builds on Bigtable (2006) and Megastore, stores its data on Colossus (the successor to GFS), and keeps replicas consistent via Paxos (Lamport). Downstream it powered Google's ad backend F1 and the commercial Google Cloud Spanner, and inspired a whole generation of "NewSQL / global databases" — CockroachDB, YugabyteDB, TiDB.
Bigtable was useful but only guaranteed single-row atomicity; transactions across rows or tables were left for the application to shoulder — painful to write. Megastore added synchronous replication and transactions but had low write throughput. The field near-universally believed "global replication" and "strongly consistent transactions" could not coexist — partly the CAP tradeoff, but more fundamentally a time problem.
To make machines scattered across continents agree on "which event came first," you need a time reference everyone trusts. But physical clocks always drift, and NTP's error can reach tens to hundreds of milliseconds with no reliable upper bound — you get a timestamp but don't know how far off it is. Without trustworthy time, you can't order transactions by timestamp, and so you can't build cross-data-center strong consistency. Prior systems dodged this: either give up global transactions, or lock the data into one region. Spanner chose to tackle it head-on.
A traditional clock API returns a point in time and says nothing about its error — the root of all evil. TrueTime inverts this: TT.now() returns an interval [earliest, latest] and guarantees the true time lies within it. Half the interval's width is called ε (epsilon), the "uncertainty right now."
Where does that guarantee come from? Each data center runs a set of time masters calibrated by two different-failure-mode sources — GPS receivers and atomic clocks (a GPS antenna can fail, an atomic clock can slowly drift, but they rarely fail together) — plus a known upper bound on local quartz drift, from which ε is computed. In practice ε is just a few milliseconds (roughly 1–7 ms, averaging about 4 ms). The point is not to eliminate error — that's impossible — but to quantify it and hand it to the system to deal with. TrueTime also offers two predicates: TT.after(t) (has t definitely become the past?) and TT.before(t).
Spanner's strongest promise is external consistency (transaction-level linearizability): if transaction T1 commits before T2 in real time, then T1's timestamp < T2's timestamp — the order the world sees matches the order things actually happened.
How is that enforced? At commit the coordinator picks a timestamp s = TT.now().latest (the upper end of the interval, erring large), then deliberately waits until TT.after(s) is true — until even the most conservative clock confirms "s is now in the past" — before releasing locks and making the write visible. That step is commit wait, roughly twice the uncertainty (≈ 2ε, on the order of 10 ms). This wait guarantees any transaction that starts later reads a TrueTime already past s, so it must get a larger timestamp. In other words, Spanner doesn't pretend clocks are perfect — it honestly waits the uncertainty out.
A Spanner deployment is a universe, divided into zones (roughly a data center, the unit of physical isolation and deployment). Data is sliced into tablets (multi-version (key, timestamp) → value maps, stored on Colossus). The several replicas of each tablet, sitting in different zones, form a Paxos group with an elected leader: every write is replicated through Paxos to a majority of replicas, and losing a minority still keeps service alive. A batch of contiguous keys sharing a prefix forms a directory — the smallest unit of data placement and cross-group movement.
A transaction within one Paxos group is easy; one spanning multiple groups is coordinated by two-phase commit (2PC). The Achilles' heel of classic 2PC is that if the coordinator crashes, participants get stuck and can't release their locks. Spanner's cleverness: every participant in the 2PC — and the coordinator itself — is a Paxos group. Any single-node crash is automatically covered by that group electing a new leader. So the 2PC no longer has a single point of failure and won't block forever. Read-write transactions use two-phase locking (2PL) for concurrency control (pessimistic locking).
Because every write carries a globally meaningful timestamp and old versions are kept (multi-version), read-only transactions and snapshot reads need no locks at all: give a timestamp t and you read "the version as of t," and any replica that has "caught up past t" can serve it locally — reads don't block writes, writes don't block reads, and reads can be spread to whichever replica is nearest the user. This falls out naturally once TrueTime gives global timestamps real meaning.
Spanner broke the dogma that "global distribution vs. strongly consistent transactions is a forced choice," showing that one API that states clock uncertainty honestly is enough to do externally-consistent transactions at global scale. It turned "time" — historically the least reliable thing in distributed systems — into a first-class citizen you can use to order transactions. Engineering-wise it became the core of the commercial Google Cloud Spanner; intellectually it ignited the whole NewSQL / global-database generation (CockroachDB, YugabyteDB, TiDB), though most of those followers, lacking atomic clocks, approximate TrueTime with looser clock bounds or hybrid logical clocks (HLC).
① One line: Spanner is the first database that is both globally distributed and supports externally-consistent distributed transactions; the key is TrueTime.
② Pain: under global replication, machine clocks drift and NTP error has no upper bound; without trustworthy time you can't order cross-data-center transactions by timestamp — so "global vs. strong consistency" was deemed impossible together.
③ Core idea: TrueTime returns not a point but an interval [earliest, latest] guaranteed to contain the true time; ε is the uncertainty, squeezed to a few ms by GPS + atomic clocks.
④ Ordering mechanism: external consistency = the real-time-earlier committer gets the smaller timestamp; enforced by commit wait — pick s=now().latest, wait until TT.after(s) (~2ε), then release, waiting the uncertainty out.
⑤ Architecture: data sliced into tablets, replicas across zones form a Paxos group (majority writes); contiguous same-prefix keys form a directory, the placement/movement unit.
⑥ Cross-group transactions: 2PC on top of Paxos — every participant/coordinator is a Paxos group, so a single-node crash is absorbed by in-group consensus and 2PC never blocks forever.
⑦ Dividend: global timestamps + multi-version → read-only transactions and snapshot reads are fully lock-free and can read any caught-up, nearby replica.
⑧ Impact & limits: proved "global + strong consistency" can coexist and spawned NewSQL/global databases; but writes have a ~2ε latency floor, it depends on GPS+atomic clocks, cross-group goes through 2PC, it chooses C over A under partition, and its first SQL was limited.