Cuckoo Filter: Alternative to Bloom Filter

Key Insights

Cuckoo filters support deletion operations that Bloom filters cannot, while achieving better space efficiency at low false positive rates (typically under 3%)
The “cuckoo kicking” mechanism allows filters to maintain high load factors (95%+) by relocating existing fingerprints during insertion conflicts
For most practical applications requiring membership testing with possible deletions, cuckoo filters should be your default choice over Bloom filters

The Limitations of Bloom Filters

Bloom filters have served as the go-to probabilistic data structure for membership testing since 1970. They’re simple, fast, and space-efficient. But after five decades of use, their limitations have become pain points in modern systems.

The most significant limitation: Bloom filters don’t support deletion. Once you insert an element, it’s there forever. Counting Bloom filters attempted to solve this by replacing bits with counters, but they multiply memory usage by 3-4x and introduce counter overflow risks.

Bloom filters also suffer from capacity inflexibility. You must decide the expected number of elements upfront. Underestimate, and your false positive rate degrades. Overestimate, and you waste memory. The false positive rate is mathematically tied to filter size and element count—there’s no escaping this relationship.

These constraints led researchers Fan, Andersen, Kaminsky, and Mitzenmacher to introduce cuckoo filters in 2014. Their solution addresses deletion, improves space efficiency for practical false positive rates, and often delivers faster lookups.

How Cuckoo Filters Work

Cuckoo filters borrow from cuckoo hashing, a technique where items can occupy one of two possible locations. When a collision occurs, the existing item gets “kicked” to its alternate location, potentially triggering a chain of displacements—like a cuckoo bird pushing eggs out of a nest.

Instead of storing full elements, cuckoo filters store compact fingerprints. A fingerprint is a small hash of the element, typically 8-16 bits. The filter organizes these fingerprints into buckets, with each bucket holding multiple entries (commonly 4).

Here’s the basic structure:

import hashlib
from typing import Optional

