The Cuckoo Filter: A Bloom Filter That Can Delete

The problem: membership you can also delete from

Countless systems ask the same question millions of times a second: have I seen this key before? A CDN checks whether a URL is cacheable; a database skips an on-disk table that cannot hold a row; a crawler avoids re-fetching a page. Storing the full key set is too expensive, so we accept a controlled lie. An approximate membership query (AMQ) structure may occasionally answer "present" for a key that is absent (a false positive), but it never answers "absent" for a key that is present — zero false negatives.

The classic AMQ structure is the Bloom filter, but it has a stubborn weakness: you cannot delete from it. Each key sets k shared bits, so clearing one key's bits would also unset bits belonging to other keys — a plain Bloom filter can only grow. The cuckoo filter, introduced by Bin Fan, Dave Andersen, Michael Kaminsky, and Michael Mitzenmacher in their 2014 CoNEXT paper “Cuckoo Filter: Practically Better Than Bloom,” fixes this. It supports insertion, lookup, and deletion, often uses less space than a Bloom filter at low false-positive rates, and answers every query by inspecting just two memory locations.

Fingerprints in a cuckoo table, and the XOR trick

A cuckoo filter is a compact cuckoo hash table (Pagh and Rodler, 2001) that stores not keys but short fingerprints — an f-bit hash of each item, typically 6–16 bits. The table is an array of m buckets, each holding b slots (usually b = 4). Every item may live in exactly one of two candidate buckets, and a lookup only ever inspects those two.

In ordinary cuckoo hashing the two buckets are two independent hashes of the key. But a filter throws the key away — it keeps only the fingerprint. So how do you relocate an entry when you no longer know the item it came from? The answer is partial-key cuckoo hashing. Bucket indices are defined as:

i1 = hash(x)
i2 = i1 XOR hash(fingerprint(x))

Because XOR is its own inverse, either index yields the other from data you already hold: i1 = i2 XOR hash(f). Given only an entry's fingerprint and its current bucket, you can always compute its alternate bucket — no original key required. Crucially it is hash(f), not f itself: hashing the fingerprint first scatters the alternate bucket across the whole table, so an item's two homes are far apart and uniformly spread rather than clustered in nearby indices. The table size m is kept a power of two so the XOR result is always a valid bucket index.

Insert, lookup, delete — and the eviction cascade

Lookup is trivial and worst-case O(1): compute f, i1, and i2, then scan the at-most 2b slots in those two buckets for a matching fingerprint. If found, report maybe present; otherwise definitely absent. Because an inserted item is guaranteed to sit in one of its two buckets, there are never false negatives.

Insertion is where the cuckoo behavior appears. If either candidate bucket has a free slot, drop the fingerprint in and finish. If both are full, the filter kicks out a random resident fingerprint e, puts the new one in its place, then relocates e to its alternate bucket — computed on the spot as i XOR hash(e). That bucket may also be full, forcing another eviction, so displacements can cascade in a chain:

insert(x):
  f = fingerprint(x); i = hash(x)
  if bucket[i] or bucket[i XOR hash(f)] has room:
     add f; return Done
  for n in 1..MaxKicks (default 500):
     swap f with a random entry in bucket[i]
     i = i XOR hash(f)
     if bucket[i] has room: add f; return Done
  return FAILURE   // table is effectively full

Deletion mirrors lookup: find a slot in either candidate bucket whose fingerprint equals f and clear it. This is exactly the operation Bloom filters cannot perform — though, as we will see, it carries a correctness caveat.

Space, load factor, and the false-positive math

A lookup for an absent item false-positives only if one of the ≤ 2b fingerprints it scans happens to equal f. With f-bit fingerprints that probability is about 2b / 2^f. Inverting, to hit a target rate ε you need f ≈ ⌈log₂(2b/ε)⌉ bits; for b = 4 that is log₂(1/ε) + 3.

