Premium Video

This video is available to premium subscribers only

Unlock Full Access

Large systems spend a surprising amount of time looking for things that are not there.

A Bloom filter lets a system ask a cheap question first: "Can this item possibly exist?" It answers with very little memory, and when the answer is "no," the system can skip an expensive lookup entirely.

In this chapter, we'll learn what a Bloom filter is, how it works, how to size it correctly, and how large-scale systems use it to avoid unnecessary and expensive lookups.

Suppose you're building a sign-up page for an application with one billion users. When someone types a username, you want to tell them right away whether it's already taken.

The simplest approach is to check the database as they type. But with millions of people signing up, this could generate a huge number of database queries.

Another option is to store all existing usernames in an in-memory hash set. But even if each username averages just 20 bytes, one billion usernames would require around 20 GB of memory, not including the extra overhead of the hash set. That's a lot of memory just to answer a simple yes-or-no question.

Now, think about the usernames people try. Many of them are probably available. So a large portion of these database queries simply confirm that a username doesn't exist.

What if we could quickly rule out those usernames without querying the database, and only check the ones we're unsure about?

That's exactly what a Bloom filter helps us do.

A Bloom filter is a space-efficient data structure used to check whether an item belongs to a set.

It supports two basic operations:

When you check an item, the Bloom filter gives one of two answers:

The important thing is that a Bloom filter doesn't store the actual items. Instead, it uses a compact array of bits to keep track of what's been added. This makes it very memory-efficient, but it also means it can't always tell us for certain whether an item exists.

A Bloom filter has two main components:

Let's understand how this works with a simple example. Suppose we have a bit array with 10 positions, numbered from 0 to 9, and we use 3 hash functions.

In a real system, the bit array might contain millions or even billions of bits, but the underlying idea remains the same.

Adding Items

Let's start by adding the username alice. We pass it through our three hash functions, which return positions 1, 4, and 7. We then set the bits at those positions to 1.

Next, let's add another username, dave. This time, the hash functions return positions 2, 5, and 7. We set those bits to 1 as well. Notice that position 7 is already set to 1, so we simply leave it unchanged.

After adding both usernames, our bit array has ones at positions 1, 2, 4, 5, and 7. We haven't stored the actual usernames anywhere in the Bloom filter, just a few bits representing them.

Checking an Item

Now suppose someone tries the username bob. We pass it through the same three hash functions, which return positions 0, 4, and 8. We then check the bits at those positions.

Position 4 is set to 1, but positions 0 and 8 are still 0.

This tells us something important. If bob had been added to the Bloom filter, all three positions would have been set to 1. Since at least one of them is 0, we know for certain that bob was never added.

Assuming the filter is up to date, we can tell the user that the username is available without even querying the database.

To summarize the two operations:

Now suppose someone tries the username carol. We pass it through the same three hash functions, which return positions 1, 2, and 5. We then check the bits at those positions.

Position 1 was set by alice, while positions 2 and 5 were set by dave. All three bits are set to 1, so the Bloom filter tells us that carol might already exist.

But here's the interesting part. We never actually added carol to the filter. This is called a false positive. The Bloom filter can't tell whether those bits were set by carol or by a combination of other usernames.

For our username availability check, that's fine. Whenever the filter says "possibly," we simply query the database to confirm whether the username exists. This way, we only need to query the database when we're unsure.

In general, a false positive is safe when it only causes extra work, not a wrong decision.

Safe uses:

Risky uses:

The opposite mistake, however, cannot happen. A Bloom filter never says "definitely not" for an item that was actually added.

That's because whenever we add an item, we set all of its corresponding bits to 1. And in a standard Bloom filter, bits only change from 0 to 1. They never go back to 0. So any item we've added will always have all of its bits set to 1.

This guarantee is what makes Bloom filters so useful. When the filter says an item doesn't exist, we can trust that answer and safely skip the database lookup. But when it says an item might exist, we need to verify it if we want to be certain.

How often does a Bloom filter return false positives? That depends on three things:

As we add more items, more bits get set to 1. And the more bits that are set, the more likely it is that a new item will find all its positions already set, even if it was never added. So if the filter is too small for the number of items, it fills up quickly and starts returning "possibly" for almost every check.

A useful way to understand this is to look at the number of bits per item. With around 10 bits per item and a well-chosen number of hash functions, the false positive rate is about 1%. Increase that to 15 bits per item, and the rate drops to roughly 1 in 1,000.

As a general rule, every additional 5 bits per item reduces the false positive rate by about 10 times.

If you want to calculate the size yourself, these are the standard formulas, where p is the target false positive rate:

Choosing the number of hash functions also involves a trade-off.

So we need to find the right balance based on how many bits we have per item. For a false positive rate of around 1%, the optimal number is roughly 7 hash functions, assuming the bit array is sized appropriately.

Fortunately, we don't usually need to figure this out ourselves. Most Bloom filter libraries let us specify the expected number of items and the desired false positive rate. They then calculate the appropriate bit array size and number of hash functions.

The hash functions should be fast and distribute values evenly, but they don't need to be cryptographically secure. That's why algorithms like MurmurHash are commonly used.

A few practical notes:

Let's return to our example with one billion usernames. Storing all of them in a hash set would require at least 20 GB of memory.

But a Bloom filter with a 1% false positive rate needs only about 10 bits per username. For one billion usernames, that's roughly 1.2 GB:

