Cuckoo Filters
Cuckoo filters store compact fingerprints in buckets and support deletion, making them an alternative to Bloom filters for some membership workloads.
Cuckoo Filters
Cuckoo filters store compact fingerprints in buckets and support deletion, making them an alternative to Bloom filters for some membership workloads. Hash an item to a primary bucket and short fingerprint. Derive a second candidate bucket from the first bucket and fingerprint. Insert into either bucket; if full, relocate existing fingerprints through a bounded kick-out sequence. Query checks both buckets. Delete removes a matching fingerprint, but collisions mean deletion is approximate unless exact verification is added.
Mechanism and worked example
A cache can use a Cuckoo filter to avoid exact negative lookups while deleting entries as cache items expire. Choose fingerprint width and bucket size for a target false-positive rate; occupancy near capacity increases insertion failures and relocation work.
| Structure | Deletion | Insertion | Merge |
|---|---|---|---|
| Bloom | Not standard variant | Simple bit setting | Compatible OR |
| Counting Bloom | Counter decrement | More memory | Parameter compatibility |
| Cuckoo | Fingerprint deletion | Relocation may fail | No general OR merge |
| Exact set | Exact | Exact capacity | Application-defined |
Failure modes and operations
Insertion can fail after relocation budget is exhausted even if global free slots exist. A false-positive match can delete the wrong item. Concurrent relocation needs synchronization. Independently built filters do not generally merge through simple bitwise OR.
Trade-offs and design boundary
Cuckoo filters support deletion and can be space-efficient at high load, but insertion is more complex and may fail near capacity. Bloom filters have simpler insertion and merge semantics but standard variants cannot delete. Exact sets remain appropriate when false positives are unacceptable.
Interview transfer exercise
When must deletion never remove a colliding object? A Cuckoo filter alone is insufficient; verify exact identity or choose stronger deletion semantics.
Read the diagram
Hash to primary bucket and fingerprint → Derive alternate bucket → Insert or relocate fingerprint → Query checks both buckets; deletion removes match