# IBLT (Invertible Bloom Lookup Table) Tutorial

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

## Introduction

`ExDataSketch.IBLT` answers a different question than the other filters
here: not "is this item in the set," but **"what's different between two
sets"** -- without transferring either set. Inserting an item touches
`hash_count` cells, each XOR-accumulating the item's key into a running
`key_sum` and bumping a `count`. Two IBLTs built from mostly-overlapping
sets can be `subtract/2`'d cell-by-cell (also just XOR); every cell
where the sets agreed cancels out to zero, and any cell left with
`count = +-1` holds exactly one surviving key -- which `list_entries/1`
peels off, repeating until nothing's left to peel:

```mermaid
flowchart LR
    A[item] --> B["hash_count cells"]
    B --> C["count += 1,\nkey_sum ^= key"]
    D[Party A IBLT] --> F["subtract/2\n(XOR cell-by-cell)"]
    E[Party B IBLT] --> F
    F --> G["list_entries/1:\npeel cells with\ncount = +-1"]
```

This is the classic use case for syncing two replicas, or diffing two
nodes' key sets, when most of the data already matches -- exchange
just the IBLT (small, proportional to `cell_count`, not to the set
size) instead of either full set.

**Use it for:** reconciling two mostly-agreeing sets -- replica sync,
"what changed since the last checkpoint," diffing two nodes' key sets
-- when you have a reasonable estimate of how *many* items differ,
even if you have no idea *which* ones.

**Don't use it for:** plain membership testing (not what this answers
at all -- see `ExDataSketch.Bloom`/`ExDataSketch.Cuckoo`); cases where
the actual difference could exceed what `:cell_count` was sized for --
decode then fails cleanly (`{:error, :decode_failed}`, never a silently
wrong answer) but you get nothing back, so `:cell_count` needs a real
estimate of the expected diff size, not the total set size.

**What it buys you:** an IBLT's size is proportional to `:cell_count`
(the *expected difference*), never to the sets themselves. At
`cell_count: 100` (used throughout this tutorial), each IBLT is a
fixed __~2.4 KB__ -- whether the underlying sets have 200 keys or
200,000:

| Approach                         | Data to diff two 200K-key sets | Answer                              |
| ------------------------------------ | --------------------------------- | -------------------------------------- |
| Transfer both full sets              | 2+ MB                              | Exact                                  |
| `ExDataSketch.IBLT` (cell_count=100) | ~2.4 KB, fixed                     | Exact diff, if it fits `:cell_count`   |

## Sample data (cached locally)

Two servers' key sets, 200,000 keys in common, each with a handful
of keys the other doesn't have -- realistic for "two replicas that
mostly agree, but drifted slightly."

```elixir
{server_a_keys, server_b_keys, only_in_a, only_in_b} = ExDataSketch.SampleData.iblt_keys()
IO.puts("Server A: #{length(server_a_keys)} keys, Server B: #{length(server_b_keys)} keys")
IO.puts("True diff: #{length(only_in_a)} keys only in A, #{length(only_in_b)} keys only in B")
```

## Basic usage

```elixir
alias ExDataSketch.IBLT

iblt = IBLT.new() |> IBLT.put("hello")
IBLT.member?(iblt, "hello")
```

## Reconciling two large, mostly-overlapping sets

Both servers build an IBLT sized for the *expected* diff (a handful of
items), not their full 200,000+-key sets:

```elixir
cell_count = 100

iblt_a = IBLT.new(cell_count: cell_count) |> IBLT.put_many(server_a_keys)
iblt_b = IBLT.new(cell_count: cell_count) |> IBLT.put_many(server_b_keys)

IO.puts("Each IBLT: #{IBLT.size_bytes(iblt_a)} bytes, regardless of the 200,000+ keys inside")

diff = IBLT.subtract(iblt_a, iblt_b)
{:ok, entries} = IBLT.list_entries(diff)

IO.puts("Recovered #{length(entries.positive)} positive and #{length(entries.negative)} negative entries")
```

`list_entries/1` returns `{key_hash, value_hash}` pairs, not the original
strings (an IBLT stores hashes, not the items themselves) -- positive
entries are in A but not B, negative are in B but not A. To turn a hash
back into a known candidate item, hash your own candidates with the same
function IBLT itself uses and match:

```elixir
positive_hashes = MapSet.new(entries.positive, fn {key_hash, _value_hash} -> key_hash end)
negative_hashes = MapSet.new(entries.negative, fn {key_hash, _value_hash} -> key_hash end)

recovered_only_in_a =
  Enum.filter(only_in_a, fn key ->
    MapSet.member?(positive_hashes, ExDataSketch.Hash.hash64(key, seed: 0))
  end)

recovered_only_in_b =
  Enum.filter(only_in_b, fn key ->
    MapSet.member?(negative_hashes, ExDataSketch.Hash.hash64(key, seed: 0))
  end)

IO.puts("Correctly recovered #{length(recovered_only_in_a)}/#{length(only_in_a)} A-only keys")
IO.puts("Correctly recovered #{length(recovered_only_in_b)}/#{length(only_in_b)} B-only keys")
```

In a real reconciliation, you already know your own full key set on each
side, so "which of my candidates does this hash belong to" is exactly
the natural query -- IBLT tells you which of your local keys the other
side is missing (or vice versa) without either side ever sending its
full set.

## What happens when the diff exceeds capacity

Undersize `cell_count` relative to the actual difference and decoding
fails cleanly instead of returning a wrong answer:

```elixir
undersized_a = IBLT.new(cell_count: 4) |> IBLT.put_many(server_a_keys)
undersized_b = IBLT.new(cell_count: 4) |> IBLT.put_many(server_b_keys)

undersized_diff = IBLT.subtract(undersized_a, undersized_b)
IBLT.list_entries(undersized_diff)
```

## Merging (set mode)

`put_many/2` builds from a batch directly; `merge/2` combines two
already-built IBLTs (both must share the same `cell_count`/`hash_count`/
`seed`) -- useful for the same distributed-worker pattern as the other
mergeable sketches:

```elixir
half = div(length(server_a_keys), 2)
{first_half, second_half} = Enum.split(server_a_keys, half)

worker_a = IBLT.new(cell_count: cell_count) |> IBLT.put_many(first_half)
worker_b = IBLT.new(cell_count: cell_count) |> IBLT.put_many(second_half)

merged = IBLT.merge(worker_a, worker_b)
IO.puts("Merged contains a first-half key: #{IBLT.member?(merged, hd(first_half))}")
```

## Serialization

```elixir
binary = IBLT.serialize(iblt_a)
{:ok, restored} = IBLT.deserialize(binary)
IO.puts("Round-tripped count: #{IBLT.count(restored)}")
```

## See also

* `ExDataSketch.IBLT` module documentation -- full API reference,
  including key-value mode (`put/3`, `delete/3`) for reconciling
  key-value pairs, not just bare keys.
* `ExDataSketch.Bloom`/`ExDataSketch.Cuckoo` -- if you only need "is this
  item present," not "what's different," a plain membership filter is
  cheaper; see `livebooks/sketches/bloom.livemd`.