What Is a Bloom Filter - and When You Actually Don't Need One
A Bloom filter is a small, fixed-size bit array that answers one question: "is this key definitely absent, or possibly present?" It never says no when the answer is yes, but it will sometimes say maybe when the answer is no.
That asymmetry is the whole product. You trade exact answers for memory, and you get a structure that holds membership information for millions of keys in a few megabytes, with no stored keys at all.
The problem it exists to solve is expensive lookups. If checking whether a key exists means a disk seek, a network round trip, or a cross-region query, you want something cheap in front of it that can rule out most of the misses. A Bloom filter is that guard, and its cost is that it lets a small fraction of misses through and can never take a key back out.
| Concept | Bloom filter (BF) |
|---|---|
| Where it sits | Data structure - sits in front of an expensive lookup, at the cache or storage layer |
| In one sentence | A probabilistic set membership structure that can tell you a key is definitely absent, but only that it is probably present. |
The 60-Second Answer
A Bloom filter is a bit array plus k hash functions. Adding a key sets k bits; checking a key tests those same k bits. All bits set means "maybe present"; any bit clear means "definitely absent".
The one problem it solves: it kills the cost of negative lookups. Queries for keys that do not exist get rejected in memory instead of hitting disk, network, or another service.
The one cost it adds: false positives, and no deletion. Every query still needs a real lookup behind it to confirm a hit, and once a key is in, a standard Bloom filter cannot remove it - you rebuild.
Use it when misses dominate your traffic and the miss path is expensive. If the whole key set fits in a hash set in memory, use the hash set.
How It Actually Works
The mechanism, step by step
- 1. The filter is a bit array, not a container of keys
- 2. k hash functions map each key to k bit positions
- 3. A query tests the same k bits and returns absent or maybe
- 4. False positive rate is a function of bits per key and k
- 5. Deletion is not supported, and clearing bits corrupts the filter
- 6. Rebuilds handle churn, and the swap has to be atomic
- 7. The filter only pays off when misses are common and expensive
1. The filter is a bit array, not a container of keys
Nothing is stored, only evidence
A Bloom filter allocates m bits, all zero, and never stores the keys themselves. That is why its size depends on the number of keys and the error rate you accept, not on how long the keys are.
A 64-byte URL and a 4-byte integer occupy exactly the same space in the filter. This also means you cannot enumerate the contents, and you cannot ask the filter what it holds - you can only interrogate it one candidate at a time.
⚠️ In production — Because keys are not stored, you cannot rebuild a Bloom filter from itself. If you lose the source of truth for the key set, the filter is unrecoverable - it is a derived index, and your backup plan has to treat it as one.
2. k hash functions map each key to k bit positions
One key, several independent slots
Inserting a key runs it through k independent hash functions, each yielding an index into the bit array, and sets those bits to 1. Multiple keys will collide on individual bits, and that is expected - the design assumes bits are shared.
In practice implementations rarely run k separate hash algorithms. They compute one wide, high-quality hash and derive k indices from its halves, which is far cheaper and behaves close enough to independent hashing for the math to hold.
h = hash128(key)
h1, h2 = h & 0xFFFFFFFFFFFFFFFF, h >> 64
for i in range(k):
bits[(h1 + i * h2) % m] = 1
⚠️ In production — The hash must be well-distributed, not cryptographic. Using a weak hash - or worse, a language's built-in object hash that is randomised per process - will either wreck your false positive rate or make the filter's contents inconsistent across restarts and across machines.
3. A query tests the same k bits and returns absent or maybe
One zero is proof, all ones is a guess
Lookup hashes the candidate the same way and reads the k bits. If any bit is 0, the key was never inserted - that is a mathematical certainty, since insertion would have set it. If all k bits are 1, the key may have been inserted, or those bits may have been set by other keys.
This is why the answer type is not boolean. The correct mental model is DEFINITELY_NOT or MAYBE, and every MAYBE has to be resolved by the real lookup behind the filter.
⚠️ In production — Teams write if (filter.mightContain(key)) return true; and ship a correctness bug. The filter can only be used to skip work on the negative branch. On the positive branch it must always fall through to the authoritative store.
4. False positive rate is a function of bits per key and k
You buy accuracy with memory
Three parameters interact: m (bits), n (keys inserted), and k (hashes). For a given m/n ratio there is an optimal k, and pushing the error rate down costs bits per key on a curve with sharply diminishing returns.
The practical shape: each additional order of magnitude of accuracy costs roughly a constant number of extra bits per key. Going from a loose filter to a tight one is cheap at first and expensive at the end. Size for the n you actually expect - the rate is only what you designed for if n stays at or below your assumption.
⚠️ In production — The failure is silent. Insert twice the keys you sized for and nothing errors - the filter just fills up and the false positive rate climbs until nearly every query returns MAYBE, at which point you are paying memory for a structure that no longer filters anything. Track the fill ratio (fraction of bits set), not just the insert count.
5. Deletion is not supported, and clearing bits corrupts the filter
Unsetting a bit erases other keys too
You cannot remove a key by clearing its k bits, because those bits are almost certainly shared with other keys. Clearing them would make the filter report DEFINITELY_NOT for keys that are actually present, breaking the one guarantee the structure offers.
The variants that support removal change the shape of the data. A counting Bloom filter replaces each bit with a small counter, incremented on add and decremented on remove, at several times the memory. A cuckoo filter stores short fingerprints in buckets and supports deletion directly, at the cost of a more complex insert path that can fail when the table is full.
⚠️ In production — "We'll just add deletes later" is the most common design regret here. Retrofitting deletion means changing the on-disk format and the memory budget, so decide up front whether your key set is append-only. If it is not, look at cuckoo filters before you commit.
6. Rebuilds handle churn, and the swap has to be atomic
Regenerate from source, then hot-swap
The standard answer to a changing key set is to build a fresh filter from the source of truth and swap it in. Storage engines do this naturally: each immutable file gets its own filter built at write time, and the filter dies with the file.
For a long-lived service, build the new filter off to the side and replace the pointer in one operation. If you mutate a live filter in place while queries read it, readers can observe a half-built filter, which reports DEFINITELY_NOT for keys that exist.
⚠️ In production — Rebuild cost scales with the full key set, not with the number of changes. A filter that needs a full rebuild every few minutes because keys churn constantly is a sign you picked the wrong structure - the rebuild becomes the dominant cost, and a cache with TTLs is usually the better answer.
7. The filter only pays off when misses are common and expensive
Savings come from the negative path
The value is (miss rate) x (cost of a miss) minus the false positive leakage. If 90% of your queries are for keys that do not exist and each miss costs a disk seek, the filter removes most of that work. If 95% of your queries hit, the filter adds hash computations to nearly every request and saves almost nothing.
Measure your miss rate before you build anything. It is the single number that decides whether this structure is worth its complexity.
⚠️ In production — The filter itself has to be in memory and hot to help. A filter large enough to be paged out, or one fetched over the network per query, can cost more than the lookup it was meant to avoid - at which point you have added a data structure and made the system slower.
## Where You Meet It
- An LSM-tree storage engine keeps data in many immutable sorted files on disk. Without a filter, a read for a missing key touches every file in a level. Each file carries a Bloom filter built at write time, so the engine skips files that definitely do not contain the key and usually reads only one. This is the canonical production use, and it is why read amplification on missing keys stays bounded as the number of files grows.
- A CDN edge node needs to decide whether an object is worth caching. Caching every one-hit object thrashes the cache with content nobody requests twice. The node keeps a Bloom filter of recently seen request keys and only admits an object to the cache on the second sighting, so single-request objects never take up space. False positives admit a small number of one-hit objects, which costs a cache slot and nothing else.
- A username registration service checks availability on every keystroke. Nearly all candidate names are free, so nearly all queries are misses against a large table. A Bloom filter of taken names in the application process answers most of them without touching the database; the small fraction of false positives just triggers the real query, which returns "available" and corrects the answer. The user never sees a wrong result.
- A crawler must avoid re-fetching URLs it has already visited. The visited set grows into the hundreds of millions and no longer fits comfortably in a hash set per worker. A Bloom filter holds it in a few hundred megabytes; a false positive means one URL is silently skipped. That is acceptable for a crawler and unacceptable for anything that has to be complete - which is exactly the design conversation to have before adopting it.
- A distributed database replicates writes between regions and wants to avoid shipping keys the peer already holds. Each side sends a Bloom filter of its key set instead of the keys, and the peer uses it to filter what it sends back. False positives mean a few keys are not sent that should have been, so the protocol runs a second exact pass over a much smaller candidate set.
When You Actually Need It
- Your miss rate is high - most queries are for keys that do not exist - and you can prove it from metrics, not intuition.
- The lookup behind the filter is genuinely expensive: a disk seek, a network round trip, a cross-region call, or a query that takes locks.
- The key set is too large to hold exactly in memory, but a few bits per key would fit comfortably.
- A false positive is harmless in your system - it costs one wasted real lookup and nothing else. If it can cause a wrong user-visible answer, stop here.
- The key set is append-only, or it is cheap to rebuild the filter from the source of truth on a schedule you control.
- You need to send set membership over the network, and shipping the actual keys would be prohibitively large.
When You Don't
- The whole key set fits in a hash set. Below roughly a million small keys you are usually talking about tens of megabytes for an exact
HashSetordict- which is exact, supports deletion, and needs no tuning. Use it. A Bloom filter at this scale buys you a modest memory saving and a class of correctness bug you did not have before. - Your traffic is mostly hits. If lookups usually find the key, the filter says MAYBE nearly every time and you pay k hashes per request to skip almost no work. Put an LRU cache in front instead - it accelerates the hits, which is where your traffic actually is.
- A false positive can produce a wrong answer. "Have I already charged this card?", "is this user authorised?", "has this message been delivered?" - if the MAYBE branch is treated as yes, you get silent, unreproducible incorrectness. Use an exact index, or use the filter only as a hint that always falls through to a real check.
- You need to delete keys. A standard Bloom filter cannot remove anything. If your set shrinks, use a cuckoo filter, a counting Bloom filter with the memory overhead priced in, or an exact set with TTLs - do not clear bits.
- The set churns faster than you can rebuild. If keys expire in minutes and the rebuild takes minutes, the rebuild is the system. A cache with per-key TTLs models expiry directly and is simpler to reason about.
- The backing store already filters cheaply. If your database keeps its own index in memory and a miss is a hash lookup on a warm page, you are adding a structure in front of something already fast. Measure the miss path first; if it is not slow, there is nothing to save.
What People Get Wrong
"Bloom filters can give false negatives too, so they're just approximate."
The absent answer is exact. If any of the k bits is 0, the key was never inserted - insertion always sets those bits, and standard Bloom filters never clear them. False negatives only appear if you break the invariant by clearing bits to fake deletion, or by querying a filter that is still being built.
"It's a compressed set - we can use it to store the key list compactly."
It stores no keys at all. You cannot iterate it, dump it, or recover a key from it. It answers membership queries about candidates you already have in hand; if you need to know what is in the set, this is the wrong structure.
"Bloom filters make lookups faster."
They make misses faster and hits slightly slower. Every hit now pays k hash computations plus the original lookup. The net gain is entirely determined by your miss ratio - on a hit-heavy workload the filter is pure overhead.
"Just size it generously and you never have to think about it again."
The false positive rate is a function of how many keys you actually inserted. Oversizing buys headroom, not immunity - past your design n the rate degrades continuously and silently, with no error and no log line. Monitor the fill ratio or you will discover it as a latency regression months later.
Why It Was Built This Way
The design starts from a hard constraint: memory is far smaller than the key set, and the keys themselves are the expensive part. Any structure that stores keys - a hash set, a tree, a sorted array - costs at least the size of the data. Once you accept that you cannot afford the keys, the only thing left to store is evidence that a key was seen, and the cheapest possible evidence is a single bit.
One bit per key would be a perfect hash, which you cannot build without knowing the key set in advance. So the design gives up on assigning each key its own bit and lets keys share bits. Sharing is what makes the structure small, and it is also precisely what creates false positives: a key's bits can all be set by other keys that happen to hash there. The k-hash trick is the mitigation - requiring several independent bits to be simultaneously set makes an accidental collision on all of them much less likely than a collision on any one.
What was traded away is symmetry. The structure is deliberately one-sided: it is exact in the negative direction and approximate in the positive direction, because setting bits is monotone and never reversible. That single choice explains everything else. It explains why deletion is impossible - you cannot un-share a bit. It explains why the filter degrades silently rather than failing - adding keys only ever adds ones, and a saturated filter is a valid filter that answers MAYBE to everything. And it explains where the structure belongs: in front of an expensive lookup that can confirm the MAYBE, never as the final authority on anything.
Related Briefs
What to Read Next
- cuckoo filter vs bloom filter
- LSM tree read path and SSTable indexes
- HyperLogLog for cardinality estimation
- consistent hashing
A Bloom filter is worth adding when you have measured a high miss rate against an expensive backing store, and when a false positive costs you one wasted lookup rather than a wrong answer. It is not a cache and not a set - it is a guard on the negative path, and every MAYBE must still reach the real store. If your key set fits in a hash set, or your traffic mostly hits, the simple option is the correct one.
댓글
댓글 쓰기