Spanner: Google's Globally-Distributed Database

In one breath — the whole paper, compressed

Spanner shards data across many sets of Paxos state machines in datacenters worldwide, then layers two-phase locking and two-phase commit on top of those Paxos groups to provide general-purpose distributed transactions. Its central novelty is TrueTime, a clock API that returns an interval [earliest, latest] guaranteed to contain the absolute time of the call rather than a single instant, with instantaneous error bound epsilon typically 1 to 7 ms in production. A coordinator leader picks a commit timestamp s no smaller than TT.now().latest and then holds the data invisible until TT.after(s) is true — commit wait — which forces commit timestamps to agree with real-time order, making Spanner externally consistent, equivalently linearizable, at global scale. Because every version carries a globally meaningful timestamp, read-only transactions and snapshot reads execute lock-free on any sufficiently up-to-date replica, and schema changes commit atomically at a future timestamp across potentially millions of participant groups. Spanner runs Google's advertising backend F1 on five replicas across the United States, replacing a manually sharded MySQL whose last resharding took over two years of effort.

Before this paper — the world it landed in

By 2011 Google's storage stack was split. Bigtable scaled beautifully but replicated across datacenters only eventually consistently and had no cross-row transactions, which drew persistent complaints from teams with complex, evolving schemas. Megastore offered exactly what those teams wanted — a semi-relational data model and synchronous replication — and at least 300 Google applications used it, including Gmail, Picasa, Calendar, Android Market and AppEngine, despite write throughput that collapsed at several writes per second on a Paxos group. Teams that needed both scale and transactions engineered around the gap: Percolator bolted cross-row transactions onto Bigtable, and F1's revenue-critical advertising backend ran on MySQL manually sharded by customer, a dataset of only tens of terabytes whose last resharding consumed over two years and dozens of coordinating teams. The prevailing view, argued by the Bigtable and PNUTS authors among others, was that general two-phase commit was simply too expensive to offer. And with no way to speak of a single global time, a consistent snapshot or an atomic schema change spanning datacenters had no well-defined meaning at all.

The problem — what was actually breaking

Bigtable is difficult to use for applications with complex, evolving schemas or that want strong consistency under wide-area replication, because it replicates across datacenters only eventually consistently and offers no cross-row transactions.
Megastore gave applications the semi-relational model and synchronous replication they wanted, but it has no long-lived leaders, so writes issued from different replicas necessarily conflict inside Paxos even when they do not logically conflict, and a group's throughput collapses at several writes per second.
F1's advertising database was manually sharded MySQL in which each customer was pinned to a fixed shard; resharding as customers and data grew took over two years of intense, cross-team effort, so growth had to be capped by pushing data into external Bigtables, which broke transactional behavior and cross-data querying.
Assigning commit timestamps that actually reflect serialization order is trivial on one machine but meaningless across datacenters, since machine clocks disagree by unknown amounts and conventional time interfaces report a point value with no notion of uncertainty.
Applications need fine-grained control over how far data sits from its users, how far replicas sit from each other, and how many replicas exist, but a flat key-value store gives the system no way to learn which rows belong together and should move together.
Some operations must be atomic over an entire database — a schema change whose participant count is the number of groups in the database, potentially millions, or a consistent backup — and cannot be expressed as a standard transaction; Bigtable's schema changes are atomic only within one datacenter and block all operations.

Core ideas — the contributions, and why they work

TrueTime: a clock that reports uncertainty

TT.now() returns a TTinterval [earliest, latest] guaranteed to contain the absolute time at which it was invoked, rather than a single instant; half the interval's width is the instantaneous error bound epsilon. TT.after(t) and TT.before(t) are convenience wrappers answering has t definitely passed and has t definitely not arrived. The point is that uncertainty becomes a first-class value an algorithm can reason about, instead of an unstated assumption that breaks silently. It works because Google can bound epsilon cheaply with GPS receivers and atomic clocks, and because when the bound degrades only latency suffers — correctness never does.

Commit wait buys external consistency

Two rules govern commit. Start: the coordinator leader assigns a commit timestamp s no less than TT.now().latest computed after the commit request arrives. Commit Wait: no client may see data committed by that transaction until TT.after(s) is true. Together they sandwich s between the absolute arrival time of the commit request and the absolute time the commit becomes visible, so if T1 commits before T2 starts in real time then s1 is less than s2 — exactly external consistency, equivalently linearizability. The price is an expected delay of at least 2 epsilon per read-write transaction, which Spanner overlaps with Paxos communication.

