Hybrid Logical Clocks: Physical Time With a Logical Counter

A system that needs causal order and also wants its timestamps to look like dates has two obvious options, and both are unsatisfying. A Lamport clock gives order but its values bear no relation to physical time, so a timestamp of 4001 says nothing about when the event happened. A wall clock gives a recognizable date but orders events incorrectly whenever the clocks disagree. Hybrid logical clocks are the construction that gets most of both: the timestamp is a pair of a physical reading and a small counter, it is always close to real time, and it still respects happens-before.

The pair and the invariant

An HLC timestamp is (l, c), where l is a physical-time component and c is a counter. The pair is compared lexicographically: first l, then c. The design maintains an invariant that connects the pair to the local physical clock reading pt: the logical component never falls behind the physical clock, so l ≥ pt, and it never runs far ahead of it either, so l - pt ≤ ε for some bounded ε.

The first part of the invariant keeps the timestamp from being stale relative to the machine’s own clock. The second keeps it a usable approximation of the real instant. The bound ε is a property of the implementation and the clock quality, not of the algorithm; a system with well-synchronized clocks keeps ε small, and the whole point of the construction is that the causal guarantee is maintained by the algorithm rather than assumed about the clocks.

The state is one pair per process, not a vector. That is the significant economy: HLCs give the full happens-before guarantee of a Lamport clock, in a constant-size timestamp, while staying close to physical time.

The send and receive rules

The update rules are a refinement of Lamport’s. On a local event or a send, the process reads the physical clock pt; on receipt of a message carrying (lm, cm), it merges before applying the local step.

def local_event(l, c, pt):
    """Stamp a local event; pt is the current physical reading."""
    l_new = max(l, pt)
    # the counter only advances when the physical clock has not moved
    return (l_new, 0) if l_new > l else (l_new, c + 1)

def receive(l, c, pt, lm, cm):
    """Merge an incoming stamp, then stamp the receive itself."""
    l_new = max(l, lm, pt)
    if l_new == l == lm:
        c_new = max(c, cm) + 1
    elif l_new == l:
        c_new = c + 1
    elif l_new == lm:
        c_new = cm + 1
    else:
        c_new = 0            # the local physical clock is strictly greatest
    return (l_new, c_new)

The receive rule is the whole mechanism. Four cases matter. When the local and remote l agree and both dominate the physical clock, the counters are merged and incremented, which orders the receipt after both the send and any local event at the same l. When only the local l dominates, the counter increments. When the remote l dominates, the counter is set just above the remote counter. When the physical clock strictly dominates both, the counter resets, and the timestamp is a plain physical reading.

The counter field is 32 bits in most implementations, and the reason is that it only increments while the physical clock is not advancing past l — the window where several events happen inside one clock tick, or where a message arrives from a peer slightly ahead. A counter overflow is treated as a fault that forces resynchronization, because it means the physical component has been stuck for an implausibly long time.

Why the counter is usually zero

The interesting property of the scheme is that the counter is zero for most timestamps. Whenever the local physical clock has advanced since the last event, l is set to the physical reading and c is reset. On a host with microsecond-resolution clocks and events separated by more than a microsecond, every timestamp is a pure physical reading.

The counter becomes nonzero in three situations: several events within one clock tick, a receive from a peer whose l is ahead of the local physical clock, and a receive from a peer whose l equals the local one. The first is a throughput effect; the second is a clock skew effect; the third is a coincidence. In all three, the counter does the ordering work that the physical component cannot, and the pair still sorts close to the real time because l is the maximum of the participating physical readings.

The consequence for a reader of a log is that HLC timestamps look like timestamps with occasional small increments. The sorting is close to chronological, and the causal order is exact. That combination is why the scheme is used in systems that expose a timestamp to users: the value is meaningful as a date and still correct as a causal marker.

The bound, and what it does not guarantee

The ε bound is a property of the pair (l, c) relative to the true physical instant, and it holds only while the physical clocks are within some error of each other. If a peer’s clock is ahead by a large amount, a message from it pushes the receiver’s l forward, and the receiver’s subsequent timestamps are ahead of its own physical clock by that amount. The bound grows to the size of the skew, and it stays there until the local physical clock catches up.

This is not a flaw; it is the design’s honest accounting. An HLC does not make a badly synchronized clock good. It makes the ordering correct regardless of the skew, and it keeps the timestamp within the skew of real time. The size of the skew is still the thing that determines whether the timestamp is useful as a date, and a system that needs the timestamp to be accurate to a millisecond still needs the clocks to be synchronized to a millisecond.

The second limitation is that the pair is a total order, not a partial one. Two HLC timestamps are always comparable, and the comparison is consistent with causality, but a comparison that says a < b does not establish that a → b. Concurrent events receive distinct timestamps, ordered by the physical component and then by the counter, and the order is arbitrary among them. This is the same loss as in a scalar clock, and the reason HLCs are used for ordering and versioning rather than for conflict detection. A system that must know whether two writes were concurrent needs a vector or a version vector, as in Vector Clocks and the Detection of Concurrency.

Packing the pair into one integer

The pair does not have to travel as two fields. A common encoding packs the physical component in milliseconds into the high bits of a 64-bit integer and the counter into the low bits, for example 48 bits of milliseconds and 16 bits of counter. The packed value compares as an ordinary unsigned integer, so an index can be a plain B-tree key and no comparator needs to know about the two components.

The split has to be chosen against the lifetime of the system. Forty-eight bits of milliseconds covers roughly 8,900 years from an epoch, which is enough. Sixteen bits of counter allows 65,535 events inside one millisecond before the counter would overflow into the physical field, and an overflow that silently carries into the millisecond bits is worse than an error, because it produces timestamps that look valid and are wrong. Implementations therefore check the counter against the mask before packing and treat exhaustion as a fault that forces a wait for the next millisecond or a resynchronization.

The alternative is a 12-byte encoding with a full 64-bit physical value and a 32-bit counter, which removes the packing arithmetic at the cost of a wider key. The trade is the usual one: bytes in every index entry against a comparison that is a subtraction.

Snapshot reads without a global clock

One of the practical uses of a bounded HLC is consistent snapshot reads. If every node’s timestamp is within ε of real time, a reader that has a timestamp T can be sure that any write with a timestamp below T - ε is visible at every node whose clock is within the bound, because that write’s physical component is definitely in the past everywhere. Waiting for the bound to elapse before serving a read at T gives a snapshot that is consistent across nodes without a centralized sequencer.

The wait is the cost. A read at the current time must be delayed by ε, and the read latency therefore includes the clock bound. Systems that need low read latency reduce ε by tightening synchronization, which is a hardware and network cost, or accept stale reads, which is a semantic cost. The trade is the same one made by TrueTime, discussed in Bounded Clock Uncertainty and Commit-Wait, with a different mechanism for establishing the bound and a much smaller value for it.

HLCs occupy a useful middle position in the family of clocks: cheaper than a vector, more informative than a scalar, and closer to physical time than either. The mechanism is small enough to implement in a page, and the properties are strong enough that the remaining design question is only how tight the physical bound can be made.