Bloom Filters & Counting Filters

1. What It Is & Why It Exists

The Core Problem

In distributed storage engines, caching tiers, web crawlers, and high-velocity security gateways, verifying whether an element exists before executing a costly operation is a foundational requirement. However, naive approaches to set membership fail severely at cloud scale:

• The Memory Exhaustion Trap (Hash Sets): Storing raw keys in an in-memory hash table (e.g., std::unordered_set, Java HashSet, or Redis SADD) requires storing the entire key string plus object pointers and hash bucket metadata. For an index of $1\text{ Billion}$ 32-byte keys (such as UUIDs, URL hashes, or credit card digests), a standard hash set consumes $64\text{ to }128\text{ GB of RAM}$, making in-memory caching economically unviable.
• The Disk I/O Bottleneck (Negative Search Penalty): In log-structured storage engines (LSM-trees like RocksDB or Apache Cassandra), reading a key that does not exist is the most expensive operation possible. The engine must scan the active MemTable and sequentially search through multiple levels of on-disk SSTables (Sorted String Tables) across NVMe/SSD storage before definitively confirming that the record is absent.
• Cache Penetration Attacks: Malicious actors deliberately query millions of non-existent entity IDs (e.g., /users/-1, /products/invalid_uuid). Because these keys never exist in Redis caches, 100% of requests bypass the caching layer and hit downstream databases directly, causing connection pool exhaustion and database collapse.

The Breakdown: The Negative Lookup Penalty & Hash Table Bloat

Concrete Proof: In-Memory Set vs. Raw Disk Scan vs. Bloom Filter

Consider a distributed datastore processing $100,000\text{ QPS}$, where $80\%$ of queries request non-existent keys (e.g., ad fraud checks, blacklist checks, or cache penetration):

---

The First-Principles Solution: Probabilistic Set Membership

A Bloom Filter is a space-efficient, bit-level probabilistic data structure designed by Burton Howard Bloom in 1970. It answers set membership queries with mathematical guarantees:

• Definitive Negative ($0\%$ False Negatives): If the filter returns false, the element is definitely NOT in the set ($P(\text{Negative} \mid x \notin S) = 1.0$). Downstream disk or database lookups can be skipped entirely with complete safety.
• Probabilistic Positive (Tunable False Positives): If the filter returns true, the element is probably in the set. A small, mathematically controlled fraction $p$ (e.g., $1\%$ or $0.1\%$) of negative elements may return true, causing an unnecessary disk read but never returning corrupted or missing data.
• Key-Length Invariant: Memory consumption depends strictly on the number of items ($n$) and desired error rate ($p$), completely independent of the size of the key strings being indexed.

Synthesizing vector architecture diagram...

Both panels answer a lookup for a key that does not exist. In the "Broken Baseline" panel, the read misses the MemTable in RAM and then has to open the L0, L1 and L2 SSTables on disk one after another, because only after checking every level can the engine be sure the key is absent: 3 disk reads to return 404. In the "Production Standard" panel, the read asks a Bloom filter in RAM first; FALSE is guaranteed correct (Bloom filters never give false negatives), so the engine returns 404 from RAM with zero disk reads, and only TRUE ("probably present") leads to a targeted disk read. Lookups for missing keys are very common (existence checks, cache misses), so this filter removes most of the disk work.

---

2. Core Mechanics & Algorithmic Architecture

A Tiny Worked Example: Tracing Insertions and Queries Bit by Bit

Before the general math below, it helps to trace a Bloom filter small enough to hold in your head. Use a toy filter with $n = 2$ (we will insert 2 elements), $m = 8$ (an 8-bit array, indices 0 through 7), and $k = 2$ hash functions ($h_1$ and $h_2$).

Initial State (Empty Filter)

An 8-bit array, every bit starting at 0:

textCopy
[ 0, 0, 0, 0, 0, 0, 0, 0 ]

Step 1 — Inserting Elements

Insert "apple": hashing the word through both functions gives $h_1(\text{"apple"}) \bmod 8 = 2$ and $h_2(\text{"apple"}) \bmod 8 = 5$. Flip bits 2 and 5 to 1:

textCopy
[ 0, 0, 1, 0, 0, 1, 0, 0 ]   (bits 2 and 5 set)

Insert "banana": this word's hashes are $h_1(\text{"banana"}) \bmod 8 = 5$ — notice this collides with the bit "apple" already set — and $h_2(\text{"banana"}) \bmod 8 = 7$. Bit 5 was already 1, so it stays 1; flip bit 7 to 1:

textCopy
[ 0, 0, 1, 0, 0, 1, 0, 1 ]   (bits 2, 5, and 7 now set)

Step 2 — Querying the Filter

Query "apple" (an item actually in the set): $h_1(\text{"apple"}) \bmod 8 = 2 \to$ bit is 1; $h_2(\text{"apple"}) \bmod 8 = 5 \to$ bit is 1. Both bits are 1, so the filter returns True — a True Positive.

