Clocks, Ordering and Why "Before" Is Hard

At seventeen minutes past three on a Tuesday morning in June, four wind turbines standing on the same electrical feeder shut themselves down within seconds of each other. By twenty past nine a report had gone out naming the one that went first. By lunchtime the report had been withdrawn, and the turbine it named was the only one anybody had opened.

Galewatch, which collects a reading every two seconds from every wind turbine on the farms it monitors and sells the owners dashboards, had twenty one farms and twelve hundred and forty turbines by June. Drumlea Moss is the newest of them: forty turbines, DM-01 to DM-40, live since the Thursday in May that lesson 033 is about.

Here is what the shard held, out of the table lesson 013 cut by farm.

turbine   recorded_at    event
DM-11     03:17:02.4     shutdown
DM-14     03:17:05.1     shutdown
DM-18     03:17:05.3     shutdown
DM-22     03:17:05.5     shutdown

Say it out loud, because the audio version skips the block. DM-11 stopped two point seven seconds before the next one, and the other three went within four tenths of a second of each other. That is what a cascade looks like. One machine faults, the feeder it sits on wobbles, the neighbours protect themselves. The report named DM-11 as the initiating fault and a service visit was booked against it.

At twenty to twelve a technician at the farm had DM-11's local panel open on the maintenance network for an unrelated reason, and happened to look at the clock on it. The panel said 11:40:41.8. The laptop beside it said 11:40:46.0.

DM-11's clock was four point two seconds slow.

One unchecked clock against another, which is the right objection to raise. It held up: the measurement at the end of this lesson put DM-11 at the same four point two seconds.

None of the data is wrong. Every reading that turbine ever sent is in the table, exactly once, carrying the value it measured. Lesson 019's unique constraint on (turbine_id, recorded_at) had shipped three weeks earlier and was doing its job. The links held, the shard answered in under ten milliseconds the way lesson 013 promised, and nothing in the ingest path had a bug in it. Add the four point two seconds and DM-11 shut down at 03:17:06.6, which is after all three of the others. The turbine they blamed was the last one to go.

Then it got worse in the way these things do. Nobody had ever measured the clock on DM-14, DM-18 or DM-22. Their three stamps sit four tenths of a second apart, and four tenths of a second is a long way inside the error of a clock nobody has looked at. So the question the morning began with, which of the four went first, is not answerable from what Galewatch stored, and it never was. The one firm conclusion available is that the answer everybody acted on named the turbine that can be ruled out.

A morning, a withdrawn report, and a visit to a healthy machine.

Two timestamps do not make an order

A wall clock is the one you mean when you say clock: the thing behind now() and CURRENT_TIMESTAMP, a number the machine keeps that is supposed to track the time everybody else is tracking too. It is maintained by counting oscillations of a crystal, starting from a value somebody put there, and corrected now and then by asking somebody else.

Which makes every value it gives you an estimate of a shared quantity, with an error attached that nobody prints. A timestamp is a measurement, not a fact about order.

The consequence is the whole of today. Two timestamps from two machines can be subtracted to learn which event came first only when the gap between them is larger than the sum of the two clocks' errors. Inside that band the subtraction returns a number, the number has a sign, and the sign means nothing at all.

Run the June arithmetic. The gap the report turned on was two point seven seconds. The error on one of the two clocks, on its own, was four point two. There was never a careful enough ingest path, a better index or a tighter transaction that would have produced the right answer, because the error was baked into the number before the reading left the tower.

Marlow Books, the four person online bookshop in this course, has never once had this problem. That absence has a cause, and the cause is the lesson. Marlow has one Postgres. One machine decides the order of two writes there, and it is the same machine that decides what the data is, because the decision is a position in the write ahead log that lesson 012 watched a replica replay. A created_at column on a Marlow order is decoration. The day Marlow has a second place that accepts writes, which is lesson 024's promoted replica or a queue of the kind lesson 017 describes, it inherits every paragraph below.

Which is why lesson 033's protocol runs on a counter rather than a clock. Raft asks which term you are from because that question has an exact answer, and "what time is it" does not. The one place Raft does need time is the election timeout, and that asks how long since I last heard from anybody, which is a different question with a different answer.

What NTP gives you, and what it takes

The Network Time Protocol is how a machine stops being wrong about the time. It asks a time server, works out the offset between that server's clock and its own, and corrects itself.

The mechanism is four numbers. Your machine records t1 when it sends the request, the server records t2 when it arrives and t3 when it replies, and you record t4 when the reply lands. The round trip is (t4 - t1) - (t3 - t2), which strips out the server's own thinking time. The offset is ((t2 - t1) + (t3 - t4)) / 2.

