Bloom, Cuckoo & XOR Filters Compared

Three Ways to Remember Without Storing Keys

Imagine a venue that must quickly reject people whose names are definitely not on a very large guest list. Keeping the complete list at every entrance is expensive. Instead, each entrance keeps a compact summary. The summary may occasionally say “possibly present” for a person who is absent, forcing a check against the authoritative list, but it must never say “absent” for a guest who was correctly inserted.

That is the contract of an approximate membership filter. A negative answer is definitive under the stated model; a positive answer may be a false positive. Bloom, cuckoo, and XOR filters all provide this asymmetric answer, but they organize evidence differently:

• A Bloom filter sets several shared bits for every key and checks that all corresponding bits are set.
• A cuckoo filter stores a short fingerprint in one of two candidate buckets and may relocate fingerprints during insertion.
• An XOR filter stores fingerprint values in an array constructed so that the XOR of three addressed cells reproduces every member's fingerprint.

This deep dive builds on the membership-filter prerequisite. The earlier chapter establishes hashes, false positives, and no-false-negative semantics. The unresolved engineering choice is which family fits a set that is static or changing, needs deletion or not, must build incrementally or offline, and is constrained by memory, latency, construction reliability, or adversarial exposure.

For a tiny Bloom example, use $m=8$ bits and $k=2$ hash locations. Inserting A sets positions 1 and 5; inserting B sets 2 and 5. A lookup for absent C that checks 1 and 2 returns “possibly present” because both bits happen to be set. Nothing was corrupted: the shared-bit representation deliberately permits this false positive. If C checked positions 0 and 7, either zero bit would prove absence.

The core metrics require precise denominators. Bits per key is total allocated filter storage divided by successfully represented keys, including slack and metadata when comparing implementations. Load factor is occupied capacity divided by allocated slots or cells, defined differently by family. False-positive rate is the fraction of absent queries answered positive for a declared workload. Construction covers insertions, relocations, peeling, retries, and failure handling. Deletion must preserve all remaining members; removing shared evidence without sufficient counts can create false negatives.

Bloom Bits, Cuckoo Buckets and XOR Peeling

For a Bloom filter with $m$ bits, $n$ inserted keys, and $k$ ideal independent hash positions, a given bit remains zero with probability $(1-1/m)^{kn}\approx e^{-kn/m}$. An absent query is a false positive when all $k$ queried bits are one, giving

$$ p_{\mathrm{Bloom}}\approx\left(1-e^{-kn/m}\right)^k. $$

Let $c=m/n$ be bits per key. Minimizing with respect to $k$ gives $k^*=c\ln2$, rounded to a practical positive integer. At this optimum, roughly half the bits are set and

$$ p^\approx(1/2)^{c\ln2}=e^{-c(\ln2)^2}, \qquad c=-\frac{\ln p^}{(\ln2)^2}. $$

For target $p=0.01$, $c\approx9.585$ bits/key and $k\approx6.64$, so a practical design tests nearby integers, usually 7, using the exact allocated $m$ and expected $n$.

A cuckoo filter stores an $f$-bit fingerprint in one of two candidate buckets, often with $b$ slots per bucket. The alternate bucket is derived from the current bucket and fingerprint so a fingerprint can be relocated without the full key. Lookup checks at most $2b$ slots. Under a simplified uniform-fingerprint model, the false-positive probability is approximately

$$ p_{\mathrm{cuckoo}}\approx1-(1-2^{-f})^{2b}\approx\frac{2b}{2^f}. $$

With $b=4$ and target near $1\%$, the approximation suggests $f\approx10$ bits. Actual bits/key are closer to $f/\alpha$ plus metadata, where $\alpha$ is achieved slot load. Insertions can trigger eviction chains and can fail near high load; bounded retries, stash policy, resizing, and atomicity are part of the contract.

An XOR filter is built for a known static key set. Each key selects three cells, forming a 3-uniform hypergraph. Construction repeatedly removes a key incident to a degree-one cell—the peeling phase. If every key peels, reverse order assigns cell fingerprints so the XOR of the three cells equals the key fingerprint. If a nonempty core remains, construction chooses a new seed or larger array and retries. A nonmember's reconstructed $f$-bit value matches its fingerprint with probability approximately $2^{-f}$ under the model. The space is roughly array-size factor times $f$ bits per key, commonly around $1.23f$ for a suitably engineered three-location design, before metadata and alignment.

