Bloom filter
A space-efficient probabilistic structure that says 'definitely not here' or 'maybe here' for set membership. No false negatives, some false positives. Used to avoid expensive lookups for keys that don't exist.
- Avoiding expensive lookups for non-existent keys (cache, disk, DB).
- Pre-filtering before a slow path.
- When you need exact membership or deletion.
- Small sets where a hash set is fine.
Definition
A Bloom filter is a bit array + k hash functions. To add, set k bits; to query, check k bits — all set means 'maybe present', any unset means 'definitely absent'. Items can't be removed (Counting Bloom filters can).
Why it exists
Checking whether a key exists before an expensive DB/disk lookup saves huge work for negative queries. Bloom filters do this in a few bytes per item with tunable false-positive rate.
How it works
Choose bit-array size m and hash count k for a target false-positive rate p. Insert sets k bits; lookup checks them. As the filter fills, false positives rise; rebuild when over capacity. Used in Cassandra (SSTable lookups), Postgres (BRIN-ish), CDNs.
Scaling limits
False positives cost an unnecessary lookup; rate grows with load. Can't remove items (use Counting Bloom or Cuckoo filter for deletes). Can't list members. Needs a rebuild to shrink.
Cost shape
Tiny memory (bits per item). Blow-ups: overfilled filters with high false-positive rates causing many wasted lookups.
Alternatives
- Cuckoo filter — Supports deletion and similar space, more complex.
- Hash set — Exact but uses far more memory.
Failure modes
- High false-positive rate from under-sizing.
- Stale filter not rebuilt after deletions.