Bloom Filters: Just Say No

You’ve just thought of an awesome project which is going to make you millions, the next big thing. But there’s just one issue: to implement your idea, you need a way to efficiently answer the question, “Have I seen this item before?”

The first thought that comes to your mind is likely a HashSet or a HashMap. Both give you the answer in near constant time. Problem solved, right?

Not exactly. This would’ve worked if we were building a project just for a small group of people, but this is a project which is going to serve millions of users (and make millions of dollars). The real constraint here is memory. If we were to store all the parsed data in memory, the millions you were about to earn would quickly vanish into paying server bills, and the performance would degrade significantly.

So what do we do now? Can we think of a way to figure out if we have seen something quickly, without storing all the past items, while accepting a small percentage of error?

The Black Box

This is where Bloom filters come into the picture. Consider the Bloom filter as a black box where you want to check if you’ve seen something in the past. The Bloom filter does some magic (aka maths), and spits out “No” or “Maybe”.

Did you notice it didn’t say “Yes”? This is the small error percentage we discussed earlier. If the Bloom filter says “No”, you surely haven’t seen the item. If it says “Maybe”, there is a high chance you’ve seen the item, but it can’t say it with a 100% guarantee. In that case, you just go to the database to check if the item is actually present.

Now you might think, how exactly is it helping if we have to go to the database anyway to verify, and we’re just adding a new operation in between? It turns out this operation drastically improves our average response time because the 'magic' ensures the number of false positives is extremely low, saving countless unnecessary database trips.

Making the Black Box Transparent

Let's see how it actually works by making the black box transparent.

Let’s say we are expecting to remember 1,000 items. We create an array of bits of size 16, and we define 3 hash functions. Each function takes an input and returns a specific index. Because they are deterministic, passing the same input will always return the exact same numbers.

Before we add “AskMaddyy” to our database, we run it through the 3 functions. Let's say it returns 2, 5, and 6. We check our bit array, and at indexes 2, 5, and 6, we set the value to 1. If the previous value was 0 it becomes 1; if it was already 1, it remains unchanged.

Now your database consists of just one element, “AskMaddyy”, and the array looks like the one above. Now, you’re asked: Have you seen “AskMaddyy2”?

You pass it through the hash functions. There are two scenarios we can encounter. Let’s look at them one by one.

Scenario 1: Definite NO

Let's say you get values 2, 6, and 11 from the three hash functions. You check the array and see the value at index 11 is 0. If “AskMaddyy2” was already inserted into the database, the functions guarantee they would return the same output, meaning index 11 should’ve been set to 1. Since it’s 0, we can say with absolute certainty that AskMaddyy2 is not present, completely avoiding a database query.

Scenario 2: False Positive (Maybe)

Coming to the second scenario, let’s say the functions returned the values 2, 5, and 6 for “AskMaddyy2”. We check the array and see all those bits are already 1. Because of this collision, the Bloom filter can’t confidently say the element doesn’t exist.

So, we search through the actual database. We see that “AskMaddyy2” doesn’t exist there, and hence we finally return false. This is a false positive.

The Optimal Formula

As you can see, the hash functions we choose play a very important role. They should distribute numbers equally across the array to avoid too many collisions. Similarly, the size of the bits array is crucial; if we use a small array for millions of elements, it will quickly fill up with 1s, and every future call will result in a 'Maybe' (forcing a database trip).

Mathematicians have figured out the exact formula for optimal sizing. You don’t need to memorize this, but for the curious minds, here is how you find the optimal configuration:

• N is the expected number of items in your Database.
• M is the optimal size of the bits array.
• K is the optimal number of hash functions.
• P is the acceptable false positive probability (e.g., 0.01 for 1%).

Why Deletion is Impossible

Did you notice one important limitation? Deletion from a standard Bloom filter is impossible! Go ahead, think about why that might be.

Consider this as the starting point of a Bloom filter where the database already has 10 elements.

Let’s say you want to add “Madhav teaches System Design”. The 3 functions bring out values 1, 5, and 15. You set those indexes to 1 in the bit array and add the element to the database. The bloom filter now looks like this:

Now, imagine for some reason you wanted to delete that element. You hash it again, get 1, 5, and 15, and decide to set those bits back to 0. But wait, indexes 5 and 15 were already set to 1 before we even added this new element! They belonged to other items.

If you blindly set them to 0, the filter becomes inconsistent. If someone later searches for the original items that relied on bits 5 and 15, the filter will see a 0 and incorrectly return 'No'. This is why we don’t allow deletion in a standard Bloom filter.

Real World Examples

You’ve now figured out how to design a system that can definitively say 'No', saving huge amounts of processing time. This exact concept is used everywhere in modern systems.

Have you ever tried to set your Instagram username to “cooldude6969”, and instantly seen a 'Username is taken' message? With billions of users, checking the database for every keystroke would be disastrous. Instead, Instagram uses a Bloom filter. If the filter returns “No”, the username is instantly available. If it says “Maybe”, only then does it make a quick trip to the database.

The exact same technology is used by Google when you’re choosing your email (I know you regret choosing your current email, so do I). It's also used by web browsers to quickly check if a URL is malicious without downloading a massive database of bad URLs.

To no one’s surprise, Bloom filters helped pioneers build massive, fast systems by simply giving them the power to say a firm NO.