These derivations are conditional. Correlated hashes change Bloom occupancy. Short fingerprints and nonuniform buckets change cuckoo FPR. Duplicate keys must be normalized for XOR construction. A peel failure is expected probabilistic behavior, not permission to publish an invalid filter. None of the three structures is cryptographically secure by default.

flowchart TD
    A[Define n target FPR lifecycle] --> B{Set changes after build?}
    B -->|insert only or rebuildable| C[Bloom bit array]
    C --> D[Derive occupancy and optimize k]
    D --> E[All k bits set means possible]
    B -->|insert and delete| F[Cuckoo buckets and fingerprints]
    F --> G[Place in one of two buckets]
    G --> H[Relocate on collision]
    H --> I[Lookup both buckets]
    B -->|static batch| J[XOR three-cell hypergraph]
    J --> K[Peel degree-one cells]
    K --> L{All keys peeled?}
    L -->|yes| M[Reverse-assign fingerprints]
    L -->|no| N[Retry seed or resize]
    A --> X{Hash and capacity assumptions valid?}
    X -->|no| Y[Formula or construction guarantee invalid]
    X -->|yes| B
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    class A,B,C,F,J navy;
    class D,G,H,K purple;
    class E,I,M teal;
    class L,N,X,Y crimson;

False Positives, Construction and Deletion Tradeoffs

Consider $n=1{,}000{,}000$ keys and target false-positive rate $p=1\%$. The optimal Bloom formula gives $m/n=-\ln(0.01)/(\ln2)^2\approx9.585$ bits/key and $k\approx6.64$. Choosing $k=7$ and allocating $m=9{,}585{,}059$ bits yields predicted

$$ p\approx\left(1-e^{-7n/m}\right)^7\approx0.01004. $$

The bit array alone is about $1.143$ MiB. Real storage rounds words or pages and carries seed, length, count, and version metadata.

For a cuckoo design with $b=4$, fingerprint width $f=10$, and achieved load $\alpha=0.95$, fingerprint payload is about $f/\alpha\approx10.53$ bits/key. The simple lookup approximation is $1-(1-2^{-10})^8\approx0.778\%$. Bucket rounding and metadata increase space; duplicate fingerprints, insertion retries, and maximum kick count affect behavior.

For a three-location XOR design with $f=8$, ideal FPR is about $1/256\approx0.391\%$. At array factor $1.23$, fingerprint payload is about $9.84$ bits/key. It looks excellent for a static set, but the cost comparison must include the input key set during construction, peel queues, retry work, seed metadata, and rebuild deployment strategy.

Deletion separates the families sharply. Ordinary Bloom cannot clear bits safely. A counting Bloom filter replaces bits with counters and supports deletion only when increments and decrements are correct and counters do not overflow or underflow. Cuckoo deletion removes a matching fingerprint, but an API deleting a key never inserted can remove another key's colliding fingerprint and create a false negative; deployments often require an authoritative membership check or strict delete provenance. Standard XOR filters are static and normally rebuilt for changes.

from hashlib import blake2b
from math import exp, log, ceil
from random import Random

def bloom_parameters(n, target_fpr):
    if not isinstance(n, int) or n <= 0:
        raise ValueError("n must be a positive integer")
    if not 0.0 < target_fpr < 1.0:
        raise ValueError("target_fpr must lie between zero and one")
    bits = ceil(-n * log(target_fpr) / (log(2) ** 2))
    hashes = max(1, round((bits / n) * log(2)))
    predicted = (1 - exp(-hashes * n / bits)) ** hashes
    return bits, hashes, predicted

