What is a Bloom filter, and what real backend problems does it solve?

#What a Bloom Filter Actually Is

A Bloom filter is a probabilistic data structure built to answer one question as cheaply as possible: "have I possibly seen this before?" It trades perfect accuracy for O(1) lookups and a memory footprint that stays flat no matter how many items you insert — a hash set of a billion strings costs gigabytes; a Bloom filter tuned for the same billion items with a 1% false-positive rate costs a couple of bytes per item, and the multiplier doesn't move with string length.

Structurally it's nothing more than a bit array of size m, all zeros to start, plus k independent hash functions. Inserting an item means hashing it k ways and flipping those k bits to 1. Checking membership means hashing the same item the same k ways and asking whether every one of those bits is already set.

That asymmetry is the whole design:

• If any of the k bits is 0, the item is definitely not in the set. No false negatives are possible, ever — this is the guarantee that makes Bloom filters safe to use as a fast pre-check in front of something authoritative.
• If all k bits are 1, the item is probably in the set — "probably" because other insertions could have flipped those same bits purely by coincidence. This is the false positive, and it's the price you pay for the compression.

You can tune the false-positive rate by trading space: more bits per item and more hash functions push the error rate down, at the cost of memory. The two classic formulas an interviewer wants you to at least gesture at are the optimal bit-array size m = -(n · ln p) / (ln 2)² for n expected items and target false-positive rate p, and the optimal hash count k = (m/n) · ln 2. In practice you rarely hand-derive these — libraries compute them from n and p — but knowing that both exist, and that adding items beyond the n you sized for degrades the false-positive rate, is the signal an interviewer is listening for.

One more property matters as much as the false positive: a standard Bloom filter cannot delete. Clearing a bit to "remove" an item could unset a bit another item also depends on, silently turning a true positive into a false negative — which breaks the one guarantee the structure exists to provide. If you need deletion, you reach for a counting Bloom filter (each slot is a small counter instead of a single bit, incremented on insert and decremented on delete) or a newer structure like a Cuckoo filter, which supports deletion natively and is often more space-efficient at the same false-positive rate.

#Bloom Filter vs. the Alternatives

#The Backend Problems It Actually Solves

The pattern that shows up over and over in real systems is: put a Bloom filter in front of an expensive, authoritative lookup, and let it absorb the traffic that would otherwise hit that lookup for nothing.

• Negative caching in front of a database. If most lookups are for keys that don't exist — checking username availability, looking up a cache key before falling through to a slow origin, checking whether a URL is malicious — a Bloom filter answers "definitely doesn't exist" without a disk seek or a network round trip, and only forwards the "maybe exists" cases to the real store.
• Avoiding cache penetration. A flood of requests for keys that were never cached (or don't exist at all) can bypass your cache layer entirely and hammer the database — a classic outage vector. A Bloom filter of "keys known to exist" sitting in front of the cache absorbs that flood.
• LSM-tree storage engines (Cassandra, HBase, RocksDB, LevelDB) keep one Bloom filter per on-disk SSTable. Before doing a disk read to check whether a key lives in a given file, the engine checks that file's Bloom filter first — with dozens of SSTables, this turns an O(number of files) disk-seek storm into a handful of in-memory bit checks.
• Distributed crawlers and dedup pipelines use a Bloom filter to decide "have we already enqueued/processed this URL (or event, or user id)?" without keeping every ever-seen key in memory — the crawler design later in this module leans on exactly this.
• CDN and browser security lists (the classic example is a "known malicious URL" check) use Bloom filters so that the common case — the URL is fine — never needs a network call to a threat-intelligence service.

#Implementation

Below is a real Bloom filter — sized from the standard formulas, using two independent hash functions combined via double hashing to simulate k hash functions cheaply — used to guard a username-availability check in front of a database.

Wrap long lines
import hashlib
import math


class BloomFilter:
    def __init__(self, expected_items: int, false_positive_rate: float = 0.01):
        self.size = self._optimal_size(expected_items, false_positive_rate)
        self.hash_count = self._optimal_hash_count(self.size, expected_items)
        self.bit_array = bytearray(math.ceil(self.size / 8))

    @staticmethod
    def _optimal_size(n: int, p: float) -> int:
        # m = -(n * ln p) / (ln 2)^2
        return max(1, math.ceil(-(n * math.log(p)) / (math.log(2) ** 2)))

    @staticmethod
    def _optimal_hash_count(m: int, n: int) -> int:
        # k = (m / n) * ln 2
        return max(1, round((m / n) * math.log(2)))

    def _bit_positions(self, item: str):
        # Double hashing: derive k independent-enough hashes from just two
        # real hash functions instead of paying for k separate ones.
        h1 = int(hashlib.sha256(item.encode()).hexdigest(), 16)
        h2 = int(hashlib.md5(item.encode()).hexdigest(), 16)
        for i in range(self.hash_count):
            yield (h1 + i * h2) % self.size

    def add(self, item: str) -> None:
        for bit in self._bit_positions(item):
            self.bit_array[bit // 8] |= (1 << (bit % 8))

    def might_contain(self, item: str) -> bool:
        return all(
            self.bit_array[bit // 8] & (1 << (bit % 8))
            for bit in self._bit_positions(item)
        )


class UsernameRegistry:
    """Guards a slow, authoritative username lookup with a Bloom filter."""

    def __init__(self, existing_usernames: list[str]):
        self.bloom = BloomFilter(expected_items=len(existing_usernames), false_positive_rate=0.001)
        for name in existing_usernames:
            self.bloom.add(name)

    def is_taken(self, username: str) -> bool:
        if not self.bloom.might_contain(username):
            # Zero doubt: this username has never been inserted. Skip the DB.
            return False
        # The filter says "maybe" — confirm against the real source of truth.
        return self._check_database(username)

    def _check_database(self, username: str) -> bool:
        # SELECT 1 FROM users WHERE username = %s (or a Redis GET, etc.)
        raise NotImplementedError

With one million existing usernames and a 0.1% false-positive rate, this filter costs roughly 1.8 MB of memory and answers the overwhelming majority of "is this taken?" checks — every single one for a genuinely available username — without ever touching the database.

🧠 Check your understanding
0/3 · 0/3 answered
1. A Bloom filter reports that a key is present. What can you conclude?
The key is present with the configured false-positive probability of being wrongThe key is definitely presentThe key has been deletedThe key was never inserted
2. Why can't a standard Bloom filter support deletion?
Deletion is supported, it just requires a lockClearing a bit could unset a bit that another inserted item still depends on, creating a false negativeBit arrays are immutable in most languagesIt would require rehashing all future insertions
3. Where is a per-SSTable Bloom filter used in a real storage engine?
To compress the SSTable on diskTo encrypt keys at restTo decide whether a disk read for a given file is worth doing before doing itTo replace the primary key index entirely