Bloom Filters

Metadata

1. Overview

What problem does it solve?

If you have a database with 1 billion registered usernames, and a new user tries to register user123, how do you check if user123 is already taken?

1. Query the DB? That requires an expensive disk read for every single registration attempt.
2. Load all 1 billion names into a RAM Hash Map? That would take roughly 20–50 Gigabytes of RAM just to store strings.

A Bloom Filter is a probabilistic data structure that solves this. It can store 1 billion items using roughly 1 Gigabyte of memory (a 95%+ space saving).

However, it makes a trade-off: It can tell you with 100% certainty that an item is NOT in the set, but it can only tell you with high probability that an item IS in the set.

What breaks without it?

• Ghost Cache Misses: Without a Bloom Filter, a CDN or database will go to disk to look for a file that doesn't exist, wasting precious disk I/O.
• Out of Memory: Trying to keep track of massive sets (like "every malicious IP address in the world" or "every URL crawled by Google") in RAM using standard data structures will crash your servers.

2. Motivation

The Power of "Definitely Not"

In 1970, Burton Howard Bloom invented this structure to handle the spell-checking problem. A dictionary had 500,000 words. Memory in 1970 was measured in Kilobytes.

Instead of storing the actual words, Bloom realized you just need to set bits in an array to 1. If a user searches for a word, and the Bloom Filter says "Definitely Not", you can instantly return a 404 Not Found without ever touching the hard drive. If the Bloom Filter says "Probably Yes", then you do the slow disk read to verify.

Since most database queries for non-existent items are a massive waste of resources, eliminating them at the RAM layer provides an incredible speed boost.

3. Real-World Usage

4. Prerequisites

5. Visual Explanation

How it Works (Inserting and Checking)

A Bloom Filter is just a giant array of bits (0s and 1s), initially all set to 0. You also select K different, fast hash functions (e.g., K=3).

1. Inserting "apple" Pass "apple" through the 3 hash functions. Get the modulo of the array size.

• Hash1("apple") % 10 = 2
• Hash2("apple") % 10 = 5
• Hash3("apple") % 10 = 7 Turn bits 2, 5, and 7 to 1.

[ 0, 0, 1, 0, 0, 1, 0, 1, 0, 0 ]
        ^        ^     ^

2. Checking "banana" (Definitely Not)

• Hash1("banana") % 10 = 2 (Bit 2 is 1)
• Hash2("banana") % 10 = 8 (Bit 8 is 0) -> STOP! Because Bit 8 is 0, "banana" was definitely not inserted.

3. Checking "grape" (False Positive)

• Hash1("grape") % 10 = 5 (Bit 5 is 1)
• Hash2("grape") % 10 = 7 (Bit 7 is 1)
• Hash3("grape") % 10 = 2 (Bit 2 is 1) All bits are 1! The filter says "Probably Yes". But wait, we never inserted "grape"! The bits were set by "apple". This is a False Positive.

6. Internal Working

6.1 Sizing the Filter

The math behind Bloom Filters is beautiful because you can perfectly predict the false positive rate. You need to know two things in advance:

1. N: How many items you expect to insert (e.g., 1 Million).
2. P: Your acceptable false positive rate (e.g., 1% or 0.01).

Using these, you can calculate:

• M: The size of the bit array required (Memory).
• K: The optimal number of hash functions to run.

To store 1 Million items with a 1% false positive rate:

• You need M = 9,585,058 bits (Only 1.14 Megabytes!)
• You need K = 7 hash functions.

6.2 Why you can't DELETE

You cannot remove an item from a standard Bloom Filter. If you try to delete "apple" by flipping bits 2, 5, and 7 back to 0, you might accidentally delete another word (like "grape") that happened to share one of those bits. (If you need deletions, you must use a more complex variant called a Counting Bloom Filter).

7. Implementation

Why Python? Python's bitarray and mmh3 (MurmurHash3) libraries make it easy to write a mathematically accurate Bloom Filter in under 50 lines of code.

"""
015 - Bloom Filter Implementation
Demonstrates how to build a space-efficient probabilistic data structure.
Prerequisites: `pip install bitarray mmh3`
"""
import math
import mmh3
from bitarray import bitarray

class BloomFilter:
    def __init__(self, expected_items: int, false_positive_rate: float):
        """
        Initializes the filter with the optimal array size (M) and 
        number of hash functions (K) based on the expected load.
        """
        self.expected_items = expected_items
        self.fp_rate = false_positive_rate

        # Math formulas to calculate optimal M and K
        self.m = self._get_optimal_m(expected_items, false_positive_rate)
        self.k = self._get_optimal_k(self.m, expected_items)

        # Initialize the bit array with all zeros
        self.bit_array = bitarray(self.m)
        self.bit_array.setall(0)

        print(f"--- Bloom Filter Initialized ---")
        print(f"Expected Items: {expected_items:,}")
        print(f"Target FP Rate: {false_positive_rate * 100:.2f}%")
        print(f"Array Size (M): {self.m:,} bits (~{self.m // 8 // 1024} KB)")
        print(f"Hash Funcs (K): {self.k}\n")

    def _get_optimal_m(self, n, p):
        """ m = -(n * ln(p)) / (ln(2)^2) """
        return int(-(n * math.log(p)) / (math.log(2) ** 2))

    def _get_optimal_k(self, m, n):
        """ k = (m / n) * ln(2) """
        return int((m / n) * math.log(2))

    def add(self, item: str):
        """Hashes the item K times and sets the corresponding bits to 1."""
        for i in range(self.k):
            # mmh3 allows using a 'seed' (i). We use this to simulate K different hash functions.
            digest = mmh3.hash(item, i) % self.m
            self.bit_array[digest] = 1

    def check(self, item: str) -> bool:
        """
        Checks if the item is in the set.
        Returns False if definitely NOT in the set.
        Returns True if PROBABLY in the set.
        """
        for i in range(self.k):
            digest = mmh3.hash(item, i) % self.m
            if self.bit_array[digest] == 0:
                # If even one bit is 0, the item was DEFINITELY NOT added.
                return False
        return True


