Time and Ordering: Why a Timestamp Can’t Tell You What Happened First

This laptop’s clock, kept in sync by NTP, was tens of milliseconds off, and 187 ms off after a sleep. We measured what a gap like that does to a database that keeps the last write, then built the clocks that fix it: Lamport, vector, hybrid, TrueTime.

Every event in a program gets a time. Log lines have one, rows have one, and messages have one. It’s tempting to sort by those times and call the result “what happened”. On one machine that mostly works. Across machines it doesn’t, because each machine has its own clock and no two agree.

This part measures how far apart real clocks are, and what the gap does to a real database. Then it builds the clocks that distributed systems use instead: Lamport clocks, vector clocks and hybrid logical clocks. Last, it covers Google’s TrueTime, which doesn’t pretend the gap is zero.

Try this first

Two app servers share one database table. The database resolves conflicts by keeping the write with the latest timestamp, and each server stamps its writes with its own clock.

Server A writes "A" to a row. Server B reads the row, sees "A", and 50 ms later writes "B". The database acknowledges both writes.

Which value is in the row now?

1. "B", because it was written last.
2. "A", sometimes.
3. It depends on something the question hasn’t told you.

Write down your answer. The measured answer is below, against Cassandra. It depends on how far apart the two servers’ clocks are. The lab sets that gap on purpose, and one of the gaps it tries is about what this laptop’s own clock turned out to be.

How far off is a clock that NTP keeps in sync?

The laptop this series is written on keeps its clock in sync with systemd-timesyncd, a small NTP client. We asked six public time servers how far off its clock was, 30 times each, over about a minute. The script only asks. It never sets the clock.

Each question is one NTP exchange with four timestamps. The client notes when it sent the request (T1). The server notes when the request arrived (T2) and when it sent the reply (T3). The client notes when the reply arrived (T4). RFC 5905 gives the offset and the round-trip delay:

theta = T(B) - T(A) = 1/2 * [(T2-T1) + (T3-T4)]
delta = T(ABA) = (T4-T1) - (T3-T2).

The offset formula averages the two directions. It’s exact only if the request and the reply took equally long. If the whole round trip went one way, the estimate would be wrong by half the round trip. So each reply gives an estimate and an error bar: the offset, plus or minus half the delay.

Here’s what came back.

• Nearby servers agree. Cloudflare’s first reply came back in 14.0 ms and said this clock was 71.1 ms behind, give or take 7.0 ms. Windows said 75.9 ms, give or take 7.8, and Apple 72.5 ms, give or take 7.1.
• Far servers can’t be sure. The first reply from ntp.ubuntu.com said the clock was 5.7 ms ahead. Its round trip was 375.7 ms, so its own bar was ±187.8 ms. That’s not wrong. It’s just not much use.
• The best reply from each server is the one with the shortest round trip. For Cloudflare, Windows and Apple, the best replies said 70.2 to 73.6 ms behind, each give or take 5.3 ms or less.
• All 180 bars overlap in one range, 73.3 to 74.6 ms. Every reply is consistent with this clock being about 74 ms behind those servers. Don’t read that narrow range as the precision, though. Two replies set its two ends. It assumes every server is exactly right, and that this clock held still for the minute, which it didn’t quite, as we’ll see. Roughly 70 to 75 ms behind is the honest reading.

That last step is the idea behind NTP’s own selection algorithm: don’t trust any one reply, find where they overlap. RFC 5905 says the selection algorithm “operates to find an intersection interval containing a majority clique of truechimers”, after Marzullo. The real algorithm also accounts for each server’s own distance from its reference clock, which our bars leave out.

Now look at the server this laptop actually syncs to. It’s ntp.ubuntu.com, over IPv6. (Our probe reached it over IPv4, with round trips of 136 to 376 ms.) timedatectl timesync-status reported an offset of -40.923 ms, a delay of 241.207 ms and a jitter of 101.865 ms. So the daemon thought this clock was about 41 ms ahead, while the nearby servers put it about 74 ms behind. Both fit inside the bar a 241 ms round trip allows, about ±120 ms. The daemon was doing its job. It just had a poor view, and it was steering the clock by it.

What NTP promises

The folklore says NTP keeps clocks within a millisecond. RFC 5905 says something more careful. Its abstract claims “potential accuracy to the tens of microseconds with modern workstations and fast LANs”. The body is plainer:

Typical secondary servers and clients on fast LANs are within a few hundred microseconds with poll intervals up to 1024 seconds, which was the maximum with NTPv3. With NTPv4, servers and clients are precise within a few tens of milliseconds with poll intervals up to 36 hours.

The conditions matter. Hundreds of microseconds is for “fast LANs”. A few tens of milliseconds is for a client that polls as rarely as once every 36 hours. Over the public internet, the round trip sets the limit, and asymmetry hides inside it. chrony’s FAQ puts it bluntly: “Even if the measured offset of the clock is stable to nanoseconds, it could be off by milliseconds due to asymmetric network delay”.

Inside a cloud region, it can be much better. In 2023 AWS said its time service would “typically” give “a clock error bound of under 100us using the NTP connection”, and under 40 µs with a hardware clock. Note the word “typically”: that’s AWS’s description of its service, not a guarantee.

