Bloom Filters from First Principles: Architecture, Trade-Offs, and Internals

The set membership problem is straightforward: given a set $S$ and an element $x$, determine whether $x \in S$. In software engineering, this check powers critical paths—from checking if a user has already watched a video, to avoiding redundant disk lookups in distributed storage systems, to verifying if a malicious URL is in a blocklist.

While simple to state, standard data structures hit fundamental scaling limitations in memory-constrained environments or high-throughput distributed systems. The Bloom filter provides a probabilistic solution, achieving massive space savings by sacrificing absolute correctness in a controlled, predictable way.

---

The Memory Wall of Traditional Sets

To understand why Bloom filters exist, we must analyze the spatial limitations of standard set implementations.

1. Array-Based Sets

• Lookup Complexity: $O(N)$
• Evaluation: Infeasible for millions of elements due to linear scan latency.

2. Balanced Binary Search Trees (e.g., Red-Black Trees, std::set)

• Lookup Complexity: $O(\log N)$
• The Hidden Metadata Problem: For an integer set storing 4-byte integers on a 32-bit/64-bit machine:
  • Actual Payload: 4 bytes
  • Left Pointer: 4 to 8 bytes
  • Right Pointer: 4 to 8 bytes
  • Parent/Color metadata: 1 to 4 bytes

+-----------------------------------------------+
|           Standard BST Node Overhead          |
+-----------------------+-----------------------+
| Left Child Pointer    | 8 bytes (Metadata)    |
| Right Child Pointer   | 8 bytes (Metadata)    |
| Tree Metadata/Color   | 8 bytes (Metadata)    |
| Value (e.g., Int32)   | 4 bytes (Actual Data) |
+-----------------------+-----------------------+
Total Node Size: ~28-32 bytes to store 4 bytes of data (~85% overhead)

For 1,000,000 integers (4 MB of raw data), a balanced binary tree consumes 12 MB to 32 MB of memory. Over two-thirds of the memory is consumed entirely by metadata (pointers and node tracking). Additionally, pointer chasing across fragmented heap memory leads to poor CPU L1/L2/L3 cache locality and frequent cache misses.

3. The Bare Minimum Constraint

Even if metadata overhead is eliminated using a contiguous, open-addressing hash table or sorted array ($O(\log N)$ lookup via binary search), storing the raw keys represents an impassable lower bound:

$\text{Minimum Space} = N \times \text{sizeof}(key)$

Consider an application like Instagram Reels:

• Assume 1,000,000 users and 1,000,000 reels.
• Tracking which user has seen which reel naively requires up to $10^{12}$ interaction records.
• Even storing compact 64-bit IDs consumes terabytes of memory purely for presence checks.

To break below this theoretical lower bound, the actual key data cannot be stored. Information must be discarded.

---

The Bloom Filter Intuition: Sacrificing Information

A Bloom filter resolves the space constraint by storing the presence of an item rather than the item itself.

              Hash Functions
Item (x) ---> h1(x) ---> Index A ---> [1]
         ---> h2(x) ---> Index B ---> [1]
         ---> h3(x) ---> Index C ---> [1]
                                        |
                                        v
                             Bit Array [0, 1, 0, 0, 1, ...]

Mechanics of a Naive Bloom Filter

1. Initialize a bit array $B$ of size $m$, where every bit is set to 0.
2. Choose a hash function $h(x)$ that maps keys uniformly into the range $[0, m-1]$.

Insertion:

To insert key $x$: $\text{index} = h(x) \pmod m$ Set $B[\text{index}] = 1$.

Membership Query:

To check if key $y$ exists: $\text{index} = h(y) \pmod m$

• If $B[\text{index}] == 0$, $y$ is definitely not present.
• If $B[\text{index}] == 1$, $y$ is probably present.

Why False Positives Are Inevitable

Assume a small bit array of $m = 16$ bits (2 bytes), inserting strings "apple", "ball", and "cat":

• h("apple") % 16 = 2 $\rightarrow$ Set $B[2] = 1$
• h("ball") % 16 = 5 $\rightarrow$ Set $B[5] = 1$
• h("cat") % 16 = 2 $\rightarrow$ Hash collision; $B[2]$ is already $1$

