On this page

Google Spanner & TrueTime

In 2012, James Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes and a long list of Google colleagues published "Spanner: Google's Globally-Distributed Database" at OSDI. It described something most of the field had stopped believing was practical: a database that shards data across thousands of servers in data centres on several continents, replicates it synchronously with Paxos, and still gives general-purpose transactions with the strongest practical consistency guarantee — external consistency (strict serializability) — plus SQL-like queries and lock-free consistent snapshot reads.

The trick that made it work was not a new consensus protocol. It was a clock. Spanner's TrueTime API exposes clock uncertainty explicitly: instead of "it is 12:00:00.000", it says "it is somewhere between 12:00:00.000 and 12:00:00.007". Spanner then waits out that uncertainty before making a commit visible. Because Google built GPS receivers and atomic clocks into its data centres, the uncertainty is a few milliseconds, so the wait is cheap.

This page follows the OSDI 2012 paper, with later material from "Spanner: Becoming a SQL System" (SIGMOD 2017), "F1: A Distributed SQL Database That Scales" (VLDB 2013), Eric Brewer's "Spanner, TrueTime and the CAP Theorem" (2017) and the Cloud Spanner documentation. The NewSQL page compares Spanner with CockroachDB, TiDB and YugabyteDB at a product level, and Clock Synchronization covers NTP, PTP and TrueTime's hardware. This page goes deep on why the protocol is correct.


1. The problem and its constraints

By 2010 Google had two storage systems for structured data, and both disappointed some important users:

  • Bigtable scaled enormously but only offered single-row transactions and, across data centres, eventual consistency. The Spanner paper says Bigtable "can be difficult to use for some kinds of applications: those that have complex, evolving schemas, or those that want strong consistency in the presence of wide-area replication".
  • Megastore offered a semi-relational schema and synchronous replication, and was popular — the paper says at least 300 applications used it, including Gmail, Picasa, Calendar, Android Market and AppEngine — despite relatively poor write throughput.

Meanwhile, Google's advertising backend (F1) ran on a manually sharded MySQL deployment. Resharding it had last taken over two years of effort. The ads team needed a database that scaled automatically, never lost a write, survived data-centre failures, and still offered SQL, secondary indexes and ACID transactions.

So Spanner's goals were:

GoalConstraint it implies
Scale to millions of machines, hundreds of data centres, trillions of rowsAutomatic sharding and resharding; data movement without downtime
Survive the loss of a data centre or regionSynchronous replication across zones with consensus (Paxos)
General-purpose transactions across shardsDistributed commit (two-phase commit) over replicated shards
Strongest practical consistencyExternally consistent reads and writes — transactions appear in an order consistent with real time
Fast reads without locksMulti-version storage; reads at a timestamp served by any sufficiently up-to-date replica
Applications control latency and placementReplication configuration chosen per database (which regions, how many replicas)

The authors' stance on transactions is worth quoting because it shaped the system:

We believe it is better to have application programmers deal with performance problems due to overuse of transactions as bottlenecks arise, rather than always coding around the lack of transactions.

That's the opposite of the NoSQL consensus of the time, and the industry mostly came around to Spanner's view.


2. Architecture

Universe, zones, spanservers

