Time & Clocks

Seat A-12 is held by Bruno. At 10:00:00.040 (real time) he gives up and releases it through inventory-1; twenty milliseconds later, at 10:00:00.060, Carla grabs it through inventory-2. Both updates replicate to the other nodes, and the store resolves the conflict with the most common rule there is — last write wins by timestamp. But inventory-1's clock runs 50 ms ahead: Bruno's release is stamped 10:00:00.090, Carla's hold 10:00:00.060. The release "wins", the seat shows as FREE, and Carla — who has already been charged — has no seat. No message was lost and no code had a bug: the system simply trusted two clocks that disagreed.

A distributed system has no global clock. Every machine has its own, they drift apart, and the network delay between them is variable and unknown — so "which happened first?" has no free answer. This page shows what physical clocks can and cannot do, and the tools that order events without trusting them: logical clocks, vector clocks, hybrid clocks, TrueTime, and plain single authorities.

Two clocks in every machine

Every operating system offers two different clocks, and mixing them up is a classic bug:

// Wrong: if NTP steps the wall clock during the call, the "duration" can be negative or huge
long start = System.currentTimeMillis();
callPaymentProvider();
long elapsedMs = System.currentTimeMillis() - start;

// Right: the monotonic clock only measures elapsed time, and never goes backwards
long t0 = System.nanoTime();
callPaymentProvider();
long elapsedNs = System.nanoTime() - t0;

Physical clocks drift

A computer's clock is a quartz oscillator, and quartz is imperfect: its frequency depends on temperature and on the crystal. Drift is measured in ppm (parts per million): 20 ppm means 20 µs gained or lost per second — about 1.7 seconds per day. Google assumes a bound of 200 ppm for its servers¹. Left alone, two machines' clocks diverge without limit.

NTP (Network Time Protocol) corrects this by periodically asking time servers (organised in strata, stratum 0 being atomic or GPS clocks) and adjusting the local clock — gradually (slewing) for small offsets, by a jump (stepping) for large ones. Its accuracy is limited by the network delay it cannot measure exactly: NTP assumes the request and the response took equally long, so asymmetric delays become clock error.

The synchronised servers stay within a couple of milliseconds of each other (a sawtooth: drift, correct, drift); the one that lost NTP silently walks away — 24 ms after ten minutes at 40 ppm, and over three seconds after a day. Nothing alerts by default. Typical orders of magnitude (illustrative, they depend heavily on the setup):

Why timestamps cannot order events

The opening story, step by step. Each node stamps its write with its own wall clock; replication delivers both writes to both nodes; last-write-wins (LWW) keeps the higher timestamp:

sequenceDiagram
    participant B as Bruno
    participant I1 as inventory-1 (clock +50 ms)
    participant I2 as inventory-2 (clock accurate)
    participant C as Carla
    B->>I1: release A-12 (real time .040)
    Note over I1: stamped .090
    C->>I2: hold A-12 (real time .060)
    Note over I2: stamped .060
    I1->>I2: replicate release @ .090
    I2->>I1: replicate hold @ .060
    Note over I1,I2: LWW: .090 > .060, the release wins<br/>Carla's hold is silently discarded

With clocks synchronised to within ε, two events less than ε apart cannot be ordered by their timestamps — and in an LWW store, the node with the fastest clock wins every conflict. Cassandra uses LWW per column by default, and so does any "updated_at wins" merge logic you write yourself. LWW is acceptable when losing one of two concurrent writes is harmless (a profile picture); it is dangerous for seats and money.

The way out is to stop asking clocks when something happened and ask instead what could have influenced what.

Lamport clocks

Leslie Lamport's 1978 paper³ — one of the most cited in computer science — observed that what matters is the happened-before relation (→):

• if a and b happen in the same process and a comes first, then a → b;
• if a is the sending of a message and b its receipt, then a → b;
• if a → b and b → c, then a → c (transitivity).

If neither a → b nor b → a, the events are concurrent (a ∥ b): neither could have influenced the other.

A Lamport clock is a counter per process with three rules:

1. Before each local event, increment the counter.
2. When sending a message, attach the counter.
3. When receiving a message carrying t, set the counter to max(local, t) + 1.

