vault

Hybrid Logical Clock

23 min read

Hybrid Logical Clock

Hybrid Logical Clock (HLC) is a distributed-systems clock construction that combines the physical wall-clock time of an operation with a logical Lamport-style counter to produce timestamps that are simultaneously close-to-real-time and causally consistent. Each timestamp is a pair (l, c) where l is the largest physical-clock reading observed at this node so far (its own clock or a peer’s clock learned from a message), and c is a small logical counter used to order events that happen “at the same physical millisecond.” The protocol is three rules: on a local event, the node reads its physical clock pt, sets the new l to max(pt, l_old) and increments c if l did not advance (else resets c to 0); on send, the node attaches its current (l, c) to the message; on receive with incoming (l_m, c_m), the node sets the new l to max(l_old, l_m, pt) and computes c based on which of the three was maximum (taking the existing c plus 1 if l_old won, taking c_m plus 1 if l_m won, resetting to 0 if pt won, breaking ties with max(c_old, c_m) + 1). Two HLC timestamps (l_a, c_a) < (l_b, c_b) lexicographically iff a → b (causally before), giving the same happens-before decidability as scalar Lamport clocks but with timestamps that track real time within bounded skew. HLC was published by Sandeep Kulkarni, Murat Demirbas, and colleagues at SUNY Buffalo at OPODIS 2014 (Logical Physical Clocks). It was designed to give Spanner-class external consistency (causal + physical-time-aware ordering) without Spanner’s hardware dependency on atomic clocks and GPS receivers (Google’s TrueTime, see Distributed SQL Database System Design). Production adopters include CockroachDB (explicitly built on HLC), YugabyteDB, and MongoDB (which uses an HLC-style cluster-time mechanism for causal consistency). HLC is now a foundational primitive of modern distributed SQL databases: any database wanting to provide snapshot reads, serializable transactions, and consistent backups across geographic distribution without paying for atomic-clock hardware uses HLC or a close variant.

1. Plain-Language Definition

A clock in a distributed system has two jobs that pull in opposite directions. It must capture causality — if event a caused event b, the timestamp of a should be strictly less than the timestamp of b — and it should approximate physical time — the timestamp should be close to the wall-clock time when the event occurred, so that humans can interpret it, log lines from different machines can be merged sensibly, and time-based queries (“show me everything from 14:00–14:05”) return the right rows.

Lamport’s scalar logical clock (1978) solves causality but ignores physical time: it is just a monotonically-increasing integer that bears no relationship to wall-clock time. A Lamport timestamp of 12345 doesn’t mean anything in seconds; you can’t compare it to 2026-05-09 14:00:00.000.

Vector Clocks also solve causality but produce timestamps of size O(N) for N nodes, growing without bound as the cluster scales. They also ignore physical time.

Physical wall-clock timestamps (just now()) approximate physical time but violate causality because clocks are not perfectly synchronized — a message can be sent at 14:00:00.100 from a node whose clock is fast and arrive at a node with a slow clock at “14:00:00.050” (50 ms in the past), making the receive look like it happened before the send. Pure physical timestamps cannot be trusted to order causally-related events.

Hybrid Logical Clock (HLC) is the engineering compromise that gets both. It is a clock that:

  • Looks like a physical timestamp to within a small bounded error (typically a few milliseconds, bounded by the Network Time Protocol sync error).
  • Strictly captures the happens-before relation: a → b ⟹ HLC(a) < HLC(b) lexicographically.
  • Costs only O(1) storage per timestamp (constant, regardless of cluster size, unlike vector clocks’ O(N)).
  • Requires no special hardware (no atomic clocks, no GPS receivers — software-only, runs on any commodity server with NTP).

That combination is what makes HLC interesting: it gives the causal correctness of Lamport, the size efficiency that vector clocks lack, and the human-interpretable physical-time alignment that pure logical clocks lack. The cost is a small bounded error from real time.

2. Mechanism — The Three Rules

Every node i maintains a local HLC state consisting of two numbers:

  • l_i — the largest “logical-physical” timestamp this node has observed (either its own physical clock or a peer’s, whichever was larger).
  • c_i — a small logical counter used to break ties within the same l.

