Bloom Filters

A Useful Answer Doesn’t Have to Be an Exact Answer

Imagine a key-value storage engine (like RocksDB or Cassandra) holding data across dozens of immutable on-disk SSTable files. When a user requests user:994812, most SSTables on disk do not contain that key. Checking every file on disk would turn a fast lookup into dozens of slow random reads.

Before touching disk, we ask a tiny in-memory Bloom filter attached to each file: Could this key be in here?

• One 0 bit → Definitely not. Skip the disk read immediately with 100% certainty.
• All 1 bits → Possibly yes. Perform the disk read; 99% of the time the key is genuinely there, and ~1% of the time a false positive costs one ordinary lookup.

How m Bits and k Hashes Work Together

A Bloom filter allocates an array of m bits (all initialized to 0) and k independent, deterministic hash functions mapping keys into 0 .. m - 1:

1. add(item): Compute all k positions for item and set bits[pos] = 1.
2. might_contain(item): Compute the exact same k positions. If any position holds 0, item was never inserted (False). If every position holds 1, return True (“possibly present”).

In our m = 12, k = 3 seeded SHA-256 example:

• Inserting "dog" sets bits [9, 3, 10].
• Inserting "pig" sets bits [8, 9, 1].
• Probing "elk" checks [11, 2, 8] → bits 11 and 2 are 0 → Definitely absent!
• Probing "rat" checks [8, 10, 3] → bit 8 came from "pig", while 10 and 3 came from "dog" → False positive!

Complete Python Implementation

from hashlib import sha256


class BloomFilter:
    def __init__(self, m: int = 12, k: int = 3):
        if type(m) is not int or type(k) is not int or m <= 0 or k <= 0:
            raise ValueError("m and k must be positive integers")
        self.m, self.k = m, k
        self.bits = [0] * m

    def positions(self, item: str):
        for seed in range(self.k):
            data = f"{seed}:{item}".encode()
            number = int.from_bytes(sha256(data).digest()[:8], "big")
            yield number % self.m

    def add(self, item: str) -> None:
        for index in self.positions(item):
            self.bits[index] = 1

    def might_contain(self, item: str) -> bool:
        return all(self.bits[index] for index in self.positions(item))

Choosing m and k Before Filling the Filter

After inserting n distinct items into m bits using k hash functions, the false-positive probability is approximately:

p ≈ (1 − e^(−k · n / m))^k

Given an expected population n and target false-positive rate p (for instance p = 0.01, or 1%):

• Optimal bits: m ≈ −n · ln(p) / (ln 2)² (roughly 9.6 bits per item for a 1% false-positive rate — regardless of how large the keys themselves are!)
• Optimal hash count: k ≈ (m / n) · ln 2 ≈ 7 hashes for a 1% target.

Two Production Traps to Avoid

1. The Shared-Bit Deletion Trap: Clearing bits[8] = 0 to “delete” "pig" silently corrupts "dog" or any other key hashing to index 8, introducing false negatives! If deletions are required, use a Counting Bloom Filter (small integer counters per slot) or a Cuckoo Filter.
2. Unbounded Growth: A fixed-size Bloom filter cannot resize by rehashing keys because it never stored the keys. Size m upfront for peak cardinality, or layer scalable filters across immutable segments.