Bloom Filters

Why LSM engines need this

B-Tree vs LSM Storage Engines mentioned that reads check the memtable plus every SSTable on disk, newest first, and that Bloom filters skip absent keys. This subtopic is that claim, expanded to interview depth: what the filter actually is, why it can never miss a real hit, and why "possibly present" still costs a disk seek.

The structure, in one picture

A Bloom filter is a bit array of size m plus k independent hash functions. Insert hashes an item k ways and sets those k bits; a query hashes the same way and checks all k bits.

add("user:42") -> set bits [3, 17, 55] might_contain("user:42") -> bits [3, 17, 55] all 1 -> "maybe present" might_contain("user:99") -> bit 17 is 0 -> "definitely absent"

One-sided error is the whole design. A "definitely absent" answer is always correct — no false negatives. A "maybe present" answer can be a false positive: some combination of other keys' insertions happened to set the same bits. There is no delete on a plain filter (clearing a bit can belong to several keys); a counting Bloom filter trades more memory per slot for that capability.

Sizing it — the parameter an interviewer expects you to name

Given	Choose
n items, target false-positive rate p	m = -(n·ln p) / (ln 2)² bits, k = (m/n)·ln 2 hash functions

Saying "use a Bloom filter" without a target p is an incomplete answer — the false-positive rate is the tunable knob the whole structure exists to let you set, not an accident of implementation. A well-tuned SSTable filter typically runs ~1% false-positive rate at roughly 1 byte per key.

Where it sits in the read path

GET key -> check memtable -> check Bloom filter per SSTable (newest to oldest) filter says "absent" -> skip that SSTable entirely, zero disk I/O filter says "maybe" -> actually read the SSTable to confirm

Cassandra, HBase, RocksDB, and LevelDB all attach one Bloom filter per SSTable for exactly this reason: a key that doesn't exist would otherwise force a disk seek against every SSTable that might contain it. At a 1% false-positive rate, the filter turns ~99% of "not here" lookups into a pure in-memory check instead of a disk read — the entire point of the LSM read path's "check filter before disk" step from the previous subtopic.

A second common production use, outside storage engines: browsers ship a Bloom filter of known-malicious URLs (Chrome's Safe Browsing) so a "definitely safe" verdict never needs a network round-trip; only a "maybe malicious" hit triggers the authoritative server check.

Not covered here

Why hash collisions happen far sooner than intuition suggests (the birthday paradox this filter's false-positive math descends from) — see the DSA roadmap's Hash Table Internals & the Birthday Paradox subtopic. "How many distinct keys have I seen" (a different question — cardinality, not membership) is HyperLogLog, covered in Application Caching & Specialized Stores.

Where this goes next

External Sort & Large Queries covers the other classic "doesn't fit in memory" problem — sorting, instead of point lookups.