Abstract

Spanner is Google’s scalable, multi-version, globally distributed, and synchronously replicated database. It is the first system to distribute data at global scale and support externally consistent distributed transactions. The paper describes how Spanner is structured, its feature set, the rationale underlying its design decisions, and a novel time API called TrueTime that exposes clock uncertainty. TrueTime and its implementation are critical to supporting external consistency and a variety of powerful features: non-blocking reads in the past, lock-free read-only transactions, and atomic schema changes across all of Spanner.

Historical Context

What Existed Before Spanner

Before Spanner, Google faced a painful trade-off:

• Bigtable (2006): Scalable but provided only eventual consistency and single-row transactions. Developers had to build complex application-level consistency on top.
• Megastore (2011): Provided cross-datacenter ACID transactions but with poor write throughput (a few writes per second per entity group) due to synchronous Paxos across data centers.
• Traditional SQL databases: Provided ACID but couldn’t scale globally.

Google engineers found themselves spending enormous effort working around Bigtable’s lack of transactions. As the paper states:

“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.”

Spanner was designed to give them the best of both worlds: the scalability of Bigtable with the transactional guarantees of traditional SQL.

Key Concepts

TrueTime API

The most novel contribution of the paper. TrueTime is an API that exposes clock uncertainty:

Unlike NTP (which gives a single time value with unknown error), TrueTime explicitly bounds the uncertainty. Google achieves this using:

• GPS receivers in each data center (accurate to ~1μs)
• Atomic clocks as backup (in case GPS fails)
• Time masters that serve synchronized time to all machines
• Average uncertainty (ε): typically 1-7ms, with a mean of ~4ms

Why TrueTime Matters

With bounded clock uncertainty, Spanner can assign globally meaningful timestamps to transactions:

1. A transaction commits at timestamp s
2. The commit waits until TT.after(s) is true (the “commit-wait” rule)
3. This guarantees that any transaction that starts after this one sees the committed data

This waiting time is typically just a few milliseconds, a small price for external consistency — the strongest consistency guarantee possible.

sequenceDiagram
    participant Client
    participant Spanner
    participant TrueTime

    Client->>Spanner: Begin Transaction
    Spanner->>Spanner: Execute reads/writes
    Spanner->>TrueTime: TT.now() → [earliest, latest]
    Note over Spanner: Assign commit timestamp s = latest
    Spanner->>Spanner: Commit-wait until TT.after(s)
    Note over Spanner: Wait ~4ms (avg uncertainty)
    Spanner-->>Client: Commit success at timestamp s

External Consistency

External consistency (also called strict serializability or linearizability of transactions) means:

If transaction T1 commits before transaction T2 starts (in real time), then T1’s commit timestamp is less than T2’s commit timestamp.

This is stronger than serializability (which only requires some serial ordering) because it respects real-time ordering. It means Spanner behaves as if there’s a single global clock ordering all transactions — which is exactly what TrueTime provides.

Architecture

Data Model

Spanner organizes data into:

• Universes: A single Spanner deployment (e.g., one for test, one for production)
• Zones: The unit of physical isolation (like a data center). Each zone has:
  • A zonemaster: Assigns data to spanservers
  • Hundreds of spanservers: Serve data to clients
  • Location proxies: Route clients to the right spanserver
• Directories: The unit of data placement and replication. A directory is a set of contiguous keys that share the same replication configuration.

graph TD
    subgraph Universe
        subgraph Zone1[Zone 1 - US East]
            ZM1[Zonemaster]
            SS1[Spanserver 1]
            SS2[Spanserver 2]
        end
        subgraph Zone2[Zone 2 - Europe]
            ZM2[Zonemaster]
            SS3[Spanserver 3]
            SS4[Spanserver 4]
        end
        subgraph Zone3[Zone 3 - US West]
            ZM3[Zonemaster]
            SS5[Spanserver 5]
            SS6[Spanserver 6]
        end
    end

    UP[Universe Master] --> Zone1
    UP --> Zone2
    UP --> Zone3
    PS[Placement Driver] --> Zone1
    PS --> Zone2
    PS --> Zone3

Spanserver Architecture