Define pt_i to be the current reading of node i’s wall-clock (e.g., time.Now() in Go, gettimeofday() in C, System.currentTimeMillis() in Java).

Rule 1 — Local event (or send) at node i. The node generates a fresh HLC timestamp:

l_old := l_i
l_i := max(l_old, pt_i)
if l_i == l_old:
    c_i := c_i + 1            # physical clock didn't advance; bump logical counter
else:
    c_i := 0                  # physical clock advanced; reset logical counter
return (l_i, c_i)

The intuition: if the physical clock has moved forward since the last HLC reading, use the new physical value and reset the logical counter to 0. If the physical clock hasn’t moved (because two events happen within the same clock tick, which is very common at high event rates), keep the old l and increment the logical counter to give this event a strictly-larger HLC than the previous one.

Rule 2 — Send. Send is just Rule 1 followed by attaching the resulting (l, c) to the outgoing message.

Rule 3 — Receive at node i of message with timestamp (l_m, c_m). The node reconciles its own (l_i, c_i) with the sender’s (l_m, c_m):

l_old := l_i
l_i := max(l_old, l_m, pt_i)
if l_i == l_old and l_i == l_m:
    c_i := max(c_i, c_m) + 1     # all three matched; combined logical counter
elif l_i == l_old:
    c_i := c_i + 1               # local was the largest
elif l_i == l_m:
    c_i := c_m + 1               # remote was the largest
else:
    c_i := 0                     # physical clock won; reset logical counter
return (l_i, c_i)

The key invariant: after Rule 3, the new (l_i, c_i) is strictly greater than both (l_old, c_old) (the receiver’s previous state) and (l_m, c_m) (the sender’s state) under lexicographic ordering. This is the property that gives HLC its causal correctness.

sequenceDiagram
    participant A as Node A (clock: 100)
    participant B as Node B (clock: 102, 2ms ahead)
    Note over A: pt=100, send msg<br/>HLC = (100, 0)
    A->>B: msg with (100, 0)
    Note over B: receive: pt=102<br/>l = max(l_B_old, 100, 102) = 102<br/>c = 0 (physical won)<br/>HLC = (102, 0)
    Note over B: local event<br/>pt=102, l unchanged<br/>c = 1<br/>HLC = (102, 1)
    B->>A: msg with (102, 1)
    Note over A: receive: pt=101<br/>l = max(101, 102, 101) = 102<br/>c = c_m + 1 = 2<br/>HLC = (102, 2)

The diagram traces a 3-event sequence: A sends to B, B has a local event, B sends to A. Even though A’s wall clock (100, then 101) lags B’s wall clock (102) by 1–2 ms, the HLC produces a strictly-monotonic, causally-correct sequence: (100,0) < (102,0) < (102,1) < (102,2). The l component tracks the larger of the two clocks and is bounded above by the maximum across the cluster; the c component handles the within-millisecond ties that physical time cannot resolve.

3. Origins — Kulkarni et al. 2014

HLC was published by Sandeep Kulkarni, Murat Demirbas, Deepak Madappa, Bharadwaj Avva, and Marcelo Leone at SUNY Buffalo, in the OPODIS 2014 paper Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases. The paper’s framing is explicit: HLC is designed for the use case where you need both causality (like Lamport / vector clocks) and a relationship to wall-clock time (like Spanner’s TrueTime), but you cannot afford TrueTime’s hardware dependency.

The paper’s contributions are: (1) the algorithm above, including the proof that the HLC’s l component is bounded above by max_i pt_i + ε where ε is the maximum clock skew across the cluster (i.e., HLC stays close to wall time); (2) the proof that HLC strictly captures happens-before; (3) the proof that HLC is O(1) per timestamp; (4) demonstration of how HLC enables consistent snapshot reads and serializable transactions in a globally-distributed database without requiring atomic-clock hardware.

