Bloom Filter
On this page
A web crawler finds 100 million new links a day. Before fetching each one, it must ask "have I already crawled this URL?" The answer lives in a database of 10 billion URLs. Checking it costs a network round trip and a disk read per link, and since most links are new, almost every check returns "no" after doing all that work. The crawler spends more time asking than crawling.
What it needs is a tiny, in-memory structure that can say "definitely not seen" instantly for most URLs, and only send the doubtful ones to the database. That structure is a Bloom filter.
How it works

Start with an array of m bits, all 0, and pick k independent hash functions.
- Add an item: compute its k hashes, each giving a position in the array, and set those bits to 1.
- Check an item: compute the same k positions. If any of them is 0, the item was never added; nothing could have cleared that bit. If all are 1, the item was probably added, but those bits might have been set by other items. That is a false positive.
The filter never stores the items themselves, which is why it is so small, and why it cannot list them or delete them.
Sizing
Three numbers are linked: the number of items n, the bits m, and the false-positive rate p. Useful rules of thumb:
| Bits per item (m / n) | Best k | False-positive rate |
|---|---|---|
| 5 | 3–4 | about 9% |
| 10 | 7 | about 1% |
| 15 | 10 | about 0.1% |
| 20 | 14 | about 0.01% |
The formula behind it is m = −n · ln(p) / (ln 2)², with k = (m / n) · ln 2. For 1 billion items at 1%: about 9.6 billion bits, which is 1.2 GB. Storing the URLs themselves (about 100 bytes each) would take about 100 GB.
If you add more items than you sized for, the array fills with 1s and the false-positive rate climbs quickly. Size for the expected peak, or rebuild a larger filter.
Where it goes

The pattern is always the same: put the filter in front of something expensive, and only pay for the expensive check when the filter says "maybe".
Trade-offs and costs
- False positives, never false negatives. Design so that a false positive costs a little (one extra database read), never correctness.
- No deletes. Clearing a bit might erase evidence of another item. Variants exist: a counting Bloom filter keeps small counters instead of bits (about 4× the memory) and supports delete; a cuckoo filter supports delete with similar space.
- Must be rebuilt to grow. A standard filter has a fixed size. Scalable variants chain filters of growing size.
- Rebuild on restart. If the filter lives in memory, you need to reload it from the source data or a snapshot after a crash.
- CPU per check is k hash computations, still microseconds, far cheaper than any I/O.
When to reach for it
- "Have I seen this before?" over a huge set, where most answers are "no": crawled URLs, already-recommended items, usernames taken.
- Avoiding disk reads for keys that do not exist. LSM-tree databases (Cassandra, RocksDB, HBase) keep a Bloom filter per data file, so a read skips files that cannot contain the key.
- Cutting network calls: a client-side filter of known-malicious URLs, checked locally before asking a server.
- Join and dedup steps in data pipelines, to skip records that cannot match.
Do not use it when you need the exact answer every time, when you must delete often, or when the set is small enough to keep in a hash set.
Example
Crawler deduplication. Assumptions: 10 billion URLs already crawled, 100 million new links discovered per day, about 80% of them truly new.
- Filter size: 10 billion URLs at 1% false positives needs about 12 GB of bits. Split it into 16 shards by URL hash, about 750 MB each, held in memory on the frontier servers.
- Per-link check: hash the normalized URL, check its shard. 80 million new links get "definitely not seen" and go straight to the crawl queue with no database read.
- The "maybe" path: 20 million links that were really seen, plus about 1% of the 80 million new ones (0.8 million false positives), go to the seen-URL store for an exact check. Database reads drop from 100 million to about 21 million a day.
- Adding: after a URL is crawled, add it to the filter and the store.
- Growth: at 100 million new URLs a day the filter fills; rebuild it monthly at a larger size from the URL store.
Common mistakes
- Treating "maybe" as "yes". If the filter says maybe, confirm with the real store, unless a false positive is truly harmless.
- Getting the direction wrong. It can say "definitely not", never "definitely yes".
- Undersizing and then adding far more items than planned, so the false-positive rate climbs past 10%.
- Trying to delete from a standard filter.
- Using it where a hash set fits in memory and gives exact answers.
Say this in the interview
"Before fetching a URL, the frontier checks a Bloom filter of crawled URLs. With 10 bits per URL we get about 1% false positives, so 10 billion URLs fit in about 12 GB across a few servers. If the filter says not seen, we crawl without touching the database; if it says maybe, we confirm against the URL store. A false positive costs one extra read, never a wrong result. We rebuild the filter from the store when it gets full."
Used in
- Database (LSM-tree reads), Cache (skip lookups for keys that don't exist), Read-heavy Systems.
- Design a Web Crawler, Design a Distributed Key-Value Store, Design a URL Shortener.