A Filter That Lies
A Bloom filter's false-positive rate has a famous closed-form formula. The formula is right about filters in general and wrong about yours.
What it is
4096 bits, 512 keys, 6 hash functions each. Insert everything, then ask about 40,000 keys that were definitely never inserted and count how many come back “yes”.
Then throw the filter away, build another from a fresh set of keys, and do it again. Every dot on the right is one complete filter. The blue line is what the textbook formula predicts. Tap to skip to the next one.
How it works
A Bloom filter is m bits and k hashes. Adding a key sets k bits, asking about a key checks those k bits and says yes only if all of them are set. “No” is always the truth. “Yes” might be a coincidence, k bits that happen to have been set by other keys.
The standard formula for how often that coincidence happens is (1 - e^(-kn/m))^k, and
there’s a matching one for the k that minimises it, (m/n) ln 2. Here that gives k = 6 and
a predicted rate of 2.16%.
Both hold up. Averaged over 24 independently-keyed filters the measured rate tracks the prediction to within 1.4% at every k from 3 to 8, and the measured minimum lands on k = 6 as promised.
What surprised me
My first run measured 2.33% against a predicted 2.16%. 8% worse than the spec. With 40,000 probes that’s five standard errors, far too big to shrug off, so I went looking for the bug: non-independent hashes, an off-by-one in the fill, the known result that the textbook formula is slightly optimistic.
None of those. The formula is fine. That one filter was bad.
Building 200 filters, each from a different set of 512 keys, and probing each with 40,000 absent keys:
| rate | vs formula | |
|---|---|---|
| formula | 2.158% | n/a |
| mean of 200 | 2.181% | 1.01x |
| best filter | 1.785% | 0.83x |
| worst filter | 2.533% | 1.17x |
| 90th percentile | 2.347% | 1.09x |
The spread across key sets is 6.3% of the mean and 1.9 times larger than the probe-sampling noise, so it isn’t measurement error, it’s real structural variation between filters. Which keys you inserted decides how much your bits overlap, and that’s fixed the moment you insert them.
So the formula is a statement about the population of filters, not about the object on your server. Yours is a single draw. It’ll sit somewhere in a 6%-wide band, it’ll sit there permanently, and probing it harder won’t move it. More probes measure your filter’s rate more precisely, and your filter’s rate is the thing that’s off.
That’s a strange kind of error to have in production. It doesn’t fluctuate, it can’t be averaged away, and every dashboard measuring it will agree with itself while disagreeing with the spec sheet.
What I would do next
Insert the keys, measure the rate, and if it came out unlucky, rebuild the whole filter with a different hash seed and measure again. Two draws, keep the better one. Same trick as picking a good hash function, applied one level up.