Time and clocks

Two support agents fix the same customer's delivery address, 30 milliseconds apart. The first types "MG Road". The second, who has just spoken to the customer, types "Indiranagar". Their requests land on two different servers, and the database keeps whichever write has the later timestamp. The second server's clock happens to be 80 ms slow. The parcel goes to MG Road, the old address, and no log anywhere shows an error.

Nothing crashed. Two clocks disagreed, and the system trusted one of them.

Every machine has two clocks#

Your operating system gives you two different clocks, and they answer different questions.

The wall clock (time of day) answers "what time is it?" It is what Date.now() in JavaScript and time.time() in Python read. It is kept in step with the outside world by NTP, the network time protocol, which nudges it every few minutes. Nudging means it can jump: forward, or backward, by a few milliseconds or by much more if it was badly off.

The monotonic clock answers "how much time has passed?" It only ever moves forward, it is not adjusted to match anyone else, and its actual value means nothing (often "time since boot"). You cannot compare it across two machines. You can measure a duration with it safely.

// Wrong: if NTP steps the wall clock back during the call, tookMs can be negative.
const start = Date.now()
await callPaymentGateway()
const tookMs = Date.now() - start
 
// Right: performance.now() is monotonic, so a duration can never go backwards.
const t0 = performance.now()
await callPaymentGateway()
const took = performance.now() - t0

Timeouts, latency metrics and "has this lease run out yet" all belong on the monotonic clock. The wall clock is for showing a time to a human, or for logs.

How wrong a clock can be#

A computer's clock is a quartz crystal, and quartz drifts with temperature and age. Google's Spanner paper plans for a worst case of 200 microseconds per second. That sounds tiny, and it is 17 seconds a day if nothing corrects it.

NTP corrects it, as well as the network lets it. Syncing over the public internet typically keeps a server within a few to tens of milliseconds. Syncing to your cloud provider's time service inside the same region usually gets well under a millisecond. Then there are the jumps: a VM paused while it moves hosts and waking up seconds behind, a misconfigured NTP server, a leap second, an engineer setting the clock by hand.

So the rule is: two timestamps from two machines can be ordered wrongly by however far apart their clocks are, and you do not know that distance. Usually it is milliseconds. Sometimes it is not.

When timestamps decide who wins#

Plenty of real databases settle conflicting writes by keeping the one with the higher timestamp. It is called last write wins, or LWW. Cassandra does it for every column, and DynamoDB global tables do it when two regions write the same item. It is simple and needs no coordination, and it means clock skew can silently throw away a write. Try it, then switch the ordering rule.

With a wall clock, the only thing that matters is whether the skew is bigger than the gap. Two writes 30 ms apart are safe with 10 ms of skew and wrong with 80. With the two logical clocks, the skew slider stops doing anything at all, because they do not read the time.

Lamport clocks: order without time#

In 1978 Leslie Lamport pointed out that you rarely need to know when something happened. You need to know what could have caused what. He defined happened before: event a happened before event b if they ran on the same machine in that order, or if a was sending a message and b was receiving it, or through any chain of those.

A Lamport clock is a single counter per machine that respects that order:

class LamportClock {
  private counter = 0
 
  // Before any local event, including sending a message: count up.
  tick(): number {
    this.counter += 1
    return this.counter
  }
 
  // On receiving a message stamped `remote`: jump past it.
  receive(remote: number): number {
    this.counter = Math.max(this.counter, remote) + 1
    return this.counter
  }
}

The guarantee: if a happened before b, then a's number is smaller than b's. Break ties with the machine's id, written as (5, A), and every event in the system gets a single total order that never contradicts cause and effect.

The guarantee only goes one way. A smaller number does not mean "happened before". It might mean "happened at the same time on a quieter machine". That is the limitation you saw in the widget: Lamport clocks order concurrent writes consistently, but arbitrarily, and they cannot tell you a conflict happened.

Vector clocks: noticing that two writes were concurrent#

A vector clock keeps one counter per machine instead of one counter in total. Each machine counts its own events in its own slot, and when it receives a message it takes the larger of each slot.

Comparing two vector clocks gives one of three answers:

Before: every slot in the first is less than or equal to the second, and at least one is smaller. {A:1, B:0} is before {A:1, B:1}. The second write saw the first, so it can safely replace it.

After: the same, the other way round.

Concurrent: each has a slot bigger than the other. {A:1, B:0} and {A:0, B:1}. Neither write saw the other, so neither should silently win.

That third answer is what Lamport clocks cannot give you. Amazon's Dynamo, described in a 2007 paper, used vector clocks for its shopping cart: when two versions of a cart were concurrent, it returned both to the application, which merged them by taking the union of the items. (The known cost: an item you deleted could reappear after a merge.) Riak worked the same way.

The price is size. A vector clock has a slot for every machine that ever wrote the value, so systems with many writers trim old slots, which reintroduces some guessing. This is also why most databases you will actually use pick LWW: it is simpler, and they decided the lost writes were acceptable. Know which one your database picked.

Hybrid logical clocks#

What if you want timestamps that look like real time, so you can ask for "the data as of 10:00:00", and that also never contradict cause and effect? A hybrid logical clock (HLC) stores two parts: the largest wall clock time this machine has seen (from its own clock or from any message), and a small counter for events that share that time. Like a Lamport clock, it jumps past any stamp it receives. Unlike one, it stays within the clock skew of real time.

CockroachDB and YugabyteDB stamp every transaction this way, and MongoDB's cluster time works the same way. HLC does not make skew disappear. It means skew can only reorder events that were truly concurrent, never an event and its cause. CockroachDB adds a guard: a node whose clock drifts too far from the rest of the cluster shuts itself down rather than risk ordering writes wrongly.

TrueTime: measuring your own uncertainty#

Google took the opposite approach with Spanner: make the clock error small and know how big it is. Every data centre has GPS receivers and atomic clocks, and the TrueTime API does not return a time. It returns an interval, "it is now somewhere between 10:00:00.003 and 10:00:00.009". The 2012 paper reports that the error either side of the reading usually stayed between about 1 and 7 ms.

Then Spanner does something that sounds wasteful and is brilliant: after picking a commit timestamp, it waits until the uncertainty has passed before telling the client the write is done. Any transaction that starts after that moment is guaranteed to get a later timestamp, on any machine, anywhere in the world. A few milliseconds of waiting buys global ordering without machines having to talk to each other. The full design is in Design a global database.

Checkpoint#