Expiring Deduplication Keys Without Losing Late Retries

Measure the sender’s retry horizon by deliberately failing a delivery and watching every attempt, set the TTL from that plus outage tolerance, and bound memory with a second probabilistic tier rather than by shortening it — a shorter TTL trades a memory cost for silent duplicates that appear hours after the deploy.

This guide sits under Time-Windowed Deduplication for Moving Assets, within Idempotency & Spatial Deduplication. It sizes the STATE_TTL used by the sliding window and by the claim in Cache-Backed Idempotency Checks.

When to use this pattern

  • The deduplication store’s TTL was chosen to match the window, or to match a round number, or to fit a memory budget.
  • Duplicates appear in production but never in testing — the signature of a TTL shorter than a retry ladder.
  • Memory pressure is being managed by shortening the TTL, which is the trade this guide argues against.

Measure the horizon; the documentation is a lower bound

The attempt nobody documented is the one that arrives A provider's published retry schedule lists five attempts over about ninety minutes. Deliberately failing one delivery and recording every subsequent attempt reveals eight, the last arriving nine hours and twenty minutes after the original — the outer three are not in the documentation, either because they were added later or because the published schedule describes a different tier of the product. A TTL set from the documented horizon plus a comfortable-looking margin, say two hours, expires the key before attempts six, seven and eight, so each of them wins its claim and is written as a new observation. The failure is invisible in any test that runs faster than two hours, invisible in staging where nothing fails for long enough to reach the outer attempts, and appears in production as a small persistent rate of duplicate records with no error to attach it to. A TTL set from the measured horizon plus outage tolerance covers all eight, and costs only memory. one deliberately failed delivery · every subsequent attempt recorded 0 1 h 30 9 h 20 documented: 5 attempts measured but undocumented: 3 more attempts TTL = 2 h key gone before attempt 6 attempts 6, 7 and 8 each win a claim and are written as new observations TTL = measured horizon + outage tolerance (12 h) every attempt after the first loses · costs memory, and nothing else Invisible in any test faster than two hours, and in staging where nothing fails long enough to reach the outer attempts. In production it is a small persistent rate of duplicate records with no error attached to it.
Figure 1. The documented schedule is a lower bound on the horizon. The only reliable number comes from failing a delivery on purpose and writing down what arrives.

Complete runnable implementation

python 
import hashlib
import time

import redis.asyncio as redis
from prometheus_client import Counter, Gauge

TIER1_HIT = Counter("dedup_tier1_hit_total", "Suppressed by the exact tier")
TIER2_HIT = Counter("dedup_tier2_hit_total", "Suppressed by the filter tier")
EVICTED = Gauge("dedup_store_evicted_keys", "Redis evicted_keys — must stay 0")

# Tier 1: exact keys, covering the period most redeliveries land in.
TIER1_TTL = 2 * 3600
# Tier 2: probabilistic, covering the full measured horizon plus tolerance.
HORIZON_SECONDS = 12 * 3600
# Two rotating filters so a key is always covered for at least HORIZON_SECONDS
# regardless of where in the rotation it was written.
FILTER_SLOTS = 2


