Spanner and TrueTime

Why did a wallet go below zero for five milliseconds?

A student moved from Pune to a hostel in Delhi for college. His prepaid wallet still lives in Mumbai, its home region since lesson 7.4, so every lunch he pays from Delhi crosses the country once.

The natural improvement is to let both regions take wallet payments. Each region stamps its writes with its own clock, and the nightly audit puts them in order by timestamp. It sounds like the way a global database ought to work.

It runs for a week on staff wallets. At 13:02 one afternoon the student’s mother tops up his wallet with ₹500 from Mumbai. Her app says “Done”. On the phone with her, he taps Pay for a ₹400 thali in Delhi a moment later.

That night the audit rebuilds every wallet at every second from the two regions’ logs, ordered by timestamp. His wallet reads minus ₹400 at 13:02:07. His spend carries a stamp 5 ms earlier than the top-up that paid for it. The money arrived before he spent it, and both people on that phone call know it. The log says the opposite.

The cause is ordinary. The Delhi server’s clock ran a few milliseconds behind Mumbai’s. Both were synchronised, but not to within five milliseconds.

Google’s Spanner is the usual answer, and Google put GPS receivers and atomic clocks in its data centres for it. Before reading on, consider the puzzle. An atomic clock is still a clock, and no two clocks agree exactly. How can a better clock make the log tell the truth?

A clock that admits its error, and a rule that waits it out

In lesson 3.3 the strongest promise was linearizability: once a write is acknowledged, every later read sees it. The same promise across many machines and many keys is called external consistency, and a good clock alone does not give it. It comes from a clock that reports how wrong it might be, and a rule that waits until that possible error has passed.

TrueTime

Google’s clock service. Instead of one time, TT.now() returns an interval guaranteed to contain the true time; TT.after(t) is true when t has definitely passed. Half the interval’s width is the uncertainty, ε.

For example: The Spanner paper reports ε as a sawtooth between about 1 and 7 ms over each 30-second poll of the time masters, so about 4 ms most of the time: 1 ms of it is the trip to the masters, and up to 6 ms is the assumed drift of 200 microseconds a second between polls.

Spanner’s rule has two parts. Start: the coordinator leader picks a commit timestamp s no smaller than TT.now().latest when the commit request arrives. Commit wait: no client may see the transaction’s data, and the client is not told “committed”, until TT.after(s) is true. The proof is short. If T2 starts after T1 commits in real time, then s1 is earlier than T1’s real commit (commit wait), which is earlier than T2’s real start, which is no later than s2 (start rule). So s1 < s2, whatever the two servers’ clocks say.

The clock is one part of the database. Each range of keys is a Paxos group (lesson 3.4), and a transaction that spans groups runs two-phase commit between them, with replicated coordinators so a crash does not leave anyone blocked (lesson 6.4). TrueTime adds the ordering, and with it lock-free read-only transactions: a read at a timestamp sees exactly the transactions stamped at or before it.

Should both regions write wallets?

The mechanism is clear. Whether this business needs it is a separate question.

A globally ordered database is a real and excellent design, and for a bank spread over continents it may be the right one. Here the conflict is a handful of students who moved cities, and one leader per wallet already gives a single order without trusting any clock: the leader’s log is the order.

What to remember

1. No two clocks agree exactly. A useful clock reports an interval, [earliest, latest], with a bound on its error, ε.
2. Start rule: stamp a commit no earlier than TT.now().latest. Commit wait: acknowledge only once that stamp is surely past. Together they make timestamps follow real-time order.
3. The price is about 2ε per commit, often hidden behind Paxos replication; the investment in GPS and atomic clocks buys a small ε.
4. Without bounded clocks, put one leader in charge of each key’s order, or accept uncertainty windows and retries.

Never order writes from different machines by their clocks unless the clock error is bounded and waited out.

In the real world

The lab leaves out what makes a real commit: locks held until the wait ends, prepare timestamps from every participant group, leader leases whose intervals never overlap, and the rule that a read-only transaction at a timestamp may have to wait until the replica it reads has caught up to it. The paper describes each.

The idea survives the simplification. Uncertainty cannot be removed from a clock; once it has a bound, you can wait it out.