Bloom Filters

Chain: a HashSet stores the actual keys → 1B URLs averaging ~64 bytes each → ~64 GB of RAM just to remember what you've seen. That won't fit on one machine, so you shard or spill to disk → every membership check may cross the network or hit disk.

A Bloom filter stores no keys at all — only bits. For 1B items at a 1% false-positive rate it needs about 9.6 bits/item ≈ 1.2 GB. That's a ~50x memory reduction, small enough to live in RAM on a single node.

The cost: you give up the ability to retrieve or enumerate keys, and you accept that ~1% of "present" answers are wrong (false positives).

Chain: run the item through all k independent hashes → each produces an index in [0, m) → set the bit at each of those k positions to 1. Example with k=3, m=16: "a.com" hashes to {2, 7, 13} → bits 2, 7, 13 become 1.

Insert "b.com" → hashes to {7, 9, 13} → bits 7 and 13 are already 1, so they stay 1; bit 9 flips to 1. Bits are shared across items and never reset on insert.

The cost: because bits are shared and never cleared, you can never delete from a standard Bloom filter — clearing a bit for one item could silently erase another item that relied on it. Insert is O(k), independent of how many items are already stored.

Chain: query = hash the item with the same k functions → check those k bits → if all are 1, answer "maybe present"; if any is 0, answer "definitely absent."

Once a bit is set to 1 it is never cleared. So if "a.com" was inserted, bits 2, 7, 13 are permanently 1. A query for "a.com" can therefore never find a 0 in those positions → it can never wrongly say "absent." That's the no-false-negatives guarantee.

The asymmetry / cost: the reverse can happen. "c.com" might hash to {2, 9, 13} — all of which were set by other items — so the filter says "maybe present" for something never inserted. That's a false positive, the price you pay for the guarantee.

Chain: false-positive probability is roughly p ≈ (1 − e^(−kn/m))^k. The optimal sizing falls out of this:

• Bits per item: m/n ≈ −1.44 · log₂(p) → for p=1%, that's ~9.6 bits/item → m ≈ 96 Mbit ≈ 12 MB for 10M items.
• Optimal hashes: k ≈ 0.693 · (m/n) → ~7 hash functions.

Why "more hashes" is wrong: more k sets more bits per insert → for a fixed array the bits saturate with 1s faster → past the optimum, false positives go up, not down. (Concretely, with this m: k=7 gives ~1.0%, but k=12 gives ~1.8%.) There's a sweet spot.

The cost: p is fixed at design time by m and k. If your real n exceeds the planned capacity, the array fills and the false-positive rate degrades sharply — and you can't resize a standard filter in place.

Chain: keep one small in-memory Bloom filter per SSTable → on a read, check the filter first → if it says "definitely absent," skip the disk seek entirely. Across several SSTables at a 1% false-positive rate, ~99% of the irrelevant disk reads vanish → a disk seek (~5–10 ms) is replaced by an in-RAM bit check (~100 ns), a ~50,000x gap.

Same pattern elsewhere: a CDN/cache checks "have we ever stored this key?" before a backend round-trip; a crawler checks "seen this URL?" before fetching; Chrome historically pre-screened malicious URLs locally before calling Google's service.

When it does NOT help: the filter only adds value when the answer is usually "no." If most queried items are present, the filter says "maybe" almost every time → you do the expensive lookup anyway plus the filter check → net slowdown. It's a negative-lookup optimizer.

Chain: replace each single bit with a small counter (typically 4 bits). Insert → increment the k counters. Delete → decrement them. A position is "set" if its counter is > 0. Now decrementing for one item doesn't wipe a position another item depends on (those counters are still positive) → safe deletion.

The costs:

• ~4x the memory — 4-bit counters instead of 1-bit slots.
• Counter overflow re-introduces false negatives — a 4-bit counter saturates at 15; once it stops incrementing, later decrements pull it below the true count, so a future delete can drop a still-live position to 0 → a real item now reads "absent."
• Deleting a never-inserted item is unsafe — it decrements counters shared with real items, which can later flip those items to false negatives. CBFs only preserve the no-false-negative guarantee if you delete strictly items you actually inserted.

Chain: use a Scalable Bloom Filter — a chain of sub-filters. Fill filter #1 to its target; when it's saturated, freeze it and start filter #2 with more bits and a tighter target FPR. A query checks every layer and returns "present" if any layer says so.

Why the geometric tightening: because a query consults all layers, their per-layer false-positive rates compound. Shrinking each new layer's FPR by a fixed ratio (r < 1) makes the total a convergent geometric series → the overall false-positive rate stays bounded as n grows without knowing n up front.

The costs: every query now checks all layers → query time grows with the number of layers (more hashing, worse cache locality); and the tightening means total memory is somewhat larger than one perfectly-sized filter would have been. (A Cuckoo filter is the modern alternative: similar space, but supports deletion and better lookup locality — at the cost of more complex inserts that can fail and force a rebuild.)

Model answer: "A Bloom filter gives me an O(k), constant-memory membership pre-check — ~1.2 GB for 1B items at 1% FPR vs ~64 GB for a real set — so I skip the expensive disk/network lookup for items I can prove aren't present."

"The risk I'm accepting is a tunable false-positive rate: ~1% of the time I'll do a wasted lookup that finds nothing, but I will never miss an item that's actually there, and I lose the ability to delete or enumerate keys."

The trade-off in one line: you trade exactness and deletability for a massive space saving and O(1)-ish speed. Name the FPR number, name the no-false-negative guarantee, and name what you gave up — that's the complete answer.