class TieredDeduplicator:
    """Exact for the recent window, probabilistic for the long tail.

    Memory is bounded by the tier-2 filter rather than by shortening the TTL,
    because a shorter TTL buys memory with duplicates.
    """

    def __init__(self, client: redis.Redis) -> None:
        self._client = client

    def _slot(self, now: float) -> int:
        return int(now // HORIZON_SECONDS) % FILTER_SLOTS

    async def seen(self, key: str, now: float | None = None) -> bool:
        now = now or time.time()

        # Tier 1 — exact, and authoritative when it answers yes.
        if not await self._client.set(f"d1:{key}", b"1", nx=True, px=TIER1_TTL * 1000):
            TIER1_HIT.inc()
            return True

        # Tier 2 — a rotating Bloom filter. Both slots are checked, so a key
        # written just before a rotation is still found afterwards.
        for offset in range(FILTER_SLOTS):
            slot = (self._slot(now) - offset) % FILTER_SLOTS
            if await self._client.execute_command("BF.EXISTS", f"d2:{slot}", key):
                # A false positive suppresses a genuine event. That is the
                # safe direction for telemetry and the wrong one for edits —
                # see the gotchas.
                TIER2_HIT.inc()
                return True

        await self._client.execute_command("BF.ADD", f"d2:{self._slot(now)}", key)
        return False

    async def sample_evictions(self) -> None:
        """Eviction shortens every TTL at once, silently. Watch it."""
        info = await self._client.info("stats")
        EVICTED.set(info.get("evicted_keys", 0))


async def measure_retry_horizon(receiver_log) -> float:
    """Derive the horizon from observation rather than documentation.

    Fail one delivery deliberately, then take the span between the first and
    last attempt carrying the same delivery id.
    """
    attempts: dict[str, list[float]] = {}
    for record in receiver_log:
        attempts.setdefault(record["delivery_id"], []).append(record["received_at"])
    spans = [max(t) - min(t) for t in attempts.values() if len(t) > 1]
    return max(spans) if spans else 0.0

Checking both filter slots is what makes the rotation safe. A single rotating filter loses every key at the instant it rotates, which reproduces the original bug on a twelve-hour cycle.

Two ways to pay for a twelve-hour horizon A stream of forty thousand events per second is deduplicated over a twelve-hour horizon. Holding an exact key for every event across that period means about one point seven billion keys resident, which at roughly sixty bytes per Redis key with its expiry metadata is on the order of a hundred gigabytes — enough that the usual response is to shorten the TTL, which is precisely the change that admits duplicates. The two-tier store holds exact keys only for the first two hours, about two hundred and ninety million keys, and covers the remaining ten hours with two rotating Bloom filters sized for the full horizon at a one-in-a-thousand false-positive rate, costing roughly ten bits per key. The total is a small fraction of the exact figure. What is given up is exactness in the tail: about one event in a thousand that reaches tier two is wrongly suppressed. For telemetry that is a good trade, because another ping follows in seconds; for feature edits it is not, because nothing resends a cadastral boundary change. 40 000 events/s · 12-hour horizon exact keys for the whole horizon ≈ 1.7 billion keys resident ≈ 60 bytes each with expiry metadata on the order of 100 GB the usual response is to shorten the TTL — which is exactly the change that admits duplicates exact, and unaffordable two tiers tier 1 · exact, 2 h → ≈ 290 million keys tier 2 · two rotating Bloom filters, 12 h ≈ 10 bits per key at a 1-in-1000 error rate a small fraction of the exact figure approximate in the tail, and affordable What is given up, and for which streams it is acceptable About one event in a thousand reaching tier 2 is wrongly suppressed. Fine for telemetry — another ping follows in seconds. Not fine for feature edits: nothing resends a cadastral boundary change.
Figure 2. The two-tier store does not make the horizon cheaper to cover exactly; it makes it cheap to cover approximately, and the approximation errs towards suppression.

Parameter reference

Name Type Spatial constraint Default
TIER1_TTL int Covers where most redeliveries land; exact, so safe for any stream 7200
HORIZON_SECONDS int Measured retry span plus outage tolerance 43200
FILTER_SLOTS int ≥ 2, so a key written before a rotation is still found after it 2
Filter error rate float The rate at which a genuine event is wrongly suppressed 0.001
Redis maxmemory policy str volatile-ttl or a dedicated instance — never allkeys-lru —
evicted_keys counter Must stay at zero; any value means the TTL is not in force 0

Gotchas and spatial edge cases

  1. Eviction silently shortens every TTL at once. Under allkeys-lru Redis will evict deduplication keys to make room for whatever else shares the instance, so a cache used for tile fragments can break idempotency for the whole pipeline. Nothing errors, and the symptom is a rise in duplicate writes that correlates with unrelated traffic. Use a dedicated instance and alert on the eviction counter.

  2. A false positive in tier two suppresses a real event, which is the wrong direction for edits. For vehicle telemetry, losing one ping in a thousand from the deep tail is harmless. For feature changes it is data loss, and those streams need exact keys across the whole horizon even if that means a bigger store — the identity keys in Event Key Generation for Spatial Data are usually low enough in volume to afford it.

  3. A single rotating filter reproduces the original bug on a schedule. When it rotates, every key it held disappears at once, so a redelivery arriving a minute later is admitted. Two slots with both checked is the minimum; three gives margin if the horizon estimate is soft.

  4. The horizon is per sender. Four providers means four horizons, and the TTL must cover the longest. Measuring one and applying it to all is the same mistake as reading it from documentation, with more confidence attached.

  5. A key claimed before processing and never released holds its slot for the full TTL. That is the correct behaviour for suppression, and it means a crash between claim and processing loses the event for the whole horizon. Release on failure, and treat the TTL as the backstop rather than the mechanism.

  6. Bloom filters cannot be resized in place. If the event rate doubles, the existing filter’s error rate rises and there is no way to fix it without rotating early and losing coverage. Size for the peak rate you expect over the filter’s lifetime, and alert when the observed insert count approaches the configured capacity.

One filter rotates into a hole; two do not A rotating probabilistic filter is used to cover the long tail of the retry horizon. With a single slot, the filter is cleared at each rotation, so every key it held vanishes at that instant: a redelivery arriving a minute after a rotation finds nothing, wins its claim, and is written a second time. The bug therefore reproduces the original problem on a twelve-hour cycle, and because it only affects redeliveries that straddle a rotation boundary, it appears as a small periodic spike in duplicate writes that correlates with nothing an operator is looking at. With two slots and both consulted on every check, a key written just before a rotation is still found in the previous slot afterwards, so coverage is continuous and every key is guaranteed at least the full horizon regardless of where in the cycle it was written. The cost is one extra membership check per lookup and twice the filter memory, which is a small fraction of what exact keys over the same horizon would cost. one rotating slot slot A — keys held rotation slot A cleared — every key gone at once a redelivery a minute later wins its claim the original bug, on a 12-hour cycle · a small periodic spike that correlates with nothing an operator watches two slots, both consulted slot A slot B — overlaps A a key written just before a rotation is still found after it every key gets at least the full horizon, wherever it lands Cost: one extra membership check per lookup and twice the filter memory — a small fraction of exact keys over the same horizon.
Figure 3. The rotation is the only moment a probabilistic tier can lose data, so it is the only part of the design that needs to be redundant.

Verification

python 
import pytest

HORIZON = 12 * 3600


@pytest.mark.asyncio
async def test_redelivery_at_the_end_of_the_ladder_is_suppressed(dedup):
    """The failure the TTL exists to prevent, at nine hours."""
    assert await dedup.seen("evt-1", now=0.0) is False
    assert await dedup.seen("evt-1", now=9 * 3600) is True


@pytest.mark.asyncio
async def test_key_written_before_a_rotation_survives_it(dedup):
    """A single filter would fail here; two slots do not."""
    await dedup.seen("evt-2", now=HORIZON - 60)
    assert await dedup.seen("evt-2", now=HORIZON + 60) is True


@pytest.mark.asyncio
async def test_beyond_the_horizon_is_admitted(dedup):
    """Deliberate: past the horizon, a repeat is treated as a new event."""
    await dedup.seen("evt-3", now=0.0)
    assert await dedup.seen("evt-3", now=3 * HORIZON) is False


def test_measured_horizon_exceeds_the_documented_one():
    """The assertion that justifies measuring at all."""
    log = [{"delivery_id": "d1", "received_at": t}
           for t in (0, 60, 300, 1800, 5400, 12_000, 21_600, 33_600)]
    assert measure_retry_horizon(log) > 90 * 60      # documented: 90 minutes

The second test is the one that catches a single-slot filter, and it is worth writing with explicit timestamps around the rotation boundary — a randomised or relative-time version passes most of the time and fails only when the test happens to run near a rotation.