Time, clocks & ordering

Inside every server a quartz crystal vibrates at a nominal frequency and the operating system counts the vibrations. No crystal is exact. Its error, the drift, is quoted in parts per million (ppm): a clock 1 ppm fast gains one microsecond per second, which is 86,400 × 0.000001 = 86.4 ms per day. Ordinary computer crystals are rated at about ±20 to ±100 ppm (1.7 to 8.6 seconds a day), and temperature moves them. The difference between two machines' clocks at one instant is their clock skew.

NTP (Network Time Protocol) corrects this: your machine asks a server with a better source (a GPS receiver or an atomic clock) for the time, estimates the offset from the round trip, and adjusts. How it adjusts depends on how far off you are:

• Under 128 ms: slew. The clock is sped up or slowed by at most 500 ppm, so removing 100 ms takes 100 ÷ 0.5 = 200 s.
• Larger: step. The clock jumps.
• Past 1,000 s: give up. The daemon exits, so a node that "runs NTP" can still be minutes off.

Monitor skew; don't assume it.

Your OS also gives you two clocks. The time-of-day clock (CLOCK_REALTIME, System.currentTimeMillis()) says what time it is and can jump backwards: an NTP step moves it either way, and a positive leap second makes 23:59:59 happen twice. The monotonic clock (CLOCK_MONOTONIC, System.nanoTime()) counts from an arbitrary starting point (usually boot), is only ever slewed, never stepped, and means nothing on another machine. Measure every duration and timeout with it; Failure detection & split brain shows what those timeouts decide.

The jumps are real:

• 30 June 2012. A leap second triggered an operating-system bug that left CPUs spinning. Several large websites and an airline reservation system went down.
• 1 January 2017. A large DNS provider's software subtracted two wall-clock readings, got a negative duration, and crashed; at peak 0.2% of queries failed.

Large cloud providers now smear the leap second over 24 hours, each second about 11.6 µs longer than normal, so nothing jumps. In 2022 the General Conference on Weights and Measures resolved to loosen UTC's tie to the Earth's rotation by 2035, ending leap seconds in practice; the exact rule is still being settled.

The running example: a shopping cart on two replicas, A and B. Each stamps a write with its own wall clock, and for each key both keep the version with the latest timestamp: last write wins (LWW). A's clock is 10 ms ahead of B's, well inside what public NTP delivers. The app adds a book through A and, 8 ms later, having learned the book is out of stock, removes it through B.

The removal was the later event and the caused one: a reaction to the add. It lost because a timestamp records what a clock said, not what happened. This is not a contrived case: last write wins is a common default in replicated databases, and tests of real ones have measured acknowledged writes being lost this way. Equal timestamps are broken by some fixed rule, again not by which came later.

A system cannot know when things happened, but it can know what could have influenced what, because influence travels only inside a process or in a message. That idea is the root of everything that follows.

Happens-before, written a → b, is the smallest relation such that:

• Same node: if a and b are on the same node and a comes first, a → b.
• Message: if a is the sending of a message and b its receipt, a → b.
• Chain: if a → b and b → c, then a → c.

If neither a → b nor b → a, the events are concurrent: not "at the same instant" but unable to have affected each other. Give the cart a third replica, C, and seven events: A adds the book (e1) and replicates it to B, which applies it (e2); C adds socks (e3) and replicates to A (e4); B removes the book (e5) and replicates to C (e6) and A (e7).

Happens-before is a partial order: some pairs are simply unordered, a fact about the system rather than a gap in your knowledge. Which of the possible orders a store lets you observe is the subject of Consistency models.

A Lamport clock is one integer per node, starting at 0, and two rules:

• On every event: add 1 to the counter and stamp the event with it. Every message carries the sender's counter.
• On receiving a message stamped t: set the counter to max(counter, t) + 1 and stamp the receipt with that.

In the cart, a write and the replication message it sends are one event, so the message carries the write's number.

The guarantee is the clock condition: if a → b then L(a) < L(b). Along e1 → e2 → e5 → e6 the stamps read 1, 2, 3, 4. Now the trap: the converse is false. L(e3) = 1 and L(e5) = 3, yet the socks and the removal are concurrent. From L(a) < L(b) you may conclude only that b did not happen before a; whether a influenced b or they were independent, the numbers cannot say. Ties happen too: e1 and e3 are both 1.

You get a total order by comparing the pair (L, node id): the stamp first, then the node's name to break ties. e1 on A precedes e3 on C because A sorts before C. That order is arbitrary for concurrent events but identical on every node, and it never puts an effect before its cause. It is enough to build distributed mutual exclusion, where nodes take turns at a shared resource.

To keep what a single counter throws away, keep one counter per node: a vector clock.

• On every event: node i adds 1 to its own entry, V[i]. Messages carry the whole vector.
• On receiving a message: take the larger of the local and received value in every entry, then add 1 to your own entry.

V(e) records how many events of each node the event e could know about. Same seven events, entries ordered [A, B, C]:

Comparing two vectors tells you how the events are related:

• Before: every entry of V(a) is less than or equal to the matching entry of V(b), and at least one is smaller, written V(a) < V(b). This works in both directions: a → b exactly when V(a) < V(b).
• Concurrent: neither vector is ≤ the other.

Socks against removal: [0,0,1] and [1,2,0]. C's entry is larger on the left, A's and B's on the right: concurrent, and now the clock says so.

This saves the cart. A store that keeps concurrent versions instead of picking one hands both to the app to merge: removal plus socks gives {socks}. With a merge like this an add is never lost, though a deleted item can resurface.

The price is size: one entry per node that ever wrote, growing with the cluster, and it has been proved that nothing smaller captures happens-before in general. Real stores cap the vector and drop its oldest entries.

A version vector has the same shape but counts updates to one data item per replica, not every event on a node. That is what replicated stores usually attach to a value.

Happens-before is a partial order. Lamport stamps with node ids extend it to a total order, one of many possible: any interleaving of the concurrent events is equally valid.

Why want a total order? Because the standard way to replicate a service is the replicated state machine: every replica applies the same commands in the same order, so identical inputs yield identical state. Getting crash-prone nodes to agree on that one order is the consensus problem: Consensus & leader election. And when a partition splits the cluster, no clock lets both halves keep writing without diverging: CAP & PACELC.

Two modern designs put physical time back. A hybrid logical clock stamps each event with a pair (l, c): l is the largest physical time the node has seen, in its own clock or in a message, and c counts events within one l. The rules keep the clock condition, l stays within the clock-synchronization error of real time, and the pair fits in 64 bits. Several distributed SQL databases use it, and they shut a node down when its clock strays too far from the rest of the cluster.

The second design makes the uncertainty explicit. GPS receivers and atomic clocks in every data center let the clock return an interval [earliest, latest] that is guaranteed to contain the true time, a few milliseconds wide. A transaction then waits out that uncertainty before its writes become visible: commit wait. Timestamp order then agrees with real-time order, at the cost of a few milliseconds per commit.