Concrete scenario
An LSM engine wants to avoid disk reads for keys absent from each immutable table.
Mechanics
A Bloom filter sets k hash-selected bits in an m-bit array. If any queried bit is unset, a correctly constructed and current append-only filter proves the key was not inserted; if all are set, the answer may be a false positive. Size m and k from expected items and target false-positive rate.
Failure mode
Deleting bits from a standard filter can create false negatives. An undersized or stale filter raises error rates, so mutable sets need rebuilds, counting filters, or another design.
Trade-off
Bloom filters save memory and negative lookup I/O but cannot return values or prove presence. Lower false-positive rates consume more memory and hash work.
Worked example: sizing a filter
For n items and a target false-positive rate p:
- Bits needed:
m = -n x ln(p) / (ln 2)^2, about9.6 x nbits for p = 1%. - Best number of hash functions:
k = (m / n) x ln 2, about 7 for p = 1%.
| Target FP rate | Bits per item | Hash functions k | Memory for 100M items |
|---|---|---|---|
| 10% | 4.8 | 3 | about 60 MB |
| 1% | 9.6 | 7 | about 120 MB |
| 0.1% | 14.4 | 10 | about 180 MB |
| 0.01% | 19.2 | 13 | about 240 MB |
Each 10x reduction in false positives costs only about 4.8 more bits per item. Compare that with storing the 100M keys themselves (for example 16-byte IDs, about 1.6 GB).
Worked example: LSM read path
A RocksDB/Cassandra key lookup may need to check 10 SSTables. Without filters, a miss costs up to 10 disk reads. With a 1% filter per SSTable, the expected wasted reads for a missing key are 10 x 0.01 = 0.1, a 100x reduction. RocksDB's default configuration uses about 10 bits per key, and Cassandra's bloom_filter_fp_chance defaults to 0.01 (0.1 for LeveledCompaction).
Variants
| Variant | Adds | Cost |
|---|---|---|
| Counting Bloom filter | Deletes (4-bit counters) | About 4x memory |
| Cuckoo filter | Deletes, better space below about 3% FP | Inserts can fail when nearly full |
| Scalable Bloom filter | Growth without knowing n up front | Chain of filters, slightly slower lookups |
| Blocked Bloom filter | One cache line per lookup (fast) | Slightly higher FP rate at the same size |
| Xor / ribbon filters | About 20-30% less space, static sets | Must be built all at once |
Real uses: LSM engines (RocksDB, Cassandra, HBase, LevelDB), Chrome's old Safe Browsing malicious-URL prefilter, Akamai's "one-hit-wonder" cache admission (only cache on the second request), and Medium's "already recommended" checks.