Bloom Filters

1. The problem

Consider an LSM-tree storage engine like RocksDB or Apache Cassandra storing hundreds of millions of keys across thousands of immutable disk files (SSTables).

Curriculum Bridge (CORE-M08-003 $\to$ CORE-M08-001): As we saw in Step 17 (CORE-M08-003: LSM-Trees and SSTables), log-structured storage engines buffer writes in an in-memory MemTable and flush them sequentially to disk as immutable SSTables (Sorted String Tables) across levels $L_0\dots L_k$. Here we solve the primary read-amplification bottleneck of LSM-Trees: avoiding unnecessary disk seeks into SSTables that do not contain the queried key.

When a client queries a non-existent key:

[ Read GET /users/999999 ] ──► Check MemTable (Miss)
                                    │
                                    ├──► Seek SSTable #1 on NVMe (Miss)
                                    ├──► Seek SSTable #2 on NVMe (Miss)
                                    ├──► Seek SSTable #3 on NVMe (Miss) ... ($10 - 20\mu\text{s}$ each!)

To determine that the key does not exist, the engine would have to perform random disk seeks across every SSTable. Under read-heavy workloads with missing keys, disk I/O saturates immediately.

An exact in-memory hash set could prevent this, but storing 100 million 32-byte UUID keys in RAM requires over 3.2 GB of memory (plus pointer overhead).

We need a data structure that:

1. Occupies only a fraction of the memory of an exact set ($<1.2\text{ bytes per key}$).
2. Can answer membership queries in $O(k)$ operations.
3. Never yields false negatives (if it says an item is missing, it is guaranteed absent).

2. Mental model: The Fingerprint Array

Think of a Bloom Filter as a shared wall of light switches:

Item "alice" ──► Hash Functions ──► Flips switches #2, #5, #9  [ ON ]
Item "bob"   ──► Hash Functions ──► Flips switches #5, #11, #14 [ ON ]

When you query whether "charlie" is in the building:

• If any of "charlie"’s assigned switches are OFF, "charlie" has definitely never been here.
• If all of "charlie"’s switches are ON, "charlie" might have been here—or "alice" and "bob" happened to flip those exact switches between them (False Positive).

3. Core concepts

A Bloom Filter (invented by Burton Howard Bloom in 1970) is a space-efficient probabilistic data structure based on:

• A bit array of size $m$, initialized to all zeros.
• $k$ independent, uniformly distributed hash functions: $h_1(x),h_2(x),\dots ,h_k(x)$, each mapping an element $x$ to an index $\{0,1,\dots ,m-1\}$.

The Asymmetric Guarantee

4. Internal workings

SYSTEM ARCHITECTURE BLUEPRINTDATA STRUCTURES

⤢Expand

ARCHITECTURAL FLOW · STEP 1 OF 4

1. Key Proposal & Hash Evaluation

Client provides key 'user:101'. The element passes through k independent uniform hash functions (Murmur3 / xxHash).

Architectural Invariant: Space Complexity: O(m) bits regardless of element size. Hash evaluation is strictly O(k).

ARCHITECTURAL FLOW · STEP 2 OF 4

2. Bit Array Mutation

The hash functions produce indices [0, 2, 3, 5]. The storage engine flips these bit positions to 1 in the bit array via atomic bitwise OR.

Architectural Invariant: Idempotency: Setting an already-set bit is a no-op. Deletions are mathematically impossible in a standard Bloom filter.

ARCHITECTURAL FLOW · STEP 3 OF 4

3. Negative Query: Definite Absence Proof

Client queries 'user:999'. Hashes point to indices [1, 2]. Index 1 is 0. The filter immediately guarantees absence with ZERO disk I/O.

Architectural Invariant: Zero False Negatives: If even a single probe bit is 0, the element was definitively never inserted.

ARCHITECTURAL FLOW · STEP 4 OF 4

4. Positive Query: Potential Presence & Secondary Probe

Client queries 'user:101'. Hashes check [0, 2, 3]. All target bits are 1. The filter reports 'MIGHT EXIST'; exact storage lookup proceeds.

Architectural Invariant: Optimal Sizing: Optimal hash count k = (m/n) * ln(2) minimizes false positives for n elements in m bits.

1. Insertion Algorithm

To insert an element $x$:

