Start here: the problem it solves#
TL;DRthe 30-second version
- A cuckoo filter is an approximate membership test: it answers 'is this key in the set?' with 'definitely no' or 'probably yes', in a fixed, tiny amount of memory that never stores the keys themselves.
- It keeps a table of buckets, each with a few slots. For each key it stores a short fingerprint — a few bits of the key's hash — in one of the key's two candidate buckets.
- The two candidate buckets are i1 = hash(key) and i2 = i1 XOR hash(fingerprint). Because the second is derived from the fingerprint alone, you can find an item's other bucket from a stored fingerprint with no key on hand. That is partial-key cuckoo hashing.
- When both candidate buckets are full, it kicks a fingerprint out to its own alternate bucket and repeats — a relocation cascade — until a slot opens up. If it can't find room within a kick limit, the add fails and you resize.
- Its edge over a Bloom filter: you can delete a key (clear its fingerprint), and for low false-positive rates it uses less space. Its cost: an add can fail near full, and you can only delete keys you actually added.
You often need to answer one small question very fast: have I seen this key before? A web crawler asks it of every URL it finds. A database asks it before reading a file from disk. A cache asks it before doing expensive work. Keeping the real set of keys would be huge, and you don't need the keys back — you only need a yes-or-no answer.
The Bloom filter is the classic answer to that question. It uses a bit array and a few hash functions, and it never stores the keys, so it fits a set of a billion keys in a few gigabits instead of terabytes. It says 'definitely not present' or 'possibly present', which is exactly the shape of answer you want.
But a Bloom filter has a hole: you cannot remove a key from it. Its bits are shared across many keys, so clearing the bits for one key would silently delete others that happen to share them. If your set changes over time — URLs that expire, cache entries that get evicted, items that leave a window — a Bloom filter can only grow, never shrink. That is the gap a cuckoo filter fills.
The idea that almost works: a counting Bloom filter#
The reason a Bloom filter can't delete is worth pinning down. To add a key, it sets a handful of bits chosen by its hash functions. Two different keys will often set some of the same bits. So a given bit that is 1 might be 'owned' by several keys at once. Clearing it to delete one key would break every other key that relied on it — turning a true member into a false negative, which the structure is supposed to never produce.
The obvious fix is to replace each bit with a small counter. Adding a key increments its counters; deleting a key decrements them. A counter stays above zero as long as any key still needs it, so deletes become safe. This is a real structure — the counting Bloom filter — and it works.
The problem is the price. To make counter overflow rare you need about four bits per cell instead of one, so a counting Bloom filter costs roughly three to four times the memory of a plain Bloom filter for the same false-positive rate. You wanted deletes, and you paid for them with a big chunk of the space savings that made the Bloom filter attractive in the first place.
The mechanism: fingerprints in two candidate buckets#
A cuckoo filter is a table of buckets. Each bucket has a fixed number of slots — four is the usual choice — and each slot holds one fingerprint or is empty. A fingerprint is just a few bits of the key's hash, say one byte. The filter never stores the key, only this short stand-in for it.
Every key gets two candidate buckets, and it may live in either one. The first is the key's home bucket, straight from its hash. The second is where the clever part lives, so let's name both precisely.
- Bucket one is i1 = hash(key), folded to the number of buckets.
- Bucket two is i2 = i1 XOR hash(fingerprint). It is the first bucket's index, combined with a hash of the fingerprint using exclusive-or.
Exclusive-or is its own inverse, and that is the entire trick. Given a fingerprint sitting in some bucket i, its other candidate bucket is i XOR hash(fingerprint) — and you can compute that from the fingerprint alone, without ever knowing the key it came from. So when you need to move a stored fingerprint, you can find its alternate home even though the key is long gone. This is called partial-key cuckoo hashing: the alternate bucket is derived from a partial key, the fingerprint, rather than the full key.
With that in place, the three operations are short. Looking up a key checks both of its candidate buckets for the fingerprint. Deleting a key finds the fingerprint in one of them and clears that slot. Adding a key is where the cuckoo behavior shows up.
- Add: compute the fingerprint and the two candidate buckets. If either bucket has a free slot, drop the fingerprint in and stop.
- If both candidate buckets are full, pick one and kick out an existing fingerprint to make room for the new one.
- Move the kicked-out fingerprint to its own alternate bucket. If that bucket is full too, kick one of its fingerprints onward, and repeat — a relocation cascade.
- Stop when a fingerprint lands in a free slot. If the cascade runs past a kick limit without finding room, the table is too full: the add fails and you resize.
The bird gives the structure its name. A cuckoo chick shoves the other eggs out of the nest; here a new fingerprint shoves an old one out of a full bucket, and the evicted fingerprint goes and does the same somewhere else. Because every fingerprint always has a second home it can be found from, this shuffling never loses anything — it just repacks the table until everyone has a slot.
8 buckets, 2 slots each · key 'berry' has fingerprint d2 and candidate buckets 7 and 5, both full
Go deeperWhy the false-positive rate is bounded, and how small the fingerprint can be
A lookup only ever compares fingerprints, so the one way it can be wrong is a fingerprint collision: some other key stored the same fingerprint in one of the buckets you check. With f-bit fingerprints and b slots per bucket, a query touches up to 2b stored fingerprints, and each matches the target by chance with probability about 1 in 2^f. So the false-positive rate is at most roughly 2b / 2^f.
Read that backwards to size the fingerprint. For a target false-positive rate ε, you need about f ≈ log2(2b / ε) bits. With b = 4 slots and a 1% target, that is around ten bits per item — a byte or two, whatever the number of keys. Adding a couple of bits to the fingerprint cuts the false-positive rate by roughly a factor of four.
The bucket size b is a second dial. Bigger buckets pack the table tighter — with b = 4 you can fill to about 95% before adds start to fail — but each extra slot a query scans slightly raises the false-positive rate, which you pay back with one more fingerprint bit. Four slots is the sweet spot the original paper recommends, and it is why so many implementations use it.
A worked example: add, cascade, delete#
Take a small filter with 8 buckets and 2 slots each, and add a few fruit names. The first few land straight into an empty candidate bucket with no fuss: compute the fingerprint, find a free slot in bucket i1 or i2, drop it in, done.
Now add 'berry', and suppose both of its candidate buckets, 7 and 5, are already full. This is where the cuckoo move happens.
- Bucket 7 is full and bucket 5 is full, so make room. Kick a fingerprint out of bucket 7 — call it 3b — and put berry's fingerprint d2 there instead.
- 3b needs a new home. Its alternate bucket, found from 3b alone, is bucket 5. But bucket 5 is full too, so kick one of its fingerprints — f2 — out and put 3b there.
- f2 needs a home. Its alternate bucket is 6, which has a free slot. f2 lands there, and the cascade settles after two kicks. 'berry' is now a member.
Nothing was lost in that shuffle. Every fingerprint that moved went to a bucket it was always allowed to live in — its own alternate — so a later lookup for any of those keys still finds it in one of its two candidate buckets. The table just got repacked to fit one more item.
Now the payoff a Bloom filter can't match: delete 'apple'. Recompute its fingerprint and its two candidate buckets, find the fingerprint in one of them, and clear that slot. A query for 'apple' now checks both buckets, finds the fingerprint in neither, and returns 'definitely not present'. The set shrank, in place, with no rebuild.
PredictYou delete a key that was never added, whose fingerprint happens to equal a stored fingerprint sitting in one of its candidate buckets. What goes wrong?
Hint: Delete clears a slot by matching the fingerprint, not the key.
You remove the wrong key. The delete finds a matching fingerprint in a candidate bucket and clears it — but that fingerprint belonged to a different key that shares it. That key now reads as absent, which is a false negative the structure is supposed to never produce. This is why a cuckoo filter's delete is only safe for keys you actually inserted: clearing a fingerprint you never stored can silently evict someone else's. The membership answer stays correct only under that rule.
Memory and speed#
A lookup or a delete touches exactly two buckets, and each bucket is a short run of slots that sit next to each other in memory. So both are constant-time and, in practice, two cache-line reads — which is part of why a cuckoo filter is fast. An add is also constant-time on average; only near a full table does the relocation cascade add a few extra bucket touches.
- Memory is the table: numBuckets × slots × fingerprint-bits, fixed at creation. Per item it works out to about f / α bits, where f is the fingerprint size and α is the load factor you can reach — roughly 0.95 with 4-slot buckets. There is no per-item pointer or key stored.
- Lookup and delete are O(1): compute the fingerprint and two buckets, scan up to 2b slots. No probing beyond the two candidate buckets, ever.
- Add is O(1) on average. When both candidate buckets are full it triggers a relocation cascade, capped at a kick limit (the original paper uses 500). Hitting that cap means the table is too full and the add fails.
- The false-positive rate is bounded by about 2b / 2^f, one-sided (no false negatives for keys you added). Add fingerprint bits to shrink it.
Variants and sharp edges
- Bucket size b: b = 4 is the common default (high load factor, small enough that the false-positive rate stays cheap). b = 2 fills to a lower load but scans fewer slots per query; b = 8 packs tighter but needs an extra fingerprint bit.
- Semi-sorted buckets: fingerprints within a bucket can be sorted and compressed, saving about one bit per item. This is the 'cuckoo filter, semi-sorted' variant in the original paper.
- Counting cuckoo filter: to support inserting the same key many times, store a small count alongside each fingerprint, so duplicates don't each consume a slot.
- Number of buckets must be a power of two, so that i1 XOR hash(fingerprint) stays a valid bucket index. That constrains sizing to powers of two unless you use a variant (such as vertical or 'morton' layouts) built to relax it.
Strengths, limits, and when to reach for it
A cuckoo filter makes a clear bargain against a Bloom filter: gain deletion and, at low false-positive rates, better space — at the cost that an add can fail near full and deletes must be disciplined.
- Deletion — you can remove a key by clearing its fingerprint, so a set that changes over time can shrink in place. This is the headline reason to pick it over a Bloom filter.
- Space at low error — for target false-positive rates below about 3%, a cuckoo filter uses fewer bits per item than even a space-optimized Bloom filter; around 3% they are roughly even, and above that the Bloom filter can win.
- Fast lookups — a query reads just two adjacent buckets, so it is often two cache-line accesses, versus a Bloom filter's several scattered bit probes.
- The limits — an add can fail once the table passes its load threshold, so you must size for headroom and be ready to resize; deletes are only safe for keys you actually inserted; the same key can be inserted at most 2b times; and the bucket count must be a power of two.
- When a Bloom filter still wins — if you never delete and your target false-positive rate is loose (a few percent or higher), a plain Bloom filter is simpler, never fails an add, and can be more compact.
Cuckoo vs the neighbours
| Bloom filter | Counting Bloom | Cuckoo filter | |
|---|---|---|---|
| Answers | is it present? | is it present? | is it present? |
| Delete? | no | yes | yes (added keys only) |
| Memory vs Bloom | baseline | ~3–4× larger | smaller for ε < 3% |
| Add can fail? | no | no | yes, near full |
| Lookup cost | k scattered bit probes | k scattered counters | 2 adjacent buckets |
| False negatives? | never | never | never (with disciplined deletes) |
All three answer the same question — is this key present? — and none stores the keys. A Bloom filter is the compact, append-only default. A counting Bloom filter buys deletes by spending three to four times the memory. A cuckoo filter buys deletes and, at low error rates, better space, by accepting that an add can fail near full and that deletes must be limited to keys you added.
There are newer cousins worth knowing by name. A quotient filter also stores fingerprints and supports deletes, using a different collision scheme. An xor filter is smaller and faster to query than either but is immutable once built — no adds or deletes after construction. Which one fits depends on whether your set changes and how tight your error budget is.
Where cuckoo filters run in the wild
- Redis — the cuckoo filter data type (CF.ADD / CF.EXISTS / CF.DEL / CF.COUNT) is offered alongside the Bloom filter exactly for the case where you need to remove items, such as a deduplication set whose entries expire.
- Deletion-heavy dedup and caches — anywhere a membership set changes over time: 'have I processed this event?' over a sliding window, 'is this item still cached?', 'has this token been revoked?'.
- Networking — approximate set membership in switches and middleboxes, where the low false-positive rate and compact size matter and entries come and go with flows.
- Storage and databases — as a Bloom-filter alternative in read paths when the on-disk set of keys is updated in place rather than only appended.
Common misconceptions & gotchas
Can a cuckoo filter give a false negative?
Not if you only delete keys you actually inserted. Every added key's fingerprint sits in one of its two candidate buckets, and a lookup checks both, so a present key is always found. The one way to break this is to delete a key you never added: the delete may clear a matching fingerprint that belongs to a different key, making that key falsely absent. Discipline on deletes is the price of correctness.
Why can an add fail when the table isn't even full?
Because every key can only live in two specific buckets. If both are full and the relocation cascade can't find a free slot within the kick limit, the add fails even if empty slots exist elsewhere — those slots just aren't reachable for this key. This gets likely past the load threshold (about 95% for 4-slot buckets). The fix is to build a bigger table and rehash.
Why must the number of buckets be a power of two?
The second candidate bucket is i2 = i1 XOR hash(fingerprint). For that exclusive-or to always land on a valid bucket index, and for the relation to be reversible (i1 = i2 XOR hash(fingerprint)), the index space has to be a power of two. Sizes in between need a variant designed to relax this, at some added complexity.
How is this different from cuckoo hashing?
Cuckoo hashing is a hash table that stores whole keys and uses two hash functions plus eviction to keep lookups to two probes. A cuckoo filter stores only fingerprints, not keys, and computes the second bucket from the fingerprint (partial-key hashing) so it can relocate entries without the keys. That is what shrinks it from a hash table to a compact membership filter.
QuizYou insert the same key 'user:42' into a cuckoo filter with 4-slot buckets nine times in a row. What happens?
- The ninth insert fails — the key's two buckets hold only 2b = 8 slots for its fingerprint
- All nine succeed — the filter grows to fit them
- Only the first succeeds — duplicates are rejected
- The false-positive rate drops with each insert
Show answer
The ninth insert fails — the key's two buckets hold only 2b = 8 slots for its fingerprint — The key always yields the same fingerprint and the same two candidate buckets. With 4 slots per bucket, those two buckets hold 2b = 8 fingerprints between them, so the same fingerprint can be stored at most eight times. The ninth insert finds no room in either bucket and the cascade can't help — the fingerprint is only allowed in those two buckets — so the add fails. If you need to insert a key many times, use a counting cuckoo filter, which keeps a tally instead of a slot per copy.
In an interview
Lead with the gap it fills. A Bloom filter gives you a tiny 'have I seen this key?' test but can't delete, because its bits are shared across keys. A cuckoo filter keeps the tiny footprint and adds deletion by storing a short fingerprint of each key in a table of buckets you can actually remove from. Name where it runs: Redis CF commands, and deletion-heavy dedup sets and caches.
Then explain the mechanism in three moves. First, each key has two candidate buckets — i1 from its hash, and i2 = i1 XOR hash(fingerprint) — and the exclusive-or makes the second recoverable from the fingerprint alone, which is partial-key cuckoo hashing. Second, an add drops the fingerprint into a free slot of either bucket, and if both are full it kicks a fingerprint out to its alternate and cascades until a slot opens. Third, lookup checks both buckets and delete clears the fingerprint from one of them.
If pushed, give the numbers and the caveats: the false-positive rate is about 2b/2^f so you size the fingerprint from your error target; 4-slot buckets fill to about 95% before adds start to fail; deletes are only safe for keys you inserted; and for error rates below a few percent it beats a space-optimized Bloom filter on memory. Then open the simulator: add a key into an empty bucket, force both candidate buckets full to watch a relocation cascade, then delete a key and query it to watch the answer flip to 'not present'.
References & further reading
- Fan, Andersen, Kaminsky & Mitzenmacher — Cuckoo Filter: Practically Better Than Bloom (CoNEXT 2014) — the original paper: partial-key cuckoo hashing, the 2b/2^f bound, bucket size 4, and the space comparison with Bloom
- Fan et al. — Cuckoo Filter: Better Than Bloom (USENIX ;login: 2014) — a shorter, readable write-up of the same design and its trade-offs
- Redis — Cuckoo filter data type (CF.ADD / CF.EXISTS / CF.DEL) — a production implementation offered alongside the Bloom filter for the delete-supporting case
- efficient/cuckoofilter — the authors' reference C++ implementation — the canonical code: bucket layout, semi-sorting, and the insert/relocate loop
- Mitzenmacher — Cuckoo Filters (My Biased Coin) — one of the authors on the intuition behind partial-key cuckoo hashing
Ready to try it?
The simulator is a real, deterministic implementation — pick a scenario and step through it, scrubbing the timeline forward and backward through every change.