Engineering Atlas › System Design Fundamentals

Cuckoo filters that support deletion

12 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

Layout

The filter is an array of m buckets, each holding b fingerprint slots (b = 4 is the common choice). A fingerprint is f bits derived from a hash of the key, with zero reserved to mean "empty slot". Nothing else is stored: no key, no value.

Partial-key cuckoo hashing

Classic cuckoo hashing needs the original key to relocate an evicted item, but a filter only has the fingerprint. So the two indices are tied together through it:

XOR is its own inverse, so from either bucket and the fingerprint you can compute the other. The fingerprint is hashed before the XOR; with a raw 8-bit fingerprint, evicted items would land at most 256 buckets away and crowd one region of the table (Fan et al.). m must be a power of two so the XOR stays in range.

Insert, lookup, delete

To insert, write the fingerprint into either bucket if one has a free slot. Otherwise swap it with a victim in one bucket and move the victim to its alternate bucket, repeating up to a limit such as 500 kicks, after which the table is considered full. Bucket size sets how full the table can get before that happens: about 50% with one slot per bucket, 84% with two, 95% with four and 98% with eight, given long enough fingerprints (Fan et al.). Plain cuckoo hashing with one slot and two choices stalls near the same 50% mark (Wikipedia).

Lookup checks both buckets: at most 8 comparisons in two memory locations. Delete clears one matching copy.

False positives and space

A lookup for an absent key compares against up to 2b stored fingerprints, each matching with probability 1 / 2^f. So the false-positive rate is about 2b / 2^f. With b = 4 and f = 12, that is 8 / 4096, roughly 0.2 percent. The space per item is about f / load bits; at 95 percent load and f = 12, that is 12.6 bits per item.

A Bloom filter needs about 1.44 * log2(1/rate) bits per item: 12.9 bits for 0.2 percent. Below that rate the cuckoo filter wins; above roughly 3 percent its fixed overhead makes Bloom smaller. That crossover assumes the table is sized exactly. Real implementations round m up to a power of two, which can nearly double the memory for an unlucky capacity, and a Boston University study found Bitcoin Core's Bloom filters smaller than the reference cuckoo filter at most capacities for rates of 3% and below (Boskov et al.).

There is a subtler cost. To keep high occupancy, the fingerprint must grow with the logarithm of the table size divided by the bucket size. In practice the bucket size rescues it: with b = 4, about 6-bit fingerprints already reach near-optimal load at a billion buckets, so this lower bound rarely bites before the false-positive target does (Fan et al., Section 4).

Caveats built into the design

Deleting a never-inserted key can remove another key's identical fingerprint. Inserting one key 2b times fills both its buckets. And the filter cannot be resized in place, because the hash bits needed for a larger table were thrown away. If the set is built once and never changes, a static filter is the better tool: xor filters are smaller and faster to query than both Bloom and cuckoo filters, but cannot add or delete after construction (Graf and Lemire).

Down the stack

Layer 1The contract

Any item inserted and not deleted is always reported present. An absent item is reported present with probability at most about 2b / 2^f. Inserts can fail when the table is too full, and the caller must handle that failure. Deletes are safe only for items that were actually inserted. Lookups take a bounded amount of work: two buckets, never more.

Layer 2The mechanism

The reference implementation from the paper's authors packs each bucket's four fingerprints into one word and adds semi-sorting: fingerprints within a bucket are sorted, and the four 4-bit prefixes are encoded as one of 3,876 possible sorted combinations in 12 bits instead of 16, saving one bit per item. Insertion picks a random victim slot on each kick and gives up after 500 kicks. The bucket count also has to stay a power of two for the XOR step; implementations that relax this to save memory break its symmetry, and evictions can then land in a bucket that is neither of an item's two candidates, a true false negative (Boskov et al.).

Redis exposes the filter through CF.RESERVE with capacity, bucket size, maximum iterations, and an expansion factor; it was the RedisBloom module until Redis 8 made it part of the server. Its defaults differ from the paper: two slots per bucket, 20 maximum iterations, an expansion factor of 1 and at most 32 expansions (Redis config). Fingerprints are fixed at 8 bits, so the rate is 2b / 256: 0.78% with one slot per bucket at 55% fill, 3.12% with four slots at 95% fill (Redis docs). A 0.1% target is out of reach there and needs a custom implementation. When a filter fills, Redis chains a new sub-filter rather than resizing, so later lookups must check every sub-filter and the error rates of the sub-filters add up. CF.ADD allows duplicates; CF.ADDNX checks first.