A Spanner deployment is a universe. Google ran only a handful: a test/playground universe, a development/production universe, and a production-only universe. A universe is organised into zones:

  • A zone is the unit of administrative deployment and of physical isolation. There may be several zones in one data centre (for isolating different applications' data). Zones can be added and removed as data centres come and go.
  • Each zone has one zonemaster, which assigns data to spanservers, and several hundred to several thousand spanservers, which store and serve data. Location proxies in each zone tell clients which spanserver holds their data.
  • The universe master is mainly a status console for interactive debugging. The placement driver moves data across zones automatically on a timescale of minutes, to meet replication constraints or balance load.
flowchart TB
    UM["Universe master<br/>(status, debugging)"]
    PD["Placement driver<br/>(moves data between zones)"]
    subgraph Z1["Zone A (e.g. us-east)"]
        ZM1["Zonemaster"]
        LP1["Location proxies"]
        SS1["Spanservers<br/>(100s to 1000s)"]
    end
    subgraph Z2["Zone B (e.g. us-central)"]
        ZM2["Zonemaster"]
        LP2["Location proxies"]
        SS2["Spanservers"]
    end
    subgraph Z3["Zone C (e.g. us-west)"]
        ZM3["Zonemaster"]
        LP3["Location proxies"]
        SS3["Spanservers"]
    end
    UM --- Z1
    UM --- Z2
    UM --- Z3
    PD --> ZM1
    PD --> ZM2
    PD --> ZM3
    ZM1 --> SS1
    ZM2 --> SS2
    ZM3 --> SS3
    SS1 <-->|"Paxos replication"| SS2
    SS2 <-->|"Paxos replication"| SS3
    SS1 <-->|"Paxos replication"| SS3

Inside a spanserver

Each spanserver manages between 100 and 1,000 tablets. A Spanner tablet (similar to, but not the same as, a Bigtable tablet) is a bag of mappings:

(key: string, timestamp: int64) → string

The timestamp is part of the key: Spanner is a multi-version store, more like a multi-version database than a key-value store. Tablet state is stored in B-tree-like files and a write-ahead log on Colossus (the successor to GFS).

On top of each tablet, a spanserver runs a single Paxos state machine. The set of replicas of a tablet — typically 3 or 5, in different zones — forms a Paxos group. Each group elects a leader; leaders hold time-based leases, 10 seconds long by default. The paper's Figure 2 shows the stack, which in words is:

flowchart TB
    subgraph Spanserver["One replica of a Paxos group on a spanserver"]
        TM["Transaction manager<br/>(participant leader, 2PC)"]
        LT["Lock table<br/>(two-phase locking, key ranges)"]
        PX["Paxos state machine<br/>(leader lease, replication log)"]
        TAB["Tablet: (key, timestamp) to value<br/>B-tree files + WAL on Colossus"]
    end
    TM --> LT
    LT --> PX
    PX --> TAB
    PX <-->|"Paxos messages"| R2["Replica in zone B"]
    PX <-->|"Paxos messages"| R3["Replica in zone C"]
  • Writes must go through the Paxos protocol at the leader.
  • Reads access state directly from the tablet at any replica that is sufficiently up to date (Section 4 explains what "sufficiently" means).
  • At the leader, a lock table implements two-phase locking for concurrency control. (Long-lived transactions, such as report generation, perform poorly with optimistic concurrency control under conflicts, so Spanner chose pessimistic locking.)
  • Also at the leader, a transaction manager supports distributed transactions. The leader is then called a participant leader. If a transaction involves only one Paxos group — most do — it bypasses the transaction manager entirely: the lock table and Paxos together are enough.

Directories and splits

Above tablets, Spanner has a bucketing abstraction called a directory in the paper: a set of contiguous keys that share a common prefix. A directory is the unit of data placement — all data in a directory has the same replication configuration, and when data moves between Paxos groups, it moves directory by directory. A background task called Movedir moves directories to balance load, to put data closer to its users, or to change replication. The paper says a 50 MB directory can be moved in a few seconds; Movedir moves data in the background and then uses a transaction to move the last nominal amount atomically, so it doesn't block ongoing reads and writes for long.

A Paxos group can hold many directories, and a directory too large for one group is broken into fragments served by different groups. In Cloud Spanner's public documentation, the user-visible unit is a split: a contiguous key range, created and merged automatically based on size and load. Each split is replicated by its own Paxos group (one group may serve several splits).


3. Data model and schema

Spanner's data model, as described in the paper, is schematised semi-relational tables with a SQL-based query language and general transactions. It began as a Bigtable-like versioned key-value store and moved toward a full relational database; the SIGMOD 2017 paper describes how it became a full SQL system (with a distributed query processor, "Spanner SQL", later shared with F1 as GoogleSQL).

Every table must have an ordered set of one or more primary-key columns. The primary key forms the row's name, and each table defines a mapping from primary-key columns to the other columns. Rows are stored sorted by primary key, as in Bigtable.

Interleaved tables

The key schema feature is interleaving: a child table's rows can be stored physically inside its parent's rows. The paper's example (in its original syntax):

CREATE TABLE Users {
  uid   INT64 NOT NULL,
  email STRING
} PRIMARY KEY (uid), DIRECTORY;

CREATE TABLE Albums {
  uid  INT64 NOT NULL,
  aid  INT64 NOT NULL,
  name STRING
} PRIMARY KEY (uid, aid),
  INTERLEAVE IN PARENT Users ON DELETE CASCADE;

DIRECTORY declares Users as a top-level table whose each row, with all interleaved descendants, forms a directory. Albums rows are keyed by (uid, aid) and stored right after their Users row, sorted by the shared key prefix:

Users(1)
  Albums(1, 1)
  Albums(1, 2)
Users(2)
  Albums(2, 1)
  Albums(2, 2)
  Albums(2, 3)

The point is locality: a user's row and all their albums live in the same directory, so they're on the same Paxos group. A transaction touching one user's data is single-group — no two-phase commit — and a join of a user with their albums is a local scan. The paper notes that this lets clients describe locality relationships between tables, which is necessary for good performance in a sharded, distributed database.

Cloud Spanner's DDL today looks like standard SQL:

CREATE TABLE Singers (
  SingerId   INT64 NOT NULL,
  FirstName  STRING(1024),
  LastName   STRING(1024)
) PRIMARY KEY (SingerId);

CREATE TABLE Albums (
  SingerId   INT64 NOT NULL,
  AlbumId    INT64 NOT NULL,
  AlbumTitle STRING(MAX)
) PRIMARY KEY (SingerId, AlbumId),
  INTERLEAVE IN PARENT Singers ON DELETE CASCADE;

-- An index interleaved in the parent keeps index entries next to the rows they index.
CREATE INDEX AlbumsByTitle ON Albums(SingerId, AlbumTitle), INTERLEAVE IN Singers;

Two schema rules follow from the sorted, range-sharded storage:

  • Avoid monotonically increasing primary keys (timestamps, sequences) for high-write tables — they make every insert land on the last split. Cloud Spanner recommends UUIDv4, bit-reversed sequences or hashed prefixes.
  • Interleave what you access together, but don't over-interleave: a very large parent row (millions of children) concentrates load on one split.

Commit timestamps as data

Because every committed transaction has a globally meaningful timestamp, Cloud Spanner lets you store it: a TIMESTAMP column with OPTIONS (allow_commit_timestamp = true) can be written with PENDING_COMMIT_TIMESTAMP(), which Spanner fills with the transaction's commit timestamp. That's a reliable change-ordering field without any application clock.


4. TrueTime

The API

TrueTime has three methods (paper Table 1):

MethodReturns
TT.now()A TTinterval: [earliest, latest]
TT.after(t)true if t has definitely passed
TT.before(t)true if t has definitely not arrived

The guarantee: for an invocation tt = TT.now(), the absolute time at which the call happened, , satisfies

The instantaneous error bound is half the interval's width, and is the average. TT.after(t) is just TT.now().earliest > t; TT.before(t) is TT.now().latest < t.

The important change from an ordinary clock is that TrueTime admits what it doesn't know. Every distributed system has clock error; most ignore it and hope. TrueTime makes it a first-class part of the API, and Spanner reasons with it.

How it's implemented

The underlying time references are GPS and atomic clocks — chosen because they fail in different ways (GPS: antenna and receiver failures, radio interference, spoofing, the GPS leap-second handling; atomic clocks: drift over long periods due to frequency error).

  • Each data centre has a set of time master machines. Most have GPS receivers with dedicated antennas, physically separated to reduce correlated failures. The rest, called Armageddon masters, have atomic clocks. Masters compare their time references with each other, and each master cross-checks its reference's rate against its own local clock, evicting itself if they diverge substantially. Between synchronisations, Armageddon masters advertise a slowly increasing uncertainty derived from conservatively applied worst-case drift; GPS masters advertise uncertainty close to zero.
  • Every machine runs a timeslave daemon that polls a variety of masters — some nearby GPS masters, some farther ones, and some Armageddon masters — to reduce vulnerability to any one master's errors. It applies a variant of Marzullo's algorithm to detect and reject liars, and synchronises the local clock to the non-liars.
  • Between polls, the daemon advertises a slowly growing uncertainty. It assumes a conservative worst-case local clock drift of 200 µs/s. Polls happen every 30 seconds, so drift adds up to 6 ms between polls; with about 1 ms of communication delay to the time masters, follows a sawtooth from about 1 to 7 ms, and is about 4 ms most of the time.
  • Machines whose local clocks drift beyond the bound are evicted. The paper notes that its machine statistics showed bad CPUs were six times more likely than bad clocks — clocks were among the most reliable components.

Time-master unavailability or overloaded machines and network links can cause occasional spikes in . Spanner stays correct during those spikes; it just gets slower, because commit waits get longer.


5. Transactions and timestamps

Spanner supports three kinds of operations (paper Table 2):

OperationConcurrency controlReplica required
Read-write transactionPessimistic (two-phase locking at leaders)Leader
Read-only transactionLock-free; reads at a system-chosen timestampLeader for timestamp (multi-group: none), any up-to-date replica for reads
Snapshot read, client-chosen timestampLock-freeAny up-to-date replica
Snapshot read, client-chosen bound (e.g. "at most 10 s stale")Lock-freeAny up-to-date replica

Everything rests on two invariants about timestamps.

Invariant 1: leader leases are disjoint

Each Paxos group's leader holds a lease, granted by votes from a quorum of replicas and extended on successful writes. Spanner guarantees the disjointness invariant: for each Paxos group, each leader's lease interval is disjoint from every other leader's. A replica that votes for a leader promises not to vote for another until the lease would have expired, and it judges that expiry using TrueTime — TT.after(lease end) — so even with clock uncertainty no two leases overlap. The paper describes the details in an appendix.

A leader assigns timestamps only within its lease, and timestamps it assigns to Paxos writes are monotonically increasing, even across leaders (the monotonicity invariant): a new leader only assigns timestamps after the previous leader's lease has ended, and the previous leader only assigned timestamps inside its lease.

Invariant 2: external consistency

The paper defines it precisely. Let and be the start and commit events of transaction , and its commit timestamp. Then:

In words: if starts after has committed (in real, absolute time), then 's commit timestamp is greater than 's. Timestamp order then matches real-time order, so reading at any timestamp gives a state that real-world observers would agree is consistent.

Two rules make that hold. Let be the arrival event of the commit request at the coordinator leader.

  1. Start rule. The coordinator leader assigns no less than TT.now().latest, computed after .
  2. Commit wait. The coordinator leader ensures clients can't see any data committed by until TT.after(s_i) is true — that is, until .

The proof (from the paper) chains four inequalities:

Commit wait pins 's timestamp in the past before anyone can see it; the start rule pins 's timestamp no earlier than the real moment it reached the coordinator. Real time sits between them.

Commit wait: a worked timeline

Assume ms everywhere, and absolute times in milliseconds.

With commit wait (what Spanner does):

Absolute timeEvent
100's commit request reaches coordinator leader A. A's TT.now() = [96, 104]. Start rule:
100–103A runs Paxos for the commit record (overlaps with the wait)
≈108A's TT.now().earliest passes 104, so TT.after(104) is true. A releases locks and tells the client "committed at 104"
109The client, having seen the commit, starts on a different group whose leader B has a clock that's off by the maximum the other way. B's TT.now() must still contain the true time 109, so latest ≥ 109. Start rule: ✔

No matter how wrong B's clock is within its interval, , because by the time anyone could know committed, true time is already past 104.

Without commit wait (what goes wrong):

Absolute timeEvent
100 reaches A. TT.now() = [96, 104]. . A acknowledges immediately
101The client starts at leader B. B's clock happens to be behind: TT.now() = [97, 102] (contains 101, so it's within bounds).
later. A snapshot read at timestamp 103 sees but not — even though started after was acknowledged. External consistency is violated

