Lesson 31 · Time, order and truth · Module 3

Buying Order With Clocks

Lesson 20 ended with a prohibition: never use a wall-clock timestamp to order two events on different machines. This lesson is the exception, and it is not what people think it is. The trick is not better clocks. The trick is a clock that tells you how wrong it might be — and a transaction that sits still until that much time has definitely gone by.

The win in this lesson: you will be able to explain why waiting makes ordering safe, and why the real idea is the interval in the API rather than the atomic clock in the rack.

1. The problem an accurate clock does not solve

Give every machine a very good clock. Have each transaction take its commit timestamp from that clock. You still lose, because "very good" is not "exact", and the residual error is invisible to the code reading the clock.

Here is the rule that looks sufficient and is not: a transaction takes as its timestamp the latest time its clock could possibly be. Two transactions, on two machines whose clocks are uncertain by different amounts. Time runs downward, and downward is absolute time — the order things really happened in.

So the timestamp alone cannot carry the order. Something has to connect the number a transaction chose to the moment other transactions are allowed to see its effects. That something is a wait — and to know how long to wait, the clock has to tell you how wrong it is.

2. A clock that admits what it does not know

Ordinary time APIs return a number. A number is a claim of exactness that no clock can support. The first move is to change the return type:

"TrueTime explicitly represents time as a TTinterval, which is an interval with bounded time uncertainty (unlike standard time interfaces that give clients no notion of uncertainty)."

Spanner: Google's Globally-Distributed Database, Corbett et al., OSDI 2012, §3 TrueTime. Line-break hyphens removed and the space restored where the PDF glued "a" to "TTinterval".

The whole API is three methods. It fits in four lines, and the first line is the lesson:

Method        Returns
TT.now()      TTinterval: [earliest, latest]
TT.after(t)   true if t has definitely passed
TT.before(t)  true if t has definitely not arrived

Table 1 of the paper, §3, reproduced with the PDF's lost word-spacing restored.

The guarantee attached to that interval is the only thing the rest of the design rests on:

"The TT.now() method returns a TTinterval that is guaranteed to contain the absolute time during which TT.now() was invoked."

Corbett et al., §3. Word-spacing restored as above.

Where the width comes from

Half the interval's width is the error bound, written ϵ:

"Define the instantaneous error bound as ϵ, which is half of the interval's width […]"

Corbett et al., §3. The PDF's "fi" ligature has been expanded.

3. Commit wait: pay for the order in milliseconds

A read-write transaction holds two-phase locks, which gives the protocol a window to work in:

"[…] they can be assigned timestamps at any time […] when all locks have been acquired, but before any locks have been released."

Corbett et al., §4.1.2 Assigning Timestamps to RW Transactions. The elision spans a page break.

Two rules use that window. The first stops the timestamp being too early: the coordinator assigns "a commit timestamp s_i no less than the value of TT.now().latest" (§4.1.2). The second is the one this lesson is about, and it stops the timestamp being too late:

"The coordinator leader ensures that clients cannot see any data committed by Ti until TT.after(si) is true. Commit wait ensures that si is less than the absolute commit time of Ti […]"

Corbett et al., §4.1.2, the Commit Wait rule. Subscripts are flattened by PDF text extraction: read Ti and si as T_i and s_i.

Read that as an instruction and it is embarrassingly simple: pick a timestamp, then do nothing until that timestamp is definitely in the past, and only then let anyone see your writes. Same scenario as §1, same two machines, same clocks. Only the waiting is added.

And the implementation is exactly as blunt as the diagram:

"Before allowing any coordinator replica to apply the commit record, the coordinator leader waits until TT.after(s), so as to obey the commit-wait rule described in Section 4.1.2. Because the coordinator leader chose s based on TT.now().latest, and now waits until that timestamp is guaranteed to be in the past, the expected wait is at least 2∗ϵ. This wait is typically overlapped with Paxos communication."

Corbett et al., §4.2.1 Read-Write Transactions. Line-break hyphens removed.

4. What the waiting buys

It buys a single invariant, and that invariant is the one you met in Lesson 23 under a different name:

"[…] the serialization order satisfies external consistency (or equivalently, linearizability [20]): if a transaction T1 commits before another transaction T2 starts, then T1's commit timestamp is smaller than T2's."

Corbett et al., §1 Introduction. The PDF's "fi" ligature has been expanded.

