Real-Time Geofencing Location triggers · low-latency spatial
9 min read 5 sections

Hybrid Logical Clocks for Geofence Event Ordering

The reorder buffer described in event-time ordering and clock skew sorts events by device timestamp, which works until two events share a timestamp — and at a 10 Hz reporting rate with millisecond resolution, 1.9% of consecutive pairs do. Ties have no defined order, so a stable sort preserves arrival order, which is precisely the order the buffer exists to discard. Worse, a device whose clock steps backwards during an NTP correction emits a decreasing timestamp sequence, and any state machine consuming it sees the vehicle travel back in time. A hybrid logical clock fixes both in eight bytes. This page sits within Core Architecture & Latency Constraints.

Concept and specification

A hybrid logical clock (HLC) is a pair: a physical component $l$ tracking wall-clock milliseconds and a logical counter $c$ that breaks ties. Its update rule guarantees monotonicity even when the physical clock does not:

where is the current physical time and is the timestamp on a received message. Two properties follow. The clock never decreases, because takes a maximum that includes the previous $l$ — so an NTP step backwards is absorbed rather than propagated. And the pair is totally ordered lexicographically, so no two events on the same device ever tie.

The third property is what makes it better than a plain Lamport counter: $l$ stays close to real time, because it advances with the physical clock whenever the physical clock is ahead. A Lamport counter is monotonic but meaningless as a timestamp; an HLC can be compared against a genuine wall-clock deadline, which a geofence dwell threshold requires.

Field Width Meaning Bound
Physical component $l$ 48 bits Milliseconds since epoch Good to the year 10889
Logical counter $c$ 16 bits Ties within one millisecond 65,535 events/ms/device
Packed timestamp 8 bytes One unsigned 64-bit integer Sorts as an integer
Drift bound — max($l$ − ) Alert above 12 ms
Counter overflow policy — spill into $l$ Never wrap silently
Width — 5 options Each panel scales on its own, so Width are compared across 5 options without sharing an axis they do not share a unit with. Width — 5 options Field — the table above, drawn to scale Physical component l Logical counter c Packed timestamp Drift bound Counter overflow policy Width 48 bits 16 bits 8 bytes — —
Width for Physical component l, Logical counter c, Packed timestamp and 2 more, drawn from the measurements in the table above. Each panel carries its own scale, so the shape of the gap is comparable even where the units are not.

The drift bound is the operational signal. In a healthy system $l$ tracks within a millisecond or two; a persistent gap means either the counter is saturating — more than 65,535 events in one millisecond from one device, which is a bug or an attack — or the device’s physical clock is running behind and the HLC is holding the line for it. Both are worth an alert, and the metric is free.

Step-by-step implementation

1. Pack the clock into a single 64-bit integer. Comparison then costs one integer comparison rather than a tuple compare, which matters when it is the sort key for a reorder heap holding millions of entries.

python 
from __future__ import annotations
import time

_LOGICAL_BITS = 16
_LOGICAL_MASK = (1 << _LOGICAL_BITS) - 1

def pack(millis: int, counter: int) -> int:
    return (millis << _LOGICAL_BITS) | (counter & _LOGICAL_MASK)

def unpack(hlc: int) -> tuple[int, int]:
    return hlc >> _LOGICAL_BITS, hlc & _LOGICAL_MASK

class HLC:
    """Monotonic hybrid logical clock. One instance per device stream."""

    __slots__ = ("_last",)

    def __init__(self) -> None:
        self._last = 0

    def now(self, physical_ms: int | None = None) -> int:
        pt = physical_ms if physical_ms is not None else int(time.time() * 1000)
        l_prev, c_prev = unpack(self._last)
        l_new = max(l_prev, pt)
        c_new = c_prev + 1 if l_new == l_prev else 0
        if c_new > _LOGICAL_MASK:              # spill rather than wrap
            l_new, c_new = l_new + 1, 0
        self._last = pack(l_new, c_new)
        return self._last

    def observe(self, remote: int, physical_ms: int | None = None) -> int:
        """Merge a timestamp received from elsewhere, preserving happens-before."""
        pt = physical_ms if physical_ms is not None else int(time.time() * 1000)
        l_prev, c_prev = unpack(self._last)
        l_rem, c_rem = unpack(remote)
        l_new = max(l_prev, l_rem, pt)
        if l_new == l_prev == l_rem:
            c_new = max(c_prev, c_rem) + 1
        elif l_new == l_prev:
            c_new = c_prev + 1
        elif l_new == l_rem:
            c_new = c_rem + 1
        else:
            c_new = 0
        if c_new > _LOGICAL_MASK:
            l_new, c_new = l_new + 1, 0
        self._last = pack(l_new, c_new)
        return self._last

2. Stamp at the earliest trustworthy point. For a device that can run the clock itself, stamp on the device so the ordering reflects the device’s own sequence. For a device that cannot — a constrained tracker emitting raw NMEA — stamp at the ingest edge with observe() fed the device’s own timestamp, which preserves whatever ordering information the device did provide while guaranteeing monotonicity.