That's the whole idea: commit wait makes 's acknowledgment wait until 104 is unambiguously in the past. The expected wait is at least — about 8 ms with ms — but much of it overlaps with Paxos replication, which takes milliseconds anyway.

sequenceDiagram
    autonumber
    participant C as Client
    participant A as Coordinator leader A
    participant P as Paxos replicas of A
    participant B as Leader B, other group
    C->>A: commit T1
    A->>A: TT.now is 96 to 104, so s1 = 104
    A->>P: Paxos write of commit record at 104
    P-->>A: quorum ack
    Note over A: commit wait until TT.after 104, earliest above 104
    A-->>C: committed at 104, locks released
    C->>B: start T2, commit
    B->>B: TT.now latest at least the true time, above 104
    B-->>C: committed at s2 above 104

6. Write path: read-write transactions

Single-group transactions

Most transactions touch one Paxos group — interleaved schemas are designed to make that so. The client sends reads to the group's leader, which takes read locks; the client buffers writes locally; at commit, the leader takes write locks, picks a timestamp (start rule, greater than anything it's assigned before), replicates the commit through Paxos, waits out commit wait, applies, releases locks and replies. No transaction manager or two-phase commit is involved.

Multi-group transactions: 2PC over Paxos

For transactions spanning groups, Spanner runs two-phase commit, with one big difference from classic 2PC: every participant and the coordinator is itself a Paxos group. A participant's "prepare" is a Paxos-replicated log record, so the classic 2PC problem — a coordinator crash leaving participants blocked forever — is mostly solved: if a coordinator leader fails, another replica of the coordinator group takes over with the state intact.