Globally meaningful timestamps make reads lock-free

Because every version's timestamp is comparable anywhere in the universe, a read at timestamp t sees exactly the effects of every transaction that committed as of t, across the whole database. Read-only transactions therefore choose one timestamp and run as snapshot reads with no locks at all, so they never block writers and are never blocked by them. Snapshot reads execute at any replica that is sufficiently up-to-date, which is why their throughput scales with the number of replicas rather than piling onto the leader. Once a timestamp is chosen commit is inevitable unless the data has been garbage-collected, so clients can drop the retry loops that would otherwise have to buffer results.

Directory as the unit of placement

A directory is a set of contiguous keys sharing a common prefix, and it is the granularity at which Spanner places, replicates and moves data. All data in a directory shares one replication configuration, so an application can give user A three replicas in Europe and user B five in North America purely by tagging directories. Administrators publish a menu of named options along two dimensions — number and type of replicas, and geography — and applications select from that menu, which cleanly separates policy from mechanism. A consequence is that a Spanner tablet, unlike a Bigtable tablet, is a container that may hold several non-contiguous partitions of the row space, chosen deliberately so that frequently co-accessed directories can be colocated.

Semi-relational schema with INTERLEAVE IN

Spanner exposes schematized tables and a SQL-like language, but every table must declare an ordered set of primary-key columns, and every database must be partitioned by the client into hierarchies of tables declared with INTERLEAVE IN PARENT. A row of a top-level directory table with key K, together with every descendant-table row whose key starts with K in lexicographic order, forms one directory, physically interleaved on disk; ON DELETE CASCADE makes deleting the parent remove the children. This makes the application data model and the physical locality unit the same object: the schema itself declares which rows are accessed together. Without such declarations, the paper states plainly, Spanner would not know the most important locality relationships.

Two-phase commit layered over Paxos

Each shard's replica set is a Paxos group with a long-lived leader; a transaction touching only one group skips the transaction manager entirely, since the lock table plus Paxos already provide transactionality. Multi-group transactions run classic two-phase commit between participant leaders, but each prepare and commit record is itself replicated through Paxos, so losing a coordinator machine does not block the protocol the way textbook 2PC does — running 2PC over Paxos mitigates its availability problems. The paper argues explicitly against the received wisdom that general 2PC is too expensive: it is better to let programmers hit transaction bottlenecks as they arise than to force every application to code around the absence of transactions. The client, not a server, drives the commit, which avoids sending the write payload twice across wide-area links.

Non-blocking atomic schema changes

A schema change cannot be an ordinary transaction because the participant count is the number of groups in the database, potentially in the millions. Spanner instead assigns the schema-change transaction an explicit timestamp t in the future and registers it during the prepare phase. Ordinary reads and writes, which implicitly depend on the schema, then synchronize against the registered t: those with earlier timestamps proceed untouched, those with later timestamps block behind the change. The whole construction is meaningless without TrueTime, since making a change happen at t across thousands of servers requires a shared, bounded notion of when t is.

How it works — the mechanism, concretely

Spanserver software stack

A Spanner deployment is a universe, divided into zones that are the unit of administrative deployment, physical isolation and replication placement; each zone has a zonemaster, between one hundred and several thousand spanservers, and location proxies clients use to find them, while a singleton universe master and placement driver handle status display and minute-timescale data movement. Each spanserver is responsible for 100 to 1000 tablets, where a tablet implements a bag of mappings from (key:string, timestamp:int64) to string, stored as B-tree-like files plus a write-ahead log on Colossus, the successor to GFS. On top of each tablet sits exactly one Paxos state machine whose metadata and log live in that same tablet; the replica set is a Paxos group, writes must initiate Paxos at the leader, reads can be served directly from any sufficiently up-to-date replica's tablet, and the implementation is pipelined for WAN latency while still applying writes in order. Leader replicas additionally run a lock table mapping key ranges to two-phase-locking state — long-lived leaders are what make that table efficient to manage — and a transaction manager that acts as participant leader for cross-group commit, whose own state is stored in the underlying Paxos group and therefore replicated.

Directories, placement, and movedir

