Why architecture matters here
The architecture matters because read amplification is the defining cost of LSM engines, and Bloom filters are the primary weapon against it. Because a key may exist in many SSTables, a point read without filters degrades toward checking all of them, each check being a random disk seek. For lookups of keys that are absent — cache misses, existence checks, first-time inserts that must confirm no prior value — every one of those seeks is pure waste. A Bloom filter turns 'check N files on disk' into 'check N tiny bitmaps in memory and only read the one or two that might match,' which can cut read I/O by an order of magnitude.
It matters because the guarantee it provides — no false negatives — is precisely the guarantee a read path can build on. If a filter said 'not present' for a key that was actually there, the engine would return wrong answers, which is unacceptable. Bloom filters never do that: a 'no' is always true. A 'yes' can be wrong (a false positive), but the only cost of a false positive is one unnecessary disk read that then finds nothing — a performance blemish, never a correctness bug. That one-sided error is what makes the structure safe to short-circuit reads with.
It matters because the trade-off is smoothly tunable, letting operators dial the memory-versus-I/O balance per workload. More bits per key and an optimal number of hash functions push the false-positive rate down toward a fraction of a percent at the cost of more RAM; fewer bits save memory at the cost of more wasted reads. Because filters are small, this is a cheap knob with a large effect, and getting it right is often the difference between a working cache-cold read path and a saturated one.
The architecture: every piece explained
The bit array (m bits). At its core a Bloom filter is an array of m bits, all initially 0. The array represents a set of keys without storing the keys themselves — it stores only the footprints they leave. m is chosen relative to the number of keys n and the target false-positive rate; a common rule of thumb is about 10 bits per key for roughly a 1% false-positive probability. Because it holds bits, not keys, the filter is dramatically smaller than the data it guards and fits comfortably in memory.
The k hash functions. Each key is run through k independent hash functions, each producing a position in the bit array. On insert, all k of those bit positions are set to 1. On test, the same k positions are examined. Using several hash functions spreads each key's footprint across the array so that different keys are unlikely to fully overlap, which is what keeps the false-positive rate low. In practice k is often synthesized cheaply from two base hashes rather than computing k fully independent hashes.
The test operation and its asymmetry. To test membership, hash the key to its k positions and read those bits. If any is 0, the key was never inserted — a 0 could only be there if this key had not set it — so the answer is a definitive 'not present.' If all are 1, the key is 'possibly present': either it really was inserted, or its k positions happen to have been set by other keys. That coincidence is the false positive, and it is the only error the structure can make.
The LSM placement. In an LSM engine every SSTable is written with its own Bloom filter over the keys it contains, and that filter is loaded (or block-cached) in memory. A point lookup walks the relevant SSTables and consults each filter first; SSTables whose filters say 'no' are skipped without any disk access, and only 'maybe' SSTables have their index and data blocks read. Filters are immutable per SSTable, just like the SSTables themselves, so they are built once at flush/compaction time and never mutated.
End-to-end flow
When an SSTable is created — by flushing a memtable or by compacting several SSTables into one — the engine builds a Bloom filter over exactly the set of keys that file contains. It sizes the bit array from the key count and the configured bits-per-key, computes k positions for each key with the hash functions, and sets those bits. The finished filter is written alongside the SSTable and typically pinned in memory so it can be consulted without disk I/O later.
On a point read for some key, the engine determines which SSTables could hold it (across memtable and the LSM levels) and, for each, tests the filter first. For a key that does not exist anywhere, most or all filters return 'not present,' and the engine skips those files entirely — the read completes having touched only memory. This is the dominant win: existence checks and misses, which are extremely common, are answered without a single random seek.
For an SSTable whose filter returns 'maybe,' the engine proceeds to actually read: it consults the SSTable's index to find the data block, reads that block, and looks for the key. Usually the key is there (a true positive) and the value is returned. Occasionally the filter was wrong and the key is absent (a false positive) — the engine has paid for one wasted block read and moves on. The false-positive rate directly controls how often this waste happens.
Over time, as writes accumulate and compaction reshapes the levels, SSTables are created and destroyed and their filters are rebuilt to match. Because a Bloom filter cannot delete individual keys, a key that is deleted (tombstoned) or overwritten does not get removed from an existing filter — it simply disappears when the SSTable containing it is compacted away and a fresh filter is built over the surviving keys. This is why the filter's immutability aligns naturally with the LSM's immutable-file design.