1. Feed $x$ into each of the $k$ hash functions to compute $k$ bit indices: $$i_1=h_1(x)(\mathrm{mod}m),i_2=h_2(x)(\mathrm{mod}m),\dots i_k=h_k(x)(\mathrm{mod}m)$$
2. Set the bit at each computed index to $1$: $$\text{array}[i_1]\leftarrow 1,\text{array}[i_2]\leftarrow 1,\dots ,\text{array}[i_k]\leftarrow 1$$

2. Query Algorithm

To test whether an element $y$ is in the set:

1. Compute the same $k$ bit indices: $$i_j=h_j(y)(\mathrm{mod}m)\text{for }j\in \{1,\dots ,k\}$$
2. Inspect the bit array at those positions:
   • If any $\text{array}[i_j]==0$: Return DEFINITELY_ABSENT.
   • If all $\text{array}[i_j]==1$: Return POSSIBLY_PRESENT.

3. Why Deletions are Impossible

Standard Bloom filters do not support deletions.

If key $A$ maps to bits $\{2,5,9\}$ and key $B$ maps to $\{5,11,14\}$:

• Bit $5$ is shared by both keys.
• If you attempted to delete key $A$ by setting bits $2,5,9$ to $0$, bit $5$ would become $0$.
• A subsequent query for key $B$ would observe bit $5==0$ and falsely report that key $B$ does not exist.
• Result: You would introduce false negatives, destroying the fundamental invariant of the data structure.

(To support deletion, you must use a Counting Bloom Filter, which replaces single bits with 4-bit integer counters, quadrupling the memory footprint).

4. Kirsch-Mitzenmacher Optimization (Double Hashing)

Evaluating $k$ independent non-cryptographic hash functions (such as MurmurHash3 or xxHash) is computationally expensive.

Kirsch and Mitzenmacher (2006) proved that you can simulate $k$ hash functions using only two independent hash values $h_1(x)$ and $h_2(x)$:

This optimization reduces CPU overhead by up to $70\%$ with zero measurable increase in the false-positive rate. Production engines like RocksDB and Google Guava use this technique exclusively.

5. Mathematical foundations

Derivation of False Positive Probability

Assume hash functions are independent and uniform.

1. The probability that a specific bit is not set by a single hash function during one insertion is: $$1-\frac{1}{m}$$
2. After inserting $n$ elements, each evaluated by $k$ hash functions ($k\cdot n$ total hash operations), the probability that a specific bit remains $0$ is: $$P(\text{bit is }0)={\left(1-\frac{1}{m}\right)}^{kn}\approx e^{-kn/m}$$
3. Therefore, the probability that a specific bit is $1$ is: $$P(\text{bit is }1)=1-e^{-kn/m}$$
4. For an element that was not inserted, a false positive occurs when all $k$ of its computed positions happen to be set to $1$: $$p\approx {\left(1-e^{-kn/m}\right)}^k$$

Optimal Parameter Formulas

1. Optimal Number of Hash Functions ($k_{\text{opt}}$)

To minimize false positives for a given bit size $m$ and item count $n$: $$k_{\text{opt}}=\frac{m}{n}\ln 2\approx 0.693\times \frac{m}{n}$$

2. Required Bit Array Size ($m$) for Target Error Rate ($p$)

Substituting $k_{\text{opt}}=\frac{m}{n}\ln 2$ (which sets the optimal bit fill ratio to exactly $50\%$, i.e. $e^{-k_{\text{opt}}n/m}=0.5$) into $p\approx (0.5{)}^{k_{\text{opt}}}$ yields $\ln p=-k_{\text{opt}}\ln 2=-\frac{m}{n}(\ln 2{)}^2$: $$m=-\frac{n\ln p}{(\ln 2{)}^2}\approx -2.0814\cdot n\ln p$$ Converting from natural logarithm ($\ln p=\ln 2\cdot {\log }_{2}p$) to base-2 logarithm cancels one factor of $\ln 2$: $$\frac{m}{n}=-\frac{\ln p}{(\ln 2{)}^2}=-\frac{{\log }_2(p)}{\ln 2}\approx -1.4427\cdot {\log }_2(p)$$ (Sanity check at $p=0.01$: ${\log }_2(0.01)=-6.6439$, so $-1.4427\times (-6.6439)=9.585\text{ bits/key}$, i.e., $1.4427\text{ bits}$ per factor-of-2 reduction in false-positive rate, or $4.7925\text{ bits}$ per order-of-magnitude $10\times$ reduction.)

3. Sensitivity to Overfilling ($n_{\text{actual}}>n_{\text{planned}}$)

