Hybrid Logical Clocks architecture — physical + logical, causality, bounded

Two clocks, two different failures

A distributed system that wants to order events has two families of clock available, and each fails in a way the other does not.

Physical clocks give you a number that means something outside the system. You can put it in a log line, compare it to an entry in someone else's audit trail, express a retention policy against it, or answer “what did this row look like at 14:32 yesterday.” What they do not give you is monotonicity or agreement. A machine's wall clock can step backwards when the sync daemon corrects a large offset, can freeze and then jump during a VM live migration or a long stop-the-world pause, and at any instant disagrees with its neighbours by some nonzero amount. The mechanics of keeping that disagreement small — polling, filtering, slewing versus stepping, stratum hierarchies — belong to the synchronisation protocol, and are developed in NTP: keeping clocks in sync across a network. For HLC purposes only the consequence matters: skew is bounded in the healthy case and nonzero always, so two raw wall-clock timestamps from two hosts cannot be compared and believed.

Logical clocks invert the tradeoff. A Lamport counter is incremented on every local event and carried on every message, with the receiver taking the max and adding one. That is enough to guarantee that if e causally precedes f then L(e) < L(f). Vector clocks go further and detect concurrency exactly, at the cost of one counter per node in every timestamp — see vector clocks and causal consistency for that machinery. But the number a logical clock produces is meaningless outside the system. It cannot expire a lease, cannot be joined against an external event stream, cannot be shown to an operator, and cannot answer a bounded-staleness read.

HLC is the observation that you do not have to choose. Seed a logical clock with the physical clock and the resulting value inherits causality from the logical side and interpretability from the physical side.

The state and the three update rules

Each node keeps two integers: l, the highest physical-clock reading it has seen anywhere in its causal past, and c, a counter that breaks ties inside a single tick of l. A timestamp is the pair (l, c), compared lexicographically. pt below is a fresh read of the local wall clock.

class HLC:
    def __init__(self):
        self.l = 0      # physical component, e.g. milliseconds since epoch
        self.c = 0      # logical counter within one value of l

    # local event, or the timestamp stamped on an outgoing message
    def now(self, pt):
        l_prev = self.l
        self.l = max(l_prev, pt)
        self.c = self.c + 1 if self.l == l_prev else 0
        return (self.l, self.c)

    # receiving a message stamped (lm, cm)
    def update(self, pt, lm, cm):
        l_prev = self.l
        self.l = max(l_prev, lm, pt)
        if self.l == l_prev == lm:
            self.c = max(self.c, cm) + 1     # both sides already at this tick
        elif self.l == l_prev:
            self.c = self.c + 1              # our l wins
        elif self.l == lm:
            self.c = cm + 1                  # their l wins
        else:
            self.c = 0                       # physical time moved past both
        return (self.l, self.c)

Three things are worth reading off that code. First, l is a running maximum and therefore never decreases — a backwards jump in pt is simply absorbed, with c taking over the ordering job until physical time catches back up. Second, c resets to zero the moment pt advances past l, which is what stops it drifting upward forever the way a Lamport counter does. Third, the receive rule is the only place causality enters: taking max with the sender's lm is what makes the receiver's timestamp strictly greater than the sender's, and the max(c, cm) + 1 branch is what preserves that when both nodes are inside the same millisecond.

Concretely: node A stamps a write at (1720394890, 0). It sends two more messages within the same millisecond and gets (1720394890, 1) and (1720394890, 2). Node B, whose clock happens to read 1720394887 — three milliseconds behind — receives the last of these. Its physical reading loses the max, so it adopts 1720394890 and stamps (1720394890, 3). The reply is unambiguously after the write that caused it, even though B's own clock still says otherwise.

The construction at a glance

Why the value stays anchored to physical time