The intellectual lineage runs from Lamport 1978 (scalar logical clocks for causality, no physical time) → Mattern 1989 / Fidge 1988 (vector clocks for full partial-order reconstruction, no physical time, O(N) size) → Spanner 2012 (Corbett et al., TrueTime API using atomic clocks and GPS to bound clock uncertainty, expensive hardware) → HLC 2014 (Kulkarni et al., software-only approximation of TrueTime’s properties using NTP-synchronized clocks plus Lamport-style counters). The HLC paper explicitly positions itself as the answer to “can we build a globally-distributed transactional database without TrueTime?“

4. Comparison with Vector Clocks

Vector Clocks capture the full happens-before partial order: given two vector timestamps, you can determine whether a → b, b → a, or a ∥ b (concurrent). This requires O(N) storage per timestamp for N nodes — every timestamp carries one integer per node. Vector clocks cannot be compressed; the size grows with cluster size, which becomes prohibitive at scales of thousands of nodes.

HLC sacrifices the full partial-order reconstruction for O(1) size. With HLC you can determine a → b ⟹ HLC(a) < HLC(b), but the converse is not guaranteed: HLC(a) < HLC(b) does not imply a → b — the events might be concurrent but happen to have been ordered by HLC’s lexicographic tiebreaker. This is the same limitation as Lamport scalars: HLC gives a total order consistent with causality, not the full causal partial order. For most use cases (especially database transactions), the total order is exactly what you want — a transaction needs a single commit timestamp, not a list of vector components.

The choice between HLC and vector clocks is therefore: do you need to detect concurrency (Dynamo-style sibling reconciliation, OR-Set CRDTs)? If yes, vector clocks. Do you need a causal total order with physical-time alignment for transaction commit ordering? If yes, HLC. Most modern transactional systems pick HLC; most CRDT-heavy systems pick vector clocks (or a refinement like dotted version vectors).

5. Comparison with Spanner’s TrueTime

Google Spanner (Corbett et al. OSDI ‘12) achieves external consistency — the property that if transaction T1 commits before transaction T2 starts in real time, then T1’s commit timestamp is less than T2’s commit timestamp — using the TrueTime API. TrueTime exposes now() not as a single timestamp but as an interval [earliest, latest] representing the bounded uncertainty in physical time. Spanner machines are equipped with atomic clocks and GPS receivers that keep the uncertainty interval narrow (typically 1–7 ms). Spanner’s commit protocol enforces external consistency by waiting out the uncertainty: after assigning a commit timestamp, the coordinator waits until TT.now().earliest > commit_ts, ensuring that any later transaction will see a strictly-later timestamp.

HLC achieves a weaker but operationally similar property using only NTP-synchronized clocks (no atomic clocks, no GPS). The HLC l component plays the role of TrueTime’s “current time” reading, and the c component handles the within-tick ordering that TrueTime would handle by waiting out uncertainty. The trade-off is:

  • TrueTime gives bounded uncertainty (the interval is small and known) and external consistency (real-time order respected).
  • HLC gives causally consistent timestamps that are close to wall time but cannot be guaranteed to respect real-time order between non-causally-related transactions on machines with skewed clocks.

In practice, HLC’s weaker guarantee is sufficient for many use cases (snapshot reads, serializable transactions when paired with consensus like Raft) and dramatically cheaper. Spanner’s external consistency is needed when the database is the authoritative source of truth for real-world time-ordered events (e.g., financial trades, regulatory audit logs); HLC suffices when the database itself defines the order.

6. Worked Example — 3-Node Database with Skewed Clocks

Consider a 3-node distributed key-value database (nodes A, B, C) with the following clock skew:

  • A’s wall clock is correct.
  • B’s wall clock is 2 seconds ahead of true time.
  • C’s wall clock is 1 second behind true time.

