Idempotent Trigger Emission Semantics for Geofencing

At-least-once delivery is the only honest guarantee a real-time geofence pipeline can offer, which means every ENTER, EXIT, and DWELL trigger will eventually be emitted more than once — a producer retry after a lost acknowledgement, a consumer rebalance that reprocesses uncommitted offsets, a load-shed replay, a dead-letter drain. If a duplicated ENTER double-charges a surge fare or a duplicated EXIT fires a compliance alarm twice, the pipeline is correct on paper and wrong in production. Idempotent emission is the discipline that makes duplication invisible: a deterministic key derived from the trigger’s own semantics, checked against a bounded dedup window, so the second, third, and fourth copies of the same logical transition collapse to a single downstream effect. This page expands the delivery-semantics model introduced in event routing and backpressure, and the failure it addresses is duplicate side effects under retry and replay — the traffic shape where correctness depends not on delivering each trigger once, but on acting on each transition once.

The reader is a backend engineer whose geofence service emits triggers into Kafka or Redis Streams and who has watched a single physical fence crossing produce two ENTER events downstream. The fix is not “deliver exactly once” — that guarantee is expensive and, as covered in exactly-once vs at-least-once trigger delivery, is really at-least-once plus an idempotent consumer wearing a costume. The fix is to make the key deterministic so two emissions of the same transition are provably identical, and to make the dedup window cheap enough to consult on every trigger without moving the P99.

Algorithmic Divergence & Latency Profiles #

The whole scheme rests on the key being deterministic — computable identically from the trigger’s semantics on every emission, with no wall-clock, no random nonce, no producer-assigned sequence number. The canonical key is a hash over the tuple (device_id, fence_id, transition, event_time_bucket):

k = H\big(\text{device_id} \parallel \text{fence_id} \parallel \text{transition} \parallel \lfloor t_{\text{event}} / W \rfloor\big)

where $W$ is the bucket width and $H$ is a fast non-cryptographic 128-bit hash. Each field is load-bearing. device_id and fence_id scope the key to one asset and one boundary. transition distinguishes an ENTER from the EXIT that follows — without it, a device leaving and re-entering the same fence would collide. The event_time_bucket is the subtle one: hashing the raw event timestamp would make two retries of the same crossing produce different keys if their timestamps differ by a nanosecond, defeating dedup entirely; flooring to a bucket of width $W$ (typically 1–5s) means all emissions of one physical crossing land in the same bucket and hash identically, while a genuine re-entry a minute later lands in a different bucket and is correctly treated as new. The event-time bucketing that absorbs clock skew is developed in depth in deduplicating ENTER/EXIT events with idempotency keys.

The dedup lookup cost is $O(1)$ regardless of window size — a hash-table probe or a Redis SETNX. What diverges across implementations is the constant factor and the memory of the window. The three contenders and their measured profiles on a single node, dedup window sized to 5M keys, driven at 25k triggers/sec:

The in-process LRU holds the whole window in ~400MB at a P99 under 0.2ms because it never leaves the process — no serialization, no network hop. Redis pays a network round-trip (P99 ~0.9ms) but is the only option when multiple consumer instances must share one dedup view across a rebalance. The bloom filter is the cheapest in memory (~90MB) and the fastest, but it is probabilistic: it can report a novel key as seen (a false positive that silently drops a real trigger) and cannot delete, so it is only safe as a pre-filter in front of an authoritative store, never as the sole gate.

Concrete sizing anchors the design: a 5M-key window at ~80 bytes per entry (128-bit key + TTL timestamp + LRU pointers) is ~400MB of RSS, and at 25k triggers/sec with a 5-minute retention that window holds every trigger for 300s — 7.5M keys — so the 5M figure requires either a tighter TTL (~3.3 min) or per-partition sharding of the window. This is the lever: the window must be large enough to span the maximum retry/replay delay and small enough to fit the memory budget of the memory-constrained spatial processing node.

Implementation Trade-offs & the Critical Path #

The per-trigger critical path is: derive the key, atomically test-and-set the window, emit only on novel. The atomicity matters — a check-then-set with a gap between the two lets two concurrent copies of the same trigger both see “novel” and both emit. The in-process path uses a single-threaded async design so the check-and-set is naturally atomic under the GIL; the Redis path uses SET key val NX EX ttl, a single atomic command, rather than a GET followed by a SET.

from __future__ import annotations

import time
from collections import OrderedDict
from dataclasses import dataclass
from enum import Enum

import xxhash  # fast non-cryptographic 128-bit hash