Each item then costs f bits divided by the achieved load factor α, so space ≈ (log₂(1/ε) + 3)/α bits per item. The empirical magic is that 4-slot buckets reach α ≈ 95% before insertions start failing (b = 2 tops out near 84%, b = 8 near 98% — more slots per bucket give more room to absorb collisions). At ε = 1% that is roughly 10 / 0.95 ≈ 10.5 bits per item.

Fan et al. shave off more with semi-sorting: the fingerprints in a bucket are unordered, so you can sort them and store the sorted tuple as an index into a precomputed table. For b = 4 with 4-bit fingerprints there are only 3876 monotone combinations, which pack into 12 bits instead of 16 — a saving of 1 bit per item. With semi-sorting the cuckoo filter uses less space than a space-optimal Bloom filter (1.44·log₂(1/ε) bits) whenever ε is below roughly 3%, while additionally supporting deletion and answering each query in two cache-line reads instead of k scattered probes.

Where it wins, and real deployments

The cuckoo filter shines exactly where the Bloom filter's immutability hurts:

• Deletable working sets. Tracking active flows, sessions, or recently-seen items in a sliding window requires forgetting. A Bloom filter can only be periodically discarded and rebuilt; a cuckoo filter deletes in place.
• RedisBloom / Redis Stack ships a first-class cuckoo-filter type (CF.ADD, CF.EXISTS, CF.DEL, CF.COUNT) alongside its Bloom filter, precisely so applications can delete members and count duplicates.
• Deduplication and caching. Content-addressed stores and web caches use it to answer "seen this blob?" while still evicting entries as they expire.
• Networking and security. The original paper targeted network middleboxes — IP/flow membership and blocklists that add and remove entries — where per-packet latency makes the two-bucket, cache-friendly lookup attractive.

The reference C++ implementation lives at github.com/efficient/cuckoofilter from the authors' group at Carnegie Mellon and Intel Labs, with widely-used ports in Go, Rust, and Python. Its lineage runs from Pagh and Rodler's cuckoo hashing through the same team's MemC3 and SILT work on cache-efficient hashing for key-value stores.

Failure modes, limits, and its cousins

Bounded capacity. Unlike a Bloom filter, which merely earns a higher false-positive rate as it fills, a cuckoo filter can outright fail to insert. When an eviction chain exceeds MaxKicks (default 500) the table is declared full. You must size it for the expected item count, and because entries store only fingerprints — not keys — you cannot simply rehash into a larger table on overflow; growing generally means rebuilding from the original data source. This is a genuine edge on which the resizable quotient filter wins.

Deletion must be honest. You may only delete items you actually inserted. Deleting a key that was never added can remove a fingerprint that legitimately belongs to a different item sharing that fingerprint and bucket, introducing a false negative and breaking the AMQ guarantee. Duplicate insertions are allowed but consume capacity: the same item can be stored at most 2b times.

Fingerprints have a floor. Partial-key cuckoo hashing can only reach 2^f distinct alternate buckets, so for very large tables the fingerprint must be long enough (it must grow with the log of the table size) or the load factor collapses; in practice 6–16 bits is ample.

Against its relatives: the quotient filter resizes and merges more gracefully and touches a single cache line; the cuckoo filter is simpler, deletes cleanly, and is slightly smaller at very low ε. Both localize a key's data to a handful of slots — the structural move that unlocks deletion — whereas a Bloom filter smears every key across the entire array.

Cuckoo filter vs. other approximate-membership structures (ε = target false-positive rate)

Structure	Bits per item (ε=1%)	Accesses per lookup	Delete? / Resize?
Bloom filter	1.44·log₂(1/ε) ≈ 9.6	k random probes	No / No
Counting Bloom filter	~4× Bloom (≈38)	k random probes	Yes / No
Cuckoo filter (b=4)	(log₂(1/ε)+3)/0.95 ≈ 10.5 (semi-sorted ≈9.5)	2 buckets (2 cache lines)	Yes / No (fixed capacity)
Quotient filter	~2.125 + log₂(1/ε) ≈ 9	~1 (one cluster)	Yes / Yes
Cuckoo hash table (exact)	stores full keys	2 buckets	Yes / Yes (rehash)