TL;DR — A Bloom filter is a probabilistic bitset that sits in front of every SSTable in an LSM-tree and answers “definitely not here” with no I/O. Used well, it cuts read amplification by an order of magnitude; used poorly, it leaks memory and false-positive rate into your hot path. Tuning comes down to bits-per-key, hash function choice, and whether you use vanilla, blocked, or ribbon filters.

If you have ever stared at a RocksDB get() taking 8 ms and wondered where the time went, the answer usually involves at least one disk seek — and at least one Bloom filter saving you from another. Bloom filters are the unsung heroes of log-structured merge-tree (LSM-tree) storage engines, and they are one of the few components where a tiny tweak in configuration can swing tail latency by 3–5x.

This post walks through how they work, why LSM-trees in particular lean on them so hard, the math behind the false-positive rate, and the tuning levers that matter when you are running RocksDB, Cassandra, or HBase in production.

Why LSM-Tree Reads Need a Filter

An LSM-tree writes new keys into an in-memory memtable and flushes it to disk as an immutable, sorted file called an SSTable (Sorted String Table). Over time, those SSTables are merged in the background by a compaction process. By the time a key has been written a few times, it can live in several SSTables at once.

A point read like get("user_42") therefore has a problem: where is user_42? It could be in the memtable, in any of a dozen recent flushed SSTables, or in a deep level-4 file. Without help, you have to check every one of them, which is exactly the kind of read amplification LSM-trees were supposed to avoid.

The Bloom filter is that help. Each SSTable carries a small probabilistic structure that can answer “this key is definitely not in this file” with zero disk I/O. The answer is sometimes wrong on the positive side — it might say “maybe here” when the key actually isn’t — but it is never wrong on the negative side. That one-sided guarantee is what makes it so useful.

The 60-Second Bloom Filter Refresher

A Bloom filter is a bit array of size m and k independent hash functions. To insert a key, you hash it k times and set those k bits to 1. To query a key, you hash it k times and check whether all k bits are 1. If any is 0, the key is definitely not present. If all are 1, the key is probably present.

The probability of a false positive — when all k bits happen to be 1 for a key that was never inserted — is:

$$ p \approx \left(1 - e^{-kn/m}\right)^k $$

For a given bits-per-key ratio b = m/n, the optimal k that minimizes p is k = (b \cdot \ln 2). Plugging that in gives the well-known rule of thumb:

bits per key (b)optimal kfalse-positive rate (p)
64~5.6%
85~2.3%
107~0.82%
128~0.31%
1611~0.02%
2014~0.0001%

A typical RocksDB default of 10 bits per key gives you roughly a 1% false-positive rate. For a single SSTable that sounds fine. For a read that touches 10 SSTables, the probability that at least one of them false-positives is 1 - (1 - 0.01)^10 ≈ 9.6%. That is the number that actually matters in production, and it is the reason careful tuning compounds.

Where the Filter Lives in the Read Path

When a get arrives at a RocksDB instance, the read path looks roughly like this:

  1. Check the active memtable, then any immutable memtables. Exact match. If found, return.
  2. For each SSTable that might contain the key, check its Bloom filter. This is an in-memory operation, but it still costs CPU and cache lines.
  3. If the filter says “maybe”, open the SSTable. Binary-search or hash-lookup the index block to find the data block.
  4. Read the data block from disk (or page cache), parse it, return the value.

The Bloom filter sits at step 2. Its job is to make step 3 rare. As described in the RocksDB wiki, the filter block is loaded alongside the index and metaindex blocks when an SSTable is opened, and stays resident in the block cache as long as the file is open. A well-tuned filter block is typically 1–5 MB even for a multi-GB SSTable — small enough to live in RAM comfortably, large enough to keep the false-positive rate under control.

A common rookie mistake is to assume “Bloom filter” is a single global structure per database. It is not. Every SSTable has its own filter, sized for the keys in that file.

Patterns in Production

RocksDB and the Block-Based Table

RocksDB uses block-based tables with a configurable filter_policy. The most common choices are:

  • rocksdb::NewBloomFilterPolicy(10, false) — 10 bits per key, the legacy hash function. Solid default.
  • rocksdb::NewBloomFilterPolicy(10, true) — same size, but uses a faster, locality-friendly hash that the RocksDB team added for better cache behavior.
  • Ribbon filters (since RocksDB 7.0) — a newer, more space-efficient alternative we’ll cover below.

