IBLT (Invertible Bloom Lookup Table) Tutorial

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:

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."

{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

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:

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:

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:

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:

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

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