TL;DR — In an LSM-tree, point reads must probe every sorted run from newest to oldest until a key is found. A bloom filter placed in front of each SSTable rejects 99%+ of non-existent keys with a single cache-resident probe, collapsing read amplification from “touches every level” to “touches the level that actually owns the key.” Sizing is governed by the equation m = -n·ln(p) / (ln 2)², and most production engines default to ~10 bits per key at a 1% false positive rate.

Why LSM-Tree Reads Need Help

Log-Structured Merge-trees (LSMs) optimize for write throughput by absorbing incoming keys into an in-memory memtable and flushing immutable sorted runs (SSTables) to disk. The trade-off is well documented: writes are sequential and cheap, but a point read for a key that does not exist must, in the worst case, check every level from L0 to the bottom. Each check usually means a binary search inside an SSTable, plus at least one block cache miss when the block has been evicted.

For a write-heavy workload this is fine. For a read-heavy or mixed workload — think user-facing key-value stores, time-series dedup, or session caches — the cost compounds. A modern LSM like RocksDB or Cassandra typically has 4–7 levels, and at steady state each level holds roughly 10× more data than the one above it. The probability that a missing key lives in only the deepest level is high, but the I/O cost of proving that is paid on every miss.

Bloom filters are the standard remedy. They live in the block cache next to each SSTable’s index, cost a handful of bits per key, and answer the question “is this key definitely not in this file?” in nanoseconds. When the answer is no, the engine skips the file entirely.

How a Bloom Filter Works

A bloom filter is a fixed-size bit array with m bits and k independent hash functions. To add a key, you hash it k times and set the corresponding bits. To query, you hash the same way and check that all k bits are set.

Two properties matter:

  • No false negatives. If the key was inserted, every one of its k bits is set, and the query will report “maybe present.”
  • Bounded false positives. A query for a key that was never inserted can still find all k bits set by coincidence. The probability of that happening is the filter’s false positive rate, p.

The classical sizing relationship, derived from the birthday-style occupancy of the bit array, is:

m = -n · ln(p) / (ln 2)²
k = (m / n) · ln 2 ≈ 0.6931 · (m / n)

where n is the number of inserted keys. For a 1% false positive rate, this works out to roughly 9.6 bits per key and 7 hash functions. A 10% rate cuts the cost to ~4.8 bits/key and ~3 hashes — fine for warm caches, painful for the last level of a deep LSM where every miss costs a disk read.

The filter is not a probabilistic data structure in the “might be wrong about presence” sense that some introductory material implies. It is exact about the negative answer and probabilistic about the positive. That asymmetry is what makes it useful: a false positive just costs one extra SSTable probe, while a true negative saves an entire binary search plus a block fetch.

Where the Filter Sits in the LSM-Tree

Modern engines do not put one giant bloom filter in front of the whole database. They put a block-level filter in front of every data block, and an SSTable-level summary that lets the read path avoid even loading block filters for files that cannot contain the key.

In RocksDB, this shows up as two cooperating structures stored alongside each table file:

  • Filter block — a sequence of per-data-block bloom filters, one for every 4 KB (configurable) of user data. The filter block itself is read once and cached in the block cache.
  • Index block — the binary-searchable structure that maps a key range to a data block number and a sequence number for MVCC.

The read path looks like this:

  1. Probe the in-memory memtable and any immutable memtables.
  2. For L0 (where SSTables can overlap), probe each file’s bloom filter until you find a hit, then check the file.
  3. For L1+, use the level’s index to find the single SSTable whose key range contains the key, then probe that file’s filter. If the filter says no, skip the file.
  4. Repeat down the levels until a hit is found or the bottom is reached.

This is the design described in the original RocksDB bloom filter documentation and elaborated in the LevelDB design notes. The crucial detail is that for non-overlapping levels, you never probe filters for files that cannot contain the key — the index alone narrows the candidate to one file per level, and the bloom filter only has to make a yes/no decision for that one file.

Patterns in Production: RocksDB, Cassandra, and ScyllaDB

RocksDB and its derivatives

RocksDB exposes two parameters that map directly to the math above: bloom_filter_bits_per_key (the m/n ratio) and bloom_filter_whole_key_filtering (whether to filter on the full key, or only the prefix). It also supports a partitioned filter index for very large files, which decouples the filter block from the index block so cold filters do not evict hot ones from cache.

A representative production configuration for a write-heavy cache that still serves point reads at high QPS looks like:

# rocksdb options
write_buffer_size: 128MB
max_bytes_for_level_base: 512MB
max_bytes_for_level_multiplier: 10
target_file_size_base: 64MB
max_background_jobs: 8

# bloom filter tuning
table_options:
  filter_policy: bloom_filter:10:false
  # 10 bits/key ≈ 1% FPR, whole-key filtering off → prefix filtering
  block_size: 4096
  enable_index_compression: true
  partition_filters: true
  use_delta_encoding_for_keys: false

The bloom_filter:10:false syntax means 10 bits per key with prefix filtering. Prefix filtering is critical for workloads that do Get(key) followed by Seek(prefix) — the filter can answer both with the same structure, which is how TiKV’s transaction layer keeps its point-read cost flat even with multi-version storage.

Cassandra and ScyllaDB

Cassandra stores a bloom filter per SSTable, loaded into memory on file open. The relevant parameters are bloom_filter_fp_chance in the table definition. ScyllaDB’s technical whitepaper on its LSM-based storage engine describes how it keeps the filter for the largest files resident regardless of the cache pressure from data blocks — recognizing that evicting the filter forces every miss to do a disk seek.

The “ribbon filter” twist