Bit Array Index:   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
Bit Array Value:  [0][0][1][0][0][1][0][0][0][0][0][0][0][0][0][0]
                         ^        ^
                   apple, cat    ball

Raw storage for "apple" (5 bytes), "ball" (4 bytes), and "cat" (3 bytes) requires 12 bytes without pointers. The Bloom filter encodes this presence in 2 bytes (16 bits).

However, consider an uninserted key "elephant":

• h("elephant") % 16 = 2
• The filter checks $B[2]$, finds it set to 1, and returns true.

This is a false positive. The bit was asserted by "apple" and "cat", but the filter cannot distinguish what caused the bit to be set because the original key was never stored.

The Asymmetric Guarantee

• Negative Response (0): Absolute certainty. If the bit is 0, no inserted element could have hashed to that index. Zero false negatives.
• Positive Response (1): Probabilistic. The bit could have been set by the query element or by a collision with previously inserted elements.

$\text{Bloom Filter Answer} \in \{\text{Definite No}, \text{Maybe Yes}\}$

---

Hash Function Selection: Why MurmurHash?

Standard cryptographic hash functions like SHA-256 or MD5 provide low collision rates, but are suboptimal for Bloom filters.

Attribute	Cryptographic Hashes (SHA-256, MD5)	Non-Cryptographic Hashes (MurmurHash3, xxHash)
Primary Goal	Pre-image and collision resistance	High throughput, uniform bit distribution
CPU Cost	High (multiple complex mathematical rounds)	Low (simple shift, XOR, multiply instructions)
Throughput	Moderate	5x to 10x faster than SHA variants
Use Case	Security, digital signatures, passwords	In-memory hash tables, Bloom filters, caches

Because Bloom filters operate internally within trusted data-path boundaries, cryptographic resistance against adversarial hash inversion is unnecessary. High-speed computation and uniform bit distribution across the array are the primary requirements, making MurmurHash or xxHash standard industry choices.

---

Capacity Degradation and the Resizing Problem

As elements are added to a Bloom filter of size $m$, the density of 1s increases monotonically. If $k$ hash functions are used and $n$ elements are inserted, the probability that a specific bit is still 0 is:

$p_0 = \left(1 - \frac{1}{m}\right)^{kn} \approx e^{-\frac{kn}{m}}$

As $n \to \infty$, $p_0 \to 0$, meaning every bit in the array becomes 1. At that point, all membership queries return true, rendering the filter useless ($100\%$ false positive rate).

Saturation Progression:
Initial:    [0][0][0][0][0][0][0][0] -> FPR: 0%
Moderate:   [0][1][0][1][1][0][1][0] -> FPR: Acceptable (~1-2%)
Saturated:  [1][1][1][1][1][1][1][1] -> FPR: 100% (Useless)

Why Can’t a Bloom Filter Be Resized In-Place?

A hash mapping is fundamentally bound to the array dimension:

$\text{index} = h(x) \pmod m$

Doubling the array size from $m$ to $2m$ alters the modulo base. An existing bit array cannot simply be appended to or zero-extended because an element previously mapped to index $i$ might map to $i + m$ under modulo $2m$.

Because the raw keys were discarded during insertion, recalculating $h(x) \pmod{2m}$ from the bit array alone is impossible.

How Resizing Is Handled in Production

1. Maintain a Source of Truth: The authoritative data must persist in secondary storage (e.g., PostgreSQL, Cassandra, SSTables, S3).
2. Allocate a New Filter: When the false positive rate breaches a target threshold, provision an expanded bit array of size $m_{new}$.
3. Re-ingest Elements: Read historical keys from the source of truth, compute $h(x) \pmod{m_{new}}$, and set the bits in the new filter.

+-------------------------------------------------------------+
|                       Re-ingestion Path                     |
+-------------------------------------------------------------+
|  Persistent DB (Source of Truth)                            |
|  [ Key 1, Key 2, Key 3, ... Key N ]                         |
|         |                                                   |
|         v                                                   |
|  Hash & Modulo by new size: h(x) % m_new                    |
|         |                                                   |
|         v                                                   |
|  New Expanded Bloom Filter (Size: m_new)                    |
|  [0][1][0][0][1][1][0]...                                   |
+-------------------------------------------------------------+

