Cuckoo Filters

The Bloom Filters lesson ended owing us two things, and it was honest about both. First, you can't delete — bits are shared, so clearing one to remove an item would knock out some other member; the only fix, a counting Bloom filter, costs 4× the space. Second, a Bloom filter isn't actually the smallest structure once you demand a low error rate — below a few percent, there's a tighter option. This lesson is that option, and it pays off both IOUs at once.

It's called a cuckoo filter, after the bird that lays its eggs in another bird's nest and shoves the existing eggs out. That shoving is the idea. A cuckoo filter is built on cuckoo hashing, a way of organizing a table where every item has two possible homes instead of one, and where inserting a new item is allowed to evict a resident and relocate it — a small, self-organizing game of musical chairs that lets the table pack extremely tightly. Wrap that idea around short fingerprints instead of whole keys, and you get a membership filter that is compact like Bloom, but can delete, is smaller at low error rates, and touches only two buckets per lookup instead of Bloom's k scattered probes.

Nothing here is free — the cuckoo filter has its own honest cost, and we'll get to it. But if the Bloom Filters lesson was "give up a little accuracy for enormous space savings," this one is "give up a little more structure to get deletes and even better space." Same bargain, sharper tool.

Forget fingerprints for a moment and look at the table itself. In an ordinary hash table, each key hashes to one bucket; if that bucket is taken, you probe or chain, and as the table fills, collisions pile up and everything slows down. Cuckoo hashing (Pagh and Rodler, 2001) makes one change with big consequences: every key gets two candidate buckets, from two different hash functions.

Inserting is a three-step rule:

1. If either of the item's two buckets has a free slot, drop it in. Done.
2. If both are full, pick one, evict a resident, and put the new item there.
3. Now the evicted resident is homeless — so relocate it to its other bucket. If that's full too, evict its resident and keep going. This is the cascade: a chain of shoves that ripples through the table until someone lands in a free slot.

It sounds chaotic, but it's remarkably tame in practice. Because every item has a second option, the table can be packed far tighter than a one-home table before it jams. In a measured run filling a table to ~88% full, 92.4% of inserts needed no eviction at all — they found a free slot immediately — and when a cascade did happen it averaged just 2.87 shoves. The pay-off is a very high load factor: the fraction of slots you can actually fill before the table gives up. Widen each bucket to hold a few items and it climbs dramatically — with four slots per bucket (the standard choice), a real cuckoo table filled to 96.6% before its first failed insert. Compare that to one slot per bucket, which jammed at just 50.5%. Two homes and a shove turn a half-empty table into a nearly-full one.

Now make it a filter. Just like Bloom, we don't want to store whole keys — that would defeat the whole purpose. So instead of the item, each slot holds a short fingerprint: a handful of bits (say 8 to 16) derived by hashing the item. The table becomes an array of buckets, each holding a few fingerprints, and membership is "is this item's fingerprint sitting in one of its two buckets?"

But there's an immediate, sneaky problem — and its solution is the cleverest idea in the whole design. The eviction cascade needs to relocate a resident to its other bucket. In plain cuckoo hashing you'd re-hash the resident's key to find its alternate home. But we threw the key away — all we kept is a fingerprint. How do you find a fingerprint's other home when you don't have the thing it came from?

The answer is partial-key cuckoo hashing, and it's a trick with XOR. The two buckets are defined as:

i₁ = hash(item) and i₂ = i₁ ⊕ hash(fingerprint)

Look at what that buys you. XOR is its own inverse, so the relationship is symmetric: i₁ = i₂ ⊕ hash(fingerprint). From either bucket, you can compute the other one using nothing but the fingerprint itself — you never need the original item. So during a cascade, when you evict a fingerprint from bucket i, its other home is simply i ⊕ hash(fingerprint), computed on the spot. (Verified directly: bounce a fingerprint from its first home to its second and back, a hundred thousand times, and it always returns exactly where it started.) That single algebraic identity is what lets fingerprints and cuckoo hashing coexist — without it, the filter would be impossible to maintain.

The lab below is the whole mechanism in your hands. Add items and watch each fingerprint claim a home — and when both homes are full, watch the eviction cascade shove residents around until one lands. Select an item and the dashed line shows its two homes, joined by that XOR.

Lookup is easy and fast. Compute the item's fingerprint and its two buckets, and check whether that fingerprint is sitting in either one. In neither? Then it was definitely never added — a genuine member would have left its fingerprint in one of exactly these two places. In either? Then it's maybe present. Same one-sided guarantee as Bloom — no false negatives, only false positives — but notice the lookup touched only two buckets. A Bloom filter has to probe k scattered bit positions; a cuckoo lookup reads two adjacent, cache-friendly buckets. That locality is a quiet, real performance win.

And now the headline, the first IOU paid: delete actually works. To remove an item, find its fingerprint in one of its two buckets and erase it. That's it. Because each item's fingerprint occupies a specific slot rather than being smeared across shared bits, you can take it back out without disturbing anyone else. In a measured run, inserting 2,000 items and deleting 1,000 of them left every one of the remaining 1,000 still present — zero false negatives. This is exactly the operation a plain Bloom filter cannot perform; it's the reason cuckoo filters exist. In Redis, which ships both, the contrast is literal: a cuckoo filter has a CF.DEL command that works, while asking a Bloom filter to delete (BF.DEL) returns "ERR unknown command" — the operation simply doesn't exist.