Each spanserver manages 100-1000 tablets (similar to Bigtable tablets). For each tablet:

1. Data stored in a Colossus (successor to GFS) B-tree-like structure
2. A Paxos state machine replicates the tablet across zones
3. The Paxos leader manages a lock table for concurrency control
4. A transaction manager coordinates two-phase commit across Paxos groups

Transaction Types

Read-only transactions are particularly powerful: they can execute across any replica (not just the leader) without locks, because the multi-version storage lets them read a consistent snapshot.

How It Works

Read-Write Transactions

1. Client begins transaction, acquires read locks
2. Reads execute at the leader replica
3. Client buffers writes locally
4. At commit time:
   • If the transaction spans a single Paxos group: leader chooses a timestamp and commits via Paxos
   • If it spans multiple Paxos groups: uses two-phase commit coordinated by one group’s leader
5. All participants wait for commit-wait before acknowledging

Two-Phase Commit + Paxos

Spanner uses Paxos to replicate both the participants and the coordinator of 2PC, avoiding the traditional problem where coordinator failure blocks the entire transaction:

sequenceDiagram
    participant Coord as Coordinator<br/>(Paxos Group A Leader)
    participant PA as Paxos Group A<br/>(3-5 replicas)
    participant PB as Paxos Group B<br/>(3-5 replicas)

    Note over Coord: Phase 1: Prepare
    Coord->>PA: Prepare (replicated via Paxos)
    Coord->>PB: Prepare (replicated via Paxos)
    PA-->>Coord: Prepared
    PB-->>Coord: Prepared

    Note over Coord: Choose timestamp s = max(all prepare timestamps)
    Note over Coord: Phase 2: Commit
    Coord->>PA: Commit at s (replicated via Paxos)
    Coord->>PB: Commit at s (replicated via Paxos)

    Note over Coord: Commit-wait until TT.after(s)
    Coord-->>PA: Release locks
    Coord-->>PB: Release locks

The key insight: even if the coordinator machine dies, the Paxos group replicating the coordinator’s state can elect a new leader and resume the 2PC protocol. This eliminates the single point of failure in traditional 2PC.

Impact & Legacy

Direct Descendants

Key Innovations

1. TrueTime proved that globally consistent transactions are practical — the commit-wait latency (4-7ms) is acceptable for most workloads
2. Showed that strong consistency doesn’t require sacrificing scalability — Spanner scales to millions of nodes across global data centers
3. Demonstrated that Paxos-replicated 2PC is reliable — by replicating the coordinator, 2PC’s single point of failure is eliminated
4. Multi-version concurrency with globally meaningful timestamps — enables lock-free read-only transactions at any replica

Publication

Published at OSDI 2012 (Operating Systems Design and Implementation), one of the top two systems conferences. The paper has been cited over 4,000 times and is widely considered one of the most influential database papers of the 2010s.

Key Takeaways

• TrueTime is the key innovation: By bounding clock uncertainty with GPS + atomic clocks, Spanner can assign globally meaningful timestamps, enabling external consistency
• Commit-wait is the price of consistency: Transactions wait a few milliseconds for clock uncertainty to pass before acknowledging — a small price for global ACID
• Paxos + 2PC solves coordinator failure: Replicating the 2PC coordinator via Paxos eliminates the classic blocking problem
• Read-only transactions are free: Multi-version storage with globally ordered timestamps enables lock-free, any-replica reads
• CAP theorem doesn’t prevent building highly available consistent systems: Spanner chooses CP but achieves very high availability (five-nines) through aggressive replication across zones

Interview Relevance

Spanner concepts are tested frequently in system design interviews, especially at Google:

• “How would you design a globally distributed database?” — Spanner’s architecture is the gold standard answer
• “How do you achieve global consistency?” — TrueTime, commit-wait, and Paxos replication
• “What’s the difference between Spanner and DynamoDB?” — CP vs AP, strong vs eventual consistency, SQL vs NoSQL
• “How does Spanner differ from traditional 2PC?” — Paxos replication of coordinator eliminates blocking
• “Can you explain external consistency?” — Stronger than serializability, respects real-time ordering