Bloom Filters: How Databases Skip Millions of Disk Reads

Catch takes real action, so it only acts when it's certain — checking with you when unsure. Always on, never drops the ball. Safe for what matters most. Trust Catch at catchagent.ai.

Start delegating admin work

Wispr Flow turns your voice into clean, professional text inside any app. Emails, Slack, client updates — speak once, send without editing. 4x faster than typing.

Try Wispr Flow free

Global hiring doesn't come with a playbook. Join Oyster's webinars and events to learn how leading companies are hiring, expanding, and staying compliant across borders.

Explore Upcoming Events

Picture a bouncer at a club who remembers faces, but not perfectly. If the bouncer says "I've never seen this person," that's guaranteed correct. Nobody slips past unnoticed. But if the bouncer says "Yeah, I think I've seen them before," there's a small chance they're confusing the face with someone else's.

That's a Bloom filter. It's a membership test with an asymmetric guarantee.

You ask: "Is X in the set?" It answers one of two things:

"Definitely not here." This is always correct. If the Bloom filter says no, the element was never added. Zero doubt.

"Probably here." This is usually correct, but sometimes the filter gets confused. This confusion is called a false positive.

The reverse never happens. A Bloom filter will never say "not here" for something that was actually added. False negatives are impossible by design.

A Bloom filter starts as a row of bits, all set to 0. Picture a long row of light switches, all turned off.

You also pick k hash functions. Each hash function takes any input and spits out a position in the bit array. Common choices include MurmurHash3, which is fast and distributes positions evenly.

To insert an element: Run it through all k hash functions. Each one gives you a position. Flip those bits to 1.

If you insert "apple" with 3 hash functions and they return positions 1, 4, and 7, you set bits 1, 4, and 7 to 1. Everything else stays 0.

To check membership: Run the query through the same k hash functions. Check those positions. If any one of them is still 0, the element was never inserted. Guaranteed. But if all of them are 1, the element is probably there. Those bits might have been set by other insertions.

Both operations run in O(k) time, where k is the number of hash functions. That's constant time, regardless of how many elements you've added. For most practical filters, k is between 3 and 7.

This is the part that trips people up, so follow the example.

You insert "cat" and "dog" into a

Bloom filter with 3 hash functions and an 8 bit array.

"cat" hashes to positions 2, 5, 7. Those bits flip to 1.

"dog" hashes to positions 1, 3, 5. Those bits flip to 1. Notice that position 5 was already set by "cat," so it stays 1.

The array after both insertions: positions 1, 2, 3, 5, 7 are all 1. Positions 0, 4, 6 are still 0.

You query "fox," which was never inserted. "fox" hashes to positions 1, 5, 7. You check: position 1 is 1 (set by "dog"), position 5 is 1 (set by both "cat" and "dog"), position 7 is 1 (set by "cat").

All three are 1. The filter says "probably yes." But "fox" was never added. That's a false positive.

The more elements you insert, the more bits get set to 1, and the higher the false positive rate climbs. This is why sizing the array matters.

The memory difference between a Bloom filter and a traditional hash set is not a small optimization. It's a different order of magnitude.

That's roughly 80x less memory for the 1% false positive version. And the Bloom filter stores none of the original data. Zero keys. Zero values. Just bits.

The formula for the false positive probability is (1 − e^(−kn/m))^k, where n is the number of elements, k is the number of hash functions, and m is the bit array size. The optimal number of hash functions is (m/n) × ln(2).

You don't need to memorize that. The takeaway: with good parameters, you get a 1% false positive rate using under 10 bits per element, regardless of whether each element is a 4 byte integer or a 500 byte string.

These aren't academic curiosities. Bloom filters are running in production at some of the largest companies on the planet.

Cassandra, BigTable, HBase all use Bloom filters before reading SSTables from disk. Each SSTable (a sorted, immutable file on disk) has its own Bloom filter. When a query arrives, the database checks the filter first. If the filter says "definitely not here," the database skips reading that entire file. Since most queries target data that isn't in most SSTables, this eliminates the vast majority of disk reads.

