Skip to content
learn
  1. Learn
  2. High Level System Design
  3. Distributed Systems Theory

System Design HLD-08.04

Time and clocks

Why wall clocks cannot order events across machines, and how Lamport timestamps, vector clocks, hybrid logical clocks and TrueTime fix ordering.

Advanced 14 min Last reviewed

The big idea

Ordering events sounds trivial: compare their timestamps. Across machines it is not. Each computer's clock is a cheap quartz oscillator that drifts, by around tens of parts per million, and is periodically corrected by NTP, which can make it jump forwards or even backwards. Two machines' clocks commonly disagree by milliseconds, sometimes far more after a bad sync. So if server A records an event at 10:00:00.005 and server B at 10:00:00.003, you cannot conclude B's happened first, and a "last write wins" rule based on those timestamps can silently keep the older write.

The fix is to stop asking "what time was it?" and ask "what could have influenced what?". Event X can only have caused event Y if information could flow from X to Y, either on the same machine or through a message. Logical clocksA logical clock: counters attached to events so that causes always get smaller values than their effects, without using physical time. track exactly that, and they are the foundation of ordering in replicated systems, from version vectors in databases to the timestamps of globally distributed SQL.

Think of letters between friends without dates. You can still order them: a letter that replies to another was written after it. That reply relation, not the calendar, is what logical clocks capture.

How it works

Step 1: How skew breaks last-write-wins

Clock skew makes last-write-wins keep the older write Server A's clock runs 40 milliseconds fast. A writes x equals 1 at real time .010 but stamps it .050. Server B writes x equals 2 later, at real time .030, stamped .030. The store keeps the larger timestamp, so x equals 1 wins and the newer write is silently lost. Server A clock 40 ms fast Replicated store last write wins Server B clock correct x = 1 at 10:00:00.050 (really .010) x = 2 at 10:00:00.030 (really .030) keep the larger timestamp: .050 x = 1 -- the newer write was discarded Figure 1. A's write really happened first, but its fast clock gives it the larger timestamp. Last-write-wins keeps it and silently discards B's newer write (red).

Step 2: Happens-before

Event a happens beforeEvent a happens before event b if they are on the same process and a comes first, or a is a message send and b its receipt, or there is a chain of such steps from a to b. event b if: a and b are on the same process and a came first; or a sends a message and b receives it; or there is a chain of such steps. If neither happens before the other, the events are concurrent: neither could have known about the other.

Step 3: Lamport timestamps

Each process keeps a counter. It adds one for every event; it attaches the counter to every message; on receiving a message it sets its counter to the maximum of its own and the message's, then adds one. Result: if a happens before b, then a's timestamp is smaller than b's. Ties broken by process id give a total order every node agrees on. But the converse does not hold: a smaller Lamport number does not mean "happened before"; the events may be concurrent.

Step 4: Vector clocks

Each process keeps a vector with one counter per process. It increments its own entry on each event, sends the whole vector with messages, and on receipt takes the element-wise maximum, then increments its own entry. Now you can compare any two events: if every entry of V(a) is less than or equal to V(b), and at least one is smaller, a happened before b; if neither dominates, they are concurrent. That is exactly what replicated stores need to detect conflicting writes ( Multi-leader and leaderless replication ). The cost is a vector that grows with the number of processes.

Try it

This interactive needs JavaScript. The diagrams and text above cover the same idea.

Try this:

  1. In Lamport mode, step through. Watch event d on B jump past its own count to max plus one when A's message arrives.
  2. At the end, compare c and f. Lamport gives c a smaller number, but they are unrelated: Lamport cannot tell you that.
  3. Switch to vector clocks and run all. Compare c and f again: the vectors are incomparable, so they are concurrent. Check that a's vector is below g's: a really did happen before g, through two messages.

Going deeper

Hybrid logical clocks

Hybrid logical clocksTimestamps that combine physical time with a logical counter: close to wall-clock time, but still guaranteeing that causes get smaller timestamps than effects. (HLC) combine the two worlds: each timestamp is a physical time plus a small logical counter, taking the maximum of local and received times like Lamport clocks. They stay close to real time, so they are useful for things like snapshot reads "as of 10:00", while still respecting causality. CockroachDB and others use them.

TrueTime: bounding the uncertainty

Google's Spanner takes another route: GPS receivers and atomic clocks in every data center keep clock uncertainty within a few milliseconds, and the TrueTime API returns an interval, "now is between earliest and latest". To commit, Spanner waits out the uncertainty interval, so no later transaction can get an earlier timestamp anywhere in the world. Bounded uncertainty, not perfect clocks, is what makes external consistency possible.

Trade-offs

OptionWins whenLoses when
Wall-clock timestamps Human-readable logs and rough ordering on one machine Correct ordering across machines; last-write-wins can keep the wrong write
Lamport timestamps A cheap total order consistent with causality Detecting concurrency
Vector clocks Detecting concurrent, conflicting writes exactly Size grows with the number of writers
Hybrid logical clocks Causal order that stays close to real time Still bounded by clock sync quality for real-time meanings

Common mistakes

  • Resolving conflicts by comparing timestamps from different machines.
  • Assuming system time never goes backwards; use monotonic clocks to measure durations.
  • Using Lamport timestamps to decide whether two writes conflict.
  • Ignoring clock skew alerts, until a lease or certificate check fails.

Check yourself

  1. Why can't you order events across machines by wall-clock time?

    Show answer

    B. Clocks drift and are corrected, so they disagree between machines Skew of milliseconds or more means a later event can carry an earlier timestamp.

  2. On receiving a message, what does a Lamport clock do?

    Show answer

    B. Sets itself to max(own, message) + 1 Taking the maximum and adding one ensures the receive is ordered after the send.

  3. Vector clocks V(x) = [2,0,1] and V(y) = [1,1,1]. What is the relationship?

    Show answer

    C. Concurrent x is larger in the first entry and y in the second, so neither dominates.

  4. What does Spanner's TrueTime provide?

    Show answer

    B. A bounded uncertainty interval for the current time, which commits wait out Knowing the maximum error lets Spanner assign globally consistent commit timestamps.

Recap

  • Physical clocks drift and jump, so timestamps cannot order events across machines.
  • Happens-before captures what could have influenced what.
  • Lamport timestamps respect causality but cannot detect concurrency.
  • Vector clocks detect concurrent events, at the cost of size.
  • Hybrid logical clocks and TrueTime bring real time back with bounded error.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy