Sizing & Tuning Bloom Filters

A bloom filter is a tradeoff between memory and false-positive rate. The math is precise — you choose how much memory to spend per key and read off the resulting accuracy.

The Formulas

Given:

• n = number of distinct elements
• m = bit array size in bits
• k = number of hash functions

The expected false-positive rate is approximately:

p ≈ (1 - e^(-k*n/m))^k

To minimize p for fixed m and n:

k_optimal = (m / n) * ln(2)        ≈ 0.693 * (m/n)

To choose m for a target p:

m = -n * ln(p) / (ln(2))^2          ≈ 1.44 * n * log2(1/p)

A Practical Table

The cost grows logarithmically: each 10x reduction in FP rate costs ~5 more bits per key.

Real Workload Sizing

For an SSTable of 100M keys at 1% FP:

• Filter size: ~120 MB
• Inserts per key: 7 hashes (~1 µs)
• Queries per key: ~7 cache-line reads (mostly L1/L2 cache hits)

The filter lives in RAM (or block cache) and never touches disk during a query.

Per-Block vs Per-SSTable

Engines can put the bloom filter at SSTable granularity (one filter for the whole file) or at block granularity (one filter per 4 KiB data block).

• Per-SSTable: one filter check per SSTable. Higher hit rate. Cheaper to build.
• Per-block: many filters; "MAYBE" answers route to a specific block, reducing the cost of false positives.

RocksDB defaults to per-block (more precisely, per-prefix or per-full-key, depending on configuration).

Diminishing Returns

Beyond about 0.01% FP rate, the cost per key (memory + hash function count) grows faster than the savings (1% to 0.1% saves 10x more disk reads; 0.01% to 0.001% saves only ~9% more). Most production systems pick 1% as the sweet spot.

Caveats

• Filters are useless for range queries. Range scans always have to merge SSTables; you can't bloom-check a range.
• Filters are useless for scans of all keys with a prefix unless you use a prefix-specific filter (RocksDB has these).
• Filters help most when misses dominate the workload (cache lookups, primary-key indexes with non-existent keys).