class BloomFilter:
    def __init__(self, bits, hashes):
        if bits <= 0 or hashes <= 0:
            raise ValueError("bits and hashes must be positive")
        self.bits = bits
        self.hashes = hashes
        self.array = bytearray((bits + 7) // 8)

    def _locations(self, value):
        data = str(value).encode("utf-8")
        digest = blake2b(data, digest_size=16, person=b"filter-demo").digest()
        h1 = int.from_bytes(digest[:8], "little")
        h2 = int.from_bytes(digest[8:], "little") | 1
        return [(h1 + i * h2) % self.bits for i in range(self.hashes)]

    def add(self, value):
        for location in self._locations(value):
            self.array[location // 8] |= 1 << (location % 8)

    def contains(self, value):
        return all(self.array[location // 8] & (1 << (location % 8))
                   for location in self._locations(value))

#Normal sizing and deterministic experiment.
n, target = 20_000, 0.01
bits, hashes, predicted = bloom_parameters(n, target)
filter_ = BloomFilter(bits, hashes)
inserted = [f"member-{i}" for i in range(n)]
for item in inserted:
    filter_.add(item)
assert all(filter_.contains(item) for item in inserted)

queries = 100_000
false_positives = sum(filter_.contains(f"absent-{i}")
                      for i in range(queries))
observed = false_positives / queries
print("bits/key hashes predicted observed:",
      bits / n, hashes, predicted, observed)
assert abs(observed - predicted) < 0.002

#Formula comparisons for candidate fingerprints.
bucket_slots, fingerprint_bits, load = 4, 10, 0.95
cuckoo_fpr = 1 - (1 - 2 ** (-fingerprint_bits)) ** (2 * bucket_slots)
xor_bits, xor_factor = 8, 1.23
print("cuckoo FPR and payload bits/key:",
      cuckoo_fpr, fingerprint_bits / load)
print("XOR FPR and payload bits/key:", 2 ** (-xor_bits), xor_bits * xor_factor)

#Boundary and invalid inputs.
empty = BloomFilter(64, 3)
assert not empty.contains("never-added")
for bad_n, bad_p in [(0, 0.01), (100, 0.0), (100, 1.0)]:
    try:
        bloom_parameters(bad_n, bad_p)
    except ValueError as error:
        print("invalid test passed:", error)

Filters Under Changing Production Workloads

In a teaching setting, Bloom filters make false positives visible with a small bit array. Cuckoo buckets then show how fingerprints enable relocation and deletion, while XOR peeling demonstrates that a static set can support faster, denser queries by moving complexity into construction.

In professional storage engines, immutable SSTables are an excellent fit for static filters. An XOR filter can be built alongside a newly flushed table and published atomically only after successful peeling and validation. A Bloom filter remains attractive when implementation maturity, streaming construction, or broad library support matters more than the last bits per key. The decision depends on measured negative-lookup latency, cache behavior, build throughput, retry rate, and recovery path—not payload arithmetic alone.

A dynamic cache-admission service has a different profile. It may need millions of inserts and deletes per second. A cuckoo filter offers deletion and typically few cache-line probes, but the system must monitor load factor, kick-chain tails, stash occupancy, failed inserts, and delete provenance. A scalable or layered Bloom design may be easier if deletes can be represented by epochs or rebuilds.

Adversarial use changes the threat model. An attacker who learns noncryptographic hash behavior may craft collisions, concentrate Bloom bits, trigger cuckoo relocation storms, or create repeated XOR build failures for chosen sets. A secret keyed hash can make targeting harder, but key rotation, cross-node compatibility, and denial-of-service limits still need design. Approximate filters must never authorize access: a positive is not proof of membership.

Evidence that invalidates a selection includes observed FPR above budget on production-shaped negatives, construction retry tails above deployment SLO, cuckoo load below planned capacity because of key distribution, false negatives after deletion, cross-language hash mismatch, memory above full-footprint budget, or p99 lookup regressions caused by cache misses.

flowchart TD
    A[Define set lifecycle and negative-query workload] --> B{Need incremental deletion?}
    B -->|yes| C[Cuckoo or counting Bloom candidate]
    B -->|no| D{Static keys available before build?}
    D -->|yes| E[XOR and Bloom candidates]
    D -->|no| F[Bloom or layered candidate]
    C --> G[Size load fingerprints and failure policy]
    E --> H[Size FPR array factor and retry workspace]
    F --> I[Size m n k and growth headroom]
    G --> J[Benchmark construction updates lookup deletion]
    H --> J
    I --> J
    J --> K{Full-footprint SLOs pass?}
    K -->|no| L[Reject resize or change family]
    K -->|yes| M[Deploy shadow verification and monitoring]
    M --> N{FPR load retries or false negatives breach?}
    N -->|yes| L
    N -->|no| M
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    class A,B,D navy;
    class C,E,F,G,H,I purple;
    class J,M teal;
    class K,L,N crimson;

Benchmark the Right Membership Filter

The correct benchmark starts with the decision avoided by a negative answer. A filter that is marginally faster but produces more false positives may increase total latency if backing-store misses are expensive. Conversely, extra memory may be worthwhile when it prevents network or disk work. Measure the whole path with actual positive/negative mix, cardinality growth, CPU cache, allocator, construction, retries, and serialization.

This topic bridges backward to hashing and approximate membership guarantees. It leads forward to LSM-tree filter policies, learned filters, quotient and fuse filters, cache-aware layouts, adversarial hashing, and multi-level FPR budgeting. The durable skill is not memorizing a winner; it is mapping lifecycle and failure contracts to a measured design.