This is significant skew — modern NTP keeps clocks within tens of milliseconds — but illustrates the algorithm clearly. Suppose:

  • True-time 100.000s: client writes x=1 to A. A’s clock reads 100.000. A’s HLC: (100.000, 0).
  • True-time 100.001s: A asynchronously replicates x=1 to B. B’s clock reads 102.001 (2s ahead). On receive, B computes l = max(l_B_old, 100.000, 102.001) = 102.001 — B’s local clock is the maximum because B is fast. c = 0 (physical won). B’s HLC: (102.001, 0). B writes x=1 durably with this timestamp.
  • True-time 100.002s: a different client reads x from C. C’s clock reads 99.002 (1s behind). C does not yet have the replicated x=1. C returns the old value x=0 (or “not found”).
  • True-time 100.003s: A asynchronously replicates x=1 to C. C’s clock reads 99.003. On receive, C computes l = max(l_C_old, 100.000, 99.003) = 100.000 — A’s HLC value wins because both C’s local HLC and C’s wall clock are smaller. c = 1 (l matched l_m, increment c_m). C’s HLC: (100.000, 1). C writes x=1 durably with this timestamp.
  • True-time 100.004s: a client now reads x from B. The read carries no HLC (this is a fresh client). B returns x=1 with HLC (102.001, 0).
  • True-time 100.005s: the same client reads x from C. The client passes the previously-seen HLC (102.001, 0) (this is causal consistency: the client says “I already saw timestamp ≥ (102.001, 0), don’t return anything older”). C compares its current HLC (100.000, 1) to the requested (102.001, 0). C’s HLC is less than what the client requires. C must either wait until its HLC catches up to (102.001, 0), fetch the requested key from a peer at the required HLC, or return an error. This is how HLC enables causal consistency for clients.

Two observations from this example:

First, despite B being 2 seconds ahead of true time, the HLC correctly preserves the causal order: A’s write happened before B replicated it, and HLC’s l component records this fact (the value passed from A to B was 100.000; B’s HLC becomes 102.001 only because B’s local clock is the maximum, not because of any replication ordering). The causal relationship A's write → B's replication is preserved: (100.000, 0) < (102.001, 0) lexicographically.

Second, the HLC’s l value at B (102.001) is bounded by max-cluster-clock, not by an unbounded counter. If B’s clock were to go backward (NTP step adjustment or operator intervention), the HLC l would not decrease — it would stay at 102.001 (because of the max in Rule 1) and c would increment for subsequent events until B’s wall clock caught up again. This is the source of one of HLC’s key practical properties: HLC is monotonic even when wall clocks regress, which is critical for transaction-ordering correctness.

7. Variants and Implementations

CockroachDB. Uses HLC as its primary clock, documented explicitly in Living without atomic clocks. CockroachDB reads NTP-synchronized clocks and configures a maximum acceptable clock-offset bound (default 500 ms in production, configurable). If a node’s clock offset from peers exceeds the bound, the node self-terminates — it is unsafe to participate in HLC-coordinated transactions when the assumption of bounded skew is violated. This self-termination is a critical safety property; without it, a node with a runaway clock would issue HLC values far in the future, polluting the cluster’s HLC state.

YugabyteDB. Also uses HLC, derived from the same paper. YugabyteDB’s transactions overview documents the integration of HLC with Raft-replicated tablets to achieve serializable cross-shard transactions.

MongoDB. Implements an HLC-style mechanism called cluster_time for causal consistency (Causal Consistency Spec). The cluster_time is signed (HMAC-SHA1) to prevent clients from injecting fabricated timestamps that would manipulate snapshot reads. The signing detail is an important production hardening that the original HLC paper does not discuss.

Antidote / RedisGraph / etc. A number of research and production systems have adopted HLC or close variants for their snapshot-read implementations. The pattern has become a default for transactional distributed databases that don’t have access to TrueTime hardware.

Bounded HLC. One common practical variant caps the size of c (e.g., c < 2^16) and refuses to advance the HLC beyond the bound. This protects against a degenerate case where the physical clock stalls for a very long time and c grows arbitrarily; in production, a clock that has stalled for that long is itself an incident that should be detected and addressed, so refusing to advance is the right behavior.

HLC + bounded uncertainty (HLC-U). Recent research (post-2014) has explored adding an uncertainty interval to HLC to recover some of TrueTime’s properties without atomic clocks, by using NTP’s reported uncertainty instead. This is a topic of ongoing work; production systems generally use plain HLC.

8. Real-World Examples