The useful half of HLC is that l is not just monotone, it is close to real time. The argument is short. l is a maximum over physical-clock readings, so it can never be smaller than the local pt. And every value it could have picked up came from some node's physical clock, so it can never exceed the largest wall-clock reading anywhere in the fleet. That sandwiches the drift: l - pt is bounded above by the maximum clock skew across the cluster. HLC contributes no drift of its own; it inherits exactly whatever bound the synchronisation layer provides, which in a datacentre with a healthy time service is single-digit milliseconds.

The counter is bounded for the same reason. c can only grow while l is stuck, and l is only stuck while every physical clock feeding it is behind the value it already holds. Once real time overtakes l, c is reset. In practice it stays in the single digits and only spikes when a node emits a burst of events inside one tick — which is precisely why systems that keep the physical component at nanosecond resolution, like CockroachDB, see the counter fire almost never.

The asymmetry is the thing to internalise. A backwards clock jump is harmless: l holds, c increments, correctness is untouched. A forward jump is poison. A node whose clock briefly reads an hour into the future stamps a message with that value, every node that receives it takes the maximum and adopts it, and because l is a maximum it can never come back down. The whole cluster is now issuing timestamps an hour ahead of real time, all bounded-staleness and time-travel reads are wrong, and there is no automatic recovery — you wait it out or you rebuild. This is why the defence has to be at the boundary: refuse an incoming lm that is more than a configured maximum offset ahead of the local clock, and have a node that finds itself disagreeing with the majority of its peers take itself out of service rather than infect them. CockroachDB's --max-offset defaults to 500 milliseconds and a node self-terminates when its measured offset against a majority of peers approaches that bound.

Fitting it into 64 bits

The property that made HLC spread is not elegance, it is that adoption is nearly free. A column, an index key or a wire field that already held a millisecond wall-clock timestamp can hold an HLC without changing its width. The usual packing splits a 64-bit integer into a 48-bit physical field and a 16-bit counter.

CBITS = 16
CMASK = (1 << CBITS) - 1        # 65535

def pack(l_ms, c):
    if c > CMASK:                 # counter overflow: borrow one millisecond
        l_ms, c = l_ms + 1, 0     # safe -- l is allowed to lead pt
    return (l_ms << CBITS) | c

def unpack(ts):
    return ts >> CBITS, ts & CMASK

# ordering is just integer ordering:
#   pack(1720394890, 3) < pack(1720394890, 4) < pack(1720394891, 0)

Forty-eight bits of milliseconds covers roughly 8,900 years from the Unix epoch, so the physical field is not a horizon anyone needs to plan for. Sixteen bits of counter allows 65,536 distinguishable events per node per millisecond; overflow is handled by incrementing the physical field and resetting the counter, which is legitimate precisely because l is already permitted to run ahead of pt. Other splits exist for other resolutions: MongoDB's cluster time uses a 32-bit seconds field with a 32-bit increment, and CockroachDB declines to pack at all, carrying a 64-bit nanosecond wall value beside a 32-bit logical counter.

The packing buys one more property that matters more than the byte count. Because the physical component occupies the high bits, the big-endian byte order of the packed integer is identical to the lexicographic order of (l, c). An HLC therefore sorts correctly as a raw index key, in a B-tree, in an LSM key suffix, or in any comparator that already understood integers. No custom collation, no schema migration, no change to range scans that were written against wall-clock timestamps. That is the entire adoption story.

What it guarantees, and what it does not

The guarantee is one-directional and it is worth stating precisely: if event e happened before event f, then hlc(e) < hlc(f). The contrapositive is the form you actually use in code — if hlc(f) <= hlc(e) then f cannot have caused e, so it is safe to reorder them, drop the older one, or resolve them without further coordination.

The converse is false, and this is the most commonly misread property. hlc(e) < hlc(f) does not mean e caused f. Two genuinely concurrent events on two nodes that never exchanged a message will still receive comparable timestamps, and one will be arbitrarily declared earlier. HLC cannot detect concurrency; it deliberately trades that away for a compact, externally meaningful value. If your conflict resolution needs to know “these two writes are concurrent, so merge them or ask the user,” HLC will not tell you — it will silently pick a winner. That is what vector clocks and CRDTs are for.

