Bloom filter: checking membership with tiny memory

A Bloom filter is a compact data structure that answers one question: is this item in the set? Its answers are:

• "Definitely not": always correct.
• "Possibly yes": usually right, sometimes a false positive.

It never gives a false negative, and it uses far less memory than storing the items.

How it works

Start with an array of m bits, all 0, and k different hash functions.

• Add an item: run it through the k hashes, and set those k bit positions to 1.
• Check an item: run the same k hashes. If any bit is 0, the item was never added. If all are 1, it was probably added (those bits might have been set by other items).

Tuning

More bits per item and the right number of hashes lower the false-positive rate. As a rough guide, about 10 bits per item with 7 hashes gives around a 1% false-positive rate. You choose the rate you can accept when you size the filter.

Limits

• You cannot delete an item, since bits are shared. A counting Bloom filter uses small counters instead of bits to allow removal.
• It does not store the items, so you cannot list them.
• If you add far more items than planned, false positives rise.

Where it is used

• Cache penetration: before querying the database for a key, check the filter. If it says "definitely not", skip the query. This protects the database from requests for items that do not exist.
• Databases (LSM-tree stores like Cassandra, RocksDB): avoid reading disk files that cannot contain a key.
• Crawlers: "have I already visited this URL?"
• Spam and malicious-URL pre-checks, and duplicate detection in large streams.

Example

A signup form checks "is this username taken?" A Bloom filter of all usernames says "definitely not taken" for most new names, so you skip the database. When it says "maybe", you do the real check.

Takeaway: use a Bloom filter as a cheap first check that can say "no" with certainty, and always confirm "maybe" with the real source.

---

System Design series, Part 2 (building blocks): topic 8 of 14. Previous: gRPC vs REST: which API style to choose.