Deduplicating ENTER/EXIT Events with Idempotency Keys

A vehicle crosses a surge-pricing perimeter once, but the pipeline can emit that ENTER two or three times — a producer retry after a lost ack, a consumer replaying uncommitted offsets after a rebalance, a load-shed drain from the dead-letter path. The physical event happened once; the downstream must act once. This page sits under idempotent trigger emission semantics and the broader event routing and backpressure architecture, and it drills into the two parameters that decide whether dedup actually works: how the key is constructed, and how wide the event-time bucket and the dedup TTL must be. Get the bucket too small and a jittery timestamp splits one crossing into two keys that both fire; get it too large and a genuine re-entry is silently swallowed as a duplicate.

Concept and specification #

The idempotency key is a deterministic hash over four fields, and the design constraint is that every emission of one physical transition must produce a byte-identical key while any distinct transition must not:

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

The first three fields scope the key; the fourth — the event-time bucket $\lfloor t_{\text{event}}/W\rfloor$ — is where the real engineering lives. Retries and reprocessing re-stamp or re-observe the event, so their raw timestamps differ by milliseconds; flooring to a bucket of width $W$ maps all of them to the same integer. The bucket must satisfy two opposing bounds simultaneously:

$${\Delta }_{\text{skew}}<W<{\Delta }_{\text{revisit}}$$

where ${\Delta }_{\text{skew}}$ is the maximum spread between duplicate emissions of one crossing (clock skew + retry delay + GPS jitter) and ${\Delta }_{\text{revisit}}$ is the minimum time before a device could genuinely re-cross the same fence. If those bounds cross — a fleet where devices skew by 8s but can legitimately re-enter a small fence in 5s — no single $W$ is safe, and you must add a monotonic sequence hint or shrink the fence’s re-entry semantics.

The transition field is not optional: an ENTER and the EXIT that follows share device_id, fence_id, and possibly the same bucket if the dwell was brief, so without transition in the material a quick pass-through would collapse ENTER and EXIT into one key and drop the EXIT. Encoding the transition (E/X/D) keeps them distinct.

A useful way to reason about the bucket is as a lossy quantization of the time axis: every emission is snapped to the nearest lower multiple of $W$, and dedup collapses everything that snaps to the same grid point. Two emissions collide if and only if $\lfloor t_1/W\rfloor =\lfloor t_2/W\rfloor$, which holds whenever they fall in the same interval $[nW,(n+1)W)$ — but not when they straddle a boundary even if they are milliseconds apart. That boundary blind spot is the single structural weakness of fixed bucketing, and it is why the boundary-guard probe in the implementation is not optional polish but a correctness requirement: without it, roughly $2g/W$ of all duplicate pairs (for guard band $g$) fall across an edge and leak, which at $W=2\text{s}$ and a 200ms retry spread is on the order of 10% of duplicates.

Step-by-step implementation #

Prerequisites: Python 3.11+, xxhash>=3.0 for a fast 128-bit non-cryptographic hash, and either an in-process TTL map or redis>=5.0 for a cross-process window. Input is a stream of transition events carrying device_id, fence_id, a transition kind, and an event timestamp in nanoseconds; output is the same stream with duplicates dropped.

1. Derive the key deterministically. No wall-clock, no random nonce, no producer sequence number — the key must be reproducible from the event’s own fields alone.

from __future__ import annotations
from dataclasses import dataclass
from enum import Enum
import xxhash

BUCKET_WIDTH_NS: int = 2_000_000_000   # 2s: > max duplicate spread, < min re-visit

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

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

def make_key(ev: TransitionEvent) -> int:
    # Floor event time into a bucket so retries of one crossing collide,
    # while a genuine re-entry in a later bucket stays distinct.
    bucket = ev.event_time_ns // BUCKET_WIDTH_NS
    material = f"{ev.device_id}|{ev.fence_id}|{ev.kind.value}|{bucket}"
    return xxhash.xxh128_intdigest(material)

Gotcha: floor the timestamp before hashing, not after. Hashing then bucketing is meaningless — a hash destroys the ordering the floor relies on.

2. Bucket-boundary guard. A crossing whose duplicates straddle a bucket edge (one at 1.999s, its retry at 2.001s) hashes to two buckets and leaks a duplicate. Probe the adjacent bucket for keys within a guard band so edge-straddling duplicates still collapse.

def candidate_keys(ev: TransitionEvent, guard_ns: int = 200_000_000) -> list[int]:
    # If the event sits within guard_ns of a bucket edge, also emit the key for
    # the neighbouring bucket so a straddling retry is caught by either key.
    base = ev.event_time_ns // BUCKET_WIDTH_NS
    keys = [xxhash.xxh128_intdigest(
        f"{ev.device_id}|{ev.fence_id}|{ev.kind.value}|{base}")]
    offset = ev.event_time_ns % BUCKET_WIDTH_NS
    if offset < guard_ns:                       # near lower edge -> also prev bucket
        keys.append(xxhash.xxh128_intdigest(
            f"{ev.device_id}|{ev.fence_id}|{ev.kind.value}|{base - 1}"))
    elif offset > BUCKET_WIDTH_NS - guard_ns:   # near upper edge -> also next bucket
        keys.append(xxhash.xxh128_intdigest(
            f"{ev.device_id}|{ev.fence_id}|{ev.kind.value}|{base + 1}"))
    return keys