Day-Zero Sizing Parameters

To avoid thrashing re-allocations, Bloom filters are sized up-front using two target parameters:

• $n$: Expected number of elements to insert.
• $p$: Acceptable false positive probability (e.g., $1\%$ or $0.01$).

The required bit array size $m$ and optimal number of hash functions $k$ are derived as:

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

$k = \frac{m}{n} \ln 2$

For example, standard Redis Bloom filter implementations frequently allocate an initial baseline (e.g., 1 KB) and expand into a Scalable Bloom Filter (a chain of multiple filters with decreasing error rates) as key volume increases.

---

Practical System Design Use Cases

Bloom filters are useful whenever the cost of a false positive is negligible compared to the resource savings achieved by eliminating unnecessary lookups.

1. Content Distribution Networks (CDNs) and Disk Caches

• Problem: Checking whether a requested static asset exists in local disk/SSD cache requires an expensive disk I/O operation. If the asset is missing, that disk read was entirely wasted before falling back to the origin server.
• Architecture: The CDN maintains an in-memory Bloom filter representing all locally cached asset paths.

Incoming Request for Asset
          |
          v
+-------------------+
| In-Memory Bloom   |
|      Filter       |
+-------------------+
     /        \
    /          \ 
  "NO"        "MAYBE"
  /              \
v                v
Skip Local Disk;   Check Local SSD/Disk Cache
Fetch Immediately       /             \
from Origin Server   Hit               Miss (False Positive)
                      |                  |
             Return Cached File     Fetch from Origin

• Trade-off Analysis: If the filter returns No, the system skips the disk entirely and routes immediately to the origin. If it returns Maybe, it checks the disk. A false positive merely results in a missed disk lookup, which was the default behavior without the filter.

2. Feed Recommendations (e.g., Social Media Short-Form Video)

• Problem: Ensuring a user is not shown a video or reel they have already watched.
• Scale: A user watching hundreds of clips per day accumulates tens of thousands of views over time. Storing full 64-bit reel IDs in-memory per active user session incurs heavy RAM costs.
• Implementation: Maintain a per-user Bloom filter in memory. When recommending an item:
  • Bloom.contains(reel_id) == false: Safely serve the reel. The user has definitely not seen it.
  • Bloom.contains(reel_id) == true: Skip the reel. Assume it has been seen.
• The Cost of False Positives: A false positive means the system skips a reel the user hasn’t seen yet. In a system with millions of available videos, skipping a candidate reel causes zero user-facing degradation.

3. High-Volume Marketing / Notification Campaigns

• Problem: Sending an email campaign to tens of millions of users without duplicating messages.
• Implementation: A Bloom filter tracks user_ids that have been sent the campaign.
• Trade-off Analysis:
  • Contains == false: The user has not been sent the email. Dispatch it.
  • Contains == true: The user might have received it. Suppress dispatch.
  • If a false positive occurs (e.g., for 1% of users), those users do not receive the email. In broad promotional campaigns where secondary channels (push notifications, in-app banners) exist, dropping a small, controlled fraction of messages is an acceptable engineering trade-off to save millions of database writes.

---

Summary of Key Takeaways

1. Metadata Dominates at Scale: Pointer overhead in tree-based sets consumes 60–85% of allocated memory, degrading CPU cache utilization.
2. Presence Over Data: Bloom filters do not store keys; they store existential footprints via bit patterns, breaking below theoretical raw-key storage floors.
3. Asymmetric Guarantees: A Bloom filter never produces false negatives (a 0 means the key is definitely absent), but allows configurable false positive rates (a 1 means the key is probably present).
4. Hash Efficiency Matters: Fast, uniform, non-cryptographic hashes like MurmurHash or xxHash are preferred over cryptographic algorithms like SHA-256.
5. Immutable Dimensions: Because hashing relies on modulo arithmetic ($h(x) \pmod m$), an existing Bloom filter cannot be resized in-place. Resizing requires an external source of truth to re-ingest keys into an expanded array.