Hybrid logical clocks

Deep dive

How it works

In: local event or received timestamp (l_m, c_m), physical clock pt · Out: a new timestamp (l, c) larger than everything seen · State: one (l, c) pair, packed in a u64 · Cost: O(1), 8 bytes, order of 10-30 ns

State (l, c), physical clock pt.

1. Local or send: l' = max(l, pt); c = (l' == l) ? c + 1 : 0; l = l'.
2. Receive (l_m, c_m): l' = max(l, l_m, pt); c = max(c, c_m) + 1 if l' == l == l_m, c + 1 if only l' == l, c_m + 1 if only l' == l_m, else 0.
3. Packing (l << 16) | c into a u64, both rules become: new = max(old + 1, remote + 1, pt << 16).

Uncertainty (CockroachDB). A read at timestamp t that finds a value written in (t, t + max_offset] can't know whether that write happened before it in real time, so it restarts at a higher timestamp. Nodes whose clocks drift beyond the bound must stop serving, or reads can miss committed writes.

node A pt=100: write → (100,0) ─msg─► node B pt=98: recv → max((98,0),(100,1)) = (100,1)
node B next local event pt=99 → (100,2)    pt=101 → (101,0)

Code

use std::sync::atomic::{AtomicU64, Ordering};
use std::time::{SystemTime, UNIX_EPOCH};

const LOGICAL_BITS: u32 = 16;

#[derive(Debug)]
pub struct ClockSkew { pub remote_ms: u64, pub local_ms: u64 }

pub struct Hlc { state: AtomicU64, max_offset_ms: u64 }

#[inline] pub fn wall_ms(ts: u64) -> u64 { ts >> LOGICAL_BITS }
#[inline] pub fn logical(ts: u64) -> u64 { ts & ((1 << LOGICAL_BITS) - 1) }

fn physical_ms() -> u64 {
    SystemTime::now().duration_since(UNIX_EPOCH).unwrap().as_millis() as u64
}

impl Hlc {
    pub fn new(max_offset_ms: u64) -> Self { Hlc { state: AtomicU64::new(0), max_offset_ms } }

    /// Timestamp for a local event or an outgoing message.
    pub fn now(&self) -> u64 {
        let pt = physical_ms() << LOGICAL_BITS;
        // max(old + 1, pt): if wall time advanced, counter resets to 0; else counter += 1.
        let prev = self.state.fetch_update(Ordering::AcqRel, Ordering::Acquire,
                                           |old| Some((old + 1).max(pt))).unwrap();
        (prev + 1).max(pt)
    }

    /// Merge a timestamp received from another node.
    pub fn update(&self, remote: u64) -> Result<u64, ClockSkew> {
        let pt_ms = physical_ms();
        if wall_ms(remote) > pt_ms + self.max_offset_ms {
            // Accepting it would drag our clock beyond the skew bound for everyone.
            return Err(ClockSkew { remote_ms: wall_ms(remote), local_ms: pt_ms });
        }
        let pt = pt_ms << LOGICAL_BITS;
        let next = |old: u64| (old + 1).max(remote + 1).max(pt);
        let prev = self.state.fetch_update(Ordering::AcqRel, Ordering::Acquire,
                                           |old| Some(next(old))).unwrap();
        Ok(next(prev))
    }
}

/// Read-side uncertainty check for MVCC (CockroachDB style).
pub enum Visibility { Visible, Invisible, Uncertain }

pub fn classify(read_ts: u64, value_ts: u64, max_offset_ms: u64) -> Visibility {
    let limit = read_ts + (max_offset_ms << LOGICAL_BITS);
    if value_ts <= read_ts { Visibility::Visible }
    else if value_ts <= limit { Visibility::Uncertain }  // restart the read at value_ts
    else { Visibility::Invisible }
}

A 16-bit counter that overflows simply carries into l, moving it 1 ms ahead; with normal traffic c stays small because l resets it every millisecond.

Complexity and constants

• One atomic RMW per event: order of 10-30 ns uncontended including clock_gettime via vDSO (order of 20 ns).
• 8 bytes per timestamp; CockroachDB uses 64-bit wall nanos + 32-bit logical (12 bytes), MongoDB cluster time uses 32-bit seconds + 32-bit increment.
• NTP keeps datacenter clocks within order of 1-10 ms typically, worse under faults; PTP with hardware timestamping reaches order of µs.
• Uncertainty window = max offset: larger offset → more read restarts on contended keys.

Efficiency

• Cost: one atomic read-modify-write per event: order of 10-30 ns uncontended including clock_gettime via vDSO (order of 20 ns). 8 bytes per timestamp (CockroachDB: 12, MongoDB cluster time: 8). No messages beyond the timestamp already piggybacked. Bound: clock read and the atomic, not the network.
• Levers:
  • pack (l << 16) | c into one u64 — update becomes max(old + 1, remote + 1, pt << 16), one CAS loop — hot paths
  • read the physical clock via vDSO — no syscall, order of 20 ns — Linux servers
  • tighter clock sync (NTP order of 1-10 ms, PTP with hardware timestamps order of µs) — smaller max offset, fewer read restarts on contended keys — databases using uncertainty windows
  • keep timestamps small in messages (8 bytes) — negligible bandwidth — high-rate replication
• Naive → standard → state of the art:
  • central timestamp oracle · one network round trip per timestamp
  • Lamport clock · O(1), 8 bytes, but no relation to wall time
  • HLC (or TrueTime with commit-wait where bounded-uncertainty clocks exist) · O(1), 8 bytes, within skew of real time

Implementation notes

• Use the realtime clock (CLOCK_REALTIME), not monotonic, for pt, but never let the HLC go backwards when the wall clock steps back (the max handles it).
• Persist an upper bound (e.g. now + 1 s written every second) so a restarted node with a reset clock doesn't reissue old timestamps.
• Refuse or alarm on remote timestamps beyond max_offset; CockroachDB also measures offsets via RPC heartbeats and a node exits if its clock is off by more than 80 % of max offset from a majority.
• Choose the bit split for your write rate: 16 bits of counter = 65,536 events per ms per node before carrying.
• Comparing HLCs from different nodes as "real-time order" is only valid beyond the skew bound.

Pitfalls

• A single node with a fast clock (e.g. +1 h) drags every HLC it talks to forward permanently; reject via the max-offset check.
• Treating HLC order as linearizability: two writes within the skew window on different nodes may be ordered opposite to real time unless you use uncertainty restarts or commit-wait.
• Using the HLC for timeouts or leases: use the monotonic clock for durations.
• Truncating to 32-bit seconds loses ordering of events in the same second unless the counter is wide.

Variants and alternatives

In production

Databases: CockroachDB (hlc package, MVCC timestamps, uncertainty intervals), YugabyteDB (hybrid time), MongoDB (cluster time for causal consistency), Apache Kudu (HybridTime).

Implementations

Sources

• Sandeep Kulkarni, Murat Demirbas, Deepak Madappa, Bharadwaj Avva, Marcelo Leone, Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases, OPODIS 2014. paper · report
• James C. Corbett et al., Spanner: Google's Globally-Distributed Database, OSDI 2012. paper
• Rebecca Taft et al., CockroachDB: The Resilient Geo-Distributed SQL Database, SIGMOD 2020. paper
• Misha Tyulenev et al., Implementation of Cluster-wide Logical Clock and Causal Consistency in MongoDB, SIGMOD 2019. paper