# Cuckoo Filter Tutorial

```elixir
Mix.install([
  {:ex_data_sketch, "~> 0.10"}
],
config: [
    ex_data_sketch: [
      backend: ExDataSketch.Backend.Rust,
      integrations: [opentelemetry: false]
    ]
  ])

```

## Introduction

`ExDataSketch.Cuckoo` stores a short *fingerprint* of each item (not
bits shared across everything, the way Bloom does) in one of two
candidate buckets. If both candidate buckets are full, it *kicks* an
existing fingerprint out to its own alternate bucket and tries again,
up to `:max_kicks` times -- the same relocate-on-collision idea cuckoo
hashing uses for hash tables. Because each fingerprint lives in one
specific slot rather than being smeared across shared bits, it can be
found and cleared again later:

```mermaid
flowchart LR
    A[item] --> B["fingerprint(item),\ni1 = hash(item)"]
    B --> C["i2 = i1 XOR hash(fingerprint)"]
    C --> D{"empty slot in\nbucket i1 or i2?"}
    D -->|yes| E["store fingerprint"]
    D -->|no| F["kick a resident\nfingerprint to its\nalternate bucket,\nrepeat"]
```

That gives Cuckoo two things Bloom can't do: **deletion**, and a
filter that can report when it's genuinely **full** (kicked out of
kicks) rather than silently degrading its false-positive rate past
capacity. The trade-off is that Cuckoo has no `merge/2` -- its
per-bucket fingerprint layout isn't associatively mergeable the way
Bloom's bit array is.

**Use it for:** the same "have I seen this" role as Bloom, specifically
when you also need to delete items later (session/cache eviction,
"unban this IP"), or need a hard, honest signal that the filter is
full instead of accuracy quietly degrading.

**Don't use it for:** anywhere you need to `merge/2` two independently
built filters -- use `ExDataSketch.Bloom` there; extremely tight
false-positive targets at minimal memory, where Bloom's plain bit
array has a slight edge (Cuckoo's fixed per-slot fingerprint width is
less granular than Bloom's tunable bit count).

**What it buys you:** at the default `fingerprint_size: 8`,
`bucket_size: 4` (FPR `~= 2 * bucket_size / 2^fingerprint_size`, about
3.1%), 500,000 sessions (used throughout this tutorial) measured
__~512 KB__ -- close to Bloom's per-item cost, but now deletable:

| Approach                        | Memory (500,000 sessions) | Delete? | FPR   |
| ---------------------------------- | ---------------------------- | --------- | ------- |
| Exact set (raw session strings)   | 7+ MB (grows with item size)  | Yes       | 0%      |
| `ExDataSketch.Cuckoo` (fp=8)     | ~512 KB, fixed bits/item       | Yes       | ~3.1%   |

## Sample data (cached locally)

```elixir
{inserted, novel} = ExDataSketch.SampleData.cuckoo_sessions()
IO.puts("#{length(inserted)} inserted sessions, #{length(novel)} novel sessions")
```

## Basic usage

```elixir
alias ExDataSketch.Cuckoo

{:ok, filter} = Cuckoo.new(capacity: 500_000) |> Cuckoo.put_many(inserted)

Cuckoo.member?(filter, hd(inserted))
```

`put/2` returns `{:ok, cuckoo} | {:error, :full}` so you can detect and
handle a full filter explicitly; `put!/2` (and `update/2`, its alias)
raises `ExDataSketch.Errors.FilterFullError` instead, for callers who'd
rather crash than silently drop an insert:

```elixir
f = Cuckoo.new(capacity: 100)
f = Cuckoo.put!(f, "a")
Cuckoo.member?(f, "a")
```

## Deletion

```elixir
f = Cuckoo.new(capacity: 100) |> Cuckoo.put!("x")
IO.puts("Before delete: #{Cuckoo.member?(f, "x")}")

{:ok, f} = Cuckoo.delete(f, "x")
IO.puts("After delete: #{Cuckoo.member?(f, "x")}")
```

Unlike Bloom (where you can't safely un-set a shared bit), Cuckoo stores
one fingerprint per logical slot, so removing an item's fingerprint
doesn't affect any other item.

## What "full" looks like

A Cuckoo filter's load factor tops out well under 100% -- push past it
and inserts start failing instead of silently corrupting the filter.
Force it with a tiny capacity:

```elixir
tiny = Cuckoo.new(capacity: 16, bucket_size: 4)

result =
  Enum.reduce_while(1..1000, {:ok, tiny}, fn i, {:ok, f} ->
    case Cuckoo.put(f, "item_#{i}") do
      {:ok, updated} -> {:cont, {:ok, updated}}
      {:error, :full} -> {:halt, {:error, :full, i - 1}}
    end
  end)

case result do
  {:error, :full, items_inserted} ->
    IO.puts("Filter reported full after #{items_inserted} inserts (capacity was 16)")

  {:ok, _} ->
    IO.puts("Never filled -- try a smaller capacity")
end
```

## No false negatives, measured false-positive rate

Same property as Bloom -- every inserted item is always found; measure
the false-positive rate on novel items:

```elixir
false_positives = Enum.count(novel, &Cuckoo.member?(filter, &1))
observed_fpr = false_positives / length(novel)
IO.puts("False positives: #{false_positives} / #{length(novel)} (#{Float.round(observed_fpr * 100, 4)}%)")
```

## Sizing: fingerprint_size trade-off

Wider fingerprints mean a lower false-positive rate at the cost of more
memory per slot:

```elixir
for fp_size <- [8, 12, 16] do
  {:ok, f} = Cuckoo.new(capacity: 500_000, fingerprint_size: fp_size) |> Cuckoo.put_many(inserted)
  observed = Enum.count(Enum.take(novel, 50_000), &Cuckoo.member?(f, &1)) / 50_000
  IO.puts("fingerprint_size=#{fp_size} (#{Cuckoo.size_bytes(f)} bytes): observed FPR=#{Float.round(observed * 100, 4)}%")
end
```

## Serialization

```elixir
binary = Cuckoo.serialize(filter)
{:ok, restored} = Cuckoo.deserialize(binary)
IO.puts("Round-tripped membership check: #{Cuckoo.member?(restored, hd(inserted))}")
```

## See also

* `ExDataSketch.Cuckoo` module documentation -- full API reference.
* `ExDataSketch.Quotient` -- deletion that's *always* safe (deleting a
  non-member is a guaranteed no-op, not just usually one) and does
  support `merge/2`; see `livebooks/sketches/quotient.livemd`.
* `ExDataSketch.Bloom` -- no deletion, but mergeable and simpler; see
  `livebooks/sketches/bloom.livemd`.