Engineering Atlas › System Design Fundamentals

Ordering events without wall clocks

12 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

Why not physical time

Clocks on different machines disagree and can jump. If node A stamps an event at 10:00:00.005 and node B, 8 ms behind, stamps a later event that depends on it at 10:00:00.002, sorting by timestamp puts effect before cause. Often we need only an order that never contradicts causality.

Happens-before

Define a -> b when a and b are on the same process and a came first, or a sends a message that b receives, or there is some c with a -> c and c -> b (Lamport 1978). If neither a -> b nor b -> a, the events are concurrent: neither could have known about the other. This is a partial order. Many pairs of events are simply unordered.

Lamport clocks

Each process keeps an integer. It increments before each local event or send, attaches the value to messages, and on receive sets its counter to max(local, received) + 1. This guarantees that if a -> b, then L(a) < L(b). The converse does not hold: L(a) < L(b) does not mean a caused b. Breaking ties by process ID produces a total order consistent with causality, which is enough for mutual exclusion, totally ordered broadcast, and replicated state machines. Raft's terms are the same idea; the Raft paper calls them a logical clock (Raft paper).

Vector clocks

Each process keeps a vector with one entry per process. It increments its own entry on each event, sends the whole vector, and on receive takes the element-wise maximum and then increments its own entry. Now V(a) < V(b) (every entry less than or equal, at least one strictly less) if and only if a -> b. If neither vector dominates, the events are concurrent. This lets a replicated store detect conflicting writes instead of silently picking one, which is how Amazon's Dynamo kept concurrent shopping-cart versions for the application to merge (Dynamo paper).

Hybrid logical clocks

An HLC timestamp is a pair (l, c): l tracks the largest physical time seen, and c is a counter that breaks ties when physical time has not advanced. It fits in 64 bits, stays within the clock skew bound of real time, and respects happens-before (Kulkarni et al.). The catch is that "within the skew bound" is an assumption the operator must make true. If real skew exceeds the bound the database was configured with, HLC databases can return stale reads, and independent testing has shown exactly that. CockroachDB and YugabyteDB use HLCs for transaction timestamps because they need both causal safety and timestamps that mean something to humans and to snapshot reads.

Down the stack

Layer 1The contract

Every logical clock promises the clock condition: if a -> b then C(a) < C(b). That one implication is testable by recording send and receive pairs and checking that every receive carries a larger stamp than its send. Lamport clocks promise only that. Vector clocks promise the converse too, so comparison answers "before, after or concurrent" exactly. HLCs promise the clock condition plus two bounds from the Kulkarni et al. paper: the logical part l never drifts from physical time by more than the clock skew bound, and the counter c stays small as long as clocks are roughly in sync. HLCs also promise per-node monotonicity even when the underlying wall clock is stepped backwards, which plain CLOCK_REALTIME does not.

Layer 2The mechanism

Real implementations differ mostly in encoding and in how they police skew. CockroachDB's hlc.Timestamp holds a 64-bit WallTime in nanoseconds and a 32-bit Logical counter (timestamp.proto). Each node is configured with a maximum clock offset (500 ms by default, with 250 ms recommended for new multi-region clusters), and a node whose clock is off from at least half of its peers by 80% of that limit shuts itself down rather than hand out misleading timestamps (CockroachDB FAQ). Operators are told to alert on the clock_offset_meannanos metric well before that point. Reads use an uncertainty interval from the read timestamp up to read timestamp plus max offset: if a value falls inside that window, the reader cannot tell whether it happened before or after, so the transaction restarts at a higher timestamp.

YugabyteDB, following Apache Kudu, packs a hybrid time into one 64-bit word: physical microseconds shifted left by 12 bits, with the low 12 bits as the logical counter (hybrid_time.h). Its skew bound is the max_clock_skew_usec flag, 500 ms by default (yb-tserver reference). The HLC paper suggests a similar split of 48 bits for l and 16 for c. MongoDB's cluster time is a BSON Timestamp of 32-bit seconds and a 32-bit increment, gossiped on every message as $clusterTime and signed so that a client cannot push the cluster's clock arbitrarily far forward (MongoDB docs).

