Why architecture matters here
Why not just use a Bloom filter and move on? Three production pressures. Deletion: caches evict, LSM levels compact away keys, flows expire — and a Bloom filter cannot unset a bit that other items share. The standard workaround, the counting Bloom filter, replaces each bit with a 4-bit counter and quadruples memory for the same false-positive rate. Cache behavior: a Bloom lookup at 1% FPR probes ~7 random bits — up to 7 cache misses; a cuckoo filter lookup reads exactly two buckets, and with 4-slot × 8-bit-fingerprint buckets each bucket is 4 bytes — two cache lines worst case, one when i1 hits. Space at low FPR: Bloom costs 1.44·log2(1/ε) bits per item forever; a cuckoo filter at 95% load costs (f + 3)/0.95-ish bits per item with ε ≈ 2b/2^f, and the crossover lands around ε = 3% — below that, cuckoo is strictly smaller. Most serious systems run at 0.1–1%, squarely in cuckoo territory.
The architectural insight worth internalizing is why deletion falls out for free: because each item occupies one identifiable slot (its fingerprint in one of two buckets) rather than smearing itself across k shared bits, membership becomes ownership — and anything owned can be moved or removed. Every capability the cuckoo filter adds over Bloom traces back to that single change of representation.
The architecture: every piece explained
The structure is an array of buckets, each holding b fingerprint slots — b=4 is the standard, because it lifts the achievable load factor from 50% (b=1) to ~95% while keeping the false-positive rate manageable. A fingerprint is f bits of a hash of the item, f typically 8–16: ε ≈ 2b/2^f, so 8 bits with b=4 gives ~3%, 12 bits ~0.2%, 16 bits ~0.012%. The two candidate buckets are i1 = hash(x) and i2 = i1 XOR hash(fp(x)). The XOR construction is chosen for one property: it is an involution — i1 = i2 XOR hash(fp) too — so from any bucket holding a fingerprint, the alternate is computable from local information. Hashing the fingerprint before XORing matters: XORing the raw fingerprint would confine alternates to a 2^f-bucket neighborhood; hashing spreads them across the table.
Lookup: compute fp, i1, i2; scan both buckets for fp; report maybe/no. Delete: same scan, remove one matching copy — correct only if the item was actually inserted, which is why delete without prior insert is undefined behavior, and why duplicate inserts must be bounded (2b copies max) if deletes are in play. Insert is where cuckoo earns its name: if either bucket has a free slot, done; otherwise evict a random resident fingerprint, move it to its alternate (computable via the XOR), and if that bucket is also full, the eviction cascades — up to a MaxKicks bound, canonically 500. The chain almost always terminates in a handful of kicks below ~95% load; hitting MaxKicks means the table is effectively full, and the filter must report insert failure, spill to a small stash, or trigger a resize. A practical refinement, semi-sorting, sorts the four fingerprints within a bucket and encodes them compactly, saving about one bit per item at some CPU cost.
End-to-end flow
Trace an insert under pressure. Item x hashes to fp=0xA7, i1=412; bucket 412's four slots are full, and so is i2=8891. The filter picks a victim in 412 — say fp=0x3C — computes its alternate 412 XOR hash(0x3C) = 1077, and finds 1077 has a free slot: 0x3C moves, 0xA7 takes its place, chain length 1. At 90% load, chains like this average a few kicks; the p99 grows as load climbs, which is why kick-chain length is the operational early-warning metric — it inflects sharply before inserts start failing outright.
Now the read path in situ: an LSM storage engine keeps one cuckoo filter per SSTable. A point-get for key k checks each level's filter before touching disk; two cache-line reads per table, and the 0.2% false-positive rate (f=12) means one wasted disk probe per five hundred absent-key lookups. When compaction merges tables and drops tombstoned keys, the engine deletes those keys from the surviving filter instead of rebuilding it from scratch — the operation Bloom could not offer. Meanwhile a duplicate-suppression service uses the same structure differently: insert on first sight, delete when the item's TTL lapses, and the filter's occupancy tracks the live window instead of growing monotonically. The failure path completes the picture: during a traffic spike the dedup filter reaches 96% load, a chain hits MaxKicks, and the insert fails — the service routes the item to the exact-check slow path and increments a saturation counter, which is precisely the graceful degradation the design intends. An insert failure is the filter saying resize me, not a correctness bug.