Spanner: Google’s Globally-Distributed Database

Who should read it

Read it for database or distributed-systems research and for interviews where globally distributed transactions come up: it is the standard example of combining Paxos replication, two-phase locking, two-phase commit and a clock with explicit uncertainty to obtain externally consistent transactions and lock-free snapshot reads. It is not needed for application-level backend interviews, where knowing what external consistency buys and what commit wait costs is enough, and it is not a guide to today’s managed Cloud Spanner product, which has evolved since 2012.

Study objectives

• Explain the TrueTime API and the assumption it encodes: absolute time lies within the returned interval.
• Derive why the start rule plus commit wait guarantee that commit timestamps respect real-time order (external consistency).
• Walk through a read-write transaction: wound-wait two-phase locking at group leaders, client-buffered writes and two-phase commit with a coordinator group.
• Explain why read-only transactions and snapshot reads need no locks, and how safe time decides whether a replica can serve a read at a timestamp.
• Separate the paper’s correctness arguments from its measured latency, availability and clock-uncertainty results.

Prerequisites

• Replication, quorums and consensus (Raft)
• Clocks, ordering, leases and fencing
• Transactions, isolation anomalies and MVCC

Main concepts to understand

• TrueTime: TT.now() returns an interval [earliest, latest] with bounded uncertainty, implemented with GPS and atomic-clock time masters.
• External consistency: if T1 commits before T2 starts in real time, T1’s commit timestamp is smaller than T2’s.
• Commit wait: the coordinator delays making a commit visible until its timestamp is guaranteed to be in the past.
• Paxos groups with timed leader leases, and the disjointness and monotonicity invariants on timestamps.
• Read-write transactions: wound-wait locking at leaders, writes buffered at the client, two-phase commit across Paxos groups.
• Read-only transactions and snapshot reads at a timestamp, served by any replica whose safe time is high enough.
• Directories as the unit of placement and data movement, and interleaved tables for locality.
• Atomic schema changes registered at a future timestamp.

What to inspect in the evaluation

• Microbenchmarks: note the setup (timeshared machines, data served from memory, warmed location caches, clients and zones a short network distance apart) before generalizing any latency figure.
• Two-phase commit scalability: check how participants were placed, which percentiles are reported and where latency starts to rise.
• Availability: understand the three kill scenarios (non-leader zone, leader zone with handoff, leader zone without warning) and how lease length shapes recovery.
• TrueTime measurements: what was sampled, over what period, and which events cause uncertainty spikes; these are observations from one environment, not a proof of the bound.
• F1 case study: production observations from one internal customer; ask which workload, replica placement and baseline they imply.
• Missing comparisons: there is no head-to-head comparison with another distributed database on the same workload; think about what such a comparison would need.

Guarantees versus empirical results

Reading plan

1. Pass 1 (40 minutes): abstract, introduction, the TrueTime API table and the conclusions; write two sentences on what external consistency means and what Spanner pays for it.
2. Pass 2 (120 minutes): Section 4 (Concurrency Control) slowly. Reconstruct the start and commit-wait rules and the short proof of the external-consistency invariant; draw a read-write transaction across two Paxos groups with prepare and commit timestamps; explain safe time and why a prepared transaction can hold back reads.
3. Pass 3 (80 minutes): Section 2 (Implementation) for directories and placement, then Section 5 (Evaluation) with the evaluation questions in this guide; finish with related work and list which assumptions you would test first.

Discussion prompts

• What breaks if a machine’s clock drifts faster than TrueTime assumes? Which invariant fails first, and what would a client observe?
• Commit wait trades latency for ordering. How would larger clock uncertainty change latency and throughput, and what could shorten the wait?
• Compare external consistency with serializability and with linearizability. Which anomaly would a merely serializable system allow?
• How could similar guarantees be obtained without specialized clocks: a central timestamp oracle, hybrid logical clocks, deterministic ordering as in Calvin? What does each cost?
• Why does the client drive two-phase commit and buffer writes until commit? What does that imply for reading your own writes inside a transaction?

Related topics

• Consistency models and isolation guarantees
• Clocks, ordering, leases and fencing
• OLTP vs OLAP, distributed joins and distributed transactions
• Distributed transactions and recovery research
• Database paper route: CMU courses to Spanner