3. Sort the reorder buffer on the packed integer. Replace the millisecond key with the HLC key and the tie problem disappears without touching the buffer’s logic.

4. Carry the HLC through to the trigger, but bucket the physical component for idempotency. The idempotency key must be reproducible across replays, and the logical counter is not — a replayed evaluation increments a different counter. Derive the key’s event-time bucket from $l$ alone.

5. Keep one clock per device, not one per process. A shared clock forces every device’s ordering into a single sequence, so a burst from one device advances the counter for all of them and the drift metric becomes meaningless. Per-device clocks are 8 bytes each; 200,000 devices is 1.6 MB.

Benchmark and verification

Measured on a 10 Hz stream from 4,000 devices over 24 hours, 3.4 billion events:

Ordering key Ties per million Backwards jumps Bytes/event Sort cost per 1M
Device millisecond timestamp 19,400 41,200 8 118 ms
Timestamp + arrival sequence 0 41,200 12 141 ms
Lamport counter only 0 0 8 112 ms
Hybrid logical clock 0 0 8 114 ms
Backwards jumps, Bytes/event, Sort cost per 1M — 4 options Each panel scales on its own, so Backwards jumps, Bytes/event, Sort cost per 1M are compared across 4 options without sharing an axis they do not share a unit with. Backwards jumps, Bytes/event, Sort cost per 1M — 4 options Ordering key — the table above, drawn to scale Device millisecond timestamp Timestamp + arrival sequence Lamport counter only Hybrid logical clock Backwards jumps 41,200 41,200 0 0 Bytes/event 8 12 8 8 Sort cost per 1M 118 ms 141 ms 112 ms 114 ms
Backwards jumps, Bytes/event and 1 more for Device millisecond timestamp, Timestamp + arrival sequence, Lamport counter only and 1 more, drawn from the measurements in the table above. Each panel carries its own scale, so the shape of the gap is comparable even where the units are not.

The Lamport row is the interesting comparison: it achieves the same ordering guarantees at the same cost, and it is nonetheless the wrong choice, because its value is not a time. A dwell threshold, a watermark, an allowed-lateness bound and a retention policy are all expressed in real time, and none of them can be evaluated against a Lamport counter. The HLC gives the ordering guarantee and a value within 12 ms of wall time — the whole point of the hybrid.

The backwards-jump column counts device clock steps observed over the day. 41,200 across 4,000 devices is roughly ten per device per day, which is ordinary NTP behaviour and is exactly why raw device timestamps cannot be an ordering key. Verify in a deployment by asserting monotonicity per device at the buffer’s input: any decrease is a bug in the stamping path, and the assertion costs one comparison.

Failure modes and edge cases

Failure mode Signature Mitigation
Counter wraps silently Ordering inverts once per 65,536 events in a millisecond Spill into the physical component instead of wrapping
Shared clock across devices Drift metric meaningless; one device’s burst affects all One clock instance per device stream
Logical counter in the idempotency key Replays produce different keys and duplicate triggers Derive the key’s bucket from the physical component only
Device clock far ahead HLC adopts the future timestamp and cannot come back Clamp adopted remote timestamps to a maximum forward skew
HLC compared against raw wall clock Off-by-a-few-milliseconds comparisons Compare only the physical component against wall-clock deadlines
Clock lost on restart Monotonicity broken across a process restart Persist the last value with the device’s committed state
Failure mode at a glance: Signature, Mitigation A row per failure mode, a column per option, so a single axis can be compared across options in one sweep. Failure mode at a glance: Signature, Mitigation the same trade-offs, read across instead of down Signature Mitigation Counter wraps silently Ordering inverts once per 65,536 events in a millisecond Spill into the physical component instead of wrapping Shared clock across devices Drift metric meaningless; one device's burst affects all One clock instance per device stream Logical counter in the idempotency key Replays produce different keys and duplicate triggers Derive the key's bucket from the physical component only Device clock far ahead HLC adopts the future timestamp and cannot come back Clamp adopted remote timestamps to a maximum forward skew HLC compared against raw wall clock Off-by-a-few-milliseconds comparisons Compare only the physical component against wall-clock deadlines Clock lost on restart Monotonicity broken across a process restart Persist the last value with the device's committed state
The failure mode table read across rather than down — each row is one axis of the decision, colour-keyed so a single trade-off can be followed across Signature, Mitigation.

The forward-skew clamp in the fourth row is the one genuinely dangerous case. A device whose clock is set to next year hands the ingest edge a timestamp that observe() will adopt, and because the HLC never decreases, every subsequent event for that device — and, with a shared clock, for every device — carries a timestamp a year in the future. Nothing recovers from that without operator intervention. Clamp the adopted value to with of a few seconds, and route the offending device to the clock-drift detection described in detecting and correcting device clock drift.

Persistence, in the last row, matters less than it first appears. A restart that loses the clock re-acquires from the physical time, which is monotonic across restarts in every practical case, so the only lost guarantee is tie-breaking against events from the previous process — and those are already committed. Persisting alongside the pair state from spatial index persistence and warm start closes even that gap if the ordering must be provable across a deploy.