ExDataSketch

Production-grade streaming data sketching algorithms for Elixir.

ExDataSketch provides probabilistic data structures for approximate counting, frequency estimation, quantile computation, heavy-hitter detection, membership testing with deletion, and set reconciliation on streaming data. Stream-native integration with Elixir's Collectable, GenStage, Broadway, and Flow, plus :telemetry/OpenTelemetry instrumentation, persistence backends (ETS, DETS, CubDB, Mnesia, Ecto), and 23 production-oriented Livebooks (7 cross-cutting integration guides plus a per-family tutorial for every sketch).

Supported Algorithms

Capability Matrix

*Bloom count is a popcount-based cardinality estimate.

When to Choose

• Bloom -- Default choice for membership testing. No deletion needed, mergeable.
• Cuckoo -- Need to delete items. Better space efficiency than Bloom at low FPR.
• Quotient -- Need deletion and merge. Good when filter resizing may be needed.
• CQF -- Need to count how many times each item was inserted (multiset).
• XorFilter -- Static set known at build time. Smallest footprint, fastest lookups.
• IBLT -- Need to find differences between two sets (reconciliation).

Installation

Add ex_data_sketch to your list of dependencies in mix.exs:

def deps do
  [
    {:ex_data_sketch, "~> 0.10.1"}
  ]
end

Quick Start

# HLL: count distinct elements
hll = ExDataSketch.HLL.new() |> ExDataSketch.HLL.update_many(1..100_000)
ExDataSketch.HLL.estimate(hll)  # ~100_000

# Stream API: build from lazy enumerables
sketch = 1..100_000 |> Stream.map(&to_string/1) |> ExDataSketch.Stream.hll(p: 14)

# Collectable: Enum.into works with any mergeable sketch
sketch = Enum.into(1..50_000, ExDataSketch.ULL.new(p: 14))

# Partitioned parallel reduction
sketch = ExDataSketch.Stream.reduce_partitioned(1..1_000_000, ExDataSketch.HLL, partitions: 8, p: 14)

# Persistence: save and load from ETS
:ets.new(:sketches, [:set, :public, :named_table])
ExDataSketch.Storage.ETS.save(sketch, :sketches, "daily:2024-01-15")
{:ok, loaded} = ExDataSketch.Storage.ETS.load(ExDataSketch.HLL, :sketches, "daily:2024-01-15")

# KLL: quantile estimation
kll = ExDataSketch.KLL.new() |> ExDataSketch.KLL.update_many(1..100_000)
ExDataSketch.KLL.quantile(kll, 0.5)   # approximate median (~50_000)
ExDataSketch.KLL.quantile(kll, 0.99)  # 99th percentile (~99_000)

# Bloom: membership testing
bloom = ExDataSketch.Bloom.new(capacity: 100_000)
bloom = ExDataSketch.Bloom.put_many(bloom, 1..50_000)
ExDataSketch.Bloom.member?(bloom, 42)      # true
ExDataSketch.Bloom.member?(bloom, 99_999)  # false (probably)

See the Quick Start Guide for more examples.

Livebooks

23 production-oriented Livebooks demonstrate real-world patterns: a per-family tutorial for all 16 sketches (each generating and caching its own sample data), plus 7 cross-cutting guides covering stream consumption, distributed merge semantics, framework integration, and a 1-billion-row-style case study. See Livebooks Guide for the recommended reading order and what each Livebook teaches.

Documentation

Full documentation is available at HexDocs.

Architecture

• Binary state: All sketch state is canonical Elixir binaries. No opaque NIF resources.
• Backend system: Pure Elixir reference implementation with optional Rust NIF acceleration. The Rust backend falls back to Pure automatically when unavailable.
• Streaming native: ExDataSketch.Stream, Collectable, and from_enumerable/2 for lazy stream consumption. Broadway, GenStage, and Flow integration for production pipelines.
• Persistence: ETS, DETS, CubDB, Mnesia, and Ecto backends with atomic save/load/merge/delete operations. All storage uses EXSK v2 binary format with CRC32C checksum.
• Observability: Structured :telemetry events at batch boundaries, optional OpenTelemetry span bridge, category-based enable/disable.
• Serialization: ExDataSketch-native format (EXSK) for all sketches, plus Apache DataSketches CompactSketch interop for Theta. v1 format escape hatch for backward compatibility.
• Deterministic hashing: Stable 64-bit hash (ExDataSketch.Hash) for reproducible results.
• Backend parity: Both backends produce byte-identical serialized output for the same inputs.

Compatibility and Stability

The following guarantees apply within the v0.x release series:

• EXSK serialization: The ExDataSketch-native binary format is stable. Binaries produced by any v0.x release can be deserialized by any other v0.x release, with one exception: see the ULL v1/v2 state-format note below.
• Pure vs Rust parity: Given identical inputs, both backends produce byte-identical serialized state and identical estimates.
• Deterministic output: The same input sequence always produces the same sketch state and estimate, regardless of backend.
• Backward compatibility: v0.7.x EXSK v1 frames remain decodable. HLL.serialize(sketch, format: :v1) (and, as of v0.10.0, every other family except FilterChain) produces backward-compatible v0.7.x-style output (requires :phash2 hash strategy where applicable).

Not guaranteed:

• ULL binary format (v0.10.1+): ExDataSketch.ULL's register encoding and estimator were rewritten in v0.10.1 to fix a correctness bug (the previous implementation was an HLL-derived approximation, not real UltraLogLog, and overestimated cardinality by orders of magnitude once a sketch's registers filled up). Its internal ULL1 state format version was bumped 1 -> 2 as part of the fix; sketches serialized by v0.10.0 or earlier fail to decode on v0.10.1+ with a clear error instead of being silently misread. Rebuild any persisted ULL sketches from source data after upgrading. No other family is affected.
• ULL estimate stability: beyond the v0.10.1 binary-format break above, ULL estimates also shifted at low cardinalities between v0.8.0 and v0.9.0 due to an earlier accuracy correction.
• Cross-language interop: Theta and KLL (as of v0.10.0) support Apache DataSketches compact binary formats. HLL and CMS DataSketches interop is not implemented.
• Performance stability: Benchmark results may vary across hardware and OTP versions.
• EXSK format across major versions: The binary format may change in future major releases.

Development

# Get dependencies
mix deps.get

# Run tests with coverage
mix test --cover

# Run lints
mix lint

# Run benchmarks
mix bench

# Generate docs
mix docs

Roadmap

License

MIT License. See LICENSE for details.