Notesstorage🌱 seedling
Bloom Filter
Also: Bloom Filters · Probabilistic Membership Filter · Ribbon Filter
A compact bit array plus k hash functions that answers "is this key in the set?" with definitely not or maybe. It has false positives but never false negatives, so a "no" safely skips work.
Why it exists
An LSM-Tree read for an absent or old key would check every SSTable on disk. A small in-memory filter per file rules most of them out for free.
How it works
- Add: hash the key k ways and set those k bits to 1. Bits are never cleared.
- Query: check the same k bits. Any 0 means the key was never added. All 1s means it probably was, but other keys may have set those bits.
- With m bits and n keys, the false-positive rate is about (1 − e^(−kn/m))^k, minimised at k ≈ 0.69·m/n.
- About 10 bits per key gives ≈ 1% false positives; roughly every 5 more bits per key cuts the rate tenfold.
Trade-offs
| Gains | Costs |
|---|---|
| skips disk reads for keys that aren't there | memory per key, held for every file |
| tiny compared with the data it guards | false positives still cost a wasted read |
| no false negatives | no deletes (bits are shared); point lookups only |
In practice
- RocksDB builds one filter per SSTable; its Ribbon filter matches a Bloom filter's 1% rate in about 7 bits per key, trading 3–4× the CPU to build it for ~30% less memory.
- Cassandra exposes the target false-positive rate per table as
bloom_filter_fp_chance.
Pitfalls
- Filters don't help range scans: there's no single key to hash. Prefix filters help only when queries share a known prefix.
- Removing a key would mean clearing bits other keys share, so standard Bloom filters can't delete; rebuild them instead, as compaction does.
Connections
- Part of
- Storage
- In real systems
- RocksDBCassandraApache Parquet
Recall
These cards are also in your review deck, scheduled with spaced repetition.