Bloom Filters

The Core Idea

A Bloom filter is a space-efficient probabilistic data structure that tests whether an element is a member of a set. It can tell you 'definitely not in the set' or 'probably in the set.' False positives are possible; false negatives are not.

Step-by-Step Walkthrough

Cassandra uses Bloom filters for each SSTable (sorted file on disk). When a read query arrives: check the Bloom filter for each SSTable. If the filter says 'not present,' skip reading that file entirely. This avoids expensive disk I/O for most queries.

With 10 SSTables and Bloom filters, instead of reading 10 files, you might only read 1-2 (the ones where the filter says 'might be present').

Why This Approach Wins

• Bit array + hash functions: A Bloom filter is a bit array of m bits with k hash functions. To add an element, hash it k times and set those bit positions to 1.
• Lookup: Hash the query k times. If ALL positions are 1, the element is probably in the set. If ANY position is 0, the element is definitely not in the set.
• False positive rate: Depends on m (array size), k (hash functions), and n (elements). Typical: 1% false positive rate with 10 bits per element.
• No deletion: Standard Bloom filters do not support deletion (clearing a bit might affect other elements). Counting Bloom filters add this capability.
• Space efficiency: A Bloom filter with 1% false positive rate uses ~10 bits per element, regardless of element size.

In Production

Google Bigtable uses Bloom filters to avoid reading SSTables that do not contain the requested row.

Cassandra uses per-SSTable Bloom filters, reducing disk reads by 90%+ for missing keys.

Akamai CDN uses Bloom filters to track which content is cached at each edge server.

Tradeoffs and Limitations

• Space vs Accuracy: More bits = lower false positive rate, but more memory.
• No deletion: Standard Bloom filters are append-only. Counting Bloom filters support deletion but use more space.
• Probabilistic: Bloom filters are not 100% accurate — you must handle false positives in your application logic.

Production Gotchas

1. Using Bloom filters for small sets where a hash set is better
2. Not sizing the filter correctly — too small leads to unacceptable false positive rates
3. Forgetting that Bloom filters cannot return the actual data — only membership

The Interview Angle

1. What is a Bloom filter and how does it work?
2. What are false positives and false negatives in a Bloom filter?
3. Where are Bloom filters used in practice?
4. How do you choose the size and number of hash functions?

Next Up

• Database Indexes
• Caching
• Distributed Caching

Original DosiBridge notes for Bloom Filters

This section is written specifically for this page, not copied from a general system-design checklist. The useful way to study Bloom Filters is to connect the concept to a production service where growth exposes the first weak assumption in the original design. That framing changes the design discussion from definitions to operating choices.

What makes this topic distinct

• Query Shape: For Bloom Filters, decide the query shape before choosing tools; otherwise the design looks clean but fails when bloom changes.
• Write Amplification: For Bloom Filters, decide the write amplification before choosing tools; otherwise the design looks clean but fails when filters changes.
• Replication Lag: For Bloom Filters, decide the replication lag before choosing tools; otherwise the design looks clean but fails when bloom changes.
• Migration Safety: For Bloom Filters, decide the migration safety before choosing tools; otherwise the design looks clean but fails when filters changes.
• Data Ownership: For Bloom Filters, decide the data ownership before choosing tools; otherwise the design looks clean but fails when bloom changes.

Production review question

If a team adopts Bloom Filters, what observable signal proves it helped instead of only making the architecture diagram more fashionable?

Practical metric to track

Track bloom-filters health as a named dashboard or review item: combine one user-facing metric, one saturation metric, and one correctness metric. For Bloom Filters, this keeps the discussion grounded in behavior that can be measured after deployment instead of generic advice that sounds good in an interview but never gets verified.