Cuckoo Filters: Probabilistic Membership Testing with Native Deletion Support

Bloom Filters are widely used for set-membership testing, but they suffer from two major architectural drawbacks: standard Bloom Filters do not support deleting items, and Counting Bloom Filters introduce substantial memory overhead (typically 3x to 4x more space) to support deletions.

Introduced by Bin Fan, David G. Andersen, Michael Kaminsky, and Michael D. Mitzenmacher in 2014, the **Cuckoo Filter** is a compact probabilistic data structure based on Cuckoo Hashing. It provides zero false negatives, bounded false positives, and **native O(1) dynamic deletions** while consuming less memory than a Bloom Filter for target false positive rates below 3%.

Foundations: Cuckoo Hashing Mechanics

Cuckoo Hashing resolves collisions by mimicking the nesting behavior of the cuckoo bird (kicking other eggs out of a nest):

Two Candidate Buckets: Each key $x$ maps to two candidate bucket locations ($i_1$ and $i_2$).
Eviction / Kickout: If both candidate buckets are full upon inserting $x$, the filter greedily evicts an existing occupant from one of the buckets and moves it to its alternative alternate bucket.
Cascaded Relocations: This relocation process repeats until an empty slot is found or a predefined maximum loop threshold (e.g., 500 kicks) is reached, at which point the table is considered saturated.

Partial-Key Cuckoo Hashing & Fingerprints

Storing raw full-size keys or full hashes inside a Cuckoo Filter would consume too much memory. Instead, Cuckoo Filters store tiny bit-level **fingerprints** (typically 8 to 16 bits) derived from the key: $f = \text{fingerprint}(x)$.

Because the original key $x$ is not stored, the filter cannot compute the second bucket index $i_2 = \text{hash}_2(x)$ directly from an evicted fingerprint. To solve this, Cuckoo Filters use **Partial-Key Cuckoo Hashing** with bitwise XOR:

i_1 = hash(x)
i_2 = i_1 ^ hash(fingerprint(x))

Because XOR is self-inverting ($(A \oplus B) \oplus B = A$), calculating the alternate location requires only the current bucket index and the stored fingerprint itself: $i_1 = i_2 \oplus \text{hash}(f)$.

Core Operations and Complexity Analysis

1. Membership Query (Contains)

Given key $x$, compute its fingerprint $f$ and both candidate bucket indices $i_1$ and $i_2$. Inspect all slots within bucket $i_1$ and bucket $i_2$. If fingerprint $f$ is found in either bucket, return true; otherwise, return false. Time Complexity: Strictly $O(1)$ worst-case (inspects at most $2 \times b$ slots, where $b$ is bucket capacity, typically 4).

2. Native Deletion (Delete)

To delete key $x$, calculate $f$, $i_1$, and $i_2$. Search for fingerprint $f$ in bucket $i_1$ or $i_2$. If found, remove a single matching fingerprint instance and clear the slot. Unlike Counting Bloom Filters, this requires no auxiliary counter arrays. Time Complexity: Strictly $O(1)$.

3. Insertion

If either bucket $i_1$ or $i_2$ has an empty slot, place fingerprint $f$ directly. If both buckets are full, select one at random, kick out its occupant $f'$, insert $f$, and relocate $f'$ to its alternate location $i' = i \oplus \text{hash}(f')$. Expected Time Complexity: Amortized $O(1)$.

Cuckoo Filter vs. Bloom Filter Comparison

Dynamic Deletions: Cuckoo Filters natively support deletions; standard Bloom Filters cannot delete keys without rebuilding.
Lookup Speed & Cache Locality: Cuckoo Filters check at most 2 contiguous memory buckets (1 to 2 CPU cache lines); Bloom Filters query $k$ scattered bit positions across the entire array ($k$ potential cache misses).
Space Efficiency: For target false positive rates $p < 0.03$ (3%), Cuckoo Filters use fewer bits per element than Bloom Filters.
Saturation Behavior: When capacity is reached, Bloom Filters experience increased false positives, while Cuckoo Filter insertions start failing (requiring table resizing).