Directories are a bucketing abstraction above the key-value bag, and movedir is the background task that relocates them between Paxos groups; it is also how replicas are added or removed, because Spanner does not yet support in-Paxos configuration change. Movedir is deliberately not one transaction: it registers that a move has started, copies data in the background while client operations continue, and only when all but a nominal amount remains does it use a transaction to atomically move that remainder and update both groups' metadata. A 50MB directory can be expected to move in a few seconds. If a directory grows too large Spanner shards it into fragments that may be served by different Paxos groups on different servers, and movedir actually moves fragments rather than whole directories.

TrueTime implementation

Each datacenter runs a set of time master machines and every machine runs a timeslave daemon. Most masters have GPS receivers on dedicated, physically separated antennas; the rest, called Armageddon masters, carry atomic clocks whose failure modes are uncorrelated with GPS antenna faults, radio interference, spoofing and leap-second bugs. Masters continuously compare references against each other and cross-check their reference against their own local clock, evicting themselves on substantial divergence; between synchronizations Armageddon masters advertise slowly growing worst-case-drift uncertainty while GPS masters advertise near zero. Each daemon polls a mix of nearby GPS masters, distant GPS masters and Armageddon masters, applies a variant of Marzullo's algorithm to detect and reject liars, and syncs the local clock; machines whose frequency excursions exceed the worst-case bound from component specs are evicted. Epsilon grows between polls at an applied drift rate of 200 microseconds per second over a 30-second poll interval, producing a 0 to 6 ms sawtooth, plus roughly 1 ms of communication delay to the masters.

Read-write transaction path

Writes are buffered at the client until commit, so a transaction's reads do not see its own writes — acceptable because reads return the timestamps of data read and uncommitted writes have no timestamp yet. Reads go to the relevant group leaders, which acquire read locks using wound-wait to avoid deadlock, and the client sends keepalives so participant leaders do not time the transaction out. At commit the client chooses a coordinator group and sends every participant leader the coordinator's identity plus that participant's buffered writes, which avoids crossing wide-area links with the data twice. Each non-coordinator participant leader acquires write locks, picks a prepare timestamp larger than any timestamp it has previously assigned, logs a prepare record through Paxos, and reports its prepare timestamp. The coordinator leader acquires write locks but skips prepare; it picks a commit timestamp s at least as large as every prepare timestamp, greater than TT.now().latest at the moment the commit message arrived, and greater than its own previously assigned timestamps, logs the commit through Paxos, waits until TT.after(s) — expected at least 2 epsilon, usually overlapped with Paxos communication — then sends s to the client and participants, who log the outcome, apply at s and release locks.

Safe time and serving reads at a timestamp

Every replica maintains t-safe, the maximum timestamp at which it is up-to-date, and may satisfy a read at t only when t does not exceed t-safe. It is the minimum of two quantities. The Paxos safe time is simply the timestamp of the highest applied Paxos write, which is sound because timestamps increase monotonically within a group and Paxos applies writes in order. The transaction-manager safe time is infinity when no transaction is prepared-but-not-committed; otherwise it is one less than the smallest prepare timestamp among prepared transactions in the group, because those transactions' outcomes and therefore their affected state are still indeterminate. Everything rests on two invariants: disjointness, that within each Paxos group each leader's lease interval is disjoint from every other leader's, enforced using TrueTime rather than extra synchronous log writes; and monotonicity, that timestamps assigned to Paxos writes within a group increase even across leader changes, enforced by requiring a leader to assign only within its own lease interval.

Read-only transaction timestamps

A read-only transaction must be predeclared as write-free and executes in two phases: assign a read timestamp, then run all its reads as snapshot reads at that timestamp on any sufficiently up-to-date replicas. Spanner requires a scope expression summarizing which keys the whole transaction will read, inferred automatically for standalone queries. If the scope lies within one Paxos group the client goes to that leader, which can do better than TT.now().latest: absent prepared transactions it can set the read timestamp to LastTS(), the timestamp of the group's last committed write, which trivially preserves external consistency since the transaction is ordered right after that write. If the scope spans several groups, the most thorough option would be a negotiation round with all the leaders based on LastTS(), but the current implementation takes the simpler path of reading at TT.now().latest, which may block until safe time advances.

Refinements that avoid needless waiting