BUCKET_WIDTH_NS: int = 2_000_000_000   # 2s: absorbs sub-second skew, splits real re-entry


class Transition(Enum):
    ENTER = "E"
    EXIT = "X"
    DWELL = "D"


@dataclass(slots=True, frozen=True)
class Emission:
    device_id: str
    fence_id: str
    transition: Transition
    event_time_ns: int


def idempotency_key(e: Emission) -> int:
    # Deterministic: no wall-clock, no nonce. Two emissions of the same physical
    # crossing produce the SAME key because event_time floors to one bucket.
    bucket = e.event_time_ns // BUCKET_WIDTH_NS
    material = f"{e.device_id}|{e.fence_id}|{e.transition.value}|{bucket}"
    return xxhash.xxh128_intdigest(material)         # 128-bit, collision-safe at 5M keys


class DedupWindow:
    """In-process TTL LRU. Single-threaded async use makes check-and-set atomic
    under the GIL, so no lock is needed on the hot path."""
    __slots__ = ("_seen", "_ttl_ns", "_capacity")

    def __init__(self, ttl_s: float = 200.0, capacity: int = 5_000_000) -> None:
        self._seen: OrderedDict[int, int] = OrderedDict()   # key -> expiry_ns
        self._ttl_ns: int = int(ttl_s * 1e9)
        self._capacity: int = capacity

    def admit(self, key: int, now_ns: int) -> bool:
        # Returns True exactly once per key within the window; False = duplicate.
        exp = self._seen.get(key)
        if exp is not None and exp > now_ns:
            self._seen.move_to_end(key)              # LRU touch
            return False                             # duplicate -> caller drops emit
        self._seen[key] = now_ns + self._ttl_ns
        self._seen.move_to_end(key)
        # Bound memory: evict oldest by insertion/TTL when over capacity.
        while len(self._seen) > self._capacity:
            old_key, old_exp = next(iter(self._seen.items()))
            if old_exp > now_ns and len(self._seen) <= self._capacity:
                break
            self._seen.popitem(last=False)           # drop oldest
        return True


class IdempotentEmitter:
    def __init__(self, window: DedupWindow) -> None:
        self._window = window
        self._metrics = {"emitted": 0, "suppressed": 0}

    async def emit(self, e: Emission, sink) -> bool:
        now = time.time_ns()
        key = idempotency_key(e)
        if not self._window.admit(key, now):
            self._metrics["suppressed"] += 1         # retry/replay collapsed here
            return False
        await sink(e, key)                            # downstream carries the key too
        self._metrics["emitted"] += 1
        return True

Two decisions carry the weight. First, idempotency_key reads nothing from the environment — same input, same output, forever — which is what lets a retry three hours later collapse against the original. Second, the downstream sink receives the key alongside the trigger, so a consumer can dedup a second time at the sink boundary; belt-and-suspenders dedup is correct because the key is stable across every hop. The Redis variant swaps DedupWindow.admit for a single await redis.set(key, 1, nx=True, ex=ttl) returning whether the key was new — the same semantics, cross-process, at the cost of a round-trip.

Memory Footprint & Streaming Churn #

The dedup window is the pipeline’s second-largest resident structure after the spatial index, and its footprint is fully determined by the retention TTL and the trigger rate: $\text{keys}=\text{rate}\times \text{TTL}$. At 25k triggers/sec and a 200s TTL the window holds 5M keys; the OrderedDict entry — a 128-bit int key, an 8-byte expiry, and the dict/linked-list overhead — runs ~80 bytes, so ~400MB RSS. Pushing the TTL to 600s to survive a slow DLQ replay triples that to ~1.2GB, which is why the TTL is not a free parameter: it must bracket the maximum retry/replay delay and no more.

Churn is the subtler cost. At 25k inserts/sec plus matching evictions, the OrderedDict mutates 50k times/sec, and every insertion/eviction allocates and frees an entry — exactly the generation-0 pressure that the memory-constrained spatial processing discipline warns against. Two mitigations: keep the key an int (not a str) so CPython interns small structure rather than allocating a string per key, and prefer a fixed-size ring or a bloom pre-filter that never allocates per-key when the window is dominated by novel traffic. Under sustained load the eviction path is the hot allocator; pooling the entry objects or using a bloom pre-filter to skip the LRU entirely for obviously-novel keys keeps gen-2 sweeps out of the P99. When the window is shared via Redis, the churn moves off-heap to the Redis server, trading local GC pressure for network cost and the server’s own eviction (maxmemory-policy allkeys-lru).

