Cuckoo filters: relocate compact fingerprints safely

Last updated: 4 Oct 20269 min read

tutorial

A cuckoo filter stores a short fingerprint rather than a full incident ID. A key selects a first bucket, and its fingerprint determines an alternate bucket through an XOR offset. A fingerprint may occupy either bucket. When both are full, bounded relocations move an existing fingerprint to its alternate bucket until space opens. The alternate calculation is symmetric: applying the same XOR offset twice returns the original bucket. This program records displaced slots and restores them in reverse if its kick limit is reached, so a rejected insertion cannot lose a previously accepted fingerprint. Queries can return false positives when fingerprints collide. The filter does not deduplicate keys, and every successful add consumes a slot; duplicate submissions should be controlled by an authoritative layer.

Operational case

A service inserts twenty-five incident IDs into two-slot buckets. Every accepted ID must remain a possible member even if later insertions kick fingerprints across buckets. If the table reaches a relocation cycle, add returns false and the old state is restored. The accepted list in the example is maintained only to demonstrate that invariant; the filter itself keeps no exact identities. Fingerprint-only deletion is intentionally absent from this API. Removing a matched fingerprint without an authoritative identity rule can erase a different key's representation when collisions and candidate-bucket overlap occur. A membership-positive result alone is never permission to delete.

Working Python program

import hashlib
import random


class FingerprintIncidentFilter:
    def __init__(self, bucket_count=32, bucket_size=2, fingerprint_bits=12,
                 max_kicks=80, seed=47):
        if bucket_count < 2 or bucket_count & (bucket_count - 1):
            raise ValueError("bucket count must be a power of two")
        if bucket_size < 1 or not 4 <= fingerprint_bits <= 32 or max_kicks < 1:
            raise ValueError("invalid bucket, fingerprint, or kick limit")
        self.buckets = [[] for _ in range(bucket_count)]
        self.bucket_size = bucket_size
        self.fingerprint_bits = fingerprint_bits
        self.max_kicks = max_kicks
        self.random_source = random.Random(seed)

    def _alternate(self, bucket_number, fingerprint):
        digest = hashlib.blake2b(fingerprint.to_bytes(4, "big"), digest_size=8).digest()
        offset = (int.from_bytes(digest, "big") & (len(self.buckets) - 1)) or 1
        return bucket_number ^ offset

    def _locations(self, incident_id):
        digest = hashlib.sha256(incident_id.encode("utf-8")).digest()
        fingerprint = (int.from_bytes(digest[:4], "big")
                       & ((1 << self.fingerprint_bits) - 1)) or 1
        first = int.from_bytes(digest[4:12], "big") & (len(self.buckets) - 1)
        return fingerprint, first, self._alternate(first, fingerprint)

    def add(self, incident_id):
        fingerprint, first, second = self._locations(incident_id)
        for bucket_number in (first, second):
            if len(self.buckets[bucket_number]) < self.bucket_size:
                self.buckets[bucket_number].append(fingerprint)
                return True
        bucket_number = self.random_source.choice((first, second))
        displaced_fingerprint = fingerprint
        changes = []
        for _ in range(self.max_kicks):
            slot = self.random_source.randrange(self.bucket_size)
            previous = self.buckets[bucket_number][slot]
            self.buckets[bucket_number][slot] = displaced_fingerprint
            changes.append((bucket_number, slot, previous))
            displaced_fingerprint = previous
            bucket_number = self._alternate(bucket_number, previous)
            if len(self.buckets[bucket_number]) < self.bucket_size:
                self.buckets[bucket_number].append(displaced_fingerprint)
                return True
        for changed_bucket, changed_slot, previous in reversed(changes):
            self.buckets[changed_bucket][changed_slot] = previous
        return False

    def might_contain(self, incident_id):
        fingerprint, first, second = self._locations(incident_id)
        return fingerprint in self.buckets[first] or fingerprint in self.buckets[second]


filter_index = FingerprintIncidentFilter()
accepted = []
for incident_number in range(47, 72):
    incident_id = f"incident-{incident_number}"
    if filter_index.add(incident_id):
        accepted.append(incident_id)
print("accepted=", len(accepted),
      "all-present=", all(filter_index.might_contain(incident_id)
                           for incident_id in accepted), sep="")

Output

accepted=25all-present=True

Time, space, and tradeoff

Lookup checks at most two buckets, each holding at most S fingerprints, so it takes O(S) comparisons plus hash work; S is often a small fixed bucket size. Direct insertion is O(S), while a displaced insertion can take O(KS) for a configured K-kick limit and O(K) undo records. Storage is O(BS) fingerprint slots for B buckets, excluding Python container overhead. The fixed table has no automatic growth or rebuild, and an insertion can fail before every slot is occupied. Finite fingerprints admit false positives; no quantified rate is promised for this deterministic example. The seeded relocation choice makes tests repeatable but is not a security mechanism.

Common Mistakes

Do not leave displaced entries changed after a failed insertion.
Do not treat fingerprint equality as exact key equality.
Do not assume an add call cannot fail below full occupancy.
Do not delete a positive match without an identity-safe policy.

Connected lessons

Compare its mutation contract with Counting Bloom filters: delete only a known insertion, Scalable Bloom filters: grow without discarding old members, Blocked Bloom filters: localize probes and watch skew, then run the membership audit and contract quiz.

Static XOR filters: peel a fingerprint membership index adds a distinct structure contract to compare.

data structures

range-query-structures