We learn to demand that our data structures stay correct. A hash set that sometimes claims an absent item is present is a bug you would stay late to fix. So here's an idea that sounds like a joke: a data structure we allow to be wrong. It sometimes tells you “yes, that’s in the set” about something you never inserted. You would never ship that. Except it runs right now inside Cassandra, HBase, RocksDB, Bigtable, most CDNs, and the code that warns your browser about malicious URLs. Burton Bloom published the Bloom filter in 1970. It is one of the most deployed structures in all of software. Its whole power comes from being wrong, carefully, in exactly one direction.
Here is the thread that the whole post depends on. A Bloom filter trades a small, one-sided error for a large space win. The error only ever runs one way, so that trade is almost free. It can produce a false positive. It says “maybe present” when the answer is no. But the filter never produces a false negative. It never says “not present” about something that is present. Once you see that asymmetry, you see the entire trick. It explains why the filter lives in the hot read path of nearly every database you use.
The problem: “is X in this huge set?” — cheaply
A membership test sounds trivial: keep a HashSet, call .contains(). And for a few million small items, do exactly that. The trouble starts at scale. Suppose you need to ask “have I seen this key before?” against a billion keys. An exact structure must store the keys themselves. At, say, 32 bytes each, that is ~32 GB of RAM, per replica, forever. Or you keep the set on disk. Then you pay a slow random read for every single lookup, including the many lookups whose answer is “no.”
Now notice something about a lot of real workloads. Most lookups are misses. A database checks whether a key lives in a particular file. Your CDN checks whether it ever cached a URL. A crawler checks whether it already visited a link. In each case the common answer is “no.” So the question becomes this. Could we answer “definitely not” very cheaply, and pay the expensive exact lookup only for the rare “maybe”? That is precisely the shape of a Bloom filter.
How it works: a bit array and a few hashes
The entire structure is a bit array of m bits (all zero to start) and k independent hash functions. That is it. The filter never stores a key.
- Insert(x): run
xthrough allkhashes. Each hash produces an index into the bit array. Set thosekbits to 1. - Query(x): hash
xthe samekways and look at thosekbits. If any of them is 0 →xwas definitely never inserted. If all of them are 1 →xis probably in the set.
class BloomFilter {
constructor(m, k) { this.bits = new Uint8Array(m); this.m = m; this.k = k; }
add(x) {
for (let i = 0; i < this.k; i++) {
this.bits[hash(x, i) % this.m] = 1; // set k bits
}
}
mightContain(x) {
for (let i = 0; i < this.k; i++) {
if (this.bits[hash(x, i) % this.m] === 0) {
return false; // a 0 bit ⇒ DEFINITELY not present. Certain.
}
}
return true; // all 1s ⇒ MAYBE present. Go verify.
}
}The asymmetry comes straight from the mechanics. If you inserted x, you set its k bits. Bits only ever move from 0→1, and the filter never clears them. So a later query still finds those bits at 1. A false negative is impossible. But a false positive can happen. Other insertions might set all of x’s k bits by collision. The filter sees all-1s and honestly reports “maybe,” even though you never added x.
The math: how wrong, and how small
The false-positive rate is not vague. You tune it with two knobs: m (bits) and k (hashes), against n (items inserted). The false-positive probability is approximately:
// p ≈ (1 - e^(-k·n/m))^k
// Optimal number of hashes for a given size: k = (m/n)·ln 2
You do not need to memorize it. You need the punchline, and it is genuinely surprising:
| Bits per item (m/n) | Optimal hashes (k) | False-positive rate |
|---|---|---|
| ~5 bits | 3 | ~10% |
| ~10 bits | 7 | ~1% |
| ~15 bits | 10 | ~0.1% |
| ~20 bits | 14 | ~0.01% |
The main use: skipping disk reads in an LSM tree
Here is where Bloom filters earn their fame. It connects directly to how modern write-optimized databases store data. In an LSM-tree (Cassandra, RocksDB, LevelDB, HBase, ScyllaDB), the engine spreads your data across many immutable files on disk called SSTables. A single key could live in any of them, or in none. So a naïve point lookup for a key that does not exist is a disaster. You check every SSTable, and each check is a random disk read. You pay all of that just to conclude “not found.” Misses become the most expensive reads, which is exactly backwards.
The fix: give each SSTable its own small Bloom filter. The engine holds it in RAM, and it summarizes the keys inside that SSTable. Now a lookup asks each filter first:
- Filter says “definitely not here” → skip that SSTable entirely. No disk read. This is the common case, and it is free.
- Filter says “maybe” → now, and only now, pay for the real disk read to check.
The result is dramatic. For a non-existent key, the number of disk seeks drops from “one per SSTable” to “roughly zero” plus the occasional false-positive read. Bloom filters are the single reason LSM read amplification stays survivable. Turn them off in RocksDB or Cassandra, and your read latency and disk IO grow fast. This is one of the highest-leverage knobs in the whole storage engine.
Where else you meet them
- Cassandra / HBase / RocksDB / Bigtable. Per-SSTable filters to skip disk on point lookups (above).
- CDNs & caches. They detect the “one-hit wonder.” Do not cache a URL until you see it at least twice. A Bloom filter cheaply remembers “have I seen this once before?” across billions of URLs. Akamai used this to avoid caching objects that arrive only once.
- Chrome / Google Safe Browsing. Your browser can’t download the whole multi-million-entry malicious-URL list. It keeps a Bloom filter locally. The filter answers “definitely safe” for the vast majority. Only on a “maybe” does the browser ask Google’s server to check. Fast, private-ish, and small.
- Bitcoin (SPV wallets, BIP-37). Lightweight clients send a Bloom filter of their addresses. Full nodes then return only plausibly relevant transactions, and they never learn exactly which addresses are yours.
- Databases that avoid duplicate work. Web crawlers dedup “already-visited” URLs. Analytics systems dedup events. Medium checks “have you already read this post?” These are all membership tests where a rare false positive is harmless.
- Weak-password / breach checks. “Is this password in the leaked set?” A false positive only makes a user select a different password. No harm.
The fine print: the real limits
The one-sided-error deal brings real constraints, and you must design around them:
- You can’t delete. If you clear an item’s bits, you might clear a bit that another item needs. That creates a false negative, the one error a Bloom filter must never make. Standard Bloom filters only insert. To delete items you need a counting Bloom filter, where each slot holds a small counter instead of a bit. You can also rebuild the filter from scratch at intervals.
- You must size for
nup front. The FPR is only as good as your estimate of how many items you insert. Overfill it, and the bit array saturates toward all-1s. The false-positive rate then climbs toward 100%, and every query becomes “maybe.” Scalable Bloom filters add capacity. They chain a new filter when the current one fills. - It only answers membership. You can’t list what’s inside, read values, or get a count. It answers exactly one question, “possibly present?”, and nothing else.
- Your design must tolerate false positives. The pattern only works when a “maybe” triggers a cheap, correct fallback, such as a disk read or a server call. If a false positive causes a wrong result instead of a redundant check, a Bloom filter is the wrong tool.
- Tiny — ~10 bits/element for 1% FPR, regardless of element size.
- O(k) constant-time insert and query.
- Never a false negative — “no” is always true.
- Turns expensive misses into free RAM checks.
- False positives — “yes” means “maybe, check.”
- No deletion (without a counting variant).
- Must size for expected
n. It degrades when overfilled. - Membership only — no values, counts, or iteration.
The takeaway
The instinct that a data structure must be perfectly correct makes the Bloom filter feel like cheating. But look at what the “error” actually costs you: nothing. One reframe carries the whole idea:
- A bounded, one-sided error is almost free. A Bloom filter is wrong only in the safe direction, with false positives and never false negatives. So you can put it in front of any expensive membership check as a cheap gate. “No” ends the query at once and with certainty. “Maybe” falls through to the real lookup you wanted anyway. You buy a ~1000× space reduction, and you pay only in the occasional unnecessary check.
- This is a whole family, not a one-off. The Bloom filter is the gateway to approximate data structures. HyperLogLog counts a billion distinct items in ~1.5 KB. Count-Min Sketch estimates frequencies in constant space. All of them rest on the same bargain. Give up exactness within a known error bound, and space and speed collapse by orders of magnitude.
Next time you are about to hold an entire set in memory, ask the question a Bloom filter poses. Ask it too when you are about to read the disk for each “have I seen this before?” check. Do I actually need a perfect answer here? Or do I need a fast, certain “no” and a cheap way to check the “maybes”? Surprisingly often, being a little bit wrong on purpose is the most efficient way to be right.
bloom_filter_fp_chance. Fan et al. wrote “Cuckoo Filter: Practically Better Than Bloom” (2014). For the wider family, read Flajolet et al. on HyperLogLog and Cormode & Muthukrishnan on the Count-Min Sketch. This post pairs with the LSM-tree deep dive, where these filters live. It also pairs with the long-tail post, because the misses a Bloom filter eliminates are the cold tail.