Layer 3The machine

A bucket of four 12-bit fingerprints is 48 bits and fits in one 64-bit word. Checking it is a single load followed by bit tricks: broadcast the query fingerprint into every field, XOR, and test whether any field became zero. That is a few nanoseconds once the word is in cache.

The real cost is memory latency. A table larger than the last-level cache costs about 80 to 100 ns per random access. Both bucket addresses are known up front, so the CPU can fetch them in parallel, and a lookup costs about one memory latency in total. A standard Bloom filter with k = 10 hash functions touches up to 10 cache lines. Inserts near full load are the slow path: each kick is another dependent random access, so a chain of 100 kicks takes around 10 us and tail latency climbs sharply above 90 percent occupancy.

Why it's built this way

  1. Storing whole keys is too expensive, so the filter stores short fingerprints and accepts false positives.
  2. Deleting requires finding the exact copy to remove, so each item must have a small, fixed set of possible locations.
  3. During eviction the key is gone, so the alternate location is derived from the fingerprint by XOR.
  4. Memory latency dominates, so items get two candidate buckets, each sized to fit in one word or cache line, and four slots per bucket let the table reach about 95 percent load.

Diagram

flowchart TD
    K["Key x"] --> H["fp = fingerprint(x), i1 = hash(x)"]
    H --> I2["i2 = i1 XOR hash(fp)"]
    I2 --> F{"Free slot in i1 or i2?"}
    F -->|yes| W["Store fp, done"]
    F -->|no| E["Swap fp with a victim in bucket i"]
    E --> A["i = victim's alternate bucket"]
    A --> G{"Free slot in i?"}
    G -->|yes| W
    G -->|"no, kicks < max"| E
    G -->|"no, kicks = max"| X["Fail: filter full"]

Worked example

A CDN edge node has a 20 TB disk cache holding about 200 million objects. Before going to disk, it wants a cheap in-memory test of "is this object on disk at all?" so misses skip the disk lookup. Evictions require deletes.

Target a false-positive rate of 0.1 percent. With 4-slot buckets that needs 8 / 2^f <= 0.001, so f = 13 bits. Sizing for 95 percent load, 200 million items need about 210 million slots, or 52.6 million buckets; rounded up to the next power of two that is 2^26, about 67 million buckets and 268 million slots. Memory is 268 million times 13 bits, about 436 MB, and the table will run at about 75 percent load, which leaves headroom for growth and keeps eviction chains short.

A standard Bloom filter at 0.1 percent needs 360 MB but cannot delete, so it would need periodic rebuilds. A counting Bloom filter with 4-bit counters supports deletes but needs about 1.4 GB.

Lookups are two random memory reads, negligible at 200,000 requests per second, and each false positive costs only one wasted disk index probe.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
Cuckoo filterDeletes, compact at low error rates, two memory reads per lookupInserts can fail near full, no resize, duplicate inserts break itSet membership with removals and error rate under about 3 percent
Bloom filterSimple, inserts never fail, easy to merge (bitwise OR)No deletion, k memory reads per lookupAppend-only sets, higher error rates, mergeable filters
Quotient filterDeletes, resizable, merges, cache friendlyMore complex, slower when nearly fullYou need resizing or merging with deletes
Exact hash setNo false positivesStores full keys, often 10x the memoryThe set is small or errors are unacceptable

Pitfalls in production

Leadership lens

Check yourself

  1. Why must the alternate bucket be computed from the fingerprint and not from the original key?

    Show answer

    During eviction the filter only has the fingerprint stored in a slot, not the key, so the alternate location must be derivable from the current bucket index and the fingerprint alone.

  2. Where does the false-positive rate of roughly 2b / 2^f come from?

    Show answer

    A lookup compares the query's fingerprint with up to b entries in each of two buckets, and each comparison matches by chance with probability 1 / 2^f.

  3. Why can't you double a cuckoo filter's size the way you resize a hash table?

    Show answer

    Bucket indices in a larger table need hash bits that were discarded when only the fingerprint was kept, so existing entries cannot be relocated without the original keys.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →