Bloom filter architecture, in depth: false positive math, two-hash indexing, cache-blocked layouts and sizing

The structure and its one-sided error

The structure is an array of m bits, all zero, and k hash functions that each map a key to a position in the array. To insert a key, set the k bits it maps to. To query a key, read those k bits: if any is zero, the key was never inserted, because inserting it would have set that bit, and bits are never cleared. If all are one, either the key was inserted or other keys happened to set every one of its bits. That second case is a false positive.

So the filter has no false negatives and a tunable false positive rate p. Callers must be designed around that asymmetry: a "no" lets you skip work, and a "yes" means you do the work you would have done anyway. A filter never replaces the authoritative store; it only lets you avoid consulting it for most keys that are not there. If your workload mostly queries keys that are present, a filter saves nothing, because those queries go to the store either way.

The structure and its one-sided error

The structure is an array of m bits, all zero, and k hash functions that each map a key to a position in the array. To insert a key, set the k bits it maps to. To query a key, read those k bits: if any is zero, the key was never inserted, because inserting it would have set that bit, and bits are never cleared. If all are one, either the key was inserted or other keys happened to set every one of its bits. That second case is a false positive.

So the filter has no false negatives and a tunable false positive rate p. Callers must be designed around that asymmetry: a "no" lets you skip work, and a "yes" means you do the work you would have done anyway. A filter never replaces the authoritative store; it only lets you avoid consulting it for most keys that are not there. If your workload mostly queries keys that are present, a filter saves nothing, because those queries go to the store either way.

Deriving the false positive rate

Assume the hash positions are uniform and independent. After inserting n keys with k positions each, a particular bit has been missed by all kn bit settings with probability (1 - 1/m)^kn, which is very close to e^-kn/m. The fraction of bits set, the fill, is therefore about 1 - e^-kn/m. A query for an absent key returns a false positive when all k of its positions land on set bits, so

p ≈ (1 - e^-kn/m)^k.

For fixed bits per key, m/n, there is a best k. Too few hash functions and each query checks too few bits; too many and the array fills up. Minimising p over k gives k = (m/n) ln 2, at which point the fill is exactly one half and p = (1/2)^k, about 0.6185^m/n. Rearranging gives the sizing rule: bits per key = -ln p / (ln 2)², about 1.44 log₂(1/p). Each extra 4.8 bits per key cuts the false positive rate by a factor of ten.

Those figures are for the classic layout with ideal hashing. They are also within about 44% of the theoretical minimum for any approximate membership structure, log₂(1/p) bits per key, which is why newer structures can beat Bloom filters on space but not by orders of magnitude.

Worked example: 20 million keys, then 40 million

A service keeps 20 million user ids that have ever been flagged and checks every request against the list; the authoritative list is in a database 2 ms away. You want at most 1% of clean requests to pay that 2 ms. Bits needed: 20,000,000 x 9.585 = 191.7 million bits, about 24 MB; k = 7.

Check the design point. kn/m = 7 x 20 / 191.7 = 0.730, so the fill is 1 - e^-0.730 = 0.518 and p = 0.518⁷ ≈ 1.0%. Now suppose the list grows to 30 million and nobody rebuilds the filter. kn/m becomes 1.096, the fill 0.666, and p = 0.666⁷ ≈ 5.8%. At 40 million the fill is 0.768 and p ≈ 15.7%. The filter still never misses a flagged user, so nothing visibly breaks; it just quietly sends fifteen times more clean traffic to the database. That is the characteristic Bloom filter failure, and it is why the fill ratio is the metric to watch: at the design point it is about 0.5, and anything well above that means the filter is overloaded.

You can also recover the number of keys from the fill alone. With X bits set, n ≈ -(m/k) ln(1 - X/m). For the filter above at fill 0.518 that gives 27.39 million x 0.730 = 20.0 million, which lets a monitoring job report the effective key count of a filter it did not build.

Two hashes are enough

Computing k independent hash functions per key is wasteful. Kirsch and Mitzenmacher showed in "Less Hashing, Same Performance" that two hash values are enough: positions g_i = h1 + i x h2 mod m for i from 0 to k-1 give the same asymptotic false positive rate as k independent functions. In practice, compute one 128-bit hash and split it. Two details matter: h2 must never be zero (force it odd), and the hash must be good, since a weak hash on structured keys such as sequential ids clusters positions and inflates p far above the formula.

import hashlib, math

