Bloom Filters

Pradeep P
2 days ago
3 min read

Series: Modern System Design · Layer 4 — Data

Layer 4 · Post 17 of 17

← Previous: Logical Clocks → Next: Sidecar Pattern

Layer 4 — Data · Post 111 of 119

A compact structure that can say "definitely not present" or "maybe present" — never a false negative, sometimes a false positive.

What you'll learn

Why a few extra hash bits save a disk seek or an RPC
How false positives behave, and why deletes are awkward
Where LSM trees, CDNs, and "is this user id new?" use them

The idea in one minute

A Bloom filter is a bit array plus k hash functions. To add a key, set k bits. To query: if any of those bits is 0, the key was never added (definite miss). If all are 1, the key is probably in the set — or those bits were set by other keys (false positive).

Add "alice":   hashes -> bits 3, 19, 41  set to 1
Query "bob":   bit 7 is 0  ->  definitely not present
Query "carol": all 1s      ->  maybe — go check the real store

You trade a tunable false-positive rate for tiny memory. You cannot list the keys, and classic Bloom cannot delete (clearing a bit breaks other keys). Counting Bloom / cuckoo filters exist for that.

Why it matters

This is the named trick behind "don't hit disk / origin if we know the key is absent." LSM-tree databases (Cassandra, RocksDB, LevelDB) keep a Bloom per SSTable so a read does not open every file. Caches use it to skip origin for never-seen URLs. Interviewers like it because it is probabilistic systems design in one data structure — not a buzzword.

It does not replace an index. A positive still needs a real lookup.

How it works

Parameters. Array size m, items n, hashes k. False-positive rate is roughly (1 - e^{-kn/m})^k. You pick a budget (e.g. 1% FPR) and size m from expected n. Undersize the array and the filter becomes "maybe" for everything — useless.

k is usually small (a handful). Too many hashes = more bits set = more false positives after a point.

No false negatives (if you implemented hashes correctly and never deleted bits). That invariant is why it is safe as a negative cache for existence.

Deletes. Bit-clearing is wrong. Rebuild, use a counting filter, or a cuckoo filter (can delete, different failure modes).

Cardinality. Bloom does not count distinct items well (HyperLogLog is the named cousin for count). Bloom is membership.

Distributed. Union of Bloom filters (OR the bits) works if they used the same m and hashes. Intersection is not "keys in both sets" in a clean way. Sending a Bloom of a cache to a peer is a known "what might you have?" gossip trick.

A simple example

Username signup: "is alice taken?" The DB has billions of users. A Bloom of taken names lives in memory. No → return "available" without a query (must still transactionally insert — Bloom can lag; a race needs a unique constraint). Yes → SELECT to confirm (false positive: name is actually free; you did an extra read, still correct if you check).

Bad use: Bloom says no, you skip the unique index and insert. Another replica already inserted. You needed the constraint anyway.

SSTable: "does this file contain user:42?" Bloom says no → skip 64 MB file. Bloom says maybe → read index / data. False positives cost a seek; false negatives would miss data — Bloom is built so that does not happen.

Common mistakes

Using it as the source of truth. Always confirm positives on the real store when it matters.

Forgetting to size for n. A "small Bloom" that has eaten 10× planned keys is a random bit set.

Deletes on a classic Bloom. Silent corruption of other keys' bits.

Hashing the wrong thing. Hash userId consistently; hash of User{id, ts} changes and you will false-negative (worse: you think you cannot FN, but you hashed a different string).

Security. Bloom of passwords or tokens can still leak membership to a probing attacker. Do not expose internal filters as public APIs without thought.

How this shows up in real systems

Cassandra, RocksDB, HBase, Bigtable papers: SSTable Blooms.
Akamai / CDN / squid-style: "might this be in cache?"
Chrome Safe Browsing (historical): compact bad-URL set.
Spark / BigQuery / warehouse: some join filters (Bloom joins).

Recap

Definite no / maybe yes. Never a false negative; tune false positives vs memory.
Use it to skip work, then verify on the real data.
Next: how we actually run proxies next to apps — sidecar.