Cuckoo filters
A membership filter you can actually delete from, bought by storing fingerprints instead of bits, and paid for with a table that fails loudly instead of degrading quietly.
A Bloom filter has one operation it simply cannot perform: forget something. Clearing a key’s bits would clear bits other keys depend on, so the structure is append-only for life. Every cache that needs to evict, every index that needs to drop a row, every set that needs a TTL runs into this and has to reach for something else.
The cuckoo filter is what you get when you ask for that “something else” and refuse to give up much space to get it.[1]paperCuckoo Filter: Practically Better Than Bloom
Fingerprints, not bits
A Bloom filter stores evidence that a key was inserted, smeared across k bits. A
cuckoo filter stores an actual fingerprint - a short hash of the key, typically 8 to
12 bits - in a slot.
That single change is what makes deletion possible. To remove a key you compute its fingerprint, find the slot holding that exact value, and clear it. You are removing a specific thing rather than trying to un-smear evidence.
Each key has two candidate buckets, each holding a handful of slots (four is the usual choice). A lookup checks both buckets and asks whether any slot holds the fingerprint. If neither does, the key is definitely absent.
The trick that makes it work
Here is the problem that makes this harder than it sounds. When both candidate buckets are full, the filter evicts an existing fingerprint and rehomes it - that is the “cuckoo” part, borrowed from cuckoo hashing.[2]paperCuckoo Hashing But to rehome an evicted entry you need to know its other bucket, and all you have is its fingerprint. The key is gone. You never stored it.
The solution is to make the second bucket derivable from the first plus the fingerprint:
i1 = hash(key)
i2 = i1 XOR hash(fingerprint)Because XOR is its own inverse, this works in both directions: from i1 you get i2, and
from i2 you get back i1. The filter can always find an entry’s alternate home knowing
only where it currently sits and what it contains.[1]paperCuckoo Filter: Practically Better Than Bloom
There is a trap buried in that XOR, and it is the reason the widget above declares its
bucket count as a power of two rather than as a free integer. The involution only holds if
the index is masked - (i XOR h) & (m-1). Write it as (i XOR h) % m with m = 1000
and the arithmetic stops being its own inverse: some entries get relocated to a bucket from
which they can never be relocated back, and the filter starts missing keys it genuinely
holds. The bit pattern looks entirely normal.
The formula
A lookup scans two buckets of b slots. Each occupied slot is one chance for a fingerprint
collision, and with f bits there are 2^f - 1 usable fingerprints. So at load factor α:
P(false positive) ≈ 1 - (1 - 1/(2^f - 1))^(2bα)Every extra fingerprint bit halves the rate and costs one bit per stored item. That is a
much more direct dial than a Bloom filter’s interaction between m, k and n.
Where it beats Bloom, and where it does not
The paper’s claim is specific and worth stating precisely: for false positive rates below roughly 3%, a cuckoo filter uses less space than a Bloom filter, and it supports deletion.[1]paperCuckoo Filter: Practically Better Than Bloom Above that threshold, Bloom is smaller. A cuckoo filter is not a strict upgrade.
There is a second advantage that rarely makes the summary and often matters more in
practice: locality. A Bloom filter lookup with k = 7 touches seven effectively random
bit positions, which is up to seven cache misses. A cuckoo filter touches two buckets,
which is two cache lines.[3]source codeefficient/cuckoofilter - the authors' reference implementation
Deleting a key it never had
This is the failure mode that deserves more attention than it gets, and it is what the widget’s second failure verb does.
Deleting is “find a slot holding this fingerprint and clear it”. Fingerprints are short, so they collide. If you delete a key that was never inserted and its fingerprint happens to match a stored one, the filter cheerfully removes somebody else’s entry.
The result is a false negative: the filter now says “definitely not present” about a key you definitely inserted. That is the one answer a membership filter is never allowed to get wrong, and unlike a false positive it is silent - there is no counter to watch and no degradation to notice.
The cliff
Bloom filters degrade. Push past the n you sized for and nothing breaks, nothing is
reported, and the answer slowly drifts toward “yes” for everything.[4]paperSpace/Time Trade-offs in Hash Coding with Allowable Errors
Cuckoo filters do the opposite. Relocation chains get longer as the table fills, and past roughly 95% occupancy with four slots per bucket, an insert exhausts its kick budget and returns failure. The table is full and says so.
Hit Saturate in the widget and watch the insert-failure counter start climbing while the false positive rate stays flat - the exact inverse of what the same verb does to a Bloom filter.
Here they are under one slider, sized to the same 256 bytes:
Bloom filter
2048 bits, k=5. Accepts every key it is ever given, and never reports a problem.
Cuckoo filter
256 slots of 8-bit fingerprints - the same 256 bytes. Refuses inserts once full, and can delete.
| Measure | Bloom filter | Cuckoo filter | Gap |
|---|---|---|---|
| False positive rate | 0.02 | 0.07 | 3.3× |
The homeless fingerprint
One last detail, which we got wrong on the first attempt and which the widget’s own invariant caught.
When a kick chain exhausts its budget, it is still holding a fingerprint - the one it evicted on its last hop. Dropping it is the obvious thing to do, and it is silently catastrophic: that fingerprint belonged to a key somebody inserted, so discarding it deletes that key. The filter manufactures its own false negatives, and nothing in the bit pattern or the false positive rate reveals it.
The reference implementation keeps exactly one such entry in a victim slot, treats the table as full from that point, and consults the victim on every lookup.[3]source codeefficient/cuckoofilter - the authors' reference implementation The widget above does the same.
The dial
The line - when someone asks
A cuckoo filter stores a short fingerprint of each key in one of two candidate buckets, and finds the second bucket by XORing the first with a hash of the fingerprint - so it can relocate an entry knowing only the fingerprint, never the key. That is what buys deletion, which a Bloom filter cannot do at all, and it caps a lookup at two buckets instead of k scattered probes. The catch is that it fails hard rather than softly: past about 95% occupancy inserts start returning failure, and deleting a key you never inserted can remove a different key's fingerprint and destroy the guarantee the whole structure exists to provide.
Recall
Loading…
Where are you with this?
Saved on this device. Sign in to keep it across devices.
Sources
Primary
- [1]
- [2]
- [3]
Secondary
- [4]