Sweaty Imposter

Bloom Filter

TechniqueApproximationMidSeniorUpdated
Probabilistic set membership in tiny memory. No false negatives; tunable false-positive rate.

When to Use Bloom Filter

When 'might be there' is good enough and you want to short-circuit an expensive lookup. Reading a row that doesn't exist is wasted input/output (I/O); a bloom filter says 'definitely not, skip it.'

In Practice

Cassandra puts a bloom filter in front of every SSTable to skip reads that would miss. Chrome historically used one for the malicious-URL list (millions of URLs, ~2MB).

How Bloom Filter Comes Up in Interviews

Scenario

Cassandra puts a tiny in-memory probabilistic structure in front of each SSTable so reads for keys that don't exist can skip the disk entirely. What is it?

A bloom filter gives O(1) 'definitely not present / maybe present' membership in a few bits per element with no false negatives, perfect for short-circuiting expensive lookups.

Bloom filters are perfect for the 'cheap pre-check before expensive lookup' pattern, and Cassandra's SSTable use case is the textbook one. Each SSTable's bloom filter says either 'definitely not here, skip the disk read' or 'maybe, go check,' with no false negatives. Cassandra ships with ~1% false-positive bloom filters by default (tunable per table), using roughly 10 bits per key. The space-efficiency comes from a small array of bits and k hash functions; the tradeoff is that you can't delete keys without a counting bloom filter variant. The pattern shows up in HBase, LevelDB, RocksDB, Bitcoin's SPV nodes, and Chrome's historical malicious-URL filter.

Where It Comes Up