Look at what that division by two is doing. It assumes the request took as long to get there as the reply took to come back. Suppose the real round trip is the forty five milliseconds lesson 002 measured on Tarrow Ridge's fixed wireless link, your clock is in fact perfectly correct, and the outbound leg takes ten milliseconds while the return leg takes thirty five. Put the numbers in: t1 is 0, t2 is 10, t3 is 11, t4 is 46, and the formula returns minus twelve and a half milliseconds. You conclude you are twelve and a half milliseconds ahead when you are exactly right, and twelve and a half is half of the twenty five millisecond asymmetry. NTP's error is half the asymmetry of the path, and nothing in the protocol can see it.

Here is the uncomfortable half of the June story. Put the whole of Tarrow Ridge's forty five milliseconds on one leg, which no real link does, and the error is still twenty two milliseconds, nearly two hundred times smaller than DM-11's four point two seconds. The clocks were not seconds out because time is hard. They were seconds out because nothing was looking: the farm's industrial network does not route to the internet, there was no time server on the farm side of it, and DM-11's daemon had been failing to reach anybody since the day it was commissioned.

A correction comes in two shapes. A slew changes the clock's rate, running it slightly fast or slow until it catches up, so time keeps moving forward and only its speed is a lie. A step sets it, which means the clock can jump, and a jump can go backwards. The classic daemon slews small corrections and steps large ones, with the threshold around a tenth of a second and configurable; and on a leap second some operators deliberately smear an extra second across hours of slew rather than repeat a second that code might see twice.

A fortnight after the trip, a turbine that had been offline since Tuesday came back, its daemon reached a server for the first time in days and stepped the clock back six seconds. The next three readings it sent carried stamps already sitting in the table. Lesson 019's insert ... on conflict (turbine_id, recorded_at) do nothing did exactly what it had been asked to do, and three genuinely new readings stopped existing. Three out of the 43,200 a turbine produces in a day, which lesson 025 derived, so nothing in any chart moved and no line was logged anywhere.

Lesson 019 named this seam itself, in the sentence that handed clocks to today: the uniqueness is exactly as trustworthy as the clock inside the turbine. What it bought was real, since duplicates had been accumulating for as long as the company existed. What it cost was a silent deletion, which is the worse of the two, because the duplicates were visible to anybody who counted rows.

The identity of an event should come from a counter, not from a clock. (turbine_id, seq), with the turbine incrementing seq on every sample it takes and never reusing a value, is correct no matter what the clock does, and it keeps lesson 019's whole argument intact: the reading still names itself. It also needs new firmware on twelve hundred and forty turbines, which for the older ones means an engineer and a van, the wall lesson 029 hit trying to rotate an API key out of a tower.

So there is an interim, and it is the kind of fix you ship on a Thursday. Add a digest of the reading's own values to the conflict target, which means a unique index on three columns instead of two, still carrying lesson 010's (turbine_id, recorded_at) as its prefix and still answering the panel. A genuine resend of a reading carries identical bytes and still collides, so the duplicates stay dead; two different readings that landed on the same stamp differ somewhere in the payload and both survive. The residual is honest and small: a turbine feathered in low wind, reporting the same zeros twice at the same stamp, still loses one. Write that down next to the constraint so the next person knows it is a choice.

The other clock on the machine is the one nobody reaches for. A monotonic clock counts up from an arbitrary origin, usually the last boot, is never stepped and never goes backwards, and has no relationship whatsoever to the time of day. Linux calls it CLOCK_MONOTONIC, and NTP can still adjust its rate; CLOCK_MONOTONIC_RAW refuses even that. It is meaningless across two machines or across a reboot, and inside one process it is the only honest way to measure how long something took. Measure durations on the monotonic clock and stamp events on the wall clock, and never let one do the other's job.

Now go back to lesson 032's mover, which copied for seventy one seconds after its sixty second lease had expired. Lesson 032 blamed the process: paused, swapping, blocked on a socket or stopped for a collection, and any of those will do it. A correction does the same thing and is harder to see: the holder subtracts its lease's wall clock expiry from a wall clock reading, a daemon steps that clock back five seconds between the two, and the holder concludes it has five seconds left that it does not have. Two leaders, no pause, no bug in anybody's code. A process that is wrong about the time writes log lines that agree with it, which is why the only instrument that catches this sits on the other machine.

The only order you can observe

Leslie Lamport fixed this vocabulary in 1978, in a paper called "Time, Clocks, and the Ordering of Events in a Distributed System", and its contribution is a definition rather than a mechanism. Event A happens before event B if they are on the same machine and A came first, or if A is the sending of a message and B is the receipt of that message, or if there is a chain of those steps leading from A to B. Anything else is concurrent, which does not mean simultaneous. It means nothing in the system can tell you which came first, so any order you present is one you invented.