Async Mutation Boundaries & Queue Semantics #

The dedup window is mutable shared state on the hot path, so its concurrency model is a correctness boundary, not a performance detail. The in-process DedupWindow is safe only because the emitter is single-threaded async — the admit check-and-set runs to completion between await points, so no two coroutines interleave on the same key. The moment you spread emission across threads or processes, that atomicity evaporates and you must move to Redis SETNX (atomic server-side) or a per-key lock, because a torn check-and-set is exactly the race that emits a duplicate. This is the same lock-free-under-the-GIL reasoning that governs async index updates without locking, applied to a dedup map instead of a spatial index.

Ordering and idempotency are orthogonal and must not be conflated. Idempotency guarantees each transition acts at most once; it says nothing about the order ENTER and EXIT arrive. A load-shed replay can deliver an ENTER after its own EXIT, and dedup alone will happily admit both because they carry different transition fields and hash to different keys. Ordering is enforced separately — by keying the producer on device_id so a device’s transitions stay on one partition, or by having the downstream resolve state against event time. When the dedup store itself is the backpressure boundary (a Redis window under a burst), a bounded queue in front of the emitter sheds load per the backpressure and flow-control strategies, and every shed trigger is safe to replay later precisely because the key makes the replay idempotent. Idempotent emission is what makes aggressive load-shedding survivable — the same closing argument the core architecture makes about retries.

Operational Runbook & Failure Mitigation #

When duplicates leak downstream or the window blows its memory budget, the cause is one of a small set of failure modes. Diagnose with the suppressed/emitted ratio (the dedup hit rate), tracemalloc on the window, and a downstream duplicate-detection audit.

The standing diagnostic loop:

1. Confirm the symptom downstream. Query the sink for records sharing an idempotency key. Zero duplicates is nominal; any duplicate means the key derivation or the window is at fault, not the downstream.
2. Attribute to key vs window. If duplicates carry different keys for the same physical crossing, the bug is in derivation — almost always a bucket too narrow or a nonce leaking into the material. If they carry the same key, the window admitted twice — a torn check-and-set or a TTL expiry.
3. Check the dedup hit rate. Pull suppressed / (emitted + suppressed) from Prometheus. A healthy retrying pipeline sits around 1–5% suppression; a sudden drop to ~0% means dedup is not engaging (window cleared on restart, or keys changed); a spike toward 50% means a producer is emitting a storm of duplicates upstream.
4. Localize memory growth. Diff tracemalloc snapshots 60s apart on the window. Growth beyond rate × TTL × 80 bytes means eviction is not keeping up — check the TTL and the LRU eviction path.
5. Quantify GC pauses. gc.get_stats() gen-2 collections rising with the emitter P99 means the insert/evict churn is the tail; pool entry objects or add a bloom pre-filter and re-measure.
6. Verify across a rebalance. Force a consumer rebalance and confirm the dedup view survives — an in-process window that clears on restart re-admits every in-flight trigger, so a shared Redis window is mandatory when instances rotate. This ties directly to consumer group rebalancing without dropping triggers.

Continuous monitoring should target a stable dedup hit rate, zero same-key double-admits, and window RSS within 10% of the rate × TTL prediction — a drift in any of the three is the earliest sign of a derivation or eviction regression.

Architectural Guidance: When to Choose Which #

The dedup-store choice is driven by two axes — whether emission is single- or multi-process, and how much memory the window is allowed.

The invariant across every variant is that the key is deterministic and the window is bounded: two emissions of the same transition always hash identically, and the window can never grow past rate × TTL. Idempotent emission does not make delivery exactly-once — it makes duplicate delivery harmless, which is the only guarantee that survives contact with retries, rebalances, and load-shedding. Derive the key from semantics alone, size the window to bracket your worst-case replay delay, keep the check-and-set atomic, and a physical fence crossing fires its downstream effect exactly once no matter how many times the pipeline delivers it.

Frequently Asked Questions #

Related #

• Event Routing & Backpressure — parent overview of trigger routing, delivery semantics, and flow control.
• Deduplicating ENTER/EXIT Events with Idempotency Keys — key construction and event-time bucketing in depth.
• Exactly-Once vs At-Least-Once Trigger Delivery — why exactly-once is at-least-once plus an idempotent consumer.
• Dead-Letter Topics & Poison-Message Handling — the DLQ path whose replay depends on these keys.
• Backpressure & Flow-Control Strategies — load-shedding made safe by idempotent replay.