Cuckoo Filters: Fingerprints, Buckets, and Deletion

In one line

A cuckoo filter stores short fingerprints of items in a table of buckets (typically 4 slots each); each item has two candidate buckets and insertion evicts and relocates existing fingerprints when both are full. It supports deletion, reaches ~95% occupancy, and uses less space than a Bloom filter when the target error is below about 3%.

0/6 · 0%

Think of it like this

Assigning coats to two possible hooks per person. If both your hooks are full, you move someone else's coat to their other hook, and so on, like a cuckoo pushing eggs out of a nest, until everyone fits.

Key ideas

01
Structure (Fan et al., 2014): an array of buckets, each holding b fingerprints of f bits. An item's fingerprint fp = hash(x) truncated to f bits.
02
Partial-key cuckoo hashing: bucket i1 = hash(x) mod B, i2 = i1 XOR hash(fp) mod B. The second bucket can be computed from the first and the fingerprint alone, which is what makes relocation possible without the original item.
03
Insert: put fp in i1 or i2 if either has a free slot; else evict a random fingerprint from one of them, move it to its alternate bucket, repeat up to a limit (~500 kicks); if it still fails, the filter is full.
04
Lookup: check whether fp is in bucket i1 or i2 (2 bucket reads, cache-friendly). Delete: remove one copy of fp from either bucket.
05
False positives come from another item with the same fingerprint in one of the two buckets: roughly 2b / 2^f. Space ≈ (log2(1/ε) + 3) / α bits per item (α ≈ 0.955 load), so about 10.1 bits at 1% (Bloom 9.6) and 13.6 bits at 0.1% (Bloom 14.4).
06
Limits: deletes must be for inserted items (else another item's matching fingerprint is removed); the same item can be inserted at most 2b times; inserts can fail near full capacity, so size with headroom.

Code & diagrams

cuckoo.txttext

buckets (b = 4 slots each), fingerprint f = 8 bits
insert x: fp = 0xA3, i1 = 17, i2 = 17 XOR hash(0xA3) = 922
  bucket 17: [0x11, 0x5C, 0x9E, 0x02]  full
  bucket 922: [0x7F, 0xA3?, --, --]    free slot -> store 0xA3
lookup y: fp = 0x44, i1 = 301, i2 = 1450 -> neither bucket holds 0x44 -> DEFINITELY ABSENT
delete x: remove one 0xA3 from bucket 17 or 922

Bits/item (alpha = 0.955):   eps 3%: cuckoo 8.4  bloom 7.3
                             eps 1%: cuckoo 10.1 bloom 9.6
                             eps 0.1%: cuckoo 13.6 bloom 14.4

cuckoo.redisredis

127.0.0.1:6379> CF.RESERVE cf:sessions 10000000 BUCKETSIZE 4
OK
127.0.0.1:6379> CF.ADD cf:sessions s:9f3c
(integer) 1
127.0.0.1:6379> CF.EXISTS cf:sessions s:9f3c
(integer) 1
127.0.0.1:6379> CF.DEL cf:sessions s:9f3c
(integer) 1
127.0.0.1:6379> CF.EXISTS cf:sessions s:9f3c
(integer) 0

Interview problem

The problem

Membership with frequent deletion and tight memory

You need membership checks for 200 million active items with frequent deletions and tight memory, target error 0.1%. Evaluate Bloom, Counting Bloom and Cuckoo filters.

The interviewer follows up

Why can a cuckoo filter fail an insert when a Bloom filter never does?

Explain it without notes

How does partial-key cuckoo hashing let the filter relocate fingerprints without the original items?

Practice

Compare memory for 100M items at 1% and at 0.1% for Bloom and Cuckoo filters.

Trade-offs

↔
Cuckoo filters add deletion and fast lookups but can fail inserts near capacity and are more complex to implement.

Done when you can

I can explain cuckoo filter insertion, lookup, deletion, space and limits, and choose it over Bloom when appropriate.

Command Palette