That definition is where the June story ends for good, and it took me a while to see it. DM-11 and DM-14 never exchanged a message. There is no chain between them: each sampled its own sensors and shipped its own readings to an ingest box that saw both long after the fact. In Lamport's sense the two shutdowns are concurrent, and no logical clock ever devised will order them, because the cause they share is a disturbance on a wire that is not part of the system at all. A logical clock orders what talks. It has nothing to say about two things that never spoke.

For everything that does talk, the cheapest mechanism that respects the definition is four lines of code. Each machine keeps one counter. Increment it on every event. Send it on every message. On receiving a message, set your counter to the larger of yours and theirs, then increment. That is a Lamport counter, and it guarantees exactly one thing: if A happens before B then L(A) is less than L(B).

The converse is false, and this is the part people carry out of a blog post wrong.

one counter per box, max-plus-one on receive

box 3    e1(1)        e3(2)
                         \  message carries 2
box 4        e2(1)        \--> e4(3)

e3 happens before e4, and 2 < 3 says so.
e1 and e2 are concurrent, and 1 = 1 says nothing.
e2 and e3 are concurrent, and 1 < 2 says nothing either.

The last line is the one to keep: e2 on box 4 has counter 1, e3 on box 3 has counter 2, the counters are ordered and the events are not. A smaller Lamport number is not evidence of anything. You have already met this number twice, by the way, doing one specific job: lesson 032's fencing token and lesson 033's term are Lamport counters used to answer "is this message from a period I have already left", and they work because that question only needs the implication that holds.

To tell concurrent from ordered you have to stop collapsing the counters into one. A vector clock keeps one counter per writer, increments its own, and merges by taking the larger of each position. Compare two vectors element by element: if every entry of A is at least B's and one is strictly larger, A knew about B. If each has an entry larger than the other, they are concurrent and you know it rather than guessing.

Price it for Galewatch before admiring it. Twelve hundred and forty writers at four bytes a counter is about five kilobytes of vector attached to lesson 002's two hundred byte reading, twenty five times the payload, and at six hundred and twenty readings a second that is roughly two hundred and sixty gigabytes a day of bookkeeping against under eleven gigabytes of actual readings. The number is not the reason to refuse, though. A vector clock answers whether two writers touched the same thing without seeing each other, and Galewatch has no two writers touching the same thing: every reading is its own key, written once, never updated. Five kilobytes to detect a conflict that cannot occur. Lesson 058 owns the case where it earns every byte, two copies of one document edited offline, and lesson 087 the case where you have to show the user both.

Buying a usable before

Five tools, and what each one refuses to do.

The physical clock orders everything badly and the logical clock orders some things perfectly. Two mechanisms close that gap from opposite ends.

A hybrid logical clock is a timestamp made of a pair, a physical part lifted from the wall clock and a small logical counter underneath it. On any event, take the larger of your physical part and the current wall clock; if it did not move, bump the counter. On receiving a message, take the larger of the two physical parts and settle ties with the counter. What comes back respects happens-before the way a Lamport counter does, never goes backwards, sorts correctly, and stays close enough to real time that a human reading it recognises the afternoon. CockroachDB runs on these. The price is in the merge rule: one machine whose clock is far ahead drags the whole cluster's stamps forward and they cannot come back, so these systems need a limit past which a badly wrong machine is thrown out rather than followed.

The other end is to stop pretending the clock is exact. Google's Spanner asks for an interval instead of an instant: its TrueTime call returns an earliest and a latest, built on GPS receivers and atomic clocks in its data centres, and the 2012 paper that described it reports an uncertainty of single digit milliseconds. Then comes the move that makes it useful, commit wait: a transaction whose timestamp has to be a real statement about order picks a time, does its work, then waits out the remaining uncertainty before telling anybody it committed. By the time you see the answer, the stamp on it is in the past for every other machine. You can buy a real "before", and the price is the width of your uncertainty, paid in latency on every write.

I am confident about that shape, and I would not quote you an exact bound for any particular deployment, because it depends on the hardware in the room and how often it syncs. Seven milliseconds of uncertainty is a bill you can read. Four seconds of uncertainty is not a design.

So what did Galewatch actually do in June? Three things, and they had to come in this order.

A second column, which is almost free. Every reading now carries received_at, stamped by the ingest box that took it, alongside the recorded_at the turbine wrote. A timestamptz is eight bytes, four percent of that two hundred byte reading and 428 megabytes a day across the fleet. The four ingest boxes sit in one data centre with a time server on the same network and agree with each other to a millisecond or two, which is a thousand times finer than the thing being measured, so for this purpose they count as one clock.

Then the estimator, which is a query over data you now have and the cheapest thing here. The gap between the two columns is the clock offset plus the transit plus any time the reading spent in a turbine's flash, and lesson 003's four hour link drops mean that last term is sometimes four hours. Take the minimum gap per turbine over a day instead of the average. The minimum is the offset plus the smallest transit any reading achieved, transit has a floor near the link's one way delay, and so the minimum gap is the offset plus a few tens of milliseconds. That is NTP's own trick done with data you were storing anyway.