Another advantage is that the filter's size doesn't depend on the length of each item. So a long URL takes up the same 10 bits as a short username.

With such a small memory footprint, we can keep a copy of the filter on every application server. Most username availability checks can then be handled locally in memory, without touching the database. And for usernames that are actually available, only about 1 in 100 will trigger an unnecessary database query.

This implementation uses a small FNV-1a hash function and double hashing.

It is meant for learning. In production, use a well-tested library with strong hashing, serialization support, and clear sizing controls.

Expected output:

The False result for user:999 is common while the filter is still fairly empty. As the filter gets closer to its planned capacity, some missing items will return True.

Bloom filters have one important limitation: you cannot remove items once they've been added.

Suppose the account alice is deleted, and we want to remove its username from the filter. We might try setting its bits at positions 1, 4, and 7 back to 0.

But remember, position 7 is also used by dave. If we clear that bit, the filter would now tell us that dave is definitely not in the set, even though we added it earlier.

This is called a false negative, and it breaks the most important guarantee of a Bloom filter.

That's why a standard Bloom filter only supports adding items, not removing them. If your data changes frequently, you can either rebuild the filter periodically or use a different variant that supports deletion.

One such variant is the counting Bloom filter. Instead of storing a single bit at each position, it uses a small counter.

After adding alice and dave, position 7 holds a count of 2:

So if we remove alice, the counter at position 7 goes from 2 to 1, and dave can still be found:

The trade-off is memory usage. Each counter typically uses 4 bits instead of 1, making the filter about four times larger.

We also need to be careful to remove only items that were actually added. Otherwise, we could decrement the wrong counters and introduce false negatives.

For applications where items are frequently added and removed, cuckoo filters are another option, and they can often use less memory. Instead of setting shared bits, a cuckoo filter stores a short fingerprint of each item, so it can delete an item by removing its fingerprint.

Another limitation is that a Bloom filter has a fixed size, which we choose when creating it.

Suppose we design a filter for 100 million items, but the set eventually grows to 300 million. As more items are added, the array fills up with ones, and the false positive rate increases sharply.

Unfortunately, we can't simply resize the filter. Since it doesn't store the original items, there's nothing to rehash into a larger array.

There are two common options:

RedisBloom works this way. You reserve a filter with a target error rate and capacity, and it adds sub-filters as the capacity is reached:

Sizing the filter well up front is still cheaper than relying on extra sub-filters.

One of the most common uses of Bloom filters is inside databases.

Storage engines like Cassandra, HBase, and RocksDB store data across many immutable files on disk. When we look up a key, it could be present in any of those files. Checking every file would require multiple disk reads, many of which would find nothing.

To avoid this, each file can have a Bloom filter that tracks the keys it contains, and that filter is kept in memory. Before reading a file, the database first checks its Bloom filter. If the filter says the key is definitely not there, the database can skip that file entirely.

This way, many unnecessary disk reads are replaced with fast in-memory checks. It helps most for keys that don't exist, which would otherwise mean reading every file.

Cassandra even lets us configure the target false positive rate for each table, using the bloom_filter_fp_chance setting. A lower rate uses more memory.

Bloom filters are also useful in caching.

Skipping One-Hit Wonders

Akamai, one of the largest CDNs, found that many objects requested from its servers were only requested once. Caching these objects wasted disk space and pushed out more popular objects that users might request again.

To avoid this, they used a Bloom filter to track which objects had been requested recently:

This helps prevent one-time requests from filling up the cache.

Preventing Cache Penetration

Bloom filters can also help prevent a problem called cache penetration. This happens when many requests ask for keys that don't exist. Each request misses the cache and ends up hitting the database, creating unnecessary load.

By maintaining a Bloom filter of all valid keys, the system can quickly reject requests for keys that definitely don't exist, without querying the database.

The filter has to be updated whenever a new valid key is created. Otherwise, it would reject requests for real items.

Bloom filters also have a useful property in distributed systems.

Suppose we have two servers, each maintaining a Bloom filter for its own data. If both filters use the same bit array size and the same hash functions, we can combine them using a bitwise OR operation:

The result is exactly what we would get if we had added all the items from both servers into a single Bloom filter.

This makes it easy to merge filters created by different servers, without having to process the original data again. It also allows us to send a compact summary of a large dataset over the network, rather than transferring all the individual keys.

Bloom filters work best when most lookups are for items that don't exist in the set, and when we can perform a slower, exact check if the filter says an item might exist.

However, they're not suitable for every situation.

Bloom Filters vs Related Structures

Bloom filters are part of a larger family of compact data structures. The easiest way to choose the right one is to ask what question the system needs answered.

Use a Bloom filter when you need a compact membership check. Use HyperLogLog for distinct counts. Use Count-Min Sketch for frequencies.

A Bloom filter uses a compact bit array and a set of hash functions to check whether an item might exist.

When we add an item, we set a few bits to 1. When we check an item, we look at those same bits. If even one bit is 0, the item is definitely not in the set. But if all the bits are 1, the item might be in the set.

This small chance of false positives allows Bloom filters to save a significant amount of memory, using only about 10 bits per item for a 1% false positive rate.

Standard Bloom filters don't support deleting items or resizing, but variants like counting and scalable Bloom filters help address these limitations.