Handling Deletes

In one line

Deleting from the database leaves the item's bits in a standard Bloom filter, producing false positives that the database check absorbs. For frequent deletes, choose between tolerating them with periodic rebuilds, counting Bloom filters, cuckoo filters, or time-windowed filters that expire together.

0/4 · 0%

Think of it like this

Crossing someone off a guest list written in permanent marker. You can't erase them, so the list slowly fills with people who left. Either you tolerate a few wasted checks, rewrite the list every week, or switch to a list that supports erasing.

Key ideas

01
Tolerate: deleted items remain as false positives. Harmless for correctness; the effective FPR rises as deletions accumulate (their bits still count toward the fill).
02
Periodic rebuild: rebuild from the current dataset (nightly or when observed FPR drifts); cheap for moderate sets and naturally purges deleted items.
03
Counting Bloom: decrement counters on delete, only for verified members; ~4× memory.
04
Cuckoo filter: remove the fingerprint; similar memory to Bloom at low error rates; delete only inserted items.
05
Time-windowed filters: when items naturally expire (sessions, daily dedup), keep one filter per window and drop whole filters, instead of deleting individual items.
06
Order of operations with deletable filters: delete from the database first, then from the filter (the reverse would briefly report a present item as absent: a false negative).

Code & diagrams

delete-strategies.txttext

Strategy               Memory     Delete cost   FPR over time          Complexity
Tolerate + rebuild     1x         none          drifts up until rebuild low
Counting Bloom         ~4x        O(k)          stable                 medium (verify before delete)
Cuckoo filter          ~1x        O(1)          stable                 medium (headroom, dup limit)
Time-windowed filters  1x/window  drop filter   stable per window      low (only for expiring data)

Interview problem

The problem

Frequent deletes

A membership set sees frequent deletes (about 20% of items churn per week). Evaluate a standard Bloom filter, a Counting Bloom filter, a Cuckoo filter and periodic rebuilds.

Explain it without notes

Why must you delete from the database before deleting from a deletable filter?

Practice

Estimate the FPR drift for a filter sized for 10M items at 1% after 5M deletions and 5M new insertions without a rebuild.

Trade-offs

↔
Deletable filters avoid rebuilds but cost memory or complexity; rebuilds are simple but need a pipeline and cause periodic drift.

Done when you can

I can choose and implement a delete strategy that keeps the filter correct and efficient.

Command Palette