sequenceDiagram
    participant O as order
    participant K as Kafka consumer (inventory)
    participant N as notification
    Note over O: create order 981 (L=1)
    O->>K: OrderPaid (L=2)
    Note over K: receive: max(0, 2) + 1 = 3
    Note over N: unrelated local event (L=1)
    K->>N: TicketIssued (L=4)
    Note over N: receive: max(1, 4) + 1 = 5

The guarantee is one-directional: if a → b then L(a) < L(b). The converse does not hold — L(a) < L(b) does not prove that a happened before b; they may be concurrent. Breaking ties by node id gives a total order consistent with causality, which is enough for many algorithms (Raft's term is a Lamport-style counter). What a Lamport clock cannot do is detect concurrency.

Vector clocks

A vector clock keeps one counter per node. Each node increments its own entry on a local event, attaches the whole vector to messages, and on receipt takes the element-wise maximum (then increments its own entry). Comparing two vectors answers the question Lamport clocks cannot:

• V(a) ≤ V(b) element-wise (and different) → a → b;
• V(b) ≤ V(a) → b → a;
• neither → concurrent: a real conflict that needs resolution.

Three replicas of Carla's cart ([SP, LIS, NYC] counters):

The store keeps both versions (siblings) and asks the application to merge them — exactly what Amazon's Dynamo did for the shopping cart (merge by union, which is why deleted items occasionally came back)⁴. Riak exposed the same model.

sequenceDiagram
    participant SP as replica SP
    participant LIS as replica LIS
    participant NYC as replica NYC
    Note over SP: add ticket [1,0,0]
    SP->>LIS: replicate [1,0,0]
    SP->>NYC: replicate [1,0,0]
    Note over LIS: add parking [1,1,0]
    Note over NYC: remove ticket [1,0,1]
    LIS->>NYC: replicate [1,1,0]
    Note over NYC: [1,1,0] vs [1,0,1]: concurrent<br/>keep both, merge in the application

Both clocks side by side, on three BoxOffice services:

The cost is size: the vector grows with the number of nodes (or clients) that write. Practical systems use version vectors with one entry per replica (not per client) and prune old entries.

Hybrid logical clocks

Logical clocks capture causality but have nothing to do with real time — you cannot ask "what was the state at 10:00:00?". Physical clocks are close to real time but do not capture causality. A hybrid logical clock (HLC, Kulkarni et al., 2014)⁵ combines both into one fixed-size timestamp (l, c):

• l is the largest physical time the node has seen (its own clock or any message's);
• c is a logical counter that breaks ties when l does not advance.

import time

class HLC:
    def __init__(self):
        self.l, self.c = 0, 0                 # (physical part in ms, logical counter)

    def now(self):                             # local event or send
        pt = int(time.time() * 1000)
        if pt > self.l:
            self.l, self.c = pt, 0
        else:
            self.c += 1                        # wall clock did not advance: count
        return (self.l, self.c)

    def update(self, ml, mc):                  # on receiving a message stamped (ml, mc)
        pt = int(time.time() * 1000)
        new_l = max(self.l, ml, pt)
        if new_l == self.l == ml:
            self.c = max(self.c, mc) + 1
        elif new_l == self.l:
            self.c += 1
        elif new_l == ml:
            self.c = mc + 1
        else:
            self.c = 0
        self.l = new_l
        return (self.l, self.c)

HLC timestamps respect causality (like Lamport clocks), stay within the clock-sync error of real time (so they can be used for "read as of 10:00:00" snapshots), and fit in 64 bits. CockroachDB, YugabyteDB and MongoDB (cluster time) use them. They still rely on a bound on clock skew: CockroachDB, for example, has a configured maximum offset (500 ms by default) and a node that detects it is further off than that shuts itself down rather than risk inconsistency⁶.

TrueTime and Spanner

Google's Spanner¹ took the opposite route: instead of avoiding physical time, make it trustworthy. Each data centre has GPS receivers and atomic clocks, and the TrueTime API does not return a time but an interval: TT.now() = [earliest, latest], guaranteed to contain the true time, with an uncertainty ε that the paper reports as typically 1–7 ms.

To make transactions externally consistent (if T1 commits before T2 starts, T2's timestamp is larger), Spanner uses commit wait: it picks the commit timestamp s = TT.now().latest and then waits until TT.now().earliest > s before making the commit visible — i.e. until s is guaranteed to be in the past everywhere.

sequenceDiagram
    participant C as client
    participant S as Spanner leader
    participant TT as TrueTime
    C->>S: commit T1
    S->>TT: now()
    TT-->>S: [10:00:00.100, 10:00:00.106]
    Note over S: s = .106 (latest), replicate via Paxos meanwhile
    S->>TT: now() until earliest > .106
    TT-->>S: [10:00:00.107, 10:00:00.113]
    S-->>C: committed at s = .106
    Note over C,S: any later transaction gets s' > .106

The cost of correctness is literally waiting out the uncertainty (on average ~2ε per commit, overlapped with the Paxos replication). Smaller ε means faster commits, which is why Google invests in clocks. AWS later published a similar open-source API, ClockBound, that returns error bounds on EC2 instances.

Ordering in practice

Most systems never implement vector clocks or TrueTime. They get order from simpler sources — and it is worth knowing what each one guarantees:

A Snowflake ID (Twitter, 2010) packs a 64-bit integer with a 41-bit millisecond timestamp, a 10-bit machine id and a 12-bit per-millisecond sequence — up to 4,096 ids per millisecond per machine, unique without coordination, and roughly sortable by time. UUIDv7 (RFC 9562, 2024)⁷ standardises the same idea in a 128-bit UUID with a 48-bit Unix-millisecond prefix: B-tree indexes stay compact because new keys are appended at the end instead of scattered like random UUIDv4.

// 64-bit id: 41 bits of ms since a custom epoch | 10 bits machine id | 12 bits sequence
final class Snowflake {
    private static final long EPOCH = 1735689600000L;   // 2025-01-01T00:00:00Z
    private final long machineId;                         // 0..1023, assigned per instance
    private long lastMs = -1, seq = 0;

    Snowflake(long machineId) { this.machineId = machineId; }

    synchronized long next() {
        long now = System.currentTimeMillis();
        if (now < lastMs) now = lastMs;                   // clock stepped back: do not go backwards
        if (now == lastMs) {
            seq = (seq + 1) & 0xFFF;                      // 4096 ids per ms
            if (seq == 0) while ((now = System.currentTimeMillis()) <= lastMs) { }  // wait next ms
        } else {
            seq = 0;
        }
        lastMs = now;
        return ((now - EPOCH) << 22) | (machineId << 12) | seq;
    }
}

    var holdId = UUID.randomUUID();
    var expiresAt = OffsetDateTime.now(ZoneOffset.UTC).plus(holdTtl);
@Scheduled(fixedDelay = 5000)
@Transactional
public void expireHolds() {
    int freed = jdbc.sql("""
            WITH expired AS (
                UPDATE inventory.holds SET status = 'EXPIRED'
                WHERE id IN (SELECT id FROM inventory.holds
                             WHERE status = 'ACTIVE' AND expires_at < now()
                             ORDER BY expires_at
                             LIMIT 500
                             FOR UPDATE SKIP LOCKED)
                RETURNING id)
            UPDATE inventory.seats
            SET status = 'AVAILABLE', hold_id = NULL, version = version + 1
            WHERE status = 'HELD' AND hold_id IN (SELECT id FROM expired)""")
            .update();
    if (freed > 0) {
        log.info("expired holds freed {} seats", freed);
    }
}

How it connects

flowchart LR
    DRIFT["clock drift<br/>NTP, PTP"] --> LWW["LWW loses writes"]
    LWW --> VV["version vectors, CRDTs<br/>→ Replication & Consistency"]
    HB["happened-before"] --> LAM["Lamport clocks"]
    LAM --> TERMS["Raft terms, fencing tokens<br/>→ Consensus"]
    HB --> VEC["vector clocks"] --> VV
    DRIFT --> HLC["hybrid logical clocks"]
    LAM --> HLC
    DRIFT --> TT["TrueTime<br/>commit wait"]
    HLC --> SNAP["consistent snapshots<br/>CockroachDB, YugabyteDB"]
    TT --> SNAP
    AUTH["single authority<br/>DB now(), Kafka offsets"] --> PRAC["practical ordering"]
    IDS["Snowflake, UUIDv7"] --> PRAC

Palette components that provide order or time: sql (sequences, now() on the primary) · kafka (offsets per partition) · scheduler (wall-clock triggers — beware skew) · cache (TTL expiry). Continues in: Messaging — Kafka (ordering by key), Case study: URL shortener (unique ids), Observability (clock skew in traces).

Key takeaways