Bloom filters

The problem

Your read path hits the database on every request. Many of those requests look for rows that do not exist: user profiles that were deleted, product IDs that were never created, cache keys that have not been set yet. Each one triggers a disk read, finds nothing, and returns empty.

At low volume, this is fine. At 100,000 reads per second where 30% are misses, you're burning 30,000 disk reads per second just to confirm that data isn't there.

The question: can you answer "this key definitely does not exist" in a few nanoseconds and without reading disk? A Bloom filter does exactly that.

What a Bloom filter is

A Bloom filter is a probabilistic data structure that tells you, with certainty, when something is not in a set, and tells you with high probability when something might be in the set.

Two guarantees:

• No false negatives. If the filter says "not present," the item is definitely not in the set.
• Some false positives. If the filter says "might be present," it could be wrong.

Analogy: Imagine checking whether a name appears in a massive phone book. Instead of flipping through every page, you run the name through a set of highlighter tests: "does the first syllable match any red-highlighted pattern?" "Does the last letter match any blue-highlighted pattern?" If all tests pass, the name might be there. If any test fails, the name is definitely not there. The highlighter tests are the hash functions. The phone book pages are not touched unless all tests pass.

How it works

A Bloom filter is a bit array of m bits, all initialized to 0, combined with k independent hash functions.

Adding an element:

1. Run the element through all k hash functions.
2. Each hash function produces an index in [0, m).
3. Set the bit at each of those k positions to 1.

Checking membership:

1. Run the query element through all k hash functions.
2. Check the bit at each of the k positions.
3. If any bit is 0: the element is definitely NOT in the set.
4. If all bits are 1: the element MIGHT be in the set (could be a false positive from other elements).

// Bloom filter with m=16 bits, k=3 hash functions
bits = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

function add(element):
  for each hash_fn in [h1, h2, h3]:
    index = hash_fn(element) % 16
    bits[index] = 1

function might_contain(element):
  for each hash_fn in [h1, h2, h3]:
    index = hash_fn(element) % 16
    if bits[index] == 0:
      return false       // definitely not present
  return true            // might be present

// Example:
add("alice")   // sets bits at positions [2, 7, 11]
add("bob")     // sets bits at positions [4, 7, 14]

might_contain("alice")  // checks positions 2, 7, 11 → all 1 → true
might_contain("charlie")// checks positions 5, 9, 11 → bit 5 is 0 → false (definitely not present)
might_contain("dave")   // checks positions 2, 4, 14 → all 1 → true (FALSE POSITIVE)

Dave was never added, but his hash positions all happened to be set by Alice and Bob. That is a false positive.

Bloom filter internals: the bit array

spawnSync d2 ENOENT

Step-by-step: add("alice")

spawnSync d2 ENOENT

Step-by-step: contains("charlie")

spawnSync d2 ENOENT

How false positives happen

spawnSync d2 ENOENT

Sizing the filter: the false positive rate math

The false positive rate is determined by three parameters: m (bit array size), n (number of elements inserted), and k (number of hash functions).

The approximate false positive probability is:

p ≈ (1 - e^(-kn/m))^k

For practical use, the optimal number of hash functions is k = (m/n) × ln(2).

The bit array size needed for a target false positive rate p with n elements:

m = -(n × ln(p)) / (ln(2))^2

Target: 1% false positive rate for 1 million elements
m = -(1,000,000 × ln(0.01)) / (ln(2))^2
m = -(1,000,000 × (-4.605)) / 0.480
m ≈ 9,585,000 bits ≈ 1.15 MB
k = (9,585,000 / 1,000,000) × ln(2) ≈ 6.6 → use k=7

Target: 0.1% false positive rate for same 1 million elements
m ≈ 1.73 MB  (1.5x more bits for 10x better accuracy)

A 1% false positive rate for a million elements costs under 1.2 MB. That's in-memory. Disk reads cost orders of magnitude more. This is why Bloom filters are effective: the filter is tiny relative to the cost of the reads it prevents.

What Bloom filters cannot do