Because $m$ and $k$ are fixed at allocation time, inserting $2n$ elements into a filter sized for $n$ at $p=0.01$ ($m/n=9.585,k=7$) pushes the bit fill ratio from $50\%$ to $1-e^{-7\times 2/9.585}\approx 76.8\%$, causing the actual false-positive rate to jump nearly $16\times$: $$p_{\text{overfilled}}\approx (0.768{)}^7\approx 0.158(15.8\%\text{ vs. }1.0\%\text{ target!})$$

Quick Reference Sizing Table

Complete Worked Example

Scenario: You are designing the storage index for an e-commerce catalog with $n=100\text{ Million}$ ($10^8$) SKU records. You want to filter out queries for invalid SKUs before reading from NVMe disk, targeting a $1\%$ false-positive rate ($p=0.01$) under uniform independent hashing.

Step 1: Calculate Total Bit Array Size

$$m=-\frac{10^8\times \ln (0.01)}{(\ln 2{)}^2}=-\frac{10^8\times (-4.60517)}{0.480453}\approx 958,505,838\text{ bits}$$ $$\text{Memory}=\frac{958,505,838\text{ bits}}{8}\approx 119.81\text{ MB (decimal)}=\frac{119,813,230}{1,024^2}\approx 114.26\text{ MiB}$$

Step 2: Calculate Optimal Hash Count

Step 3: Comparison with Exact Hash Set

• Storing 100M 32-byte string keys in a standard HashSet<String>: $$100\text{M}\times (32\text{ bytes key}+8\text{ bytes hash}+8\text{ bytes pointer}+16\text{ bytes node overhead})\approx 6.4\text{ GB}$$
• Result: The Bloom Filter delivers a $56\times$ reduction in RAM consumption ($114\text{ MB}$ vs. $6.4\text{ GB}$).

6. Implementation: Production-Grade Bloom Filter in TypeScript

import crypto from 'node:crypto';

export class BloomFilterSimulation {
  private readonly sizeBits: number;
  private readonly hashCount: number;
  private readonly bitArray: Uint8Array;
  private itemCount: number = 0;

  constructor(expectedItems: number, targetFpRate: number = 0.01) {
    // Optimal bit array size m = -n * ln(p) / (ln 2)^2
    this.sizeBits = Math.ceil(
      (-expectedItems * Math.log(targetFpRate)) / (Math.LN2 * Math.LN2)
    );
    // Optimal hash function count k = (m / n) * ln(2)
    this.hashCount = Math.max(
      1,
      Math.round((this.sizeBits / expectedItems) * Math.LN2)
    );
    const byteLength = Math.ceil(this.sizeBits / 8);
    this.bitArray = new Uint8Array(byteLength);
  }

  public getParameters(): { sizeBits: number; hashCount: number; byteLength: number } {
    return {
      sizeBits: this.sizeBits,
      hashCount: this.hashCount,
      byteLength: this.bitArray.length,
    };
  }

  // Kirsch-Mitzenmacher optimization: g_i(x) = h1(x) + i * h2(x) (mod m)
  private getHashPositions(key: string): number[] {
    const digest = crypto.createHash('md5').update(key).digest();
    const h1 = digest.readUInt32BE(0);
    const h2 = digest.readUInt32BE(4);

    const positions: number[] = [];
    for (let i = 0; i < this.hashCount; i++) {
      // Use unsigned 32-bit arithmetic to prevent negative modulo
      const combined = (h1 + i * h2) >>> 0;
      positions.push(combined % this.sizeBits);
    }
    return positions;
  }

  public add(key: string): void {
    const positions = this.getHashPositions(key);
    for (const pos of positions) {
      const byteIdx = Math.floor(pos / 8);
      const bitOffset = pos % 8;
      this.bitArray[byteIdx] |= 1 << bitOffset;
    }
    this.itemCount++;
  }

  public mightContain(key: string): boolean {
    const positions = this.getHashPositions(key);
    for (const pos of positions) {
      const byteIdx = Math.floor(pos / 8);
      const bitOffset = pos % 8;
      if ((this.bitArray[byteIdx] & (1 << bitOffset)) === 0) {
        return false; // Guaranteed absence: zero false negatives!
      }
    }
    return true; // Probable presence: subject to bounded false positives
  }

