How to Build a Cuckoo Filter in Python So a Fast Membership Check Can Forget Deleted Items

Programs ask the same slow question over and over. Does this coupon code exist? Has this URL been crawled already? Is this username taken? The true answer lives in a database, on a disk or across a network, and every lookup costs time. A membership filter is a small structure kept in memory in front of that slow lookup. It answers one question cheaply: is this item definitely not in the set? Most of the time the answer is a fast “definitely not”, and the slow lookup never happens.

The best-known membership filter is the Bloom filter, and it has one famous limit. You can add items, but you can never remove them (the Bloom filter tutorial on this site builds one). A cuckoo filter, introduced by Bin Fan, David Andersen, Michael Kaminsky and Michael Mitzenmacher in 2014, answers the same question in a similar amount of memory and adds deletion. In this tutorial you will build one from scratch in about 120 lines of standard-library Python, test it, measure it against a Bloom filter, and put it in front of a coupon table.

You will also break it on purpose, four different ways. Deletion is where a cuckoo filter turns dangerous: used carelessly, it quietly forgets items that really are in the set, and then the filter’s main promise, that a “no” always means no, stops being true. Each failure is reproduced below with real numbers, next to the guard that prevents it.

What a membership filter promises

Four terms appear all the time, so here they are once:

• Hash function: a function that turns any item into a fixed-size number. The same item always gives the same number, and different items give numbers that look random.
• False positive: the filter says an item is present, but it was never added. A filter is allowed to do this, rarely. The caller simply does the slow lookup and finds out.
• False negative: the filter says an item is absent, but it was added. A filter must never do this. A gatekeeper that turns away real items is broken, not “approximate”.
• Fingerprint: a few bits taken from an item’s hash. A cuckoo filter stores the fingerprint instead of the item, and that is why it is small.

Three ideas that make a cuckoo filter work

Idea 1: keep a fingerprint, not the item. Twelve bits per item cost far less memory than a whole coupon code. The price is that two different items can share a fingerprint, and then the filter cannot tell them apart. Shared fingerprints are the source of every false positive.

Idea 2: give each item two possible buckets. A bucket is a small group of slots, four in this tutorial, and each slot holds one fingerprint. A lookup only ever checks an item’s two buckets, at most eight slots, no matter how many items the filter holds.

Idea 3: when both buckets are full, kick someone out. The name comes from cuckoo hashing, which borrows the habit of the cuckoo bird, whose chick pushes the other eggs out of the nest. The new fingerprint takes a random slot in one of its buckets and shoves the old occupant out. The evicted fingerprint moves to its own other bucket, and if that bucket is full too, it shoves someone else out, and so on. The chain ends when a fingerprint lands in an empty slot, or when the filter gives up after a fixed number of kicks. Because every fingerprint has two homes to choose from and each home holds four fingerprints, a table can be filled to roughly 95 percent before an insert fails (Step 4 measures this).

The catch, and the XOR trick that solves it

When a fingerprint is kicked out, the filter holds only the fingerprint. The original item is gone, so the filter cannot hash it again to find the other bucket. The paper’s answer is partial-key cuckoo hashing: the second bucket is computed from the first bucket and the fingerprint alone, as bucket2 = bucket1 XOR hash(fingerprint).

XOR (“exclusive or”) compares two numbers bit by bit and gives a 1 wherever the bits differ. Its useful property is that XOR with the same number twice undoes itself. If bucket 136 XOR 23 gives bucket 159, then 159 XOR 23 gives 136 again. So from either bucket you can reach the other one using only the fingerprint, which means a kicked-out fingerprint can always find its second home. You will see those exact numbers in Step 1.

Prerequisites

• Python 3.13 or newer. I used Python 3.13.14 on Windows 11. Linux and macOS behave the same. Where I write python, use python3 if that is your command name. The filter itself needs only the standard library.
• pytest 9.1.1 for the tests (pip install pytest==9.1.1).
• Basic Python: functions, classes, lists and loops. Bit operations are explained where they first appear.
• About an hour to read and run everything. The slowest step takes well under a minute.

Create an empty folder called cuckoo_lab and work inside it. Every file in this tutorial goes in that folder, and every command assumes you run it from there. A fresh virtual environment keeps things tidy:

python -m venv .venv
# Windows: .venv\Scripts\activate    Linux or macOS: source .venv/bin/activate
pip install pytest==9.1.1

The numbers in this tutorial come from those runs. Every step is seeded and uses fixed item names, so on Python 3.13 you should see the same digits. Only timings will differ.

Step 1: Turn an item into a fingerprint and two buckets

Create cuckoo.py. This first part of the file sets up the filter and answers the central question: given an item, which fingerprint do we store, and in which two buckets can it live?

"""cuckoo.py: a cuckoo filter with deletion, after Fan, Andersen, Kaminsky and Mitzenmacher (CoNEXT 2014)."""
import hashlib
import random
from array import array

MIX = 0x5BD1E995  # the multiplier the authors' C++ code uses to spread a fingerprint over the buckets


def next_power_of_two(n):
    return 1 << max(0, (n - 1).bit_length())