A single prepared transaction otherwise pins transaction-manager safe time for a whole group and blocks reads that do not conflict with it at all; Spanner removes these false conflicts by keeping a fine-grained mapping from key ranges to prepared-transaction timestamps in the lock table, which already maps key ranges to lock metadata, so a read is checked only against ranges it actually conflicts with. LastTS() has the mirror-image weakness — a just-committed transaction forces even a non-conflicting read-only transaction to a later timestamp — and the same per-key-range mapping would fix it, though the paper notes this optimization was not yet implemented. Paxos safe time cannot advance without writes, so each leader maintains MinNextTS(n), the minimum timestamp that may be assigned to Paxos sequence number n plus one, and a replica that has applied through n may advance its Paxos safe time to MinNextTS(n) minus one; disjoint leases are what make those promises binding across leaders. Leaders advance MinNextTS every 8 seconds by default and on demand from slaves, so in the worst case healthy slaves of an idle group can only serve reads at timestamps more than 8 seconds old.

What the paper showed — measurements and proofs

In microbenchmarks on 4-core, 4GB scheduling units with 50 Paxos groups and 2500 directories, a 4KB write on a single replica took 14.4 +/- 1.0 ms versus 9.4 +/- 0.6 ms with commit wait disabled, so commit wait costs about 5 ms and Paxos latency about 9 ms; latency then stayed roughly constant at 3 and 5 replicas with smaller standard deviation, since a larger quorum is less sensitive to one slow slave.
Throughput split along the expected lines: snapshot reads scaled almost linearly with replicas at 13.5, 38.5 and 50.0 Kops/sec for 1, 3 and 5 replicas, while write throughput went 4.1, 2.2, 2.8 Kops/sec because the work per write grows linearly with the replica count.
Two-phase commit stayed usable at scale across 3 zones of 25 spanservers each: mean latency was 17.0 ms with 1 participant, 31.5 ms at 5, 42.7 ms at 50 and 71.4 ms at 100, only rising sharply to 150.5 ms at 200 participants, with 99th percentiles under 132 ms up to 100 participants.
In the availability test — 5 zones of 25 spanservers, 1250 Paxos groups, 100 clients issuing an aggregate 50K reads/sec with all leaders in one zone — killing a non-leader zone had no effect on read throughput, killing the leader zone after leadership handoff cost only 3 to 4 percent, and a hard kill of the leader zone dropped completions to nearly zero with full recovery after about 10 seconds, exactly the Paxos leader-lease length.
TrueTime epsilon measured at several thousand spanservers in datacenters up to 2200 km apart stayed low at the 90th, 99th and 99.9th percentiles; in production epsilon is a sawtooth of roughly 1 to 7 ms with a mean near 4 ms, tail spikes fell after network improvements on March 30, and a roughly one-hour excursion on April 13 was traced to two time masters taken down for routine maintenance.
In F1 production measured over 24 hours, 21.5 billion reads averaged 8.7 ms, 31.2 million single-site commits averaged 72.3 ms and 32.1 million multi-site commits averaged 103.0 ms; over 100 million F1 directories consist of exactly one fragment, so reads and writes for the vast majority of customers are guaranteed to touch a single server, and only 7 directories had 100 to 500 fragments, all of them secondary-index tables.

Limits and trade-offs — conceded and discovered

The paper concedes that commit wait charges roughly 2 epsilon of extra latency on every read-write transaction, so write performance is bounded by clock quality; the authors note that for applications replicating across nearby datacenters epsilon may noticeably affect performance, and say they see no insurmountable obstacle to reducing epsilon below 1 ms.
Several implementation expediencies are admitted outright: every Paxos write is logged twice, once in the tablet's log and once in the Paxos log; Spanner does not support in-Paxos configuration changes, so replica membership changes must go through movedir; and the fine-grained LastTS() optimization is described but was not yet implemented.
The authors state that node-local data structures perform relatively poorly on complex SQL queries because they were designed for simple key-value access, and that Spanner had no automatic secondary indexes — F1 had to build its own consistent global indexes out of Spanner transactions.
Availability is bounded by the 10-second Paxos leader lease: an ungraceful loss of the leader zone drove completion rates almost to zero until leases expired and new leaders were elected, and the paper acknowledges that shorter leases would help only at the cost of more lease-renewal network traffic.
Later work exposed the deeper dependency the paper treats as routine: TrueTime needs GPS receivers and atomic clocks in every datacenter, hardware most operators do not have, which is why descendants such as CockroachDB substituted hybrid logical clocks with an uncertainty window and accept occasional read restarts instead.

