Bloom filters

How many bits per key buy which false-positive rate, and what is a filter actually worth?

A Bloom filter answers "is key k in the set?" with either "definitely not" or "probably yes". It is a bit array of m bits (all zero at the start) and k hash functions. To insert a key, compute k hash values and set those k bits to 1. To test a key, compute the same k positions: if any bit is 0, the key was never inserted. If all are 1, the key was probably inserted, but those bits might have been set by other keys.

class Bloom:
    def __init__(self, m_bits, k):
        self.m, self.k = m_bits, k
        self.bits = bytearray((m_bits + 7) // 8)
    def _positions(self, key):
        # k positions from two hashes ("double hashing"); illustrative only
        h1, h2 = hash(("a", key)), hash(("b", key))
        return [(h1 + i * h2) % self.m for i in range(self.k)]
    def add(self, key):
        for p in self._positions(key):
            self.bits[p >> 3] |= 1 << (p & 7)
    def maybe_contains(self, key):
        return all(self.bits[p >> 3] & (1 << (p & 7)) for p in self._positions(key))

The derivation

Let there be m bits, n keys and k hash functions. After n insertions, a given bit is still zero with probability (1 − 1/m)^(kn) ≈ e^(−kn/m). So the false-positive rate is

RelationshipBloom filter false positives →

FPR = (1 - e^{- kn / m})^{k}

$m$: bits in the filter
$n$: keys inserted
$k$: hash functions per key

Data table

False-positive rate by bits per key (optimal k)
Bits per key m/n	False-positive rate
2	38.3%
2.27	33.5%
2.55	29.4%
2.83	25.7%
3.1	22.6%
3.38	19.8%
3.65	17.3%
3.92	15.2%
4.2	13.3%
4.47	11.6%
4.75	10.2%
5.03	8.94%
5.3	7.84%
5.58	6.87%
5.85	6.02%
6.13	5.27%
6.4	4.62%
6.67	4.05%
6.95	3.55%
7.22	3.11%
7.5	2.72%
7.78	2.39%
8.05	2.09%
8.32	1.83%
8.6	1.61%
8.88	1.41%
9.15	1.23%
9.43	1.08%
9.7	0.946%
9.97	0.829%
10.3	0.727%
10.5	0.637%
10.8	0.558%
11.1	0.489%
11.3	0.428%
11.6	0.375%
11.9	0.329%
12.2	0.288%
12.4	0.252%
12.7	0.221%
13	0.194%
13.3	0.17%
13.6	0.149%
13.8	0.13%
14.1	0.114%
14.4	0.1%
14.7	0.088%
14.9	0.077%
15.2	0.067%
15.5	0.059%
15.8	0.052%
16	0.045%
16.3	0.04%
16.6	0.035%
16.9	0.031%
17.1	0.027%
17.4	0.023%
17.7	0.021%
17.9	0.018%
18.2	0.016%
18.5	0.014%
18.8	0.012%
19.1	0.011%
19.3	0.009%
19.6	0.008%
19.9	0.007%
20.1	0.006%
20.4	0.005%
20.7	0.005%
21	0.004%
21.3	0.004%
21.5	0.003%
21.8	0.003%
22.1	0.002%
22.4	0.002%
22.6	0.002%
22.9	0.002%
23.2	0.001%
23.4	0.001%
23.7	0.001%
24	0.001%

Stated in 2 places →Trade-off: Exactness vs. approximation →

Minimizing this over k gives k* = (m/n) · ln 2. At that point exactly half the bits are set. Half-full is the maximum-entropy state of the array (each bit is as unpredictable as possible), so each bit carries the most information it can. At the optimum, FPR = 2^(−k) = 0.6185^(m/n).

Two numbers follow, and both are worth memorizing:

Ten bits per key buys roughly 1% false positives.
Every additional 4.8 bits per key divides the false-positive rate by ten. This is the same constant, ln 10 / ln²2, that appeared in the Lookup structures derivation of how to give different LSM levels different filter budgets. It is the same constant because it is the same optimization.

Bloom is 44% above the floor, and that 44% has a meaning

The information-theoretic floor for approximate membership at false-positive rate ε is n · log₂(1/ε) bits. At 1% that is 6.64 bits per key. Bloom spends 9.58. The ratio is exactly 1/ln 2 ≈ 1.44. What you buy with that extra 44% is incremental insertion: you can add keys one at a time, at any moment. The cuckoo, XOR and ribbon filters give some of that 44% back by giving up something. Stated this way, the whole filter family becomes one trade-off rather than three competing designs.

Its space does not depend on key size. Ten bits per key whether the key is an 8-byte integer or a 200-byte URL. That is the underrated property: it lets the filter live in a memory tier much faster than the data it guards.

The real cost in production is cache misses

The k hash probes are k random bit positions in a structure much larger than the CPU cache. That is up to seven cache misses per query, around 500 ns: a sizeable fraction of the NVMe read the filter was supposed to avoid.

Blocked (split-block) Bloom filters fix this. A first hash chooses one cache-line-sized block (64 bytes), and all k bits go inside that block. This turns k misses into one. It follows the Batch-size law: confine the work to one transfer unit. The price is a slightly worse false-positive rate, because keys spread unevenly across blocks (the balls-in-bins variance from earlier articles returns), so you need roughly 10 to 20% more bits for the same rate. Everyone takes this trade now. Parquet's filter specification and Impala's runtime filters use it.

What a filter is actually worth

A filter converts a random I/O into a memory probe with probability 1 − ε. Its value is therefore proportional to the latency ratio between the tier it guards and the tier it lives in:

Guarded tier	Ratio to RAM probe	Value of a filter
Spinning disk	~10⁵	free money
NVMe SSD	~10³	still pays
Another in-memory table	~1	pure overhead

Every guard structure (filter, zone map, cache, index) is worth the latency ratio across the boundary it guards. This is why the same structure is obviously correct in one tier and obviously wasteful one tier up.

Correct the folklore

"Bloom filters make lookups fast" is backwards. They make negative lookups fast, and they do nothing for positive lookups except add a probe. If your workload mostly hits, the filter is a cost. This is exactly why RocksDB has the option optimize_filters_for_hits. The filter question is really a question about your read distribution.

No deletion. You cannot clear a bit, because other keys may share it. Counting Bloom filters replace each bit with a 4-bit counter, at 4 times the space. Or you move to the next structure.