Hybrid Logical Clock

A multi-region store resolves conflicting writes to the same key by comparing timestamps taken from each node's clock. One node's clock is 400 ms fast. Every write it makes wins every conflict it enters, and the symptom reported by users is that their edits silently disappear - no error, no log line, just a value that reverted.

The two classical answers each give up something important. Wall-clock timestamps are comparable, human-readable and comparable across systems, and they can order an effect before its cause. Lamport clocks and version vectors guarantee causal ordering and carry no relation to real time, so a timestamp cannot be shown in a log, compared with an external event, or used to answer "as of 14:00".

A hybrid logical clock keeps both properties. Each timestamp is a pair: a physical component tracked against the wall clock, and a logical counter that advances when the physical part cannot. On every send and receive, a node takes the maximum of its own physical reading and the one carried on the message; if they are equal, it increments the counter. The result is within the clock-offset bound of real time and monotonically increasing along every causal chain.

Why it matters

Any system that resolves conflicts, assigns commit order, or answers historical queries needs a timestamp that means two things at once: comparable to civil time and consistent with causality. Pick only the first and you lose edits to clock skew. Pick only the second and you cannot answer time-travel queries or correlate with anything outside the system.

The construction also changes what clock synchronisation is for. With an HLC, NTP quality sets how far timestamps can drift from real time, not whether ordering is correct - so a clock problem becomes a bounded degradation rather than a silent correctness failure.

Implementation patterns

• Carry the timestamp on every message - requests, responses, replication streams - because the clock only advances correctly if causal edges are observed. An HLC that is not propagated is just a wall clock.
• Bound the physical component. Refuse a message whose physical part exceeds local time by more than the configured maximum offset, and treat that as an error rather than adopting it: otherwise one node with a broken clock drags the whole cluster's timestamps forward and they never come back.
• Pair it with a drift guard, as the stores that use it do. CockroachDB's documented default treats 500 ms as the maximum offset and has a node shut itself down when it finds itself more than 80% of that away from half the cluster.
• Uncertainty intervals for reads. A read at timestamp T may encounter a write whose timestamp is within the uncertainty window, and the resolution is to restart the read at a higher timestamp - which is why clock skew shows up as a retry rate rather than as a wrong answer.
• Enough bits for the counter. A burst of events inside one physical tick advances the logical part, and the format must not overflow it.

Industry example

The construction is from Kulkarni, Demirbas and colleagues (2014), motivated explicitly by wanting Lamport-clock guarantees with timestamps that are still usable as time. CockroachDB and YugabyteDB both use hybrid logical clocks for transaction timestamps, and CockroachDB's documented behaviour makes the dependency concrete: a node whose clock drifts too far removes itself from the cluster rather than risk serving timestamps it cannot justify.

The contrast worth carrying is with Google's Spanner, which solves the same problem with hardware - atomic clocks and GPS receivers give a tightly bounded uncertainty interval, and commits wait out that interval. HLC is the software answer to the same question: accept a larger uncertainty bound and pay for it in read restarts rather than in commit waits.

Failure scenarios

• One node with a fast clock, whose timestamps are adopted by every peer it talks to, pulling the cluster's timestamps into the future permanently. Rejecting out-of-bound timestamps is the only defence.
• Drift beyond the configured bound, which turns into read restarts and then into a node removing itself - correct behaviour that looks like an availability incident.
• A node that is suspended and resumed with a stale clock, which believes it is in the past and produces timestamps that violate the bound on receipt.
• Treating the physical component as a trustworthy wall-clock time in business logic - it is within a bound of real time, not equal to it, and that difference matters for anything regulatory.
• Logical counter overflow in a hand-rolled implementation, which silently breaks ordering under bursts.

Trade-offs

When not to use it

If writes are single-homed - one leader per key, as in a sharded primary-replica design - commit order comes from the log and you do not need clock-derived ordering at all. Introducing an HLC where a single log already orders writes adds a dependency and solves nothing.

If the only requirement is to detect concurrent writes so the application can merge them, a version vector is simpler, needs no clock and does not fail when NTP does. And if the data is genuinely last-write-wins with no correctness consequence - a cache of presence information, a counter of views - the cheap wall-clock answer is proportionate.

Interview question

Q: A multi-region store resolves write conflicts with last-write-wins on each node's wall clock. Users report edits disappearing. Explain the mechanism to the engineer who built it, and propose a fix with its operational cost.

What a strong answer covers: skew means an effect can carry an earlier timestamp than its cause, so the "newer" write loses silently; the choice between version vectors (detect and merge, no clocks) and hybrid logical clocks (order, with a bounded clock dependency); propagation on every message; rejecting out-of-bound timestamps so one bad clock cannot poison the cluster; the monitoring and enforcement that must accompany it; and the recognition that single-homing the writes removes the problem entirely where the data model allows it.

Quick check

Quiz: What does the logical component of an HLC guarantee that the physical component cannot? That a cause is always stamped strictly before its effect, even when both occur inside the same physical clock tick or when the sender's clock is ahead.

Flashcard: How does a node update its HLC on receiving a message? It takes the maximum of its own physical reading and the message's, and increments the logical counter when they are equal - so the timestamp never goes backwards along a causal chain.