Two clocks, one table: last write wins

Now the question from the start. Cassandra doesn’t use version numbers to decide which of two writes to keep. Its documentation says so:

Cassandra uses a simpler last-write-wins model where every mutation is timestamped (including deletes) and then the latest version of data is the “winning” value.

The timestamp comes from “either from a client clock or, absent a client-provided timestamp, from the coordinator node’s clock.” And the Go driver sends one by default. Its DefaultTimestamp option is true, and the value it sends is time.Now().UnixNano() / 1000, the client’s own clock in microseconds.

So we ran the question from the start against Cassandra 5.0.9. Two app servers, A and B, each with its own connection. A writes. B reads the row and sees A’s value, waits, then writes its own. B’s write comes after A’s in real time, and it was made knowing A’s value. Then we read the row back.

We can’t move this laptop’s clock without moving everything on it. So A’s fast clock is modelled where the driver reads it: A’s writes carry WithTimestamp(now + skew), the value the driver would send from a machine whose clock read that far ahead. B’s writes carry exactly what the driver sends by default, time.Now().UnixNano() / 1000. We compute it ourselves only so the lab can record it.

We tried skews of 0, 1, 10, 70 and 500 ms. The 70 ms is about what this laptop’s clock measured, over a poor sync path. Servers synced over a short path inside one data center are usually far closer: AWS quotes a typical bound under 100 µs. So read 70 ms as a bad day, and watch the 10 ms row too.

• With both clocks right, nothing was lost. 140 handoffs, 140 of B’s writes kept.
• With A 70 ms fast, B’s write was lost whenever it was sent less than 70 ms after A’s. When B waited 0, 5 or 50 ms, all 20 of its writes were lost. When B waited 65 ms, its writes went 69.4 to 71.1 ms after A’s, and the 6 sent before the 70 ms mark were lost. The last one lost was sent 69.92 ms after A’s, and the first one kept 70.19 ms after. From a 100 ms wait on, none were lost.
• Every lost write was acknowledged. Cassandra returned success to B each time.
• Cassandra did exactly what its documentation says. In all 700 handoffs, the value left in the row carried the larger of the two timestamps. That’s the definition of last write wins. What the lab adds is what that means when one of the timestamps comes from a fast clock.

The skew doesn’t have to be large. With A just 10 ms fast and B waiting 5 ms, B’s writes went 9.8 to 11.5 ms after A’s. The 3 sent within 10 ms were lost, and the 17 sent later were kept.

With A 1 ms fast, nothing was lost, but only because B’s write never went within 1 ms of A’s. The closest was 3.7 ms, about as long as A’s write and B’s read took together.

Now make it a counter. A and B take turns reading a number, adding one, and writing it back, 20 ms apart. That’s 400 increments, and every write was acknowledged.

A’s clock	Increments acknowledged	Counter at the end
right	400	400
1 ms fast	400	400
10 ms fast	400	400
70 ms fast	400	200
500 ms fast	400	200

With turns 20 ms apart, only a skew of more than 20 ms can lose an increment, which is why the 10 ms row is clean. The handoffs above lost writes at 10 ms when they came closer together.

At 70 ms, every one of B’s 200 increments vanished. B always read A’s latest value, added one, and wrote a result that lost to A’s older timestamp. Nothing failed. The number was just half what it should have been.

This isn’t a Cassandra bug. The docs say “Cassandra’s correctness does depend on these clocks, so make sure a proper time synchronization process is running such as NTP.” Jepsen found the same in ScyllaDB, which uses the same model: “even skews as small as one second resulted in lost updates”, and “This behavior turned out not to be a bug; it is, in fact, documented behavior.” DynamoDB global tables, in their default mode (MREC), resolve concurrent writes across Regions the same way, “using the modification with the latest internal timestamp”, a method it calls “last writer wins”.

Two fixes, and their limits

Carry the timestamp you read. B’s read returned A’s value and A’s timestamp. If B stamps its write with the later of its own clock and A’s timestamp plus one microsecond, its write sorts after A’s, however fast A’s clock is.

We ran all 700 handoffs again with that one change, and B’s write was kept every time, at every skew and every wait. We ran the counter that way too, each write carrying past the timestamp its read returned, and it reached 400 at every skew.

That’s the rule Lamport clocks are built on, below: when you receive a timestamp, move past it. It has two limits. It only helps a write that read what it overwrites; two clients that read the same value and both write still race, and one of them loses. And B’s write now carries A’s fast time, so skew spreads through causality instead of being corrected.

Compare, don’t timestamp. A Cassandra lightweight transaction writes only if a condition holds: UPDATE kv SET v = ? WHERE k = ? IF v = ?. We ran the same counter that way.

• The counter reached 400 at every skew, even with A 500 ms fast.
• The conditional writes weren’t stamped with the client’s clock. We sent one with a client timestamp an hour in the future. Cassandra ignored it: the stored timestamp was within 0.1 s of the time we read it back. A plain insert with the same timestamp stored it as sent, an hour ahead.
• CQL won’t even let you try it in the statement: USING TIMESTAMP on a conditional update fails with Cannot provide custom timestamp for conditional updates.

