Hybrid Logical Clock

ELI5

An HLC is a wristwatch with a tally counter on top. The watch face shows the wall clock; the tally bumps every time you record an event in the same millisecond. When you receive someone else’s note, you set your watch to whichever is later (yours or theirs) and bump the tally so two events never share a stamp.

Technical Deep Dive

Shape

HlcTimestamp { wall_time: i64 ms since epoch, counter: i32 } (relay/src/services/hlc.rs:14). Total order: lexicographic on (wall_time, counter).

Server Clock — now()

classDiagram
    class HlcTimestamp {
      +i64 wall_time
      +i32 counter
      +new(wall, counter) HlcTimestamp
      +now_millis() i64
    }
    class HlcClock {
      -AtomicI64 last_wall_time
      -AtomicI32 counter
      -i64 max_skew_ms
      +new() HlcClock
      +with_max_skew(ms) HlcClock
      +now() HlcTimestamp
      +receive(remote) Option~HlcTimestamp~
    }
    HlcClock --> HlcTimestamp : produces

now() reads physical time, then in a CAS loop:

• if physical time > last → (physical, 0),
• else → (last, last_counter + 1), and writes back atomically. Result: monotonic timestamps even under contention.

Receive Algorithm

sequenceDiagram
    autonumber
    participant Phys as physical_time
    participant Local as last_wall, last_counter
    participant Remote as remote.wall, remote.counter
    participant Out as new HLC
    Phys->>Out: read now_millis
    Remote->>Out: arrive
    Note over Out: if remote.wall > physical + max_skew_ms → reject (None)
    Out->>Out: max_wall = max(physical, last, remote.wall)
    alt physical is sole max
      Out->>Out: counter = 0
    else last == remote.wall == max_wall
      Out->>Out: counter = max(last_counter, remote.counter) + 1
    else last is max
      Out->>Out: counter = last_counter + 1
    else remote is max
      Out->>Out: counter = remote.counter + 1
    end
    Out-->>Local: CAS write

Default max_skew_ms is 60_000 ms (HlcClock::new()); excessive remote skew returns None and the caller rejects the operation.

Storage Encoding

HlcTimestamp::encode() flattens to a single i64 as wall_time * 1000 + (counter % 1000). Caveat: counters ≥ 1000 in the same millisecond lose precision on round-trip. In SQLite, hlc_timestamp and hlc_counter are stored as separate columns to avoid this exact loss (see relay/migrations/002_create_operations.sql).

Client HLC

ClientHlc (app/src/services/lseq.ts:307) is a single-threaded mirror with tick() and receive(remoteWall, remoteCounter). It does not enforce max_skew_ms; that check is server-side only.

Concurrency

HlcClock uses two AtomicI64/AtomicI32 fields. The now() and receive() methods loop on compare_exchange, so they are wait-free under low contention but can spin under heavy concurrent writers.

Key Terms

• counter → 32-bit logical tally bumped within the same wall millisecond; resets to 0 when wall time advances.
• encode() → lossy 64-bit packing intended for back-of-envelope storage; the production path stores the two fields separately.
• max_skew_ms → upper bound for trusting a remote wall time relative to local physical time; protects against malicious or buggy clients.

Q&A

Q: What if two operations arrive with identical (wall_time, counter)? A: The total order is still defined (they compare equal), but the server now()/receive() always produce strictly monotonic timestamps for its own events, so collisions only occur across nodes with truly equal wall+counter — practically rare.

Q: Does encode() round-trip safely for typical traffic? A: For counters < 1000 in the same ms, yes. Storage code stores both fields separately to be safe.

Q: What is the default skew tolerance? A: 60 seconds. Use HlcClock::with_max_skew(...) to override.

Examples

Two clients type “A” and “B” within the same millisecond. Client A sends (1700000000000, 0), client B sends (1700000000000, 1) after seeing A. The relay’s receive for B’s op resolves to (1700000000000, 2) (max counter + 1), guaranteeing strict ordering even though wall time tied.