CockroachDB transactions. When a CockroachDB transaction begins, it acquires an HLC-derived read timestamp (the snapshot it will read from). Reads at that timestamp see a consistent snapshot — every committed transaction with HLC less than the read timestamp is visible; every later one is not. Writes happen at a commit timestamp, also HLC-derived, and Raft groups serialize the writes within a range. The combination of HLC + Raft achieves serializable isolation across the cluster, with HLC providing the inter-shard ordering and Raft providing the intra-shard linearizability. See Distributed SQL Database System Design for the full architecture.

YugabyteDB DocDB. Same pattern: HLC for inter-shard ordering, Raft for intra-shard. YugabyteDB documentation calls out HLC by name and notes that consistent backups depend on HLC’s bounded-skew property.

MongoDB causal consistency. MongoDB clients can specify readConcern: {level: "majority"} with a clusterTime to get causal consistency: subsequent reads will see at least the writes corresponding to the requested cluster_time. This is exactly the “C reads with previously-seen HLC” pattern from the worked example above. MongoDB’s clusterTime is HMAC-signed to prevent forgery.

MongoDB sessions and operationTime. MongoDB sessions track an operationTime (the HLC of the most recent operation in the session); subsequent operations in the session can causally chain via this value. This enables “read your writes” consistency without forcing all reads through the primary.

9. Tradeoffs

Bounded skew dependency. HLC’s correctness depends on the assumption that wall clocks across the cluster stay within some bounded skew ε. If ε is violated (e.g., NTP is broken on some node), the HLC l value can run far ahead of physical time, and the protocol’s monotonicity guarantees still hold — but the HLC stops being close to wall time, which breaks the property that makes HLC useful for human-interpretable timestamps and time-based queries. CockroachDB’s self-termination on out-of-bound clocks is the correct response to skew-bound violations; systems that don’t enforce this are vulnerable to clock-runaway scenarios.

O(1) but not full partial order. HLC compresses causality into a scalar (well, a pair), losing the ability to detect concurrency. For systems that need to detect concurrent updates and reconcile (Dynamo-style sibling resolution, OR-Set CRDTs, Git-style merge), vector clocks remain necessary. HLC is for systems that want a single global commit order, not for systems that need to track parallel branches of history.

Linearizability requires consensus. HLC does not provide linearizability across nodes — it provides causal-consistent ordering of events that have flowed through the system. To get linearizability (e.g., serializable transactions across multiple shards), HLC must be combined with a consensus protocol like Raft (within each shard) plus an inter-shard coordination mechanism. CockroachDB and YugabyteDB both do this. HLC alone is the clock; the transaction system is HLC + Raft + a transactional protocol.

Logical counter c growth. If the physical clock stalls (e.g., the host is suspended or NTP regresses), c will grow with each event. In well-behaved production environments, this is bounded — physical time advances continuously, so c resets to 0 frequently. In pathological cases, c can grow without bound; production implementations cap c and treat overflow as an incident. The cap is typically set high enough (e.g., 2^16) that overflow signals real abuse rather than normal operation.

10. Pitfalls

Unbounded clock skew breaks HLC. HLC’s safety properties (lexicographic ordering captures causality) hold regardless of skew; HLC’s liveness properties (timestamps stay near wall time) require bounded skew. A common production failure: NTP is misconfigured on a single node, that node’s clock drifts hours into the future, the node generates HLC values hours ahead of its peers, those values propagate via replication, and now the entire cluster’s HLC is hours ahead of wall time. Until the offending node’s clock is corrected (and the cluster’s HLC waits for wall time to catch up), the cluster cannot accept new writes that would correctly order with respect to wall time. The cure: monitor NTP sync status across all nodes (Network Time Protocol integration is mandatory), self-terminate nodes whose skew exceeds the configured bound, alert on any HLC l value running materially ahead of wall time.

Logical counter overflow. If the physical clock stalls (suspend-resume on a VM, NTP step adjustment that pushes the clock backward), c can grow unbounded as events accumulate at the same l. Production caps c and rejects further events when the cap is hit. The cap is typically large enough (e.g., 2^16 or 2^32) that hitting it requires a pathological scenario (tens of thousands of events within a single physical millisecond), but the cap must be there. Hitting the cap should trigger an alert; the response is typically to reset the affected node’s clock and let HLC re-synchronize.