The proof in §4.1.2 is four lines, and the diagram above is those four lines drawn:

s1  <  t_abs(commit of T1)    commit wait  — the wait drags the real commit past s1
t_abs(commit of T1)  <  t_abs(start of T2)    assumption — T2 really did start later
t_abs(start of T2)  <=  t_abs(arrival at T2's coordinator)    causality
t_abs(arrival at T2's coordinator)  <=  s2    the start rule — s2 is at least TT.now().latest
-------------------------------------------------------------------------------
s1  <  s2                                       transitivity

Restated from the proof block in §4.1.2; the paper's subscripts and event names have been spelled out. Every symbol is the paper's, the wording of the right-hand column is mine.

That is the whole argument. Commit wait supplies the top line; the start rule supplies the bottom line; transitivity does the rest. No line of it depends on the clocks being accurate — only on ϵ being an honest bound.

Three ways to order two writes, priced

Row two is the honest cheap answer and it is genuinely enough for many systems. Row three is what you buy when the answer has to be a single number that an unrelated client, on another continent, can compare against its own.

5. What it costs

Commit wait puts a floor under write latency that has nothing to do with your disks, your network or your code. The floor is the clocks.

ϵ values from §3 and §5.3; the wait column applies the paper's "at least 2∗ϵ". The throughput column is my arithmetic for conflicting writes to a single key, where the waits cannot overlap.

The measured cost is modest, which is the point of all the GPS hardware:

"From the 1-replica experiments, commit wait is about 5ms, and Paxos latency is about 9ms."

Corbett et al., §5.1 Microbenchmarks. The comparison baseline is defined in the Table 3 caption: "1D means one replica with commit wait disabled."

And this is the inversion worth carrying out of the lesson. Normally better hardware buys you throughput. Here, better clocks buy you latency — directly, linearly, with no software change at all:

"[…] TrueTime ϵ may noticeably affect performance. We see no insurmountable obstacle to reducing ϵ below 1ms. Time-master-query intervals can be reduced, and better clock crystals are relatively cheap."

Corbett et al., §7 Future Work. Line-break hyphens removed.

6. The residual risk

Every guarantee above rests on one unproven sentence: ϵ is a real bound. It is not measured. It is derived from datasheets. If a local oscillator misbehaves outside its specification, the interval stops containing the truth and the whole edifice fails — silently, because nothing in the system can detect it:

"[…] the most serious problem would be if a local clock's drift were greater than 200us/sec: that would break assumptions made by TrueTime."

Corbett et al., §5.3 TrueTime. Line-break hyphens removed from "True-Time".

The defence is empirical, not logical, and the paper says so plainly — this is a claim about observed failure rates, not a proof:

"Our machine statistics show that bad CPUs are 6 times more likely than bad clocks. […] we believe that TrueTime's implementation is as trustworthy as any other piece of software upon which Spanner depends."

Corbett et al., §5.3. Line-break hyphens removed from "True-Time's".

Three practical consequences fall out of that:

• Clock infrastructure becomes a latency dependency. Losing time masters does not take the database down; it makes every write slower. The paper reports exactly that: an hour-long rise in ϵ that "resulted from the shutdown of 2 time masters at a datacenter for routine maintenance" (§5.3).
• Eviction is part of the design, not an operational afterthought. Daemons "apply a variant of Marzullo's algorithm [27] to detect and reject liars" (§3), and machines whose frequency strays outside spec are thrown out of the fleet. A clock that cannot be trusted must be removed, because there is no way to correct for it.
• You almost certainly cannot rebuild this. Without dedicated time masters, ϵ on commodity cloud instances is orders of magnitude larger, and 2ϵ of commit wait stops being milliseconds. Reach for Lesson 22's vector clocks, or for a system that already has the hardware.

7. Check yourself

8. Back to your world

You are unlikely to be issued a rack of atomic clocks. Two things transfer anyway.

First, find one API in your system that returns a point estimate where it should return a range — a cache's freshness, a replica's lag, a queue's depth, a progress bar. Change the return type to a pair and watch how much defensive guesswork upstream disappears. Exposing uncertainty instead of hiding it is the portable idea, and it costs nothing.

Second, if anything in your system compares timestamps across machines to decide an order, you now know the exact price of doing that correctly: hold the locks for twice your worst-case clock error. Measure that error. If nobody can tell you what it is, the comparison is not safe — and, per Lesson 20, it never was.