The paper's description (Section 4.2.1), step by step:

  1. Reads. The client issues reads to the leader of the appropriate group; the leader acquires read locks and returns the most recent data. Spanner uses wound-wait to avoid deadlocks: an older transaction requesting a lock held by a younger one "wounds" (aborts) the younger one; a younger requester waits. While a transaction stays open, the client sends keepalive messages so participant leaders don't time it out.
  2. Buffered writes. Writes are buffered at the client until commit. A consequence the paper notes: reads within a transaction don't see the transaction's own writes, which was a natural fit because reads return the timestamps of data read and uncommitted writes don't have timestamps yet.
  3. Commit begins. The client picks a coordinator group and sends a commit message to each participant's leader with the coordinator's identity and the buffered writes. Having the client drive 2PC avoids sending data twice across wide-area links.
  4. Prepare at participants. Each non-coordinator participant leader acquires write locks, chooses a prepare timestamp larger than any timestamp it has assigned to previous transactions (preserving monotonicity), logs a prepare record through Paxos, and sends its prepare timestamp to the coordinator.
  5. Coordinator decides. The coordinator leader also acquires write locks but skips the prepare phase. After hearing from all participants, it chooses a commit timestamp that is ≥ every prepare timestamp, > TT.now().latest at the time it received the commit message, and > any timestamp it has assigned before. It logs a commit record through Paxos (or an abort if a participant failed).
  6. Commit wait. Before letting any replica apply the commit record, the coordinator waits until TT.after(s).
  7. Finish. The coordinator sends to the client and to all participant leaders. Each participant logs the outcome through Paxos; all participants apply at the same timestamp and release locks.
sequenceDiagram
    autonumber
    participant C as Client
    participant CL as Coordinator leader, group 1
    participant PL as Participant leader, group 2
    participant PX1 as Paxos replicas, group 1
    participant PX2 as Paxos replicas, group 2
    C->>CL: reads, read locks taken with wound-wait
    C->>PL: reads, read locks taken with wound-wait
    Note over C: writes buffered at the client
    C->>CL: commit, writes for group 1, coordinator is group 1
    C->>PL: commit, writes for group 2, coordinator is group 1
    PL->>PL: take write locks, choose prepare ts p2
    PL->>PX2: Paxos log PREPARE at p2
    PX2-->>PL: quorum ack
    PL-->>CL: prepared at p2
    CL->>CL: take write locks, s = max of p2, TT.now latest, last ts, plus 1
    CL->>PX1: Paxos log COMMIT at s
    PX1-->>CL: quorum ack
    Note over CL: commit wait until TT.after s
    CL-->>C: committed at s
    CL->>PL: commit at s
    PL->>PX2: Paxos log COMMIT at s
    PL->>PL: apply at s, release locks
    CL->>CL: apply at s, release locks

The cost is visible in the latency: a cross-group commit needs a Paxos round at each participant (prepare), a Paxos round at the coordinator (commit), plus commit wait, plus the messages between them, all in the wide area if groups' leaders are in different regions.

Schema changes

The paper also describes non-blocking schema changes across millions of groups: a schema-change transaction is assigned a timestamp in the future, registered in the prepare phase, and reads and writes synchronise with it by timestamp — those with timestamps before the change proceed; those after it block behind it. No global pause is needed. Cloud Spanner schema updates are similarly online, running as long-running operations.


7. Read path: lock-free reads at a timestamp

