Bloom Filters: Probabilistic Membership Testing in System Design

Suppose you run a web crawler that has visited 10 billion URLs. Before fetching a new URL, you need to check: “Have I seen this URL before?” Storing 10 billion URLs in a hash set takes hundreds of gigabytes of memory. A Bloom filter answers the same question using roughly 1 to 2 gigabytes, with a trade-off: it can say “definitely not seen” or “probably seen,” but never “definitely seen.” That small probability of a false positive is acceptable when the alternative is running out of memory.

How It Works

A Bloom filter is a bit array of m bits, initially all set to zero, combined with k independent hash functions. Each hash function maps an element to one of the m positions in the array.

Insert

To insert an element, compute all k hash values and set the corresponding bits to 1.

Insert "apple" with k=3 hash functions:
  h1("apple") = 2
  h2("apple") = 7
  h3("apple") = 13

Bit array (m=16):
  Index:  0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15
  Before: 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  After:  0  0  1  0  0  0  0  1  0  0  0  0  0  1  0  0

Lookup

To check membership, compute all k hash values and check if all corresponding bits are 1.

Check "banana":
  h1("banana") = 2   -> bit is 1
  h2("banana") = 5   -> bit is 0  <- STOP: definitely not in the set
  h3("banana") = 13  -> (not checked)

Check "grape":
  h1("grape") = 2    -> bit is 1
  h2("grape") = 7    -> bit is 1
  h3("grape") = 13   -> bit is 1
  Result: "probably in the set" (could be a false positive)

The key insight: bits can be set by different elements. If “grape” was never inserted but its hash positions happen to overlap with bits set by other elements, the filter reports a false positive.

False Positive Rate

The probability of a false positive depends on three parameters:

m = number of bits in the array
n = number of elements inserted
k = number of hash functions

False positive probability:
  p ≈ (1 - e^(-kn/m))^k

For practical sizing, given a desired false positive rate p and expected number of elements n:

Optimal number of bits:
  m = -n * ln(p) / (ln(2))^2

Optimal number of hash functions:
  k = (m / n) * ln(2)

Example:
  n = 1,000,000 elements
  p = 1% false positive rate

  m = -1,000,000 * ln(0.01) / (ln(2))^2
    ≈ 9,585,059 bits ≈ 1.14 MB

  k = (9,585,059 / 1,000,000) * ln(2)
    ≈ 6.64 → 7 hash functions

One million elements, 1 percent false positive rate, 1.14 MB of memory. A hash set storing the same elements would use roughly 40 to 80 MB depending on the element size.

Implementation

import math
import mmh3  # MurmurHash3

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

    def add(self, item: str):
        for i in range(self.hash_count):
            idx = mmh3.hash(item, i) % self.size
            byte_idx, bit_idx = divmod(idx, 8)
            self.bit_array[byte_idx] |= (1 << bit_idx)

    def might_contain(self, item: str) -> bool:
        for i in range(self.hash_count):
            idx = mmh3.hash(item, i) % self.size
            byte_idx, bit_idx = divmod(idx, 8)
            if not (self.bit_array[byte_idx] & (1 << bit_idx)):
                return False
        return True

    @staticmethod
    def _optimal_size(n, p):
        return int(-n * math.log(p) / (math.log(2) ** 2))

    @staticmethod
    def _optimal_hash_count(m, n):
        return int((m / n) * math.log(2))

bf = BloomFilter(expected_elements=1_000_000, fp_rate=0.01)
bf.add("https://example.com/page1")
bf.add("https://example.com/page2")

bf.might_contain("https://example.com/page1")  # True (correct)
bf.might_contain("https://example.com/page3")  # False (correct)
# Occasionally True for items never added (false positive, ~1% rate)

Real-World Applications

Database read optimization

Databases like Cassandra, HBase, and LevelDB use Bloom filters to avoid unnecessary disk reads. Before reading an SSTable (sorted string table) file from disk, the database checks the file’s Bloom filter. If the filter says the key is not present, the disk read is skipped entirely.

Query: GET key="user:12345"

SSTable 1: Bloom filter says "no"  -> skip disk read
SSTable 2: Bloom filter says "no"  -> skip disk read
SSTable 3: Bloom filter says "maybe" -> read from disk

This turns many disk reads into cheap in-memory checks.

Cache penetration prevention

A malicious user requests keys that do not exist in the cache or the database, causing every request to hit the database (cache penetration). A Bloom filter in front of the cache rejects requests for keys that definitely do not exist.

Request -> Bloom filter -> "not in set" -> return 404 immediately
Request -> Bloom filter -> "maybe in set" -> check cache -> check DB

Web crawler URL deduplication

Crawlers need to track billions of visited URLs. A Bloom filter provides memory-efficient deduplication at the cost of occasionally re-crawling a URL (false positive treated as “already visited” means skipping a URL; false negative is impossible).

Spell checkers

A dictionary of valid words stored in a Bloom filter lets you quickly reject misspelled words without loading the full dictionary into memory.

Counting Bloom Filters

Standard Bloom filters do not support deletion because clearing a bit might affect other elements that hash to the same position. A counting Bloom filter replaces each bit with a counter:

Standard:  bit[i] = 0 or 1
Counting:  counter[i] = 0, 1, 2, 3, ...

Insert: increment counters at hash positions
Delete: decrement counters at hash positions
Lookup: all counters at hash positions > 0

The trade-off is memory: each position needs 3 to 4 bits instead of 1, roughly quadrupling memory usage.

Bloom Filter Variants

Variant	Key Feature	Use Case
Standard Bloom	Simplest, no deletion	Static or append-only sets
Counting Bloom	Supports deletion	Dynamic sets with removals
Cuckoo filter	Better space efficiency, supports deletion	General purpose replacement
Quotient filter	Cache-friendly, supports merge	On-disk storage
Scalable Bloom	Grows dynamically	Unknown cardinality

Cuckoo filters have largely replaced counting Bloom filters in practice because they achieve similar false positive rates with less memory and support deletion natively.

Bloom Filters in Redis

Redis provides a Bloom filter module (RedisBloom) that makes deployment trivial:

# Create a filter for 1M elements with 1% error rate
BF.RESERVE urls 0.01 1000000

# Add elements
BF.ADD urls "https://example.com/page1"
BF.MADD urls "https://example.com/page2" "https://example.com/page3"

# Check membership
BF.EXISTS urls "https://example.com/page1"  # 1 (probably exists)
BF.EXISTS urls "https://example.com/page99" # 0 (definitely not)

Key Takeaways

Bloom filters trade a small, configurable false positive rate for dramatic memory savings. They answer “is this element in the set?” in constant time and constant space per element. Use them when you need to test membership in very large sets and can tolerate occasional false positives: database read optimization, cache penetration prevention, URL deduplication, and content filtering. Size them carefully using the formulas above, and consider cuckoo filters if you need deletion support.