system-design · intermediate

Bloom Filters — Probabilistic Set Membership at Scale

The Central Question

Consider a high-throughput storage engine running on the DataLab platform (datalab.com):

• An LSM-Tree storage engine (such as RocksDB or Cassandra) stores 1,000,000,000 key-value pairs distributed across 500 immutable SSTable files on disk.
• A user issues a read query: GET user_session_9012.
• user_session_9012 does not exist in the database (a non-existent key).

1. The database searches the in-memory MemTable (Key Not Found).
2. The database initiates expensive disk reads, scanning index blocks across Level 0, Level 1, Level 2, and Level 3 SSTable files on disk.
3. After executing 12 random disk page reads across 500 SSTables, the engine finally concludes that user_session_9012 does not exist.

This lesson answers one central question: How does a Bloom Filter use a compact bit array and $k$ independent hash functions to provide a fast $O(1)$ in-memory test that guarantees a key is "definitely not in the database," bypassing expensive disk seeks without storing raw key strings in RAM?

The Probabilistic Guarantee: Zero False Negatives

A Bloom Filter is a probabilistic data structure. It does not store actual key strings or values; instead, it stores bit patterns generated by $k$ independent cryptographic hash functions.

flowchart TD
  Query[Query Key: 'usr_9012'] --> Test{Evaluate Bloom Filter}
  
  Test -->|Bit Pattern Returns 0| DefNot["DEFINITELY NOT IN SET!<br/>(Zero False Negatives Guaranteed!)"]
  Test -->|Bit Pattern Returns 1| PossIn["POSSIBLY IN SET<br/>(Low False Positive Rate: p = 1%)"]
  
  DefNot -->|Fast Bypass!| ReturnNull[Return Key Not Found Immediately<br/>Latency: 0.01ms | Zero Disk Seeks!]
  PossIn -->|Perform Disk Seek| ReadDisk[Read MemTable & SSTable Files on Disk<br/>Latency: 2.0ms]

Figure 1: Decision logic for Bloom Filter set membership queries.

The Invariant Principles

1. Zero False Negatives ($0\%$ Error): If the Bloom Filter returns "Definitely Not in Set", the key is 100% guaranteed not to exist. The system can safely skip disk seeks.
2. Controlled False Positives ($p\%$ Error): If the Bloom Filter returns "Possibly in Set", the key might exist, or hash collisions might have set those bits artificially. The database proceeds to check disk files.

Anatomy of a Bloom Filter: Bit Array & Hash Functions

A Bloom Filter consists of a Bit Array of size $m$ bits (all initialized to 0) and $k$ independent uniform hash functions ($h_1, h_2, \dots, h_k$).

flowchart TB
  subgraph Step 1: Insertion of Key 'alice'
    Key1["Key: 'alice'"] --> H1["h1('alice') = Bit Index 2"]
    Key1 --> H2["h2('alice') = Bit Index 5"]
    Key1 --> H3["h3('alice') = Bit Index 9"]
  end
subgraph Step 2: Bit Array Modification (Size m = 12 bits)
    Bits["Bit Array: [0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0]"]
  end
  
  H1 --> Bits
  H2 --> Bits
  H3 --> Bits

Figure 2: Inserting a key by setting bit positions 2, 5, and 9 to 1.

1. Item Insertion Algorithm

1. Compute $k$ hash values: $h_1(\text{"alice"}), h_2(\text{"alice"}), \dots, h_k(\text{"alice"})$.
2. Map each hash value to a bit array index using modulo math: $\text{index}_i = h_i(\text{"alice"}) \pmod m$.
3. Set the bit array entries at those $k$ calculated indexes to 1.

2. Item Membership Query Algorithm

1. Compute the $k$ bit array indexes: $\text{index}_1, \text{index}_2, \dots, \text{index}_k$.
2. Inspect the bit array at those indexes.
3. If any of the $k$ bits contains a 0, return "Definitely Not in Set".
4. If all $k$ bits contain 1, return "Possibly in Set".

Mathematical Formulations: Optimal Sizing & Hash Count

Engineers configure Bloom Filters by defining two input requirements:

