Seen-sets in your projects — dedup, hidden users, and why exact is fine

The applied version: enumerate your membership tests, then show the arithmetic that says "exact is correct here."

The inventory

The cost math (do it out loud in interviews)

• Traverse's largest membership set per request: a user's blocks + friends + solved problems. At 100 users: hundreds of rows. At 1M users with 200 friends and 500 solves each: the per-request set stays ~700 rows — membership filtering is O(user's own data), independent of total scale. That's the structural reason exact sets are correct here: the filter is per-user and bounded, so Bloom's memory advantage never materializes.
• Where Bloom would appear in traverse: "have we ever seen this problem slug globally?" during bulk import at millions of rows — a global keyspace, where a false positive means skipping a new problem (a data-loss-ish outcome — so you'd still want exactness, or a two-tier check: Bloom to reject obvious dupes, exact confirm before skipping).
• Zoth's dedup table grows unbounded (Day 42's gap) — that's where a Bloom tier could help at scale (reject obviously-seen event ids before the insert-on-conflict), with the exact constraint still enforcing truth. Two-tier membership: Bloom for speed, exact for truth — the pattern to name.

The correctness framing to carry

Every membership filter is a decision boundary: ask "what happens on a false positive?" before choosing an approximate structure. In your systems the answer is always "data loss, wrong stats, or a security gap" — hence exact everywhere, and hence unique constraints as the final arbiter rather than application checks. The day a filter's false positive is cheap (recommendation dedup, "you might like"), reach for the sketch — and say exactly why.

Where exact stops being fine (the arithmetic)

The honest version of "exact is fine here" is a boundary, not a preference. Four regimes:

1. Per-user, bounded sets (your actual case). Filter size = the user's own friends + blocks + solves. At 100 users that is tens of rows; at a million users with 200 friends and 500 solves it is still ~700 rows, because the set is scoped to one user. The filter does not grow with total system size, which is the structural reason exact is correct. The rule to state: a membership test is cheap when the set is per-actor and bounded, and expensive when the set is global and unbounded. Everything below is about the second case.

2. Global, growing key spaces. "Have we ever seen this event id?" (Zoth's processed_events), "have we ever indexed this problem slug?", "has this URL been crawled?" — these grow with total volume, so an exact set's memory grows linearly and its working set stops fitting in cache. This is where approximation earns its place.

3. Where a false positive is cheap. A Bloom filter in front of a recommendation-dedup check: a false positive means one "you might like" is skipped out of thousands, which no user will ever notice. The economics are simple — a tiny probability of a slightly worse recommendation in exchange for a large constant-factor memory saving. The decision rule is not "is approximation fast" but "what does a false positive cost."

4. Where a false positive is expensive. Your actual filters: a false "already solved" means the user gets no credit for real work; a false "already processed" in Zoth means a revocation is silently dropped, which is a security failure; a false "already seen" on a submission means lost data. In all three the approximate structure's error is a correctness or security bug, so approximation is unavailable at the enforcement layer — ever.

The mechanics, and the two-tier pattern

Bloom filter: a bit array of m bits and k hash functions; insert sets k bits, query checks all k and answers "definitely not present" or "possibly present." The operational properties:

• No false negatives. This is why Bloom is safe as a pre-filter: "definitely not present" is trustworthy, so a rejection never drops a genuinely new item. The asymmetry is the entire design.
• False positives are tunable. With n expected elements and m bits, optimal k = (m/n)·ln 2 and the false-positive rate is roughly (0.6185)^(m/n). For 1% you need about 10 bits per element — so 1M items cost ~1.2 MB. That number is the whole selling point: 1.2 MB to answer membership over a million items, versus hundreds of megabytes for an exact set.
• No deletion. Clearing a bit would create false negatives for every other element sharing it. Deletable variants exist (counting Bloom, cuckoo filters, quotient filters), each adding memory or complexity. If your set has deletions, a plain Bloom is the wrong structure — which matters for Zoth, where any key space with expiry semantics cannot use one naively.
• No enumeration. You cannot list the elements. Fine for dedup, useless for "show me the seen set."

The two-tier pattern is the production answer wherever both speed and truth matter:

write path:  exact store (Postgres, unique constraint)   <- source of truth
             + optionally maintain a Bloom/cuckoo mirror for fast negative answers
read path:   Bloom says "definitely not present" -> skip the DB entirely
             Bloom says "possibly present"        -> ask the exact store
             exact store is authoritative in every case

This is what makes the sketch safe: it can only avoid work, never decide an outcome. A false positive costs one unnecessary lookup; a false negative is impossible by construction. Applied to Zoth's processed_events, the payoff is concrete — the overwhelming majority of incoming events are new, so a Bloom mirror answers most of them without touching Postgres, while the unique constraint still guarantees no event is processed twice.

Roaring bitmaps are the third option worth knowing: compressed sorted sets of integers where each 64-bit space is split into 2^16 chunks, each stored in whichever container is cheapest (array for sparse, bitmap for dense, run-length for ranges). They are exact, compact (roughly 1–2 bytes per element in the sparse regime), and support fast AND/OR/XOR. That makes them the right answer for exact set algebra at moderate cardinality: "users who solved problem A and problem B", "users active on day X but not day Y". For Traverse, a per-problem bitmap of solvers combined with AND across two problems is a design that is exact and still fits in memory — and it beats Bloom for anything where you need the actual membership list.

The closing rule to carry: state the false-positive cost before naming the structure. If it is "one wasted lookup," approximate freely. If it is "lost data, wrong stats, or a dropped revocation," the sketch may only sit in front of an exact store — never in place of one. That single question resolves every membership-design decision in this course, and it is the same question that governs caching, retries, and deduplication everywhere else.