Cuckoo filters, in depth: partial-key cuckoo hashing, sizing math, a full implementation and production failure modes

The problem: membership that can shrink

Approximate membership filters sit in front of something expensive. A storage engine checks one before reading a file from disk, a crawler before fetching a URL again, a stream processor before treating an event as new. A no answer must always be right; a yes answer may occasionally be wrong, and the cost of that mistake is one wasted expensive check.

A Bloom filter sets k bits per item in a shared bit array. Bits are shared among items, so you cannot clear an item's bits without possibly clearing someone else's, which would create a false negative. Counting Bloom filters fix this with small counters per position and pay roughly four times the memory. Sets that shrink as well as grow, such as caches, sliding windows and compacted storage levels, need something better.

The problem: membership that can shrink

Approximate membership filters sit in front of something expensive. A storage engine checks one before reading a file from disk, a crawler before fetching a URL again, a stream processor before treating an event as new. A no answer must always be right; a yes answer may occasionally be wrong, and the cost of that mistake is one wasted expensive check.

A Bloom filter sets k bits per item in a shared bit array. Bits are shared among items, so you cannot clear an item's bits without possibly clearing someone else's, which would create a false negative. Counting Bloom filters fix this with small counters per position and pay roughly four times the memory. Sets that shrink as well as grow, such as caches, sliding windows and compacted storage levels, need something better.

Partial-key cuckoo hashing

The cuckoo filter stores a short fingerprint of each item, f bits of a hash, in one slot of a hash table. The table has m buckets with b slots each; b = 4 is the standard choice. Each item has two candidate buckets. Because an item occupies exactly one slot, it can be found, moved and removed.

Ordinary cuckoo hashing would compute both buckets from the item itself. A filter does not store the item, only its fingerprint, so when an entry needs to move it must be possible to find the other bucket from the fingerprint alone. Partial-key cuckoo hashing does this:

i1 = hash(x) mod m
i2 = i1 XOR (hash(fp) mod m)      # m must be a power of two
# and symmetrically: i1 = i2 XOR (hash(fp) mod m)

XOR with the same value is its own inverse, so from either bucket you can compute the other. Hashing the fingerprint before the XOR spreads alternates across the whole table instead of a small neighbourhood. The XOR form needs a power-of-two bucket count so the result stays in range. If that wastes too much memory, i2 = (hash(fp) - i1) mod m is also its own inverse and works for any m.

Insertion places the fingerprint in either bucket if one has a free slot. If both are full, it evicts a random resident fingerprint, writes the new one in its place, and moves the victim to the victim's own alternate bucket, possibly evicting again. After a bounded number of kicks, typically a few hundred, the insert gives up and reports that the filter is full.

A complete implementation

Here is a complete, readable implementation. It uses lists for clarity; a production version packs fingerprints into a bit array, but the logic is identical.

import hashlib, random

def _h(data: bytes) -> int:
    return int.from_bytes(hashlib.blake2b(data, digest_size=8).digest(), "little")

class CuckooFilter:
    def __init__(self, capacity, bucket_size=4, fp_bits=12, max_kicks=500):
        m = 1
        while m * bucket_size * 0.95 < capacity:      # target about 95% load
            m <<= 1                                    # power of two for XOR
        self.m, self.b, self.f, self.max_kicks = m, bucket_size, fp_bits, max_kicks
        self.buckets = [[] for _ in range(m)]
        self.count = 0
        self.victim = None                             # (bucket, fp) that found no home

    def _fp_and_index(self, item: bytes):
        h = _h(item)
        fp = (h >> 32) & ((1 << self.f) - 1)
        fp = fp or 1                                   # 0 is reserved for empty
        return fp, (h & 0xFFFFFFFF) % self.m

    def _alt(self, i, fp):
        return (i ^ _h(fp.to_bytes(4, "little"))) % self.m

    def insert(self, item: bytes) -> bool:
        if self.victim:
            return False                               # full until rebuilt
        fp, i1 = self._fp_and_index(item)
        i2 = self._alt(i1, fp)
        for i in (i1, i2):
            if len(self.buckets[i]) < self.b:
                self.buckets[i].append(fp); self.count += 1
                return True
        i = random.choice((i1, i2))
        for _ in range(self.max_kicks):
            slot = random.randrange(self.b)
            fp, self.buckets[i][slot] = self.buckets[i][slot], fp   # swap with victim
            i = self._alt(i, fp)
            if len(self.buckets[i]) < self.b:
                self.buckets[i].append(fp); self.count += 1
                return True
        # Full. Keep the homeless fp in a one-entry victim cache so no
        # previously inserted item is lost.
        self.victim = (i, fp)
        return False

    def contains(self, item: bytes) -> bool:
        fp, i1 = self._fp_and_index(item)
        i2 = self._alt(i1, fp)
        if self.victim and self.victim[1] == fp and self.victim[0] in (i1, i2):
            return True
        return fp in self.buckets[i1] or fp in self.buckets[i2]

    def delete(self, item: bytes) -> bool:
        # Only call for items that were definitely inserted.
        fp, i1 = self._fp_and_index(item)
        i2 = self._alt(i1, fp)
        if self.victim and self.victim[1] == fp and self.victim[0] in (i1, i2):
            self.victim = None; self.count -= 1
            return True
        for i in (i1, i2):
            if fp in self.buckets[i]:
                self.buckets[i].remove(fp); self.count -= 1
                return True
        return False