• $n$: The total number of items to store in the filter (e.g. $n = 10,000,000$ keys).
• $p$: The acceptable False Positive Probability (e.g. $p = 0.01$, or $1\%$).

flowchart LR
  Inputs["Inputs: n = 10M keys, p = 1% error"] --> Math1["1. Calculate Optimal Bit Array Size (m)"]
  Math1 --> Math2["2. Calculate Optimal Hash Functions (k)"]
  Math2 --> Config["Result: m = 95.8 MB RAM, k = 7 Hash Functions"]

Figure 3: Deriving memory array size and hash function count from target parameters.

1. Optimal Bit Array Size Formula ($m$)

$$m = -\frac{n \times \ln(p)}{(\ln 2)^2}$$

Because $(\ln 2)^2 \approx 0.48045$, the formula simplifies to:

$$m \approx -2.081 \times n \times \ln(p) \quad \text{bits}$$

• Example: To store $n = 10,000,000$ keys with a $p = 0.01$ ($1\%$) false positive rate:

2. Optimal Number of Hash Functions Formula ($k$)

$$k = \frac{m}{n} \times \ln 2 \approx 0.693 \times \frac{m}{n}$$

• Example: With $m/n = 9.585$ bits per key:

Partitioned Bloom Filters vs Standard Filters

Why Standard Bloom Filters Cannot Handle Deletions

A standard Bloom Filter does not support item deletions.

flowchart TD
  Del["Attempting to Delete Key 'alice' (Bits: 2, 5, 9)"] --> Question{Can we set Bit 5 back to 0?}
  Question -->|NO!| Conflict["Bit 5 is shared by Key 'charlie' (Bits: 1, 5, 11)!<br/>Setting Bit 5 to 0 deletes 'charlie' silently!"]

Figure 4: Shared bit positions preventing key deletion in standard Bloom Filters.

If an application attempts to delete a key by clearing its $k$ bits to 0, it will inadvertently clear bits shared by other active keys, introducing False Negatives and corrupting the fundamental invariant.

Solution: Counting Bloom Filters

• Insert: Increment counters at the $k$ index positions ($+1$).
• Delete: Decrement counters at the $k$ index positions ($-1$).
• Trade-off: Consumes 4x to 8x more RAM than a standard bit array.

Real-World Production Use Cases

flowchart TD
  UseCases[Production Applications of Bloom Filters] --> UC1[1. LSM Storage Engines]
  UseCases --> UC2[2. Web Search & Web Crawlers]
  UseCases --> UC3[3. CDN Edge Cache Bypassing]
  UseCases --> UC4[4. Malicious URL Security Filters]
  
  UC1 --> UC1a[RocksDB / Cassandra skip non-existent SSTable files on disk]
  UC2 --> UC2a[Google Web Crawler skips millions of previously crawled URLs]
  UC3 --> UC3a[Cloudflare checks if URL exists in cache before triggering disk I/O]
  UC4 --> UC4a[Chrome checks target domain against 1M malicious site hashes in RAM]

Figure 5: Industry use cases for high-scale Bloom Filter implementations.

Complete Worked Example: Go Thread-Safe Bloom Filter Implementation

Let's inspect the complete Go implementation of a memory-efficient Bloom Filter using MurmurHash3 for the DataLab engine (datalab.com).

