How it works
Store a short fingerprint of each key in a table of buckets. Each key has two candidate buckets, and its fingerprint lives in one of them. A lookup checks both buckets: a matching fingerprint means “possibly present,” while no match means “absent,” provided updates and deletions have been handled correctly.
Compute a fingerprint f and a first bucket i1 from the key. A common construction computes the other bucket as i2 = i1 XOR hash(f). This lets the filter move a fingerprint between its two possible buckets without knowing the original key.
To insert a key, use an empty slot in either bucket. If both are full, evict a fingerprint, move it to its alternate bucket, and repeat until a slot opens. Implementations bound these relocation attempts, so an insertion can fail before the table is completely full.
False positives happen when an absent key's fingerprint matches one already stored in a candidate bucket. With b slots per bucket and f fingerprint bits, a useful approximate upper bound is 2b / 2^f. Four-slot buckets and 12-bit fingerprints give roughly a 0.2% false-positive probability.
Deletion removes a matching fingerprint, but the caller must know that the key was actually inserted and has not already been deleted. Deleting an absent key after a false-positive lookup can remove another key's fingerprint and introduce false negatives. Duplicate insertions also need a defined policy that preserves the required multiplicity.
Treat the filter as an optimization in front of authoritative storage. For example, a crawler can skip an exact visited-URL lookup on a trustworthy negative and verify positives in its URL index. A lagging or partially rebuilt filter must not be allowed to report authoritative negatives.
A worked example
Reducing visited-URL index reads
Suppose a crawler tracks 10 million visited URLs and checks 100,000 candidates per second. Assume 90% are new. With four-slot buckets, 12-bit fingerprints, and a design target of 95% occupancy, fingerprint storage is about 16 MB before metadata, layout, and capacity rounding. The approximate false-positive rate is 8 / 4096, or 0.195%. Instead of 100,000 exact lookups per second, the crawler performs about 10,000 for visited URLs plus 176 false-positive lookups for new URLs. It verifies every positive against the exact index, so collisions do not silently suppress new pages. Expired entries can be deleted only when their insertion and deletion lifecycle is known; an incomplete filter is bypassed.
Trade-offs to say out loud
- Deletion without full keys
- Deletion is supported directly, but safe use requires exact knowledge of key membership and disciplined duplicate handling.
- Memory versus false positives
- Longer fingerprints reduce unnecessary backing-store reads but increase memory consumption; compare actual layouts rather than assuming cuckoo filters always beat Bloom filters.
- Fast lookups versus variable insertion work
- Lookups inspect two candidate buckets, while insertion may trigger a relocation chain and fail near capacity.
- Capacity and growth
- A basic cuckoo filter has fixed capacity, so growth requires rebuilding from keys, using a suitable growth-capable implementation, or adding filters at the cost of extra checks.
- Update correctness
- Concurrent updates, failed relocations, and out-of-order change events require safeguards so acknowledged entries do not disappear.
- No exact membership guarantee
- A positive result still requires an exact check when incorrectly rejecting a new item, dropping an event, or granting access would be unacceptable.
When to reach for it
- A large membership set changes frequently, including real deletions, and full keys are too expensive to keep in memory.
- The read path performs many unsuccessful lookups against a database, disk index, or remote service.
- A crawler or discovery system checks large visited or exclusion sets, with an exact lookup available to verify positive results.
- The design can maintain a trustworthy filter alongside the source of truth and has an explicit capacity and rebuild plan.
How to bring it up in the interview
- Start with the avoided cost: “Most checks are misses, so a compact membership filter can save backing-store reads.” Explain why deletion makes a cuckoo filter worth considering over a standard Bloom filter.
- State the correctness contract: negatives are trustworthy only for successfully inserted, correctly maintained entries; positives are hints, not proof.
- Estimate key count, memory, absent-query fraction, and acceptable false-positive rate. Interviewers may ask whether the saved reads justify the extra update path.
- Describe capacity handling before claiming predictable performance: monitor occupancy and insertion failures, rebuild with headroom, and preserve all existing entries if relocation fails.
- Expect probes about deletion, retries, and recovery. Explain why “contains, then delete” is unsafe and why a rebuilding or lagging filter needs a safe bypass path.
Common mistakes
- Calling the filter an exact set or using a positive result alone to discard correctness-sensitive work.
- Deleting any key that tests positive, even though the match might belong to another key.
- Skipping insertion whenever lookup returns positive, which can leave a genuinely new key unrepresented after the colliding key is deleted.
- Ignoring insertion failure or allowing an unsuccessful relocation chain to lose an existing fingerprint.
- Assuming the no-false-negative property still holds when filter updates lag behind the database or a rebuild is incomplete.
Where it comes up
Interview questions where cuckoo filters is part of a strong answer, and why.
- Design a web crawlerVisited-URL deduplication is a central scaling problem where a membership filter can reduce exact index reads, with deletion useful for bounded retention.
- Design a dating app like TinderLarge swipe and exclusion histories make compact membership checks relevant to candidate filtering, with exact verification preventing false matches from hiding eligible profiles.
- Design a distributed key-value storeMembership filters are central to avoiding unnecessary storage reads in an LSM-based storage-engine design, where cuckoo filters can be compared with Bloom filters.
Questions people ask
What is the difference between a cuckoo filter and a Bloom filter?
A standard Bloom filter sets bits at several hash positions, while a cuckoo filter stores fingerprints in two candidate buckets. Cuckoo filters support deletion directly; standard Bloom filters do not, although counting Bloom filters do. Compare memory, lookup cost, insertion behavior, and deletion requirements for your workload.
Can a cuckoo filter have false negatives?
A correctly maintained filter does not return false negatives for successfully inserted entries that have not been deleted. Unsafe deletion, mishandled duplicate keys, lost fingerprints during failed insertion, or stale filter state can break that guarantee. “No false negatives” describes the data structure under its operating rules, not an automatically consistent distributed system.
What happens when a cuckoo filter is full?
Insertion may fail after a bounded number of relocations, even before every slot is occupied. The implementation must preserve existing entries and report failure rather than silently losing data. Plan to rebuild with more capacity, use supported expansion, or bypass the filter until coverage is restored.