A Bloom filter answers exactly one question, cheaply, at massive scale: "could this key possibly exist?" It can say "definitely no" with 100% certainty, or "maybe yes — go check for real." It never says "yes" with certainty, and that asymmetry is the entire point of the data structure.
It is not a cache. It doesn't store keys, values, or "the list of things that failed before." It stores nothing but bits — and it's that detail that makes it so compact it can represent membership across tens of millions of keys in a few megabytes of memory.
The Core Mechanism
Setup: a fixed-size bit array (say, 1,000,000 bits, all initialized to 0) plus a small number of independent hash functions (commonly 3–7).
Insert a key (done once, for every valid key that exists — e.g., every real userId in the DB): run the key through each hash function, each one produces an index into the bit array, and set those specific bits to 1.
insert("user_42"):
hash1("user_42") = 3 → bitArray[3] = 1
hash2("user_42") = 57 → bitArray[57] = 1
hash3("user_42") = 910 → bitArray[910] = 1
Do this for every valid key up front. After millions of inserts, the bit array is a dense mix of 1s and 0s — no individual key is retrievable from it. It's a pure Yes/No oracle, not a lookup table.
Check a key (at request time): run it through the same hash functions, and check whether all of the resulting bit positions are currently 1.
check("user_999999"): // never actually inserted
hash1("user_999999") = 3 → bitArray[3] == 1 ✓
hash2("user_999999") = 488 → bitArray[488] == 0 ✗ → STOP. Definitely NOT present.
If any bit is 0, the key is guaranteed absent — reject immediately, never touch the cache or DB. If all bits are 1, the key is "probably present" — but it might be a coincidence of other keys' bits overlapping (a false positive). Proceed to the real cache/DB check to confirm.
False Positives vs. False Negatives
These two failure modes are not symmetric — one is an accepted, tunable trade-off; the other should never structurally happen, and if it does, it's a sign something's broken operationally.
False positives — expected, and the whole trade-off of using this structure
Caused by hash collisions: unrelated keys happen to set an overlapping combination of bits, so a never-inserted key can coincidentally have all its bit positions already 1 from other keys. This gets more likely as the filter fills up (higher load factor). It's mitigated, not eliminated, by sizing the bit array bigger and/or using more hash functions — a direct memory-vs-accuracy trade-off, not a bug.
False negatives — should be structurally impossible, with exactly one real-world exception
Insertion only ever sets bits — it never clears them. So if a key was properly inserted, its bits are guaranteed to stay 1 forever... unless something else clears one of them. The only mechanisms that break this guarantee:
| Cause | Why it happens |
|---|---|
| Naive deletion | Standard Bloom filters don't support deletion — clearing a bit to "remove" key A can silently break key B if B shared that bit position. |
| Counting Bloom Filter overflow | The deletion-capable variant uses small counters instead of single bits (increment on insert, decrement on delete). If a counter is sized too small and overflows/wraps, it can corrupt back to looking empty. |
| Staleness / not re-inserted on write | The filter was built from a DB snapshot, and a new valid key was created afterward but never inserted into the filter. Structurally the filter is fine — this is an operational gap, not a flaw in the structure itself. |
Quick comparison
| False Positive | False Negative | |
|---|---|---|
| Possible by design? | Yes — accepted trade-off | No — only via deletion bugs, overflow, or staleness |
| Consequence | One extra (cheap) real check against cache/DB | A real, existing key gets wrongly rejected |
| Severity | Low — self-correcting, costs one wasted lookup | High — silently drops valid users/data |
Sizing It Correctly
The false-positive rate isn't a fixed property of a Bloom filter — it's something you design for upfront based on three numbers: the bit array size m, the number of hash functions k, and the number of items you expect to insert n. Given a target false-positive rate p, the standard formulas are:
m = -(n * ln(p)) / (ln(2))^2 to get the number of bits you need, and k = (m / n) * ln(2) to get the optimal number of hash functions for that bit array.
As a concrete example, to hold 10 million keys at a 1% false-positive rate, you land on roughly 9.6 million bits (about 1.2 MB) and 7 hash functions — which is the entire appeal of this structure: representing membership across 10 million keys in little more than a megabyte, instead of the hundreds of megabytes a real set of those keys would cost.
Where It Lives (Placement)
A Bloom filter is an in-memory data structure, not a network service — it lives wherever the code that needs to make the "should I even bother checking the cache/DB?" decision is running.
| Location | When to use | Trade-off |
|---|---|---|
| App server memory (most common) | Default choice — checking a local bit array is nanoseconds | Each instance's filter must be independently built/kept in sync |
Cache server (e.g., RedisBloom module, BF.ADD / BF.EXISTS) |
Many app instances, want one shared/consistent filter instead of N copies | Adds a network hop to check — still far cheaper than a DB hit |
| API Gateway / Load Balancer | Rare — only to block abusive/scraping traffic before it reaches any app server at all | Unusual to couple business-logic membership checks into an infra layer |
Cache-Aside vs. Read-Through
Where the check physically goes in your code depends on which caching pattern you're using. In Cache-Aside, the app owns the "check cache → miss → query DB" sequence directly, so the Bloom filter check goes right before the app's own DB call:
if (!bloomFilter.mightContain(userId)) return null; // skip cache AND DB entirely
User user = cache.getIfPresent(userId);
if (user == null) {
user = userRepository.findById(userId);
cache.put(userId, user);
}
In Read-Through, the app only ever makes one call to the cache; the DB-fetch logic is hidden inside the cache's registered loader. So the Bloom filter check has to move inside that loader, since that's the only place a DB call actually happens:
LoadingCache<String, User> cache = Caffeine.newBuilder()
.build(key -> {
if (!bloomFilter.mightContain(key)) return null; // loader skips the DB call
return userRepository.findById(key);
});
The Cold-Start Problem: What Happens on App Restart?
A freshly created Bloom filter starts with every bit at 0. If an app instance restarts and starts serving traffic before its filter is repopulated, mightContain(anyKey) returns false for every key — including real, valid ones. This isn't a tunable false-positive trade-off anymore; it's the filter wrongly rejecting all legitimate traffic, which is worse than not having a Bloom filter at all.
This has to be designed for explicitly:
1. Warm up before accepting traffic
Rebuild the filter from a full scan of valid keys in the DB before the instance passes its readiness check / joins the load balancer rotation:
@PostConstruct
public void warmUpBloomFilter() {
bloomFilter = BloomFilter.create(...);
userRepository.streamAllIds().forEach(bloomFilter::put);
// only now mark this instance ready / healthy
}
2. Persist the filter so you don't rebuild from scratch every time
Serialize the bit array periodically to durable storage (disk, S3, or a shared store), and reload that snapshot on startup instead of re-scanning the whole DB every restart:
bloomFilter.writeTo(outputStream); // periodic snapshot
BloomFilter<String> restored = BloomFilter.readFrom(in, funnel); // on startup
3. Keep it in sync on writes — this is the part that's easy to miss
Every time a new valid key is written to the DB, the filter has to be updated in the same write path, or that new key will be falsely rejected until the next full rebuild:
public User createUser(User user) {
User saved = userRepository.save(user);
bloomFilter.put(saved.getId()); // keep filter in sync, same code path
return saved;
}
If each app instance holds its own independent filter (the common case), a write on Instance A doesn't automatically propagate to Instances B, C, D. There are three common ways to handle that:
| Approach | Mechanism | Trade-off |
|---|---|---|
| Shared filter (RedisBloom) | All instances read/write the same filter over the network | Network hop per check; sync problem disappears entirely |
| Pub/Sub broadcast | Instance A publishes "key X added" to Kafka/Redis pub-sub; every instance updates its own local filter | Local in-memory speed retained; small propagation-delay window |
| Periodic full rebuild | Every instance re-scans the DB on a schedule (e.g., every 10 min) | Simplest; accepts a bounded staleness window by design |
The deeper rule: never let the filter become correctness-critical
The deeper rule underneath all three options is the same: because a cold or desynced filter risks false negatives, treat it as a pure optimization, never as the sole gate standing between a request and a real answer. Track a filterReady flag set only once warm-up completes — before that, fall back to hitting the real cache/DB for every request, accepting the temporary loss of the optimization rather than risking wrongly rejecting valid data.
FAQ
How does a Bloom filter differ from a cache? A cache stores actual values and can answer "yes, here's the data." A Bloom filter stores no data at all — only bits — and can only ever answer "definitely no" or "maybe." It's a filter in front of the real store, not a replacement for one.
Can you delete from a Bloom filter? Not from a standard one — clearing a bit can corrupt other keys sharing it. Use a Counting Bloom Filter (small counters instead of single bits) if deletion is required, and size the counters generously to avoid overflow.
What happens if the filter fills up? The false-positive rate rises as the load factor increases. Size the bit array ahead of time based on expected key count and target false-positive rate, using the sizing formulas above.
What if the app restarts? See the Cold-Start section above — warm up before serving, persist snapshots, and keep multi-instance filters in sync via a shared store or broadcast.
Top comments (0)