Safe time

Every replica tracks a value called safe time, : the maximum timestamp at which the replica is up to date. A replica can serve a read at timestamp if and only if .

  • is the timestamp of the highest-applied Paxos write. Because timestamps increase monotonically and writes are applied in order, no future write will have a timestamp at or below it.
  • accounts for prepared but not yet committed transactions. If there are none, it's . If there are, the replica doesn't yet know their commit timestamps — only that each will be at least its prepare timestamp. So is the minimum over prepared transactions of . A read can't proceed past a prepared transaction, because that transaction might commit at a timestamp the read should see.

Read-only transactions

A read-only transaction is declared in advance (it has no writes) and executes in two phases: assign a timestamp , then do the reads as snapshot reads at , at any sufficiently up-to-date replica. No locks, so reads never block writes.

Choosing :

  • The simple, always-correct choice is = TT.now().latest at the start. By the same argument as commit wait, that's after every transaction that committed before the read started, so the read is externally consistent. The cost: a replica might have to wait for to advance to .
  • If the read's scope is one Paxos group, the client asks the group leader, which can do better: if there are no prepared transactions, it uses LastTS(), the timestamp of the last committed write at that group. That's the newest timestamp that is guaranteed to include everything committed before, and it's usually already safe, so no wait.
  • If the scope spans multiple groups, Spanner avoids a negotiation round and uses TT.now().latest, possibly waiting for safe time.

Snapshot reads

A snapshot read reads at a timestamp chosen by the client, or at a staleness bound the client gives ("no more than 15 seconds old"), and Spanner picks the newest timestamp within that bound that the chosen replica has. These are the cheapest reads in Spanner — any nearby replica can serve them without contacting the leader — and Cloud Spanner exposes them as stale reads (exact staleness or bounded staleness). Strong reads, by contrast, may need to contact the leader to learn a timestamp or confirm the replica is caught up.

sequenceDiagram
    autonumber
    participant C as Client
    participant L as Group leader
    participant R as Nearby replica
    C->>L: begin read-only txn, scope is one group
    L-->>C: s_read = LastTS, no prepared txns
    C->>R: read keys at s_read
    alt t_safe below s_read
        R->>R: wait for Paxos writes or prepared txns to resolve
    end
    R-->>C: values as of s_read, no locks taken

Keeping safe time moving

An idle Paxos group has no writes, so wouldn't advance, and reads at recent timestamps would stall. The paper's refinement: each leader tracks MinNextTS(n), the smallest timestamp it might assign to the next Paxos write, and advances it by default every 8 seconds. So in the worst case, an idle replica can serve reads at timestamps more than 8 seconds old, and a read at a newer timestamp may wait (or be redirected) until the leader advances it. The paper also describes finer-grained refinements: tracking prepared transactions per key range so that a prepared transaction only blocks reads that conflict with it, and tracking LastTS() per key range.


8. Consistency guarantees, precisely

What Spanner promises, from the paper:

  • Read-write transactions are externally consistent (equivalently, strictly serializable): their commit order respects real time, and they're serializable.
  • Read-only transactions and snapshot reads at a timestamp see a consistent snapshot: all transactions with commit timestamps ≤ the read timestamp, and none after. A read-only transaction with a TrueTime-chosen timestamp is also externally consistent.
  • Bounded-staleness and exact-staleness reads are consistent snapshots at a past timestamp: serializable, but not necessarily reflecting the latest commits.
  • All of this is globally consistent across shards and regions, not per-shard.

The caveats the paper itself and later work make:

  1. Correctness depends on TrueTime's bound being right. If a machine's actual clock error exceeded , external consistency could be violated. The paper's defence is engineering: redundant GPS and atomic references, Marzullo-style liar detection, conservative drift assumptions, and eviction of machines with bad clocks. It argues that clocks are more reliable than CPUs in their fleet. But the guarantee is "correct if the bound holds".
  2. The leader lease guarantee also uses TrueTime. Disjoint leases depend on replicas measuring lease expiry with TrueTime.
  3. Commit wait is a latency floor. Every read-write transaction pays at least about . If spikes (a time master outage), write latency rises with it.
  4. Reads in a read-write transaction go to the leader and take locks. Only read-only transactions and snapshot reads are lock-free.
  5. A transaction doesn't see its own buffered writes in the original design (reads in a transaction return committed data).
  6. Availability is "CP, but effectively CA". Brewer's 2017 note argues that Spanner is technically a CP system — during a partition, a minority side can't commit — but that Google's private network and operations make partitions rare enough that Spanner offers more than five nines of availability, so users can treat it as if it were both consistent and highly available.

9. Fault tolerance and recovery

  • Replica failure. A Paxos group with 5 replicas keeps committing with 3. Reads at a timestamp can be served by any remaining up-to-date replica.
  • Leader failure. The group must wait for the old leader's lease to expire before electing a new one (that's the disjointness invariant). The paper's availability experiment (Section 5.2) shows the cost: with 5 zones of 25 spanservers each, a database sharded into 1,250 Paxos groups, and 100 clients issuing 50,000 non-snapshot reads per second with all leaders in one zone, they killed servers in three ways. Killing a non-leader zone had no effect on throughput. A soft leader kill — telling the servers to hand off leadership first — had a minor effect. A hard leader kill caused throughput to drop to nearly zero for the affected groups for about 10 seconds — the lease length — before new leaders were elected and throughput recovered. The paper notes that shorter leases would reduce this, at the cost of more lease-renewal traffic.
  • Zone or data-centre failure. As long as a majority of each group's replicas survive, the group continues. Placement (for example, five replicas across three regions with two in the leader region) determines which failures a database can survive and what commit latency it pays.
  • Coordinator failure in 2PC. Because the coordinator is a Paxos group with its commit decision in its replicated log, a new coordinator leader can finish the protocol. Participants holding prepared state are not blocked forever as in classic 2PC; they're blocked until the coordinator group recovers, usually within a lease period.
  • Time master failure. TrueTime's redundancy and liar detection tolerate individual master failures; uncertainty grows, so latency rises, but correctness holds.

10. Performance numbers from the paper

Microbenchmarks (paper Table 3). Spanservers ran on timeshared machines with 4 GB of RAM and 4 cores (AMD Barcelona, 2200 MHz); clients ran on separate machines; each zone had one spanserver; clients and zones were in a set of data centres with network distance under 1 ms. "1D" means one replica with commit wait disabled. Approximate values:

OperationLatency, 1D1 replica3 replicas5 replicas
Write~9.4 ms~14.4 ms~13.9 ms~14.4 ms
Read-only transaction—~1.4 ms~1.3 ms~1.4 ms
Snapshot read—~1.3 ms~1.2 ms~1.3 ms

Commit wait accounts for roughly 5 ms of write latency (compare 1D with 1 replica). Paxos replication adds little when replicas are within 1 ms of each other. Throughput for snapshot reads grew strongly with the number of replicas — because any replica can serve them — while write throughput didn't, because every write goes through the leader and a quorum.

Two-phase commit scalability (paper Table 4): with one participant, mean commit latency was about 17 ms. Latency grew slowly as participants were added and, in the paper's words, the cost of 2PC was reasonable up to about 50 participants, with latencies rising significantly at 100 and 200 participants (tail latencies rising faster than means).

TrueTime (paper Section 5.3, Figure 6): measured across several thousand spanservers in data centres up to 2,200 km apart, with sampled right after timeslave polls (so excluding the local-drift sawtooth), the tail values were a few milliseconds. A networking improvement that reduced link congestion visibly lowered the tail; an incident in which two time masters were shut down for maintenance caused a spike.

F1 in production (paper Section 5.4): F1 moved to Spanner in early 2011. Its database was replicated across five replicas — two on the US West Coast and three on the East Coast — chosen to survive a major natural disaster and to keep commit latency acceptable. The paper reports, over 24 hours (paper Table 6):

OperationMean latencyStd devCount
All reads8.7 ms376.4 ms21.5 B
Single-site commit72.3 ms112.8 ms31.2 M
Multi-site commit103.0 ms52.2 ms32.1 M

The large standard deviation for reads comes from a long tail (lock conflicts and other effects); commit latency is dominated by the wide-area Paxos round between the coasts. The F1 team valued that Spanner removed manual resharding and gave them synchronous replication and automatic failover — the paper says failover had become "nearly invisible" to them.


11. What it got right, what it got wrong, and successors

What it got right

  • Making clock uncertainty explicit. TrueTime turned an unsolvable problem ("synchronise clocks perfectly") into a solvable one ("bound the error and wait it out"). It's the most influential idea in the paper.
  • Paxos per shard, 2PC across shards. Replicating each shard with consensus and running 2PC over replicated participants removed 2PC's blocking problem and gave synchronous geo-replication. CockroachDB, YugabyteDB and TiDB all use this structure (with Raft).
  • MVCC with globally meaningful timestamps. Lock-free, consistent snapshot reads at any replica; consistent backups and analytics; time-travel queries.
  • Transactions as the default. Spanner showed developers would accept some latency for transactions over coding around their absence.
  • Application-controlled locality through interleaving and replica placement.

