Papers
Spanner: Google's Globally-Distributed Database
James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, JJ Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, Wilson Hsieh, Sebastian Kanthak, Eugene Kogan, Hongyi Li, Alexander Lloyd, Sergey Melnik, David Mwaura, David Nagle, Sean Quinlan, Rajesh Rao, Lindsay Rolig, Yasushi Saito, Michal Szymaniak, Christopher Taylor, Ruth Wang, Dale Woodford · OSDI (10th USENIX Symposium on Operating Systems Design and Implementation), 2012
The problem: scaling globally without giving up transactions and strong consistency
Inside Google, many applications used Bigtable, but they received constant complaints from teams that needed complex, evolving schemas, or strong consistency even with wide-area replication. Bigtable only offered eventually consistent replication across datacenters and had no cross-row transactions. Other teams chose Megastore, which had a semi-relational model and synchronous replication, but paid the price of relatively low write throughput. Spanner's first customer was F1, a rewrite of Google's ads backend, which needed horizontal scale, transactions, and strong consistency across replicas all at once. The paper describes Spanner as a scalable, multi-versioned, globally distributed, synchronously replicated database that evolved from a Bigtable-like versioned key-value store into a temporal multi-version database: data lives in semi-relational tables, each version is automatically timestamped with its commit time, old versions are subject to configurable garbage collection, and the application can read data at past points in time. The authors also defend an engineering position: it is better to let programmers deal with performance bottlenecks caused by overuse of transactions than to force them to always code without transactions. According to them, running two-phase commit over Paxos mitigates the availability problems traditionally attributed to 2PC.
Architecture: zones, Paxos groups and directories
A Spanner deployment is called a universe and is organized into zones, which are the unit of administrative deployment and physical isolation, and also the set of locations where data can be replicated. Each zone has a zonemaster, which assigns data to spanservers, and between one hundred and several thousand spanservers, which serve data to clients. Each spanserver handles between 100 and 1000 tablets, structures that map (key, timestamp) to values and keep their state in files and in a write-ahead log in the Colossus distributed file system. For replication, each tablet has a Paxos state machine; the set of replicas of a tablet forms a Paxos group. Spanner's Paxos uses long-lived leaders, based on time leases whose default duration is 10 seconds. Writes must start the Paxos protocol at the leader, whereas reads can be served by any sufficiently up-to-date replica. The leader keeps a lock table for concurrency control and a transaction manager, used when a transaction involves more than one Paxos group. On top of this, Spanner offers the concept of a directory: a set of contiguous keys with a common prefix, which is the unit of data placement. All data in a directory shares the same replication configuration, and the system moves directories between Paxos groups, even while clients are operating, to balance load or to bring data closer to those who access it. Applications control where each piece of data lives, for example by storing each user's data in its own directory, with replicas in the chosen region.
TrueTime: exposing clock uncertainty instead of hiding it
The centerpiece of Spanner is the TrueTime API, which represents time as an interval with bounded uncertainty, rather than a single instant. The call TT.now() returns a TTinterval with the endpoints earliest and latest, guaranteed to contain the absolute time at which the call happened. TT.after(t) says whether t has definitely passed, and TT.before(t) says whether t has definitely not yet arrived. The implementation uses two kinds of time reference with different failure modes, GPS and atomic clocks. Each datacenter has a set of time master machines, most with GPS receivers and the rest (called Armageddon masters) with atomic clocks, and each machine runs a timeslave daemon that polls several masters, discards the ones that lie, and synchronizes the local clock. Between synchronizations, the daemon advertises a slowly growing uncertainty, derived from a conservatively applied clock drift rate of 200 microseconds per second, polling every 30 seconds. In production, this uncertainty (epsilon) varies in a sawtooth from about 1 to 7 ms over each polling interval, which gives an average around 4 ms most of the time. The key idea is that the correctness of Spanner's guarantees depends on these bounds: if the uncertainty grows, the system gets slower because it has to wait, but stays correct.
External consistency: commit timestamps, commit wait, and 2PC across groups
Spanner assigns globally meaningful timestamps to transactions, and the order of these timestamps respects the serialization order. It guarantees external consistency, equivalent to linearizability: if a transaction T1 commits before T2 starts, then the commit timestamp of T1 is smaller than that of T2. This holds even if the transactions are distributed. Two protocol rules underpin the guarantee. The Start rule says that the coordinator leader assigns a write a commit timestamp no smaller than TT.now().latest, computed after the commit request reaches it. The Commit Wait rule says that the coordinator does not let clients see that transaction's data until TT.after(commit timestamp) is true, that is, until the timestamp is guaranteed to be in the past. The expected wait is at least twice the average uncertainty, and it generally overlaps with Paxos communication. Read-write transactions use two-phase locking, with wound-wait to avoid deadlocks. If the transaction touches a single Paxos group, the leader suffices; if it touches several, the leaders of those groups run two-phase commit: each participant records a prepare record with a timestamp via Paxos, the leader of one of the groups acts as coordinator, chooses the final timestamp, waits out the commit wait, and records the commit, and everyone applies at the same timestamp before releasing the locks. Because the transaction manager's state lives inside the Paxos group, it is replicated.
Lock-free reads, trade-offs, and production evidence
Because every version has a timestamp, Spanner offers reads that do not block writes. A read-only transaction, declared up front as having no writes, runs at a system-chosen timestamp, without locks, and can be served by any sufficiently up-to-date replica. Each replica keeps a safe time, the highest timestamp up to which it is up to date, and serves only reads at timestamps less than or equal to it. Snapshot reads, at a client-given timestamp or staleness bound, follow the same logic. The same mechanism enables atomic schema changes: the change transaction is assigned an explicit timestamp in the future, registered in the prepare phase, and reads and writes with an earlier timestamp proceed, while later ones wait for it. In the paper's benchmarks, write latency is around 14 ms and read latency around 1.3 ms, and snapshot-read throughput grows almost linearly with the number of replicas. In availability tests, killing an entire zone without warning dropped the read rate almost to zero, and recovery took about 10 seconds, tied to the leaders' lease duration. F1 uses five replicas, two on the US west coast and three on the east, and the authors report that automatic failover was almost invisible to them. As future work, the paper cites items such as more performance optimizations and automatic load-based resharding.
See the ideas at work
Practice the designs that use this paper in the System Design school.