Skip to content
Spanner: Google's Globally-Distributed Database 4 min

James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, J. J. Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild · OSDI 2012

Spanner: Google's Globally-Distributed Database

How Google built a database that is consistent across the planet: TrueTime's honest clock interval, commit wait and Paxos groups, with a clock-skew simulator.

Read the original paper

Databases · Black Belt · Pro · 4 min read

Spanner: Google's Globally-Distributed Database

Suppose you transfer money in a bank that stores its data in Tokyo, Frankfurt and Virginia. You expect the database to act as if one machine saw every transaction, one after another, in the real order they happened. That sounds obvious. It is extremely hard, because computers in different cities do not share a clock.

Spanner, Google's global database, achieves it by doing something bold: it uses GPS receivers and atomic clocks to know the time very precisely, and, more importantly, it is honest about the remaining doubt. In the authors' words, it is the first system to distribute data at global scale and still support externally-consistent distributed transactions.

Spanner's TrueTime API says "the time is somewhere between A and B." To order transactions correctly, Spanner picks a timestamp and then waits out the uncertainty before telling anyone the transaction is done. A few milliseconds of waiting buys strong consistency worldwide.

What "externally consistent" means

The promise is simple. If transaction T1 finishes before transaction T2 starts, then every observer sees T1 first. Not just on one machine. Everywhere, with data replicated around the world. This is stronger than ordinary serializability, which allows any order as long as it is consistent.

Why is it hard? To order two transactions on different machines you need timestamps, and timestamps come from clocks. Clocks drift. If the clock in Virginia is a little ahead of the one in Frankfurt, a later transaction can get an earlier timestamp. Lamport clocks avoid physical time. Spanner chooses the opposite route: make physical time trustworthy.

TrueTime: a clock that tells you how wrong it might be

A normal clock call returns one number. TrueTime's TT.now() returns an interval [earliest, latest], and it guarantees that the true time lies inside it. There are also helper calls: TT.after(t) is true only when t has definitely passed, and TT.before(t) is true only when t has definitely not arrived.

TrueTime does not pretend to know the exact time. It returns an interval that is guaranteed to contain the true time, and the code is written to wait out the doubt.

Keep reading with Pro

This paper is part of Pro. Pro and Architect open the full breakdown, with animated diagrams, interactive elements you can play with and a quiz. A few papers stay free to read in full.

Still to read

2 more sections, 1 more diagram and 2 interactive elements to play with

  • Commit wait: paying a few milliseconds for order
  • The rest of the machine

Found this breakdown useful?

Share it with someone else wrestling with this paper.

Discussion0

Join the Discussion

Sign in to leave comments, reply to others, or like insights.

Sign In to ScaleDojo

No comments yet. Be the first to start the thread!

Enjoyed this? Get more like it.

New paper breakdowns, levels, and one concept worth knowing, straight to your inbox.

No spam, ever. Unsubscribe in one click.

Enjoyed this content?

Your support keeps us creating free resources

We put a lot of hours into researching and writing these guides. If it helped you, consider buying us a coffee. Every bit goes toward keeping ScaleDojo's content free and growing.

$

One-time payment via Stripe. ScaleDojo account required.