Module 10 · Data structures for scale · Lesson 6 of 11
Cuckoo filters
A Bloom filter alternative that supports deletion and uses less space at low false-positive rates. Fingerprints in two candidate buckets, the kick-out insertion that names it, partial-key cuckoo hashing, and when to prefer it over Bloom.
Why it matters
Bloom filters cannot delete, and at false-positive rates below about 3 percent they are not the most space-efficient option either. Systems whose sets change in both directions, a cache that evicts, a blocklist that unbans, a set of live sessions, need a membership filter that forgets. The cuckoo filter gives that with simpler lookups and, at low error rates, fewer bits per item. It is the modern answer when someone asks "Bloom filter, but with deletes".
The idea
A cuckoo filter stores a short fingerprint of each item (say 8 to 16 bits) in a hash table of buckets, each holding a few entries (typically 4). Every item has exactly two candidate buckets. To query, compute the fingerprint and check both buckets for it. To delete, remove one matching fingerprint from either bucket. To insert, put the fingerprint in either candidate bucket if there is room; if both are full, evict an existing fingerprint from one of them, move it to its alternate bucket, and repeat until something finds space or a retry limit is hit. That eviction chain is the cuckoo's trick of pushing eggs out of the nest.
The partial-key trick
The second bucket must be computable from the entry alone, because during an eviction the filter has only the fingerprint, not the original item. Cuckoo filters define the alternate bucket as bucket XOR hash(fingerprint). XOR is its own inverse, so from either bucket and the fingerprint you can compute the other. That is why a fingerprint can be relocated without knowing what item it came from.
Cuckoo versus Bloom
| Bloom filter | Cuckoo filter | |
|---|---|---|
| Deletes | No (counting variant at 3 to 4× space) | Yes, if the item was inserted |
| Space at ~1% FPR | ~10 bits/item | ~9 bits/item with 4-entry buckets at 95% load |
| Space at ~0.1% FPR | ~15 bits/item | ~12 bits/item |
| Space at high FPR (>3%) | Smaller | Larger (fingerprint minimum overhead) |
| Lookup cost | k memory accesses, scattered | 2 buckets, each a cache line |
| Insert cost | k bit sets, constant | Usually constant; eviction chains near full; insertion can fail when nearly full |
| Capacity | Degrades gracefully as it overfills | Hard limit near 95% load; must be sized |
| Duplicates | Idempotent | Inserting the same item many times fills buckets; cap at 2b copies |
Caveats
Deleting an item that was never inserted can remove another item's identical fingerprint, causing a false negative, so delete only what you know was added (keep that discipline in the calling code). Insertion can fail when the table is nearly full; implementations either size for 90 to 95 percent load or resize. The false-positive rate is set by fingerprint length and bucket size: roughly 2 times bucket entries divided by 2 to the fingerprint bits, so a 12-bit fingerprint with 4-entry buckets gives about 0.2 percent.
Where it fits
Caches that evict (track what is cached without a full key index), session or token blocklists that expire, deduplication windows that slide, network flow tracking, and any Bloom filter use case where items leave the set. Several databases and proxies have adopted cuckoo filters for exactly these reasons; RocksDB offers a related ribbon filter for static sets, which shows the family is still evolving.