Cuckoo Filter

A Cuckoo filter (Fan, Andersen, Kaminsky and Mitzenmacher, 2014) answers the same MAYBE/NO question as a Bloom filter, but it supports REMOVE without counters, and for common error rates it uses less space than a counting Bloom filter. After this lesson your program stores small fingerprints in buckets, relocates them when buckets are full, and reports FULL when it cannot.

What is stored

The table has B buckets of 4 slots. Instead of setting bits, a key stores a short fingerprint, 8 bits taken from its hash, in one of two candidate buckets. A slot value of 0 means empty, so a fingerprint is never 0: if the hash byte is 0, use 1.

fingerprint = (hb) & 0xFF, or 1 if that is 0
i1 = ha mod B
i2 = i1 XOR ( (fingerprint * 0x5bd1e995) mod B )

where ha and hb are the two murmur hashes of the hashing lesson. B must be a power of two, which is what makes the XOR trick work.

The XOR trick

The second bucket depends only on i1 and the fingerprint, and XOR undoes itself: i1 = i2 XOR hash(fingerprint). So from a fingerprint sitting in bucket i, you can always find its other bucket with no knowledge of the original key. That is what makes relocation possible:

tulip  fingerprint 241   i1 = 3   i2 = 6   alt(i2, fp) = 3
daisy  fingerprint 126   i1 = 6   i2 = 0   alt(i2, fp) = 6

Applying the same step to i2 returns i1.

Insertion with kicks

1. Compute the fingerprint, i1 and i2.
2. If bucket i1 has an empty slot, store it there (the lowest empty slot). Otherwise try i2 the same way.
3. If both are full, start a chain of kicks at bucket i1 holding the fingerprint cur. For kick number n = 0, 1, 2, ...: swap cur with the fingerprint in slot n mod 4 of the current bucket, move to the other bucket of the evicted fingerprint (the XOR step), and if that bucket has an empty slot, store cur there and stop.
4. After 500 kicks without success, the table is too full. Undo every swap so the table is exactly as it was, and report FULL.

Real implementations pick the victim slot at random; this exercise uses n mod 4 so the result is the same in every language. Here is a real kick in a table of 4 buckets. Adding key14 (fingerprint 55, buckets 3 and 0) finds both buckets full, so it kicks: the fingerprint in slot 0 of bucket 3 is evicted (125), and its other bucket is 2, and that bucket has a free slot, so the evicted fingerprint moves there.

before                 after
bucket 0: 209 145  16 143    bucket 0: 209 145  16 143
bucket 1: 237 226 223 227    bucket 1: 237 226 223 227
bucket 2: 131  91   .   .    bucket 2: 131  91 125   .
bucket 3: 125 248  47 123    bucket 3:  55 248  47 123

Lookup and deletion

CHECK looks for the fingerprint in both buckets: at most 8 slot comparisons. REMOVE clears one matching slot in i1, else in i2. This is safe only for keys that were added: two different keys can share a fingerprint and a bucket. For example id6 and id22 have the same fingerprint (34); in a one-bucket table, adding id6 makes id22 read MAYBE, and REMOVE id22 removes id6's fingerprint.

Limits

• The same key added more than 8 times cannot fit: each copy needs a slot in its two buckets, so the ninth ADD returns FULL.
• With 8-bit fingerprints and 4-slot buckets, a full table has a false-positive rate near 2*4 / 256 = 3%; more fingerprint bits lower it.
• Inserts can fail, so a real system needs a plan (rebuild bigger). A Bloom filter never refuses an add.

Common mistakes

• Computing i2 from the key again instead of from i1 and the fingerprint. Relocation then breaks.
• Letting a fingerprint be 0, which looks like an empty slot.
• Leaving the table half-changed after FULL.
• Using a bucket count that is not a power of two. The program must answer ERR BUCKETS.
• Searching for a fingerprint in only one bucket.

Your exercise

The starter reads the commands and prints state. You write the fingerprint, the alternate-bucket function, ADD with kicks and rollback, CHECK and REMOVE.