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

Dwell-Time Triggers Without Timer Storms

A dwell trigger — “tell me when this vehicle has been inside the depot for ten minutes” — looks like the easiest feature in a geofencing platform and is the one most likely to take the event loop down. The naive implementation schedules a timer on ENTER and cancels it on EXIT, which is correct and costs one asyncio timer per device-fence pair. At 1.9 million live pairs with the churn a real fleet generates, that is roughly 12,000 timer creations and cancellations per second against a heap that the event loop must maintain in order, and the loop spends more time managing timers than evaluating geometry. This page sits under boundary hysteresis and debounce tuning, which needs the same machinery for its pending-vote sweep, and within Core Architecture & Latency Constraints.

Concept and specification

The structure that solves this is a hashed timer wheel: an array of buckets, each holding the set of deadlines that fall in one tick, with a cursor that advances one bucket per tick. Scheduling is — compute the bucket, append — and firing a tick is in the number of items due, rather than per operation against a global heap. For a deadline $d$ ticks in the future on a wheel of $W$ buckets, the bucket is

where $r$ is the number of full wheel rotations the entry must survive before it is due. Storing $r$ alongside the entry lets a single-level wheel handle deadlines far beyond its own span: each tick decrements the rotation counter of the entries it visits and fires only those at zero.

Parameter Symbol Typical value Effect if mis-sized
Tick duration 1 s Finer wastes CPU on empty ticks; coarser blurs the dwell threshold
Wheel size $W$ 512 buckets Small wheel means many rotations per entry, so ticks scan more
Dwell threshold $D$ 60 s – 24 h Sets the rotation count
Entries per bucket $k$ Above a few thousand, one tick becomes a latency spike
Cancellation policy — tombstone Eager removal makes cancel ; tombstones keep it
Parameter at a glance: Symbol, Typical value A row per parameter, a column per option, so a single axis can be compared across options in one sweep. Parameter at a glance: Symbol, Typical value the same trade-offs, read across instead of down Symbol Typical value Effect if mis-sized Tick duration 1 s Finer wastes CPU on empty ticks; coarser blurs the dwell threshold Wheel size W 512 buckets Small wheel means many rotations per entry, so ticks scan more Dwell threshold D 60 s – 24 h Sets the rotation count D / (W) Entries per bucket k n / W Above a few thousand, one tick becomes a latency spike Cancellation policy — tombstone Eager removal makes cancel O(k); tombstones keep it O(1)
The parameter 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 Symbol, Typical value, Effect if mis-sized.

The tick duration is the parameter that decides the trigger’s precision, and it should be chosen against the dwell threshold rather than against the reporting interval. A ten-minute dwell does not need one-second precision — a one-second tick fires within 0.17% of the threshold, and a five-second tick within 0.83%, which is inside the uncertainty of the ENTER instant itself once interpolation has estimated it. Coarser ticks mean fewer wake-ups and fewer empty scans.

Cancellation deserves its own decision. Dwell timers are cancelled far more often than they fire — most vehicles leave before the threshold — so cancel must be the cheap operation. Removing the entry from its bucket is because buckets are lists; marking the entry dead and letting the tick skip it is and costs only the memory of a tombstone until its bucket comes round. With a cancel-to-fire ratio of 8:1 on a delivery fleet, tombstoning is decisively correct.

Step-by-step implementation

1. Build the wheel over the pair state, not beside it. The wheel should hold references to the same per-pair records the debouncer uses, so a cancellation is a flag on a record rather than a lookup in a second structure.

python 
from __future__ import annotations
from dataclasses import dataclass, field

@dataclass(slots=True)
class DwellEntry:
    pair_key: int
    rotations: int
    alive: bool = True

