Bloom Filters: Probabilistic Set Membership

The problem: read amplification, again

The previous lesson showed that a GET might have to check the memtable plus every SSTable across every level before it finds — or fails to find — a key. Checking a file means at minimum reading its block index; in the worst case (key genuinely absent) you pay that cost against every single layer just to conclude "not here." A bloom filter lets you skip that cost for the common case: "this SSTable definitely does not contain this key" — answered in-memory, with no disk I/O at all.

What a bloom filter actually guarantees

A bloom filter is a probabilistic set membership structure with a specific, asymmetric error profile:

• If it says NO, the key is definitely not in the set — zero false negatives, guaranteed.
• If it says MAYBE, the key is probably in the set, but might not be — false positives are possible (and expected), at a rate that's tunable by sizing.

That asymmetry is exactly what an SSTable read path needs: check the bloom filter first, and if it says NO, skip the file entirely — no risk of missing a real key. If it says MAYBE, you still have to actually check the file (via the block index, then the block itself) to get a real answer — the bloom filter only ever saves work, it never provides a final answer.

How it works: k hash functions, m bits

The structure is a fixed-size bit array of m bits, all initially 0. To add a key, run it through k independent (well, independent-enough) hash functions, each producing a position in [0, m), and set all k of those bits:

To query a key, hash it the same way and check whether all k bits are already set:

If even one of the k bits is still 0, the key is definitely absent — it was never added, because adding always sets every one of its bits. If all k bits happen to be set, it's a MAYBE — either this key really was added, or k unrelated keys collectively happened to set exactly the bits this key would have set (a false positive), which becomes more likely as the bit array fills up.

Getting deterministic hash positions

Real bloom filters use fast non-cryptographic hashes (MurmurHash, xxHash) seeded differently per hash function, or derive multiple hash values cheaply from two independent hashes (h1 + i*h2 — the Kirsch–Mitzenmacher trick) rather than paying for k fully independent hash computations. For this exercise, determinism across runs and platforms matters more than raw speed, so a single MD5 digest is sliced into three 4-byte windows, each interpreted as a little-endian integer and reduced mod m:

One digest, three independent-enough windows — cheap, and perfectly reproducible for tests.

Sizing intuition: m, n, and k

The false-positive rate rises as more keys are added relative to the bit array's size — this is the whole tuning knob real bloom filters expose. For n keys, m bits, and k hash functions, the optimal number of hash functions (that minimizes false-positive rate for a given m/n ratio) is roughly k ≈ (m/n) * ln(2). Production LSM engines (RocksDB, Cassandra) typically target ~10 bits per key with ~7 hash functions for a false-positive rate around 1%. This exercise fixes m=64, k=3 for simplicity — small enough that with even a handful of keys added, you'll want to reason by hand about how quickly the bit array saturates and false positives start appearing.

Where this plugs into the LSM read path

Every SSTable, once written, gets its own bloom filter built from every key it contains (usually stored right in the file's footer, alongside the block index). A read path checks memtable, then for each candidate SSTable layer: consult its bloom filter first — NO means skip the file's block index and data entirely, MAYBE means fall through to the block-index lookup you built earlier in this chapter. In a database with many levels and files, this turns "check every file" into "check the bloom filter of every file, but only actually read the handful that might have it" — the single biggest practical win an LSM tree gets from adding one small in-memory structure per file.

Edge cases

• An empty filter (bits == 0) must answer NO to every query — no bits are set, so the "all k bits set" check fails trivially and correctly.
• COUNT should report the number of distinct set bits, not the number of ADD calls — two different keys can (and eventually will) set overlapping bits.
• As you add more keys than the filter was sized for, false positives become likely — MAYBE for a key you never added is not a bug, it's the expected behavior of an undersized filter; only a NO for a key you did add would indicate an actual defect.