Deduplicating Vehicle Pings in a Sliding Window

Keep one last-accepted record per asset, compare each ping against it on elapsed time OR ground distance, and do the read, the decision and the write in a single Lua script — two round trips lose the race exactly when redeliveries are most likely, and a late ping allowed to overwrite a newer record silently disables the window for that asset.

This guide sits under Time-Windowed Deduplication for Moving Assets, within Idempotency & Spatial Deduplication. It is the sliding alternative to the tumbling bucket that topic describes, and it costs one read per event to remove the boundary pair.

When to use this pattern

  • Boundary duplicates have actually been measured — pairs of pings seconds apart that both got admitted because a bucket edge fell between them.
  • A read per event is affordable, which for a Redis instance co-located with the consumer usually means it is.
  • The stream is high-volume enough that the tumbling scheme’s admitted duplicates cost more than the read.

Where the tumbling bucket lets a pair through

The boundary is a fixed clock, and the vehicle does not know about it A vehicle reports at eleven fifty-nine and fifty-eight seconds, and again at twelve hundred hours and two seconds. Under a five-minute tumbling window those two pings quantise to different buckets, so both win their claim and both are admitted, even though they are four seconds apart and describe essentially the same moment. The rate of this failure is fixed and predictable: for a fleet reporting every ten seconds it happens roughly once per asset per bucket, which for ten thousand vehicles on five-minute buckets is about two thousand admitted duplicates an hour, permanently, regardless of tuning. Under a sliding comparison the incoming ping is measured against the last one actually accepted for that asset rather than against a clock, so four seconds is four seconds wherever it falls, and the pair collapses. The cost is one stored record per active asset and one read per event; the benefit is that the failure mode disappears rather than being reduced. two pings, four seconds apart, either side of 12:00:00 tumbling — quantise the clock 12:00:00 bucket 11:55–12:00 bucket 12:00–12:05 different buckets → both admitted · ~2 000 duplicates/hour for 10 000 vehicles on 5-minute buckets sliding — compare against the last accepted ping 4 s since the last accepted ping — suppressed, wherever the clock happens to be Cost: one stored record per active asset, one read per event. Benefit: the failure mode disappears rather than shrinking.
Figure 1. The tumbling failure rate is not a tuning problem — it is fixed by the ratio of report interval to bucket width, and it does not improve with any choice of bucket.

Complete runnable implementation

python 
import math

import redis.asyncio as redis

MIN_SECONDS = 60.0        # emit at most once a minute while stationary
MIN_METRES = 25.0         # …but emit immediately if the asset has moved
STATE_TTL = 6 * 3600      # must outlive the sender's full retry ladder

# One atomic unit: read the last accepted ping, decide, write if accepted.
# Splitting this into GET and SET is a race that admits duplicates exactly
# when two workers are handed the same redelivery.
_SLIDING = """
local raw = redis.call('GET', KEYS[1])
local t   = tonumber(ARGV[1])
local lat = tonumber(ARGV[2])
local lon = tonumber(ARGV[3])
local min_s = tonumber(ARGV[4])
local min_m = tonumber(ARGV[5])
local ttl   = tonumber(ARGV[6])

if raw then
  local prev_t, prev_lat, prev_lon = string.match(raw, '([^|]+)|([^|]+)|([^|]+)')
  prev_t, prev_lat, prev_lon = tonumber(prev_t), tonumber(prev_lat), tonumber(prev_lon)

  -- A ping older than the stored one is late. Suppress it AND leave the
  -- record alone: overwriting rewinds the baseline, so the next genuine
  -- ping is compared against a position the vehicle already left.
  if t <= prev_t then return 0 end

  local dt = t - prev_t
  -- Equirectangular approximation: exact enough below a few kilometres and
  -- far cheaper than haversine at this call rate.
  local x = math.rad(lon - prev_lon) * math.cos(math.rad((lat + prev_lat) / 2))
  local y = math.rad(lat - prev_lat)
  local dm = 6371000 * math.sqrt(x * x + y * y)

  -- OR, not AND. Time alone loses a vehicle that accelerated away inside
  -- the window; distance alone never emits for a parked vehicle, so a
  -- consumer cannot tell parked from disconnected.
  if dt < min_s and dm < min_m then return 0 end
end

redis.call('SET', KEYS[1], ARGV[1] .. '|' .. ARGV[2] .. '|' .. ARGV[3], 'EX', ttl)
return 1
"""