Note the comment at the failure branch. When the kick chain gives up, the fingerprint in hand belongs to some earlier item, not necessarily the new one. Dropping it would create a false negative for an item that was inserted successfully long ago. The reference implementation keeps it in a small victim cache that lookups also check.

The math: false positives, load and space

False positives. A lookup compares the fingerprint against up to 2b stored fingerprints. Each matches by chance with probability 1/2^f, so the false-positive rate is at most 1 - (1 - 2^-f)^2b, approximately 2b/2^f. With b = 4: f = 8 gives about 3.1%, f = 12 about 0.2%, f = 16 about 0.012%. Larger buckets fill better but raise the rate linearly.

Load factor. With b = 1 the table fills to only about 50% before inserts start failing; b = 2 reaches about 84%, b = 4 about 95%, b = 8 about 98%. That is why b = 4 is the usual compromise.

Space. Write the target rate as ε and let x = log₂(1/ε). The paper gives these bits per item:

Solving 1.44 x = (x + 3)/0.955 puts the crossover at about x = 8, so a plain cuckoo filter is smaller than a Bloom filter only below roughly ε = 0.4%. Semi-sorting, which sorts the four fingerprints in a bucket and encodes them more compactly, saves one bit per item and moves the crossover to roughly ε = 2 to 3%. Either way, these numbers assume a table near 95% full, and real deployments rarely are.

Worked example: 50 million keys at 0.1%

Size a filter for 50 million keys at a target rate of 0.1%. With b = 4 we need 8/2^f <= 0.001, so f = 13, which gives 8/8192, about 0.098%. At 95% load we need at least 50M / (4 x 0.95), about 13.2 million buckets.

With the XOR scheme the bucket count rounds up to 2²⁴ = 16,777,216 buckets, 67.1 million slots. At 13 bits each that is about 872 Mbit, or 109 MB, and the table is only 74.5% full at 50 million keys. That is 17.4 bits per key. A Bloom filter at 0.1% needs 14.4 bits per key, about 90 MB, and probes ten bits per lookup.

Switch to the subtraction scheme and use exactly 13.2 million buckets: 686 Mbit, about 86 MB, 13.7 bits per key, slightly better than Bloom, with semi-sorting saving another 6 MB. Alternatively, accept power-of-two sizing and spend the slack on 16-bit fingerprints: 134 MB at a rate of 0.012%, aligned to machine words. The lesson is that rounding policy can matter more than the asymptotic formula.

Where cuckoo filters sit in a system

Typical placements are a filter per storage file in a log-structured engine (deleting keys as compaction drops them instead of rebuilding), a deduplication window that inserts on first sight and deletes on expiry, and a negative cache in front of a remote lookup service. The Cassandra Bloom filter article shows the per-file pattern with a Bloom filter, which is the baseline to beat.

Redis Stack's probabilistic module exposes cuckoo filters directly:

CF.RESERVE seen:urls 10000000 BUCKETSIZE 4 MAXITERATIONS 20 EXPANSION 2
CF.ADDNX   seen:urls "https://example.com/a"    -> 1 (added) or 0 (maybe present)
CF.EXISTS  seen:urls "https://example.com/a"    -> 1
CF.DEL     seen:urls "https://example.com/a"    -> 1

Its documentation states the defaults as a bucket size of 2, 20 max iterations and an expansion factor of 1, rounds capacity to a power of two, and grows by adding sub-filters, up to 32 of them. Each extra sub-filter and each extra slot per bucket raises the false-positive rate linearly, so reserve enough capacity up front rather than relying on expansion.

Failure modes

• Deleting what was never inserted. If x was never added but shares a fingerprint and bucket with y, deleting x removes y. Later lookups for y return no: a false negative. Only delete keys you know you inserted, for example from the authoritative store.
• Duplicates. Inserting the same item repeatedly stores repeated fingerprints in the same two buckets. After 2b copies inserts fail. Use insert-if-absent unless you need multiset semantics.
• Running near full. Kick chains lengthen sharply above about 90% load. Insert latency becomes erratic before inserts fail.
• Weak hashing. Correlation between the index hash and the fingerprint bits clusters items. Take both from one strong 64-bit hash, as in the code above.
• Concurrent writers. A kick chain modifies several buckets. Readers can briefly miss an entry in flight; use a lock, striped locks or an optimistic version counter.

Operating a cuckoo filter

Export occupancy, insert failures, average and p99 kick-chain length, and the observed false-positive rate measured by sampling yes answers against the backing store. Alert at 85 to 90% occupancy and resize by building a larger filter from the source of truth, because fingerprints alone cannot be rehashed into a table of a different size without the original keys (doubling with the XOR scheme is possible only if you kept extra hash bits). Persist the filter with its parameters and hash seed, and version the format.

Trade-offs and alternatives

Cuckoo filters win when the set changes in both directions and the error rate is low. They lose when the set is static, when you cannot guarantee deletes are only for inserted keys, or when the table cannot be rebuilt from a source of truth.

What to do next

1. Write down the target false-positive rate and the cost of a false positive in your system.
2. Compute f from 2b/2^f, then the bucket count, and check how much power-of-two rounding costs you.
3. Decide how deletes are authorised so you never delete a key that was not inserted.
4. Implement or adopt a filter with a victim cache, insert-if-absent and one strong 64-bit hash.
5. Instrument occupancy, kick-chain length, insert failures and sampled false positives.
6. Write the rebuild path from the source of truth and test it before you need it.
7. Benchmark against a Bloom filter at your real error rate and memory budget before committing.