> For the complete documentation index, see [llms.txt](https://rookiedong.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://rookiedong.gitbook.io/notes/systems/storage-engines/cuckoo-filter.md).

# Cuckoo Filter

Bloom Filters have several drawbacks. For example, they do not support deletion, and lookup efficiency can be weaker because multiple random hash functions probe multiple different positions in the bit array, which can reduce CPU cache locality.

**Cuckoo Filters improve on these points:**

![img](https://s2.loli.net/2022/07/24/OSfnMs3leCuqTpU.png)

`Cuckoo` solves this problem: it supports deletion, which Bloom Filters do not support, with **lower space overhead**.

* supports adding and removing items dynamically
* higher lookup performance, even when close to full
* easier to implement than alternatives such as the quotient filter
* less space if the target false positive rate is less than 3%

Here is a [***C++ implementation by a CMU group***](https://github.com/efficient/cuckoofilter).

## **Cuckoo Hash**

The original Cuckoo Hashing method uses two hash functions to hash a `key`, producing two candidate bucket positions:

* If both positions are empty, store the `key` in one of them randomly.
* If only one position is empty, store the `key` in the empty position.
* If neither position is empty, randomly evict one element. The evicted element is then hashed again to find its corresponding position.

Of course, if the table is truly short of space, repeatedly evicting elements is not a solution. Therefore, implementations usually set a **kick-out threshold**. If one insertion causes more consecutive evictions than the threshold allows, the table is expanded.

![image-20210727104910960](https://s2.loli.net/2022/07/24/4URBirfyup3SGVm.png)

***In other words:***

![img](https://s2.loli.net/2022/07/24/h5TSCN4qmMRQ7jK.png)

There are two hash tables, denoted as `T1` and `T2`.

There are two hash functions, denoted as `h1` and `h2`.

When inserting an element that does not yet exist, first compute its position in table `T1` using `h1`. If that position is empty, the element can be placed there.

If that position is not empty, compute its position in table `T2` using `h2`. If that position is empty, the element can be placed there.

If that position is also not empty, evict the element currently stored at that position, and place the current element there.

Another strategy is to randomly evict one of the two candidate positions. In any case, one element will be kicked out.

What happens to the evicted element?

![img](https://s2.loli.net/2022/07/24/ivVhZclT2Kqrjxu.png)

![img](https://s2.loli.net/2022/07/24/k9YiWG7tVD5nahw.png)

This recursive-looking solution appears feasible, but there is always a risk of **cyclic eviction**, where the insertion of `x` cannot be completed.

For example, consider case (b) in the figure above.

When this situation occurs, it means the Cuckoo Hash table has reached a limiting case and should be expanded, or the hash functions should be improved. Therefore, when you look at the pseudocode again, the meaning of `MaxLoop` becomes clear.

`MaxLoop` is a threshold used to prevent the eviction process from running too many times.

## **Cuckoo Filter**

![1](https://s2.loli.net/2022/07/24/YeU32Z8WGgjxaqh.jpg)

Figures (a) and (b) show a basic **Cuckoo Hash table insertion** operation. The structure consists of an **array of buckets**. Each inserted item has two candidate buckets determined by the **hash functions `h1(x)` and `h2(x)`**. The concrete process was described above.

A basic Cuckoo Filter is also built from two or more hash functions. The basic unit stored in a Cuckoo Filter's Cuckoo Hash table is called an **entry**. **Each entry stores a fingerprint.**

A fingerprint is an `n`-bit value generated by a hash function. The specific value of `n` is determined by the acceptable false-positive rate. The paper's example uses an **`8 bits`** fingerprint size.

When querying data, the filter checks whether the corresponding position contains the corresponding fingerprint:

![img](https://s2.loli.net/2022/07/24/i57bxQrg8Ukhs16.png)

When deleting data, the filter simply removes the fingerprint at that position:

![img](https://s2.loli.net/2022/07/24/e7lcZzRQypOBakj.png)

Because fingerprints are computed by hashing elements, different elements may have the same fingerprint. This is the source of false positives.

The original data is not stored, so the structure sacrifices perfect accuracy. In exchange, it stores only a few bits per item and improves space efficiency.

Figures (a) and (b) are straightforward: they still use two hash functions. However, they do not use two arrays to store data; instead, they use one-dimensional-array-based Cuckoo Hashing, whose core idea is still eviction. The important part is figure (c), where the array is expanded from one dimension to two dimensions: each index can now hold 4 elements, so space utilization increases sharply.

See Section 6 of the paper, or the discussion below, for the **disadvantages**.

### **Insert**

Insertion is the key part, and it differs from plain Cuckoo Hashing. First, recall Cuckoo Hashing: it stores the original inserted value, such as `x`. The value `x` goes through two hash functions. If the array length is `L`, the positions are:

`p1 = hash1(x) % L`

`p2 = hash2(x) % L`

***

A Cuckoo Filter uses two hash functions that are not independent.

First, consider the fingerprint. A concrete fingerprint is obtained by taking a fixed number of bits from a hash function:

`f = fingerprint(x)`

The hash functions are:

`i1 = h1(x) = hash(x)`, computed by a hash function.

`i2 = h2(x) = i1 ⊕ hash(f)`, computed by XORing the first index with the **hash of the fingerprint**.

`i1` and `i2` are the two computed **bucket indexes**. XOR is used because of its properties: equal bits produce `0`, different bits produce `1`, and **XORing any number with `0` returns the number itself**. XOR ensures an important property: position `i2` can be computed from position `i1` and the fingerprint stored at `i1`. In other words, **when moving a key out of a bucket, we can compute its alternate bucket directly from the current bucket index `i` and the fingerprint stored in that bucket**.

**Because XOR is used, the two positions are symmetric.**

As long as **`hash(x's fingerprint) != 0`**, we can guarantee `h2 != h1`, which prevents the self-kicking infinite-loop problem.

**Why not directly XOR index 1 with the fingerprint?** Because the fingerprint is usually only a small number of bits mapped from the key. If we do not hash the fingerprint first, and the fingerprint has far fewer bits than the bucket array index, then the alternate position computed as **`i ⊕ fingerprint`** will be very close to bucket `i1`. For example, with an 8-bit fingerprint, at most the lower 8 bits of `i1` can change, so the two candidate buckets can differ by at most 256 positions. This is bad for uniform distribution.

Therefore, hashing the fingerprint ensures that an evicted element can be relocated to a completely different bucket in the hash table, reducing collisions and improving table utilization.

***Another question:***

The formula does not take a modulo with the array length. How does it guarantee that the computed index falls inside the array?

This relates to another Cuckoo Filter constraint:

The **array length is forced to be a power of two**. In binary, the length has the form `10000000...` with `n` zeros.

The benefit of this restriction is that XOR operations can guarantee the computed index remains inside the array.

The drawback is that it is an additional constraint:

> * Cuckoo Filter: I support deletion.
> * Bloom Filter: I do not need the length to be a power of two.
> * Cuckoo Filter: I have higher lookup performance.
> * Bloom Filter: I do not need the length to be a power of two.
> * Cuckoo Filter: My space utilization is also high.
> * Bloom Filter: I do not need the length to be a power of two.
> * Cuckoo Filter: This is the tradeoff.

### **Search**

Given an item `x`, the algorithm first computes the fingerprint of `x` and its two candidate buckets using the insertion formulas above. Then it reads the two buckets. If **any existing fingerprint in either bucket matches**, the Cuckoo Filter returns `true`; otherwise, it returns `false`. As long as bucket overflow does not occur, the filter has no false negatives.

### **Delete**

A standard Bloom Filter cannot delete entries, so deleting a single item requires rebuilding the entire filter. A Counting Bloom Filter supports deletion but uses more space.

Like a Counting Bloom Filter, a Cuckoo Filter can delete an inserted item by removing the corresponding fingerprint from the hash table. Other filters with similar deletion procedures are more complicated than the Cuckoo Filter.

The deletion process itself is simple: check the two candidate buckets for the given item. If the fingerprint in either bucket matches, delete one copy of the matching fingerprint from that bucket.

## **Disadvantages**

* **Deletion is not perfect; there is a probability of deleting the wrong entry.** Deletion removes one copy of a fingerprint, but it cannot prove that this fingerprint belongs to the key being deleted. This problem is also related to false positives.
* **Insertion complexity is relatively high.** As the number of inserted elements increases, insertion becomes more expensive because buckets may become full and trigger eviction. Evicted items need to be recomputed and relocated. Overall, however, the complexity is still constant on average.
* The requirement that **the storage size must be a power of two** reduces space efficiency.
* **The same element can be inserted at most `k * b` times**, where `k` is the number of hash functions and `b` is the number of fingerprints that can fit in one bucket, also called the bucket size, meaning how many elements one index can hold. If a Cuckoo Filter supports deletion, it must store multiple copies of the same item. Inserting the same item `k * b + 1` times will cause insertion failure. This is similar to a Counting Bloom Filter, where repeated insertion can cause counter overflow.

  For example, suppose there are 2 hash functions and a two-dimensional array, where each index can store at most 4 elements. Then the same element can be inserted at most 8 times.

  Consider the following situation:

  `why` has already been inserted 8 times. If we insert another `why`, cyclic eviction occurs until the maximum loop count is reached, and the insertion returns `false`.

  How can this problem be avoided?

  We can maintain a record table that tracks how many times each element has been inserted.

  The logic is simple, but for large datasets, the storage cost of this table becomes another problem.

![](https://s2.loli.net/2022/07/24/e9Gqcy4o7AbdXQk.png)

**Bucket size**:

Bucket size refers to the number of fingerprints that can be stored in each bucket. If the total Cuckoo Filter size, namely the bucket array, remains unchanged while the bucket size changes, as in the example above where bucket size is 4, two consequences follow:

**(1)** **Larger buckets can improve table utilization**. That is, as `b` becomes larger, the false-positive rate also increases. With `k=2` hash functions, when the bucket size `b=1`, equivalent to a direct-mapped hash table, the load factor `α` is 50%. With bucket sizes `b=2`, `4`, or `8`, it increases to 84%, 95%, and 98%, respectively.

**(2)** **Larger buckets require longer fingerprints to maintain the same false-positive rate**. That is, as `b` becomes larger, `f` also needs to become larger. With larger buckets, each lookup checks more entries, increasing the probability of fingerprint collision.

Therefore, the bucket size should be chosen based on these tradeoffs.