None of the conditional writes was refused, because A and B took turns and never raced. So the compare did no work here. The counter survived because the server stamped the conditional writes, not the client. Refusing the loser of a race is the lost-update protection from Part 19, but this lab didn’t make A and B race.

This fix has limits too. We ran one Cassandra node, so a cluster with several coordinators wasn’t tested. And every write to the row has to be conditional. We had A write a row with a plain write, 70 ms fast, then had B update it conditionally, IF v = 'A'. Cassandra said the update was applied, 20 times out of 20, and B’s value was visible 0 times out of 20. B wrote right after A, so its write must have carried the server’s stamp, older than A’s fast client stamp. With A 500 ms fast, the same.

Your clock can go backwards

Clocks don’t only disagree with each other. One clock can also jump.

NTP clients fix small errors by slewing: running the clock slightly fast or slow until it catches up. They fix large errors by stepping: setting the clock to a new value at once. systemd-timesyncd slews offsets under 0.4 s and steps anything larger. RFC 5905’s threshold is 125 ms in the text, though its reference code says .128. A step can go backwards.

Leap seconds are the other source of jumps. By default, chrony says, “the kernel steps the system clock backwards by one second when the clock gets to 00:00:00 UTC.” Google and AWS avoid that by smearing the extra second across a day instead. Google’s standard is “a 24-hour linear smear from noon to noon UTC”, about 11.6 ppm. The price: during Google’s smear, a smeared clock is up to about half a second from an unsmeared one, and RFC 8633 says smeared clients may be off UTC “by as much as a full second, depending on the implementation”. Both Google and AWS tell you not to mix the two.

On 1 January 2017, a leap second took down part of Cloudflare’s DNS. Their post-mortem is short and worth reading:

At midnight UTC on New Year’s Day, deep inside Cloudflare’s custom RRDNS software, a number went negative when it should always have been, at worst, zero.

The code computed a duration by subtracting two wall-clock times. When the clock stepped back, the duration went negative, and “rand.Int63n promptly panics if its argument is negative.” At peak, about 0.2% of Cloudflare’s DNS queries were affected. The root cause, in their words, was “the belief that time cannot go backwards.”

Leap seconds are on their way out. In 2022 the General Conference on Weights and Measures decided that “the maximum value for the difference (UT1-UTC) will be increased in, or before, 2035”. It also noted that leap seconds “risk causing serious malfunctions in critical digital infrastructure”. Clock steps from NTP aren’t going anywhere, though.

Use the monotonic clock for durations

Operating systems give you two kinds of clock. Linux’s CLOCK_REALTIME is wall-clock time and “is affected by discontinuous jumps in the system time”. CLOCK_MONOTONIC “is not affected by discontinuous jumps”, and consecutive reads “will not go backwards”.

Every mainstream runtime exposes both. Go’s documentation has the rule in one sentence: “the wall clock is for telling time and the monotonic clock is for measuring time.”

Language	Wall clock (for telling time)	Monotonic (for measuring time)
Go	time.Now(), wall part	time.Now(), monotonic part, used by t.Sub, time.Since
Java	System.currentTimeMillis()	System.nanoTime()
C#	DateTime.UtcNow	Stopwatch
Rust	SystemTime::now()	Instant::now()

A few details matter.

• Go added this in 1.9. Since then, time.Now() carries both readings, and subtracting two Time values uses the monotonic one. That’s what Cloudflare’s code lacked in 2017. The monotonic reading is dropped when you serialise a Time, because it “has no meaning outside the current process”.
• Java’s nanoTime “can only be used to measure elapsed time and is not related to any other notion of system or wall-clock time.” Its values mean something only as a difference within one JVM.
• Rust’s SystemTime says outright that “an operation that happens after another operation in real time may have an earlier SystemTime!”, and duration_since returns a Result for that reason. Instant never goes backwards but isn’t guaranteed steady.
• .NET’s documentation gives a different reason. It tells you to prefer Stopwatch over DateTime.Now for timing because of resolution, “between 0.5 and 15 milliseconds”. The Windows counter behind Stopwatch is also “completely independent of the system time and UTC”, so it’s the right choice for both reasons.

One laptop’s clock, for 100 minutes

To watch a clock being corrected, we pointed the same probe at Cloudflare’s time server for 100 minutes, a burst of four queries about every 10 seconds, keeping the best reply of each burst. Alongside it, clocks_probe.py read three Linux clocks every 5 seconds: CLOCK_REALTIME, CLOCK_MONOTONIC, and CLOCK_MONOTONIC_RAW, which the man page describes as “a raw hardware-based time that is not subject to frequency adjustments.” Neither script sets anything.

Partway through, the laptop went to sleep. We didn’t plan that, and it turned out to be the most useful part of the run.

