Bloom filters
A tiny set that says 'definitely not here' for almost no memory.
01The intuition
The problem it solves
A school keeps a list of students who have been banned from the library. There are 50 such names. The librarian checks every student against it, which is easy: a 50-line list fits on one page.
Now make it the internet. A service must check every incoming connection against a denylist of 200 million bad IP addresses, and it must do it at the edge, on hundreds of small servers, a million times a second. Each IPv4 address is 4 bytes, each IPv6 address 16 bytes. A plain set of 200 million entries costs a few gigabytes with the overhead of a hash table, which does not fit comfortably in every edge server's memory, and shipping a multi-gigabyte update to every edge whenever the list changes is slow.
Look at what the check actually needs. Almost every connection is innocent. For those, the only answer required is "definitely not on the list". A structure that answers "definitely not" cheaply, and "maybe, go check the real list" rarely, would remove nearly all the work. That structure is a Bloom filter.
Build it one piece at a time
Step 1: an array of bits. Start with 16 bits, all 0. Choose three hash functions, each of which turns an address into a number from 0 to 15.
Step 2: add an item. To add address A, compute the three hashes, say 2, 7 and 11, and set those bits to 1.
| Bit | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| after A (2, 7, 11) | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| after B (5, 7, 14) | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
Step 3: query an item. To ask about address C, compute its three hashes. If any of the three bits is 0, C was never added: a bit set by an add is never cleared, so an added item always has all its bits at 1. That is the "definitely not" answer. If all three bits are 1, C might have been added, or other items might have set those bits by coincidence. That is the "maybe" answer, and it sends the request to the real list.
Step 4: size it for the job. The chance of a false "maybe" depends on how full the bit array is. With more bits per item and the right number of hash functions, the false positive rate drops fast. For 200 million addresses at a 1 percent false positive rate you need about 10 bits per item, roughly 240 MB, and 7 hash functions. That fits in every edge server, and a new version ships as one file.
Step 5: handle removals. You cannot clear a bit, because another item may share it. Two answers: rebuild the filter from the current list every few minutes, or use a counting Bloom filter, where each slot is a small counter that an add increments and a remove decrements, at several times the memory.
Why it works, with the numbers
With m bits, n items and k hash functions, the probability that a given bit is still 0 after all inserts is (1 − 1/m)kn, and a false positive needs all k probed bits to be 1:
false positive rate ≈ (1 − e−kn/m)k
At m/n = 10 and k = 7 this is about 0.008. So of a million innocent connections, about 8,000 go to the real list and 992,000 are cleared from memory in a few hundred nanoseconds. The guarantee is one-sided: no false negatives, ever. Every banned address is caught. The failure mode is the opposite: an innocent address occasionally takes the slow path, which must be cheap enough to tolerate, and the filter must be rebuilt when the real list changes.
The trade-off you must say out loud
You trade exactness for memory. Say the false positive rate you chose and what happens on a false positive: a lookup in the authoritative store, never a block. Say how the filter is refreshed and how long an address can be newly banned before every edge knows. The follow-up is "why not a hash set", and the answer is the arithmetic above: 240 MB versus several gigabytes, and one file to ship.
Where it shows up in the 100 Google problems
- IP denylist: a filter at every edge answers "not banned" for almost all traffic; only the maybes consult the list.
- Fraud and DDoS protection: known bad fingerprints and addresses are checked the same way before any expensive work.
- Web crawler: "have we seen this URL" over billions of URLs is the classic Bloom filter job, with the rare false positive meaning a page is skipped.
- Distributed cache: a filter in front of storage avoids disk reads for keys that were never written.