C++ Implementation Blueprint

#include <vector>
#include <string>
#include <cstdlib>
#include <cstdint>

class CuckooFilter {
private:
    static constexpr int BUCKET_SIZE = 4; // 4 fingerprints per bucket
    static constexpr int MAX_KICKS = 500;

    struct Bucket {
        uint8_t slots[BUCKET_SIZE] = {0};
    };

    size_t num_buckets;
    std::vector<Bucket> table;

    uint8_t getFingerprint(const std::string& key) const {
        size_t h = std::hash<std::string>{}(key);
        uint8_t fp = static_cast<uint8_t>(h ^ (h >> 8));
        return (fp == 0) ? 1 : fp; // 0 represents an empty slot
    }

    size_t getIndex(const std::string& key) const {
        return std::hash<std::string>{}(key) % num_buckets;
    }

    size_t getAltIndex(size_t i, uint8_t fp) const {
        size_t h = std::hash<uint8_t>{}(fp);
        return (i ^ h) % num_buckets;
    }

public:
    CuckooFilter(size_t capacity) {
        num_buckets = capacity / BUCKET_SIZE;
        if (num_buckets == 0) num_buckets = 1;
        table.resize(num_buckets);
    }

    bool insert(const std::string& key) {
        uint8_t fp = getFingerprint(key);
        size_t i1 = getIndex(key);
        size_t i2 = getAltIndex(i1, fp);

        for (int b = 0; b < BUCKET_SIZE; ++b) {
            if (table[i1].slots[b] == 0) { table[i1].slots[b] = fp; return true; }
            if (table[i2].slots[b] == 0) { table[i2].slots[b] = fp; return true; }
        }

        // Eviction / Kickout loop
        size_t curr_i = (std::rand() % 2 == 0) ? i1 : i2;
        for (int k = 0; k < MAX_KICKS; ++k) {
            int slot = std::rand() % BUCKET_SIZE;
            std::swap(fp, table[curr_i].slots[slot]);
            curr_i = getAltIndex(curr_i, fp);

            for (int b = 0; b < BUCKET_SIZE; ++b) {
                if (table[curr_i].slots[b] == 0) {
                    table[curr_i].slots[b] = fp;
                    return true;
                }
            }
        }
        return false; // Table saturated
    }

    bool contains(const std::string& key) const {
        uint8_t fp = getFingerprint(key);
        size_t i1 = getIndex(key);
        size_t i2 = getAltIndex(i1, fp);

        for (int b = 0; b < BUCKET_SIZE; ++b) {
            if (table[i1].slots[b] == fp || table[i2].slots[b] == fp) return true;
        }
        return false;
    }

    bool remove(const std::string& key) {
        uint8_t fp = getFingerprint(key);
        size_t i1 = getIndex(key);
        size_t i2 = getAltIndex(i1, fp);

        for (int b = 0; b < BUCKET_SIZE; ++b) {
            if (table[i1].slots[b] == fp) { table[i1].slots[b] = 0; return true; }
            if (table[i2].slots[b] == fp) { table[i2].slots[b] = 0; return true; }
        }
        return false;
    }
};

Real-World Systems and Engineering Use Cases

High-Throughput Key-Value Stores: Caching dynamic active sessions where keys expire or get deleted regularly, avoiding memory leaks present in Bloom filters.
Network Packet Routing & State Tables: High-speed edge firewalls inspecting network traffic flows, removing terminated TCP connection fingerprints in O(1).
Distributed File System Block Indexing: Filtering missing block requests across storage servers with high cache-line locality.
Real-Time Anti-Spam & Fraud Detection: Tracking dynamic blacklists where unbanning or updating user status requires instantaneous key deletion.