The Shortcut Has a Floor

A Bloom filter answers "have I seen this key?" with no false negatives and a tunable rate of false positives. Each key sets k bits in an array of m bits; a lookup checks the same k bits and says yes if they're all set. The textbook rate after n keys is (1 − e^−kn/m)^k. Give it 10 bits per key and 7 probes and it promises 0.82%. Give it 20 bits per key and 14 probes and it promises 0.0067%.

I wanted to know how often real filters keep that promise. The formula turned out to be fine. What breaks the promise is the arithmetic that turns a key's hash into k bit positions. The most popular shortcut puts a floor under the false-positive rate that no amount of memory gets you below, and a 2012 bug in a widely used Java library made big filters up to 4.5 times worse than advertised. I reproduced both.

The formula holds

The textbook formula assumes the bits are independent, which they aren't quite: setting one bit makes the others slightly less likely to be set. I computed the exact rate (a dynamic program over how many bits are set) for filters from 1,024 to 65,536 bits. At 1,024 bits with 20 bits per key, the exact rate is 2.7% above the formula; at 4,096 bits, 0.7%; at 65,536 bits, 0.04%. Simulated filters with truly independent probe positions matched the exact rate to within about two standard errors. Splitting the array into k slices with one probe each, another common layout, cost at most 9% at 1,024 bits and stayed within about 1% from 65,536 bits up.

So with good hashing, trust the formula. The question is whether you have good hashing.

Double hashing has a floor

Computing k independent hashes per key is slow. Kirsch and Mitzenmacher showed in 2006 that two are enough: take hashes h₁ and h₂ and probe h₁ + i·h₂ mod m for i = 0 … k−1. Their result is that the false-positive rate converges to the formula as the filter grows. It's the standard trick; most libraries use some form of it.

"Converges as the filter grows" leaves room at finite sizes. I simulated filters at 4,096 and 65,536 bits with ideal random hash values, so the only thing being tested is the index arithmetic, and swept the memory from 4 to 32 bits per key with the matching optimal k. Each point is 200 million lookups at 4,096 bits and a billion at 65,536 bits, across many independently built filters.

Up to 10 bits per key, every method lands within 4% of the formula. Past that, double hashing stops improving. With a power-of-two filter size and the stride h₂ taken straight from the hash, the rate bottoms out near 1.1/m: 2.7 in 10,000 for the 4,096-bit filter and 1.7 in 100,000 for the 65,536-bit one, whatever you spend. Using a prime size and forcing the stride to be nonzero lowers the floor to about 0.2/m. Enhanced double hashing (Dillinger and Manolios, which adds a cubic term, h₁ + i·h₂ + (i³−i)/6) lowers it to about 0.03/m.

65,536-bit (8 KB) filter: the formula's promise, and how many times worse each double-hashing variant measured. At 4,096 bits the 32-bits-per-key row reads 1,240×, 209× and 35×.

Where the floor comes from is easy to see once you look for it. If the stride happens to be 0, which a uniform hash gives you once in m keys, all k probes hit the same bit, and at the optimal k about half the bits are set. That alone is a false-positive rate of 0.5/m, and it's exactly the gap I measured between allowing stride 0 and forbidding it (0.51/m at 1,021 bits). With a power-of-two size, strides of m/2 and ±m/4 also cycle through only two or four bits, which adds roughly another 0.4/m. What's left after those are gone is pairs of keys that drew the same stride with nearby starting points and so share most of their probe positions, which for any one lookup has a chance on the order of kn/m². The cubic term breaks most of those overlaps.

None of this matters for big filters with modest targets: at 10 bits per key and 65,536 bits, every variant was within 1% of the formula. It matters when the target is low relative to 1/m. A rough rule from these runs: if the rate you want is below about ten times the floor, the floor shows. Plain double hashing in an 8 KB filter can't get below about one in 60,000 however much memory it gets, and it's already paying extra past one in 10,000. Small per-block or per-page filters asked for one in a million can be off by a lot.

A bug that only shows up in big filters

The arithmetic around the shortcut matters too. Guava, Google's core Java library, shipped this as its Bloom filter index computation, with 32-bit int hashes taken from a 128-bit MurmurHash3:

int combinedHash = hash1 + (i * hash2);
// Flip all the bits if it's negative (guaranteed positive number)
if (combinedHash < 0) {
  combinedHash = ~combinedHash;
}
bitsChanged |= bits.set(combinedHash % bitSize);

The index before the modulo is a number from 0 to 2³¹−1. In 2012 someone filed "BloomFilter broken when really big", with two problems. If the filter has more than 2³¹ bits, the rest are never touched. And if it has somewhat fewer, the modulo isn't uniform: at 3·2²⁹ bits, the first 2²⁹ positions get hit twice as often as the others. The report showed a filter configured for a one-in-a-million rate measuring three in a million.

I reimplemented that index arithmetic (signed 32-bit wraparound, the bit flip, the modulo; ideal random hash bits in place of MurmurHash3) and ran it on filters with up to 3 billion bits:

6 filters per row for the first two (3 for the last), 20 million lookups each (250 million for the one-in-a-million row). Standard errors are at most 2% of each value.

The 1.43× matches the 1.42× you get by hand from a third of the array taking half the probes, and the 3-billion-bit row is what a 2³¹-bit filter would give with all those keys crammed into it. The one-in-a-million case is worse than the 10-bits-per-key case because 20 probes compound the unevenness where 7 don't. Guava's fix was a new strategy, MURMUR128_MITZ_64, which uses two 64-bit halves of the hash and 64-bit arithmetic; the issue was slated for Guava 17 in 2014. The old strategy stays in the code so that filters serialized with it still read back correctly.

Doing the same thing in unsigned 32-bit arithmetic, without the flip, is better but still not right: the modulo of a 32-bit value is uneven too. It measured 1.11× at 3·2²⁹ bits and 1.43× at 3 billion.

A 32-bit hash is a floor too

One more way to get a floor: derive both probe hashes from a single 32-bit hash. Two keys whose hashes collide are then indistinguishable to the filter, so a lookup is a false positive whenever its hash matches any stored key's, which happens with probability about n/2³². With 100 million keys in a billion bits at 10 bits per key, the formula promises 0.82%. That design measured 3.08%, 3.8 times worse, and the 2.3% collision floor accounts for nearly all of the difference. At a million keys and a 1% target it adds under 3%, easy to miss in testing.

What I'd do

• Hash to 64 bits or more and keep the index arithmetic in 64 bits. Reduce to the filter size from the full 64-bit value, never from a 31- or 32-bit one.
• Use double hashing freely when the target is well above 1/m: at 10 bits per key it was within 4% of the formula from 4,096 bits up.
• For low targets in small filters, compare the target with about 1/m. If it's not well above, use enhanced double hashing (its floor was about 35 times lower in my runs) or truly independent hashes.
• Test a filter at the size you'll deploy, not a small one. Every problem here grows with size or with how low the target is.

Limits: random keys with ideal hash values, so this measures index arithmetic, not hash quality; weak hash functions on structured keys are a separate problem. The Guava rows reimplement its index computation in JavaScript; I didn't run the Java library. About 2,000 simulation runs in all, plus exact calculations for filters up to 65,536 bits.