Nimendra's Notes 🪴

Bloom Filters

5 min read

systemdesign database/databaseengineering

What is a Bloom Filters

A Bloom Filter is a space-efficient, probabilistic data structure used to quickly test whether an element is possibly in a set or definitely not.

Set and Maps

A set is and unordered group of (Unique) items(called elements).
It supports,

  • Adding an item
  • Removing an item
  • Checking if an item exists
fruits : {"apple", "banana", "mango"}

A Map is a collection of key-value pairs. Each key is unique, and it maps to some value.

  • Use a Set when you care only about whether something exists.
  • Use a Map when you need to associate data with keys.

The core idea is simple yet powerful. Rather than storing the actual elements, a Bloom filter keeps only hashed representations of the elements inside a compact bit array. This sacrifices some precision but delivers outstanding space efficiency and fast query times. For example, a typical Bloom filter with a 1% error rate requires just about 9.6 bits per element—regardless of the size of the elements themselves. That’s a significant improvement over traditional data structures like hash tables or hash sets, which must store the full data items.

Bloom filters may report false positives — claiming an element is present when it isn’t — but they never report false negatives. This makes them extremely reliable for exclusion queries. This property has made Bloom filters invaluable in a wide range of applications, from web caching to database query optimization, where the cost of a false positive is far lower than the cost of missing a true member.

  • Fast & Memory-Efficient: Uses much less space than a traditional set.
    • Bloom filters take significantly less space (became it does not store keys) to hold the information and is very efficient in checking existence.
  • No False Negatives: If it says “not present”, it’s definitely not.
  • Possible False Positives: If it says “present”, the item might be present (but might not be).
    • As number of keys we put in bloom filters increases, the false positivity rate increases.
    • Hence, when # of keys increase we want increase bloom filter size

Info

  • A false positive means the system says “yes, it’s here” when actually it’s not.
  • A false negative means the system says “no, it’s not here” when actually it is.

How It Works

At its core, a Bloom Filter is elegantly simple, consisting of just two components:

  • A bit array (also known as a bit vector, or bucket array) of m bits. This is the backbone of our Bloom Filter.
  • Hash functions. This is where the magic happens. We’ll use a set of k hash functions to map our data into the bit array.
  1. A Bloom Filter uses a bit array and multiple hash functions.
  2. To add an element, it hashes the item with each function and sets the corresponding bits.
  3. To check membership, it hashes the item again and checks those bits:
    • If any bit is 0 → the item is definitely not in the set.
    • If all bits are 1 → the item might be in the set.

Calculate Optimal Size of BF


Use Cases, Advantages and Disadvantages

  • In caching: check the Bloom Filter before querying the database.
    • If the filter says the key doesn’t exist → skip cache/DB lookup.
    • Saves load for keys that are truly missing.
  • Databases (e.g., Cassandra, Bigtable)
  • Network systems (e.g., email spam detection, routing tables)
  • Distributed systems (e.g., membership checking)

Advantages of bloom filter

The advantages of the bloom filter are the following:

  • constant time complexity
  • constant space complexity
  • operations are parallelizable
  • no false negatives
  • enables privacy by not storing actual items

Bloom filter disadvantages

The limitations of the bloom filter are the following:

  • bloom filter doesn’t support the delete operation
  • false positives rate can’t be reduced to zero
  • bloom filter on disk requires random access due to random indices generated by hash functions

Removing an item from the bloom filter is not supported because there is no possibility to identify the bits that should be cleared. There might be other items that map onto the same bits and clearing any of the bits would introduce the possibility of false negatives.

Scaling

When # of keys increases,

  1. We have to re-create bloom filter with larger size and populate (re-ingest) the keys again.
  2. Estimate the max keys can solve this. (Calculate Optimal Size of BF)

Counting Bloom Filters

Why Bloom filters don’t support deletion ?

A standard Bloom filters don’t support deletion.

When you insert multiple items, many of their hash bits can overlap:

Insert "apple" → bits 2, 8, 13 = 1
Insert "banana" → bits 8, 11, 17 = 1

Now, we want to delete “apple”:

  • for this we can reset the bits (2, 8, 17 to 0)
    But 8th bit shared with banana. If you reset it to 0, you’ll break the membership test for “apple” → false negative

Solution: Counting BF

A Counting Bloom Filter is an extension of the Bloom filter that:

Supports insertions
Supports lookups
Supports deletions (unlike standard Bloom filters)

How it Works

  • Uses an array of small counters instead of bits.
  • Each inserted item increments k counters (via k hash functions).
  • Lookup checks if all k counters > 0.
  • Deletion simply decrements those k counters.

More Memory(4 bits per counter vs 1 bit) and CPU usage than standard Bloom Filters.

Backlinks

Graph View