Bloom filters: why “no” is certain but “yes” only means “maybe”
TL;DR
A Bloom filter is a bit array kept in RAM. Each written key flips a few bits to 1. On lookup, a single 0 bit proves the key is absent — no disk touched. If every bit is 1, the key “might” exist and you must read disk to be sure.
How it works, by example
Take a 16-bit array where each key hashes to 3 positions. Writing user:10, user:22 and user:51 lights up 9 bits.
| Lookup | Filter answer | What happens |
|---|---|---|
user:84 | One bit is 0 → NO | Answered in RAM, no disk read. |
user:22 | All 3 bits are 1 → MAYBE | Read disk, confirm the key exists. |
user:47 | All 3 bits are 1 (set by other keys) → MAYBE | Disk read reveals it’s missing — a false positive. |
How to put it to work
- Backend developers: Put a Bloom filter in front of your cache/DB to block lookups for non-existent keys (cache penetration), or for fast “have we seen this URL/ID?” checks.
- When tuning: The false-positive rate depends on array size and number of hash functions — more memory means fewer false positives.
- Remember: A classic Bloom filter can’t delete items; use a variant such as a Counting Bloom filter if you need deletes.