Cuckoo Filters: Fingerprint Placement and the Load-Factor Ceiling

A Bloom filter answers membership with a bit array and no stored keys, which is why it cannot support deletion cheaply. A cuckoo filter answers the same question while storing a short fingerprint per entry, which makes deletion a local operation and, at moderate error rates, uses less space than a counting Bloom filter. The trade it makes is a hard capacity limit: the structure works well below about 95% occupancy and degrades sharply above it, because insertion is a relocation process that can cycle.

Two buckets, one fingerprint

Each key maps to two candidate buckets, and each bucket holds a small fixed number of slots — four is the common choice. A slot stores a fingerprint: a $f$-bit value derived from the key, with no offset, no full key, and no pointer. Lookup computes the two bucket indices, scans the eight slots they contain, and reports a match if any slot holds the key’s fingerprint.

The false-positive rate follows from that layout alone. A lookup compares against $2b$ slots, each of which holds a random $f$-bit value, so for a uniformly distributed fingerprint the probability that some slot matches is approximately

$$ 1 - \left(1 - 2^{-f}\right)^{2b} \approx \frac{2b}{2^{f}} $$

With $b = 4$ and $f = 12$, that is $8/4096 \approx 0.2%$. The space cost is the fingerprint divided by the load factor: each entry occupies one slot, and reaching a load factor $\alpha$ means reserving $1/\alpha$ slots per entry, so the per-key cost is approximately $f/\alpha$ bits. At $f = 12$ and $\alpha = 0.95$ that is about 12.6 bits per key. Raising the fingerprint by one bit halves the error, so the error falls exponentially in the fingerprint length while the space grows linearly — the same shape as the Bloom filter’s, but with the constant set by the fingerprint width rather than by a whole bit array. The practical difference shows up when the comparison is made at equal error: a Bloom filter at 0.2% needs about 12.9 bits per key, so the cuckoo filter’s advantage at that error rate is small, and it is the layout’s deletion and locality properties rather than its size that justify it at moderate error rates. The size advantage grows as the error target tightens only to the extent that the fingerprint can shrink with it, which is bounded below by the need to keep collisions rare at the load factor in use.

The bucket index must be computable from the fingerprint alone, because after a relocation the filter no longer knows which key produced the slot. This is the constraint that shapes everything else.

The XOR that makes displacement reversible

Insertion places a key in one of its two buckets. If both are full, the filter evicts a random entry from one of them, moves it to that entry’s other bucket, and repeats. Each move requires computing the destination from the fingerprint, which seems to require the original key.

Partial-key cuckoo hashing solves this by defining the second bucket as an XOR of the first with a hash of the fingerprint:

$$ i_2 = i_1 \oplus \mathrm{hash}(f) $$

The relation is its own inverse. Given $i_2$ and the same $f$, the other bucket is $i_2 \oplus \mathrm{hash}(f) = i_1$. So an evicted entry can compute its alternate home from its stored fingerprint and current bucket index, with no key material retained. The cost is that the pair of candidate buckets is no longer independent: the difference between them is fixed by $f$, so the two buckets are correlated. For $b = 4$ and $f \geq 8$ the loss in achievable load factor is small but real, and it is why the practical ceiling sits below the idealised 97–98% of full-key cuckoo hashing.

A second constraint follows from the same trick: the fingerprint must not be zero, because a zero fingerprint would map every key to the pair ${i, i}$ and collapse the structure to a single bucket. Implementations force a nonzero value, which is also what makes an empty slot distinguishable.

Why insertion can cycle forever

Relocation walks a chain: evict from bucket A, place in B, evict from B, place in C. With random eviction the chain is a random walk on a graph whose vertices are buckets, and the walk terminates when it reaches a bucket with a free slot. Below the load-factor threshold such a slot is almost always reachable within a few steps; above it, the free slots are so sparse that the walk revisits buckets it has already filled and re-evicts entries it moved earlier.

