Distributed Systems · 2 of 4

Time, Clocks & Ordering

Machines can't agree on what time it is, but they can agree on what caused what. Logical clocks order events without trusting any clock; hybrid clocks and TrueTime put physical time back, carefully.

≈ 20 min

The whole idea

Press ← → to step, or Space to play and pause, whenever a diagram has focus.

Why order matters

The previous lesson ended on a bleak note: every machine’s clock is a little wrong, by an unknown amount, and can jump. Yet nearly every distributed system needs to put events in order:

  • Replicas must apply the same writes in the same order, or they drift apart.
  • Conflict resolution must decide which of two writes came later, or whether neither did.
  • Snapshots and backups must capture a state that actually existed: no effect without its cause.
  • Users expect a reply to appear after the question it answers, as in the hero above.

The hero shows the trap. Sorting by wall-clock timestamp is wrong whenever two events are closer together than the clocks’ disagreement, and the error is silent. The way out, found by Leslie Lamport in 1978, is to notice that most of the time we don’t need when things happened. We need what could have caused what.

Happens-before

Inside a distributed system, one event can influence another only if information flowed from the first to the second. That gives a precise relation, happens-before (written a → b), defined by three rules:

  1. If a and b happen on the same process and a comes first, then a → b.
  2. If a is sending a message and b is receiving that message, then a → b.
  3. If a → b and b → c, then a → c.

If neither a → b nor b → a, the events are concurrent (a ∥ b). Concurrent doesn’t mean simultaneous. It means neither could have known about the other, however far apart their wall-clock times.

Happens-before

Causality is a property of the arrows, not of the clocks.

This is a partial order: some pairs are ordered, some aren’t. It’s also exactly the order that matters for correctness. A replica that applies an update before the update it depends on is broken; a replica that applies two concurrent updates in either order is fine, as long as every replica picks the same order (or merges them). Lamport took the idea from special relativity: an event’s causal past is like its past light cone, the only events whose signals could have reached it.

Lamport clocks

To use happens-before, you need timestamps that respect it. Lamport’s logical clocks do it with one integer per process and two rules:

  • Increment your counter before each event, and stamp the event with it.
  • Put your counter on every message you send. On receiving, set your counter to max(yours, received), then increment.

Lamport clocks

One integer per process, two rules, no synchronized time.

The guarantee is the clock condition: if a → b then L(a) < L(b). Break ties with the process ID and you get a total order, (counter, process ID), that is consistent with causality. Lamport’s paper used exactly that to build a mutual-exclusion algorithm: every process sorts lock requests by timestamp, so all agree on who’s next.

The converse doesn’t hold. L(a) < L(b) is compatible with a → b and with a ∥ b, so a Lamport timestamp can’t tell you whether two writes conflict. And a total order learned after the fact isn’t enough for decisions that must be made now. Suppose two users claim the same username on different nodes. The lower timestamp should win, but a node can only declare its claim the winner once it knows no node holds a lower one, which means hearing from every node, which stalls if any node is down. Deciding needs the order to be fixed as it happens: total order broadcast, below.

Vector clocks

To detect concurrency, give each process a vector with one counter per process (Fidge and Mattern, independently, 1988). A process increments its own entry before each event; a message carries the whole vector; a receiver takes the element-wise max and then increments its own entry.

Vector clocks

Each entry records how much of one process’s history an event has seen.

Now V(a) ≤ V(b) in every entry if and only if a → b, and if neither vector dominates, the events are concurrent. That’s the precise test conflict detection needs: overwrite when one version descends from the other; keep both (siblings) when they’re concurrent.

The price is size: one entry per process. Databases sidestep it with Version Vectors, one entry per replica rather than per client, attached to each key. Amazon’s Dynamo kept vectors bounded by truncating the oldest entries past a threshold, accepting occasional false conflicts.

Hybrid logical clocks

Logical clocks are safe but unhelpful for humans and for queries like “read the database as of 10:00:05”. Physical clocks are helpful but unsafe. A hybrid logical clock (Kulkarni et al., 2014) is both.

