Cuckoo Filter Tutorial

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:

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)

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

Basic usage

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:

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

Deletion

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:

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:

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:

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

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