In ColumnFamilyOptions, the levers you have are:

options.setBloomLocality(1);      // group filter bits for better cache locality
options.optimize_filters_for_hits = true; // assume many reads are hits; skip last level

The second option is worth highlighting: if your workload is read-heavy with high hit rates (a typical cache layer), you can ask RocksDB to not build filters for the bottommost level, because those files are usually not on the read path. This can cut filter memory by 30–50% with negligible extra I/O.

Apache Cassandra

Cassandra uses a Bloom filter per SSTable and exposes the tuning knob as bloom_filter_fp_chance on the table. The default of 0.01 corresponds to roughly 10 bits per key. The trade-off is explicit in the Cassandra documentation:

A higher bloom_filter_fp_chance (e.g., 0.1) trades index size for a small chance of unnecessary disk reads; a lower value (e.g., 0.001) trades disk I/O for index size.

In practice, Cassandra deployments with SSD-backed nodes often run with bloom_filter_fp_chance = 0.01 or even 0.1, because the cost of an extra disk read is much lower than the cost of holding a 50 GB filter in RAM. The reverse is true for spinning-disk or memory-constrained clusters.

Apache HBase and Phoenix

HBase’s StoreFile uses a Bloom filter of its own, configured via io.hfile.bloom.enabled and io.hfile.bloom.error.rate in hbase-site.xml. The interesting wrinkle is that HBase often co-locates the filter with the file’s block index in the combined “block index” structure, which is what gets cached in the LruBlockCache. For Phoenix-driven workloads, the SQL planner’s RANGE SCAN decisions interact with the filter in subtle ways — a Bloom filter helps get and scan with predicates, but it does nothing for a true range scan that has to walk the file anyway.

The Math Behind Tuning

Let’s work through a concrete example. Suppose you have a RocksDB instance with:

  • 1000 SSTables across all levels
  • Each SSTable has ~100 million keys (let’s pretend 1 KB values, so ~100 GB per file)
  • Average of 5 SSTables touched per get at steady state
  • Target tail latency: p99 reads < 5 ms
  • Bloom filter size budget: 20 GB total (so ~20 MB per SSTable)

With 20 MB = 160 Mbit per file and 100 M keys, that’s b = 1.6 bits per key. That’s far below the typical 10 — so a 1.6 bits-per-key filter has a false-positive rate of roughly 36%. Across 5 SSTables, the chance of at least one false positive is 1 - 0.64^5 ≈ 88%. That’s catastrophic: almost every read will fall through to disk.

Now flip the budget: 200 MB per SSTable at 10 bpk. FPR per file is 0.82%. Across 5 files, the chance of at least one false positive is 1 - 0.9918^5 ≈ 4%. Much better. Tail latency drops because 96% of reads short-circuit before any disk I/O on the SSTable path.

The lesson is that the aggregate false-positive rate — across all SSTables the read touches — is what drives I/O, not the per-file rate. This is why LSM-tree depth matters as much as filter size.

Choosing the Right Bits-per-Key

A useful heuristic that holds up in most production environments:

  • 8 bpk if you have many LSM levels, generous RAM, and reads are very latency-sensitive.
  • 10 bpk for balanced workloads (RocksDB’s default, Cassandra’s default).
  • 12–14 bpk for small, hot datasets where filter memory is cheap.
  • 6 bpk or lower is almost never worth it — false positives swamp any I/O savings.

A real-world anecdote: a team running an HBase cluster with 200 TB of data was spending 12% of heap on Bloom filters at 8 bpk. Dropping to 10 bpk and using locality hints dropped the index-heap ratio to 9% and improved p99 reads by 18%, because the smaller working set fit in L3 cache.

Beyond Vanilla: Blocked, Partitioned, and Ribbon Filters

The original Bloom filter has a few practical weaknesses that matter at LSM scale:

  1. Cache unfriendliness. The bits for any one key are scattered across the array, so a query may touch 8–16 cache lines.
  2. No incremental resizing. You commit to m and k at construction time.
  3. Serialization cost. For an LSM with millions of small files, every byte of filter metadata is a byte of disk and a byte of block cache.

Three modern alternatives address these.

Blocked Bloom Filters

A blocked Bloom filter hashes keys to a single block (typically 512 bytes) and uses k hash functions within that block. The query touches exactly one cache line in the common case, which is a huge win on modern CPUs. RocksDB’s BloomFilterPolicy with block_based_table_factory and use_block_based_builder = true is exactly this design, as covered in the RocksDB block-based table docs.