  public getStats(): { itemCount: number; bitsSet: number; fillRatio: number } {
    let bitsSet = 0;
    for (let i = 0; i < this.bitArray.length; i++) {
      let b = this.bitArray[i];
      while (b > 0) {
        bitsSet += b & 1;
        b >>= 1;
      }
    }
    return {
      itemCount: this.itemCount,
      bitsSet,
      fillRatio: Math.round((bitsSet / this.sizeBits) * 1000) / 10,
    };
  }
}

export function runDemo(): void {
  console.log('=== Bloom Filter: Probabilistic Membership & SSTable Simulation ===');
  const expectedItems = 1_000;
  const targetFpRate = 0.01; // 1%
  const filter = new BloomFilterSimulation(expectedItems, targetFpRate);
  const params = filter.getParameters();

  console.log(`[Config] Sized for ${expectedItems} items @ ${(targetFpRate * 100)}% FP target:`);
  console.log(`         Bit Array Size: ${params.sizeBits} bits (${params.byteLength} bytes, ~${(params.sizeBits / expectedItems).toFixed(1)} bits/item)`);
  console.log(`         Hash Count (k): ${params.hashCount} derived hashes`);

  // Insert items
  for (let i = 0; i < expectedItems; i++) {
    filter.add(`sku-electronics-item-${i}`);
  }

  // 1. Verify zero false negatives
  let falseNegatives = 0;
  for (let i = 0; i < expectedItems; i++) {
    if (!filter.mightContain(`sku-electronics-item-${i}`)) {
      falseNegatives++;
    }
  }
  console.log(`[Validation] Tested ${expectedItems} present keys: False Negatives = ${falseNegatives} (Strict 0% invariant satisfied!)`);

  // 2. Measure empirical false positives on non-existent keys
  const testAbsentCount = 10_000;
  let falsePositives = 0;
  for (let i = 0; i < testAbsentCount; i++) {
    if (filter.mightContain(`nonexistent-random-query-key-${i}`)) {
      falsePositives++;
    }
  }

  const empiricalRate = (falsePositives / testAbsentCount) * 100;
  console.log(`[Validation] Tested ${testAbsentCount} absent keys: False Positives = ${falsePositives} (${empiricalRate.toFixed(2)}% vs ${targetFpRate * 100}% theoretical target)`);

  const stats = filter.getStats();
  console.log(`[Bit Array Telemetry] Bits Set: ${stats.bitsSet} / ${params.sizeBits} (${stats.fillRatio}% fill ratio)`);
}

runDemo();

Simulation Execution Output & State Transitions

=== Bloom Filter: Probabilistic Membership & SSTable Simulation ===
[Config] Sized for 1000 items @ 1% FP target:
         Bit Array Size: 9586 bits (1199 bytes, ~9.6 bits/item)
         Hash Count (k): 7 derived hashes
[Validation] Tested 1000 present keys: False Negatives = 0 (Strict 0% invariant satisfied!)
[Validation] Tested 10000 absent keys: False Positives = 104 (1.04% vs 1% theoretical target)
[Bit Array Telemetry] Bits Set: 4940 / 9586 (51.5% fill ratio)

7. Practical applications

8. Real-world implementation: Apache Cassandra

In Apache Cassandra:

1. Every SSTable on disk has an associated Bloom filter file stored on disk (<keyspace>-<table-name>-bti-Filter.db) and memory-mapped into OS page cache.
2. The user can configure the target false-positive rate per table:

   CREATE TABLE user_profiles (
       user_id uuid PRIMARY KEY,
       name text
   ) WITH bloom_filter_fp_chance = 0.01;

3. When a point read query (SELECT * WHERE user_id = ?) arrives:
   • Cassandra checks the active MemTable.
   • For all on-disk SSTables overlapping the token range, Cassandra queries the in-memory Bloom filter.
   • If the Bloom filter returns false, Cassandra skips reading that SSTable entirely, saving disk head seeks and NVMe bandwidth.

9. Failure modes and limitations

1. Saturation (Overfilling): A Bloom filter is dimensioned for a maximum capacity $n$. If $2n$ or $3n$ keys are inserted, the bit array becomes saturated with $1$s. The false-positive rate spikes rapidly toward $100\%$, degrading the filter into an expensive no-op.
2. CPU Cache Thrashing: Standard Bloom filters evaluate $k$ hash functions across the entire $m$-bit array. Because $m$ is many megabytes in size, each of the $k$ bit lookups causes a CPU L3 cache miss. Mitigation: Blocked Bloom Filters (Putze et al.) hash an element into a single 64-byte block (matching the CPU cache line size). All $k$ hashes execute within that single cache line, eliminating L3 cache misses.
3. No Sizing Flexibility: Once allocated, a standard Bloom filter cannot be resized. To expand capacity, a new larger filter must be created and all original elements must be re-inserted.

