Skip to main content
← CONCEPTS / ALGORITHMS & DATA STRUCTURES
An end-to-end domain learning journey

Bloom Filters, Counting Bloom
& Cuckoo Filters.

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.
Start the journey7 sections
FIRST PRINCIPLES. PRODUCTION SCALE.
The idea to keep with you

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.

Full walkthrough · 7 stages
01
STAGE 01 · THE MECHANISML4 · FUNDAMENTALS

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.

Membership Lookup Path

Two-Choice Cuckoo Bucket Lookup & Eviction

Key x -> fp8-12 bit fingerprintBucket b1 = h(x)Check 4 slotsBucket b2 =b1^h(fp)1 cache-line altKick Swap / DeleteMax 500 kicks

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.

02
STAGE 02 · THE PROBLEML4 · FUNDAMENTALS

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.

03
STAGE 03 · WHERE IT IS USEDL5 · APPLIED DESIGN

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.

04
STAGE 04 · HOW IT IS MANAGEDL5 · APPLIED DESIGN

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
05
STAGE 05 · THE TRADE-OFFL6 · SCALE & TRADE-OFFS

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.

ChoiceWhat it buysWhat it costs
Standard Bloom FilterSimple, 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.
06
STAGE 06 · PRODUCTION ARCHITECTUREL7 · STAFF / PRINCIPAL

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.

CDN Admission Shield

Filter-Guarded SSD Cache Admission Path

Edge RequestGET /blob/9481Cuckoo Filter (RAM)Seen before?Origin FetchRecord fp on 1st hitNVMe SSD CacheWrite only on 2nd hit

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.

07
STAGE 07 · APPLIED PROBLEMSL7 · STAFF / PRINCIPAL

Problems Solved by Probabilistic Filters.

See how probabilistic filters eliminate unnecessary disk and database reads in production.

Practice · Explain the consequences

Practice: Make the trade-off yourself.

Question 1 of 3
Score: 0/3

Why does deleting a key by clearing its bits in a standard Bloom filter break correctness?

Recommended Learning Flow