← Concepts

Placing data

Data

Bloom Filters

A few bits per item that can say "definitely not here" for billions of items from memory. The price is that "maybe" is sometimes wrong.

Fewer bits per item saves memory and raises the false-positive rate; there is no setting where both are free.

probabilisticmembershipfalse positivescrawlers

Try it

Move the dials — the sentence under the picture changes.
False positives vs. bits per item100%10%1%0.1%0.01%4812162024bits per item64 bits, 12 items, k = 641 of 64 bits set (64% full)A query for something never added lands on 6 bits;all 6 are set 7% of the time — a false positive.“No” is always right: a zero bit proves absence.“Maybe” is right unless every bit was set by others.Deleting is impossible — the bits are shared.
At 10 bits per item and k = 7, about 0.82% of “maybe” answers are wrong. A billion items would take 1.25 GB.

The question it answers

"Have I seen this before?" is the question a crawler asks forty times per page, a cache asks before going to disk, and a database asks before opening one of its data files on disk. An exact answer needs the set: every key, stored somewhere, looked up each time. At a billion keys that is tens of gigabytes and a disk read per question.

A Bloom filter answers from a few gigabytes of memory, in a handful of nanoseconds, with one concession: it can be wrong in one direction only. When it says not present, that is certain. When it says present, it means probably — and the chance it is wrong is a number you choose.

How it works

The filter is a bit array, all zeros. To add an item, hash it k times, and set the bit at each of the k positions. To ask about an item, hash it the same k times and look at the bits: if any is zero, the item was never added; if all are one, it probably was — unless every one of those bits was set by other items, which is the false positive.

The false-positive rate depends on how full the array is. With m bits, n items and k hashes, it is roughly (1 − e^(−kn/m))^k. The widget lets you move m and k and watch it. Two things fall out: about ten bits per item gets you under 1%, and there is a best k for any bits-per-item — more hashes fill the array faster, fewer leave more collisions unnoticed.

Ten bits per item, seven hashes, one percent false positives. A billion URLs in 1.2 GB of memory, instead of 60 GB on disk.

What it is for

The pattern is always the same: put the filter in front of something expensive, and let it say no. A crawler skips URLs the filter has seen and never touches the exact set for the 99% that are duplicates. A log-structured (LSM) database — one that stores data as a series of sorted files — keeps a filter per file and reads only the files that might hold the key — the difference between one disk read per lookup and ten. A CDN avoids caching an object the first time it is requested by checking whether it has been seen before, so one-hit wonders never evict anything.

In every case a false positive is cheap: one wasted lookup, one skipped page, one unnecessary cache fill. A false negative would be expensive — a duplicate crawled, a key reported missing — and the filter never produces one.

Where it goes wrong

  • Deletion. You cannot clear a bit; other items may share it. Use a counting filter (a small counter per position) or rebuild periodically.
  • Growth. A filter sized for a million items is useless at ten million; the false-positive rate climbs toward one. Size for the final count, or use a scalable variant that adds filters as it fills.
  • Bad hashes. Correlated hash functions collide together and the maths stops applying. Two good hashes and k linear combinations of them is the standard trick.
  • When you needed certainty. A filter is for "skip the work if you can". It is not a set.

Take this with you

  • The one idea: a tiny structure that can say "definitely not" for certain and "probably yes" cheaply, in front of something expensive.
  • In an interview, give the numbers — about ten bits per item for 1% false positives — and say which direction it can be wrong in.
  • At work, you are probably already using one: inside your database, your CDN, or your browser's safe-browsing check. Reach for it when "skip the work if you can" is the shape of the problem.