What it got wrong or made hard

  • It needs special infrastructure. TrueTime depends on GPS antennas, atomic clocks and a disciplined fleet. Nobody outside Google could copy it in 2012. (Cloud providers' precise time services now narrow the gap — see below.)
  • Write latency has a floor: commit wait plus Paxos plus, for multi-region configurations, wide-area round trips. Multi-region Spanner writes cost tens of milliseconds or more.
  • The original system wasn't really SQL. The 2012 paper had a SQL-like language; the full SQL engine (Spanner SQL, query distribution, a standard SQL dialect, and later a PostgreSQL interface) came over the following years, as the SIGMOD 2017 paper describes.
  • Hotspots from sorted keys remain the user's problem, as in Bigtable.
  • Long read-write transactions are expensive under pessimistic locking with wound-wait, and very large transactions hit mutation limits.

F1 and Cloud Spanner

F1 (VLDB 2013) is the SQL layer Google's ads business built on Spanner: a distributed SQL query engine, hierarchical schemas mapped to interleaved tables, change history, and optimistic transactions on top of Spanner's locking. It's the system that proved Spanner could replace a sharded MySQL fleet carrying an enormous, revenue-critical workload.

Cloud Spanner became generally available in 2017. Key properties from its documentation:

  • Regional configurations (three read-write replicas in different zones of one region) and multi-region configurations with read-write, read-only and witness replicas (witnesses vote in Paxos but don't serve reads, letting a configuration survive a region loss without a full replica there). The published SLA is 99.999% for multi-region instances and 99.99% for regional ones.
  • Strong reads (externally consistent), stale reads (exact or bounded staleness), read-write transactions with locking, and read-only transactions.
  • GoogleSQL and PostgreSQL dialects, change streams, and partitioned DML for large updates.

CockroachDB and YugabyteDB: Spanner without atomic clocks

CockroachDB (2015) and YugabyteDB (2016) adopted Spanner's structure — range/tablet sharding, a consensus group per shard (Raft), MVCC with timestamps, and 2PC-style transactions across shards — but had to run on ordinary NTP-synchronised machines, where clock error can be tens or hundreds of milliseconds and isn't reliably bounded. Commit-waiting for a 500 ms worst case on every write would be unacceptable. Their substitute has three parts:

  1. Hybrid Logical Clocks (HLC). Timestamps combine physical time with a logical counter (see Clock Synchronization). Every message carries the sender's HLC timestamp, and the receiver advances its own clock to at least that value. This guarantees causality: if event B is caused by event A via a message, B's timestamp is greater than A's — without any bound on physical clock error.
  2. A configured maximum clock offset and uncertainty intervals. CockroachDB's --max-offset defaults to 500 ms; YugabyteDB's max_clock_skew_usec also defaults to 500 ms. When a transaction reads at timestamp and finds a value with a timestamp in , it can't tell whether that write happened before or after it in real time. Instead of commit-waiting on writes, the reader pays: it performs an uncertainty restart, moving its read timestamp above the uncertain value and retrying (CockroachDB first tries to "refresh" its earlier reads at the new timestamp to avoid a full restart). Once a transaction has read from a node, it can narrow its uncertainty window for that node using the node's clock observation.
  3. Clock-offset enforcement. If a CockroachDB node detects its clock is more than 80% of the max offset away from at least half the other nodes, it shuts itself down, because the uncertainty logic is only correct while the bound holds. Leaseholders, which serve reads, depend on the same bound.

The resulting guarantees are slightly weaker than Spanner's, and the vendors say so. CockroachDB's documentation describes its default isolation as serializable, with linearizability for single keys and no stale reads, but not full strict serializability across all transactions: a "causal reverse" anomaly is possible between transactions on disjoint keys that are related only through an outside channel — for example, a client that sees commit and then runs on unrelated keys could, in rare cases near the clock bound, have ordered before . Spencer Kimball's essay "Living Without Atomic Clocks" (2016) explains the trade-off: Spanner pays commit wait on every write to rule this out; CockroachDB pays occasional read restarts and accepts the narrow anomaly. CockroachDB later added global tables (21.1), which write at a timestamp in the future and commit-wait until it passes — explicitly borrowing Spanner's technique — so any replica can serve consistent, up-to-date reads for rarely written, globally read data.

SpannerCockroachDBYugabyteDB
ClockTrueTime: GPS + atomic, ε ≈ 1–7 msHLC on NTP, max offset 500 ms defaultHLC on NTP (optionally precise cloud time sources), max skew 500 ms default
Who waitsWriters (commit wait ≈ 2ε)Readers (uncertainty restarts)Readers (read restarts)
ReplicationPaxos per splitRaft per rangeRaft per tablet
Read servingLeader for strong, any replica for snapshot/staleLeaseholder; follower reads for stale; global tables at any replicaTablet leader; follower reads for stale
Strongest guaranteeExternal consistency (strict serializability)Serializable + single-key linearizableSerializable (and snapshot, read committed options)
Clock failureTrueTime bound violation could break invariants; fleet evicts bad clocksNode self-terminates when offset exceeds 80% of maxNode checks skew; bound violation risks anomalies

The gap is closing from the infrastructure side. Cloud providers now offer precise time with published error bounds (for example AWS's Time Sync Service with microsecond-level accuracy on supported instances, and the open-source ClockBound daemon that exposes a TrueTime-like [earliest, latest] interval). Systems that can trust a small, bounded error can shrink uncertainty windows or adopt commit wait cheaply — the Spanner technique is becoming available outside Google.


12. Lessons for system design interviews

  1. Know the definition of external consistency. "If T2 starts after T1 commits in real time, T2's timestamp is larger." Strict serializability = serializability + that real-time order.
  2. Explain commit wait with numbers. Assign = TT.now().latest; wait until TT.after(s); cost ≈ ; overlapped with Paxos. Be able to show what goes wrong without it.
  3. Uncertainty must be paid by someone. Spanner makes writers wait; CockroachDB/YugabyteDB make readers restart; systems with no bound at all (plain NTP + last-write-wins) silently reorder writes. Saying this clearly impresses interviewers.
  4. Consensus per shard + 2PC across shards is the standard architecture for distributed SQL. Know why it fixes 2PC's blocking problem (participants and coordinator are replicated state machines).
  5. Design for single-shard transactions. Interleaving / co-locating data that's updated together avoids 2PC. Make this a deliberate step in schema design.
  6. MVCC timestamps unlock cheap reads. Lock-free snapshot reads at any replica, bounded-staleness reads near the user, and consistent backups all fall out of globally meaningful timestamps.
  7. Placement is a latency decision. Commit latency ≈ the round trip to a quorum of replicas. Five replicas across two coasts means a cross-country round trip for every write — F1's ~70–100 ms commits.

13. Interview questions

1. What does TT.now() return, and why is that more useful than a normal timestamp?

An interval [earliest, latest] guaranteed to contain the absolute time of the call. A normal clock returns a single value with unknown error; algorithms that use it either ignore the error (and break when clocks skew) or can't use time at all. With a bounded interval, Spanner can reason exactly: choosing latest as a timestamp guarantees it's not in the past, and waiting until earliest exceeds a timestamp guarantees it's truly in the past.

2. Prove that commit wait gives external consistency.

Let T1 commit before T2 starts. Commit wait gives s1 < t_abs(commit of T1). By assumption, commit of T1 is before start of T2, and the start of T2 is at or before the moment T2's commit request reaches its coordinator. The start rule sets s2 ≥ TT.now().latest at that moment, which is ≥ the true time then. Chaining: s1 < commit1 < start2 ≤ server2 ≤ s2, so s1 < s2.

3. How long is commit wait, and why isn't it a big problem for Spanner?

At least 2ε on average — the timestamp is chosen at latest (about ε ahead of true time), and visibility waits until earliest passes it (about ε behind true time). With ε averaging about 4 ms, that's about 8 ms, and the paper's microbenchmarks show about 5 ms of added write latency in practice. It overlaps with the Paxos round, which takes milliseconds anyway, so in multi-region deployments the wide-area round trip dominates.

4. Walk through a transaction that updates rows in two different Paxos groups.

The client reads through each group's leader (read locks, wound-wait), buffers writes, and at commit picks one group as coordinator. It sends each participant leader its writes and the coordinator's identity. The non-coordinator leader takes write locks, chooses a prepare timestamp, logs PREPARE through its Paxos group, and reports the timestamp to the coordinator. The coordinator takes write locks, picks s ≥ all prepare timestamps and > TT.now().latest, logs COMMIT through its Paxos group, waits until TT.after(s), then informs the client and the participant, which logs the commit through Paxos, applies at s and releases locks.

5. How can a replica serve a consistent read without talking to the leader?

Each replica tracks safe time: the minimum of the highest applied Paxos write timestamp and (one less than) the earliest prepare timestamp of any prepared-but-uncommitted transaction. Any read at a timestamp ≤ safe time can be answered from local multi-version data, because no future write or pending commit could land at or below that timestamp. For a recent timestamp the replica may have to wait for safe time to advance; idle leaders advance it periodically (every 8 seconds by default in the paper).

6. What happens to Spanner if a machine's clock is wrong by more than ε?

External consistency and lease disjointness could be violated: a leader might assign a timestamp below one already committed elsewhere, or two leaders' leases might overlap. Spanner's defence is to make that extremely unlikely: redundant GPS and atomic references, liar detection across masters, a conservative drift bound (200 µs/s), and evicting machines whose clocks misbehave. It's a probabilistic engineering guarantee resting on the bound.

7. How does CockroachDB provide serializable transactions without TrueTime? What does it give up?

It uses Hybrid Logical Clocks for causality and assumes a maximum clock offset (500 ms by default). Reads that encounter values within the uncertainty window above their timestamp restart at a higher timestamp, so they never miss a write that might have happened before them. Nodes whose clocks drift beyond 80% of the bound shut down. What it gives up is strict serializability for transactions on disjoint keys related only through an outside channel (a rare causal-reverse anomaly), plus occasional read restarts. Its global tables reintroduce commit wait for data that must be readable consistently everywhere.

8. Why does Spanner interleave child tables in their parents?

To co-locate related rows on the same split and Paxos group. A user's row and their albums share a key prefix and sort together, so a transaction on one user's data is a single-group transaction (no 2PC), and a parent–child join is a local range scan instead of a distributed join.

9. You're designing a globally distributed bank ledger. Would you use Spanner-style external consistency? What would it cost?

Yes for the ledger itself: balances must reflect real-time order, double-spend checks need serializable transactions, and auditors expect consistent snapshots. The costs are write latency (commit wait plus a quorum round trip — tens of milliseconds within a region, around 100 ms across continents), and throughput limits on hot accounts because of locking. Mitigations: keep each account's data in one split near its home region (leader placement), design transactions to be single-group where possible (for example, per-account entries with asynchronous settlement between accounts), and use bounded-staleness reads for dashboards and analytics.


Further reading

  • James C. Corbett et al. Spanner: Google's Globally-Distributed Database. OSDI 2012 (and the extended version in ACM TOCS, 2013).
  • David F. Bacon et al. Spanner: Becoming a SQL System. SIGMOD 2017.
  • Jeff Shute et al. F1: A Distributed SQL Database That Scales. VLDB 2013.
  • Eric Brewer. Spanner, TrueTime and the CAP Theorem. Google, 2017.
  • Sandeep Kulkarni et al. Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases (Hybrid Logical Clocks). 2014.
  • Spencer Kimball. Living Without Atomic Clocks. Cockroach Labs blog, 2016.
  • Cloud Spanner documentation: TrueTime and external consistency, schema and data model, reads, transactions, replication.
  • Related on Archon: Clock Synchronization, NewSQL, Paxos Made Simple, Distributed Transactions, Isolation Levels, MVCC, Consistency Models, Bigtable & HBase, Calvin & FaunaDB.