# `ExDataSketch.Cuckoo`
[🔗](https://github.com/thanos/ex_data_sketch/blob/main/lib/ex_data_sketch/cuckoo.ex#L1)

Cuckoo filter for probabilistic membership testing with deletion support.

A Cuckoo filter is a space-efficient probabilistic data structure that supports
insertion, deletion, and membership queries. It uses partial-key cuckoo hashing
to store compact fingerprints in a bucket-based hash table.

Unlike Bloom filters, Cuckoo filters support deletion. Unlike XOR filters,
Cuckoo filters support incremental insertion. The trade-off is that insertion
can fail when the filter approaches capacity.

## Parameters

- `:capacity` -- expected number of items (default: 10,000). Used to derive
  the number of buckets.
- `:fingerprint_size` -- fingerprint width in bits (default: 8). Supported
  values: 8, 12, 16. Determines the false positive rate:
  FPR ~= 2 * bucket_size / 2^fingerprint_size.
- `:bucket_size` -- slots per bucket (default: 4). Supported values: 2, 4.
  Higher values improve space efficiency at the cost of lookup latency.
- `:max_kicks` -- maximum relocation attempts before declaring full
  (default: 500). Range: 100..2000.
- `:seed` -- hash seed (default: 0).

## False Positive Rates

With default bucket_size=4:

| fingerprint_size | FPR     |
|------------------|---------|
| 8                | ~3.1%   |
| 12               | ~0.2%   |
| 16               | ~0.012% |

## Hash Strategy

Items are hashed via `ExDataSketch.Hash.hash64/1` at the API boundary.
The bucket index is derived from the lower bits and the fingerprint from
the upper bits of the 64-bit hash. Alternate bucket index uses XOR with
a hash of the fingerprint (partial-key cuckoo hashing).

## Deletion Hazard

Only delete items that were definitely inserted. Deleting a false-positive
item removes a legitimate fingerprint, creating a false negative for a
different item. This hazard is inherent to all Cuckoo filters.

## Eviction Slot Selection

When an insert's target bucket is full, an existing entry is "kicked" to
its alternate bucket, repeating up to `:max_kicks` times. Which slot
within a bucket gets kicked is chosen by mixing the evicted fingerprint
and the current kick count through the same hash used for fingerprints
(`cko_fp_hash/1`), rather than a plain `rem(fingerprint + kick_count,
bucket_size)`. The plain linear form is a known cuckoo-filter
anti-pattern: with only `2^fingerprint_size` possible fingerprint values
shared across a much larger item count, two colliding fingerprints that
differ by a multiple of `bucket_size` can synchronize the kick sequence
into a short, exactly-repeating cycle among a handful of buckets, burning
through every remaining kick without ever finding an empty slot -- well
below the table's designed ~95.5% load factor. `Cuckoo.new(capacity:
500_000) |> Cuckoo.put_many(for i <- 1..500_000, do: "session_#{i}")`
reproduced this reliably before the fix. The hash-mixed slot choice stays
fully deterministic (same input sequence always produces the same
sketch state, matching this library's general guarantee) while avoiding
the arithmetic periodicity that caused it. Both backends implement this
identically, so Pure and Rust produce byte-identical state for identical
input.

## Binary State Layout (CKO1)

See `plans/adr/ADR-102-cuckoo-binary-format.md` for the full specification.
32-byte header followed by a flat bucket array of fingerprint entries.

## Merge Policy

Merge is explicitly not supported. Cuckoo filter merge would require
re-inserting all fingerprints which can fail due to capacity limits.
For mergeable membership filters, use `ExDataSketch.Bloom`.

# `t`

```elixir
@type t() :: %ExDataSketch.Cuckoo{backend: module(), opts: keyword(), state: binary()}
```

# `capabilities`

Returns the set of capabilities supported by the Cuckoo filter.

## Examples

    iex> caps = ExDataSketch.Cuckoo.capabilities()
    iex> :put in caps and :delete in caps and :member? in caps
    true

# `compatible_with?`

```elixir
@spec compatible_with?(t(), t()) :: boolean()
```

Returns `true` if two Cuckoo filters have compatible parameters.

Compatible filters have the same bucket_count, fingerprint_size,
bucket_size, and seed.

## Examples

    iex> a = ExDataSketch.Cuckoo.new(capacity: 100)
    iex> b = ExDataSketch.Cuckoo.new(capacity: 100)
    iex> ExDataSketch.Cuckoo.compatible_with?(a, b)
    true

# `count`

```elixir
@spec count(t()) :: non_neg_integer()
```

Returns the number of items currently stored in the filter.

## Examples

    iex> ExDataSketch.Cuckoo.new(capacity: 100) |> ExDataSketch.Cuckoo.count()
    0

# `delete`

```elixir
@spec delete(t(), term()) :: {:ok, t()} | {:error, :not_found}
```

Deletes a single item from the filter.

Returns `{:ok, cuckoo}` if the item's fingerprint was found and removed,
or `{:error, :not_found}` if no matching fingerprint exists.

WARNING: Only delete items that were definitely inserted. Deleting a
false-positive item removes a legitimate fingerprint belonging to a
different item, creating a false negative.

## Examples

    iex> {:ok, cuckoo} = ExDataSketch.Cuckoo.new(capacity: 100) |> ExDataSketch.Cuckoo.put("hello")
    iex> {:ok, cuckoo} = ExDataSketch.Cuckoo.delete(cuckoo, "hello")
    iex> ExDataSketch.Cuckoo.member?(cuckoo, "hello")
    false

# `deserialize`

```elixir
@spec deserialize(binary()) :: {:ok, t()} | {:error, Exception.t()}
```

Deserializes an EXSK binary into a Cuckoo filter.

Returns `{:ok, cuckoo}` on success or `{:error, reason}` on failure.

## Examples

    iex> {:ok, cuckoo} = ExDataSketch.Cuckoo.new(capacity: 100) |> ExDataSketch.Cuckoo.put("test")
    iex> {:ok, recovered} = ExDataSketch.Cuckoo.deserialize(ExDataSketch.Cuckoo.serialize(cuckoo))
    iex> ExDataSketch.Cuckoo.member?(recovered, "test")
    true

# `from_enumerable`

```elixir
@spec from_enumerable(
  Enumerable.t(),
  keyword()
) :: {:ok, t()} | {:error, :full, t()}
```

Creates a Cuckoo filter from an enumerable of items.

Equivalent to `new(opts) |> put_many(enumerable)`.

Returns `{:ok, cuckoo}` or `{:error, :full, cuckoo}`.

## Examples

    iex> {:ok, cuckoo} = ExDataSketch.Cuckoo.from_enumerable(["a", "b", "c"], capacity: 100)
    iex> ExDataSketch.Cuckoo.member?(cuckoo, "a")
    true

# `member?`

```elixir
@spec member?(t(), term()) :: boolean()
```

Tests whether an item may be a member of the set.

Returns `true` if the item is possibly in the set (may be a false positive),
`false` if the item is definitely not in the set.

## Examples

    iex> {:ok, cuckoo} = ExDataSketch.Cuckoo.new(capacity: 100) |> ExDataSketch.Cuckoo.put("hello")
    iex> ExDataSketch.Cuckoo.member?(cuckoo, "hello")
    true

    iex> cuckoo = ExDataSketch.Cuckoo.new(capacity: 100)
    iex> ExDataSketch.Cuckoo.member?(cuckoo, "hello")
    false

# `new`

```elixir
@spec new(keyword()) :: t()
```

Creates a new empty Cuckoo filter.

## Options

- `:capacity` -- expected number of items (default: 10000).
- `:fingerprint_size` -- fingerprint width in bits (default: 8).
  Supported values: 8, 12, 16.
- `:bucket_size` -- slots per bucket (default: 4).
  Supported values: 2, 4.
- `:max_kicks` -- maximum relocation attempts (default: 500).
  Range: 100..2000.
- `:seed` -- hash seed (default: 0).
- `:backend` -- backend module (default: `ExDataSketch.Backend.Pure`).
- `:hash_fn` -- custom hash function `(term -> non_neg_integer)`.

## Examples

    iex> cuckoo = ExDataSketch.Cuckoo.new()
    iex> cuckoo.opts[:capacity]
    10000

    iex> cuckoo = ExDataSketch.Cuckoo.new(capacity: 1000, fingerprint_size: 16)
    iex> cuckoo.opts[:fingerprint_size]
    16

# `put`

```elixir
@spec put(t(), term()) :: {:ok, t()} | {:error, :full}
```

Inserts a single item into the filter.

Returns `{:ok, cuckoo}` on success or `{:error, :full}` if the filter
cannot accommodate the item after max_kicks relocation attempts.

## Examples

    iex> cuckoo = ExDataSketch.Cuckoo.new(capacity: 100)
    iex> {:ok, cuckoo} = ExDataSketch.Cuckoo.put(cuckoo, "hello")
    iex> ExDataSketch.Cuckoo.member?(cuckoo, "hello")
    true

# `put!`

```elixir
@spec put!(t(), term()) :: t()
```

Inserts a single item, raising on failure.

## Examples

    iex> cuckoo = ExDataSketch.Cuckoo.new(capacity: 100)
    iex> cuckoo = ExDataSketch.Cuckoo.put!(cuckoo, "hello")
    iex> ExDataSketch.Cuckoo.member?(cuckoo, "hello")
    true

# `put_many`

```elixir
@spec put_many(t(), Enumerable.t()) :: {:ok, t()} | {:error, :full, t()}
```

Inserts multiple items in a single pass.

Returns `{:ok, cuckoo}` if all items were inserted, or
`{:error, :full, cuckoo}` with the partially updated filter
if insertion failed partway through.

## Examples

    iex> cuckoo = ExDataSketch.Cuckoo.new(capacity: 100)
    iex> {:ok, cuckoo} = ExDataSketch.Cuckoo.put_many(cuckoo, ["a", "b", "c"])
    iex> ExDataSketch.Cuckoo.member?(cuckoo, "a")
    true

# `reducer`

```elixir
@spec reducer() :: (term(), t() -&gt; t())
```

Returns a 2-arity reducer function for use with `Enum.reduce/3`.

The reducer calls `put!/2` and raises if the filter becomes full.

## Examples

    iex> is_function(ExDataSketch.Cuckoo.reducer(), 2)
    true

# `serialize`

```elixir
@spec serialize(
  t(),
  keyword()
) :: binary()
```

Serializes the filter to the ExDataSketch-native EXSK binary format.

## Options

- `:format` - serialization format: `:v2` (default, EXSK v2 with CRC32C)
  or `:v1` (legacy EXSK v1, compatible with v0.7.x readers). The v1
  format is only valid for filters using `:phash2` hash strategy.

## Examples

    iex> cuckoo = ExDataSketch.Cuckoo.new(capacity: 100)
    iex> binary = ExDataSketch.Cuckoo.serialize(cuckoo)
    iex> <<"EXSK", _rest::binary>> = binary
    iex> byte_size(binary) > 0
    true

    iex> cuckoo = ExDataSketch.Cuckoo.new(capacity: 100, hash_strategy: :phash2)
    iex> binary = ExDataSketch.Cuckoo.serialize(cuckoo, format: :v1)
    iex> <<"EXSK", 1, 8, _rest::binary>> = binary

# `size_bytes`

```elixir
@spec size_bytes(t()) :: non_neg_integer()
```

Returns the byte size of the state binary.

## Examples

    iex> cuckoo = ExDataSketch.Cuckoo.new(capacity: 100)
    iex> ExDataSketch.Cuckoo.size_bytes(cuckoo) > 0
    true

# `update`

```elixir
@spec update(t(), term()) :: t()
```

Alias for `put!/2`, added so `ExDataSketch.Cuckoo` satisfies the
`ExDataSketch.Sketch` behaviour's generic `update/2` callback.

`put/2` (returning `{:ok, cuckoo} | {:error, :full}`) remains the
family-idiomatic name for callers who need to detect a full filter;
`update/2` raises instead, matching the bare-struct-return contract every
other family's `update/2` follows (see `ExDataSketch.update/2`).

## Examples

    iex> cuckoo = ExDataSketch.Cuckoo.new(capacity: 100) |> ExDataSketch.Cuckoo.update("hello")
    iex> ExDataSketch.Cuckoo.member?(cuckoo, "hello")
    true

# `update_many`

```elixir
@spec update_many(t(), Enumerable.t()) :: t()
```

Inserts every item in an enumerable, raising if the filter fills up partway
through.

Added so `ExDataSketch.Cuckoo` satisfies the `ExDataSketch.Sketch`
behaviour's generic `update_many/2` callback. `put_many/2` (returning
`{:ok, cuckoo} | {:error, :full, cuckoo}`) remains the family-idiomatic
name for callers who need the partially updated filter on failure.

## Examples

    iex> cuckoo = ExDataSketch.Cuckoo.new(capacity: 100) |> ExDataSketch.Cuckoo.update_many(["a", "b", "c"])
    iex> ExDataSketch.Cuckoo.member?(cuckoo, "a")
    true

---

*Consult [api-reference.md](api-reference.md) for complete listing*