The question this answers
Given that duplicates will arrive, where and how do I detect them without storing every identifier forever?
A duplicate carrying a recognised identity is suppressed within the dedup state’s window, partition and availability scope. Outside those, a duplicate passes through undetected and unreported. Note the asymmetry that governs every design here: a false negative costs a duplicate; a false positive silently discards a real message, and nothing anywhere records that it happened.
Everything below is bought to hold this sentence. "Strongly consistent" with no scope attached is a slogan, not a guarantee — read what it actually covers, and what it explicitly does not.
A dedup node knows the identities in the state it currently holds. It cannot distinguish "I have never seen this" from "I saw this and forgot it" or from "another node saw this and I have no idea". That inability is the whole design problem: every dedup mechanism is an attempt to make the first meaning the overwhelmingly likely one, for a bounded cost.
A node knows its own state and the messages that arrived. Everything else is inference from evidence that was already stale. "B has not replied in five seconds" is knowledge; "B is down" is a decision — and usually the bug.
Try to need no dedup state at all
Before building a dedup store, check whether the sink can absorb the duplicate by construction. If the record has a natural business key — an order number, a payment reference, a device id plus a reading timestamp — then an upsert on that key makes a duplicate write a no-op. No separate state, no retention policy, no extra store, no window, and the mechanism inherits the sink’s availability and failure domain automatically.
This is dramatically the best option when it applies, and it is under-used because dedup is usually approached as a stream problem rather than a sink problem. INSERT … ON CONFLICT (order_ref) DO NOTHING and its equivalents solve more duplicate problems than any dedup service ever will, and they cannot silently lapse.
The second option that needs no general state is a monotonic sequence per producer. If each producer numbers its messages and messages from one producer are processed in order, the consumer stores a single high-water mark per producer and discards anything at or below it. State is O(producers) rather than O(messages) — a decisive difference at volume. This is exactly how Kafka’s idempotent producer deduplicates, and how TCP discards retransmissions (the same idea appears at the transport layer, where sequence numbers let a receiver discard a retransmission). It requires ordered submission per producer, which is the condition that rules it out when it does not fit.
| Approach | State size | Exact? | Requires |
|---|---|---|---|
| Upsert on natural key at the sinkprotocol | None extra | Yes | A natural key and a sink that can upsert |
| Per-producer sequence watermarkprotocol | O(producers) | Yes | Ordered submission per producer |
| Unique constraint on (tenant, client ref)protocol | One index | Yes | The effect is a row write |
| Keyed dedup table with TTLassumption | O(ops in window) | Yes, in window | A retention decision and storage |
| Bloom filter in front of an exact storeassumption | O(bits) | No — as a filter only | An exact check behind it |
The asymmetry that rules out naive probabilistic dedup
A Bloom filter is the obvious tool for "have I seen this?" with bounded memory, and it is used constantly in dedup designs. Its error direction is what matters, and it is the wrong way round for the naive use.
A Bloom filter never produces a false negative: if it says *not present*, the item is definitely not present. It can produce a false positive: it may say *present* for something it has never seen. So a design that reads "if the filter says present, discard as a duplicate" silently discards genuine messages at the filter’s false-positive rate. There is no error, no log entry, no retry — the message simply ceases to exist. A 1% false-positive rate on a payments stream is not a performance characteristic; it is a data-loss rate.
The correct construction inverts the reliance: use the filter for its *reliable* answer. If the filter says not present, the item is definitely new — accept it immediately without touching the exact store. If the filter says present, it *might* be a duplicate, so consult the exact store to find out. The filter becomes a fast path that eliminates most lookups against an expensive store, and it never makes the final decision. This is the same role Bloom filters play in an LSM tree, and for the same reason (Database owns the filter’s internals).
1# WRONG — the filter decides, so false positives delete real messages.2if bloom.might_contain(id):3 drop_as_duplicate(msg) # ~1% of these are genuine messages4else:5 bloom.add(id); process(msg)6 7# RIGHT — the filter only answers "definitely new", which it never8# gets wrong. Everything else falls through to an exact check.9if not bloom.might_contain(id):10 bloom.add(id)11 process(msg) # definitely new: no store lookup at all12else:13 if store.claim(id): # exact, atomic; the filter was a hint14 process(msg)15 else:16 drop_as_duplicate(msg)17# Result: ~99% of new messages skip the store, and no message is ever18# discarded on a probabilistic answer.Windows: what you forget is what you will duplicate
Exact dedup state must be bounded, so it forgets. The window is therefore the guarantee’s boundary, and every eviction is a duplicate you have chosen to accept later (What Counts as the Same Operation? makes the same argument for request keys).
Two clocks can define the window and they behave differently. A processing-time window ("remember the last 30 minutes of arrivals") is simple and bounds memory directly, but a message delayed by a broker backlog beyond that window passes through as new. An event-time window ("remember ids for events whose timestamp is within the current watermark") aligns with the data’s own notion of time and handles delayed messages correctly, at the cost of needing watermarks and of holding state for as long as you are willing to wait for stragglers (Two Clocks: When It Happened and When You Saw It, Watermarks: A Guess About Time, Made Precise Enough to Act On, Late Events: The Window Already Fired).
The operational failure is quiet in both cases. The state grows until eviction begins, evictions start, and duplicates begin passing through — with no error, and often with no metric, because "cache size" and "duplicate rate" are not usually on the same dashboard. Eviction rate is the leading indicator and must be instrumented, along with the age of the oldest retained identity, which tells you the window you actually have rather than the one you configured.
dedup_state_entries 2,940,112 (cap 3,000,000) oldest_retained_age 00:11:04 <- configured intent: 30m eviction_rate 1,840/s <- was 0/s until 09:52 duplicate_passthrough rising # Traffic grew; the cap, not the TTL, now defines the window. # Effective window fell from 30m to 11m without any config change, # and every retry slower than 11m is now a duplicate that gets through.
Dedup state is distributed state
A dedup check that requires a network round trip to a shared store adds that store’s latency to every message and its availability to your pipeline’s availability. The way out is to make the check local, and the way to make it local is to partition the stream by the dedup key so every occurrence of a given identity lands on the same node. Then the state for that key lives with the node that processes it, and the check is a memory lookup (Hash Partitioning and the Modulo Trap, Move the Computation to the Data).
The cost is that the dedup state is now partition-local, which makes rebalancing a correctness event rather than a performance one. When partitions move — a scale-up, a deploy, a failure — the state must move with them. If it does not, the new owner has no memory of the keys it has just inherited, and duplicates pass through for exactly the duration of the rebalance. Stream processors solve this with checkpointed keyed state that is restored on the new node; a hand-rolled in-memory dedup map does not, and the failure appears as a small duplicate burst at every deploy, which is easy to dismiss as noise (Rebalancing: A Load Spike You Schedule for Yourself, Rebalancing: Everyone Stops So the Partitions Can Move).
And the same failure-domain question from What Counts as the Same Operation? applies: if the dedup state is regional and the effect fails over, the duplicates arrive precisely during the failover. Dedup state that does not fail over with the effect is not protecting you during the incident that generates the retries.
What happens when the dedup store is unavailable
A dedup store that is a separate service will eventually be unreachable, and you must choose in advance what happens then. Fail open — process without checking — keeps the pipeline available and admits duplicates for the duration. Fail closed — refuse to process — preserves the guarantee and stops the pipeline. This is exactly the fail-open versus fail-closed choice Security frames for authorization, and the answer depends on which failure is more expensive for the specific effect.
For a payments pipeline, failing closed is usually right: a stall is recoverable, a duplicate charge is a refund and a support case. For a search-index update, failing open is usually right: a duplicate index write is idempotent anyway and a stalled index is worse. The mistake is not choosing — a default that nobody decided will be whatever the client library does on a timeout, which is typically fail-open with an exception swallowed somewhere.
This is also the strongest argument for co-locating the dedup claim with the effect in one store. When they are the same store, "the dedup store is down" and "the effect store is down" are the same event, so there is no partial mode to choose a policy for, and the correctness question disappears into an availability question you already had.
- Fail closed for effects where a duplicate is expensive and irreversible.
- Fail open for effects that are idempotent at the sink anyway.
- Never fail open silently — count it, so the duplicate window is a known quantity afterwards.
- Co-locate where possible, which removes the choice entirely.
Key points
- Try to need no dedup state: upsert on a natural key at the sink, or a per-producer sequence watermark.
- A false positive discards a genuine message silently — the error direction that matters, and the reason a Bloom filter must never make the final call.
- Use a Bloom filter for its reliable answer ("definitely new") as a fast path in front of an exact check.
- The window is the guarantee’s boundary; every eviction is an accepted future duplicate, so eviction rate must be instrumented.
- A cap reached before a TTL silently shortens the window without any configuration change.
- Partition by the dedup key so the check is local — and then treat rebalances as correctness events, because state must move with the partition.
- Decide fail-open versus fail-closed for a dedup store outage deliberately, or co-locate the claim with the effect and remove the choice.
The chain, answered
Every field here is required, which is why no lesson in this domain can recommend a design without naming what an operator sees when it fails, what survives the partition, what repairs it afterwards, and the simpler thing to consider first.
- • Choose an identity: a natural business key where one exists, otherwise a producer-supplied message id.
- • Choose a location: the sink (upsert), the consumer (keyed state), the producer (sequence numbers), or a shared store.
- • Partition the stream by that identity so all occurrences reach the same node and the check is local.
- • Optionally place a Bloom filter in front, used only to short-circuit the definitely-new case.
- • Perform an atomic claim against exact state — a conditional insert, a unique constraint, or a keyed state update — in the same commit as the effect where possible.
- • Bound the state by a window derived from the maximum realistic redelivery delay, and checkpoint it so it survives rebalances.
- • Emit metrics for hits, evictions and oldest retained age, because the mechanism fails silently in all three directions.
- • A false positive from a probabilistic filter drops a real message with no trace.
- • The window expires or the cap evicts before a delayed duplicate arrives.
- • A rebalance moves a partition without its dedup state, opening a duplicate window.
- • The dedup store is unreachable and the pipeline fails open without counting it.
- • The stream is partitioned by a different key than the dedup identity, so occurrences land on different nodes.
- • Two nodes concurrently claim the same identity because the claim is not atomic.
- • Key cardinality grows beyond the memory budget and evictions begin under load, exactly when duplicates are most likely.
- • The dedup state is in a different failure domain from the effect and does not survive a failover.
- • Silent message loss from a probabilistic filter: a payment appears nowhere downstream, there is no error, no DLQ entry and no log line. The only evidence is a reconciliation gap whose rate matches the configured false-positive rate.
- • Duplicate burst at every deploy: the operator sees a small spike in duplicate effects on each rolling restart, correlated with nothing else. Dedup state is in memory and does not survive partition reassignment.
- • Window collapse under growth: eviction rate goes from zero to thousands per second when traffic grows past the state cap, and duplicates start passing through. The configured TTL is unchanged and still looks correct in the config file.
- • Latency regression from a remote dedup check: p99 rises by the dedup store’s p99 on every message, and the pipeline’s availability becomes the product of two services rather than one.
- • Undetected fail-open: the dedup client swallowed timeouts and processed without checking for eleven minutes. Nobody knew until duplicates surfaced downstream, and the window could not be bounded after the fact because nothing counted it.
- • Cross-partition misses: the topic is partitioned by customer id while dedup is keyed by message id, so retries of one message land on different partitions and the local state never sees a repeat.
- • A local, partitioned dedup check needs no coordination at all — the partitioning is what buys that, and it is the main reason to align the partition key with the dedup key.
- • A shared dedup store is a coordination point on every message: its latency joins the critical path and its availability multiplies with the pipeline’s.
- • Co-locating the claim with the effect makes the coordination free by folding it into a transaction that already exists.
- • Rebalancing is coordination about ownership, and dedup state makes it a correctness-critical one rather than a purely operational one.
- • Within the window and the owning partition, duplicates are suppressed reliably.
- • Across a rebalance without state transfer, duplicates pass through for the duration of the redelivery window.
- • After an eviction, a repeated identity is indistinguishable from a new one and is processed as new.
- • When the dedup store is unavailable, behaviour is whatever the fail policy is — and if no policy was chosen, it is whatever a library default does.
- • Effects already applied are unaffected; dedup only prevents future repeats, never repairs past ones.
- • Detect: monitor hit rate, eviction rate and oldest-retained-age together. Any one alone hides the failure.
- • Contain: prefer fail-closed for expensive effects, and always count the messages processed without a check so the exposure window is bounded afterwards.
- • Recover: re-run dedup at the sink by natural key for any window where the stream-level mechanism lapsed — a second, independent line of defence that does not share the first one’s state.
- • Reconcile: compare distinct source identities against distinct sink records for the affected period; the difference gives both duplicates and losses.
- • Verify: confirm eviction rate returns to zero and that the effective window (oldest retained age) matches the configured intent, not just the config value.
- • Dedup hit rate — duplicates suppressed per second. Normally small and non-zero; a sudden zero means the mechanism has stopped working, not that duplicates stopped.
- • Eviction rate and state size against the cap. Evictions are accepted future duplicates and should be a deliberate number, not a surprise.
- • Age of the oldest retained identity — the *effective* window, which diverges from the configured TTL as soon as a cap binds.
- • Duplicate rate measured independently at the sink by natural key, which does not trust the dedup mechanism and is the only check that catches a total lapse.
- • Messages processed without a dedup check (fail-open events), counted explicitly.
- • Dedup state restore time after a rebalance, which is the length of the duplicate window on every deploy.
- • Bloom filter fill ratio and estimated false-positive rate, if one is in the path — a filter that has filled past its design point silently degrades.
- • High-volume streams where per-message durable claims would be too expensive and a partitioned in-memory check is cheap.
- • Consumers of at-least-once brokers, where duplicates are routine and the effect is not naturally idempotent (Where You Put the Acknowledgement Decides Everything).
- • Pipelines with a natural key at the sink, where an upsert removes the problem entirely at zero ongoing cost.
- • Producer-side sequencing, where a small per-producer watermark replaces per-message state.
- • When the effect is already idempotent, in which case dedup adds cost and a failure mode for nothing.
- • When a probabilistic filter is allowed to make the final decision, converting a duplicate problem into a silent loss problem.
- • When the dedup store is remote, adding latency to every message and a new dependency to the pipeline.
- • When the window is chosen from convenience rather than from the redelivery horizon, so it lapses exactly for the slow retries that matter most.
- • When it is treated as a substitute for idempotence at the sink rather than an optimisation in front of it — it will lapse, and the sink is what catches it.
- • Upsert by natural key at the sink — no state, no window, no separate failure mode (Idempotent Is a Property of the Whole Effect, Not the Write).
- • Per-producer monotonic sequence numbers with a watermark per producer, which is exact and O(producers).
- • A unique constraint in the target table, which is exact, transactional and automatically shares the effect’s failure domain.
- • Commit the input position and the output atomically, so duplicates are collapsed at commit rather than detected (Exactly-Once Is a Scope, Not a Guarantee).
- • Accept duplicates and reconcile in batch, where the effect is cheap and reconciliation is straightforward (Reconciliation Is a Component, Not a Cleanup Script).
Bounded memory against an unbounded stream
What people believe, and what is true
A Bloom filter is a good deduplicator.
Only as a fast path in front of an exact check. Used alone it discards genuine messages at its false-positive rate, silently, with no error to detect.
We keep dedup keys for an hour, which is plenty.
It covers client retries. It does not cover a DLQ drained the next morning, a webhook sender retrying for three days, or an operator re-driving a batch next week. The window must be derived from the longest legitimate replay path.
Our dedup cache has a 30-minute TTL, so the window is 30 minutes.
Only until the size cap binds. After that, evictions define the window, and it shrinks with traffic growth while the config still reads 30 minutes.
Dedup state is just a cache, so losing it is harmless.
Losing it means duplicates pass through. It is correctness state that happens to be stored like a cache, and rebalances and restarts must preserve it.
The dedup store went down but we kept processing, so nothing bad happened.
You processed without checking. Duplicates from that window are in your data, and if nothing counted the fail-open events you cannot even bound which ones.
Deduplicating in the stream means the sink does not need to be idempotent.
Stream dedup lapses at rebalances, evictions and failovers. Sink-level idempotence is the layer that catches those, and it is usually cheaper than the stream layer anyway.
Go deeper
Only the levels this lesson can honestly fill — a missing level is a claim nobody had.
Overview
Deduplication is remembering what you have already seen, with memory that runs out. Prefer designs that need no memory: upsert on a natural key, or a sequence number per producer.
Practical
Partition by the dedup key so the check is local. Use a Bloom filter only to short-circuit "definitely new". Derive the window from the longest realistic replay path, and instrument eviction rate and oldest-retained-age — the effective window is not the configured one once a cap binds. Choose fail-open or fail-closed deliberately and count fail-open events. Keep an independent sink-level check, because the stream-level one will lapse.
Advanced
Dedup state is keyed state and inherits every property of partitioned state: it must be co-partitioned with the stream, checkpointed so it migrates on rebalance, and sized so the cap never binds before the TTL. The subtle failure is that all three degrade silently and in the same direction — toward more duplicates — with no error path. That is why the only trustworthy measurement is an independent count at the sink by natural key: it does not share state, code, or failure domain with the mechanism it is checking.
Apply it
- 🔧 Implement dedup with a Bloom filter as the sole check, run a stream with a known duplicate rate, and measure how many genuine messages disappear.
- 🔧 Fill a dedup cache past its size cap under load and chart the effective window (oldest retained age) against the configured TTL.
- 🔧 Restart a consumer with in-memory dedup state and measure the duplicate burst. Then add checkpointed state and repeat.
- ⚡ A reconciliation finds 0.9% of source records missing at the sink, with no errors anywhere in the pipeline. What would you suspect first?
- ⚡ Duplicates appear only for messages that were delayed by more than about eleven minutes, and only since traffic doubled. Explain.
- ⚡ A stream is partitioned by customer id and deduplicated by message id. Why does the dedup rate look implausibly low?
- 💬 Why is a Bloom filter dangerous as the sole deduplicator, and how would you use one correctly?
- 💬 How would you choose the dedup window? What inputs go into the number?
- 💬 Your dedup TTL is 30 minutes but duplicates are getting through. The config has not changed. What do you check?
- 💬 Where should dedup state live relative to the stream partitioning, and what breaks if they disagree?
- 💬 The dedup store is unreachable. Should the pipeline keep processing?
- 💬 Why keep sink-level idempotence when you already deduplicate in the stream?