Query "cherry" (an item never inserted): $h_1(\text{"cherry"}) \bmod 8 = 1 \to$ bit is 0. The very first check already hit a 0, so the filter can stop immediately and return False without even computing $h_2$ — it is mathematically impossible for "cherry" to be in the set, because if it were, bit 1 would have been flipped to 1 at insert time. This is a Definitive True Negative, and it is exactly what saves a downstream database from a wasted disk read.

Query "grape" (the false-positive trap): this word was never inserted either, but watch what happens when its hashes happen to land on bits other words already set: $h_1(\text{"grape"}) \bmod 8 = 2 \to$ bit is 1 (set earlier by "apple"); $h_2(\text{"grape"}) \bmod 8 = 7 \to$ bit is 1 (set earlier by "banana"). Every bit the query checks is 1, so the filter returns True — a False Positive. A real system would now perform a disk read only to discover "grape" was never actually stored.

---

Mathematical Foundations of Bloom Filters

A standard Bloom filter represents a set $S = \{x_1, x_2, \dots, x_n\}$ of $n$ elements using a bit array of $m$ bits, initially all set to 0, and $k$ independent, uniformly distributed non-cryptographic hash functions $h_1, h_2, \dots, h_k$ mapping keys to indices in $[0, m - 1]$.

1. Bit Setting Probability

When inserting an element, each hash function sets a bit to 1. The probability that a specific bit is not set by a specific hash function during one insertion is:

$$P(\text{bit remains } 0) = 1 - \frac{1}{m}$$

After inserting $n$ elements, with each element setting $k$ bits, the probability that a given bit remains 0 is:

$$P(\text{bit is } 0 \text{ after } n \text{ insertions}) = \left(1 - \frac{1}{m}\right)^{kn} \approx e^{-\frac{kn}{m}}$$

Consequently, the probability that a bit has been set to 1 is:

$$\rho = P(\text{bit is } 1) \approx 1 - e^{-\frac{kn}{m}}$$

2. False Positive Probability ($p$)

A false positive occurs when querying an element $y \notin S$ whose $k$ computed hash indices all happen to be already set to 1 by other elements:

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

3. Optimal Number of Hash Functions ($k^*$)

To minimize $p$ for a fixed bit-array size $m$ and item count $n$, take the derivative with respect to $k$ and set to zero:

$$k^* = \frac{m}{n} \ln 2 \approx 0.69315 \cdot \frac{m}{n}$$

At this optimal $k^*$, the probability of any bit being 1 is exactly $\rho = 0.5$ (half of the bit array is populated with 1s).

4. Required Bit Array Sizing Formula ($m$)

Substituting $k^*$ back into the false positive equation yields the exact relationship between capacity $n$, error probability $p$, and required bits $m$:

$$m = -\frac{n \ln p}{(\ln 2)^2} \approx -1.4427 \cdot n \cdot \log_2 p$$ $$\frac{m}{n} = -\frac{\ln p}{(\ln 2)^2} \approx -2.0814 \cdot \ln p$$

---

The Kirsch-Mitzenmacher Optimization (Two-Hash Generation)

Computing $k$ distinct hash functions (e.g., evaluating 7 separate MurmurHash3 passes) imposes heavy CPU serialization penalties on query paths. Modern high-performance systems employ the Kirsch-Mitzenmacher Technique (Harvard, 2006):

$$g_i(x) = \left(h_1(x) + i \cdot h_2(x)\right) \pmod m, \quad \text{for } i = 0, 1, \dots, k - 1$$

