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.

Recall

These cards are also in your review deck, scheduled with spaced repetition.