How do you bound a Python dedupe set that tracks seen keys in a long-running service?

## The failure mode The deduplication idioms that work in a script assume a finite input. A long-running service does not have one. A fraud-scoring service that keeps a module-level `seen = set()` so it never scores the same request twice has written a cache with no eviction policy, and the only thing limiting it is how long the process stays up. At a 1,200-request-per-minute peak that is 72,000 keys an hour and about 1.7 million a day; with 36-character request ids the set alone runs into hundreds of megabytes before anything else has grown, and resident memory climbs in a slow, boring line until the process is restarted or killed. Nothing in the code looks wrong, which is precisely why it survives review. ## Bounding by count The cheapest bound is a fixed number of remembered keys with first-in-first-out eviction. Membership needs O(1), and a `set` gives that; eviction needs to know which key is oldest, and a `collections.deque` with `maxlen` gives that. The two must be kept in step: ```python from collections import deque class BoundedSeen: def __init__(self, maxlen): self._order = deque(maxlen=maxlen) self._seen = set() def add_if_new(self, key): if key in self._seen: return False if len(self._order) == self._order.maxlen: self._seen.discard(self._order[0]) self._order.append(key) self._seen.add(key) return True ``` The `discard` before the append is the whole trick, and it is exactly where this gets written wrong. Appending to a full deque silently drops the leftmost element; if you do not remove that element from the set first, the set keeps growing while the deque stays flat, and you are back to an unbounded structure that merely looks bounded. Off-by-one at that boundary is the other classic: checking `len(self._order) > self._order.maxlen` never fires, because a deque never exceeds its maxlen. A plain `dict` can do the same job on its own, using keys as the queue and relying on guaranteed insertion order to find the oldest key. Promoting a key on a hit turns the structure into an LRU rather than a FIFO, which is better when the duplicate arrival pattern is bursty rather than uniform. ## Bounding by time Count-based bounds are awkward when the real requirement is temporal: "the same request id must not be scored twice within ten minutes". Expressing that as a count means guessing the rate, and the guess breaks during a traffic spike, which is exactly when duplicates cluster. Bucketing is more honest: keep a small mapping from a coarse timestamp, a minute, to the set of keys first seen in that minute; look a key up across the buckets in the window; drop buckets that fall out of it. Eviction is then dropping whole sets, which is one operation rather than many, and the memory ceiling is the arrival rate times the window rather than a number you invented. ## The tradeoff you must state out loud Every bounded deduplicator is approximate. A duplicate whose original has already been evicted is not recognized, so it is processed a second time. That is not a bug to be fixed, it is the price of the bound, and the design decision is where to set it: the window must comfortably exceed the realistic gap between a message and its retry. Sizing it from the actual retry policy and the actual peak rate is the senior part of the answer; sizing it from a round number is how a deduplicator quietly stops deduplicating during the one incident that matters. The second tradeoff is what you store. Keys, never payloads: a 36-character id costs a fraction of the record it identifies. Where even the keys are too many to hold, a fixed-size probabilistic membership structure trades a small false-positive rate for constant memory, which changes the failure mode from "processes a duplicate" to "occasionally skips a unique item", and that is a decision for the domain, not for the code. ## Operating it A bounded structure should be observable. Export the current size, the eviction count and the hit rate, because a hit rate that collapses is the signal that the window has become too small for the current traffic, and an eviction count of zero at peak means the bound was never reached and the sizing was pure guesswork. Where duplicates must be suppressed across processes or across restarts, in-process state is the wrong home entirely, and the answer is an external store with its own expiry rather than a bigger set. ## Interview framing The question is a differentiator, not a gate. Candidates who have only deduplicated batches reach for the module-level set and see nothing wrong. Candidates who have run a service ask, unprompted, how long the process lives and what bounds the state.