Bloom filters answer set membership in O(k) bit probes using ~10 bits per key at a 1% false-positive rate with zero false negatives, while Cuckoo filters store compact fingerprints in 2-choice hash buckets to support safe item deletion and better CPU cache locality.
TL;DR30-second simplified summary▾
Core Mechanics: A Bloom Filter hashes key x with k functions into a bit array (0 bit = definitely absent; all 1s = probably present with false-positive rate p). Standard Bloom filters cannot delete items. Cuckoo Filters store short f-bit fingerprints in two candidate buckets (b1 = h1(x), b2 = b1 XOR h(fp)), supporting deletion and eviction swaps.
Visual & Structural Flow: Contrasts a Bloom Filter (No Delete) (x -> h1, h2, h3 -> bit array [0|1|0|1|1|0|1]) against a Cuckoo Filter (Supports Delete) (2-choice hash buckets b1, b2 holding [fp] fingerprints with Evict & Kick Swap).
Trade-Offs & Production: At 1% false-positive rate, a Bloom filter uses ~9.6 bits/key, whereas a Counting Bloom filter uses 4x memory (4-bit counters) and risks counter overflow. Cuckoo filters use ~12.6 bits/key (or less at <3% FP) with 2 cache-line reads instead of k random probes.
Failure Modes & Application: Never exceed a Cuckoo filter's ~95% load factor (eviction loops fail inserts) and never delete a non-existent key from a Cuckoo filter if duplicate inserts are possible.
From patterns to decisions.
Choose and size Bloom, Counting Bloom, and Cuckoo filters for SSTable point lookups, cache-penetration shields, and dynamic blocklists.
How Bloom Filters & Cuckoo Filters Work.
A Bloom Filter allocates m bits and k independent hash functions. Inserting x sets bits h_1(x)...h_k(x) to 1. Querying x returns definitely absent if any bit is 0, or probably present if all k bits are 1 (false-positive rate p). Optimal sizing uses m = -(n * ln(p)) / (ln(2)^2) bits (~9.6 bits/key for p = 1%) and k = (m/n) * ln(2) (~7 probes).
A Cuckoo Filter replaces the bitset with buckets of b = 4 fingerprint slots. Each key x yields an f-bit fingerprint fp and two candidate buckets: b1 = hash(x) and b2 = b1 XOR hash(fp). Notice b1 can be computed from b2 using only fp (b1 = b2 XOR hash(fp)), allowing items to be relocated when a bucket fills and deleted by removing one matching fp.
Two-Choice Cuckoo Bucket Lookup & Eviction
1.Zero False Negatives: If neither b1 nor b2 holds fp, key x is guaranteed absent.
2.Cache Locality: Checks at most 2 buckets (2 cache lines) vs. k=7..10 random bit probes.
3.Safe Deletion: Removes 1 matching fp from b1 or b2 without affecting other keys.
Caption: Cuckoo filters use partial-key cuckoo hashing (b2 = b1 XOR h(fp)) to relocate and delete items using only the stored fingerprint.
Why You Cannot Delete From a Standard Bloom Filter.
Because multiple keys hash onto overlapping bit positions, clearing a 1 bit to 0 when deleting key_A can silently break key_B—violating the zero false negatives invariant. Meanwhile, Counting Bloom Filters replace each bit with a 4-bit counter (4x RAM overhead) and suffer counter overflow if a hot key is inserted repeatedly.
Cache Penetration Shield
Checking a filter in RAM before querying Disk/Redis rejects non-existent IDs (e.g., crawler 404 storms) in nanoseconds.
LSM-Tree SSTable Skip
RocksDB/Cassandra attach per-SSTable Bloom filters so point lookups skip 99% of disk SSTables that do not contain the key.
Where Bloom vs. Cuckoo Filters Fit Best.
Use standard Bloom filters for immutable datasets such as RocksDB/LevelDB SSTable blocks or daily batch snapshots. Use Cuckoo filters for mutable sets (session revocation lists, CDN one-hit-wonder admission caches, or active feature-flag memberships) where entries are frequently added and removed.
Sizing Bits-per-Key, Load Factor & Rebuild Thresholds.
Size Bloom filters with explicit (n, p) budgets (~10 bits/key for 1% FP, ~14.4 bits/key for 0.1% FP). For Cuckoo filters, cap occupancy at 90–95% (bucket_size = 4) and bound eviction loops (max_kicks = 500); if an insert exhausts max_kicks, trigger an asynchronous double-capacity rebuild.
import math
def bloom_sizing(expected_items: int, fp_rate: float) -> tuple[int, int]:
"""Return (num_bits, num_hashes) for target expected_items and false-positive rate."""
if expected_items <= 0 or not (0 < fp_rate < 1):
raise ValueError("expected_items must be > 0 and 0 < fp_rate < 1")
m = int(math.ceil(-(expected_items * math.log(fp_rate)) / (math.log(2) ** 2)))
k = max(1, int(round((m / expected_items) * math.log(2))))
return m, k
Bloom vs. Counting Bloom vs. Cuckoo vs. Ribbon Filters.
RocksDB's newer Ribbon Filters save ~30% RAM over Bloom filters for static immutable SSTables, while Cuckoo Filters win for dynamic sets needing deletion and 2-bucket cache locality.
| Choice | What it buys | What it costs |
|---|---|---|
| Standard Bloom Filter | Simple, zero resize failures, ~9.6 bits/key at 1% FP. | No deletion; k=7 random bit probes cause k CPU cache misses. |
| Cuckoo Filter (4-slot buckets) | Supports deletion; only 2 cache-line lookups; smaller than Bloom at <3% FP. | Inserts fail above ~95% occupancy; must not delete keys that were never inserted. |
Two-Stage CDN One-Hit-Wonder Filter + LSM SSTable Point Lookups.
CDNs use a rotating Cuckoo/Bloom admission filter in RAM: an object is only written to NVMe SSD on its second request, cutting SSD write wear by 40–60% from one-hit-wonder tails while expiring old entries cleanly via filter rotation.
Filter-Guarded SSD Cache Admission Path
1.One-Hit Shield: Prevents single-request tail objects from thrashing SSD endurance.
2.Rotating Epochs: Swap active/passive filters hourly to bound false-positive saturation.
3.O(1) Lookup: 2 bucket checks in L2/L3 CPU cache add <50ns overhead.
Caption: Guarding SSD admission with a rotating Cuckoo filter eliminates 40-60% of wasted SSD writes from one-hit-wonder objects.
Problems Solved by Probabilistic Filters.
See how probabilistic filters eliminate unnecessary disk and database reads in production.
Practice: Make the trade-off yourself.
Why does deleting a key by clearing its bits in a standard Bloom filter break correctness?