class CuckooFilter:
    """Each item is kept as a short fingerprint in one of two buckets. Fingerprint 0 marks an empty slot."""

    def __init__(self, capacity, fingerprint_bits=12, bucket_size=4, max_kicks=500, seed=1,
                 undo_on_failure=True, num_buckets=None):
        if not 1 <= fingerprint_bits <= 32:
            raise ValueError("fingerprint_bits must be between 1 and 32")
        if num_buckets is None:
            num_buckets = next_power_of_two(max(1, capacity // bucket_size))
            if capacity / (num_buckets * bucket_size) > 0.96:
                num_buckets *= 2  # the authors' code does the same when the table would be over 96 percent full
        if num_buckets & (num_buckets - 1):
            raise ValueError("num_buckets must be a power of two")
        self.f = fingerprint_bits
        self.b = bucket_size
        self.m = num_buckets
        self.mask = num_buckets - 1
        self.max_kicks = max_kicks
        self.undo_on_failure = undo_on_failure
        self.rng = random.Random(seed)
        self.table = array("H" if fingerprint_bits <= 16 else "I", [0]) * (self.m * self.b)
        self.count = 0

    # --- where does an item live? ---
    def _reduce(self, x):
        return x & self.mask

    def _locate(self, item):
        """Return (fingerprint, first bucket) for an item."""
        if isinstance(item, str):
            item = item.encode("utf-8")
        elif not isinstance(item, (bytes, bytearray)):
            raise TypeError("items must be str or bytes")
        h = int.from_bytes(hashlib.blake2b(item, digest_size=8).digest(), "little")
        fp = h & ((1 << self.f) - 1)
        if fp == 0:
            fp = 1
        return fp, self._reduce(h >> 32)

    def _alt(self, i, fp):
        """The other bucket for a fingerprint. XOR is its own inverse, so alt(alt(i)) == i."""
        return self._reduce(i ^ (fp * MIX))

Here is what each piece does and why:

• __init__ chooses the size of the table. You pass the number of items you expect (capacity). It divides by the bucket size, rounds up to a power of two, and doubles the result if the table would be more than 96 percent full at that capacity. That is the same rule the authors’ C++ code uses. The table is one flat array of unsigned integers, one slot per fingerprint, and a slot holding 0 means empty. The other parameters are the fingerprint size in bits, the bucket size (4), the kick limit (500, the value used in the paper and in the authors’ code), a random seed so that runs repeat exactly, and two switches that later steps use.
• _locate hashes the item with BLAKE2b, a hash function in Python’s hashlib module, asking for a 64-bit (8-byte) digest. The low bits become the fingerprint and the top 32 bits become the first bucket. Because 0 marks an empty slot, a fingerprint of 0 is changed to 1. The authors’ code does the same. It makes fingerprint 1 slightly more likely than the others, which does no harm.
• _alt is the XOR trick. It multiplies the fingerprint by a constant to spread it over many bucket numbers, XORs the result with the current bucket, and keeps the low bits. The constant 0x5BD1E995 is the one in the authors’ code, where a comment says it is the hash constant from MurmurHash2.
• _reduce keeps a bucket number inside the table with a bit mask. A mask works only when the number of buckets is a power of two, which is why the constructor insists on one. Step 5 shows what happens without that rule.

Do not swap hashlib for Python’s built-in hash(). For strings and bytes, the Python documentation says the built-in values are “not predictable between repeated invocations of Python”, so a filter built in one run would give wrong answers after a restart.

Now look inside the filter. Create step01_locate.py:

"""step01_locate.py: where does an item live? A fingerprint, a first bucket and a second bucket."""
from cuckoo import CuckooFilter

flt = CuckooFilter(capacity=1000, fingerprint_bits=12)
print(f"buckets: {flt.m}, slots per bucket: {flt.b}, fingerprint bits: {flt.f}")
for name in ["[email protected]", "[email protected]", "SUMMER-2026-0001"]:
    fp, i1 = flt._locate(name)
    i2 = flt._alt(i1, fp)
    back = flt._alt(i2, fp)
    print(f"{name:18} fingerprint={fp:4} (0x{fp:03x})  bucket1={i1:3}  bucket2={i2:3}  (XOR of the two: {i1 ^ i2:2})  bucket2 leads back to {back:3}")

broken = sum(1 for i in range(flt.m) for fp in (1, 77, 4095) if flt._alt(flt._alt(i, fp), fp) != i)
print(f"round trips that fail to return to the start ({flt.m} buckets x 3 fingerprints): {broken}")

python step01_locate.py

buckets: 512, slots per bucket: 4, fingerprint bits: 12
[email protected]  fingerprint= 507 (0x1fb)  bucket1=136  bucket2=159  (XOR of the two: 23)  bucket2 leads back to 136
[email protected]    fingerprint=2855 (0xb27)  bucket1=394  bucket2=313  (XOR of the two: 179)  bucket2 leads back to 394
SUMMER-2026-0001   fingerprint= 401 (0x191)  bucket1=191  bucket2=218  (XOR of the two: 101)  bucket2 leads back to 191
round trips that fail to return to the start (512 buckets x 3 fingerprints): 0

Read the output line by line. A capacity of 1,000 produced 512 buckets: 1,000 divided by 4 is 250, which rounds up to 256 buckets, but 1,000 items in 256 buckets of 4 slots would be 97.7 percent full, above the 96 percent limit, so the table doubled to 512. Each name got a 12-bit fingerprint (between 1 and 4,095) and two bucket numbers between 0 and 511. For [email protected] the buckets are 136 and 159, and 136 XOR 159 is 23, the number printed in parentheses. XOR with 23 turns 136 into 159 and 159 back into 136, which is what the last column shows. The final line tests that property for every bucket and three fingerprints, and it must say 0.

Step 2: Add, look up and remove items

Now the three operations. Append the next block to cuckoo.py, inside the class and directly after _alt. The comment on its first line only marks where it continues.

    # cuckoo.py (continued)
    def _bucket(self, i):
        return self.table[i * self.b:(i + 1) * self.b]

    def _put(self, i, fp):
        for s in range(i * self.b, (i + 1) * self.b):
            if self.table[s] == 0:
                self.table[s] = fp
                return True
        return False

    # --- the three operations ---
    def add(self, item):
        """Store one copy of the item. Returns False when the filter is too full to take it."""
        fp, i1 = self._locate(item)
        i2 = self._alt(i1, fp)
        if self._put(i1, fp) or self._put(i2, fp):
            self.count += 1
            return True
        undo = []  # every swap is logged so that a failed insert can be taken back
        i = self.rng.choice((i1, i2))
        for _ in range(self.max_kicks):
            s = i * self.b + self.rng.randrange(self.b)
            undo.append((s, self.table[s]))
            fp, self.table[s] = self.table[s], fp  # the new fingerprint moves in, the old one is kicked out
            i = self._alt(i, fp)  # the kicked-out fingerprint goes to its other bucket
            if self._put(i, fp):
                self.count += 1
                return True
        if self.undo_on_failure:
            for s, old in reversed(undo):
                self.table[s] = old
        return False

Take add slowly, because it holds the cuckoo idea:

1. Try the easy homes first. _put scans a bucket for an empty slot (a 0) and writes the fingerprint there. add tries the first bucket, then the second. Most inserts end here.
2. Otherwise start kicking. Pick one of the two full buckets at random, pick a random slot in it, and swap: the new fingerprint goes into the slot and the old one comes out. The line fp, self.table[s] = self.table[s], fp is that swap.
3. Send the evicted fingerprint home. _alt(i, fp) gives the evicted fingerprint’s other bucket. If that bucket has an empty slot, we are done. If not, go back to step 2 with the next victim.
4. Give up after max_kicks. A table that is too full could kick forever. After 500 swaps add returns False. Before it does, it replays the saved undo list backwards to put every fingerprint back where it was. Why that matters is the first trap in Step 5.

Now add the rest of the class:

    # cuckoo.py (continued)
    def __contains__(self, item):
        fp, i1 = self._locate(item)
        i2 = self._alt(i1, fp)
        return fp in self._bucket(i1) or fp in self._bucket(i2)

    def remove(self, item):
        """Delete one copy of the item's fingerprint. Only safe for an item that is really stored."""
        fp, i1 = self._locate(item)
        for i in (i1, self._alt(i1, fp)):
            for s in range(i * self.b, (i + 1) * self.b):
                if self.table[s] == fp:
                    self.table[s] = 0
                    self.count -= 1
                    return True
        return False

    # --- bookkeeping ---
    def __len__(self):
        return self.count

    @property
    def slots(self):
        return self.m * self.b

    @property
    def load_factor(self):
        return self.count / self.slots

    def bits_per_item(self):
        """Table size in bits (fingerprint bits x slots, as if tightly packed) divided by the items stored."""
        return self.f * self.slots / self.count if self.count else float("nan")

The in operator (the __contains__ method) computes the item’s fingerprint and two buckets and checks whether the fingerprint is in either one. That is at most eight comparisons. remove finds one matching fingerprint in either bucket and erases it. The last few members report the size and the memory cost. bits_per_item counts fingerprint bits as if they were packed tightly, so a 12-bit fingerprint costs 12 bits. The Python array really uses 16 bits per slot for fingerprints up to 16 bits. The authors’ C++ code packs each four-slot bucket into (bits times 4, plus 7) divided by 8 bytes, which is 6 bytes for 12-bit tags, and the paper’s space numbers assume that packing.

Next, a small helper file that the step scripts share. Create labkit.py. It makes made-up item names such as user-0 and user-1, and it measures a false positive rate:

"""labkit.py: tiny helpers shared by the step scripts."""


def names(tag, count, start=0):
    """Deterministic made-up item names: tag-0, tag-1, ..."""
    return [f"{tag}-{i}" for i in range(start, start + count)]


def false_positive_rate(flt, tag, probes):
    """Share of never-added names that the filter wrongly reports as present."""
    return sum(1 for name in names(tag, probes) if name in flt) / probes

Now try the filter. Create step02_use_it.py:

"""step02_use_it.py: add, look up and remove items, then read the filter's own numbers."""
from cuckoo import CuckooFilter
from labkit import names, false_positive_rate

flt = CuckooFilter(capacity=6_000, fingerprint_bits=12)
members = names("user", 6_000)
for name in members:
    assert flt.add(name)
print(f"items stored: {len(flt):,} | buckets: {flt.m:,} | load factor: {flt.load_factor:.3f} | bits per item: {flt.bits_per_item():.2f}")
print("every stored item is found:", all(name in flt for name in members))
print(f"false positive rate over 200,000 strangers: {false_positive_rate(flt, 'stranger', 200_000):.4%}")

gone = members[:1_000]
print("removed 1,000 items:", all(flt.remove(name) for name in gone), f"| stored now: {len(flt):,}")
print("removed items still reported present:", sum(1 for name in gone if name in flt), "of 1,000")
print("untouched items all still present:", all(name in flt for name in members[1_000:]))

python step02_use_it.py

items stored: 6,000 | buckets: 2,048 | load factor: 0.732 | bits per item: 16.38
every stored item is found: True
false positive rate over 200,000 strangers: 0.1470%
removed 1,000 items: True | stored now: 5,000
removed items still reported present: 1 of 1,000
untouched items all still present: True

What each line tells you:

• Load factor 0.732. 6,000 items in 2,048 buckets of 4 slots is 8,192 slots, so about 73 percent are used. The 16.38 bits per item is 12 fingerprint bits divided by that load.
• Every stored item is found. That is the no-false-negatives promise at work.
• A false positive rate of 0.1470 percent. Out of 200,000 names that were never added, 294 were wrongly reported present. The paper bounds the rate at about 2b/2^f, where b is the bucket size and f the fingerprint bits. Here that is 8 divided by 4,096, or 0.195 percent. The table is only 73 percent full, so about 0.143 percent is expected, and the measurement agrees.
• Removing 1,000 items dropped the count from 6,000 to 5,000. One removed item was still reported present. That is a false positive of the ordinary kind: another stored item shares its fingerprint and buckets. It happens about once in 1,000 tries at this load.
• The untouched items are all still present, so removing one item did not disturb the others.

Step 3: Measure the false positive rate and the memory cost

A cuckoo filter is only interesting if it is small and accurate. To judge that fairly, compare it with a Bloom filter that gets exactly the same number of bits. Create bloom.py, a compact Bloom filter that derives its k bit positions from one hash (a standard trick called double hashing):

"""bloom.py: a small Bloom filter, used only to compare memory against the cuckoo filter."""
import hashlib
import math


class BloomFilter:
    def __init__(self, bits, hashes):
        self.m = bits
        self.k = hashes
        self.array = bytearray((bits + 7) // 8)

    @classmethod
    def for_budget(cls, items, bits_per_item):
        """A filter with `bits_per_item` bits for each of `items` items and the best whole number of hashes."""
        bits = round(items * bits_per_item)
        return cls(bits, max(1, round(bits / items * math.log(2))))

    def _hashes(self, item):
        if isinstance(item, str):
            item = item.encode("utf-8")
        digest = hashlib.blake2b(item, digest_size=16).digest()
        return int.from_bytes(digest[:8], "little"), int.from_bytes(digest[8:], "little") | 1

    def add(self, item):
        h1, h2 = self._hashes(item)
        for j in range(self.k):
            p = (h1 + j * h2) % self.m
            self.array[p >> 3] |= 1 << (p & 7)

    def __contains__(self, item):
        h1, h2 = self._hashes(item)
        for j in range(self.k):
            p = (h1 + j * h2) % self.m
            if not self.array[p >> 3] & (1 << (p & 7)):
                return False
        return True

Then create step03_space_vs_bloom.py. It fills a cuckoo filter to 94 percent for five fingerprint sizes, builds a Bloom filter with the same total number of bits, and measures both on names that were never added:

"""step03_space_vs_bloom.py: false positive rate and memory, cuckoo filter against a Bloom filter of the same size."""
import math

from bloom import BloomFilter
from cuckoo import CuckooFilter
from labkit import false_positive_rate, names

BUCKETS = 1 << 15
SLOTS = BUCKETS * 4
ITEMS = int(SLOTS * 0.94)
print(f"{BUCKETS:,} buckets x 4 slots = {SLOTS:,} slots, filled with {ITEMS:,} items (94 percent)")
print(f"{'bits':>4} {'bits/item':>9} {'cuckoo FPR':>11} {'bound 2b/2^f':>12} {'Bloom FPR, same bits':>21} {'Bloom bits needed':>18}")
for f, probes in [(8, 300_000), (10, 300_000), (12, 1_000_000), (14, 1_000_000), (16, 1_000_000)]:
    cuckoo = CuckooFilter(0, fingerprint_bits=f, num_buckets=BUCKETS)
    for name in names("in", ITEMS):
        assert cuckoo.add(name)
    bits_per_item = cuckoo.bits_per_item()
    bloom = BloomFilter.for_budget(ITEMS, bits_per_item)
    for name in names("in", ITEMS):
        bloom.add(name)
    cuckoo_rate = false_positive_rate(cuckoo, "out", probes)
    bloom_rate = false_positive_rate(bloom, "out", probes)
    needed = 1.44 * math.log2(1 / cuckoo_rate)  # bits per item an ideal Bloom filter needs for the cuckoo filter's rate
    print(f"{f:>4} {bits_per_item:>9.2f} {cuckoo_rate:>11.4%} {8 / 2 ** f:>12.4%} {bloom_rate:>14.4%} (k={bloom.k:>2}) {needed:>12.2f}")

python step03_space_vs_bloom.py

32,768 buckets x 4 slots = 131,072 slots, filled with 123,207 items (94 percent)
bits bits/item  cuckoo FPR bound 2b/2^f  Bloom FPR, same bits  Bloom bits needed
   8      8.51     2.8473%      3.1250%        1.6460% (k= 6)         7.39
  10     10.64     0.7263%      0.7812%        0.6040% (k= 7)        10.23
  12     12.77     0.1834%      0.1953%        0.2222% (k= 9)        13.09
  14     14.89     0.0461%      0.0488%        0.0856% (k=10)        15.96
  16     17.02     0.0112%      0.0122%        0.0267% (k=12)        18.90

This takes under a minute. The columns are the fingerprint size, the memory per stored item, the cuckoo filter’s measured false positive rate, the paper’s upper bound 2b/2^f, the measured rate of a Bloom filter with the same memory (with the number of hash functions k it used), and the bits per item an ideal Bloom filter would need to reach the cuckoo filter’s rate (the paper’s Table 2 formula, 1.44 * log2(1/rate)).

Three things stand out:

• The measured rate sits just under the bound, by about the load factor (94 percent here), because an empty slot never matches. The bound is a dependable planning number: 8 bits give about 3 percent, 12 bits about 0.2 percent, and 16 bits about 0.012 percent.
• At 8 and 10 bits the Bloom filter wins. With the same memory it makes fewer false positives (1.65 against 2.85 percent at 8 bits).
• From 12 bits up the cuckoo filter wins. At 16 bits it makes 0.0112 percent against 0.0267 percent, about 2.4 times fewer. Put differently, a Bloom filter would need 18.90 bits per item to match it, and the cuckoo filter used 17.02.

That does not contradict the paper, but it needs careful reading. The abstract says that for “applications that store many items and target moderately low false positive rates, cuckoo filters have lower space overhead than space-optimized Bloom filters”, and the introduction puts the line at a false positive rate below 3 percent. Section 6 then adds the condition that matters here: “cuckoo filters with semi-sorting are more space efficient than Bloom filters” at those rates. Semi-sorting is an optional trick that saves one bit per item, and the filter you built does not use it.

Using the formulas in the paper’s Table 2 (a space-optimized Bloom filter needs 1.44 times log2(1/rate) bits per item, a plain cuckoo filter needs log2(1/rate) plus 3, all divided by the load factor, and a semi-sorted one needs log2(1/rate) plus 2, all divided by the load factor) with the paper’s load factor of 95.5 percent, my arithmetic puts the break-even at a rate of about 0.4 percent for the plain filter and about 2.5 percent for the semi-sorted one. The paper’s own Table 3 shows the plain-filter case: a cuckoo filter at 12.60 bits per item and a Bloom filter at 13.00 bits per item both reach a 0.19 percent false positive rate, a near tie, just like the 12-bit row above.

The practical lesson: choose a cuckoo filter when you need deletion, or when you want a rate below roughly half a percent. Do not choose it only to save memory at a 1 to 3 percent rate, because a plain Bloom filter is as small or smaller there.

Step 4: Find out how full the filter can get

How much memory a filter wastes depends on how full it can get before an insert fails. Create step04_load_factor.py. It fills filters of 65,536 slots with bucket sizes 1, 2, 4 and 8, three random seeds each, and records the load at the first refused insert. That is the paper’s own test for “full”: a filter is full when “a single insertion relocates existing fingerprints more than 500 times before finding an empty entry”.

"""step04_load_factor.py: how full can a filter get before an insert fails? (the paper's Figure 2 experiment, smaller)"""
from cuckoo import CuckooFilter
from labkit import names

SLOTS = 1 << 16
print(f"{SLOTS:,} slots in every filter, 16-bit fingerprints, up to 500 kicks per insert, 3 seeds per row")
for b in (1, 2, 4, 8):
    loads = []
    for seed in (1, 2, 3):
        flt = CuckooFilter(0, fingerprint_bits=16, bucket_size=b, seed=seed, num_buckets=SLOTS // b)
        stored = 0
        for name in names(f"seed{seed}", SLOTS):
            if not flt.add(name):
                break
            stored += 1
        loads.append(stored / SLOTS)
    print(f"bucket size {b}: first refusal at {min(loads):.1%} to {max(loads):.1%} full (mean {sum(loads) / len(loads):.1%})")

python step04_load_factor.py

65,536 slots in every filter, 16-bit fingerprints, up to 500 kicks per insert, 3 seeds per row
bucket size 1: first refusal at 50.0% to 51.7% full (mean 51.0%)
bucket size 2: first refusal at 87.3% to 87.6% full (mean 87.5%)
bucket size 4: first refusal at 96.3% to 96.9% full (mean 96.6%)
bucket size 8: first refusal at 98.7% to 99.2% full (mean 99.0%)

Bigger buckets let the filter fill up more: about 51 percent with one slot per bucket, 87.5 percent with two, 96.6 percent with four and 99.0 percent with eight. The paper says occupancy “increases to 84%, 95% or 98% respectively using bucket size b = 2, 4 or 8”, so these runs came out a little higher. Expect your digits to differ slightly from any published figure, because they depend on the table size, the kick limit and the random seeds. The pattern is what matters, and it explains two design choices. Buckets of four are the usual compromise: the paper concludes that “the cuckoo filter, which uses buckets of size 4, will perform well for a wide range of applications”. And the constructor sizes the table so it is at most 96 percent full at capacity, because a filter sized exactly to its expected items sits right at the refusal point (the first refusal here came at 96.3 to 96.9 percent).

Step 5: Four ways a cuckoo filter loses items, and the guard for each

The filter’s core promise is “no false negatives”. Every trap below breaks it. They are the reason to read this far instead of copying the class and moving on.

Trap 1: a refused insert can erase an item that was already stored

When add runs out of kicks, the fingerprint it is holding has been shoved out of the table. It usually belongs to an item stored earlier, because the new item’s fingerprint went into the table at the first kick. If the code simply returns False at that point, the fingerprint in its hand is dropped and its item silently vanishes. The authors’ C++ code avoids this with a one-slot “victim” cache. When it reaches its limit (a constant commented “maximum number of cuckoo kicks before claiming failure”, set to 500), it parks the leftover fingerprint there, still reports success for that insert, and refuses the next one. Our class uses an undo log instead. Create step05_failure.py, which overfills a 4,096-slot filter with the undo log off and then on:

"""step05_failure.py: what a refused insert does to the items that were already accepted."""
from cuckoo import CuckooFilter
from labkit import names

for undo in (False, True):
    flt = CuckooFilter(0, fingerprint_bits=12, num_buckets=1024, undo_on_failure=undo)
    accepted, refused = [], 0
    for name in names("item", 4_500):  # 1,024 buckets x 4 slots = 4,096 slots, so the filter fills up and starts refusing
        if flt.add(name):
            accepted.append(name)
        else:
            refused += 1
    missing = sum(1 for name in accepted if name not in flt)
    print(f"undo_on_failure={undo!s:5}: accepted {len(accepted):,}, refused {refused}, accepted items that went missing: {missing}")

python step05_failure.py

undo_on_failure=False: accepted 4,058, refused 442, accepted items that went missing: 420
undo_on_failure=True : accepted 4,055, refused 445, accepted items that went missing: 0

With the undo log off, 442 inserts were refused, and 420 of the 4,058 items that had been accepted were gone, close to one lost item per refusal. With it on, 445 inserts were refused and nothing was lost. (The accepted counts differ by three only because the two runs diverge after the first refusal.)

Guard: treat a False from add as “the filter is full”, never as success, and keep the undo log (or the victim cache) so that a full filter still never forgets what it holds.

Trap 2: adding the same item more than 2b times

Adding an item twice does not do nothing: a second copy of its fingerprint is stored. All copies of one item share the same two buckets, and kicking cannot move them anywhere else, so one item can occupy at most 2b slots (b is the bucket size). The paper says plainly that “cuckoo filters are not suitable for applications that insert the same item more than 2b times”. Create step06_duplicates.py:

"""step06_duplicates.py: adding the same key again and again fills only its own two buckets."""
from cuckoo import CuckooFilter

for b in (2, 4):
    flt = CuckooFilter(1_000, bucket_size=b)
    results = [flt.add("coupon-SUMMER") for _ in range(12)]
    print(f"bucket size {b}: 12 adds of one key -> {results.count(True)} stored, {results.count(False)} refused (2 buckets x {b} slots)")
    removals = 0
    while flt.remove("coupon-SUMMER"):
        removals += 1
    print(f"   remove() found a copy {removals} times | still reported present afterwards: {'coupon-SUMMER' in flt}")

python step06_duplicates.py

bucket size 2: 12 adds of one key -> 4 stored, 8 refused (2 buckets x 2 slots)
   remove() found a copy 4 times | still reported present afterwards: False
bucket size 4: 12 adds of one key -> 8 stored, 4 refused (2 buckets x 4 slots)
   remove() found a copy 8 times | still reported present afterwards: False

With four-slot buckets the filter took 8 copies of one key and refused the other 4. With two-slot buckets it took 4 and refused 8. Notice the second line of each pair: every copy needs its own remove, and the key disappears only after the last one is gone.

Guard: add each item once. Decide that from your source of truth, such as the database row, and not from the filter itself. Writing if item not in flt: flt.add(item) looks safe, but a false positive would make you skip a genuinely new item, and that item would later become a false negative.

Trap 3: removing an item that was never added

remove erases a fingerprint, not an item. If you remove something that is not stored, and its fingerprint happens to match one in its buckets, a different, real item loses its fingerprint. The paper warns that “to delete an item x safely, it must have been previously inserted”, and the authors’ README says the same: “it must be ensured that this item is in the filter (e.g., based on records on external storage); otherwise, a false item may be deleted”. Create step07_stranger_removal.py. It stores 40,000 items, tries to remove 20,000 strangers, and counts the damage for three fingerprint sizes:

"""step07_stranger_removal.py: remove() on an item that was never added deletes somebody else's fingerprint."""
from cuckoo import CuckooFilter
from labkit import names

STORED, STRANGERS = names("stored", 40_000), names("stranger", 20_000)
for f in (8, 12, 16):
    flt = CuckooFilter(0, fingerprint_bits=f, num_buckets=1 << 14)
    for name in STORED:
        assert flt.add(name)
    removed = sum(1 for name in STRANGERS if flt.remove(name))
    missing = sum(1 for name in STORED if name not in flt)
    print(f"{f:2}-bit fingerprints: {removed:3} of {len(STRANGERS):,} stranger removals 'succeeded' | stored items now missing: {missing}")

python step07_stranger_removal.py

 8-bit fingerprints: 382 of 20,000 stranger removals 'succeeded' | stored items now missing: 378
12-bit fingerprints:  27 of 20,000 stranger removals 'succeeded' | stored items now missing: 27
16-bit fingerprints:   2 of 20,000 stranger removals 'succeeded' | stored items now missing: 2

With 8-bit fingerprints, 382 of the 20,000 stranger removals “succeeded”, and 378 real items stopped being found. With 12 bits it was 27 and 27, and with 16 bits it was 2 and 2. Longer fingerprints make the damage rarer, but not impossible.

Guard: call remove only when you can prove the item is currently in the filter, for example because a database row records that you added it. Never pass raw user input to it.

Trap 4: a bucket count that is not a power of two

The XOR trick has a hidden requirement. The authors’ code says it in a comment: the bucket count “is always a power of two, so modulo can be replaced with bitwise-and”. With a power of two, the mask keeps only the low bits, so XOR with the fingerprint’s hash flips the same low bits each time and the round trip works. With any other count, the large hash bits wrap around unpredictably and the round trip breaks. Create step08_modulo.py, which builds that broken variant with 1,000 buckets and compares it with a normal 1,024-bucket filter:

"""step08_modulo.py: keep the XOR trick but let the bucket count be 1,000 instead of a power of two."""
from array import array

from cuckoo import CuckooFilter
from labkit import names


class ModuloFilter(CuckooFilter):
    """A broken variant: bucket numbers are reduced with % instead of a bit mask."""

    def __init__(self, num_buckets, **kwargs):
        super().__init__(0, num_buckets=1, **kwargs)
        self.m = num_buckets
        self.table = array(self.table.typecode, [0]) * (self.m * self.b)

    def _reduce(self, x):
        return x % self.m


good, bad = CuckooFilter(0, num_buckets=1024), ModuloFilter(1000)
for label, flt in (("1,024 buckets, mask", good), ("1,000 buckets, modulo", bad)):
    failed = sum(1 for i in range(flt.m) for fp in (1, 77, 4095) if flt._alt(flt._alt(i, fp), fp) != i)
    stored = [name for name in names("item", int(flt.slots * 0.75)) if flt.add(name)]
    missing = sum(1 for name in stored if name not in flt)
    print(f"{label:22}: round trips that miss the start: {failed:4} of {flt.m * 3:,} | items added: {len(stored):,}, then missing: {missing}")

python step08_modulo.py

1,024 buckets, mask   : round trips that miss the start:    0 of 3,072 | items added: 3,072, then missing: 0
1,000 buckets, modulo : round trips that miss the start: 3000 of 3,000 | items added: 3,000, then missing: 22

In the 1,000-bucket variant, none of the 3,000 round trips returned to its starting bucket. Items are fine until a kick moves one to what the code believes is its other bucket, and that “other bucket” is the wrong one. After adding 3,000 items, 22 of them could not be found. That is a 0.7 percent false negative rate, small enough to slip past a casual test and large enough to hurt in production. The 1,024-bucket filter lost nothing.

Guard: round the bucket count up to a power of two, as the constructor does. It raises ValueError if you pass anything else.

The four traps at a glance

Step 6: Use it in front of a coupon table

The Redis documentation describes a cuckoo filter use case that matches this tutorial closely. Its coupon recipe answers the question “Has this discount code/coupon been used yet?”: keep a filter of all the codes, treat a miss as “not valid”, check the main database on a hit, and “remove from Cuckoo filter as used” once the code is valid. Let’s build exactly that, with a pretend slow database. Create step09_coupons.py:

"""step09_coupons.py: a cuckoo filter in front of a slow coupon table, and the retry bug that poisons it."""
from collections import Counter

from cuckoo import CuckooFilter
from labkit import names


class CouponTable:
    """Stands in for the slow database. redeem() succeeds once per code and counts every call."""

    def __init__(self, codes):
        self.unused = set(codes)
        self.lookups = 0

    def redeem(self, code):
        self.lookups += 1
        if code in self.unused:
            self.unused.remove(code)
            return True
        return False


class CouponGate:
    def __init__(self, codes, fingerprint_bits):
        self.table = CouponTable(codes)
        self.filter = CuckooFilter(len(codes), fingerprint_bits)
        for code in codes:
            if not self.filter.add(code):
                raise RuntimeError("filter full")  # never ignore a refused add: remove() would later hit a stranger

    def redeem(self, code):
        if code not in self.filter:
            return "no such code"  # a definite answer: the database is never asked
        if self.table.redeem(code):
            self.filter.remove(code)  # exactly one removal, made by the request that won the database race
            return "redeemed"
        return "database said no"


CODES = names("SUMMER", 20_000)
REDEEMED, UNUSED = CODES[:10_000], CODES[10_000:]
gate = CouponGate(CODES, fingerprint_bits=12)
outcomes = Counter()
for code in REDEEMED + REDEEMED + names("GUESS", 80_000):  # 10,000 redemptions, 10,000 replays, 80,000 random guesses
    outcomes[gate.redeem(code)] += 1
print("100,000 requests ->", dict(outcomes))
print(f"database lookups: {gate.table.lookups:,} (without the filter: 100,000)")
print(f"unused codes the filter still recognises: {sum(1 for code in UNUSED if code in gate.filter):,} of {len(UNUSED):,}")


def wrongly_rejected(fingerprint_bits, deliveries):
    """Redeem 10,000 of the 20,000 codes, remove each from the filter `deliveries` times, then test the other 10,000."""
    g = CouponGate(CODES, fingerprint_bits)
    for code in REDEEMED:
        assert g.table.redeem(code)
        for _ in range(deliveries):  # a message queue with at-least-once delivery runs the cleanup once per message
            g.filter.remove(code)
    return sum(1 for code in UNUSED if code not in g.filter)


print("valid, unused coupons wrongly rejected out of 10,000:")
for f in (8, 12, 16):
    print(f"  {f:2}-bit fingerprints: one removal per code -> {wrongly_rejected(f, 1)}, two -> {wrongly_rejected(f, 2)}, three -> {wrongly_rejected(f, 3)}")

Read the two classes first. CouponTable stands in for the slow database: redeem succeeds once per code and counts every call. CouponGate loads every code into the filter, and it raises an error if the filter refuses one, because ignoring a refused add would set up Trap 3 later. redeem asks the filter first. A miss is a definite “no such code” and the database is never touched. A hit goes to the database, and only the request that wins there removes the code from the filter.

python step09_coupons.py

100,000 requests -> {'redeemed': 10000, 'no such code': 89950, 'database said no': 50}
database lookups: 10,050 (without the filter: 100,000)
unused codes the filter still recognises: 10,000 of 10,000
valid, unused coupons wrongly rejected out of 10,000:
   8-bit fingerprints: one removal per code -> 0, two -> 86, three -> 90
  12-bit fingerprints: one removal per code -> 0, two -> 8, three -> 8
  16-bit fingerprints: one removal per code -> 0, two -> 1, three -> 1

The first block is the traffic test: 10,000 real redemptions, 10,000 replays of those same codes (a customer clicking twice, a script retrying) and 80,000 random guesses. The filter answered 89,950 of them with a definite “no such code”. Another 50 slipped through as false alarms, 0.056 percent of the 90,000 requests that should have been refused, and the database said no to those. The database saw 10,050 lookups instead of 100,000, about ten times fewer. All 10,000 codes that were never redeemed were still recognised, so there were no false negatives. The replays are the part a Bloom filter could not do, because it cannot forget a redeemed code, and every one of the 10,000 replays would still have reached the database.

The retry bug that poisons the filter

Now the failure. Many message queues deliver a message at least once, which means sometimes twice or three times. Suppose a worker handles each “coupon redeemed” message by calling filter.remove(code). The first removal is correct. Every extra one removes an item that is no longer there, and that is Trap 3 again: it takes out somebody else’s fingerprint when one matches. The function wrongly_rejected simulates it. It redeems 10,000 of the 20,000 codes, removes each from the filter once, twice or three times, and then counts how many of the other 10,000 valid, unused coupons the filter now rejects.

The last three lines of the output are the answer. With one removal per code, no valid coupon is lost at any fingerprint size. With a second delivery, 8-bit fingerprints reject 86 valid coupons, 12-bit fingerprints reject 8, and 16-bit fingerprints reject 1. Each of those is a real customer told that their code does not exist, with no error anywhere to explain it.

The fix: tie the removal to the database change

The filter must change exactly once per redemption, and only the database can say whether this call is the one. In SQL, UPDATE coupon SET used = 1 WHERE code = ? AND used = 0 changes a row only the first time, and the cursor’s rowcount reports whether it did. Create step10_exactly_once.py, which delivers every message three times against a real SQLite table:

"""step10_exactly_once.py: tie the filter removal to the database change, so a retried message cannot remove twice."""
import sqlite3

from cuckoo import CuckooFilter
from labkit import names

CODES = names("SUMMER", 20_000)
REDEEMED, UNUSED = CODES[:10_000], CODES[10_000:]
db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE coupon (code TEXT PRIMARY KEY, used INTEGER NOT NULL DEFAULT 0) WITHOUT ROWID")
db.executemany("INSERT INTO coupon (code) VALUES (?)", [(code,) for code in CODES])


def redeem(flt, code):
    """True only for the one call that changes used from 0 to 1; only that call touches the filter."""
    won = db.execute("UPDATE coupon SET used = 1 WHERE code = ? AND used = 0", (code,)).rowcount == 1
    if won:
        flt.remove(code)
    return won


for f in (8, 12, 16):
    flt = CuckooFilter(len(CODES), f)
    for code in CODES:
        assert flt.add(code)
    db.execute("UPDATE coupon SET used = 0")
    wins = sum(redeem(flt, code) for code in REDEEMED for _ in range(3))  # every message is delivered three times
    wrong = sum(1 for code in UNUSED if code not in flt)
    print(f"{f:2}-bit fingerprints: {wins:,} winning calls out of 30,000 deliveries | valid coupons wrongly rejected: {wrong}")

python step10_exactly_once.py

 8-bit fingerprints: 10,000 winning calls out of 30,000 deliveries | valid coupons wrongly rejected: 0
12-bit fingerprints: 10,000 winning calls out of 30,000 deliveries | valid coupons wrongly rejected: 0
16-bit fingerprints: 10,000 winning calls out of 30,000 deliveries | valid coupons wrongly rejected: 0

Out of 30,000 deliveries, exactly 10,000 won the database update and touched the filter. No valid coupon was wrongly rejected at any fingerprint size. The same pattern fixes the other trap that involves deletes: remove is safe when it follows a change in your source of truth, and unsafe when it follows a guess.

Step 7: Test the filter, then break it on purpose

The traps show why the tests matter. Create test_cuckoo.py:

"""test_cuckoo.py: tests for cuckoo.py. Run with: python -m pytest -q"""
import random
from collections import Counter

import pytest

from cuckoo import CuckooFilter, next_power_of_two
from labkit import false_positive_rate, names


def test_sizing_follows_the_reference_rule():
    assert next_power_of_two(1) == 1 and next_power_of_two(5) == 8 and next_power_of_two(1024) == 1024
    assert CuckooFilter(100).m == 32
    assert CuckooFilter(1_000).m == 512  # 1,000 / (256 x 4) is above 0.96, so the table doubles


def test_bucket_count_must_be_a_power_of_two():
    with pytest.raises(ValueError):
        CuckooFilter(100, num_buckets=1000)


@pytest.mark.parametrize("bits", [4, 8, 12, 16])
def test_fingerprints_fit_the_slot_and_are_never_zero(bits):
    flt = CuckooFilter(1_000, fingerprint_bits=bits)
    for name in names("fp", 5_000):
        fp, bucket = flt._locate(name)
        assert 1 <= fp < (1 << bits)
        assert 0 <= bucket < flt.m


def test_alternate_bucket_is_its_own_inverse():
    flt = CuckooFilter(10_000, fingerprint_bits=12)
    rng = random.Random(7)
    for _ in range(20_000):
        i, fp = rng.randrange(flt.m), rng.randrange(1, 1 << 12)
        j = flt._alt(i, fp)
        assert 0 <= j < flt.m
        assert flt._alt(j, fp) == i


def test_every_added_item_is_found():
    flt = CuckooFilter(5_000)
    for name in names("in", 5_000):
        assert flt.add(name)
    assert len(flt) == 5_000
    assert all(name in flt for name in names("in", 5_000))


def test_false_positive_rate_stays_under_the_paper_bound():
    flt = CuckooFilter(5_000, fingerprint_bits=10)
    for name in names("in", 5_000):
        flt.add(name)
    assert false_positive_rate(flt, "out", 20_000) < 8 / 2 ** 10  # 2b / 2^f from the paper


def test_remove_forgets_an_item_once():
    flt = CuckooFilter(100)
    assert flt.add("a")
    assert "a" in flt and len(flt) == 1
    assert flt.remove("a") is True
    assert "a" not in flt and len(flt) == 0
    assert flt.remove("a") is False


def test_four_slot_buckets_hold_eight_copies_of_one_key():
    flt = CuckooFilter(1_000)
    assert [flt.add("same") for _ in range(10)] == [True] * 8 + [False] * 2
    assert len(flt) == 8


def test_a_refused_add_changes_nothing():
    flt = CuckooFilter(0, fingerprint_bits=8, num_buckets=16)
    filled = [name for name in names("fill", 200) if flt.add(name)]
    refusals = 0
    for name in names("late", 100):
        before, count = flt.table.tobytes(), len(flt)
        if not flt.add(name):
            refusals += 1
            assert flt.table.tobytes() == before and len(flt) == count
    assert refusals > 0
    assert all(name in flt for name in filled)


def test_random_operations_match_a_counter_model():
    rng = random.Random(3)
    flt = CuckooFilter(0, fingerprint_bits=16, num_buckets=256, seed=5)  # small, so adds are refused now and then
    model, pool = Counter(), names("op", 3_000)
    for _ in range(12_000):
        item = rng.choice(pool)
        if rng.random() < 0.6:
            if flt.add(item):
                model[item] += 1
        elif model[item] > 0:
            assert flt.remove(item)
            model[item] -= 1
    assert len(flt) == sum(model.values())
    assert all(item in flt for item, copies in model.items() if copies > 0)


def test_a_filter_reaches_high_load_before_refusing():
    flt = CuckooFilter(0, fingerprint_bits=16, num_buckets=2048)
    for name in names("load", int(flt.slots * 0.90)):
        assert flt.add(name)


def test_str_and_bytes_are_the_same_item_and_other_types_are_refused():
    flt = CuckooFilter(10)
    flt.add("abc")
    assert b"abc" in flt
    with pytest.raises(TypeError):
        flt.add(123)


def test_the_same_seed_builds_the_same_table():
    a, b = CuckooFilter(0, seed=9, num_buckets=128), CuckooFilter(0, seed=9, num_buckets=128)
    for name in names("s", 480):
        a.add(name)
        b.add(name)
    assert a.table == b.table


def test_bits_per_item_is_table_bits_over_items():
    flt = CuckooFilter(1_000, fingerprint_bits=12)
    for name in names("b", 500):
        flt.add(name)
    assert flt.bits_per_item() == pytest.approx(12 * flt.slots / 500)

python -m pytest -q

.................                                                        [100%]
17 passed in 1.51s

Four of these tests do most of the work. test_alternate_bucket_is_its_own_inverse checks the XOR round trip from Step 1. test_a_refused_add_changes_nothing checks Trap 1: it overfills a tiny filter and compares the whole table before and after each refused insert. test_four_slot_buckets_hold_eight_copies_of_one_key pins down Trap 2. And test_random_operations_match_a_counter_model runs 12,000 random adds and removes in a table small enough to fill up, checks the filter against a plain Counter, and requires that every item the model says is present is found.

A passing test suite proves little unless it fails when the code is wrong. So the next script plants nine deliberate bugs in cuckoo.py, one at a time, in a temporary copy, and runs the tests against each. Create mutations.py:

"""mutations.py: plant deliberate bugs in cuckoo.py and check that the tests notice each one."""
import os
import re
import shutil
import subprocess
import sys
import tempfile
from pathlib import Path

HERE = Path(__file__).parent
SOURCE = (HERE / "cuckoo.py").read_text(encoding="utf-8")

MUTANTS = [
    ("a fingerprint may be 0, the empty marker", "        if fp == 0:\n            fp = 1\n", ""),
    ("the other bucket uses + instead of XOR", "return self._reduce(i ^ (fp * MIX))", "return self._reduce(i + fp * MIX)"),
    ("a refused add is not undone", "undo_on_failure=True, num_buckets=None", "undo_on_failure=False, num_buckets=None"),
    ("the undo log is replayed in the wrong order", "for s, old in reversed(undo):", "for s, old in undo:"),
    ("lookup checks only the first bucket", "return fp in self._bucket(i1) or fp in self._bucket(i2)", "return fp in self._bucket(i1)"),
    ("remove checks only the first bucket", "for i in (i1, self._alt(i1, fp)):", "for i in (i1,):"),
    ("remove forgets to lower the count", "                    self.count -= 1\n", ""),
    ("no kicks are allowed", "max_kicks=500", "max_kicks=0"),
    ("the table is never doubled when it would be over 96 percent full", "if capacity / (num_buckets * bucket_size) > 0.96:", "if False:"),
]


def run_tests(source):
    """Copy the lab to a temp folder with `source` as cuckoo.py; return (failed, passed, first failing test)."""
    with tempfile.TemporaryDirectory() as tmp:
        for name in ("labkit.py", "test_cuckoo.py"):
            shutil.copy(HERE / name, tmp)
        Path(tmp, "cuckoo.py").write_text(source, encoding="utf-8", newline="\n")
        env = dict(os.environ, PYTHONDONTWRITEBYTECODE="1")
        done = subprocess.run([sys.executable, "-B", "-m", "pytest", "-q", "-p", "no:cacheprovider", "-W", "ignore"],
                              cwd=tmp, env=env, capture_output=True, text=True)
    failed = re.search(r"(\d+) failed", done.stdout)
    passed = re.search(r"(\d+) passed", done.stdout)
    first = re.search(r"^FAILED \S+::(\S+)", done.stdout, flags=re.M)
    return (int(failed.group(1)) if failed else 0, int(passed.group(1)) if passed else 0, first.group(1) if first else "-")


failed, passed, _ = run_tests(SOURCE)
print(f"baseline: {passed} passed, {failed} failed")
caught = 0
for n, (label, old, new) in enumerate(MUTANTS, 1):
    assert SOURCE.count(old) == 1, f"mutant {n}: the text to replace must occur exactly once"
    failed, passed, first = run_tests(SOURCE.replace(old, new))
    caught += failed > 0
    print(f"mutant {n}: {label}: failing tests {failed} (first: {first})")
print(f"caught {caught} of {len(MUTANTS)} planted bugs")

python mutations.py

baseline: 17 passed, 0 failed
mutant 1: a fingerprint may be 0, the empty marker: failing tests 5 (first: test_fingerprints_fit_the_slot_and_are_never_zero[4])
mutant 2: the other bucket uses + instead of XOR: failing tests 5 (first: test_alternate_bucket_is_its_own_inverse)
mutant 3: a refused add is not undone: failing tests 2 (first: test_a_refused_add_changes_nothing)
mutant 4: the undo log is replayed in the wrong order: failing tests 2 (first: test_a_refused_add_changes_nothing)
mutant 5: lookup checks only the first bucket: failing tests 3 (first: test_every_added_item_is_found)
mutant 6: remove checks only the first bucket: failing tests 1 (first: test_random_operations_match_a_counter_model)
mutant 7: remove forgets to lower the count: failing tests 2 (first: test_remove_forgets_an_item_once)
mutant 8: no kicks are allowed: failing tests 2 (first: test_every_added_item_is_found)
mutant 9: the table is never doubled when it would be over 96 percent full: failing tests 1 (first: test_sizing_follows_the_reference_rule)
caught 9 of 9 planted bugs

All nine bugs were caught. Mutants 3 and 4 are Trap 1 (no undo, and an undo that replays in the wrong order), mutant 2 breaks the XOR round trip, and mutant 1 allows the empty marker as a fingerprint. If a mutant ever shows failing tests 0, your tests have a gap, and the fix is a new test, not a new mutant.

Run everything and confirm it works

Create run_all.py. It runs every step, the tests and the mutation check, and saves each output under out/:

"""run_all.py: run every step, the tests and the mutation check; save each output to out/NAME.txt."""
import subprocess
import sys
from pathlib import Path

HERE = Path(__file__).parent
OUT = HERE / "out"
OUT.mkdir(exist_ok=True)
STEPS = ["step01_locate", "step02_use_it", "step03_space_vs_bloom", "step04_load_factor", "step05_failure",
         "step06_duplicates", "step07_stranger_removal", "step08_modulo", "step09_coupons", "step10_exactly_once"]


def run(name, args):
    done = subprocess.run([sys.executable, "-B", *args], cwd=HERE, capture_output=True, text=True, encoding="utf-8")
    text = (done.stdout + done.stderr).rstrip("\n") + "\n"
    with open(OUT / f"{name}.txt", "w", newline="\n", encoding="utf-8") as f:
        f.write(text)
    print(f"== {name} (exit {done.returncode})", flush=True)
    print(text, flush=True)


for step in STEPS[:2]:
    run(step, [f"{step}.py"])
run("pytest", ["-m", "pytest", "-q", "-p", "no:cacheprovider", "test_cuckoo.py"])
for step in STEPS[2:]:
    run(step, [f"{step}.py"])
run("mutations", ["mutations.py"])

python run_all.py

It takes about a minute. Check these six things:

1. Step 1: the last line reports 0 failed round trips.
2. Step 2: every stored item is found, and the false positive rate is near 0.14 percent.
3. Step 3: the cuckoo filter’s rate is just under the bound in every row, and it overtakes the Bloom filter from 12 bits.
4. Step 5: with undo_on_failure=True no accepted item goes missing, and the stranger-removal and modulo steps show the damage numbers from this tutorial.
5. Step 6: the database sees about 10,050 lookups, one removal per code loses 0 coupons, and the exactly-once version loses 0 at every fingerprint size.
6. Step 7: 17 tests pass and 9 of 9 planted bugs are caught.

Mistakes to avoid

• Ignoring the result of add. A refused add means the filter is full. Stop adding, or build a bigger filter.
• Using the filter to decide whether to add or remove. A false positive from in will make you skip a real item or delete a stranger. Ask your database.
• Calling remove from code that can run twice. Retried messages, double clicks and cleanup jobs all repeat work. Tie the removal to a one-time change in your database.
• Adding the same key repeatedly. Eight copies fit with four-slot buckets, and the ninth fails.
• Sizing to exactly the expected item count. A filter near 96 percent full starts refusing inserts. Leave headroom.
• Passing a bucket count that is not a power of two, or replacing the mask with %.
• Hashing with Python’s built-in hash(). For strings and bytes it changes between runs, so a saved filter becomes unreadable.
• Treating this class as production code. It is not safe to share between threads without a lock, it cannot grow, and it does not save itself to disk.

Where to go next

• Semi-sorting. The paper describes sorting the fingerprints inside each four-slot bucket and encoding the sorted list, which saves one bit per item. That is the variant behind its claim of lower space than a Bloom filter at false positive rates below 3 percent.
• A tested implementation. Redis ships cuckoo filter commands, CF.RESERVE, CF.ADD, CF.EXISTS and CF.DEL. CF.RESERVE takes optional BUCKETSIZE, MAXITERATIONS and EXPANSION arguments, and the command pages describe costs in terms of “the number of sub-filters”, so a Redis cuckoo filter can be made of several parts, unlike the fixed table you built.
• Sets that never change. If you never delete, newer designs can be smaller. The xor filter paper says plainly that “an xor filter is immutable” and reports that “xor filters can be faster than Bloom and cuckoo filters while using less memory”, and a follow-up on binary fuse filters reports that its experiments “suggest that binary fuse filters are superior to xor filters”.
• More from this site. The Bloom filter, HyperLogLog and Count-Min sketch tutorials cover the other classic probabilistic structures, and the LSM-tree tutorial shows a Bloom filter protecting disk reads in a key-value store.

Sources

• Fan, Andersen, Kaminsky and Mitzenmacher, “Cuckoo Filter: Practically Better Than Bloom”, CoNEXT 2014 (Algorithm 1, Section 3.3, Table 2, Table 3 and Section 5.1).
• The authors’ C++ code: cuckoofilter.h, singletable.h and the repository README.
• Redis documentation: Cuckoo filter and CF.RESERVE.
• Graf and Lemire, “Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters”, and “Binary Fuse Filters: Fast and Smaller Than Xor Filters”.
• Python documentation: object.__hash__ and hashlib.