Backend & Data
Bloom filters — saying "probably" to save a lookup
Some of the best tricks in computing come from relaxing a requirement. A Bloom filter answers one question — "is this item in the set?" — using a fraction of the memory a real set would need. The catch: it can be wrong in one direction. It may say "probably yes" when the answer is no, but it will never say "no" when the answer is yes. That one-sided error is exactly what makes it so cheap and so useful.
How it works: bits and hashes
A Bloom filter is just a big array of bits, all starting at 0, plus a handful of hash functions. To add an item, hash it with each function to get several positions, and set those bits to 1. To check an item, hash it the same way and look: if any of those bits is 0, the item was definitely never added. If all are 1, it's probably present — probably, because other items might have set those same bits.
The one-sided guarantee
This asymmetry is the whole point. A "no" is certain — you skipped a bit that any real member would have set. A "yes" is only probable — a false positive, where unrelated items happened to set all the bits you checked. There are never false negatives. So a Bloom filter is perfect as a cheap first gate in front of an expensive lookup.
It's a memory-tiny "have I seen this?" checker. If it says no, that's the truth. If it says yes, it's usually right but might be bluffing — so you only pay for the slow real lookup on a "yes".
Where it earns its keep
- Databases check a Bloom filter before hitting disk: if the filter says the key isn't in this file, skip the read entirely. Huge savings on lookups for keys that don't exist.
- Caches and CDNs use them to avoid caching one-hit-wonder URLs.
- Web browsers and security tools have used them to test URLs against big blocklists without shipping the whole list.
The knobs are the trade-off: more bits and more hash functions push the false-positive rate down, at the cost of memory. You size it for your tolerance — say 1% false positives — and enjoy answering a set-membership question in a few bits per item instead of storing every item. It's the same spirit as a database index or a cache: spend a little cheap structure up front to avoid a lot of expensive work later.