By computing a single 128-bit hash (e.g., Murmur3 or xxHash128) and splitting it into two 64-bit halves ($h_1$ and $h_2$), an arbitrary number $k$ of hash coordinates can be generated with one multiply and add each, with zero asymptotic loss in false positive accuracy (the coordinates aren't independent, but the paper proves the false positive rate converges to the standard one).

---

In-Memory State Representation & Bit Storage

In high-performance C++, Java, or Go runtimes, the bit array is packed into an array of 64-bit unsigned integers (uint64_t[] or long[]):

---

State-Transition Trace: Probabilistic Membership & Collision Dynamics

Under configuration $m = 16\text{ bits}$, hash count $k = 3$, and initial bit array 0000 0000 0000 0000:

---

Filter Variants: Beyond the Standard Bloom Filter

Standard Bloom filters do not support deletion, because resetting a bit to 0 may inadvertently delete other keys sharing that bit. Modern distributed systems use three primary variants:

Synthesizing vector architecture diagram...

Read each panel as "what is stored" to "what that allows". In the "Standard Bloom Filter" panel, each position is a single bit shared by many keys, so clearing a bit to delete one key could erase evidence of others; that is why delete is not supported. In the "Counting Bloom Filter" panel, each position is a small counter (4 bits), so adding increments it and deleting decrements it, at about 4 times the memory. In the "Cuckoo Filter" panel, each key stores a short fingerprint in one of two possible buckets (moving existing fingerprints aside when a bucket is full), so deleting just removes that fingerprint, and it is often smaller than a counting filter. Use a standard filter for data that only grows, and a counting or cuckoo filter when items expire or get removed.

Comparison of Advanced Probabilistic Filters

---

State-of-the-Art Alternatives: XOR & Ribbon Filters

Standard, Blocked, Counting, and Cuckoo filters all share one structural cost: they are built incrementally, one insertion at a time, which forces them to over-provision bits to absorb the randomness of online hashing. A newer generation of static probabilistic filters instead solves a satisfiability problem once, offline, over the entire key set, trading construction flexibility for a meaningfully smaller steady-state memory footprint.

• XOR Filters (Graf & Lemire, 2019) represent each key as the XOR of three fixed pseudo-random array slots, discovered by a peeling algorithm — a variant of the same technique used to decode Cuckoo hashing chains — that finds an ordering in which every key has at least one slot no other remaining key uses. Because query time only ever XORs exactly three fixed positions together (with zero branching, no early-exit loop, and no popcount), XOR filters with 8-bit fingerprints use $9.84$ bits/key ($8 \times 1.23$) at $p \approx 0.39\%$, about $15\%$ less memory than a standard Bloom filter at the same error rate ($11.5$ bits/key), with faster and more branch-predictable queries. The trade-off is that a XOR filter is immutable once built: it cannot support incremental inserts or deletes, so it is only viable for datasets that are fully known upfront and rebuilt in batch (e.g., compiling a static blocklist or a read-only reference dictionary at deploy time).
• Ribbon Filters (Dillinger & Walzer / Meta Engineering, 2021) push the same static-construction idea further using a banded matrix (Gaussian elimination over $\text{GF}(2)$) instead of XOR-peeling: each key's fingerprint bit becomes one row of a sparse banded linear system, solved once at build time so that querying reduces to a single dot-product over a small, sequential band of the solved matrix. This banded structure packs even tighter than XOR filters — the Ribbon paper reports space overheads below $10\%$ over the information-theoretic lower bound (at some extra CPU), and RocksDB's implementation delivers $\approx 30\%$ less memory than its Bloom filter at the same target error rate. The cost is asymmetric: construction is meaningfully slower than a Bloom or XOR filter (solving the banded linear system is more expensive than XOR-peeling or simple bit-setting), so Ribbon filters are the right choice when a filter is built rarely relative to how often it is queried — which is exactly the access pattern of an immutable LSM-tree SSTable, read millions of times between the one compaction pass that rebuilds its filter.

---

3. Data Migration, Anti-Entropy & Consistency Protocols

In distributed engines, Bloom filters operate as derived, immutable acceleration metadata tightly bound to storage partitions or log-structured storage files:

1. LSM-Tree SSTable Lifecycle & Regeneration

Bloom filters are not updated via cross-node data migration. Instead, they are generated deterministically during SSTable write cycles:

• Immutable Flush: When a MemTable in RAM fills up (e.g., reaches 64 MB), it is frozen and flushed to disk as an immutable SSTable file. During the flush pass, a dedicated Bloom filter is computed for all keys in that SSTable and written into the file as a filter block (the fixed-size footer at the end of the file points to it through the index of meta blocks). Because the filter is sized from the file's own key count, it can't be over-filled later.
• Compaction Re-Generation: During background Leveled or Size-Tiered Compaction, the engine merges multiple SSTables, discards overwritten versions (and tombstones, once nothing older can exist below them), and streams a brand-new, pristine Bloom filter for the newly consolidated SSTable.
• Zero Anti-Entropy Drift: Each filter is derived from its own immutable file, so it never needs repair; each replica builds filters from its own files, and nothing ever compares them across replicas.

Synthesizing vector architecture diagram...

2. Distributed Anti-Entropy: Summary Cache & Cache Digests

In distributed web caches (the Summary Cache protocol; Squid's Cache Digests), nodes share their cached URL inventories as Bloom filters:

• Instead of asking every peer about every miss (the older Internet Cache Protocol, ICP), each node periodically publishes a Bloom filter of the URLs it holds to its peers.
• Peers query their local copy of peer filters before issuing cross-node cache-fetch requests. The Summary Cache paper (SIGCOMM 1998) measured 25 to 60 times fewer inter-cache messages than ICP and over $50\%$ less bandwidth, at almost the same hit ratio.

3. Distributed Bit-Vector Delta Sync & Atomic Double-Buffering

• Monotonic Bit-Vector Delta Synchronization: In peer-to-peer synchronization of filters that share the same $m$, $k$ and hash functions (e.g., network proxy cache routing), nodes merge bit arrays via bitwise OR ($B_{\text{local}} \gets B_{\text{local}} \lor B_{\text{remote}}$); the result is the filter of the union of both sets. Because bitwise OR is monotonic, associative, and commutative, partial network partitions or out-of-order deliveries can never create false negatives (an element once marked present remains present across all merges).
• Atomic Hot-Swapping & Memory Reclamation (RCU): In-memory filters rotating due to saturation ($\text{popcount}/m > 0.5$) or daily TTL windows employ double-buffering governed by atomic pointer swaps (std::atomic<BloomFilter*>). Live reader threads read from the active pointer without mutex locks; the writer thread constructs the replacement filter offline and swaps pointers atomically via compare_exchange_strong. Old bitmaps are deferred-freed using epoch-based memory reclamation (e.g., RCU or shared_ptr), guaranteeing zero segmentation faults from concurrent reads.

---