HLC is not a consensus protocol. Ordering and agreeing are different problems. Two nodes can mint interleaved timestamps for writes to the same key without ever communicating; nothing in the clock decides which one is committed, or that a committed history exists at all. Durability and agreement still come from Raft or Paxos, and HLC sits above them supplying the version numbers the log commits.

HLC is not TrueTime. An HLC is a point, not an interval: it carries no uncertainty bound, so there is nothing to wait out. Spanner achieves external consistency — the property that a transaction which committed in real time before another began gets a smaller timestamp even when the two never communicated — by exposing the uncertainty explicitly and paying a commit wait proportional to it, which is developed in Spanner TrueTime. HLC-based systems do not get that for free. They approximate it by treating the configured maximum offset as an uncertainty window on reads and restarting any transaction that observes a value inside it, which is cheaper in hardware and more expensive in retries.

Where it earns its keep

MVCC version timestamps. A multi-version store needs a total order over versions and a way for a reader to name a snapshot. HLC supplies both, and because the value tracks real time, snapshots become expressible in terms users understand: “read as of five minutes ago” is a subtraction, not a lookup. Bounded-staleness reads on follower replicas work the same way — see bounded staleness — and they are only meaningful because the version numbers are anchored to a clock.

Conflict-resolution ordering. Last-write-wins driven by raw wall-clock timestamps has a specific, well-known bug: a write that causally follows another can carry a smaller timestamp simply because the second node's clock ran behind, so the newer write silently loses. Cassandra's client-supplied microsecond write timestamps have exactly this exposure. Swapping the timestamp source for an HLC eliminates the causal case entirely, because the second node's clock is forced forward by the message that carried the first write. It does not fix LWW's deeper problem — concurrent writes still lose data — but it removes the failure that looks like corruption.

Session and causal-consistency tokens. Hand the HLC back to the client with the write acknowledgement; the client attaches it to subsequent reads; any replica that receives it refuses to answer until its own l has reached that value. That yields read-your-writes and monotonic reads across a replica set with no sticky routing and no leader hop. MongoDB's $clusterTime and afterClusterTime read concern implement exactly this pattern.

Debugging distributed traces. With raw wall clocks, a child span routinely appears to start before its parent because the two hosts disagree by a few milliseconds, and engineers learn to distrust the timeline. Stamping spans with an HLC makes the ordering causally sound while keeping the value readable as a date, so a trace sorted by timestamp never shows an effect before its cause.

Operating it: monitoring and failure modes

The physical component has to come from the wall clock, not a monotonic counter, because a monotonic counter has no meaning across machines. That means the correctness of everything above rests on the synchronisation layer, and the health of that layer is now a first-class production signal rather than infrastructure trivia.

Three metrics are worth alerting on. The first is the offset your time daemon reports against its upstream, the standard measure. The second is better and almost free: export l - pt per node. That is the clock's own lead over local physical time, and it is a direct read of how far ahead the fleet's fastest clock is running — a value that starts climbing and does not fall back is the forward-jump poisoning described above, caught early. The third is the high-water mark of c, which surfaces both hot single-millisecond bursts and a stalled physical clock.

The failure modes that actually occur in production are mundane. A virtual machine that is live-migrated or heavily starved for CPU sees its clock freeze and then jump. A leap second handled by stepping the clock backwards is survivable — HLC absorbs it — while one handled by smearing is preferable, since neither direction of jump is introduced. Container hosts inherit their clock from a hypervisor that may not itself be disciplined.

Two implementation details are easy to miss. Persist l, or on restart initialise it from the highest timestamp already durable in the local store, otherwise a node that restarts with a lagging clock can mint timestamps below values it has already written. And stamp every RPC, not just replication traffic: heartbeats, gossip and health checks are what keep an idle cluster's clocks converged, and a node that talks to nobody is tracking only its own drifting pt.