Each timestamp is a pair (l, c). l is the largest physical time the node has seen, its own or in any message; c is a counter that orders events sharing the same l.

A hybrid logical clock

The counter only ticks while physical time is behind; it resets as soon as the clock catches up.

The algorithm guarantees the clock condition (a → b implies HLC(a) < HLC(b)), and l never exceeds the true physical time by more than the clock skew. Packed as 48 bits of l and 16 of c, it fits in 64 bits, the same space as a physical timestamp, so it can replace one wherever it’s used.

That makes HLCs the default timestamp for distributed SQL databases that can’t buy atomic clocks:

  • CockroachDB stamps transactions with HLC time. Every read carries an uncertainty interval, its timestamp plus the cluster’s maximum clock offset (500 ms by default). A value inside that window might have been written before the read in real time, so the read restarts at a later timestamp. A node whose clock disagrees with at least half of the others by 80% of the maximum offset shuts itself down.
  • MongoDB has used a hybrid logical cluster time since 3.6 for causally consistent sessions, gossiped between nodes and drivers, and cryptographically signed so a client can’t push the clock forward.
  • YugabyteDB uses HLCs too, and since version 2.23 can take its clock bounds from AWS ClockBound to shrink its uncertainty window.

TrueTime

Google’s Spanner (OSDI 2012) took the other path: make the clock’s uncertainty explicit and small, and wait it out.

TrueTime returns an interval, not a point. TT.now() gives [earliest, latest] and guarantees true time lies inside. Each data centre has time masters: most with GPS receivers, some (the “Armageddon masters”) with atomic clocks, since the two fail in uncorrelated ways. Every machine’s daemon polls several masters, uses Marzullo’s algorithm to reject liars, and widens its interval between polls at an assumed worst-case drift of 200 µs per second.

1–7 msTrueTime uncertainty ε in 2012: a sawtooth between 30-second polls
≈ 4 msε most of the time
≈ 2εhow long a read-write transaction’s commit waits

The uncertainty is what makes commit wait both necessary and sufficient:

Commit wait

Wait out the uncertainty once, at commit, and timestamps agree with real time everywhere.

The result is external consistency: if T1 commits before T2 starts, in real time, then s1 < s2, even across continents, with no communication between T1 and T2. That’s what lets Spanner serve lock-free snapshot reads at a timestamp from any replica: the timestamp order is the real order. It also repairs Lamport’s phone-call anomaly, because physical time, bounded, captures orderings that happen outside the system.

The cost is waiting about 2ε per read-write transaction. In the paper’s single-replica benchmark, commit wait was about 5 ms. Spanner overlaps it with Paxos replication, which takes that long anyway across replicas. Smaller ε means shorter waits, which is why the clock infrastructure is the real product.In the paper’s measurements, ε spiked for about an hour when two time masters in one data centre were shut down for maintenance. The bound is only as good as the time service behind it.

Bounded clocks are no longer Google-only. Since November 2023 the Amazon Time Sync Service keeps supported EC2 instances within microseconds of UTC, and ClockBound exposes the error bound so applications can do TrueTime-style reasoning. Amazon Aurora DSQL (December 2024) picks every transaction’s start time from “EC2’s precision time infrastructure which provides an accurate clock with strong error bounds”.

Total order broadcast

Back to the username problem. What we need is a way to fix the order of messages as they’re sent, so every node learns it. Total order broadcast (also called atomic broadcast) guarantees two things:

  • Reliable delivery: if a message is delivered to one node, it’s delivered to all of them.
  • Totally ordered delivery: every node delivers messages in the same order.

Total order broadcast

Deterministic replicas fed the same ordered log stay identical. That’s state machine replication.

With it, the username race is easy: append “claim alice” to the log, read the log until your claim appears, and you win if no earlier claim for the same name precedes it. Every node reads the same log, so every node reaches the same verdict. The same trick gives a linearizable compare-and-set, and the log position is a ready-made Fencing Token: ZooKeeper’s zxid is exactly that.

The hard part is keeping the log’s order when its leader fails, without losing or reordering anything. That’s consensus, and the equivalence is exact: a total order broadcast protocol can implement consensus, and consensus can implement total order broadcast. ZooKeeper’s Zab, etcd’s Raft log and each Kafka partition are all total order broadcast in production. Kafka orders within a partition only, which is how it scales.

Unique IDs

Every system needs IDs, and the choice of scheme is a choice about time and coordination.

Four ways to make an ID

Where the timestamp sits decides how IDs sort, and how inserts land in an index.
  • Auto-increment is perfectly ordered and needs one node to issue every ID.
  • UUIDv4 needs no coordination at all. Its 122 random bits scatter inserts across a B-tree index, which hurts cache locality on large tables.
  • Snowflake (Twitter, 2010) gets uncoordinated, roughly time-sorted 64-bit IDs. Twitter promised ordering within about a second and aimed for tens of milliseconds, which is a statement about clock sync, not causality. If the clock goes backwards, a Snowflake worker refuses to generate IDs until it passes the last timestamp it used. Instagram’s 2012 variant generated IDs inside PostgreSQL: 41 bits of time, 13 of logical shard, 10 of sequence.
  • UUIDv7 (RFC 9562, May 2024, which obsoletes RFC 4122) standardizes the time-first idea in 128 bits, and the RFC tells implementations to prefer it over v1 and v6. PostgreSQL 18 (September 2025) ships uuidv7().

None of these is causal. A Snowflake or UUIDv7 ID from a node with a fast clock sorts after one made later on a node with a slow clock, just like last write wins. If you need IDs that respect causality, use a hybrid logical clock or a log position.

Trade-offs

Clock Detects concurrency? Tied to real time? Size Used for
Wall clock no roughly, ± skew 64 bits display, TTLs, LWW (unsafely)
Lamport clock no no 64 bits total order consistent with causality
Vector / version vector yes no one entry per process or replica conflict detection (Dynamo, Riak)
Hybrid logical clock no within the skew 64 bits MVCC timestamps (CockroachDB, MongoDB, YugabyteDB)
TrueTime / ClockBound via waiting yes, bounded interval external consistency (Spanner, Aurora DSQL)
Total order broadcast n/a: imposes one order no log position replication, locks, uniqueness (ZooKeeper, etcd, Kafka)

In the real world

  • Spanner gives external consistency at global scale by buying GPS receivers and atomic clocks and waiting out ε, a few milliseconds per write transaction.
  • CockroachDB chose commodity NTP and HLCs. “While Spanner always waits after writes, CockroachDB sometimes retries reads,” as its engineers put it, and it gives up linearizability for unrelated keys.
  • AWS turned bounded time into a commodity: microsecond-accurate EC2 clocks (2023), ClockBound, and Aurora DSQL (2024) built on top.
  • Dynamo-style stores detect concurrent writes with version vectors and either return siblings or merge them.
  • ZooKeeper, etcd and Kafka are total order broadcast you can rent, and the basis for most leader election, locking and configuration in production.

Pitfalls

  • Sorting by wall-clock timestamp across machines. It’s wrong whenever events are closer than the skew, and nothing tells you.
  • Reading a Lamport timestamp as “happened before”. Smaller doesn’t mean earlier in causality; it might be concurrent.
  • Using time-sortable IDs as an ordering guarantee. Snowflake and UUIDv7 are roughly sorted, bounded by clock sync.
  • Letting vector clocks grow per client. Track per replica (version vectors) or the metadata outgrows the data.
  • Treating an HLC like TrueTime. An HLC has no error bound; without commit wait or read restarts you don’t get real-time ordering.

Recall

Go deeper

Keep going

The atomic notes for this lesson live in the knowledge graph:

Next on the map: Consistency Models (what “linearizable” and “causal” promise to clients) and Consensus (how total order broadcast survives a leader’s death).

Done with this lesson?

Mark it learned and the concepts it teaches will light up in your galaxy.

Next in Distributed SystemsConsistency Models