The update rules are the ones in the Practice section: take the maximum of local l, physical time and the message's l, then set the counter based on which sources tied for that maximum.

Layer 3The machine

The physical input is clock_gettime(CLOCK_REALTIME), about 20 ns through the vDSO. The HLC must use wall time rather than CLOCK_MONOTONIC because its values need meaning across machines; monotonicity is then enforced in software by never letting l decrease.

Packing (l, c) into a single uint64 matters on the hot path. A timestamp can then be advanced with one 64-bit compare-and-swap instead of a mutex, and compared with one integer comparison. Under heavy concurrency, though, every core is writing the same 64-byte cache line, and each transfer between cores costs tens of nanoseconds, which caps a single shared clock at tens of millions of updates per second. In practice the clock is rarely the bottleneck compared to the network.

Size on the wire is the reason HLC and Lamport clocks dominate. A Lamport counter or HLC is 8 to 12 bytes per message, regardless of cluster size. A vector clock is roughly 8 bytes per participant before compression. A 64-bit Lamport counter incremented a billion times per second would take centuries to overflow, but a 12- or 16-bit HLC counter can overflow if a far-future l freezes the physical part and the node keeps generating events, which is one more reason to reject far-future timestamps.

Why it's built this way

  1. Physical clocks drift and can step, so they cannot order causally related events reliably on their own.
  2. Pure logical counters fix ordering but lose any link to real time, so "events in the last 10 minutes" and snapshot reads at a wall time become impossible.
  3. Combining the two keeps causality and stays within the skew bound, but only if that bound is enforced, hence max-offset checks and node self-termination.
  4. Metadata travels on every message and is stored with every version, so implementations pack it into a single 64-bit word and accept that concurrency detection needs the larger vector form.

Diagram

sequenceDiagram
    participant A as "Process A"
    participant B as "Process B"
    participant C as "Process C"
    Note over A: a1 (L=1)
    A->>B: m1 carries L=1
    Note over B: b1 receive (L=max(0,1)+1=2)
    Note over C: c1 local (L=1)
    B->>C: m2 carries L=2
    Note over C: c2 receive (L=max(1,2)+1=3)
    Note over A,C: a1 -> b1 -> c2, but a1 and c1 are concurrent

Worked example

An order service emits events from 3 processes into a log. Wall clocks skew by up to 15 ms, and dependent events often occur 2 to 5 ms apart, so physical timestamps misorder roughly a third of causally linked pairs in testing.

Option one, Lamport clocks: 8 bytes per event. Consumers sort by (counter, process_id). Every cause sorts before its effect. But two unrelated updates to the same order, one from checkout and one from support, also get an arbitrary order, and the consumer cannot tell they conflicted.

Option two, vector clocks: with 3 processes, 24 bytes per event. The consumer can now see that the checkout and support updates are concurrent and route them to a merge function. With 300 processes, the vector grows to 2.4 KB per event.

Option three, HLC: 8 bytes, causally safe, close to real time, so "events in the last 10 minutes" queries still work. It cannot detect concurrency, so it suits ordering and snapshots, not conflict detection.

In the wild

Trade-offs

ClockStrengthsWeaknessesChoose when
Physical (NTP)Human-meaningful, freeCan contradict causalityLogs for humans, coarse ordering
LamportOne integer, total orderCannot detect concurrencyState machine replication, ordered broadcast
VectorExact causality and concurrencySize grows with participantsConflict detection in multi-writer stores
Hybrid logicalNear real time, causal, compactNeeds bounded skew; no concurrency detectionDatabase transaction timestamps

Pitfalls in production

Leadership lens

Check yourself

  1. If L(a) < L(b) for Lamport timestamps, can you conclude that a happened before b?

    Show answer

    No. Lamport clocks guarantee only that causality implies a smaller timestamp. Concurrent events can have any ordering of timestamps.

  2. What can vector clocks tell you that Lamport clocks cannot?

    Show answer

    Whether two events are concurrent. If neither vector dominates the other, neither event could have known about the other.

  3. Why would a database choose a hybrid logical clock over a vector clock?

    Show answer

    It needs compact timestamps close to real time for snapshot reads and time-based queries, and it handles conflicts through its own concurrency control rather than by detecting concurrent writes.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →