Skip to content

Bloom filters in modern LSMs#

2024-01-20

Bloom filters are the boring plumbing that makes LSM point-lookups tolerable. Some notes on how they're actually implemented in RocksDB and Cassandra.

Full filter vs block filter#

Older RocksDB versions built one bloom filter per SST block (~4 KB). Modern RocksDB defaults to full filters — one filter per SST file — which uses less memory total and gives a lower false-positive rate for the same memory budget.

Full filter cost: for n keys and k bits per key, memory is n*k bits and false-positive rate is roughly (1 - e^(-1))^k ≈ 0.6185^k. RocksDB defaults to 10 bits per key, giving ~1% FPR.

Ribbon filters#

RocksDB 6.15+ supports ribbon filters, which are ~30% smaller than bloom filters at the same FPR, at the cost of slightly slower construction and queries. For large LSMs where the filter memory is the dominant cost, this is a significant win.

Enable via NewRibbonFilterPolicy(bits_per_key).

Cassandra's approach#

Cassandra uses a per-SSTable bloom filter, stored in -Filter.db alongside the data. Default is 0.01 FPR (~10 bits per key). You can dial this down per-table via bloom_filter_fp_chance.

For very large partitions, the filter can actually miss (per-partition) but the SSTable's index summary + partition index will still find the key. The filter is an optimization, not a correctness thing.

Practical numbers#

For a workload with 200-byte keys and a 1 TB LSM at ~10 bits/key:

Filter memory: 1 TB / 200B * 10 bits = 6.25 GB
False positive rate: ~1%
Actual disk I/O for point lookups: reduced ~99% vs no filter

The RAM cost is real but usually way cheaper than the I/O it saves.

Reference#

  • Bloom, Space/Time Trade-offs in Hash Coding with Allowable Errors (1970). The original.
  • Dillinger & Walzer, Ribbon filter: practically smaller than Bloom and Xor (2021).