class SlidingWindowDeduplicator:
    def __init__(self, client: redis.Redis) -> None:
        self._script = client.register_script(_SLIDING)

    async def accept(self, asset_id: str, epoch: float,
                     lat: float, lon: float) -> bool:
        """True if this ping should be processed; False if it is a duplicate."""
        result = await self._script(
            keys=[f"slide:{asset_id}"],
            args=[epoch, lat, lon, MIN_SECONDS, MIN_METRES, STATE_TTL],
        )
        return bool(result)

The t <= prev_t guard is the part that is easy to leave out and hard to notice missing. Without it a late ping suppresses correctly but still writes, so the baseline moves backwards and the next ping — a genuine one — is compared against stale state.

Four quadrants, and only one of them suppresses Each incoming ping is placed on two axes: seconds elapsed since the last accepted ping, and metres moved since it. The lower-left quadrant — less than sixty seconds and less than twenty-five metres — is the only region that suppresses, and it corresponds to a vehicle that has neither waited nor moved, which is either a redelivery or a stationary asset reporting again. The upper-left quadrant is a vehicle that moved far in little time, which is exactly the acceleration case a time-only rule would wrongly suppress. The lower-right is a parked vehicle whose heartbeat interval has elapsed, admitted so that a consumer can distinguish parked from disconnected — a distance-only rule would never emit here and a dwell-time consumer would see the vehicle vanish. The upper-right is unambiguous movement. Using OR rather than AND is what makes only the lower-left suppress; using AND would suppress three of the four quadrants and lose most of the stream. 60 s seconds since last accepted → 25 m metres moved ↑ SUPPRESS neither waited nor moved admit accelerated away time-only would lose this admit parked heartbeat — lets a consumer tell parked from disconnected admit unambiguous movement why OR and not AND OR suppresses one quadrant — the one that carries no new information AND would suppress three of four, discarding most of the stream The operator is the whole design; the two thresholds are just tuning.
Figure 2. Swapping the and for an or in the Lua script is a one-character change that turns a working deduplicator into a filter discarding three quarters of the stream.

Parameter reference

Name Type Spatial constraint Default
MIN_SECONDS float The stationary heartbeat interval; below the consumer’s staleness tolerance 60.0
MIN_METRES float Above measured GPS jitter, below the shortest movement that matters 25.0
STATE_TTL int The sender’s full retry ladder, not the window 21600
Distance formula — Equirectangular; error under 0.5% below ~5 km, so unusable for long gaps —
Combining operator — OR — AND discards three of the four quadrants OR
t <= prev_t guard — Suppress and do not write, or the baseline rewinds —