class BloomFilter:
    def __init__(self, n_expected: int, p_target: float):
        bits_per_key = -math.log(p_target) / (math.log(2) ** 2)
        self.m = max(64, math.ceil(n_expected * bits_per_key))
        self.k = max(1, round(bits_per_key * math.log(2)))
        self.bits = bytearray((self.m + 7) // 8)

    def _positions(self, key: bytes):
        d = hashlib.blake2b(key, digest_size=16).digest()
        h1 = int.from_bytes(d[:8], "little")
        h2 = int.from_bytes(d[8:], "little") | 1          # never zero
        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def add(self, key: bytes) -> None:
        for pos in self._positions(key):
            self.bits[pos >> 3] |= 1 << (pos & 7)

    def might_contain(self, key: bytes) -> bool:
        return all(self.bits[pos >> 3] & (1 << (pos & 7)) for pos in self._positions(key))

    def fill(self) -> float:
        return sum(bin(b).count("1") for b in self.bits) / self.m

    def estimated_count(self) -> float:
        return -(self.m / self.k) * math.log(1 - self.fill())

bf = BloomFilter(n_expected=20_000_000, p_target=0.01)   # m = 191.7M bits, k = 7

To validate any implementation, insert n random keys, query a million different random keys, and compare the observed false positive rate with the formula. A result several times higher than predicted means the hash or the position arithmetic is wrong, and this test catches it in seconds.

Memory layout: blocked and split-block filters

In the classic layout the k positions are spread across the whole array, so a lookup in a filter larger than the CPU cache costs up to k cache misses, around 100 ns each from DRAM. For a hot path doing millions of lookups per second, those misses dominate. A blocked Bloom filter, analysed by Putze, Sanders and Singler, first uses one hash to choose a block the size of a cache line (512 bits) and then sets all k bits inside that block. A lookup costs one miss.

The price is accuracy. Keys do not spread evenly over blocks, so some blocks are more loaded than average, and their false positive rate dominates. For the same p you need more bits per key. Apache Parquet's split block Bloom filter is a concrete, well-documented example: each block is 256 bits made of eight 32-bit words, the upper 32 bits of a 64-bit xxHash pick the block, and the lower 32 bits are multiplied by eight fixed odd salt constants, one per word, to choose exactly one bit in each word. That makes k equal to 8 and lets a SIMD instruction check all eight words at once. Its specification lists about 10.5 bits per value for a 1% rate, 16.9 for 0.1% and 26.4 for 0.01%, compared with 9.6, 14.4 and 19.2 for the classic layout. The gap grows as the target tightens, so blocked layouts are best at moderate rates.

The same reasoning explains how storage engines use filters: one filter per file or per block, kept in memory and consulted before any disk read. How that works inside log-structured engines, including per-level sizing, is covered in Bloom filters in LSM engines, and the engine itself in LSM-tree, in depth.

Merging, estimating and persisting filters

Filters built with the same m, k and hash functions compose. The bitwise OR of two filters is exactly the filter you would get by inserting the union of their keys, so shards can build filters independently and a coordinator can merge them, the same mergeable-summary property that makes HyperLogLog useful. The bitwise AND approximates the intersection, but with a false positive rate at least as high as a filter built from the intersection directly, so use it as a hint only.

Persist a filter with a small header: format version, m, k, hash function id and seed, and the number of keys inserted. A reader that finds an unknown hash id or a changed m must refuse the filter rather than query it, because a filter read with the wrong parameters produces false negatives, which callers are built to assume never happen. That rule matters most during rolling upgrades, when old and new builds read each other's files.

When the set changes

A standard Bloom filter cannot delete: clearing a bit might remove it from another key and create a false negative. Three responses are common. Rebuild from the source of truth on a schedule or when the fill crosses a threshold; this is the simplest and suits sets that are rebuilt anyway, such as immutable files. Counting Bloom filters replace each bit with a small counter, typically 4 bits, incremented on insert and decremented on delete; that costs four times the memory, and deleting a key that was never inserted corrupts the filter. Scalable Bloom filters handle growth by adding a new, larger filter with a tighter false positive target when the current one fills, querying all of them; the total rate stays bounded but lookups slow down as layers accumulate.

If you need deletion and a fixed size, a different structure is usually better. Cuckoo filters store short fingerprints in a hash table, support deletion, and use less space than Bloom filters at low false positive rates. Ribbon and XOR filters, built once from a static set, get closer to the log₂(1/p) minimum and are used in some storage engines for exactly that reason. When the question is "how many times" rather than "whether", the related structure is the Count-Min sketch.

Failure modes

• Overload. More keys than planned; the false positive rate climbs while nothing errors. Monitor fill and alert well above 0.5.
• Weak or mismatched hashing. Structured keys with a poor hash, or a writer and reader using different hash seeds, give far higher rates or false negatives. Version the hash in the header.
• Bad normalisation. Inserting "User@Example.com" and querying "user@example.com" is a false negative caused by the caller. Canonicalise keys in one shared function.
• Filtering the wrong workload. If most queries are for present keys, the filter adds a lookup and saves nothing. Measure the negative query fraction first.
• Unsafe deletes. Clearing bits in a plain filter, or decrementing a counting filter for an absent key, creates false negatives. Rebuild instead.
• Untested rate. No one checked the observed false positive rate against the formula. Run the random-key test in CI.

What to do next

1. Measure what fraction of lookups are for absent keys; a filter only pays off when that fraction is large.
2. Pick p from the cost of a false positive, then compute bits per key and k from the formulas above.
3. Size for the key count you expect at the next rebuild, not today's, and add headroom.
4. Use one strong 128-bit hash split into two values, with the second forced odd.
5. Choose a blocked layout for hot in-memory paths at moderate p; the classic layout for tight p.
6. Persist m, k, hash id and seed with every filter and refuse mismatches.
7. Export fill ratio and observed false positive rate; rebuild when fill drifts well past one half.