• Before the sleep, the clock’s rate was being adjusted. Against the raw hardware counter, CLOCK_MONOTONIC ran 12 ppm slow for the first two minutes or so. Then timesyncd took a sample, and the clock ran fast, by up to 2.1 ms a minute, easing off as the kernel worked through the correction. The gap to Cloudflare narrowed from 72 to 60 ms. The kernel was steering toward timesyncd’s estimate, 22 ms behind, not toward what the nearby servers saw. The six-server sweep ran just before this. If the clock was drifting at the same 0.7 ms a minute then, that alone is reason not to read the overlap above to the millisecond.
• The laptop slept for 24.7 minutes. Between the two readings either side of the sleep, CLOCK_REALTIME moved 1,488 s and CLOCK_MONOTONIC moved 5 s, the time the machine was awake between them. The man page says CLOCK_MONOTONIC “does not count time that the system is suspended”, and it didn’t. A timeout or a lease measured with it would have missed the whole sleep. The kernel’s count of suspends since boot (one) and a 1,484-second silence in the journal confirm it.
• It woke 187 ms behind. Before the sleep it had been 60 ms behind, so the sleep itself added about 127 ms of error.
• timesyncd’s next sample came one poll interval after waking. At wake its status switched to another of ntp.ubuntu.com‘s addresses, but no new sample arrived, and its status kept showing the last one from before the sleep, an offset of +22.034 ms. The correction began 34 minutes after waking, about one full poll interval (34 min 8 s).
• Then the kernel slewed hard. timesyncd’s sample said 144 ms behind, and the kernel worked most of that off at once. The clock gained 159 ms on the raw counter in 40 seconds, 68 ms of it in a single 5-second stretch. Over that stretch CLOCK_MONOTONIC ran 1.4% fast, so 5 seconds measured about 5.07. timesyncd’s status also showed the kernel’s frequency correction at +500 ppm, the cap on frequency that RFC 5905’s reference code sets. That cap limits only the frequency term. Once the offset was used up, the frequency alone kept adding about 2.5 ms every 5 seconds. The next sample said 1 ms behind and left the frequency where it was. The one after said 66 ms ahead, and that finally pulled the other way. In all, the clock gained 189 ms in 100 seconds and overshot: Cloudflare saw it 1 ms ahead. CLOCK_REALTIME minus CLOCK_MONOTONIC never moved by more than 0.04 ms, so nothing stepped the clock: this was all slewing.
• After that, it swung. For the last 23 minutes, the clock was between 7 and 90 ms behind. timesyncd’s samples read −66, +40, −27, −63, +51 and −37 ms, with round trips of 196 to 271 ms. That’s consistent with noise from a path that long, and the kernel’s frequency correction moved after every one. Five-second intervals on CLOCK_MONOTONIC came out as much as 0.29% short and 0.12% long.

So the monotonic clock never went backwards, exactly as promised. But it stopped while the machine slept, and its rate was adjusted while it ran. For a duration that must include sleep, Linux has CLOCK_BOOTTIME, “identical to CLOCK_MONOTONIC, except that it also includes any time that the system is suspended.” Go’s documentation warns about the same thing: “On some systems the monotonic clock will stop if the computer goes to sleep.”

A monotonic clock solves durations on one machine, with the catch just measured: on Linux it doesn’t count time the machine spends asleep. It can’t order events across machines at all. Its starting point is arbitrary, and Go’s documentation says its reading “has no meaning outside the current process”. For that we need a different kind of clock.

Happened-before

In 1978 Leslie Lamport published Time, Clocks, and the Ordering of Events in a Distributed System. Its first move is to stop asking what time something happened. It asks what could have affected what.

In a distributed system, it is sometimes impossible to say that one of two events occurred first. The relation “happened before” is therefore only a partial ordering of the events in the system.

Event a happened before event b, written a → b, if one of these holds:

1. a and b are on the same process, and a comes first.
2. a is sending a message and b is receiving that message.
3. There’s some c with a → c and c → b.

If neither a → b nor b → a, the events are concurrent. That doesn’t mean they happened at the same instant. It means neither could have affected the other. In Lamport’s gloss, a → b “means that it is possible for event a to causally affect event b.”

The definition uses no clocks at all. That’s the point. Happened-before is the order that actually matters for correctness. In the Cassandra test, A’s write → B’s read → B’s write, so A’s write happened before B’s. The clients’ wall-clock timestamps put them the other way round, and the database believed them.

The figure below stamps the same six events four ways. Three nodes: P’s clock is right, Q’s is 70 ms slow (about what this laptop measured), and R’s is 3 ms fast. P writes and sends a message to Q. R writes something that has nothing to do with it. Q receives P’s message and tells R.

With wall clocks, Q’s receipt is stamped 945 and P’s send 1010. Sort by timestamp and Q heard the news 65 ms before P sent it. The rest of this part is about clocks that can’t do that.

Lamport clocks

A Lamport clock is a counter per process, with two rules. In the paper they’re IR1 and IR2.

1. Tick. Each process “increments Ci between any two successive events.”
2. Carry. Every message carries the sender’s counter. On receipt, the receiver sets its counter “greater than or equal to its present value and greater than” the one in the message.

In code:

class LamportClock:
    def __init__(self):
        self.t = 0

    def local_event(self):
        self.t += 1
        return self.t

    def send(self):
        self.t += 1
        return self.t          # attach this to the message

    def receive(self, msg_t):
        self.t = max(self.t, msg_t) + 1
        return self.t

That’s all it takes to satisfy Lamport’s Clock Condition: if a → b, then C(a) < C(b). A cause always has a smaller number than its effect. In the figure, P’s send is 2 and Q’s receipt is 3, whatever Q’s wall clock says. clocks.py checked the Clock Condition on 1,670,928 causally ordered pairs of events across 300 random traces. It held on every one, and it failed as soon as we removed the carry rule.

To get a total order, sort by counter and break ties by process ID: “we use any arbitrary total ordering < of the processes.” That’s useful when everyone must agree on one order, and it matters less which order.

What Lamport clocks can’t tell you

The converse is false. C(a) < C(b) does not mean a → b. Lamport says so in the paper:

Note that we cannot expect the converse condition to hold as well, since that would imply that any two concurrent events must occur at the same time.

In the figure, R’s write gets 1 and P’s send gets 2. The numbers say R’s write came first. In fact they’re concurrent: neither could have affected the other. And in real time, R’s write came 2 ms after P’s send.

Friedemann Mattern named the cost in 1988: mapping a partial order onto integers “is losing information”. Given two Lamport timestamps, “it is not possible to decide” whether the events are causally related. So a Lamport clock can’t detect a conflict. If two writes to the same key come from concurrent events, their Lamport timestamps still order them, and one of them silently wins.

Lamport also named the anomaly that remains. A person issues request A, then phones a friend, who issues request B on another computer. B can get a lower timestamp than A, because “that precedence […] is based on messages external to the system.” The phone call is a message the clocks never saw.

Vector clocks

To detect concurrency, keep one counter per node instead of one per process’s own events. Colin Fidge and Friedemann Mattern published this independently in 1988.

• Each node keeps a vector of n counters, one per node.
• On every event, a node increments its own entry.
• Every message carries the whole vector.
• On receipt, the receiver takes the element-wise maximum, then increments its own entry.

Compare two vectors entry by entry. V(a) < V(b) if every entry of a is less than or equal to the matching entry of b, and at least one is smaller. Then:

• a → b if and only if V(a) < V(b).
• If neither vector is less than the other, the events are concurrent.

In the figure, R’s write is [0,0,1] and P’s send is [2,0,0]. Each is bigger somewhere, so neither came first. That’s exactly right, and a Lamport clock can’t say it. clocks.py checked the “if and only if” on every pair of events in the 300 traces, and it held on all of them.

This is what Amazon’s Dynamo used to find conflicting versions. “Dynamo uses vector clocks [12] in order to capture causality between different versions of the same object.” If one version’s clock is less than or equal to the other’s on every node, it’s an ancestor “and can be forgotten”. Otherwise “the two changes are considered to be in conflict and require reconciliation.”

Three things about Dynamo get retold wrongly.

1. The vector clocks detected conflicts. They didn’t resolve them. Resolution was the application’s job, like merging two shopping carts. When the store did resolve a conflict itself, it used “last write wins”, which means “the object with the largest physical timestamp value is chosen.”
2. The vectors were truncated. When a vector reached a threshold, “say 10”, Dynamo dropped the oldest pair. The paper admits this “can lead to inefficiencies in reconciliation”, and says the problem “has not surfaced in production and therefore this issue has not been thoroughly investigated.”
3. DynamoDB, the AWS service, uses last-writer-wins for global tables in their default mode, on “the latest internal timestamp”. Its documentation doesn’t mention vector clocks.

The cost of a vector clock is its size. It grows with the number of nodes, and every message carries it. The HLC paper calls that space requirement “prohibitive” for large systems. That’s why most databases don’t put a vector clock on every write.

Hybrid logical clocks

A hybrid logical clock (HLC), from Kulkarni and colleagues in 2014, wants three things at once. It wants Lamport’s guarantee that a cause is stamped before its effect, a fixed size, and a value that stays close to real time so people can read it.

Each stamp is a pair (l, c): l is a clock value and c is a counter.

• On a local event or a send: l becomes the larger of its old value and the physical clock. If l didn’t change, c goes up by one. Otherwise c resets to 0.
• On a receipt: l becomes the largest of its old value, the message’s l and the physical clock. c then goes up past whichever counters share that l, or resets to 0 if the physical clock won.

Stamps compare by l first, then c. The paper proves the guarantees that matter:

• Theorem 1: if e → f, then (l, c)(e) < (l, c)(f). That’s Lamport’s guarantee.
• Theorem 2: l is never behind the local physical clock.
• Corollary 1: l is never more than ε ahead of it, where ε bounds how far apart any two clocks are.

In the figure, Q’s receipt is stamped (1010,1): P’s clock value, carried by the message, plus a counter. Q’s own clock read 945. So the stamp sorts after the send, and it’s still within the skew of real time. clocks.py checked all three guarantees on the 300 traces, with clocks up to 10 ms apart. None failed. The furthest any l ran ahead of its own node’s clock was 8.9 ms, and the largest counter was 6.

HLC doesn’t make concurrent events distinguishable. It has the same blind spot as a Lamport clock. What it adds is a timestamp that’s also a readable time, in 64 bits.

CockroachDB: HLC plus a clock bound

CockroachDB stamps every transaction with an HLC. Its documentation: “HLC time is always greater than or equal to the wall time”, and “Whenever a transaction’s timestamp is mentioned, it’s an HLC value.”

HLC keeps causally linked events in order. But two transactions that never exchanged a message can still be misordered by skew. So CockroachDB also assumes a maximum clock offset, --max-offset, “Default: 500ms”. It uses that bound to decide when a value might be newer than a read’s timestamp, and restarts the read if so. If a node finds its clock out of sync with at least half of the other nodes by 80% of that bound, it shuts down. The flag’s own description: “servers will crash to minimize the likelihood of reading inconsistent data.” Its documentation is precise about what skew costs: under SERIALIZABLE isolation, serializability holds regardless of clock skew, but skew outside the configured bounds “can result in violations of single-key linearizability between causally dependent transactions.” Jepsen’s 2017 analysis of a 2016 beta, when the default bound was 250 ms, went further: beyond the bound, “all bets are off”.

TrueTime: a clock that admits its error

Google’s Spanner takes the opposite approach. It doesn’t hide clock uncertainty; it measures it and waits it out.

TrueTime’s TT.now() doesn’t return a time. It returns an interval “that is guaranteed to contain the absolute time during which TT.now() was invoked.” Google keeps the interval small with GPS receivers and atomic clocks. In the 2012 paper, the uncertainty ε was “typically a sawtooth function of time, varying from about 1 to 7 ms over each poll interval”, and its average was 4 ms most of the time.

Then Spanner uses commit wait. It picks a commit timestamp at the late end of the interval, then waits until that timestamp is certainly in the past before anyone can see the write. The expected wait is at least twice that average uncertainty. In the paper’s measurements, “commit wait is about 5ms”. After the wait, any transaction that starts later is guaranteed a larger timestamp. Timestamp order matches real-time order, across the whole planet.

TrueTime doesn’t make the uncertainty zero. Eric Brewer describes it as “a global synchronized clock with bounded non-zero error”. A node cut off from the time masters sees its interval “slowly grow wider over time”, and Spanner has to wait longer. The trick isn’t a perfect clock. It’s a clock that knows how imperfect it is, and a database that pays for the uncertainty in latency instead of in wrong answers.

Those figures are from 2012. Google’s current Spanner documentation describes the guarantee but gives no figure for ε. AWS offers a similar interface today: its ClockBound library returns a window “(earliest, latest) within which true time exists”.

All five compare like this:

	Keeps cause before effect	Detects concurrency	Close to real time	Size
Wall clock	no	no	yes	one number
Lamport clock	yes	no	no	one number
Vector clock	yes	yes	no	one number per node
HLC	yes	no	yes, within the skew	two numbers
TrueTime	yes, by waiting	no	yes, within ε	an interval

Choosing a clock

• Measuring how long something took on one machine: the monotonic clock. If the time the machine spends asleep must count, as for a lease or a token’s expiry, use a clock that includes it, such as Linux’s CLOCK_BOOTTIME.
• Showing people when something happened: the wall clock, in UTC. Accept that it can be off by milliseconds across machines, and can jump.
• Deciding which of two writes wins: not the wall clock, unless you’ve decided that losing writes is acceptable within your skew. Prefer a version number checked by a conditional write, used for every write to that data. Carrying the timestamp you read helps writes that depend on what they read.
• Totally ordering operations everyone must agree on: a Lamport clock with a tie-break, or a single leader that assigns the order, which is where consensus comes in, in Part 26.
• Detecting conflicting concurrent updates: a vector clock or version vector, then merge in the application.
• Timestamps that respect causality and still read as time: HLC, plus an enforced bound on clock skew.
• Timestamps that respect real-time order across the world: TrueTime-style intervals and commit wait, if you have the clock infrastructure.

Explain it like I’m ten

Three friends are in different rooms, keeping a diary of what happens. Each has a watch, and the watches don’t quite agree.

• The watches: if you sort the diaries by watch time, a friend with a slow watch can seem to reply to a note before it was written.
• The Lamport rule: each friend numbers their diary lines. When you pass a note, you write your number on it. Whoever reads the note jumps their number past it. Now a reply always has a bigger number than the note it answers.
• The catch: two friends who never passed a note can still end up with numbers that look ordered. The numbers can’t tell you “these two had nothing to do with each other”.
• The vector rule: each friend keeps a little table, one count per friend, and passes the whole table with every note. Now you can tell when two lines had nothing to do with each other: neither table is bigger everywhere.
• The hybrid rule: write the watch time, but never a time smaller than one you’ve already written, and if a note arrives from someone whose watch is ahead, use their time instead. Add a tiny counter when the time doesn’t move. The numbers stay close to real time and replies still come after notes.

The precise version

• The diary lines are events, the notes are messages, and “a reply after its note” is happened-before.
• Numbering lines and jumping past received numbers is a Lamport clock. It satisfies the Clock Condition, but not its converse.
• The table of counts is a vector clock. It characterises happened-before exactly, at a cost of one entry per node.
• Watch time with a counter is a hybrid logical clock. It satisfies the Clock Condition and stays within the clock skew of physical time.
• Where the analogy breaks: real watches don’t just differ, they drift and jump. A step backwards can make a program see time go backwards on a single machine.

Trade-offs