Gotchas and spatial edge cases

  1. The equirectangular approximation degrades over long gaps. It is accurate below a few kilometres and increasingly wrong beyond that, especially at high latitude. For a deduplication threshold of tens of metres this never matters — but if someone later reuses the same script with a five-kilometre threshold, it does. Keep the threshold and the formula documented together.

  2. A vehicle crossing the antimeridian produces a longitude difference of 360 degrees. The subtraction gives an enormous distance, so the ping is admitted. That is the safe direction — a false admission rather than a false suppression — but it means the metric for suppression rate will show a spike for any fleet operating in the Pacific.

  3. One key per asset means memory scales with the active fleet, not with events. That is the mechanism’s main advantage over a bucket-per-window scheme, and it depends on the TTL actually being set on every write; the EX in the script is what stops a churning fleet leaking keys forever.

  4. register_script uses EVALSHA with a fallback, which matters across a restart. After a Redis restart the script cache is empty and the first call falls back to EVAL; that is handled by the client, but a proxy that does not implement SCRIPT LOAD correctly will fail every call. Test against the deployment topology, not against a local Redis.

  5. The record is a comparison baseline, not an audit log. It holds only the last accepted ping, so it cannot answer “how many were suppressed” — that needs a counter, and the ratio of suppressed to accepted per asset is the signal that catches a device stuck reporting a cached fix.

  6. This suppresses re-observation, not redelivery of an already-accepted ping. A redelivery arriving with the same timestamp is caught by t <= prev_t, but one arriving after a genuinely newer ping is not — that needs the identity key from Event Key Generation for Spatial Data alongside this window.

Read-then-write loses the race exactly when it matters Two consumer workers are handed the same redelivered ping at the same moment. With separate GET and SET commands, both read the stored last-accepted record, both see the same baseline, both conclude the ping is novel, and both write — so the duplicate the mechanism exists to suppress is admitted, and one of the two writes silently overwrites the other's. The race is not rare: it happens precisely when the stream is busy and redeliveries are most likely, which is when duplicate suppression matters most and when a test running one worker at a time will never reproduce it. With the logic inside a Lua script, Redis executes the read, the comparison and the write as a single unit that no other client can interleave, so the second worker's call sees the first worker's write and returns a suppression. Nothing about the comparison changes; what changes is that it cannot be observed halfway through. GET then SET — two round trips, two workers w1 GET w2 GET w1 SET w2 SET both saw the same baseline · both admitted the ping the race fires when the stream is busy and redeliveries are likeliest — and a single-worker test never reproduces it one Lua script — one unit, no interleaving w1: read · compare · write w2: read · compare · suppress w2 sees w1's write, because it cannot run in between The comparison is unchanged. What changes is that it can no longer be observed halfway through — which is the whole reason the decision lives on the server rather than in the consumer.
Figure 3. Every ingredient of this bug is invisible in a single-threaded test, which is why the atomicity has to be a property of the design rather than something added after a duplicate is noticed.

Verification

python 
import pytest

BASE = 1_780_000_000.0
LAT, LON = 52.5200087, 13.4049547


@pytest.mark.asyncio
async def test_boundary_pair_collapses(dedup):
    """The failure the tumbling scheme has, four seconds apart."""
    assert await dedup.accept("veh-1", BASE, LAT, LON) is True
    assert await dedup.accept("veh-1", BASE + 4, LAT, LON) is False


@pytest.mark.asyncio
async def test_movement_inside_the_window_is_admitted(dedup):
    """Distance is an OR, so acceleration is not suppressed."""
    await dedup.accept("veh-2", BASE, LAT, LON)
    assert await dedup.accept("veh-2", BASE + 5, LAT + 0.002, LON) is True


@pytest.mark.asyncio
async def test_parked_vehicle_still_heartbeats(dedup):
    """Time is an OR too, so a stationary asset is not silent forever."""
    await dedup.accept("veh-3", BASE, LAT, LON)
    assert await dedup.accept("veh-3", BASE + 30, LAT, LON) is False
    assert await dedup.accept("veh-3", BASE + 61, LAT, LON) is True


@pytest.mark.asyncio
async def test_late_ping_does_not_rewind_the_baseline(dedup):
    """The guard that is easy to omit and hard to notice missing."""
    await dedup.accept("veh-4", BASE + 100, LAT, LON)
    assert await dedup.accept("veh-4", BASE, LAT, LON) is False       # late
    # If the late ping had overwritten the record, this would be admitted.
    assert await dedup.accept("veh-4", BASE + 130, LAT, LON) is False

The last test is the one that distinguishes a correct implementation from one that merely returns the right boolean. Both suppress the late ping; only the correct one still has the right baseline afterwards.