Cuckoo Filter

A Cuckoo filter stores fingerprints (a hash truncation of the original item) in a table of buckets, each holding a fixed number of entries (typically 2-4 slots per bucket). Insertion uses cuckoo hashing: an item’s fingerprint is placed into one of two candidate buckets computed from its hash; if both are full, an existing fingerprint is evicted and relocated to its alternate bucket, cascading until a free slot is found or a maximum relocation count is hit, at which point the filter is considered full and must be resized. Because the fingerprint itself (not the original key) is stored, deletion is trivial: locate the fingerprint in one of its two candidate buckets and remove it, something a standard Bloom filter cannot do without shared-counter tricks like a Counting Bloom filter, which sacrifice significant space.

The false-positive rate is governed by fingerprint size, not by the number of hash functions as in Bloom filters, giving Cuckoo filters a more predictable and often smaller memory footprint at equivalent false-positive rates below roughly 3%. Lookup is O(1) worst case: compute two candidate bucket indices, scan their fixed-size slot arrays for a matching fingerprint. This contrasts with Bloom filters where lookup cost scales with the number of hash functions (k) and cache locality degrades as k grows, since each hash function typically touches a different, non-adjacent bit region of a large bit array. Cuckoo filters exhibit better cache behavior because both candidate buckets are small, contiguous, and can be fetched in one or two cache-line reads.

Operationally, the failure mode engineers must respect is insertion failure under high load factor: as the table approaches ~95% occupancy, the cuckoo relocation chain can exceed the configured max-kicks threshold, causing the insert to fail outright rather than degrade gracefully. This is fundamentally different from Bloom filters, which never reject an insert but instead silently increase the false-positive rate as they saturate. Systems using Cuckoo filters for things like CDN edge cache admission, LSM-tree tombstone/key-existence checks (RocksDB’s experimental support), or distributed deduplication indexes must therefore either pre-size aggressively, implement filter doubling/rehashing on failure, or fall back to a secondary check path. Fingerprint collisions across the two candidate buckets during eviction chains are the most common source of subtle correctness bugs, especially when engineers hand-roll a variant instead of using a vetted implementation.

Compared to a Bloom filter, the Cuckoo filter trades a slightly more complex insertion algorithm and stricter load-factor ceiling for deletion support, better worst-case lookup latency, and tighter space bounds at low false-positive targets, making it the preferred structure whenever set membership is queried against a dynamic, mutating key population rather than a static or append-only one.