Giving Small Runs Better Bloom Filters

A Bloom filterA compact membership check that can say “definitely absent” or “possibly present.” saves work by giving a cheap, definite answer when a key is absent. In a storage engine with several sorted runs, that question repeats: can this file contain the key? The useful memory allocation depends on the whole lookup path.

Google’s Bigtable paper describes per-SSTable Bloom filters that reduce unnecessary disk access. Monkey, by Dayan, Athanassoulis, and Idreos, asks how a fixed filter budget should be divided across differently sized runs. Its central result motivates this experiment: minimizing the sum of false-positive rates can require unequal bits per key.

The question a lookup actually pays for

Suppose an absent key must check four filters. Let p_i be filter i’s false-positive rate. The expected number of unnecessary table probes is p₁ + p₂ + p₃ + p₄. This follows from linearity of expectation; the filters do not need independent outcomes for that sum to hold.

Give every run ten bits per key and each filter has roughly the same error rate. But a small run can buy that accuracy with far fewer total bits. Moving some memory from the largest run to the smallest ones can reduce several error rates while only slightly increasing the largest run’s rate.

Turning the idea into an allocation

For n_i keys and b_i bits per key, the usual continuous approximation at the optimal hash count is p_i ≈ exp(−a b_i), with a = (ln 2)². The objective and memory constraint are:

Equating the marginal benefit per bit gives a p_i / n_i = λ for every filtered run. Thus p_i is proportional to n_i, and the solution is b_i = max(0, ln[a/(λn_i)]/a). The script searches for λ and then rounds allocations to whole bytes while preserving the exact total budget.

With run sizes 2,000, 8,000, 32,000, and 128,000 keys, the allocation becomes approximately 17.74, 14.85, 11.97, and 9.08 bits per key. The largest run still gets the most total memory, just less memory per key.

What the executable test found

The code builds actual byte-array Bloom filters using deterministic SHAKE-256 hash output. Five seeds each generate 50,000 absent queries, with the same keys and seeds used for both policies. Inserted and absent keys have separate prefixes. Every absent query tests every filter; range pruning, compaction, block caching, and storage I/O are outside this experiment.

Across 250,000 absent lookups per policy, the optimized allocation produced 47.21% fewer false-positive probes. The continuous approximation predicts 32.77 versus 16.90 per 1,000. Byte rounding, integer hash counts, finite filters, and sample variation separate the prediction from the observed counts.

All 1.7 million inserted-key checks passed without a false negative. The test also checks 21 allocation cases, including low budgets where some filters receive no memory, and verifies that equal-sized runs recover equal allocation. The download includes per-filter counts, per-seed totals, probe-count histograms, and an analytical budget sweep.

Where the result stops being automatic

The optimized policy here minimizes equally costly absent-key probes. If a run is rarely reached or usually cached, its false positives cost less. A more useful objective is then Σ w_ip_i, where w_i combines reach probability and probe cost. The same derivation gives p_i proportional to n_i/w_i when the solution is interior.

Real filter design also pays for CPU and cache behavior. RocksDB’s filter documentation describes cache-local probing and the tradeoff between filter memory and avoided read work. The next meaningful system experiment would measure how the allocation interacts with cache hit rate and the fraction of negative lookups. This experiment establishes the memory-versus-probe mechanism, without turning probe counts into an unsupported latency estimate.