A naive bloom filter at 10 bits/key is cheap, but it is not the most space-efficient filter available. Both RocksDB and TiKV now ship with ribbon filters, a learning-augmented structure that achieves the same false positive rate at roughly 30% less space. The Ribbon filter paper from Google explains how it uses signal-processing-style arithmetic on a smaller “ribbon” matrix. In practice, swapping bloom for ribbon at the last level is one of the most cost-effective LSM tuning moves you can make because that level holds ~90% of the data on disk.

The Read Path, End to End

To make the savings concrete, consider a 7-level LSM with the standard 10× level multiplier and 1% bloom filter FPR per SSTable. A Get() for a missing key:

LevelFiles probed by indexFilter hit probDisk seeks if filter says no
Memtable1n/a0
L040.01 each0 (filter blocks in cache)
L110.010
L210.010
L310.010
L410.010
L510.010
L610.010 (cold-cache worst case)

Without filters, the same lookup at L6 would have to binary search a ~100 GB SSTable, which means multiple disk reads. With a filter, it is one in-memory probe.

The cumulative false positive probability — the chance that every level’s filter wrongly says “maybe” — is 1 - (1 - 0.01)^7 ≈ 0.0679, or about 6.8%. The engine then pays a real I/O for those 6.8% of misses, but still skips the other 93.2%. That is the whole point.

Sizing the Filter for Your Workload

The math, with an example

Suppose you have 100 million keys in a target file size of 64 MB, and you want a 1% FPR:

m = -1e8 · ln(0.01) / (ln 2)²
  = -1e8 · (-4.6052) / 0.4805
  = 9.585e8 bits
  ≈ 114 MB

So the bloom filter for one 64 MB data file is ~114 MB, a 1.78× overhead. At 10% FPR, it drops to ~57 MB. This is why filter FPR is the single most impactful knob in LSM read tuning.

Choosing a false positive rate

The “right” FPR depends on the cost asymmetry of a false positive:

  • Cache workload: the SSTable is in the page cache, the false positive costs a binary search of an in-memory block. 5–10% FPR is fine.
  • Cold tier, hot lookups: the SSTable is on NVMe, the false positive costs a multi-millisecond read. 0.5–1% FPR is worth the RAM.
  • Object store tier (S3, GCS): the false positive costs a GET and a multi-second download. Sub-0.1% is justifiable, and you should consider switching to a more space-efficient filter than bloom.

RocksDB supports different FPRs per level via optimize_filters_for_hits, which is the recommended setting when you know most reads hit the upper levels and want to spend filter bits on the lower ones.

Per-level filter sizing in RocksDB

A useful pattern in options is:

rocksdb::ColumnFamilyOptions cf;
cf.optimize_filters_for_hits = true;  // assume L0/L1 mostly hit, optimize L6
cf.table_factory.reset(NewBlockBasedTableFactory(
    NewBloomFilterPolicy(10 /* bits/key */)));

Setting optimize_filters_for_hits = true tells RocksDB to skip building bloom filters for the first two levels when there is no point — every L0 file has to be probed anyway, and L1 is small enough that misses are rare. That RAM goes to L6 filters instead, where it pays for itself many times over.

Failure Modes and Common Pitfalls

Forgetting to charge filter memory against block_cache

In RocksDB, the block cache holds both data blocks and filter blocks, but the filter block sizes are charged differently depending on cache_index_and_filter_blocks. If you set that flag to true (the default for high-read workloads), a 100 GB database with 1% FPR filters will burn ~5–10 GB of cache just for filters. On a memory-constrained instance, this causes data block thrash and can quietly undo all the filter’s benefits.

The fix is either to size block_cache generously (RocksDB’s rule of thumb is at least 1/3 of the database size) or set cache_index_and_filter_blocks = false and let the OS page cache handle them, which is fine on Linux since filter blocks are accessed randomly and benefit from kernel readahead.

Prefix vs. whole-key filtering

Setting whole_key_filtering = true enables a small optimization: RocksDB uses the full key for the filter, which catches Get() lookups but cannot answer Seek() for a prefix range. Most production workloads that mix point and range reads should leave whole-key filtering off and rely on prefix filtering — the FPR is slightly higher for Get(), but you can answer both query types.

Hash function quality

The default hash in RocksDB is a variant of MurmurHash, which is fast and well-distributed. If you roll your own bloom filter, do not use std::hash — its distribution on integer keys is catastrophic, and the effective FPR can be 5–10× the theoretical value. The Cuckoo filter paper by Fan et al. and the original Bloom filter paper both emphasize that hash quality dominates every other design choice.

Filter rebuild cost on compaction

Every compaction produces new SSTables and new filters. If you set FPR to 0.1% for the last level, the compactor spends a non-trivial amount of CPU hashing every key an extra ~13 times. Profile before pushing below 0.5% on the largest level; below that, the compactor can become CPU-bound.

Key Takeaways

  • A bloom filter is an exact test for “definitely not present” and a probabilistic test for “maybe present.” That asymmetry is what makes it useful for LSM read paths.
  • Sizing follows m = -n·ln(p) / (ln 2)². At 1% FPR, expect ~9.6 bits per key. At 10%, ~4.8 bits.
  • In production, set the false positive rate per level. Use optimize_filters_for_hits = true and let the engine spend filter bits where misses are most expensive — usually L5+.
  • Always account for filter memory in block_cache sizing. A 100 GB database at 1% FPR is ~5 GB of filter blocks competing with data blocks.
  • Consider ribbon filters as a drop-in upgrade if you are already on RocksDB 7.4+ or TiKV 5+: same FPR, ~30% less space, same lookup cost.
  • Whole-key vs. prefix filtering is a workload decision. If you do range scans, keep prefix filtering on.

Further Reading