Module 19 · Lesson 2 of 7
Bloom filters
“Definitely not” or “probably yes”, in a few bytes.
Gatepass has 40 million accounts. Every time someone types a username on the sign-up screen, the app asks "is this taken?", and every keystroke used to be a database query. A Bloom filter answers most of those questions from memory, in a few bytes per name, and is never wrong when it says no.
In this lesson you will fill a real Bloom filter, cause a false positive on purpose, and learn the one formula that tells you how big to make it.
A set that can only say "no" for sure
A Bloom filter is a summary of a set. You can add items to it and ask whether an item is in it. It can give two answers:
- "Definitely not." The item was never added. This answer is always correct.
- "Probably yes." The item was probably added, but it might be a coincidence. This is a false positive.
It never gives a false negative. That asymmetry is the whole point. If most of your questions have the answer "no", a Bloom filter lets you skip the expensive check for nearly all of them and only pay for the few that come back "probably".
For the username screen, most names people try are free. The filter says "definitely not taken" in under a microsecond, and only the "probably taken" cases go to the database to confirm.
How it works: m bits and k hashes
The filter is an array of m bits, all starting at 0, and k hash functions that each map an item to one bit position.
- Add an item: compute its k positions and set all of them to 1.
- Check an item: compute its k positions. If any of them is 0, the item was never added, because adding it would have set that bit. If all of them are 1, it was probably added.
Notice what is not stored: the names themselves. The filter holds only bits, so it cannot list its members, and it cannot delete one. Clearing asha's bits might also clear a bit that rohan needs, which would create a false negative.
Run it
This filter is real: names are hashed with FNV-1a, and the k positions come from two hashes combined as h1 + i × h2, a standard trick that behaves like k independent hash functions. The measured false-positive rate comes from checking 2,000 names that were never inserted.
Simulation · Bloom filter
Is this username taken?
Every name sets k bits. To check a name, look at its k bits: any 0 means definitely not taken; all 1s means probably taken. Fill the filter up and watch the false positives arrive.
m · bits
Orange: bit set. Outlined: the 3 bits for nikhil.
Definitely not taken
bits 32, 57, 18 → 000
Inserted: asha, rohan, meera, kabir, zoya, dev
Line: formula (1 − e−kn/m)k. Dot: measured on 2,000 names never inserted.
Names (n)
6
10.7 bits per name
Bits set
25%
Expected FP
1.5%
Measured FP
1.4%
best k here ≈ 7
Things to try:
- Type names into "Check a name" until you find a false positive. With 6 names in 64 bits it takes a while.
- Press "+10 users" a few times. The grid turns orange, and the measured dot climbs the curve. Past about half the bits set, false positives arrive quickly.
- Set k to 1, then 8, with 30 or so names. Too few hashes and each name is easy to impersonate. Too many and the array fills up fast. The best k sits in between.
- Change m. Doubling the bits does far more than halving the error.
The formula that sizes it
After inserting n items into m bits with k hashes, the chance that a given bit is still 0 is about e−kn/m. A false positive needs all k bits to be 1, so:
False-positive rate ≈ (1 − e^(−kn/m))^k, and it is lowest when k ≈ (m/n) × ln 2.
At that best k, the rule of thumb is simple: about 10 bits per item gives 1% false positives, and every extra 4.8 bits per item cuts it by another factor of 10.
Work it through for Gatepass. 40 million usernames at 1% needs about 9.6 bits each, so 384 million bits, which is 48 MB, with k = 7. The usernames themselves average 12 bytes, so storing the real set in a hash table costs well over 1 GB. The filter is roughly 25 times smaller and fits in every app server's memory.
What does 1% mean in practice? Of every 100 free names people try, one is wrongly flagged "probably taken" and costs one database query to clear up. The other 99 never touch the database.
Check yourself
The Gatepass Bloom filter says “definitely not” for the username “priya_k”. What can you conclude?
Where they hide in real systems
Bloom filters are everywhere a cheap "no" saves an expensive lookup:
- LSM-tree databases (Cassandra, RocksDB, HBase, Bigtable) keep a Bloom filter per data file. A read for a missing key skips every file whose filter says no, instead of reading each one from disk. You will see this in the next lesson.
- Web browsers have used them to check URLs against a list of malicious sites locally, asking the server only on a "probably".
- CDNs use them to avoid caching "one-hit wonders": an object is cached only on its second request, which the filter detects cheaply.
- Redis offers them as a module command,
BF.ADDandBF.EXISTS.
How it breaks
- Overfilling. A filter sized for 1 million items holding 5 million no longer has a 1% error rate; it is above 50%. You cannot resize a Bloom filter without the original items. Plan for growth, or use a scalable Bloom filter that adds new layers as it fills.
- Deletes. Plain filters cannot remove items. A counting Bloom filter stores a small counter per position instead of one bit, at 3–4× the memory. Cuckoo filters also support deletion and are often smaller at low error rates.
- Trusting "probably". A false positive must lead to a real check, not a decision. A filter that says "probably a fraudster" must not block anyone by itself.
Check yourself
You need a Bloom filter for 10 million items at about a 1% false-positive rate. Roughly how much memory?
Key takeaways
- A Bloom filter answers "definitely not" or "probably yes". It has false positives but never false negatives.
- It stores m bits and k hash functions, not the items, so it is tiny and cannot list or (normally) delete members.
- False-positive rate ≈ (1 − e^(−kn/m))^k. About 10 bits per item at the right k gives 1%.
- Use it in front of an expensive lookup where most answers are "no": disk reads in LSM trees, database checks, network calls.
- Size it for future growth. An overfilled filter quietly turns into one that says "probably" to everything.
Finished reading?
Mark it complete to tick it off in the course.