• Wall clocks are readable and can’t order events across machines. Measured: a laptop kept in sync by NTP was roughly 70 ms behind nearby time servers, and 187 ms behind Cloudflare after a sleep.
• Last write wins is simple and loses acknowledged writes under skew. Measured: with one clock 70 ms fast and turns 20 ms apart, 200 of 400 acknowledged increments were lost.
• Lamport clocks are one number and never put an effect before its cause. But they order concurrent events anyway, so they can’t detect conflicts.
• Vector clocks detect concurrency exactly and grow with the number of nodes. Dynamo truncated them.
• HLC gives causal order and readable time in fixed size. It still needs a bound on clock skew, and CockroachDB shuts down a node that drifts too far from the others.
• TrueTime turns clock uncertainty into waiting. In 2012 that was about 5 ms per commit, paid with GPS and atomic clocks.

Common mistakes

• Sorting events from different machines by wall-clock timestamp. In the figure’s scenario, with a 70 ms slow clock, a receipt was stamped 65 ms before its send.
• Measuring durations with the wall clock. Cloudflare’s 2017 outage came from a negative duration.
• Assuming NTP means milliseconds everywhere. RFC 5905 claims hundreds of microseconds on fast LANs, and a few tens of milliseconds for clients polling as rarely as every 36 hours. Over the internet, asymmetric paths hide error inside the round trip.
• Trusting “last write wins” to mean the latest write wins. It means the write with the largest timestamp wins, and the timestamp comes from somebody’s clock.
• Assuming a smaller Lamport timestamp means “happened before”. Lamport’s own paper says the converse can’t hold.
• Saying Dynamo resolved conflicts with vector clocks. Vector clocks detected them; applications or last-write-wins resolved them.
• Assuming TrueTime has no uncertainty. It has an interval, and Spanner waits it out.
• Mixing smeared and unsmeared time sources. During a leap-second smear they can disagree by up to a second.

Interview questions

Try to answer each one before opening the model answer.

1. Why can’t you order events in a distributed system by timestamp?

Show a strong answer

• Each machine’s clock is different. Clocks drift at different rates, and synchronization corrects them only to within its own error, which depends on the network path.
• The error can exceed the gap between events. If two events on different machines happen 5 ms apart and one clock is 70 ms fast, that clock’s event always sorts last, whichever really came first.
• Clocks also jump. An NTP step or a leap second can move a clock backwards, so even one machine’s timestamps aren’t reliably increasing.
• What matters is causality. Happened-before says which events could have affected which, and that needs logical clocks, not physical ones.

Likely follow-up: “What if you use very good clocks?” Then the error is smaller but not zero, and you need to know its bound. Spanner does exactly that and waits out the bound.

2. Explain Lamport clocks. What guarantee do they give, and what don’t they give?

Show a strong answer

• A counter per process. Increment it on every event. Attach it to every message. On receipt, set it to the maximum of its own value and the message’s, plus one.
• Guarantee: if a happened before b, then C(a) < C(b). A cause always has a smaller timestamp than its effect.
• Not guaranteed: the converse. C(a) < C(b) doesn’t mean a happened before b; they may be concurrent.
• Total order: break ties by process ID. Useful when everyone must agree on one order, and it matters less which.

Likely follow-up: “So can Lamport clocks detect conflicting writes?” No. Two concurrent writes still get ordered timestamps, so one silently wins. You need vector clocks to detect the conflict.

3. How do vector clocks work, and when would you use them?

Show a strong answer

• One counter per node. A node increments its own entry on each event, sends the whole vector with each message, and on receipt takes the element-wise maximum.
• Comparison: V(a) < V(b) if every entry is ≤ and one is <. Then a happened before b. If neither is less, they’re concurrent.
• Use: detecting concurrent updates to the same data, so you can merge them instead of dropping one. Dynamo used them this way for versions of an object.
• Cost: size grows with the number of nodes. Dynamo truncated vectors at a threshold, “say 10” pairs, trading exactness for size.

Likely follow-up: “What happens after you detect a conflict?” The application reconciles, such as by merging shopping carts, or a policy like last-write-wins picks one.

4. What is a hybrid logical clock, and why would a database use one?

Show a strong answer

• A pair (l, c). l tracks the maximum physical time seen, from the local clock or from messages. c is a counter that breaks ties when l doesn’t move.
• Guarantees: causality is preserved like a Lamport clock, l is never behind the local clock, and it’s never more than the skew bound ahead.
• Why databases like it: fixed size, readable as a time, and usable for MVCC timestamps and snapshots. CockroachDB stamps every transaction with one.
• What it still needs: a bound on clock skew. CockroachDB’s default --max-offset is 500 ms, and a node that finds its clock out of sync with at least half the others by 80% of that shuts itself down.

Likely follow-up: “Does HLC detect concurrent events?” No. It orders them like a Lamport clock does.

5. How does Spanner’s TrueTime give external consistency?

Show a strong answer

• TrueTime returns an interval, [earliest, latest], guaranteed to contain the real time. GPS and atomic clocks keep it narrow: in 2012, about 1 to 7 ms.
• Commit wait: the leader picks a timestamp no earlier than latest, then waits until earliest has passed it. Only then does the commit become visible.
• Result: if transaction T2 starts after T1 commits, T2’s timestamp is larger. Timestamp order matches real-time order.
• Cost: latency. The 2012 paper measured commit wait at about 5 ms. If a node loses its time masters, its interval widens and the wait grows.

