Back to blog
·5 min read

Bloom Filters

Bloom Filter is a space efficient probabilistic data structure. You might be thinking probabilistic data structure?? Who is even using these?? Every time you type a username to sign up somewhere, a bloom filter might already be checking it. Well then I hope this got your attention, these are used in a lot of places where we need to be space and resource efficient, let me elaborate.

The function of bloom filters can be summed up in one sentence. It tells you if an item is Definitely Not in the set or Maybe in the set.
This function in bloom filter is useful whenever you are trying to check if a value is definitely not in the set, you might be thinking why don't I just do a look up then? There comes the usefulness of bloom filter. Bloom filters are space efficient as they are just an array of bits, meaning if you do a fast query you would use a DB index which by itself takes space. If you are storing a username let's break this down:

  • 1 char = 1 byte
  • let's assume you have a 50 char limit it would take 50 bytes
  • you are going to store 100,000,000 usernames × 50 bytes ≈ 5GB
  • if you rather use a bloom filter it would take ~220MB

But this comes with a price, your bloom filter might get it wrong 0.01% of the time, it's the cost we are going to pay for the efficiency but it's not too high, it mostly costs you a DB lookup. The lookup cost is O(k) where k is the number of hash functions (will explain what this is below).

Now let's see how this Bloom filter works

Internally bloom filter is an array of bits, if you want to insert a value into the set, the value should go through k hash functions and we will get K values of which indices we will flip to one.

Bloom filter insertion diagram

Hash values if k = 3:

  • hash1(kireeti) = 3
  • hash2(kireeti) = 9
  • hash3(kireeti) = 8

We will flip the bits of 3, 9, 8 in the array, similarly we will insert "Alice".

When you are doing a lookup it should go through the same hash functions, as the bits are already flipped it will say the key maybe present!

Bloom filter lookup diagram

Hash values = 0, 3, 8
We check if the bits are flipped and see that they are not flipped.

When we do the lookup as we see that those bits are not flipped this means the username is Definitely not in the set.

This is the main use case for using bloom filter, to know if a value is Definitely not in the set and we don't need to make a costly DB query. Let's say when we get an unsure answer like maybe present we will just do the DB query then to confirm and return back the response.

The Trade-offs

Ok you might be thinking this is all nice but what's the catch? Right to point, yes the cost you pay here is the probabilistic nature where the filter can give you a wrong result 0.01% of the time. It's fine most of the time as you just need to handle this properly and at most you will do one extra DB call.

Another con is that you cannot delete the value you once inserted, let's say you inserted "Alice" and flipped bits 1, 6, 9. Now if you delete Kireeti and try to revert back 8, 9, 3, here you can observe that 9 is common, if you flip it and try to search for "Alice" the result would come out as Definitely not present, this is why we can't delete an inserted value in the filter (also there is a type of filter called cuckoo filter which can handle this).

Bloom filter deletion problem diagram

One more problem to solve is your bloom filter would be out of date with your DB, mostly you would want to put your bloom filters very close to your users. You compute your bloom filter and store it in a CDN near your users so it would be mostly out of date with your DB, but it is fine as the missed lookups would just cost an extra DB call and you can update your bloom filter every few minutes.

Also one last thing is as your bloom filter gets filled up the accuracy would go down, this is due to collisions between hash values, as even though a value might not have been inserted, their hash values might have been flipped by other values that would result in a maybe present even if it's not. If you're curious about the actual math behind how filter size and number of hash functions affect the false positive rate, the Wikipedia article breaks it down well.

Where are Bloom Filters used?

This bloom filter is widely used everywhere:

  • Google Bigtable, Apache Cassandra, RocksDB — avoid disk lookups for non-existent keys, dramatically reducing I/O
  • Chrome's Safe Browsing — checks malicious URLs locally against a bloom filter before ever querying Google's servers
  • Akamai CDN — prevents one-hit-wonder URLs from being cached by checking if a URL has been seen before

Wherever you need fast membership checks at scale, a bloom filter is likely already working behind the scenes.

Resources

data-structuresbloom-filterssystem-design