package main
import (
	"fmt"
	"math"
	"sync"
"github.com/spaolacci/murmur3"
)
type BloomFilter struct {
	mu        sync.RWMutex
	bitArray  []bool
	m         uint64 // Bit array size
	k         uint64 // Number of hash functions
	itemCount uint64
}
func NewBloomFilter(expectedItems uint64, falsePositiveRate float64) BloomFilter {
	// m = - (n  ln(p)) / (ln(2)^2)
	m := uint64(math.Ceil(-1  float64(expectedItems)  math.Log(falsePositiveRate) / math.Pow(math.Log(2), 2)))
	// k = (m / n)  ln(2)
	k := uint64(math.Round(float64(m) / float64(expectedItems)  math.Log(2)))
return &BloomFilter{
		bitArray: make([]bool, m),
		m:        m,
		k:        k,
	}
}
// Double Hashing technique: hash_i(x) = (hash1(x) + i  hash2(x)) % m
func (bf BloomFilter) getHashes(key string) []uint64 {
	h1, h2 := murmur3.Sum128([]byte(key))
	indexes := make([]uint64, bf.k)
for i := uint64(0); i < bf.k; i++ {
		combined := h1 + (i * h2)
		indexes[i] = combined % bf.m
	}
	return indexes
}
func (bf *BloomFilter) Add(key string) {
	bf.mu.Lock()
	defer bf.mu.Unlock()
indexes := bf.getHashes(key)
	for _, idx := range indexes {
		bf.bitArray[idx] = true
	}
	bf.itemCount++
}
func (bf *BloomFilter) Contains(key string) bool {
	bf.mu.RLock()
	defer bf.mu.RUnlock()
indexes := bf.getHashes(key)
	for _, idx := range indexes {
		if !bf.bitArray[idx] {
			return false // DEFINITELY NOT IN SET! (Zero False Negatives)
		}
	}
	return true // POSSIBLY IN SET (Subject to p% false positive rate)
}

Failure Modes and Engineering Mitigations

What You Should Remember

1. Zero False Negatives: A Bloom Filter guarantees that if a key returns "Definitely Not in Set", the key is 100% absent from storage ($0\%$ error).
2. Controllable False Positives: Returns "Possibly in Set" with an error rate $p$ dictated by bit array size $m$ and hash count $k$.
3. Massive Memory Savings: Bloom Filters store bit patterns, consuming 95% less RAM than raw hash tables.
4. Standard Bloom Filters cannot delete: Clearing bits during deletion corrupts shared key bits. Use Counting Bloom Filters or rebuild filters during compaction.
5. Essential for LSM Storage Engines: RocksDB and Cassandra use Bloom Filters to skip non-existent SSTable disk files, avoiding costly disk reads.

Glossary of Terms

Practice Scenario and Self-Assessment

Architecture Scenario

• The crawler tracks 500,000,000 malicious URL strings.
• The crawler must check incoming URLs against the database in RAM with sub-1ms response times.
• Target False Positive Probability: $p = 0.001$ ($0.1\%$).

1. Calculate the required Bit Array size ($m$) in Megabytes to store all 500,000,000 malicious URLs.
2. Explain why a standard Bloom Filter is superior to an in-memory Redis Hash Table for this security crawler.

Interactive Self-Assessment

The requested key is 100% guaranteed not to exist in storage (Zero False Negatives).

The requested key has a 1% chance of existing in storage.

The storage engine must re-format its hard drive file system.

The network socket terminates its HTTPS TLS encryption handshake.

Multiple keys share identical bit positions; clearing a bit for Key A deletes shared bits for Key B.

Clearing bits causes CPU hardware clock skew on the database server.

Standard Bloom Filters use 64-bit float values that cannot be decremented.

Clearing bits causes memory locks that freeze OS kernel threads.

What to Learn Next

• Database Storage Architectures — B-Trees vs LSM-Trees: See how RocksDB and Cassandra integrate Bloom Filters with SSTables.
• Types of Databases — Matching Tools to Access Patterns: Revisit database paradigms and data structures.
• Content Delivery Networks (CDN) — Edge Acceleration: Learn how CDNs use Bloom Filters to check edge cache membership.

Track: Data, Storage and Messaging

Previous: Banking Transaction Platform Design

Next: Connection Pooling — Reusing Expensive Database Sessions

Series: Caching

1. Caching 101 — Memory Offloading and Latency Reduction
2. Caching Strategies — Aside, Through, Behind, and Refresh-Ahead
3. Cache Eviction Policies — LRU, LFU, TTL, and Friends
4. Distributed Caching — Sharding and High-Availability Clusters
5. Cache Stampede — When Expiry Melts the Database
6. Stale Cache After Write — When Your Own Update Disappears
7. Content Delivery Networks (CDN) — Edge Acceleration and Caching
8. Bloom Filters — Probabilistic Set Membership at Scale (this guide)

All series

By Shubham Jain

All articles · Study paths

Shubham Jain · Learning Lab