The Lab

Bloom filters

A probabilistic set that can tell you “definitely not” or “maybe”. Add words, watch the bits flip, and trip a false positive yourself.

9 min read

A web crawler has one question it asks billions of times: have I already fetched this URL? A database asks its own version before every disk read: could this key be in this file? Both are membership questions, and the obvious way to answer them, keep a set of everything you have seen, stops fitting in memory long before you run out of things to see.

An exact set does not fit

Storing a billion URLs at around 80 bytes each is 80 GB of raw strings before a hash table adds pointers and slack. A bloom filter answers the same yes-or-no question for the same billion URLs in about 1.2 GB. Drag the slider and watch where each one crosses a laptop's memory.

1 billion
Exact set of URLs75 GB
Bloom filter, 1% error1.1 GB
Log scale. The exact set crosses a laptop's RAM at around 200 million URLs; the bloom filter is still under it past ten billion.

The trick is noticing that you never needed the set. You needed one answer from it, and you were paying to store everything required to answer every other question too.

Store the shadow, not the item

A bloom filter is a row of bits, all starting at 0. To add a word, run it through 3 different hash functions. Each one points at a bit, and you flip those bits to 1. The word itself is thrown away.

To check a word, hash it the same way and look at the same bits. If any of them is still 0, the word was definitely never added, because adding it would have set that bit. If all of them are 1, it is probably there. Probably, because other words may have set those exact bits.

check “wolf”h1 → 1h2 → 15h3 → 13
0
0
1
1
2
1
3
1
4
1
5
0
6
0
7
1
8
0
9
0
10
0
11
0
12
0
13
1
14
0
15
1
16
0
17
1
18
0
19
0
20
0
21
0
22
1
23
1
24
0
25
0
26
0
27
0
28
1
29
0
“wolf”: all three bits are 1, but it was never added. Other words set them. A false positive.
Add
Check
5 words · 11 of 30 bits set · chance of a wrong yes 6.1%
Five fruits are already in, and wolf was just checked: all three of its bits are 1, yet it was never added. Add or check your own words, or clear it and start again.

That gives the filter a one-sided error. “No” is always true. “Yes” is only probably true. The asymmetry is what makes it useful: you put it in front of something expensive, and a “no” lets you skip the work with total confidence.

A false yes only costs you the lookup you would have done anyway. A false no is impossible.

The error rate is a number you choose

The false-positive rate is not luck. Tell the filter how many items to expect and how often a wrong yes is acceptable, and the arithmetic hands you the rest: how many bits per item, and how many hash functions. There is nothing to tune by feel.

1%
1 billion
9.6
bits per item
7
hash functions
1.1 GB
vs 75 GB exact
Each extra decimal place costs the same 4.8 bits
10%
4.8 bits
1%
9.6 bits
0.1%
14.4 bits
0.01%
19.2 bits
Item size never enters into it: a 4 KB document and a six-letter word cost the same, because the filter only keeps bits.

1% costs about 9.6 bits per item, a little over a byte. Every further factor of ten costs another flat 4.8 bits, which is why absurdly low error rates are usually affordable.

You have almost certainly used one. Every LSM-tree database (RocksDB, Cassandra, HBase) keeps a bloom filter in front of each file on disk so a read can skip files that definitely do not hold the key. Crawlers use them for the visited set, CDNs for “have we ever been asked for this”, and password checkers for lists of breached passwords. The shape is always the same: something expensive sits behind the filter, and a “definitely not” is worth a great deal.

The short version

  • A bloom filter answers “have I seen this?” without storing what it has seen.
  • Adding sets k bits; checking reads the same k bits.
  • Any 0 means definitely not. All 1s means probably yes.
  • About 10 bits per item buys a 1% error rate, whatever the size of the items.