Clocks and Time in Distributed Systems

Why the clocks on different machines disagree, which clock to use for what, how last-write-wins silently loses data, and how Spanner and hybrid logical clocks work with uncertain time.

Overview

Every machine has a clock, and none of them agree exactly. On one machine that rarely matters. Across many machines, code that compares timestamps from different nodes can put events in the wrong order and quietly throw data away.

Two kinds of clock

A computer offers two different clocks, and they answer different questions. The Linux clock_gettime manual describes both.

Answers — What time is it? — How much time has passed?
Linux name — CLOCK_REALTIME — CLOCK_MONOTONIC
Value — Seconds since 1970-01-01 UTC — Seconds since some unspecified point, on Linux since boot
Can jump? — Yes: when set by hand or by NTP — No, though NTP may slow or speed it slightly
Compare across machines? — Roughly, within the sync error — Never: each machine counts from its own start
Use it for — Showing dates to people — Timeouts, durations, rate limits

A time-of-day clock can jump backward, so an elapsed time measured with it can come out negative. Measure durations with the monotonic clock.

Why clocks drift apart

A machine keeps time with a quartz crystal, and no two crystals tick at exactly the same rate. Temperature changes the rate too. So clocks drift apart unless something keeps pulling them back together. That something is usually NTP, the Network Time Protocol, which asks time servers over the network and adjusts the local clock.

NTP is only as good as the network path to its servers. The NTP project says accuracy is on the order of 100 microseconds on a lightly loaded 100 Mb/s Ethernet, and can be several tens of milliseconds over an intercontinental internet path. A misconfigured firewall, an overloaded server or a paused virtual machine can make it much worse, and a node whose NTP stopped working may drift for a long time before anyone notices.

Leap seconds add another trap: some days have 86,401 seconds. Code that assumes every minute has 60 seconds can break. Google avoids the jump by 'smearing' the leap second: from noon to noon UTC around the leap, its time servers run clocks slightly slow, by about 11.6 parts per million, so the extra second is spread over 24 hours.

NTP on a quiet LAN — About 0.1 ms — ntp.org
NTP over an intercontinental path — Up to several tens of ms — ntp.org
Spanner's assumed worst-case drift — 200 microseconds per second — Spanner paper
That drift over one day without sync — About 17 seconds (200 µs × 86,400) — Arithmetic
Google's leap smear rate — About 11.6 ppm for 24 hours — Google Public NTP

Last write wins can lose data

Some databases settle conflicting writes by keeping the one with the highest timestamp. This rule is last write wins (LWW). Cassandra does this per cell, using a timestamp from the client or, if the client sends none, from the coordinator node. Its documentation says its correctness depends on those clocks, and tells you to run NTP.

The danger is that the 'last' write is decided by clocks, not by what really happened. If one node's clock runs ahead, its writes win even when they came first.

No error or warning reports the loss. The fix is not a better clock but a different rule: detect concurrent writes with version vectors and keep both, merge them with a CRDT, or send every write for a key through one leader that orders them.

Treat a clock reading as a range

A time-of-day reading is really 'now, give or take some error'. Most APIs hide the error. Google's TrueTime, used by Spanner, returns it: TT.now() gives an interval, earliest to latest, that is guaranteed to contain the true time. TrueTime is fed by time masters in each data center, most with GPS receivers and some with atomic clocks.

The Spanner paper (OSDI 2012) reports the numbers. Each machine polls the masters every 30 seconds and assumes a worst-case drift of 200 microseconds per second, so the uncertainty grows by up to 6 ms between polls. In production the half-width of the interval, called epsilon, typically rose and fell between about 1 and 7 ms in a sawtooth over each 30-second poll, so its average was about 4 ms most of the time.

Spanner uses the interval with commit wait. It picks a commit timestamp s, then holds the commit back until TT.after(s) is true, meaning the true time is certainly past s. Only then can anyone see the data. So a transaction that starts after this one finishes always gets a larger timestamp. The paper measured commit wait at about 5 ms.

The wait is short only because the interval is small. With plain NTP and tens of milliseconds of uncertainty, every write would wait that long.

Hybrid logical clocks

A hybrid logical clock (HLC), from Kulkarni and others (2014), gets part of the benefit without special hardware. Each timestamp is a pair: l, the largest physical time the node has seen, and c, a counter that breaks ties. Every message carries the pair, and the receiver moves its own l forward to at least the sender's. The result respects cause and effect, like a logical clock, and stays close to real time, like NTP. The paper shows it fits in a 64-bit NTP timestamp.

HLC still needs clocks to stay close. CockroachDB, which uses HLC timestamps, has a --max-offset setting with a default of 500 ms. If a node's clock offset goes past the limit, the node crashes rather than risk returning inconsistent data.

Time-of-day timestamps — NTP — Rough order only; LWW can drop writes
Lamport or vector clocks — Nothing — Causal order, but no link to real time
Hybrid logical clock — NTP within a bound — Causal order, close to real time
TrueTime — GPS and atomic clocks — Real-time order, with a short commit wait

Safe and unsafe uses of time

Timeout or duration on one machine — Yes, with the monotonic clock — No other clock is involved
Showing a date to a user — Yes — A few ms of error does not matter
Ordering writes from different nodes — No — Clock error can reverse the order
A lease that says 'valid until 12:00:05' — Risky — The holder's clock may be off, or the process may pause past the deadline

For leases, a paused process is as dangerous as a wrong clock: it can wake up after its lease ended and act as if it still holds it. The chapter on faults and partial failures shows how fencing tokens guard against this.

What you will be able to do

Pick the right clock for durations, timestamps and user-facing dates.
Explain how clock skew makes last write wins drop writes silently.
Explain TrueTime intervals and why Spanner waits before a commit is visible.
Describe what a hybrid logical clock adds, and the clock bound it still needs.

Key concepts

Time-of-day clock: The wall clock: seconds since 1970 UTC. It can be set and can jump backward, so it is poor for durations and for ordering across machines.
Monotonic clock: A counter that only moves forward from an arbitrary start. Right for durations on one machine; meaningless across machines.
Clock skew: The difference between two clocks at the same moment. NTP shrinks it but never removes it.
NTP: The Network Time Protocol. Syncs a clock from time servers; accuracy depends on the network path, from about 0.1 ms on a quiet LAN to tens of ms across continents.
Last write wins (LWW): Keeping the write with the highest timestamp. Simple, but a node with a fast clock can silently override newer writes.
TrueTime: Google's clock API that returns an interval guaranteed to contain the true time. Spanner waits out the interval before a commit is visible.
Commit wait: Spanner's rule of holding a commit until its timestamp has certainly passed, so later transactions always get larger timestamps.
Hybrid logical clock (HLC): A timestamp of physical time plus a counter. It follows cause and effect and stays close to real time, as long as clocks stay within a set bound.

When to use it

Explaining why last write wins with wall-clock timestamps can lose data
Choosing how to measure timeouts, durations and rate limits
Discussing how Spanner or CockroachDB order transactions across machines
Reviewing a design that relies on leases or expiry times

Interview questions

Why is last write wins with wall-clock timestamps dangerous?
Which clock should you use to measure a timeout, and why?
How does Spanner use TrueTime to order transactions?
What is a hybrid logical clock, and what does it still need?
Why is a lease with an expiry time risky?