10. Operational perspective

What to Monitor in Production

• Bloom Filter False Positive Ratio: $$\text{False Positive Ratio}=\frac{\text{SSTables Checked where Key was Missing}}{\text{Total Filter True Responses}}$$ In Cassandra, monitor org.apache.cassandra.metrics:type=ColumnFamily,name=BloomFilterFalseRatio. If this exceeds your target (e.g. $>0.05$), the table requires rebuilding or re-tuning.
• Off-Heap Memory Footprint: Bloom filters in storage engines are typically stored in off-heap native memory. Ensure JVM max direct memory (-XX:MaxDirectMemorySize) accounts for active Bloom filters across all open SSTables.

11. Knowledge check

Complete the interactive assessment quiz at the end of this lesson to verify your mastery of asymmetric guarantees, bits-per-key sizing math, deletion hazards, and Kirsch-Mitzenmacher double hashing.

12. Exercises

Exercise 1: Sizing an SSTable Bloom Filter

• Given: An LSM storage engine produces SSTables containing $n=2\text{ Million}$ keys each. You require a false-positive rate $p\le 0.5\%$ ($0.005$).
• Deliverables:
  1. Calculate the required bit array size $m$ in bits, decimal MB, and binary MiB.
  2. Calculate the optimal number of hash functions $k_{\text{opt}}$.
  3. If your node holds $1,000$ SSTables open simultaneously, calculate total off-heap RAM consumed and compare against a Ribbon Filter ($\approx 30\%$ smaller at equivalent $p$).

Exercise 2: Quantifying Read-Amplification Savings Across Multi-Level SSTables

• Given: A storage node holds $L=12$ overlapping SSTable runs in Level 0 (L0). Point lookups for non-existent keys arrive at $20,000\text{ QPS}$, and each random NVMe 4 KiB page read takes $100\mu \text{s}$.
• Deliverables:
  1. Calculate the wasted NVMe IOPS and device bandwidth without Bloom filters vs. with a $p=1\%$ Bloom filter on each SSTable.
  2. Explain why a Blocked Bloom Filter reduces CPU L3 cache misses from $k=7$ down to $1$ per SSTable probe.

13. Design Alternatives, Trade-Offs & Summary Decision Guide

14. Authoritative References & Version Context

• Burton H. Bloom (1970), “Space/Time Trade-offs in Hash Coding with Allowable Errors”, Communications of the ACM 13(7), pp. 422–426: Original probabilistic bit-array formulation and error bounds — doi.org/10.1145/362686.362692
• Adam Kirsch and Michael Mitzenmacher (2006), “Less Hashing, Same Performance: Building a Better Bloom Filter”, ESA 2006 / Random Structures & Algorithms 33(2): Mathematical proof that two base hashes $g_i(x)=h_1(x)+i\cdot h_2(x)\mathrm{mod}m$ match $k$ independent hashes asymptotically — eecs.harvard.edu/~michaelm/postscripts/rsa2008.pdf
• Bin Fan, Dave G. Andersen, Michael Kaminsky, and Michael D. Mitzenmacher (2014), “Cuckoo Filter: Practically Better Than Bloom”, ACM CoNEXT ‘14: Deletion-capable fingerprint buckets outperforming standard Bloom filters at $p<3\%$ — doi.org/10.1145/2674005.2674994
• Peter Dillinger and Stefan Walzer (2021) / Meta RocksDB Wiki, “Ribbon Filter: Practically smaller than Bloom and Xor” (RocksDB 6.27+ / 9.x): Banded linear-system static filters saving ~30% RAM on bottommost SSTable levels — github.com/facebook/rocksdb/wiki/RocksDB-Bloom-Filter
• Apache Cassandra 5.0 Official Documentation — SSTable BTI Format & bloom_filter_fp_chance: Off-heap Filter.db configuration and BloomFilterFalseRatio JMX telemetry — cassandra.apache.org/doc/latest/cassandra/operating/bloom_filters.html
• Version Context: Storage-engine mechanics and filter comparisons reflect Meta RocksDB 8.x/9.x (format_version=5 FastLocalBloom & Ribbon filters) and Apache Cassandra 4.1 / 5.0 BTI SSTable descriptors.