• No deletions. Setting a bit to 0 to "remove" an element would incorrectly affect other elements that share that bit position. The standard solution is a counting Bloom filter (each position stores a count, not just 0/1), but it uses more memory.
• Cannot return the element. The filter only answers "yes/maybe" or "no." It stores no actual values.
• False positive rate grows as you add elements. More elements fill more bits. Once enough bits are set, almost every query returns "might be present" even for elements not in the set. Size m for your maximum n upfront.

When to use (and when not to)

Where production systems use Bloom filters

Cassandra: skipping SSTables

Cassandra stores data in immutable SSTables on disk. A read for a single key may require checking multiple SSTables (the current one plus older unflushed ones). Without optimization, this is multiple disk reads per query.

Cassandra keeps a Bloom filter per SSTable, loaded in memory. For a read request:

1. Check each SSTable's Bloom filter.
2. Skip any SSTable where the filter says "definitely not present."
3. Read only the SSTables where the filter says "might be present."

For a key that exists in only one SSTable, the Bloom filter eliminates 80-95% of SSTable reads, depending on how many SSTables exist. For keys that do not exist at all, the filter eliminates all reads after the false positive rate's fraction.

RocksDB: same pattern

RocksDB uses Bloom filters on SST files for identical reasons. At the NewBloomFilterPolicy(10) setting, roughly 10 bits per key, the filter eliminates most unnecessary reads across levels.

Cache miss protection (negative caching)

Before querying the database for a user profile, check a Bloom filter of existing user IDs. If the filter says "definitely not present," return a 404 immediately without touching the database.

This is particularly valuable for handling scraper traffic where bots probe random IDs. Without the filter, each probe generates a database read that returns empty. With the filter, the response is in-memory and instant, and the database sees no traffic from invalid IDs.

// Cache miss protection example
const bloomFilter = new BloomFilter(10_000_000, 0.01); // 10M users, 1% FP rate

// Populate on startup from known user IDs
for (const userId of await db.getAllUserIds()) {
  bloomFilter.add(userId);
}

async function getUser(userId: string): Promise<User | null> {
  // O(1) memory check — no disk
  if (!bloomFilter.mightContain(userId)) {
    return null;  // definitely doesn't exist, skip DB entirely
  }
  // Might exist — check DB (1% of non-existent IDs reach here)
  return await db.query('SELECT * FROM users WHERE id = ?', [userId]);
}

Production usage

Interview cheat sheet

• A Bloom filter answers "definitely not present" or "possibly present." No false negatives, some false positives.
• Size is proportional to the number of elements and the target false positive rate. 1% FP rate, 1M elements costs about 1.2 MB. That is the entire point: the filter is tiny relative to the cost of the disk reads it prevents.
• Deletions are not supported in a standard Bloom filter. Use a counting Bloom filter if you need deletions.
• Cassandra and RocksDB use per-SSTable Bloom filters to skip disk reads on LSM tree lookups. This is one of the key reasons LSM trees are competitive on read performance despite their append-only write model.
• In interviews: when someone asks how to avoid unnecessary database reads for non-existent keys (especially under crawler traffic), Bloom filter is the correct answer.

Quick recap

1. A Bloom filter is a probabilistic data structure that guarantees "definitely not present" while allowing a configurable rate of false positives for "might be present."
2. The filter is a bit array plus k hash functions. Adding an element sets k bits. Checking membership tests those same k bits.
3. Size is determined by element count and target false positive rate. 1% FP for 1M elements costs about 1.2 MB.
4. Standard Bloom filters do not support deletion. Counting Bloom filters do, at the cost of 4-8x more memory.
5. Cassandra and RocksDB use per-SSTable Bloom filters to eliminate most disk reads for missing keys in LSM tree lookups.
6. The filter must be sized for peak cardinality. A filter built for 10M elements and used for 50M elements degrades to near-random responses.

Related concepts

• LSM Trees — Bloom filters are an essential companion to LSM tree storage engines. Without them, read amplification (checking multiple SSTables per read) would make LSM-based systems impractically slow for random reads.
• Caching — Bloom filters and caches both reduce load on the database. The difference: caches store actual values and handle warm reads; Bloom filters handle cold misses (keys that don't exist at all).
• Hashing — The quality of the hash functions used in a Bloom filter determines both the false positive rate and the filter's security properties. Understanding what makes a good hash function matters here.