The standard guard is a kick limit — a few hundred evictions, after which insertion is declared failed. Failure is not corruption: the filter is unchanged except for the moves already committed, so the correct response is to fall back to a stash of a few overflow entries kept outside the table, or to rebuild at a larger size. A stash of a handful of entries absorbs nearly all failures near the threshold; without one, a single failed insertion must trigger a rebuild.

Two failure modes deserve names. The first is the cycle: with a small table, the relocation graph can contain a closed loop that the walk re-enters, burning the kick budget without ever reaching free space. The second is fingerprint collision during relocation. If the evicted entry’s fingerprint collides with the fingerprint of an entry already in the destination bucket, the filter now holds two copies of the same fingerprint. Lookup cannot tell them apart, so removing one leaves the other, and a subsequent removal of a key that is genuinely present may match the surviving copy. Deletion by fingerprint is therefore approximate in the same way lookup is: it may remove the wrong entry, and it may report success for a key that was never inserted.

Deletion as a local operation

Deletion computes both buckets from the key, scans the slots, and clears the first slot whose fingerprint matches. There is no counter to decrement and no other key’s state to damage, because the fingerprint is a property of this key alone. A false match removes an unrelated entry — an error, but a bounded one, and the same event that would have produced a false positive on lookup.

#include <stddef.h>
#include <stdint.h>

/* Bucket of 4 slots; fingerprint 12 bits; two candidate buckets per key. */
#define SLOTS 4
#define FP_MASK 0xFFFu

static uint64_t mix64(uint64_t x) {
    x ^= x >> 33; x *= 0xFF51AFD7ED558CCDULL;
    x ^= x >> 33; x *= 0xC4CEB9FE1A85EC53ULL;
    x ^= x >> 33;
    return x;
}

static uint16_t fp_of(uint64_t h) {
    uint16_t f = (uint16_t)(h & FP_MASK);
    return f ? f : 1;                 /* zero would collapse the bucket pair */
}

static size_t alt_bucket(size_t i, uint16_t f, size_t buckets) {
    return i ^ (mix64(f) & (buckets - 1));       /* self-inverse */
}

int cf_delete(struct cf *t, uint64_t h) {
    uint16_t f = fp_of(h);
    size_t i1 = h % t->buckets;
    size_t i2 = alt_bucket(i1, f, t->buckets);
    for (int s = 0; s < SLOTS; s++) {
        if (t->slots[i1][s] == f) { t->slots[i1][s] = 0; return 1; }
        if (t->slots[i2][s] == f) { t->slots[i2][s] = 0; return 1; }
    }
    return 0;
}

struct cf holds uint16_t slots[][SLOTS] and a buckets count; the code above is the layout, not a complete implementation. It omits the occupancy bitmap that a real filter needs to distinguish an empty slot from a slot holding the value zero, and it assumes the bucket count is a power of two so the mask is valid. The mix64 call must be a fixed function of the fingerprint alone — the whole scheme depends on it.

Where the structure fits

The cuckoo filter’s advantages over a Bloom filter are deletion, better locality (two buckets, at most two cache lines per lookup instead of $k$ random lines), and a per-key size that does not depend on the number of keys already inserted. Its disadvantages are a capacity ceiling that must be respected, an insertion path that can fail and needs a policy for failure, and a fingerprint-collision hazard in deletion that has no analogue in the insert-only structures.

The capacity ceiling is the operative constraint. A filter sized for $n$ keys at 95% occupancy holds $0.95 \times 4 \times \text{buckets}$ entries, so the bucket count must be about $n/3.8$ rather than $n/4$. Sizing at 90% costs another 5% of space and buys enough headroom that failures become rare without a stash. Sizing at 99% does not work: the insertion walk does not converge, and the filter either rebuilds constantly or silently overflows into its stash.

For workloads where the key set only grows, deletion is never needed, and the error target is around one percent, the plain bit-array filter is smaller and simpler: at that error it needs fewer bits per key than any cuckoo layout with a workable load factor. The cuckoo layout earns its place when entries must be removed individually, when probes must be cache-local, or when the key count is unknown and an insert-only structure’s growing false-positive rate is unacceptable. The cache argument is developed further in blocked and partitioned layouts, which attack the same problem from the other direction.