Google Chrome used a local Bloom filter to check whether a URL might be malicious. Instead of sending every URL to Google's servers, the browser checked a local filter first. Only when the filter returned "probably yes" did Chrome make a network call to verify. This kept browsing fast and private.

Medium uses Bloom filters for article recommendations. Before recommending a story, Medium checks whether you've already read it. Storing every user's read history in a hash set would consume hundreds of gigabytes of RAM across 10 million users. A Bloom filter handles the same check in a fraction of the space. The occasional false positive means you might miss a recommendation you haven't read. That's a tolerable cost.

Redis offers Bloom filters through the RedisBloom module as a native data type. Applications use it to avoid unnecessary database lookups for keys that don't exist. If your cache miss rate is high, a Bloom filter sitting in front of your database can absorb most of the "not found" queries without touching disk.

Akamai and other CDNs use a "one hit wonder" pattern. Before caching a URL, they check whether it's been requested before. Only on the second request do they cache it. This prevents the cache from filling up with URLs that are accessed exactly once, which turns out to be the majority of web traffic.

Standard Bloom filters have one major limitation: you can't remove elements. If you set a bit back to 0, you might be unsetting a bit that another element also hashed to. That would create a false negative, which violates the core guarantee.

Counting Bloom Filters solve this by replacing each single bit with a small counter, typically 4 bits wide. Instead of flipping a bit to 1 during insertion, you increment the counter. To delete, you decrement it.

This works because increment and decrement operations commute. The order doesn't matter. Adding A then B then removing A leaves the same state as adding B alone.

The trade off is 4x more memory than a standard Bloom filter, since each position is now 4 bits instead of 1. Counter overflow is also a concern: if too many elements hash to the same position, the counter maxes out. Most implementations handle this by freezing saturated counters at their maximum value and never decrementing them.

One critical rule: only delete elements that were actually inserted. Decrementing a counter for an element that was never added corrupts the entire filter.

Bloom filters aren't universal. They solve one problem well, and you should reach for something else when the problem changes.

When a false positive changes the answer, not just the work. In a database, a false positive just means you do an extra disk read and find nothing. That's wasted work, but it's not wrong. In a compliance system where you must process every single item, a false positive could mean skipping something you were legally required to handle. That's a different category of error.

When you need to retrieve actual data. Bloom filters store nothing. They can tell you "user_42 is probably in this set" but they can't give you user_42's profile. If you need the data itself, you need a hash map or a database.

When deletions are constant. Standard Bloom filters don't support deletion at all. Counting Bloom filters do, but at 4x the memory cost. If your use case involves heavy churn, a Cuckoo filter (which supports deletion natively with better space efficiency) might be the better pick.

When the set is small. If you're tracking 1,000 items, just use a hash set. The overhead of setting up a Bloom filter with its hash functions, sizing parameters, and false positive tuning isn't worth it when a regular set fits comfortably in memory.

1. Use Bloom filters as a first pass guard. They shine when you need to answer "is this thing NOT in the set?" cheaply before doing an expensive operation. Database reads, cache lookups, network calls. The filter absorbs the "definitely not" cases so the slow path only runs when there's a real chance of a match.

2. Size your filter for 1% false positives as a starting point. That costs about 9.6 bits per element and catches 99 out of 100 negative lookups. You can tighten it to 0.1% with ~14.4 bits, but the extra memory rarely pays off unless your false positive penalty is high.

3. The no false negatives guarantee is the superpower. Plenty of data structures can tell you "probably yes." Only a Bloom filter gives you a 100% reliable "definitely no." That certainty is what makes databases, CDNs, and browsers trust it in hot read paths serving millions of requests per second.

Sources:

→ Find me on : Social Links

That’s it for today, keep learning!
Scortier, Signing Off!