What it became — the systems that inherited it

Spanner converted scale-or-transactions from received wisdom into an engineering trade-off with a price tag measured in milliseconds of commit wait, and it made external consistency a shipping product feature rather than a theoretical property. Google productized it as Cloud Spanner in 2017 and later published the SQL layer that grew on top of it, while F1 evolved into a distributed query engine of its own; the same timestamp machinery underpins Google's consistent backups and consistent MapReduce executions. CockroachDB adopted the architecture nearly wholesale — key ranges replicated by consensus, distributed SQL above them, two-phase commit across ranges — but replaced TrueTime with hybrid logical clocks plus a maximum-offset uncertainty interval, trading Spanner's specialized hardware for read restarts. YugabyteDB took a similar path with hybrid logical clocks, and TiDB adopted the sibling design of a centralized timestamp oracle inherited from Percolator. Spanner also reopened the CAP debate: Google later argued in print that Spanner is technically CP but effectively CA, because Paxos over Google's own network makes partitions rare enough to ignore in practice, a framing now standard in geo-distributed SQL. Finally, the paper's closing demand — that distributed algorithms stop assuming loosely synchronized clocks and weak time APIs — has been vindicated by AWS Time Sync's ClockBound and Aurora DSQL, which expose bounded clock error to applications the way TrueTime first did.

In the paper’s words — verbatim

“It is the first system to distribute data at global scale and support externally-consistent distributed transactions.”

Abstract

“If the uncertainty is large, Spanner slows down to wait out that uncertainty.”

§1

“As a community, we should no longer depend on loosely synchronized clocks and weak time APIs in designing distributed algorithms.”

§8

Vocabulary — as this paper uses it

Universe: One Spanner deployment. Because Spanner manages data globally there are only a handful; Google ran a test/playground universe, a development/production universe, and a production-only universe.
Zone: The unit of administrative deployment and physical isolation within a universe, roughly the analog of one Bigtable deployment, and the granularity at which data can be replicated. A zone contains one zonemaster and between one hundred and several thousand spanservers, and zones can be added or removed from a running system.
Spanserver: The server process that serves data to clients. Each spanserver is responsible for 100 to 1000 tablets, runs a Paxos state machine over each one, and on the tablets where it is leader also runs a lock table and a transaction manager.
Tablet: Spanner's storage container, implementing a bag of mappings from (key, timestamp) pairs to strings, backed by B-tree-like files and a write-ahead log on Colossus. Unlike a Bigtable tablet it need not be a single lexicographically contiguous partition of the row space, since it may hold several directories.
Directory: A set of contiguous keys sharing a common prefix, formed by a directory-table row plus all interleaved descendant rows under that key. It is the unit of data placement, of replication configuration, and of movement between Paxos groups; oversized directories are split into fragments.
TTinterval and epsilon: TT.now() returns a TTinterval, an interval [earliest, latest] guaranteed to contain the absolute time of the invocation. Epsilon is half the interval's width, the instantaneous error bound, typically a 1 to 7 ms sawtooth in Google's production environment with a mean near 4 ms.
Commit wait: The rule that a coordinator leader must not let any replica reveal data committed by a transaction until TT.after(s) holds for its commit timestamp s. It guarantees s lies in the absolute past by the time the commit becomes visible, at an expected cost of at least 2 epsilon.
External consistency: The guarantee, equivalent to linearizability, that if a transaction T1 commits before another transaction T2 starts then T1's commit timestamp is smaller than T2's. Spanner was the first system to provide it at global scale.
Safe time: The maximum timestamp at which a replica is up-to-date, and therefore the newest timestamp at which it may serve a read. It is the minimum of the Paxos safe time, the timestamp of the highest applied Paxos write, and the transaction-manager safe time, one below the smallest prepare timestamp of any prepared transaction in the group.

On the timeline — where this sits in the story

Year2012

MilestoneSpanner

Problem solvedGlobal services needed data replicated across regions while still supporting strong, externally consistent transactions.

How it solved itSpanner combined replication, distributed transactions, TrueTime, and SQL-like semantics.

Why it matteredReframed the relationship between global scale and transactional consistency.

DDIACh. 6: Replication Ch. 8: Transactions Ch. 10: Consistency & Consensus

View on the timeline