The first week's answers, across twelve hundred and forty turbines: a median offset of four tenths of a second, two point one at the ninety fifth percentile, nine point six at the ninety ninth, and a worst case of forty one seconds on a turbine that had been reporting cheerfully for two years. A dozen of them more than nine and a half seconds out. DM-11's four point two sits between the ninety fifth and the ninety ninth, and that is the finding rather than the forty one seconds: the clock that cost a morning was not even unusual. Two turbines both inside that ninety fifth percentile can still disagree by up to four point two seconds, and the June question lived inside three point one.

That band is what goes on the glass. Lesson 012 argued for putting the staleness number next to the reading rather than hoping, and lesson 023 placed that argument in the vocabulary; the same move works for time. When an engineer asks a panel to order events from different turbines inside the band, show them in time order with the band drawn around them and the word unordered on it. A dashboard that refuses to rank four events is more use than one that ranks them wrongly, and it cost one query and a shaded rectangle.

Stagefront, the ticketing service in this course where a stadium show goes on sale at ten in the morning, escapes all of this by the same route Marlow does. Lesson 015 settled a seat claim inside one short transaction on one machine, so the order of two buyers' clicks is decided by the same thing that decides who gets the seat, exactly as at Marlow. Ask which of two buyers clicked first across two machines and no clock will answer, at any price Stagefront would pay. Lesson 013 said sharding spreads load across data rather than across time; the time version is that keeping one decision in one place is also how you keep its order free.

Recap

A timestamp is a measurement, not a fact about order. Two stamps from two machines can be subtracted to learn which came first only when the gap exceeds the sum of the two clocks' errors. June's gap was two point seven seconds against one clock's error of four point two, so no amount of care downstream could have put the answer there.

NTP gives you a bounded error, not a shared instant. It divides a round trip in half, so its error is half the path's asymmetry and it cannot see it. It corrects by slewing the rate or stepping the value, and a step can go backwards. Clocks seconds out are evidence that nobody has an instrument pointed at them.

The identity of an event should come from a counter, not from a clock. A unique constraint on a timestamp a turbine wrote turns a visible duplicate problem into a silent deletion the first time that clock steps back. A sequence number the writer owns is immune; a digest in the conflict target is the version you can ship this week.

Measure durations on the monotonic clock and stamp events on the wall clock. Lesson 032's lease is broken by a time correction exactly as thoroughly as by a pause, with the extra cruelty that the process writes its logs with the same wrong clock.

Happens-before is the only order you can observe, and everything else is concurrent. Same machine, or a message between them, or a chain of those. A Lamport counter respects it in one direction only: if A happened before B the counter says so, and a smaller counter proves nothing. A vector clock separates concurrent from ordered at one counter per writer. Neither can order two turbines that never exchanged a message, which is why June needed a better physical clock rather than a cleverer logical one.

You can buy a real "before", and the price is the width of your uncertainty, paid in latency on every write. Carry an interval instead of an instant, then wait out the interval before admitting you committed. Seven milliseconds of uncertainty is a seven millisecond bill. Four seconds is a different company.

Check your understanding

1. A colleague proposes ordering events across your fleet by writing created_at from each service's own clock and sorting on it, pointing out that every machine runs a time daemon. Say what you would measure before agreeing, what band you would expect to find, and what you would put in the API response for a client that sorts on that column anyway.

2. Galewatch's interim fix adds a digest of the reading to lesson 019's conflict target. Work out what happens to a turbine that is feathered and reporting identical zeros, say whether the loss matters for this product, and name what you would monitor to find out.

3. A job runner holds a sixty second lease and extends it by comparing now() against the expiry it was given. Describe the two separate ways that comparison can be wrong, say which one your dashboards would show you, and give the code change that removes one of them entirely.

4. Somebody suggests attaching vector clocks to Galewatch readings so the ordering question is settled properly. Give the size arithmetic, then give the stronger argument against it, and name one system in this course where you would attach them without arguing.

5. You are asked to answer "which of these two orders was placed first" across two regions, for a business where the answer decides who gets a refund. Price the commit wait approach against routing both writes to one region, and say what you would need to know about the business before choosing.

6. An engineer shows you a trace where a child span starts before its parent, and concludes the tracing library is broken. Give the more likely explanation, say which clock each timestamp should have come from, and describe what you would change so the question stops arising.

Next lesson

035 Distributed Locks and Their Sharp Edges. Today's clock errors are the ones that make a lock hand the same resource to two holders; next lesson takes the lock apart properly, with the lease, the fence and the clock all now named.