Likely follow-up: “How does CockroachDB do it without atomic clocks?” It doesn’t give the same guarantee. It uses HLC plus a configured maximum offset, and restarts reads that find a value inside the uncertainty window. Its own blog says it “only goes as far as to claim serializability”, and it names the anomaly that remains, where causally related transactions on different keys can appear out of order, “causal reverse”.

6. A service computes request latency as end - start using wall-clock time, and occasionally reports negative latencies. Why, and how do you fix it?

Show a strong answer

• The wall clock can step backwards. NTP steps large corrections, and a leap second can step the clock back one second.
• Fix: use the monotonic clock: time.Since in Go, System.nanoTime() in Java, Stopwatch in C#, Instant in Rust.
• Real incident: Cloudflare’s DNS in 2017. A duration went negative at the leap second, and rand.Int63n panicked on it.

Likely follow-up: “Can you compare monotonic readings across machines?” No. Its starting point is arbitrary, and on Linux it doesn’t count time the machine spent suspended.

7. Your system uses last-write-wins with client timestamps. What can go wrong, and what would you change?

Show a strong answer

• A client with a fast clock wins every conflict within its skew, even against writes that came later and knew about its write.
• Measured: against Cassandra with one client 70 ms fast, every write from the other client sent within 70 ms was acknowledged and lost. A read-modify-write counter, taking turns 20 ms apart, ended at 200 after 400 acknowledged increments.
• Fixes: a conditional write (compare-and-set on a version), which Cassandra stamped with the server’s clock in our single-node lab, provided every write to that row is conditional; carrying the timestamp you read, for writes that depend on what they read; or a CRDT that merges instead of picking a winner.
• At minimum: monitor clock offset and alert on it. CockroachDB goes further and shuts a node down, though Jepsen noted in 2017 that there is still “a few-second window during which transactional anomalies can occur”.

Likely follow-up: “Does server-side timestamping fix it?” Only if one server stamps everything. With several coordinators, their clocks disagree too.

Sources

• Lab: system-design/checks/part25_time/.
• ntp_probe.py: SNTP queries to six public servers, 30 rounds each, and a 100-minute run against one server, alongside timedatectl timesync-status.
• clocks_probe.py: CLOCK_REALTIME, CLOCK_MONOTONIC and CLOCK_MONOTONIC_RAW read side by side every 5 seconds, alongside the 100-minute run. suspend_evidence.py confirms the sleep from the kernel’s suspend count and the system journal.
• lww/: Cassandra 5.0.9 in Docker, pinned by digest, with the Go driver apache/cassandra-gocql-driver v2.1.2. Handoffs at five skews and seven waits, 20 each, with and without carrying the timestamp read; a counter of 400 increments, plain, carried and with lightweight transactions; and conditional writes after a fast plain write.
• clocks.py: the four clocks on the figure’s scenario, and each clock’s theorem checked on 300 random traces.
• Leslie Lamport, Time, Clocks, and the Ordering of Events in a Distributed System, CACM, 1978, and his note on it.
• Colin Fidge, Timestamps in Message-Passing Systems That Preserve the Partial Ordering, 1988.
• Friedemann Mattern, Virtual Time and Global States of Distributed Systems, 1988.
• Kulkarni, Demirbas et al., Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases, 2014.
• DeCandia et al., Dynamo: Amazon’s Highly Available Key-value Store, 2007.
• Corbett et al., Spanner: Google’s Globally-Distributed Database, OSDI 2012, and Eric Brewer, Spanner, TrueTime & The CAP Theorem, 2017.
• NTP: RFC 5905, RFC 8633, chrony’s documentation and FAQ, and systemd-timesyncd (source, v255).
• Leap seconds: Google’s leap smear, AWS Time Sync, CGPM 2022 Resolution 4, and Cloudflare’s 2017 post-mortem.
• Clocks in runtimes: Linux clock_gettime, Go time, Java System, .NET Stopwatch, Windows QPC, and Rust’s Instant and SystemTime.
• Databases: Cassandra 5.0’s architecture and CQL docs; CockroachDB’s transaction layer and --max-offset; DynamoDB global tables; Jepsen’s analyses of ScyllaDB 4.2 and CockroachDB; Google Cloud Spanner’s TrueTime; AWS’s ClockBound and microsecond-accurate clocks.

What to remember

• Clocks on different machines disagree. A laptop kept in sync by NTP was roughly 70 ms behind nearby time servers, and 187 ms behind Cloudflare after a sleep. A single reply over a long path can’t tell you better than half its round trip.
• Last write wins means largest timestamp wins. With one clock 70 ms fast, Cassandra acknowledged and lost every write sent within 70 ms of the fast client’s.
• Measure durations with the monotonic clock. Wall clocks step, sometimes backwards.
• Happened-before is the order that matters, and no physical clock gives it to you.
• Lamport clocks keep causes before effects in one number. They can’t detect concurrency.
• Vector clocks detect concurrency exactly, at one entry per node.
• HLC and TrueTime both keep timestamps close to real time. HLC needs a skew bound; TrueTime measures its uncertainty and waits it out.

A timestamp tells you what a clock said. It doesn’t tell you what happened first.