class TimerWheel:
    """Single-level hashed wheel with rotation counts and tombstoned cancels."""

    def __init__(self, size: int = 512, tick_s: float = 1.0) -> None:
        self.size, self.tick_s = size, tick_s
        self.buckets: list[list[DwellEntry]] = [[] for _ in range(size)]
        self.cursor = 0
        self.live: dict[int, DwellEntry] = {}

    def schedule(self, pair_key: int, delay_s: float) -> None:
        ticks = max(1, int(delay_s / self.tick_s))
        entry = DwellEntry(pair_key, rotations=ticks // self.size)
        self.buckets[(self.cursor + ticks) % self.size].append(entry)
        self.live[pair_key] = entry

    def cancel(self, pair_key: int) -> None:
        entry = self.live.pop(pair_key, None)
        if entry is not None:
            entry.alive = False        # O(1): the tick will skip and drop it

    def tick(self) -> list[int]:
        bucket = self.buckets[self.cursor]
        due: list[int] = []
        keep: list[DwellEntry] = []
        for e in bucket:
            if not e.alive:
                continue                # tombstone: drop it here
            if e.rotations:
                e.rotations -= 1
                keep.append(e)
            else:
                due.append(e.pair_key)
                self.live.pop(e.pair_key, None)
        self.buckets[self.cursor] = keep
        self.cursor = (self.cursor + 1) % self.size
        return due

2. Drive the wheel from one coroutine, not from the clock. A single while True: await asyncio.sleep(tick); wheel.tick() loop replaces every per-pair timer with exactly one. Compute the sleep from a monotonic deadline rather than sleeping a fixed interval, or the wheel drifts by the duration of each tick’s work.

3. Schedule against event time, not arrival time. A dwell is a statement about how long the device was inside, which is measured in event time. Scheduling from arrival time makes the trigger fire early for a device whose data was delayed — a device whose ENTER arrived 30 s late gets its ten-minute dwell at nine minutes thirty of real dwell. Convert the event-time deadline into a wheel delay at scheduling time using the current watermark from event-time ordering and clock skew.

4. Make the fired trigger re-check the state. A tick firing is evidence that the deadline passed, not that the device is still inside. Between scheduling and firing the pair may have gone STALE, or an out-of-order EXIT may have arrived. Re-read the pair’s committed state at fire time and suppress the dwell if it is no longer INSIDE — cheaper and more robust than trying to keep the wheel perfectly consistent.

5. Cap the work per tick. A bucket holding 40,000 entries blocks the loop for milliseconds. Bound the number fired per tick and carry the remainder into the next one, accepting a small delay rather than a latency spike; alert when the carry is non-zero for several consecutive ticks, which means the wheel is undersized for the fleet.

Benchmark and verification

Measured with 1.9 million live pairs, a cancel-to-fire ratio of 8:1, and a ten-minute dwell threshold, on one core:

Approach Schedule cost Cancel cost Memory Loop P99 during churn
One asyncio timer per pair 41 µs 27 µs 380 MB 94 ms
Global heap with lazy deletion 3.1 µs 0.2 µs 152 MB 18 ms
Hashed wheel, eager cancel 0.9 µs 61 µs 61 MB 22 ms
Hashed wheel, tombstoned cancel 0.9 µs 0.1 µs 61 MB 2.4 ms
Schedule cost, Cancel cost, Loop P99 during churn — 4 options Each panel scales on its own, so Schedule cost, Cancel cost, Loop P99 during churn are compared across 4 options without sharing an axis they do not share a unit with. Schedule cost, Cancel cost, Loop P99 during churn — 4 options Approach — the table above, drawn to scale One asyncio timer per pair Global heap with lazy deletion Hashed wheel, eager cancel Hashed wheel, tombstoned cancel Schedule cost 41 µs 3.1 µs 0.9 µs 0.9 µs Cancel cost 27 µs 0.2 µs 61 µs 0.1 µs Loop P99 during churn 94 ms 18 ms 22 ms 2.4 ms
Schedule cost, Cancel cost and 1 more for One asyncio timer per pair, Global heap with lazy deletion, Hashed wheel, eager cancel 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 third row is the instructive failure: a wheel with eager cancellation is worse than a heap, because cancels outnumber fires eight to one and each one scans a bucket. The same structure with tombstones is the best on every axis. That pairing — the right structure with the wrong cancellation policy performing worse than a simpler structure — is why the policy belongs in the design rather than being left to whoever writes the cancel method.

The loop P99 column is what an operator actually feels. Per-pair timers push the event loop’s iteration time to 94 ms during churn, which is two full latency budgets, and every coroutine on that loop — including the geometry evaluation the service exists to do — waits behind it. The wheel keeps it at 2.4 ms.

Verify with py-spy rather than with a synthetic benchmark, following the method in py-spy flame graphs for asyncio spatial pipelines. The signature of a timer storm is unmistakable: asyncio.base_events._run_once and heapq frames dominating the profile while application code barely appears.

Failure modes and edge cases

Failure mode Signature Mitigation
Scheduling from arrival time Dwell fires early for devices with delayed data Schedule from event time against the watermark
No re-check at fire time Dwell fires for devices that already left Re-read committed state before emitting
Unbounded bucket Periodic multi-millisecond loop stalls Cap fires per tick and carry the remainder
Tombstones never collected Memory grows with cancellations Drop dead entries during the tick that visits their bucket
Tick drift Dwell thresholds slowly become inaccurate Sleep to a monotonic deadline, not for a fixed interval
Wheel restarted with the process All pending dwells lost silently Persist deadlines with the pair state, rehydrate at warm start
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 Scheduling from arrival time Dwell fires early for devices with delayed data Schedule from event time against the watermark No re-check at fire time Dwell fires for devices that already left Re-read committed state before emitting Unbounded bucket Periodic multi-millisecond loop stalls Cap fires per tick and carry the remainder Tombstones never collected Memory grows with cancellations Drop dead entries during the tick that visits their bucket Tick drift Dwell thresholds slowly become inaccurate Sleep to a monotonic deadline, not for a fixed interval Wheel restarted with the process All pending dwells lost silently Persist deadlines with the pair state, rehydrate at warm start
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 last row connects to spatial index persistence and warm start and is the one most often discovered in production. A wheel is in-memory by construction, so a deploy silently discards every pending dwell — a fleet of vehicles that were eight minutes into a ten-minute dwell simply never trigger. The fix is to store the deadline alongside the committed pair state in whatever durable store holds it, and to re-schedule on startup, dropping deadlines that have already passed while the process was down but emitting for those that passed and whose pair is still INSIDE.

Two subtleties round this out. A dwell threshold longer than the wheel’s span times its rotation capacity — days, for a “parked for a week” trigger — should not be handled by a bigger wheel but by a second, coarser one, with entries promoted from the coarse wheel to the fine one as they approach. And a device that leaves and re-enters within the dwell period must restart its dwell, not continue it, which means the cancel on EXIT must be unconditional even when an ENTER is expected imminently; the alternative silently converts an intermittent presence into a continuous one.