Bloom Filters

Concept. A Bloom filter is a bit array hashed by k functions. It answers "definitely not in the set" or "probably in the set" in constant time, using about 10 bits per item (far less than a hash set), with no false negatives.

Intuition. A Bloom filter over Listens.song_id fits in a few KB at this scale. Before reading any page, ask the filter "is song X here?" If it says no, skip the page. If it says maybe, do the real read. That skips the page read for almost every true miss.

Space-efficient probabilistic data structure

Tells you "definitely not in set" or "maybe in set".

Visual: How Bloom Filters Work

A 16-bit array; bits 3, 7, 9, 11, and 14 are set (orange), the rest are unset (white). INSERT "alice" hashes to bits 3, 7, 14 and sets them. LOOKUP "bob" hashes to bits 3, 9, 2; bit 2 is 0, so "bob" is definitely not in the set. Color key: orange is a set bit, grey is an unset bit, green is a guaranteed answer.

Figure 1. A Bloom filter is a 16-bit array plus k = 3 hash functions. INSERT "alice" hashes to bits 3, 7, and 14 and sets them (orange), alongside bits 9 and 11 already set by earlier inserts the figure does not show. LOOKUP "bob" hashes to bits 3, 9, and 2; bit[2] = 0 guarantees "bob" is not in the set (green). That asymmetry is the whole point: any 0 bit means definitely not in the set, while all 1s means only probably in, so false positives are possible but false negatives never are.

The false-positive rate is p ≈ (1 − e^−kn/m)^k, minimized at k = (m/n) · ln 2. At about 10 bits per item with optimal k ≈ 7 the rate is about 1%, so a billion-item filter needs only ~1.25 GB of bits, versus tens of GB for an equivalent in-memory hash set. That space saving, at the cost of a small false-positive rate, is why Bloom filters guard expensive lookups.

Problem-Solving Applications

For detailed examples of how Bloom filters solve real-world problems at scale, see the Data Structures Problem Solving guide, which covers:

CDN Cache Optimization (Cloudflare): How Cloudflare uses Bloom Filters to prevent "One-Hit Wonder" files (assets requested only once) from ever being written to their SSD caching layer. This intercepts billions of useless IO write operations, preventing physical hardware degradation of their global SSDs (tying back to our Storage Hierarchy constraints).
Web Crawler Efficiency: How Google and Bing prevent duplicate page crawling
Real-time Username Validation: How social platforms provide instant availability feedback

Optional

// Bloom Filter - 20 lines that save 10x space
class BloomFilter:
    bits = BitArray(size=m)      // m bits, all 0
    k = 3                         // number of hash functions

    Add(item):
        for i in 0..k-1:
            index = hash_i(item) % m
            bits[index] = 1

    Contains(item):
        for i in 0..k-1:
            index = hash_i(item) % m
            if bits[index] == 0:
                return False      // Definitely not in set
        return True               // Maybe in set

// Optimal parameters (math magic)
m = -n * ln(p) / (ln(2)^2)      // bits needed
k = m/n * ln(2)                  // hash functions

Example: 1M items, 1% false positive
→ m = 9.6M bits = 1.2MB
→ k = 7 hash functions

The Trade-off

Space per item	False positive rate	Hash functions (k)
4 bits	15%	3
10 bits	1%	7
14 bits	0.1%	10

Rule of thumb: 10 bits per item = 1% false positives = sweet spot

System Design Note: Bloom filters are the standard solution for "have we seen this?" queries at scale. For more worked examples, see the Data Structures Problem Solving guide. Case Study 2.2 puts this at planet scale: how Chrome Safe Browsing ships one Bloom filter to 3 billion devices.