Bloom filters

Every database that stores data on disk faces the same annoying question thousands of times a second: is this key even here? Answering it properly means a disk seek. Answering it wrongly in the cautious direction - “maybe, go and check” - costs the same seek you were going to do anyway. Answering it wrongly in the confident direction would corrupt your results.

A Bloom filter is what you build when you notice that asymmetry.^[1]paperSpace/Time Trade-offs in Hash Coding with Allowable ErrorsBloom, B. H., Communications of the ACM 13(7), 1970

Shrink the bit array until the measured false positive rate parts company with the formula. Then hit Saturate and watch it answer yes to everything.

Inserted

0 / 200

Bits set

0.0%

Queries

0

False positives

-

▶ PlayStepResetNew seedtick 0 / 1200Copy link to this state

Break itSaturate

Bit array size (m)

1024 bits

Shrink this and watch the array fill up.

Hash functions (k)

3

More hashes means fewer collisions per key, but fills the array faster.

Keys to insert (n)

200

How it actually works

The structure is a bit array of size m and k hash functions. To insert a key, hash it k ways and set those k bits. To query a key, hash it the same k ways and check whether all of those bits are set.

If any bit is clear, the key was definitely never inserted - inserting it would have set that bit. That is the guarantee, and it is absolute. If every bit is set, the key is probably present, but those bits may simply have been set by other keys that happened to collide.

So the error is one-sided: false positives yes, false negatives never.

The formula, and where it comes from

After inserting n keys, a given bit is still clear with probability (1 - 1/m)^(kn), which for large m approaches e^(-kn/m). A query needs all k of its bits set, so:

P(false positive) ≈ (1 - e^(-kn/m))^k

Two things fall out of it that people consistently get wrong.

More hash functions is not better. Each extra hash makes a false positive require one more coincidence, but also sets one more bit per insert, filling the array faster. The optimum is k = (m/n)·ln 2, and past it the rate climbs again. Turn k up to 10 in the widget with the defaults and watch the rate get worse.

The formula is an approximation, and a slightly optimistic one. It assumes the k positions are independent, which they are not - a rigorous treatment shows the classic expression is a lower bound on the true rate.^[3]paperOn the False-Positive Rate of Bloom FiltersBose, P. et al., Information Processing Letters 108(4), 2008

The k-hashes-are-expensive problem

Computing ten independent hashes per lookup would defeat the purpose. In practice you compute two and derive the rest:

position_i = (h1 + i·h2) mod m

Kirsch and Mitzenmacher showed this costs nothing in false positive rate compared to k genuinely independent hashes.^[2]paperLess Hashing, Same Performance: Building a Better Bloom FilterKirsch, A. & Mitzenmacher, M., ESA 2006, 2006 Nearly every production implementation does this, RocksDB included.^[4]source codeRocksDB - Bloom filters in the SST read path

What it costs you

You cannot delete. Clearing a key’s bits would clear bits other keys are relying on, which would create the false negatives the structure promises never to produce. Counting Bloom filters buy deletion back by replacing bits with small counters, at several times the space.

You cannot enumerate. The filter knows nothing about which keys are inside it; there is nothing to iterate.

And it degrades rather than failing. Push past the n you sized for and nothing breaks, errors are not reported, and no exception is raised - the answer simply drifts toward “yes” for everything. Hit Saturate in the widget: the array goes solid, the false positive rate climbs toward 100%, and the filter is still, technically, working exactly as designed.

The dial

You gainMembership testing in a fraction of the memory the real set would need

You payOccasional false positives, no deletions, and no way to enumerate what is inside

The line - when someone asks

A Bloom filter is a bit array plus k hash functions: inserting sets k bits, and querying checks those same k bits. It can say "probably present" when the item was never inserted, but it can never say "absent" about something you did insert - the error is one-sided. You size it with m ≈ -n·ln(p)/(ln2)², and you reach for it when a false positive costs you a cheap extra lookup rather than a wrong answer.

Recall

Loading…

Where are you with this?

SeenUnderstoodMastered

Saved on this device. Sign in to keep it across devices.

Sources

Primary

• [1]
  Space/Time Trade-offs in Hash Coding with Allowable Errors

  Bloom, B. H.Communications of the ACM 13(7)1970paperprimaryarchived
• [2]
  Less Hashing, Same Performance: Building a Better Bloom Filter

  Kirsch, A. & Mitzenmacher, M.ESA 20062006paperprimary
• [3]
  On the False-Positive Rate of Bloom Filters

  Bose, P. et al.Information Processing Letters 108(4)2008paperprimary

Secondary

• [4]
  RocksDB - Bloom filters in the SST read path

  source code