3. Test-and-set against the dedup store. The check and the set must be one atomic operation, or two concurrent copies both see “novel.” Redis SET NX EX is atomic server-side.

import redis.asyncio as redis

TTL_S: int = 300   # bracket max retry + DLQ replay delay

async def admit(r: redis.Redis, ev: TransitionEvent) -> bool:
    # Admit only if ALL candidate keys are novel; set them together so a
    # straddling duplicate is rejected by whichever bucket it shares.
    keys = candidate_keys(ev)
    async with r.pipeline(transaction=True) as pipe:
        for k in keys:
            pipe.set(f"idem:{k}", b"1", nx=True, ex=TTL_S)
        results = await pipe.execute()
    return all(results)   # False if any key already existed -> duplicate

4. Size the TTL to the worst-case replay. The TTL must outlive the longest window in which a duplicate can arrive — producer retry ceiling, plus DLQ retention if replay is possible. A TTL shorter than the DLQ retention admits an old duplicate when the dead-letter replay runs after the key has expired.

Benchmark and verification #

The metric is the duplicate-trigger rate observed downstream — the fraction of physical crossings that fired a side effect more than once — measured over a 12-hour replay of a production trace (410M transition events, ~6% of them retried or replayed at least once), comparing no dedup, raw-timestamp keys, and bucketed keys with the boundary guard:

Raw-timestamp keys barely help (3.62%) because retries re-stamp the event to a slightly different nanosecond — proof that bucketing, not hashing, is what does the work. A 2s bucket drops duplicates to 0.11%, and the boundary guard mops up the edge-straddlers to 0.02% at a small P99 cost (the extra adjacent-bucket probe). The 30s bucket reaches 0% duplicates but over-suppresses — 214 genuine re-entries within 30s were swallowed, the exact failure of a bucket wider than ${\Delta }_{\text{revisit}}$. A minimal harness proves the two-sided property:

import time

def verify_bucket(events: list[TransitionEvent]) -> dict[str, int]:
    # Present each event twice (retry) plus a genuine re-entry 45s later.
    seen: set[int] = set()
    fired = 0
    for ev in events:
        for _ in range(2):                          # retry: must fire once
            k = make_key(ev)
            if k not in seen:
                seen.add(k); fired += 1
        later = TransitionEvent(ev.device_id, ev.fence_id, ev.kind,
                                ev.event_time_ns + 45_000_000_000)  # +45s re-entry
        k2 = make_key(later)
        if k2 not in seen:
            seen.add(k2); fired += 1                 # must fire again (distinct bucket)
    return {"fired": fired, "expected": 2 * len(events)}  # 1 per crossing + 1 re-entry

fired must equal expected — one fire per crossing despite the retry, plus one for the legitimate 45s re-entry — confirming the bucket collapses duplicates without swallowing real re-visits.

Failure modes and edge cases #

• Bucket too small. If $W$ is below the maximum duplicate spread (clock skew + retry delay), the two copies of one crossing land in different buckets, hash differently, and both fire. Symptom: duplicate rate tracks the retry rate. Fix: widen $W$ above ${\Delta }_{\text{skew}}$ and add the boundary guard.
• Bucket too large. If $W$ exceeds the minimum genuine re-visit interval, a device that legitimately re-enters within $W$ is suppressed as a duplicate and the real ENTER is lost. Symptom: missing re-entries in an audit. Fix: narrow $W$ below ${\Delta }_{\text{revisit}}$; if the bounds cross, add a per-crossing sequence hint.
• Clock skew across devices. Two devices reporting the same fence with clocks 5s apart is fine — their keys differ by device_id. The danger is one device whose clock jumps mid-stream, splitting its own crossing across buckets. Carry a monotonic ingest timestamp alongside event time and clamp implausible jumps, as the core pipeline does for event-time ordering.
• NaN or missing timestamp. An event with a null or NaN event_time_ns cannot bucket; route it to the dead-letter path rather than defaulting to now(), which would make the key non-deterministic and defeat dedup entirely.
• Bucket-edge straddle. Without the guard band, a crossing at 1.99s and its retry at 2.01s produce different bucket keys. The adjacent-bucket probe in step 2 is the fix; size the guard at roughly the retry delay.
• TTL expiry before replay. A DLQ drain that runs hours later, after the dedup key has expired, re-admits the trigger. Size the TTL at or above the DLQ retention; this is the same coupling that makes replaying dead-letter triggers safely depend on window sizing.

Related #

• Idempotent Trigger Emission Semantics for Geofencing — parent overview of deterministic keys and the dedup window.
• Exactly-Once vs At-Least-Once Trigger Delivery — why an idempotent consumer is what makes at-least-once safe.
• Replaying Dead-Letter Geofence Triggers Safely — where TTL-vs-retention sizing decides replay correctness.