# ── Simulation ──

if __name__ == "__main__":
    # Create a filter expecting 100,000 items with a 1% false positive rate
    bf = BloomFilter(expected_items=100000, false_positive_rate=0.01)

    print("Adding users to the database: ['alice', 'bob', 'charlie']")
    bf.add("alice")
    bf.add("bob")
    bf.add("charlie")

    print("\n--- Checking Existing Users ---")
    print(f"Is 'alice' registered?   {bf.check('alice')} (Expected: True)")
    print(f"Is 'bob' registered?     {bf.check('bob')} (Expected: True)")

    print("\n--- Checking New Users ---")
    print(f"Is 'david' registered?   {bf.check('david')} (Expected: False - Definitely Not)")
    print(f"Is 'eve' registered?     {bf.check('eve')} (Expected: False - Definitely Not)")

    # ── Forcing a False Positive Demo ──
    print("\n--- Stress Testing for False Positives ---")
    print("Filling filter with 100,000 dummy users...")
    for i in range(100000):
        bf.add(f"dummy_user_{i}")

    # Now we check users that we NEVER added
    false_positives = 0
    test_count = 10000
    for i in range(test_count):
        if bf.check(f"never_added_{i}"):
            false_positives += 1

    actual_fp_rate = (false_positives / test_count) * 100
    print(f"Tested {test_count:,} unregistered users.")
    print(f"False Positives found: {false_positives}")
    print(f"Actual FP Rate: {actual_fp_rate:.2f}% (Target was 1.00%)")

Sample Output

--- Bloom Filter Initialized ---
Expected Items: 100,000
Target FP Rate: 1.00%
Array Size (M): 958,505 bits (~117 KB)
Hash Funcs (K): 6

Adding users to the database: ['alice', 'bob', 'charlie']

--- Checking Existing Users ---
Is 'alice' registered?   True (Expected: True)
Is 'bob' registered?     True (Expected: True)

--- Checking New Users ---
Is 'david' registered?   False (Expected: False - Definitely Not)
Is 'eve' registered?     False (Expected: False - Definitely Not)

--- Stress Testing for False Positives ---
Filling filter with 100,000 dummy users...
Tested 10,000 unregistered users.
False Positives found: 104
Actual FP Rate: 1.04% (Target was 1.00%)

Notice how accurate the math is! We targeted 1%, and under a full 100k load, the actual FP rate is 1.04%. All using just 117 KB of RAM.

8. Complexity

Scalability Characteristics

• Bloom filters do not scale dynamically. If you initialize a filter for 1 Million items and insert 10 Million items, the array fills up with 1s. The False Positive rate will skyrocket to near 100% (everything will return "Probably Yes").
• To scale a Bloom Filter, you must create a new, larger filter and re-hash all existing items into it, or use a Scalable Bloom Filter (an array of Bloom Filters).

9. Trade-offs

10. Production Evolution

11. Common Bugs

12. Interview Questions

1. What is the primary benefit of a Bloom Filter? Hint: Massive memory savings. It allows you to answer "Does this item exist?" in O(1) time without keeping the actual items in memory.

2. Can a Bloom Filter give a False Negative? (i.e., it says the item is NOT there, but it actually is). Hint: No. A Bloom Filter has zero false negatives. If it says "Definitely Not", it is 100% accurate.

3. How does Cassandra (or any LSM-Tree database) use Bloom Filters? Hint: When a read query comes in, Cassandra has to check multiple SSTables on disk. Before reading an SSTable, it checks the in-memory Bloom Filter. If the filter says "Definitely Not", it skips the expensive disk read for that file entirely.

4. Why can't you delete an item from a standard Bloom Filter? Hint: If you flip the item's hashed bits back to 0, you might be flipping bits that are shared by another item, accidentally deleting that item too.

13. Used By (Downstream Blocks)

• 012 CDN — CDNs use Bloom Filters to quickly determine if an asset is cached locally before doing a slow disk lookup.
• 013 Database Indexing — Vital for LSM-Tree performance (Cassandra, LevelDB, RocksDB).

14. Used In (Case Studies)

15. Related Blocks

16. Try It Yourself

Exercise 1: Redis Bloom

If you have Redis installed (with the RedisBloom module), translate the Python script to use Redis commands. Use BF.RESERVE to create the filter, BF.ADD to insert, and BF.EXISTS to check. This is how you implement Bloom Filters in a distributed microservices environment!

Website Metadata