Bloom Filters: Probabilistic Set Membership

A bloom filter is a tiny bit array that answers "is this key possibly in the set?" with two outcomes:

• maybe (could be present, or could be a false positive)
• definitely not (guaranteed absent)

It uses ~10 bits per element to achieve a ~1% false-positive rate, and the operations are O(k) where k is a small constant (typically 5-10) — vastly cheaper than the disk read it eliminates.

Why LSM Trees Adore Bloom Filters

A point lookup in an LSM tree may have to check many SSTables, each potentially requiring a disk read. For a missing key, that's wasted I/O. A bloom filter sits in front of each SSTable:

With 1% false positives, 99% of negative lookups avoid disk entirely. For a workload of mostly-hits-or-misses (a cache, a primary key index), this is the single biggest perf win in the LSM toolbox.

How It Works

The filter is a bit array of m bits, initially zero. To insert key k, hash it with k independent hash functions h1, ..., hk and set bits h1(k) % m, h2(k) % m, ..., hk(k) % m.

To query: hash with the same k functions, check that ALL of those bits are 1. If any is 0, the key was never inserted (definitely not present). If all are 1, the key may have been inserted (or those bits may have been set by inserting other keys).

Sizing

For n elements with target false-positive rate p:

m = -n * ln(p) / (ln 2)^2     (bits)
k = (m/n) * ln 2              (hash functions)

For p = 0.01 (1%): m/n ≈ 9.6 bits per key, k ≈ 7. For 1M keys, that's 1.2 MiB for the filter — trivial.

No Deletes

Bloom filters do not support delete. Clearing the bits would create false negatives (other keys that legitimately share those bits would disappear). Variants like counting bloom filters allow deletes at higher memory cost; LSM engines just rebuild the filter on each new SSTable, which is rewritten by compaction anyway.

Double Hashing Trick

Real implementations don't compute 7 independent hashes per key — that's slow. The standard trick (Kirsch & Mitzenmacher 2008): use 2 hashes h1, h2 and synthesize h_i = h1 + i*h2 mod m. Statistically indistinguishable from 7 independent hashes; ~3.5x faster.

RocksDB's Ribbon Filter

For very large datasets RocksDB now offers the ribbon filter — similar false-positive rate at 30% fewer bits per key. The implementation is more complex (it's based on Gaussian elimination over GF(2)) but the API is identical from the engine's perspective.