HLC alone does not give linearizability. A common interview misconception: “We’re using HLC, so our transactions are linearizable.” HLC only orders events that have flowed through the system; it does not coordinate concurrent transactions on different nodes. Two concurrent writes to the same key on two different shards may be assigned HLC values that order them, but the question of which write wins is decided by the consensus protocol layered on top. Without consensus (typically Raft or Paxos), HLC gives only causal consistency, not strong consistency. The full stack is HLC + Raft + transactional protocol, not HLC alone.

Treating HLC timestamps as wall time. Because HLC’s l component is close to wall time, engineers sometimes use HLC values directly as if they were wall-clock timestamps for time-based queries, log filtering, billing periods, etc. This usually works but can fail subtly in two cases: (1) when a node’s clock is briefly skewed forward, the HLC l jumps and stays elevated even after the clock recovers, so a “between 14:00 and 14:05” query may include events whose actual wall time was earlier; (2) when c is non-zero, two events with the same l are ordered by c rather than by their actual wall-clock micro-difference. For most uses this is fine; for forensic or regulatory time-ordering, use a separate physical-time field.

Persisting HLC across restarts. A node restart that doesn’t persist its HLC state will start with l = 0, then the first incoming message or local event will set l to either the incoming peer’s l or pt, whichever is larger. This is usually fine — the node will catch up to the cluster’s HLC on its first interaction. But there is a brief window between restart and first interaction in which the node’s HLC is artificially behind; if the node starts serving reads in that window, it could return data older than its previous state’s reads. Cure: persist the HLC l (and optionally c) on every commit, restore on restart. CockroachDB and YugabyteDB both do this.

Forgetting to sign HLC values in adversarial environments. A client that fabricates an HLC value can manipulate snapshot reads (claim “I saw timestamp T”, forcing the database to wait for or reject the read). MongoDB’s HMAC-signed cluster_time is the production answer: only the database can issue cluster_time values, and clients must echo them back unforged. Systems that pass HLC to untrusted clients without signing are vulnerable to this attack; the fix is to sign or to wrap HLC in a session-local opaque token.

11. Interview Discussion

In a system-design interview, HLC comes up when discussing distributed databases, snapshot isolation, causal consistency, or “how do we order events without a global clock and without TrueTime.” A strong answer starts: “I’d use Hybrid Logical Clocks. Each node combines its NTP-synchronized wall-clock reading with a small logical counter. On every event, you take max(local, peer, wall) for the physical part and bump the counter for tiebreaking. This gives you O(1) timestamps that are causally correct and close to wall time.” Naming Kulkarni 2014 as the source (Logical Physical Clocks) is a strong signal.

Common follow-ups: “Why not use vector clocks?” — vector clocks are O(N) and grow with cluster size; HLC is O(1). Vector clocks detect concurrency; HLC gives a total order. Most transactional databases want the total order. “Why not use TrueTime like Spanner?” — TrueTime requires atomic clocks and GPS receivers; HLC is software-only. The trade is weaker (HLC doesn’t provide external consistency without consensus on top), but it’s free. “What if a node’s clock is way off?” — HLC’s safety holds regardless of skew, but liveness and “close-to-wall-time” properties require bounded skew. CockroachDB self-terminates nodes whose skew exceeds a configured bound (e.g., 500 ms); other implementations alert and quarantine. “Does HLC give linearizability?” — no, it gives causal consistency. Linearizability requires combining HLC with a consensus protocol like Raft.

A weak candidate confuses HLC with TrueTime, claims “HLC is just a logical clock” without distinguishing it from Lamport, or proposes HLC as a substitute for consensus. The interview is testing whether the candidate can place HLC correctly in the stack: it is the clock, not the transaction system; the transaction system needs HLC plus consensus plus a protocol.

Cross-references: HLC’s predecessors are Vector Clocks (which it improves on for size) and Lamport scalars (which it improves on for time alignment); its dependency is Network Time Protocol (which provides the bounded-skew assumption); its consumer is Distributed SQL Database System Design (which uses HLC for snapshot isolation); its complement is Raft (which provides linearizability where HLC provides causality). For the broader story of why distributed clocks are hard, see the Vector Clocks note.

12. See Also

Graph View

Backlinks