class CuckooFilter:
    def __init__(self, capacity: int, bucket_size: int = 4, fingerprint_bits: int = 8):
        self.bucket_size = bucket_size
        self.fingerprint_bits = fingerprint_bits
        self.fingerprint_mask = (1 << fingerprint_bits) - 1
        
        # Number of buckets (power of 2 for efficient modulo)
        self.num_buckets = self._next_power_of_2(capacity // bucket_size)
        
        # Each bucket holds `bucket_size` fingerprints
        # None represents empty slot
        self.buckets: list[list[Optional[int]]] = [
            [None] * bucket_size for _ in range(self.num_buckets)
        ]
        self.size = 0
        self.max_kicks = 500
    
    def _next_power_of_2(self, n: int) -> int:
        p = 1
        while p < n:
            p *= 2
        return max(p, 1)
    
    def _hash(self, data: bytes) -> int:
        return int(hashlib.sha256(data).hexdigest(), 16)
    
    def _fingerprint(self, item: str) -> int:
        h = self._hash(item.encode())
        fp = h & self.fingerprint_mask
        # Fingerprint must be non-zero to distinguish from empty
        return fp if fp != 0 else 1
    
    def _index1(self, item: str) -> int:
        return self._hash(item.encode()) % self.num_buckets
    
    def _index2(self, index1: int, fingerprint: int) -> int:
        # XOR with hash of fingerprint gives alternate location
        fp_hash = self._hash(fingerprint.to_bytes(2, 'big'))
        return (index1 ^ fp_hash) % self.num_buckets

The critical insight is partial-key cuckoo hashing: the alternate bucket location is computed using XOR with the fingerprint’s hash. This means you can calculate both bucket positions knowing only one position and the fingerprint—no need to store the original item.

Core Operations: Insert, Lookup, Delete

The insert operation attempts to place a fingerprint in one of two candidate buckets. If both are full, it kicks an existing fingerprint and relocates it to its alternate bucket, continuing until finding an empty slot or hitting a maximum kick count.

def insert(self, item: str) -> bool:
    fingerprint = self._fingerprint(item)
    i1 = self._index1(item)
    i2 = self._index2(i1, fingerprint)
    
    # Try to insert in either bucket
    for bucket_idx in (i1, i2):
        bucket = self.buckets[bucket_idx]
        for slot in range(self.bucket_size):
            if bucket[slot] is None:
                bucket[slot] = fingerprint
                self.size += 1
                return True
    
    # Both buckets full—start kicking
    import random
    current_idx = random.choice([i1, i2])
    
    for _ in range(self.max_kicks):
        # Pick random slot to kick
        slot = random.randint(0, self.bucket_size - 1)
        
        # Swap fingerprints
        fingerprint, self.buckets[current_idx][slot] = \
            self.buckets[current_idx][slot], fingerprint
        
        # Move to alternate bucket
        current_idx = self._index2(current_idx, fingerprint)
        
        # Try to insert kicked fingerprint
        bucket = self.buckets[current_idx]
        for slot in range(self.bucket_size):
            if bucket[slot] is None:
                bucket[slot] = fingerprint
                self.size += 1
                return True
    
    # Filter is too full
    return False

def lookup(self, item: str) -> bool:
    fingerprint = self._fingerprint(item)
    i1 = self._index1(item)
    i2 = self._index2(i1, fingerprint)
    
    return (fingerprint in self.buckets[i1] or 
            fingerprint in self.buckets[i2])

def delete(self, item: str) -> bool:
    fingerprint = self._fingerprint(item)
    i1 = self._index1(item)
    i2 = self._index2(i1, fingerprint)
    
    for bucket_idx in (i1, i2):
        bucket = self.buckets[bucket_idx]
        for slot in range(self.bucket_size):
            if bucket[slot] == fingerprint:
                bucket[slot] = None
                self.size -= 1
                return True
    return False

All three operations run in O(1) average time. Lookup and delete check at most 2 buckets × 4 slots = 8 locations. Insert is O(1) amortized, though the kicking chain can occasionally extend to hundreds of operations near capacity.

Cuckoo vs. Bloom: Performance Comparison

The space efficiency comparison favors cuckoo filters at practical false positive rates. For false positive rates below 3%, cuckoo filters use less memory per element than Bloom filters. The crossover point depends on implementation details, but the general rule holds.

import time
from bloom_filter2 import BloomFilter  # pip install bloom-filter2

def benchmark_comparison(num_elements: int = 100_000):
    # Setup
    test_items = [f"item_{i}" for i in range(num_elements)]
    query_items = [f"item_{i}" for i in range(num_elements, num_elements * 2)]
    
    # Cuckoo filter
    cf = CuckooFilter(capacity=num_elements, fingerprint_bits=12)
    
    # Bloom filter with similar false positive rate (~0.1%)
    bf = BloomFilter(max_elements=num_elements, error_rate=0.001)
    
    # Insert benchmark
    start = time.perf_counter()
    for item in test_items:
        cf.insert(item)
    cf_insert_time = time.perf_counter() - start
    
    start = time.perf_counter()
    for item in test_items:
        bf.add(item)
    bf_insert_time = time.perf_counter() - start
    
    # Lookup benchmark (existing items)
    start = time.perf_counter()
    for item in test_items:
        cf.lookup(item)
    cf_lookup_time = time.perf_counter() - start
    
    start = time.perf_counter()
    for item in test_items:
        item in bf
    bf_lookup_time = time.perf_counter() - start
    
    # False positive check
    cf_fp = sum(1 for item in query_items if cf.lookup(item))
    bf_fp = sum(1 for item in query_items if item in bf)
    
    print(f"Elements: {num_elements}")
    print(f"Cuckoo - Insert: {cf_insert_time:.3f}s, Lookup: {cf_lookup_time:.3f}s")
    print(f"Bloom  - Insert: {bf_insert_time:.3f}s, Lookup: {bf_lookup_time:.3f}s")
    print(f"False positives - Cuckoo: {cf_fp}, Bloom: {bf_fp}")

Lookup performance in cuckoo filters is often faster because they access only two memory locations versus multiple locations for Bloom filters (which use multiple hash functions). This cache-friendliness matters significantly at scale.

Choose Bloom filters when you need higher false positive rates (above 3%), when deletions are never required, or when you’re working with existing infrastructure that already uses them. Choose cuckoo filters for everything else.

Handling Filter Fullness and Failures

When insertion fails after exhausting the maximum kick count, the filter has reached its practical capacity. This typically happens around 95% load factor with 4 entries per bucket.

def _resize(self) -> bool:
    """Double the filter capacity and rehash all fingerprints."""
    old_buckets = self.buckets
    old_num_buckets = self.num_buckets
    
    # Double capacity
    self.num_buckets *= 2
    self.buckets = [[None] * self.bucket_size 
                    for _ in range(self.num_buckets)]
    self.size = 0
    
    # Reinsert all fingerprints
    # Note: We can't recalculate i1 without original items
    # This is a limitation—practical implementations track items separately
    # or use a different resize strategy
    for bucket_idx, bucket in enumerate(old_buckets):
        for fingerprint in bucket:
            if fingerprint is not None:
                # Use current index as i1, calculate new alternate
                i1 = bucket_idx % self.num_buckets
                i2 = self._index2(i1, fingerprint)
                
                inserted = False
                for idx in (i1, i2):
                    for slot in range(self.bucket_size):
                        if self.buckets[idx][slot] is None:
                            self.buckets[idx][slot] = fingerprint
                            self.size += 1
                            inserted = True
                            break
                    if inserted:
                        break
                
                if not inserted:
                    # Resize failed—restore old state
                    self.buckets = old_buckets
                    self.num_buckets = old_num_buckets
                    return False
    
    return True

In practice, most implementations don’t resize dynamically. Instead, they either allocate sufficient capacity upfront or use a cascade of filters, creating new filters when existing ones fill up.

Real-World Applications

Network deduplication: Detecting duplicate packets in high-speed network streams. The deletion capability allows removing expired entries without rebuilding the entire filter.

Database query optimization: RocksDB uses cuckoo filters in its block-based table format to avoid unnecessary disk reads. When checking if a key exists, the filter quickly eliminates blocks that definitely don’t contain it.

Cache filtering: Preventing cache pollution by tracking recently evicted items. If an item was recently evicted and accessed again, it’s likely worth caching. Deletions handle the natural turnover of tracked items.

Distributed systems: Synchronizing set membership across nodes with bandwidth constraints. The compact representation and deletion support make cuckoo filters suitable for anti-entropy protocols.

Implementation Considerations and Libraries

Fingerprint size directly controls false positive rate: 8 bits gives roughly 3% FP rate, 12 bits gives 0.1%, and 16 bits gives 0.003%. Each additional bit halves the false positive rate but increases memory proportionally.

Bucket size affects load factor and lookup performance. Four entries per bucket achieves 95% load factor with good cache behavior. Larger buckets increase capacity but slow lookups.

For production use, reach for established libraries:

# Python: cuckoopy or cuckoofilter
from cuckoofilter import CuckooFilter

cf = CuckooFilter(capacity=1000000, fingerprint_size=2)
cf.insert("user:12345")
assert cf.contains("user:12345")
cf.delete("user:12345")
assert not cf.contains("user:12345")

// Go: github.com/seiflotfy/cuckoofilter
package main

import "github.com/seiflotfy/cuckoofilter"

func main() {
    cf := cuckoo.NewFilter(1000000)
    cf.Insert([]byte("user:12345"))
    cf.Lookup([]byte("user:12345")) // true
    cf.Delete([]byte("user:12345"))
}

// Rust: cuckoofilter crate
use cuckoofilter::CuckooFilter;

let mut cf = CuckooFilter::with_capacity(1_000_000);
cf.add("user:12345").unwrap();
cf.contains("user:12345"); // true
cf.delete("user:12345");

Start with the defaults these libraries provide. Only tune fingerprint and bucket sizes after profiling shows the need. The default configurations handle the vast majority of use cases efficiently.