Google Spanner and TrueTime

01 · CONTEXT

Why Spanner existed

Before Spanner, Google teams that needed a database with global reach ran into two imperfect systems. Bigtable had many users, but drew complaints from those with complex, evolving schemas or who wanted strong consistency with wide-area replication; in addition, it only offered eventually consistent replication across datacenters. Megastore had a semi-relational model and synchronous replication, but with relatively low write throughput.

The first customer was F1, a rewrite of Google's ads backend, which came from a manually sharded MySQL. The last reshard of that database took more than two years of intense effort, and F1 needed strong transactional semantics, which made the other NoSQL systems impractical.

Spanner's answer is to shard the data across many sets of Paxos state machines spread around the world, with synchronous replication, and offering distributed transactions with external consistency. According to the paper, it is the first system to do this at global scale.

02 · ARCHITECTURE

Zones, Paxos groups, and directories

A Spanner deployment is organized into zones. The zone is the unit of administrative deployment and the set of zones is also the set of locations where data can be replicated. Each zone has a zonemaster, which assigns data to the spanservers, and between one hundred and several thousand spanservers, which serve data to clients.

Each spanserver implements a Paxos state machine on top of each tablet, and the set of replicas is a Paxos group. Writes start at the leader; reads access state directly from the tablet on any sufficiently up-to-date replica. The leader also holds the lock table used in concurrency control.

1. The application asks the location proxy which spanserver serves the data it wants.

2. The proxy points to the leader replica of the Paxos group responsible for the data.

3. A write goes to the leader, which locks the keys involved.

4. The leader replicates the write to the followers in other zones; with a majority of votes, it is committed.

5. A read can be served by any sufficiently up-to-date replica, without going through the leader.

6. In the background, the placement driver moves directories between groups when it is necessary to balance load or meet replication constraints.

To control locality, Spanner groups contiguous keys with the same prefix into directories. The directory is the unit of placement: all of its data has the same replication configuration, and it is directory by directory that data moves between Paxos groups, even with client operations in progress. The application can, for example, store each user's data in its own directory, so that one user has replicas in Europe and another in North America.

03 · TIME

TrueTime: a clock with declared uncertainty

To order transactions worldwide, Spanner assigns commit timestamps with global meaning. The intended guarantee is external consistency, equivalent to linearizability: if one transaction finishes before another starts, the first one's timestamp is smaller than the second's. Ordinary clocks do not say how wrong they are; TrueTime is the API that exposes that uncertainty.

TT.now() returns an interval, with endpoints earliest and latest, that is guaranteed to contain the absolute time of the call. TT.after(t) is true only when t has definitely passed. It is this honesty about error that makes it possible to reason about order without assuming perfect clocks.

1. The spanserver asks the local daemon for the time and receives an interval, not a single instant.

2. The daemon queries several masters, both GPS and atomic clock, and discards those that diverge from the rest.

3. The two types of reference exist because they fail in different ways: a GPS failure does not, by itself, bring down the atomic clocks.

4. Between two queries, the daemon advertises an uncertainty that grows slowly, and the spanserver starts working with an increasingly wide interval.

5. If the masters become unavailable, the uncertainty rises and the spanserver has to wait longer; correctness is preserved, but latency gets worse.

TrueTime uses two types of time reference, GPS and atomic clocks, because they fail in different ways. The remaining masters, called Armageddon masters, have atomic clocks. On each machine, a daemon queries several masters and rejects those that lie. In production at the time, the instantaneous uncertainty ranged from about one to seven milliseconds in each polling interval, and the average uncertainty was four milliseconds most of the time; the implementation generally keeps it below ten milliseconds.

04 · TRANSACTIONS

Commit wait: trading latency for order

Read-write transactions use two-phase locking. When the transaction touches a single Paxos group, as most do, it bypasses the transaction manager. With more than one group, the leaders coordinate a two-phase commit over Paxos, which mitigates the availability problems of that protocol. The authors argue for dealing with the bottlenecks of excessive transaction use when they appear, rather than forcing everyone to program without transactions.

1. The client, which keeps the writes in a buffer, drives the commit: it sends the request to the leaders of the two groups and indicates which one is the coordinator.

2. The participant leader locks the data, chooses a prepare timestamp greater than any it has already assigned, and records the prepare via Paxos.

3. The participant notifies the coordinator of its prepare timestamp.

4. The coordinator chooses the commit timestamp: not less than the prepare timestamps and greater than TT.now().latest at the moment it received the request.

5. The coordinator records the commit via Paxos but, before allowing its replicas to apply the record, waits until TT.after of the timestamp is true.

6. After the wait, the coordinator's replicas apply the record; the coordinator sends the timestamp to the client and the participant, and all apply at the same timestamp and release the locks.

External consistency comes from two rules. In the Start rule, the coordinator chooses a commit timestamp greater than TT.now().latest at the moment it received the request and not less than the participants' prepare timestamps. In the Commit Wait rule, it prevents clients from seeing what was committed until the timestamp is in the past. The expected wait is at least twice the average uncertainty.

Not every read needs locks. A read-only transaction executes its reads at a system-chosen timestamp, without locking, and does not block incoming writes; the snapshot read is a read in the past, also without locks. Each replica tracks its safe time, the highest timestamp up to which it is up to date, and only serves reads up to it.

05 · COSTS AND LIMITS

What global scale charges

In the paper's availability test, killing a zone without leaders did not affect read throughput. Leaders have leases with a default duration of ten seconds. Killing the leaders' zone without warning had a severe effect on the completion rate, and only about ten seconds later, when the leases expired and new leaders were elected, did everything recover. Shorter leases would reduce the effect, at the cost of more renewal traffic.

Coordination also has a price. In a micro-benchmark with one replica, commit wait was about five milliseconds and Paxos latency about nine. Two-phase commit scaled reasonably up to tens of participants, and latency started to rise noticeably at one hundred. The values are those of the paper, from that time.

For F1, the gain was no longer needing manual resharding and having automatic failover, whereas with MySQL under master-slave replication failover was difficult and risked data loss and unavailability. F1 uses five replicas spread across the United States.

The paper also lists limitations of the time, such as the lack of support for configuration changes within the Paxos itself and automatic secondary indexes.