There's one sharp edge to respect, though, and it's a genuine staff-level gotcha. Only ever delete items you know you actually inserted. Here's why: suppose you delete some item x that was never added, but which happens to be a false positive — its fingerprint collides with a real member y's fingerprint sitting in a shared bucket. The delete finds that matching fingerprint and removes it — but it was y's. Now y reads as definitely not present: you've manufactured a false negative, the one error the whole structure is supposed to never make. (This isn't hypothetical — it reproduces easily in a small filter.) A Bloom filter can't fall into this trap because it can't delete at all; a cuckoo filter can, so the rule is firm: deletes are only safe for items you're certain are members.

Every structure in this section trades something, and here's the cuckoo filter's honest cost. Remember the eviction cascade — a shove that triggers another shove. When the table is nearly full, a cascade can go a long way without finding a free slot. To avoid looping forever, the algorithm caps it at some maximum number of kicks (the original paper uses 500). If a cascade blows through that cap without landing, the insert fails: the filter declares itself full and refuses the item.

This is a real difference from Bloom, and it cuts both ways. A Bloom filter never fails to insert — you can always set a few more bits; it just gets gradually less accurate as it fills. A cuckoo filter has a hard ceiling: once you approach its maximum load factor (~95% for four-slot buckets), inserts start failing outright. So a cuckoo filter needs you to know its capacity up front and size it accordingly, or wrap it in logic that grows or splits it when full (which is exactly what Redis does — it chains on an extra filter). There's a related limit: because a fingerprint can only live in its two buckets, a filter can hold at most a handful of copies of the same fingerprint (2 × the bucket size) before that item's inserts start failing — so it doesn't love unbounded duplicates either.

The mental model: a Bloom filter degrades gracefully and never says no; a cuckoo filter stays sharp right up to a wall, then says no. Which behavior you want depends on whether you know how big your set will get. Try it in the lab above — keep adding until the table refuses an insert, and watch the load factor sitting up near its ceiling when it does.

The second IOU: at low error rates, the cuckoo filter is genuinely smaller than Bloom. To see why, count bits per item. A Bloom filter needs about 1.44 · log₂(1/ε) bits per item for a false-positive rate ε. A cuckoo filter needs a fingerprint big enough to keep collisions rare — roughly log₂(1/ε) + 3 bits — divided by its load factor (~0.95), and a semi-sorting optimization shaves off about one more bit. Plot both and the lines cross near 3%:

• At a loose 10% rate, Bloom wins easily — ~4.8 bits/item versus the cuckoo filter's ~6.3. A cuckoo filter carries a minimum fingerprint overhead that only pays off when precision matters.
• At 1%, they're neck and neck and the cuckoo filter edges ahead: ~9.4 bits/item versus Bloom's ~9.6.
• At 0.1%, the gap opens: ~12.6 versus ~14.4. At 0.01%, ~16.8 versus ~19.1.

The rule of thumb from Fan and colleagues, who introduced the cuckoo filter in 2014, is exactly this: for the low false-positive rates that real applications actually want (below ~3%), the cuckoo filter uses less space than a space-optimized Bloom filter — and it deletes, and its two-bucket lookups are kinder to the CPU cache. Above 3%, when you only need a rough filter, Bloom's simplicity and smaller footprint win. The fingerprint size is your accuracy dial here, just as the bit budget was for Bloom: a real filter measured 2.27% false positives with 8-bit fingerprints, 0.14% with 12 bits, and 0.006% with 16 — each extra few bits of fingerprint cutting the error by another order of magnitude.

Two filters, same job, different bargains. The choice comes down to a few honest questions:

• Do you need to delete? Only the cuckoo filter can. If your set changes — items come and go — that's often the whole decision right there.
• How low is your false-positive rate? Below ~3%, the cuckoo filter is smaller too. Above it, Bloom is smaller and simpler.
• Do you know the capacity? Bloom degrades gracefully and never refuses an insert, so it's forgiving when you can't predict the set size. A cuckoo filter has a hard ceiling — great when you can size it, risky when you can't.
• How hot is the lookup path? A cuckoo filter reads two adjacent buckets; Bloom probes k scattered bits. For lookup-heavy workloads, that cache locality matters.

The rule of thumb: reach for a Bloom filter when the set only grows and a rough rate is fine; reach for a cuckoo filter when you need deletes, a low error rate, or fast lookups on a set whose size you know. You can touch both today in Redis — BF.* for Bloom, CF.* for cuckoo, CF.DEL and all.

That's the second sketch, and it closes out the membership question — "is this thing in the set?" — in both its forms, add-only and deletable. The rest of §8's sketches ask different questions of a stream, and each trades exactness for a structure that lives in a few kilobytes of RAM. "How many distinct things have I seen?" — that's HyperLogLog, and it's next. "How often does each thing occur?" — a Count-Min sketch. "How similar are these two sets?" — MinHash. Membership was the warm-up; now we start counting things we could never afford to store.