Partitioned (FastLocality) Filters

RocksDB’s NewBloomFilterPolicy(10, true) and the higher-level partitioned_filters option go further: the filter is split into small partitions, and a top-level index maps the query’s hash to the relevant partition. This gives both better cache locality (small, predictable reads) and partial loading (you only need to load the partition that matters). The trade-off is a small amount of extra metadata and a small CPU cost to compute the partition index.

Ribbon Filters

Ribbon filters (introduced by Bender, Farach-Colton, et al. in 2020) are the newest entry, and RocksDB adopted them as an option in version 7.0 under ExperimentalRibbonFilterPolicy. They achieve the same false-positive rate as a Bloom filter at roughly the same bits-per-key, but with much better construction speed — often 5–10x faster than the equivalent Bloom filter build, and similar query speed. The reason is that a ribbon uses a sparse encoding based on a Peeling Decoder, which can be solved greedily during construction.

For workloads with heavy compaction (lots of new SSTables), ribbon filters can noticeably reduce the CPU cost of compaction without inflating the false-positive rate. The RocksDB team has been gradually enabling ribbons by default since the 8.x releases.

The Failure Modes

False Positives That Aren’t

A common debugging story: a get returns “not found” when the key is definitely there. Engineers assume the Bloom filter is broken. It isn’t — the filter returned “maybe”, the SSTable was opened, the key was found, and the value was returned. The “not found” comes from somewhere else, usually a tombstone on a higher level or a more recent write. The filter is doing its job.

Stale Filters After Bulk Loads

Some bulk-load paths (Cassandra’s sstableloader, RocksDB’s ingest_external_file) can leave filters out of date or absent. If a loaded SSTable has no filter, every read has to consult the file’s index, which is the equivalent of a 100% false-positive rate. Always check filter presence after bulk loads; the symptom is a sudden, dramatic increase in read I/O.

Compaction Storms and Memory Spikes

Every new SSTable gets a new filter. During heavy compaction, a temporary surge of small SSTables can balloon filter memory until compaction catches up. If your block cache is sized just barely above steady state, you can evict working-set data and tank the hit rate. The mitigation is to bound the LSM fan-out by tuning level0_file_num_compaction_trigger, max_bytes_for_level_base, and (in RocksDB) max_subcompactions.

Tuning Playbook for Production

If you are tuning a real system, here is the order I would walk through it.

  1. Measure first. Use RocksDB’s perf_context (specifically block_cache_hit_count, block_read_count, and bloom_sst_hit_count) or Cassandra’s tombstone_scanned/bloom_filter_false_positive metrics to see the current state. Don’t tune blind.
  2. Pick a target. “I want p99 reads under 5 ms” is better than “Bloom filter FPR 0.1%.” Work backward from the SLO.
  3. Set bits-per-key deliberately. Start at 10. Lower it if memory is constrained and you can afford the I/O. Raise it only if filter memory is cheap and p99 is missing SLO.
  4. Enable locality hints. bloom_locality = 1 in RocksDB, default bloom_filter_fp_chance = 0.01 in Cassandra, default HBase settings for typical workloads.
  5. Consider ribbons if you are on RocksDB 8.x and compaction CPU is showing up in profiles.
  6. Use optimize_filters_for_hits if your workload is read-heavy and you can guarantee low miss rate.
  7. Re-test after every change. Bloom filter tuning interacts with block cache size, compaction strategy, and the workload’s key distribution. A “win” in microbenchmarks can be a wash in production.

Key Takeaways

  • A Bloom filter is a per-SSTable probabilistic bitset that says “definitely not here” with no disk I/O. It is the single most cost-effective read-amplification reducer in an LSM-tree.
  • The false-positive rate that matters is the aggregate across all SSTables a read touches, not the per-file rate. With 10 SSTables touched and 1% per-file FPR, ~10% of reads will hit at least one false positive.
  • The right bits-per-key depends on the trade-off between RAM (filter memory) and disk I/O. 10 bpk is a solid default; 6 bpk is almost always too aggressive; 14+ bpk is for small, hot datasets.
  • Modern variants (blocked, partitioned, ribbon) give better cache behavior, faster construction, and similar false-positive rates. Ribbon filters are the new winner for compaction-heavy workloads.
  • Always instrument before tuning. optimize_filters_for_hits, bloom_locality, and the bits-per-key knob are the three levers that move the needle most.

Further Reading