The Shape of the System

There Is No Now

Two machines, two clocks, and a question about order that physics says you are not allowed to ask.

implementing investigate

Somebody buys something in London. A second later a refund goes out from a machine in Virginia. Both rows land in your database, each one stamped by whichever machine dealt with it, and when you sort the two rows by their timestamps the refund is on top. So the refund happened before the sale it was a refund for. Nothing was broken. The code did what it should. And when you ask which one really came first the honest answer isn't that the data got lost somewhere, it's that there's nothing there to lose in the first place. You thought a timestamp was a measurement. It's more like a rumour passed on by a stranger, about a moment the two machines never actually shared.

Timestamps get written everywhere, and we just assume you can line them up across machines, like two people reading off the same ruler. You can't. A machine only ever reads its own clock. The clock in one building has no idea what the clock next door says. When you take log lines from a few different hosts and sort them by time you're really just trusting that it'll work out, and dressing that trust up as arithmetic, and most days it is close enough that nothing seems wrong. Then some day it isn't, and the effect has gone and filed itself ahead of its cause.

The clocks can't agree, and it's nobody's fault. Inside the machine there's a quartz crystal that keeps time by vibrating, and it goes a bit quicker when it's warm and a bit slower as the thing gets older, so over a day it gains or loses some fraction of a second and wanders off from whatever its neighbours are doing. The network comes along and shoves it back into line. But that correction had to travel down a wire, and nobody knows the exact delay on that wire, so the fix is a guess too, with its own error bar wrapped around it. What you end up with is skew. Pick any instant and two machines will disagree about the time by some amount you can't actually pin down. That's just the physics of it, not some sloppy thing an engineer forgot to tidy up. And do not think the network clock saves you. It makes the gap smaller. It does not close it, and if you start believing it closes it then you've thrown away the whole point. Nobody is up in the sky with a master clock stamping events as they go past.

It runs deeper than clocks being imperfect, because give yourself perfect ones and you've still got the problem. "At the same time, far apart" isn't even a sensible thing to say. Lamport got this straight out of physics. Relativity had already thrown away the idea of one universal now and kept a partial order instead, where you can only say one event came before another if a signal had time to get from the first to the second. Take two events a long way apart with no message going between them and there just isn't an order. Which came first has no answer. Not because your instruments are too rough to dig it out, but because nobody ever wrote it down. The universe didn't record one.

So in 1978 Leslie Lamport gave up on the clock and asked about cause instead. Two things on the one machine, you know which came first. A message sent from one place and received somewhere else, well, the sending came before the receiving. Take those two plain little rules and chain them right across a system and out comes a real ordering you can stand behind, made from what actually depended on what, and not from numbers that two strangers' clocks happened to be reading at the time. A logical clock is nothing more than a counter that follows that chain. It'll never once tell you the time of day, and that's the whole idea. It tells you what came after what, and honestly that was the only thing you ever needed.

There are times when cause on its own won't do it and you really do want proper wall-clock time that everyone agrees on across continents, because you've got the one database sitting in a dozen countries and a transaction in Belgium has to land after one in Brazil. Google built a thing called Spanner, and their answer wasn't to pretend the clocks agree. They made the disagreement official instead. Their clocks run off satellites and atomic references and they don't hand you the time as a single number. They give it back as an interval. The time is somewhere between these two instants, and I won't claim to be tighter than that. Back around 2012 that interval ran a few milliseconds wide. And then Spanner does what is probably the most modest thing anyone does in distributed computing. Before it'll let a transaction commit it sits there and waits out the whole width of its own uncertainty, a lot of which is hidden behind work the commit had to do anyway, until it knows for certain the moment has really gone past everywhere. Then, and only then, it commits. You buy correctness with a few milliseconds of waiting around on purpose.

So here is the rule, and what it costs you when you don't follow it. Don't trust a timestamp off another machine to order events that you care about. A time from somewhere else is a rough label and nothing more, so don't sort by it when the order is load-bearing. When the order matters you have to carry the cause yourself, out in the open, in sequence numbers and the order of messages and version histories, and not buried in a clock. The systems that took the timestamp at face value have ended up flipping cause and effect, and they've quietly dropped writes while telling the caller everything went fine, because a last-write-wins rule read off a slow clock and decided the new thing was the stale one. And there are databases that'll do exactly this to you right now, with an open bug report sitting there to prove it. You don't see the skew at all, right up to the second it decides what's real, and by then the wrong answer has already gone in, and the clock that told it to you looked completely sure of itself.

In the manifesto, this is tenet (XXIII).

Sources

One of a series of field notes on building software for the way minds actually work: tired, distractible, ordinary, and now partly machine. They all lead back to the manifesto behind them, The Shape of the System.