Bloom filter
We'll cover the following
A tiny in-memory structure that answers "is this key definitely absent, or maybe present?". It tracks all valid keys in the DB, not just what is cached.
How it works: a row of switches
An array of bits, all 0 at the start (the switches), plus a few hash functions. Each hash turns a key into a position.
index: 0 1 2 3 4 5 6 7 8 9 (10 bits, 3 hash functions)
start: 0 0 0 0 0 0 0 0 0 0
add "abc" -> hashes give 1, 4, 7 flip those to 1
add "xyz" -> hashes give 2, 4, 9 flip those to 1
bits: 0 1 1 0 1 0 0 1 0 1
check "abc" -> 1,4,7 all 1 => maybe present
check "foo" -> 0,4,7 bit 0 is 0 => DEFINITELY NOT present
check "bar" -> 2,7,9 all 1 but never added => false positive- No false negatives: adding a key always sets its bits, and bits never turn off.
- Some false positives: other keys may have set the same bits. Those requests just fall through to the cache and DB.
- The bits are shared, not owned per key. Different keys can flip the same switch.
Sizing: one rule of thumb
About 10 bits per key gives ~1% false positives, with ~7 hash functions. 1 billion objects x 10 bits = 10 billion bits = ~1.25 GB, which fits in one machine. Storing the 1B keys themselves would take ~30-50 GB.
Why 10: with 10 bits per key and 7 hashes about half the switches end up on, the ideal balance. A fake key needs all 7 of its switches on: 0.5^7 is about 0.8%, so ~1%. Fewer bits, more errors:
| Bits per key | False positives |
|---|---|
| ~5 | ~10% |
| ~10 | ~1% |
| ~15 | ~0.1% |
Using it against cache penetration
Add every valid key when it is created. On a read, check the filter first: "definitely not present" returns 404 without touching cache or DB.
Keeping it up to date across nodes
Adds only flip bits 0 to 1, so merging two copies is a simple OR with no conflicts.
- One central filter (Redis Bloom module), updated by the write path. Always consistent, one network hop per read.
- Local copy on each app server, rebuilt from the DB every few hours, with new keys broadcast via Kafka or pub/sub. Fast, but updates lag.
- Hybrid: a big local filter plus a small "recently created keys" set checked alongside it.
The danger: a stale local copy can give a false negative for a brand-new URL (created a second ago, filter has not seen it) and reject a valid request. A Bloom filter must never do that. Fix with the recent-keys check, or update the filter before returning success on the write path.
Plain Bloom filters cannot delete keys. If keys expire, rebuild periodically or use a counting Bloom filter.
Summary: say it in the interview
- "1B keys, about 10 bits each: ~1.25 GB and 7 hashes, ~1% false positives. It is an optimization, not step one; caching the not-found result is simpler."