Current section
Files
Jump to
Current section
Files
ex_data_sketch
CHANGELOG.md
CHANGELOG.md
# Changelog
All notable changes to this project will be documented in this file.
The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.1.0/),
and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.html).
## [Unreleased]
## [0.10.1] - 2026-08-11
Started as post-release fixes from a full code review of the v0.10.0 diff
(`baoulo/reviews/0.10.0_code_review.md`); grew to include two significant
correctness fixes found via manual livebook verification (`ULL`, `KLL`),
a precision-range widening (`HLL`), and 16 new per-family tutorial
Livebooks plus a runnable Phoenix demo app.
### Added
- `livebooks/sketches/` -- one tutorial livebook per sketch family (16
total: `hll`, `ull`, `cms`, `theta`, `kll`, `ddsketch`, `req`,
`frequent_items`, `misra_gries`, `bloom`, `cuckoo`, `quotient`, `cqf`,
`xor_filter`, `iblt`, `filter_chain`). Each generates its own sample
data and caches it under `System.tmp_dir!()`, regenerating only if the
cache file is missing, so re-running a livebook (or all 16 in sequence)
after the first pass is fast.
- `phoenix_demo/` -- a minimal, real, runnable Phoenix app demonstrating
`ExDataSketch.LiveDashboard.Page` and `ExDataSketch.Telemetry.Metrics.all/1`
wired into an actual `router.ex`/`telemetry.ex`, plus a live homepage
backed by two supervised `ExDataSketch.Server` instances and a
background traffic simulator. See `phoenix_demo/README.md`.
- `guides/telemetry.md`: a "Window Events" and a "Server Events" section
(`[:ex_data_sketch, :window, :roll]` and the five `:server` events),
missing since those categories shipped -- the guide previously only
documented `:sketch`/`:persistence`/`:stream`/`:pipeline`. Also adds a
`:window, :roll` handler example (migrated from the now-removed
`rolling_telemetry.livemd`).
### Fixed
- **`ExDataSketch.KLL`'s compaction violated its own weight-preservation
invariant, corrupting quantile/rank accuracy for any sketch that ever
compacted an odd-length level.** `kll_compact_level` (both the Pure
Elixir and Rust NIF backends) cleared an *entire* level and promoted
only half its items regardless of parity; for an odd-length level, that
either promotes `ceil(len/2)` or `floor(len/2)` items, and neither
equals `len/2` exactly -- so the "half the items at double the weight"
step that's supposed to exactly preserve total weight instead silently
gains or loses one item's worth of weight (`2^level`) every time. Level
capacities (`max(2, floor(k * (2/3)^depth) + 1)`) are frequently odd, so
this was the common case, not an edge case: the sum of retained sample
weights (which `quantile/2`/`rank/2` divide by to compute a target rank)
drifted further from the true item count `n` with every such
compaction -- confirmed to reach >10% relative drift by 1,000,000
inserts in one measurement. The result was wildly incorrect, and
non-monotonic in `k`, on any distribution with a sharp density change
near the queried rank (uniform data was largely unaffected; a synthetic
99%-base/1%-tail mixture queried at p99 showed errors from tens to
hundreds of percent, inconsistently across `k`). Fixed by holding back
one item (leaving it at the current level, unweighted, for a future
compaction) whenever a level has an odd length, so the actually-compacted
subset always has even length and total weight is preserved exactly --
verified by checking `sum(retained_weight) == n` holds exactly across
`n` from 1,000 to 1,000,000 (previously off by up to +104,235 at
`n=1,000,000`), and by confirming Pure and Rust backends now produce
identical quantile estimates. No binary format change -- old serialized
sketches still decode and work, they just carry forward whatever
inaccuracy was baked in at serialization time; newly-built sketches are
correct going forward. See `ExDataSketch.KLL`'s moduledoc for why *value*
error (as opposed to the documented *rank* error bound) can still be
large when querying exactly at a distribution's density cliff -- that
part is inherent to rank-approximate sketches generally, not this bug.
- **`ExDataSketch.ULL` implemented the wrong algorithm.** Both backends'
register update/merge/estimate were an HLL-derived approximation (a
single sub-bucket bit plus Ertl 2017's HLL sigma/tau estimator), not
Ertl 2023's actual UltraLogLog. It matched real UltraLogLog closely at
low cardinalities (where every prior test and property check exercised
it, up to `n=10,000` at `p=14`) but diverged sharply once every register
had been touched at least once (`zeros == 0`, the FGRA branch) --
overestimating by orders of magnitude at moderate-to-large `n` relative
to `m`, at every precision. Both backends are now a direct, numerically
verified port of hash4j's `UltraLogLog.java` (the reference Ertl 2023
implementation): the real pack/unpack register encoding (a compressed
3-bit window per byte: geometric rank plus a 2-bit sub-bucket
refinement) and the real `OptimalFGRAEstimator` (closed-form
small-range/large-range correction terms plus a 236-entry per-register
contribution table, combined via `sum^(-1/tau) * factor[p]`). Verified
byte-for-byte (register state) and to within `1e-6` relative error
(estimate) against a compiled Java reference across `p` in
`{10,12,14,16}` and `n` up to 2,000,000, plus insertion-order
independence and merge-vs-single-sketch equivalence checks. Measured
accuracy is now `~0.70/sqrt(m)` RSE (previously documented as
`~0.835/sqrt(m)`, a number derived from the wrong estimator) -- about
30% better than HLL's `~1.04/sqrt(m)`, not the previously claimed ~20%.
The `ULL1` state binary format version is bumped 1 -> 2; version-1
binaries are rejected on decode with a clear error (see Migration).
- `ExDataSketch.Telemetry.Metrics.all/1`'s two `counter` metrics
(`sketch.ingest.count`, `stream.reduce.count`) never actually fired in
any real `Telemetry.Metrics` reporter (Phoenix LiveDashboard included).
`event_counter/4` relied on `Telemetry.Metrics.counter/2`'s implicit
`:measurement` default (the metric name's own last segment, `:count`),
but no `ExDataSketch` event carries a `:count` key in its measurements
(`sketch.ingest`'s are `:duration`/`:size_bytes`; `stream.reduce` has
none at all) -- per `counter/2`'s own docs, "the measurement must still
be available in the event, otherwise the event is not accounted for."
Both counters now use an explicit constant `:measurement` function so
they actually count every occurrence, regardless of that event's real
measurement keys.
- **Critical:** `ExDataSketch.Server` now traps exits, so a supervisor-
initiated shutdown (not just an explicit `GenServer.stop/2`) snapshots
before terminating, per its documented graceful-shutdown guarantee.
- **Critical:** the `opencode` GitHub Actions workflow no longer runs
untrusted PR-comment triggers with base-repo secrets against an
unpinned third-party action; trigger is now restricted to
owner/member/collaborator comments and the action is pinned to a commit
SHA.
- `Storage.merge/3` (ETS, DETS, CubDB, Mnesia, Ecto) returns `{:error,
_}` instead of crashing when the stored binary is corrupted or from an
incompatible sketch version.
- `ExDataSketch.Server` no longer crashes if a snapshot backend raises;
the failure is caught and reported via the new
`[:ex_data_sketch, :server, :snapshot_failed]` telemetry event instead.
- `ExDataSketch.CMS.capabilities/0` no longer falsely claims `:estimate`
(CMS only supports point queries via `CMS.estimate/2`, not the generic
single-value `estimate/1`).
- GenStage integration modules (`SketchConsumer`, `SketchProducer`,
`SketchStage`) now honor `config :ex_data_sketch, :integrations,
gen_stage: false` instead of silently ignoring it.
- **`:hash_strategy` was silently dropped by `new/1`/`build/2` across all
six membership-filter families (`Bloom`, `Cuckoo`, `Quotient`, `CQF`,
`IBLT`, `XorFilter`)**, making the option a no-op: hashing always fell
back to the NIF-availability default regardless of what was requested,
and the `:v1`-format "requires `:phash2`" guard always passed
trivially as a result. `:hash_strategy` (including `:murmur3`, used for
Apache DataSketches interop) is now resolved via
`ExDataSketch.Hash.resolve_strategy/1` at build time and actually
honored, matching `ExDataSketch.HLL`'s existing behavior.
- The same six filter families now restore `:hash_strategy` from the EXSK
v2 metadata block on `deserialize/1` (previously it was discarded, so a
filter built with a non-default hash strategy and round-tripped through
serialize/deserialize would silently query membership with the wrong
algorithm afterward).
- `ExDataSketch.merge/2` on an `ExDataSketch.Window` and
`ExDataSketch.merge_many/1` on an empty list now raise the library's
own typed errors instead of a raw `UndefinedFunctionError`/
`FunctionClauseError`.
- The Apache DataSketches KLL decoder (`deserialize_datasketches/2`) now
validates that `n` is not smaller than the reconstructed retained-item
count, and that level boundaries are monotonically non-decreasing,
rejecting corrupted input with a `DeserializationError` instead of
crashing or silently misreading it.
- `ExDataSketch.Cuckoo.put!/2`/`update_many/2` and
`ExDataSketch.FilterChain.update/2` now raise
`ExDataSketch.Errors.FilterFullError` instead of a bare `RuntimeError`
when the underlying filter is full.
- Fixed a `Storage.resolve_backend/1` ambiguity: a bare 2-tuple ref whose
first element isn't an atom implementing the `Storage` behaviour is now
resolved as a whole against the configured default backend, instead of
being misread as an explicit `{backend_module, ref}` pair.
### Removed
- `livebooks/livedashboard_integration.livemd` and
`livebooks/phoenix_observability.livemd`, superseded by `phoenix_demo/`
-- both consisted mostly of commented-out router/application pseudocode
where `phoenix_demo` has working code.
- `livebooks/rolling_telemetry.livemd` -- its `ExDataSketch.Window` content
(basic usage, deterministic testing, persistence) was already covered
in more depth by `guides/windowing.md`; its telemetry section moved to
`guides/telemetry.md`; its live-dashboard demonstration is superseded
by `phoenix_demo/`.
### Changed
- **`ExDataSketch.HLL`'s maximum precision raised from `p=16` to `p=26`**,
matching `ExDataSketch.ULL`'s range. Investigation found no algorithmic
reason for the old `p<=16` ceiling: registers are a plain byte each (no
bit-packing to overflow), and the `alpha(m)` bias-correction constant's
general formula (`0.7213 / (1 + 1.079/m)`) is valid for any `m >= 128`
-- it was simply never raised. `p>=4` remains a hard floor: `alpha(m)`
only has defined cases for `m = 2^p in {16, 32, 64}` plus the general
formula for `m >= 128`, which together cover `p >= 4` exactly. See
`ExDataSketch.HLL`'s new "Precision Range" moduledoc section (and
`ExDataSketch.ULL`'s, added for contrast -- ULL's own `p<=26` ceiling
*is* a hard limit, bounded by a 24-entry estimator lookup table).
- `lib/ex_data_sketch/telemetry.ex`'s own moduledoc claimed `:ingest`'s
`size_bytes` measurement was "HLL only" -- wrong in both directions: 13
of the 14 families that emit `:ingest` report it (all but `Cuckoo`,
whose `put_many/2` returns a tagged tuple rather than a bare sketch),
and `XorFilter`/`FilterChain` don't emit `:ingest` at all. Corrected to
describe actual per-family coverage.
- Raised the minimum supported Elixir version from `~> 1.15` to `~> 1.18`
to match what CI actually tests (the 1.15-1.17 floor was never
exercised by any CI leg).
- Corrected `ExDataSketch.Storage.DETS`'s documentation, which previously
overstated `merge/3`'s atomicity under concurrent writers; it performs
the same non-atomic read-modify-write cycle as
`ExDataSketch.Storage.ETS`.
- Corrected the `ExDataSketch.Window` and `guides/windowing.md`
explanation of tumbling-window history bounds, which had the
start-of-slot/end-of-slot cases inverted.
- `guides/observability.md` now documents
`ExDataSketch.Telemetry.Metrics.all/1` and
`ExDataSketch.LiveDashboard.Page` (added in the v0.10.0 Phase 5 work)
instead of the hand-written `:telemetry.attach`/`Telemetry.Metrics`
snippets they were built to replace.
- Minor documentation corrections: `ExDataSketch.Sketch`'s claim about
how `SketchConsumer` dispatches, `Storage`'s `merge/3` callback doc
(which grouped `ExDataSketch.Storage.CubDB` with the non-atomic
backends even though its own `merge/3` uses a `CubDB.transaction/2`),
`Storage`'s `child_spec/1` callback doc (implied `CubDB` implements it;
none of the five shipped backends do), and the bare-ref resolution
error message (previously said "no backend module given" even when a
structurally plausible but invalid one was given).
### Migration
- **`ExDataSketch.ULL` binary format bump (v1 -> v2).** Sketches
serialized by prior releases will fail to decode with
`"unsupported ULL state version 1, expected 2"` rather than silently
producing the old, significantly overestimated cardinality. This is
intentional: the register encoding itself changed (not just a wrapper),
so there is no way to reinterpret old state correctly. If you have
persisted ULL sketches (snapshots, ETS/DETS/CubDB/Ecto storage
backends, `ExDataSketch.Server` snapshot files), rebuild them from
source data after upgrading. HLL and every other family are unaffected
-- this is a `ULL`-only, algorithm-only fix.
- **ULL estimates will change** for any existing sketch once rebuilt --
they are now correct rather than overestimated once a sketch's
registers fill up (`n` comparable to or larger than `m`). If you assert
specific numeric ULL estimates in tests, expect them to shift toward
the true cardinality.
## [0.10.0] - 2026-08-07
Release theme: **Production Ergonomics.** Closes the gap between "here is a
sketch struct" and "here is a production counter that answers questions
about the last five minutes": a unified sketch contract and facade
dispatch, a storage behaviour, windowing, supervised sketch processes
(`Server`/`Sketches`), ready-made `Telemetry.Metrics` + LiveDashboard
integration, raw-hashing NIF parity for the membership filters, Apache
KLL interop, and a `format: :v1` rolling-upgrade escape hatch on every
sketch family.
### Added
- `ExDataSketch.Sketch` -- the unified behaviour every concrete sketch
family now implements (`serialize/1`, `deserialize/1`, `size_bytes/1`,
`capabilities/0` required; `new/1`, `update/2`, `update_many/2`, `merge/2`
optional where a family does not support the operation). Adds
`ExDataSketch.Sketch.implemented?/1` to check compliance.
- `ExDataSketch.sketches/0` -- the registry mapping each family atom
(`:hll`, `:bloom`, and so on) to its module; single source of truth for
the capability-matrix test and `ExDataSketch.Sketch.implemented?/1`.
- Top-level facade dispatch functions on `ExDataSketch`: `new/2`, `update/2`,
`merge/2`, `merge_many/1`, `estimate/1`, `serialize/1`, `deserialize/2`,
`size_bytes/1`, `capabilities/1`. These are additive -- every per-family
module's own API is unchanged and remains the documented primary
interface. See `guides/` (forthcoming) and
`baoulo/plans/0.10.0_phase1_stub_review.md` for the full design,
including the small set of documented family-specific exceptions
(`XorFilter` has no incremental `update/2`; `Cuckoo`, `XorFilter`, and
`FilterChain` have no `merge/2`; `CMS` and the membership filters have no
single-value `estimate/1`).
- `update/2` and `update_many/2` on `Bloom`, `Cuckoo`, `Quotient`, `CQF`,
`IBLT`, and `FilterChain` -- additive aliases for `put/2` / `put_many/2`
(the family-idiomatic names, unchanged) so every family satisfies
`ExDataSketch.Sketch`'s generic callbacks.
- `capabilities/0` on `HLL`, `CMS`, `Theta`, `KLL`, `DDSketch`, `REQ`,
`FrequentItems`, `MisraGries`, and `ULL`, matching the `MapSet.t(atom())`
vocabulary already shipped on the membership filter modules.
- `ExDataSketch.Storage` promoted to a real behaviour (`@callback save/3`,
`load/3`, `merge/3`, `delete/2`, optional `child_spec/1`), implemented by
all five persistence backends (`ETS`, `DETS`, `CubDB`, `Mnesia`, `Ecto`).
Adds `ExDataSketch.Storage.backends/0` (the atom-to-module registry) and a
dispatching facade -- `save/3`, `load/3`, `merge/3`, `delete/2` on
`ExDataSketch.Storage` itself -- that accepts either an explicit
`{backend_module, ref}` pair or a bare `ref` resolved against a newly
configurable default backend:
config :ex_data_sketch, :storage, backend: ExDataSketch.Storage.ETS
Each backend module's own API is unchanged. See
`baoulo/plans/0.10.0_phase2_stub_review.md` for the full design.
- `ExDataSketch.Window` -- a ring of tumbling sub-sketches for "in the last
N" questions without a hand-rolled timer:
window = ExDataSketch.Window.new(:hll, [p: 14], every: :timer.minutes(1), keep: 5)
window = ExDataSketch.Window.update(window, user_id)
ExDataSketch.Window.estimate(window)
`new/3` accepts a registry atom (`:hll`) or a sketch module directly;
windowing requires a mergeable family (`Cuckoo`, `XorFilter`, and
`FilterChain` are rejected with a clear error). The clock defaults to
`System.monotonic_time/1` and is fully injectable (`:time_fn` at
construction, an explicit `now` on `update/3` and `tick/2`), so tests
never sleep. Adds the `:window` telemetry category and the
`[:ex_data_sketch, :window, :roll]` event. See `guides/windowing.md` and
`baoulo/plans/0.10.0_phase3_stub_review.md` for the full design,
including what "the last N minutes" actually means for a tumbling
(not exact sliding) window.
- `ExDataSketch.Server` -- a supervised, named, concurrently-updatable
sketch process wrapping a single sketch or `ExDataSketch.Window`:
{:ok, _pid} = ExDataSketch.Server.start_link(
name: :uniques, sketch: :hll, sketch_opts: [p: 14]
)
ExDataSketch.Server.update(:uniques, user_id)
ExDataSketch.Server.estimate(:uniques)
`update/2` and `update_many/2` are casts, droppable under an optional
`:max_queue` for bounded-memory backpressure (emitting
`[:ex_data_sketch, :server, :drop]`); `update_sync/2` is a call, never
dropped. Optional `:window` holds a `ExDataSketch.Window` instead of a
bare sketch, with `track_all_time: true` maintaining a second
un-windowed accumulator readable via `estimate(server, window: :all)`;
`merge/2` is not supported on a windowed server this release (tracked in
`baoulo/plans/plan-0.10.0.md` section 9). Optional `:snapshot` persists
state to any `ExDataSketch.Storage` backend periodically and on graceful
shutdown, and restores on start (crash recovery); an untrappable
`Process.exit(pid, :kill)` bypasses the graceful-shutdown snapshot, so
worst-case loss in that specific case is bounded by the snapshot
interval, not zero. Optional `:flush` provides a return-and-reset-on-a-
timer pattern. See `guides/supervised_sketches.md` and
`baoulo/plans/0.10.0_phase4_design_review.md` for the full design.
- `ExDataSketch.Sketches` -- a supervisor for starting many
`ExDataSketch.Server` processes at runtime, addressed by an arbitrary
term instead of a compile-time name:
children = [{ExDataSketch.Sketches, name: MyApp.Sketches}]
{:ok, _pid} = ExDataSketch.Sketches.start_child(MyApp.Sketches, tenant_id, sketch: :hll, sketch_opts: [p: 14])
ExDataSketch.Server.update(ExDataSketch.Sketches.via(MyApp.Sketches, tenant_id), user_id)
Backed by a `Registry` and `DynamicSupervisor` per instance. Adds the
`:server` telemetry category and the `[:ex_data_sketch, :server, :snapshot]`,
`[:ex_data_sketch, :server, :restore]`, `[:ex_data_sketch, :server, :flush]`,
and `[:ex_data_sketch, :server, :drop]` events. See
`guides/supervised_sketches.md`.
- `ExDataSketch.Telemetry.Metrics.all/1` -- a ready-made `Telemetry.Metrics`
definition for every one of the 17 events
`ExDataSketch.Telemetry.all_event_names/0` returns, for wiring straight
into a `Telemetry.Metrics` reporter or Phoenix LiveDashboard instead of
hand-writing one metric per event:
def metrics do
ExDataSketch.Telemetry.Metrics.all() ++ [
# ... your application's own metrics
]
end
Accepts `prefix:` to namespace metric names differently; the underlying
`:telemetry` event listened to is unaffected. Adds `{:telemetry_metrics,
"~> 1.0"}` as a normal (non-optional) dependency -- it defines only
struct types, with no runtime process or side effect.
- `ExDataSketch.LiveDashboard.Page` -- an optional `Phoenix.LiveDashboard.PageBuilder`
page listing every ExDataSketch telemetry event and the metric names
`ExDataSketch.Telemetry.Metrics.all/1` derives from them:
live_dashboard "/dashboard", additional_pages: [sketches: ExDataSketch.LiveDashboard.Page]
A static reference page, not a live view of any particular running
sketch (it cannot know which `ExDataSketch.Server` instances a host
application started). Only exists when the new optional
`{:phoenix_live_dashboard, "~> 0.8", optional: true}` dependency is
loaded. See `baoulo/plans/0.10.0_phase5_stub_review.md` for the full
design.
- `ExDataSketch.KLL.serialize_datasketches/2` and
`deserialize_datasketches/2` -- Apache DataSketches KLL interop
(compact `KllFloatsSketch`/`KllDoublesSketch`), replacing the
`not_implemented!` stubs (v0.10.0 Phase 7, closing G7 from the v0.9.0
code review). Unlike Theta, KLL does not hash its inputs, so this is a
full item-level round trip with no hash-equality caveat -- decoding a
Java/C++/Python-produced sketch and querying `quantile/2`/`rank/2`
answers using the exact retained values the other implementation
selected. Takes a `:variant` option (`:float` or `:double`, default
`:double`); Apache's wire format doesn't self-describe item width, so
the caller must know it in advance, same as choosing between
`KllFloatsSketch`/`KllDoublesSketch` in Java. Backed by a new
`ExDataSketch.DataSketches.KLLSketch` codec module (mirroring
`CompactSketch`'s shape) and a `Backend.kll_from_components/5`
callback (mirroring `theta_from_components/3`). Verified against the
real `datasketches` Python package (not just against our own decoder)
in both directions -- decoding its output and having it decode ours --
across a sweep of item counts and `k` values from 0 to 500,000; see
`guides/apache_interop.md`. `test/fixtures/interop/kll/` carries the
first golden cross-language fixture corpus actually generated and
committed for any family (the process `test/vectors/CROSS_LANGUAGE.md`
documented for Theta was never executed until now), pinned to
`datasketches` 5.2.0.
- `guides/apache_interop.md` -- consolidated reference for what
interoperates with Apache DataSketches (Theta, KLL) and what doesn't
(HLL -- now targeted at v0.11.0; CMS -- not planned, no standard format
exists), superseding the scattered mentions previously spread across
sketch moduledocs.
- `serialize(sketch, format: :v1)` -- the opt-in legacy EXSK v1 escape
hatch, previously HLL-only, is now available on every sketch family
except `FilterChain` (which has its own bespoke FCN1 container format
with no `Codec.sketch_id` of its own -- see its moduledoc). v1 output
is compatible with v0.7.x readers, for use during rolling upgrades.
Families with a `:hash_strategy` option require `:phash2` for v1, same
as HLL; families with no hash-strategy concept (KLL, DDSketch, REQ,
FrequentItems, MisraGries) have no such restriction. `Codec.encode/4`
(already generic across every `sketch_id_*`) needed no changes --
every family's *state* binary is unchanged between v1 and v2 eras, the
difference is purely the frame wrapper (v2 adds a hash-algorithm
metadata block + CRC32C trailer; v1 has neither).
- `ci/check_roadmap.exs` -- asserts `README.md`'s roadmap table has a
row for the version `mix.exs` currently declares, and (once that
version has no `-dev` suffix) that the row says "Released", the
install snippet matches, and `guides/roadmap.md` has moved on to
previewing the next release. Closes a twice-deferred carry-forward
item (X-R2).
### Changed
- `Bloom.put_many/2`, `Cuckoo.put_many/2`, `Quotient.put_many/2`,
`CQF.put_many/2`, `IBLT.put_many/2`, and `XorFilter.build/2` now hash
items inside the Rust NIF itself when using `Backend.Rust` with the
default hash strategy (`:xxhash3`/`:murmur3`), instead of hashing on
the BEAM and passing pre-hashed integers across the NIF boundary --
extending the raw-hashing architecture HLL/CMS/Theta/ULL already had
(`guides/hll_performance.md`) to the six membership filters (G6 from
the v0.9.0 code review, deferred twice, now closed). Measured 2.2x-
12.8x faster than the pre-hashed Rust path and up to ~2,700x faster
than Pure Elixir, depending on family -- see `guides/filter_performance.md`
for the full measured table. A custom `:hash_fn` or `:hash_strategy:
:phash2` still falls back to the pre-hashed path exactly as before;
behavior and serialized output are unchanged, only where the hash is
computed. `test/parity_test.exs` already asserted byte-identical
Pure/Rust output for every affected family under default options, so
it now exercises the raw path automatically; new tests were added only
for the `:hash_fn` fallback case (one per family) and were not
previously covered for any raw-hashing family.
- `ExDataSketch.Broadway.PeriodicAggregator` is now a thin wrapper around a
`:flush`-configured `ExDataSketch.Server`, delegating every call. Its
public API (`start_link/1`, `merge/2`, `flush/1`, `get/1`, `estimate/1`)
is unchanged. **Correction (originally published as "unchanged," which
was wrong):** the `[:ex_data_sketch, :pipeline, :periodic_flush]`
telemetry event's scope narrowed. In v0.9.0 it fired on every call to
`flush/1`, manual or automatic. In v0.10.0 it fires only on the
automatic, timer-driven path -- `Server.flush/1`'s manual call does not
invoke the `:flush` callback that emits it (see `ExDataSketch.Server`'s
moduledoc, which already documented this correctly; only this
CHANGELOG entry had the wrong claim). If you relied on this event
firing from a manual `PeriodicAggregator.flush/1` call, it no longer
will; use the `[:ex_data_sketch, :server, :flush]` event instead, which
fires on both paths.
- `ExDataSketch.update_many/2` now dispatches generically via the `Sketch`
behaviour instead of 13 hand-written struct clauses, extending coverage
to 15 of 16 families (all but the immutable `XorFilter`, which raises
`ExDataSketch.Errors.UnsupportedOperationError`).
- `ExDataSketch.GenStage.SketchConsumer` ingests raw event batches via
`sketch_module.update_many/2` directly instead of a `from_enumerable/2`
capability probe followed by a merge; behavior is unchanged, with one
fewer intermediate sketch allocation per batch.
- `ExDataSketch.FilterChain`'s internal capability checks now use
`ExDataSketch.Sketch.implemented?/1` instead of raw `function_exported?/3`.
- Removed the unused `save_opts`, `load_opts`, `merge_opts`, and
`delete_opts` types from `ExDataSketch.Storage` -- they described a
`[table: atom()]` keyword-list shape no backend ever used (every backend
takes its table/db/repo as a positional argument) and were referenced
nowhere in `lib/` or `test/`.
- Fixed a `:telemetry.attach/4` local-function-capture performance warning
in `ExDataSketch.Telemetry.OpenTelemetry.setup/0` (it now attaches a
remote function capture).
- Wired up `doctest` for `DDSketch`, `REQ`, `FrequentItems`, `MisraGries`,
and all 7 membership filter modules -- their existing `@doc` examples
were never executed by the test suite before this release.
- `test/property_guarantees_test.exs`'s bit-flip corruption-propagation
property now covers all 15 `Codec`-backed sketch families (previously
HLL/ULL/CMS only) instead of a hardcoded 3-family list. Closes a
twice-deferred carry-forward item (P5R4). Construction is factored
into a new `test/support/sketch_fixtures.ex` (`ExDataSketch.SketchFixtures`)
shared with the generalized v1 escape-hatch tests, which handles the
three constructor return shapes in play (bare struct; Cuckoo's
`{:ok, t()} | {:error, :full, t()}`; XorFilter's `build/2` returning
`{:ok, t()} | {:error, :build_failed}` since it has no
`from_enumerable/2`). `FilterChain` is excluded (bespoke construction
shape wrapping sub-sketches, each already covered independently).
### Fixed
- Removed stray `erl_crash.dump` and `.DS_Store` from the repository;
`.DS_Store` is now gitignored.
## [0.9.0] - 2026-05-19
Release theme: **Streaming Integrations.** Transforms ex_data_sketch from a collection of probabilistic algorithms into a BEAM-native streaming approximate analytics infrastructure layer. Stream/Collectable integration, Broadway/GenStage/Flow pipelines, five persistence backends, production-grade telemetry + OpenTelemetry, ULL accuracy fixes, and comprehensive educational materials.
### Added
- **Stream and Collectable integration (Phase 1).**
- `ExDataSketch.Stream` -- terminal stream consumers (`hll/2`, `cms/2`, `theta/2`, `ull/2`, `kll/2`, `ddsketch/2`, `req/2`, `bloom/2`, `quotient/2`, `cqf/2`, `iblt/2`, `frequent_items/2`, `misra_gries//2`).
- `ExDataSketch.Stream.reduce_into/3` -- reduce an enumerable into a module or existing sketch.
- `ExDataSketch.Stream.reduce_partitioned/3` -- partitioned parallel reduction with merge.
- `Collectable` protocol for all mergeable sketches -- `Enum.into/2` and `for` comprehensions.
- `from_enumerable/2` on all 13 mergeable sketch modules.
- `reducer/1` and `merger/1` on all mergeable sketch modules for `Enum.reduce/3` and `Flow.reduce/3` ergonomics.
- **Broadway, GenStage, and Flow integration (Phase 2).**
- `ExDataSketch.Broadway.accumulate/3` and `accumulate_into/4` -- build sketches from Broadway message batches.
- `ExDataSketch.Broadway.PeriodicAggregator` -- GenServer that accumulates sketches and flushes on a timer with optional callback.
- `ExDataSketch.GenStage.SketchConsumer` -- GenStage consumer that accumulates events into a sketch, supports periodic flush.
- `ExDataSketch.GenStage.SketchProducer` -- GenStage producer that emits accumulated sketches on demand.
- `ExDataSketch.GenStage.SketchStage` -- combined producer-consumer that accumulates and emits.
- `ExDataSketch.Flow.reduce/3` and `merge/2` -- parallel partition-local reduction with merge for Flow pipelines.
- All integration modules are optional and gated behind dependency availability checks (`ExDataSketch.Integration`).
- **Persistence surfaces (Phase 3).**
- `ExDataSketch.Storage.ETS` -- in-memory persistence with `save/3`, `load/3`, `merge/3`, `delete/2`.
- `ExDataSketch.Storage.DETS` -- disk-backed persistence with same API.
- `ExDataSketch.Storage.CubDB` -- CubDB persistence for atomic key-value storage.
- `ExDataSketch.Storage.Mnesia` -- distributed persistence for multi-node scenarios.
- `ExDataSketch.Storage.Ecto` -- SQL database persistence with schema and migration helpers.
- `ExDataSketch.Storage.Ecto.Schema` and `ExDataSketch.Storage.Ecto.Migration` -- Ecto schema and migration for sketch storage.
- `ExDataSketch.Storage` -- shared behaviour documentation and types for all backends.
- All backends serialize via EXSK v2 binary format with CRC32C checksum; no raw state is ever stored.
- Configuration-driven backend availability via `config :ex_data_sketch, :persistence_backends`.
- **Telemetry and observability (Phase 4).**
- `ExDataSketch.Telemetry` -- structured telemetry event emission at batch/compound operation boundaries (not per-update).
- Four event categories: `:sketch` (create, ingest, merge, serialize, deserialize), `:persistence` (save, load, merge, delete), `:stream` (reduce, partition_merge), `:pipeline` (accumulate, periodic_flush).
- `Telemetry.execute/4`, `Telemetry.span/5`, `Telemetry.span_with_result/6` -- timing wrappers with category-based enable/disable.
- `Telemetry.event_name/2` and `all_event_names/0` for programmatic handler attachment.
- `ExDataSketch.Telemetry.OpenTelemetry` -- OTEL span bridge (requires `:opentelemetry_api ~> 1.0`).
- Configuration: `config :ex_data_sketch, telemetry_enabled: false` or per-category `config :ex_data_sketch, :telemetry, sketch: true, persistence: false`.
- Telemetry events instrumented in all 13 sketch modules, all 5 storage backends, `Stream`, and `Broadway`/`GenStage`/`Flow`.
- **ULL accuracy correction (Phase 5).**
- ULL linear counting correction: `zeros > 0` threshold (not HLL-style `raw_estimate <= 2.5*m && zeros > 0`). Empirical validation shows linear counting always more accurate for ULL when empty registers exist.
- ULL large range correction: bias correction for very high cardinality estimates, matching Ertl 2023.
- Both Pure Elixir and Rust NIF backends updated; property tests updated with tiered accuracy bounds (35%/25%/15% at p=8).
- **Configurable `update_many` chunk size (Phase 5).**
- `update_many_chunk_size` option on HLL, ULL, CMS, and Theta (via `new/1` opts). Default 10,000 (backward compatible).
- **EXSK v1 serialization escape hatch (Phase 5).**
- `HLL.serialize(sketch, format: :v1)` produces a backward-compatible v0.7.x binary (requires `:phash2` hash strategy, raises `ArgumentError` for other strategies).
- `Binary.encode_v1/4` utility for custom v1 encoding.
- v0.7.x binaries remain decodable via `Binary.decode/1` (version sniffing).
- **Generalized corruption propagation properties (Phase 5).**
- HLL, ULL, and CMS bit-flip properties in `property_guarantees_test.exs` asserting that corrupted frames either fail CRC or produce estimates within 10x of the truthful estimate (never silently catastrophic).
- Quotient filter delete property: count reduction (not `member?` becomes false).
- **Benchmarks and property tests (Phase 6).**
- `bench/persistence_bench.exs` -- ETS save/load/merge overhead.
- `bench/serialization_bench.exs` -- serialize/deserialize throughput.
- `bench/merge_throughput_bench.exs` -- HLL/ULL/CMS `merge_many` benchmarks.
- `bench/update_many_chunk_bench.exs` -- configurable chunk size impact on throughput.
- `bench/stream_ingestion_bench.exs` -- stream ingestion latency and throughput.
- `test/ex_data_sketch_serialization_stability_test.exs` -- 7 round-trip properties (HLL v2/v1, ULL, CMS, Theta, Bloom, v1-v2 cross-version).
- Expanded stream properties: ULL stream equivalence, ULL partition merge, ULL merge associativity, Theta stream equivalence, CMS merge associativity.
- Expanded storage properties: DETS save/load, DETS merge.
- **Educational materials.**
- `guides/aggregation_wall.md` (188 lines) -- why exact aggregation breaks at scale, BEAM's natural fit, common patterns.
- `guides/distributed_merge_semantics.md` (328 lines) -- associativity/commutativity proofs, fan-in/tree/partition patterns, anti-patterns.
- `guides/livebooks.md` -- Livebook catalogue with recommended order and learning objectives.
- Updated `guides/telemetry.md` -- pipeline/stream event tables, `all_event_names/0` reference.
- Updated `guides/streaming_sketches.md` -- Stream API, Collectable, partitioned reduction.
- Updated `guides/broadway_integration.md` -- `accumulate/3`, `accumulate_into/4`, `PeriodicAggregator`.
- Updated `guides/genstage_integration.md` -- `SketchConsumer`, `SketchProducer`, `SketchStage`.
- Updated `guides/persistence.md` -- all 5 backends, configuration, EXSK v2 storage contract.
- Updated `guides/observability.md` -- telemetry categories, event names, OTEL bridge.
- **Livebooks.**
- `livebooks/streaming_cardinality.livemd` -- Stream API, precision tradeoffs, ULL vs HLL.
- `livebooks/broadway_integration.livemd` -- accumulate, PeriodicAggregator, partition handling.
- `livebooks/genstage_aggregation.livemd` -- SketchConsumer, SketchProducer, flush patterns.
- `livebooks/rolling_telemetry.livemd` -- time-windowed sketches, ETS persistence.
- `livebooks/distributed_merges.livemd` -- associativity, tree aggregation, ETS sharding.
- `livebooks/persistence_snapshots.livemd` -- ETS/DETS, serialization, multi-backend strategy.
- `livebooks/livedashboard_integration.livemd` -- telemetry wiring, custom dashboard pages.
- `livebooks/ai_token_analytics.livemd` -- LLM workload multi-dimensional sketch dashboard.
- `livebooks/phoenix_observability.livemd` -- DAU, latency, rate limiting, ETS persistence.
### Changed
- **`ExDataSketch.HLL.new/1`** now accepts `update_many_chunk_size` option (default 10,000).
- **`ExDataSketch.ULL.new/1`** now accepts `update_many_chunk_size` option (default 10,000).
- **`ExDataSketch.CMS.new/1`** now accepts `update_many_chunk_size` option (default 10,000).
- **`ExDataSketch.Theta.new/1`** now accepts `update_many_chunk_size` option (default 10,000).
- **ULL accuracy** at low cardinalities significantly improved via linear counting + large range correction. Users may see different estimates for sketches with very few items; the new estimates are more accurate.
- **`ExDataSketch.ULL` moduledoc** updated with estimation strategy description and p>=12 recommendation.
### Fixed
- **ULL low-precision accuracy**: p=8 with n=1000 improved from ~62.5% relative error to ~0.8% via linear counting correction.
- **ETS merge test tolerance**: 60% tolerance for cardinality < 5 (HLL at p=10 has high relative error at tiny cardinalities).
- **Quotient filter delete property**: corrected from asserting `member?` becomes false (not guaranteed) to asserting count reduction.
- **DETS API**: corrected `close_file` to `:dets.close/1` in property tests.
- **`PeriodicAggregator` telemetry metadata**: uses `sketch_type` only (removed non-existent `state.id`).
- **OTEL handler IDs**: tuples `{"ex_data_sketch_opentelemetry", event_name}`, not strings.
### Migration
See `guides/v0.8.0_migration_notes.md` for the v0.7.x to v0.8.0 migration guide. For v0.8.0 to v0.9.0:
- **No code changes required for most users.** All new modules are additive; existing APIs are backward compatible.
- **ULL estimates may change** at very low cardinalities (p < 12, n < 500). The new estimates are more accurate. If you depend on exact numeric values in tests, add tolerance for small cardinalities.
- **`update_many_chunk_size`** defaults to 10,000 (matching v0.8.0 behavior). No change needed unless you want to tune batch throughput.
- **v1 serialization** is an opt-in escape hatch via `format: :v1`. Default serialization remains EXSK v2.
- **Telemetry** is enabled by default. Disable with `config :ex_data_sketch, telemetry_enabled: false`.
- **Persistence backends** are enabled by default when their runtime dependencies are available. Disable individuals via `config :ex_data_sketch, :persistence_backends, ets: [enabled: false]`.
### Stats
- **+21 new modules**: `Stream`, `Broadway`, `Broadway.PeriodicAggregator`, `Flow`, `GenStage`, `GenStage.SketchConsumer`, `GenStage.SketchProducer`, `GenStage.SketchStage`, `Storage`, `Storage.ETS`, `Storage.DETS`, `Storage.CubDB`, `Storage.Mnesia`, `Storage.Ecto`, `Storage.Ecto.Schema`, `Storage.Ecto.Migration`, `Telemetry`, `Telemetry.OpenTelemetry`, `Integration`, `Binary`, `Binary.encode_v1/4` utility.
- **1558 tests, 204 doctests, 199 properties, 0 failures** (NIF on).
- **9 Livebooks**, **20 guides** (3 new educational guides + 6 updated + `livebooks.md` index).
- **5 new benchmark suites**, **7 new property test groups**.
- **`:telemetry ~> 1.0`** required dependency; **`:opentelemetry_api ~> 1.0`**, **`:broadway`**, **`:flow`**, **`:cubdb`**, **`:ecto_sql`**, **`:mnesia`** optional dependencies.
## [0.8.0] - 2026-05-12
Release theme: **Deterministic Foundations.** Transforms ex_data_sketch from a collection of probabilistic algorithms into a production-grade probabilistic runtime for the BEAM. Focus: deterministic hashing, binary stability, corruption detection, hot-path performance, and installation reliability.
### Added
- **Deterministic hashing infrastructure (Phase 1).**
- `ExDataSketch.Hash.XXH3` — focused XXHash3-64 wrapper. Raises `ArgumentError` when the Rust NIF is unavailable so hash drift cannot occur silently.
- `ExDataSketch.Hash.Murmur3` — full `MurmurHash3_x64_128` returning the high 64 bits (Apache DataSketches convention). Pure Elixir and Rust NIF implementations are byte-identical, verified by property-based parity (200 random inputs per CI run) and against canonical Python `mmh3` regression vectors.
- `ExDataSketch.Hash.Metadata` — 16-byte versioned binary block recording `(algorithm, seed, sketch_family, sketch_family_version, backend)` with a forward-compatible extension trailer. The building block for the EXSK v2 binary header.
- `ExDataSketch.Hash.Validation` — centralized merge-compatibility checks (`validate_options!/3`, `validate_metadata!/3`, `compatible_options?/2`).
- Public registry API on `ExDataSketch.Hash`: `default_algorithm/0`, `supported_algorithms/0`, `algorithm_info/1`.
- `ExDataSketch.Hash.resolve_strategy/1` — single source of truth for sketch constructors. Honors a user-supplied `:hash_strategy` or falls back to `default_algorithm/0`.
- HLL, ULL, Theta, CMS `new/1` now respect user-supplied `:hash_strategy` (`:xxhash3 | :murmur3 | :phash2`). The option was silently overridden in v0.7.x.
- **Binary stability and corruption detection (Phase 2).**
- `ExDataSketch.Binary` — public facade for the EXSK v2 frame (`encode/3`, `decode/1`, `peek_version/1`, `build_payload/2`, `metadata_from_opts/3`).
- `ExDataSketch.Binary.Header` — EXSK v2 frame encoder/decoder. Layout: magic + version + sketch_family + family_version + flags + header_size + `Hash.Metadata` block + payload_size + payload + CRC32C trailer.
- `ExDataSketch.Binary.Validator` — discrete defensive check helpers (`check_minimum_v2_size`, `check_magic`, `check_version`, `check_crc`).
- `ExDataSketch.Binary.CRC` — CRC32C (Castagnoli polynomial, reflected, init `0xFFFFFFFF`, final XOR `0xFFFFFFFF`). Pure Elixir and Rust NIF implementations are byte-identical, verified against the standard `"123456789" -> 0xE3069283` check vector and Python `crc32c` regression vectors.
- Rust `crc32c_nif` — table-driven CRC32C, ~1 GB/s on commodity hardware.
- **HLL hot-path generalization (Phase 3).**
- 8 new Rust NIFs: `{hll, ull, theta, cms}_update_many_raw_h_nif/_dirty_nif`. Each accepts an `algorithm: u8` parameter (`1 = xxhash3`, `2 = murmur3`) and shares a single `Murmur3_x64_128` implementation via `pub(crate)` export from `hash.rs`.
- End-to-end Murmur3 acceleration: `:murmur3` callers now hit the in-Rust hashing fast path instead of falling off to the Elixir-side hash.
- `bench/hll_hot_path_bench.exs` — comprehensive benchmark across Pure phash2 / Pure xxhash3 / Rust raw XXH3 / Rust raw_h Murmur3 at 10k / 100k / 1M items.
- **Precompiled NIF platform matrix (Phase 4).**
- Two Windows targets added: `x86_64-pc-windows-msvc` and `aarch64-pc-windows-msvc`. Release matrix is now 8 targets × 2 NIF versions = 16 artifacts per tagged release.
- `mix test.nif_on` and `mix test.nif_off` aliases automatically reset the per-env `rustler_precompiled :force_build` state between local NIF-mode flips.
- `test/ex_data_sketch/nif_availability_test.exs` — 18 contract tests asserting `Hash.nif_available?/0` stability, default-algorithm reflection, registry availability flags, `XXH3.hash/2` failure mode, Murmur3 NIF-less fallback, checksum file shape, and `nif.ex` ↔ `release.yml` target-list alignment.
- **Property-based validation (Phase 5).**
- `test/property_guarantees_test.exs` — 14 new properties locking:
- HLL / ULL cardinality monotonicity and error bounds within published RSE.
- KLL / REQ rank monotonicity and quantile/rank inversion within published epsilon.
- CMS overestimation-only (`estimate(item) >= true_count(item)`).
- Bloom / XorFilter / Cuckoo no-false-negative guarantees.
- Binary v2 bit-flip corruption never silently propagates to a sketch.
- **User-facing release guides** (shipped to HexDocs):
- `guides/v0.8.0_migration_notes.md` — v0.7.x to v0.8.0 upgrade guide.
- `guides/v0.8.0_architecture.md` — layered architecture overview.
- `guides/serialization_compatibility.md` — the v0.x EXSK stability contract.
- `guides/hash_strategies.md` — choosing between phash2, XXH3, Murmur3, and custom.
- `guides/hll_performance.md` — HLL hot-path architecture, benchmark numbers, and external-library context.
- `guides/precompiled_nifs.md` — platform matrix, release pipeline, and source-build fallback.
- `guides/roadmap.md` — v0.9.0 preview.
- **Internal plans and reviewer checklists** (repo-only, not packaged):
- [`plans/hash_binary_contract.md`](https://github.com/thanos/ex_data_sketch/blob/main/plans/hash_binary_contract.md)
- [`plans/binary_contract.md`](https://github.com/thanos/ex_data_sketch/blob/main/plans/binary_contract.md), [`plans/corruption_detection.md`](https://github.com/thanos/ex_data_sketch/blob/main/plans/corruption_detection.md)
- [`plans/hll_scheduler_safety.md`](https://github.com/thanos/ex_data_sketch/blob/main/plans/hll_scheduler_safety.md)
- [`plans/property_testing.md`](https://github.com/thanos/ex_data_sketch/blob/main/plans/property_testing.md)
- [`plans/0.8.0_implementation_plan.md`](https://github.com/thanos/ex_data_sketch/blob/main/plans/0.8.0_implementation_plan.md), Phase 1-5 reviewer checklists
- [`plans/0.8.0-risks.md`](https://github.com/thanos/ex_data_sketch/blob/main/plans/0.8.0-risks.md) (31-risk consolidated register)
- [`plans/0.8.0-review.md`](https://github.com/thanos/ex_data_sketch/blob/main/plans/0.8.0-review.md) (pre-release code review)
### Changed
- **EXSK serialization format bumped to v2.** Every sketch's `serialize/1` now produces an EXSK v2 frame (magic + version 2 + sketch family + family version + flags + header_size + 16-byte hash metadata block + payload size + payload + CRC32C trailer). v0.7.x EXSK v1 frames remain decodable via `Binary.decode/1`'s version sniffing; `ExDataSketch.Codec` is preserved as the legacy v1 path.
- **Golden vectors regenerated as v2** under `test/vectors/`. The previous v1 vectors are preserved under `test/vectors_v1/` and exercised by `test/ex_data_sketch_v1_compat_test.exs` as a permanent regression guard.
- **`README.md` roadmap rewritten** to match the strategic roadmap in [`plans/next_steps.md`](https://github.com/thanos/ex_data_sketch/blob/main/plans/next_steps.md): v0.8.0 = Deterministic Foundations; v0.9.0 = Streaming Integrations; v0.10.0 = Apache Interoperability; v0.11.0 = New Sketch Families (CPC, Tuple); v0.12.0 = Similarity & Sampling (MinHash, VarOpt); v1.0.0 = Stable Binary Contract.
- **`ExDataSketch.Hash.validate_merge_hash_compat!/3`** is preserved as a backward-compatible shim that delegates to `ExDataSketch.Hash.Validation.validate_options!/3`.
### Fixed
- `ExDataSketch.Hash.XXH3` doctests are now NIF-safe: they exercise the success path when the NIF is available and explicitly verify the documented `ArgumentError` contract when the NIF is unavailable, removing a CI failure on the `EX_DATA_SKETCH_SKIP_NIF=true` lane.
- `test/ex_data_sketch/nif_availability_test.exs` checksum-file assertions softened to "if present, parses as a map" so fresh checkouts (where `checksum-Elixir.ExDataSketch.Nif.exs` has not been populated by the release pipeline) pass CI.
### Migration
See `guides/v0.8.0_migration_notes.md` (shipped in HexDocs) for the full v0.7.x -> v0.8.0 migration guide. Key points:
- **No code changes required for most users.** EXSK v1 frames are still decoded; the `serialize/1` output format changes but downstream code that uses round-trip serialization sees no API difference.
- **One-way upgrade for persisted sketches.** v0.7.x cannot read v0.8.0-produced binaries. Stage your rollout: deploy v0.8.0 readers first, then producers.
- **Opt-in Murmur3.** New `:murmur3` strategy is opt-in via `hash_strategy: :murmur3` at sketch construction. Default remains `:xxhash3`.
### Documentation
User-facing guides (shipped to HexDocs and the Hex package):
- `guides/v0.8.0_architecture.md` — consolidated Phase 1-5 design overview.
- `guides/serialization_compatibility.md` — the v0.x stability contract.
- `guides/roadmap.md` — preview of the next release's streaming-integration scope.
Internal documentation (repo-only; linked from the user guides):
- [`plans/0.8.0-risks.md`](https://github.com/thanos/ex_data_sketch/blob/main/plans/0.8.0-risks.md) — open risk register at release time.
- [`plans/0.8.0-review.md`](https://github.com/thanos/ex_data_sketch/blob/main/plans/0.8.0-review.md) — pre-release code review.
### Stats
- **+10 new modules**: `Hash.XXH3`, `Hash.Murmur3`, `Hash.Metadata`, `Hash.Validation`, `Binary`, `Binary.Header`, `Binary.Validator`, `Binary.CRC` (Elixir); 2 Rust NIF entry points (`hash`, `crc`).
- **+11 Rust NIFs**: `murmur3_x64_128_nif`, `murmur3_x64_128_full_nif`, `crc32c_nif`, 4 × `*_update_many_raw_h_nif` + 4 × `*_dirty_nif`.
- **+92 tests, +33 doctests, +19 properties** since v0.7.1.
- **Full suite (NIF on)**: 1,317 tests, 202 doctests, 171 properties, 0 failures.
- **Full suite (NIF off)**: 1,088 tests, 202 doctests, 128 properties, 0 failures.
- **Coverage**: 92.7% line coverage (target was 70%).
- **HLL throughput**: 25-34 M items/sec at p=14 (XXH3, Rust raw); ~15x faster than the Pure path.
## [0.7.1] - 2026-03-22
### Added
- Move hashing into NIF batch calls: `update_many` for HLL, ULL, Theta, and CMS now sends raw items to Rust and hashes inside the NIF, eliminating per-item Elixir heap allocations (94.6% memory reduction at 10M items). (#202)
- Wire `:hash_fn` and `:seed` options through HLL, ULL, Theta, and CMS, enabling custom hash functions and reproducible seeded hashing. (#198)
- Merge hash-compatibility validation: `merge/2` on HLL, ULL, Theta, and CMS now raises `IncompatibleSketchesError` when hash strategy or seed differs between sketches. (#205)
- Pure backend `hll_update_many` optimization: pre-aggregate map with sorted binary splice replaces tuple-based per-hash full-tuple copies, reducing transient allocation from O(n * m) to O(n + m).
- ListIterator-based NIF item decoding for zero-copy Erlang list iteration in Rust.
- Test infrastructure: configurable coverage baselines, Rust CI coverage reporting, 39 new tests covering deserialization edge cases, custom hash_fn paths, helper functions, and merge validation.
### Fixed
- Quotient filter wrap-around bug: `extract_all` in both Pure and Rust backends failed when a cluster wrapped from slot N-1 to slot 0, producing nil quotients (Pure crash) or silent corruption (Rust). (#203, #204)
- CMS merge validation: replaced flawed `Keyword.delete(opts, :hash_strategy)` comparison with explicit width/depth/counter_width checks.
- Pure backend `update_many` regression: restored chunk + batch `*_update_many` path for HLL, ULL, and Theta (was incorrectly using per-item `*_update`).
- Seed clamping: all raw NIF functions now clamp seed values to u64 range before passing to Rust.
- Hash-dependent vector tests tagged with `@tag :rust_nif` to prevent failures in pure-only CI (vectors were generated with xxhash3).
## [0.7.0] - 2026-03-11
### Added
- UltraLogLog sketch (`ExDataSketch.ULL`) for improved cardinality estimation with ~20% lower relative error than HLL at the same memory footprint. ULL1 binary state format with 8-byte header + 2^p registers. EXSK serialization (sketch ID 15).
- ULL register encoding from Ertl 2023: `register_value = 2 * geometric_rank - sub_bit` doubles the information per register compared to HLL.
- FGRA estimator (Ertl 2017 sigma/tau convergence) for ULL cardinality estimation.
- Rust NIF acceleration for ULL: `update_many`, `merge`, and `estimate` operations with dirty scheduler thresholds.
- Precision parameter `p` supports range 4..26 (vs 4..16 for HLL), allowing higher accuracy at larger memory budgets.
- Full API: `new`, `update`, `update_many`, `merge`, `estimate`, `count`, `serialize`, `deserialize`, `from_enumerable`, `merge_many`, `reducer`, `merger`, `size_bytes`.
- ULL test vectors, parity tests, merge law property tests, and benchmark suite.
## [0.6.0] - 2026-03-11
### Added
- REQ sketch (`ExDataSketch.REQ`) for relative-error quantile estimation with configurable high-rank accuracy. REQ1 binary state format. EXSK serialization (sketch ID 13).
- Misra-Gries sketch (`ExDataSketch.MisraGries`) for deterministic heavy-hitter detection with configurable key encoding (`:binary`, `:int`, `{:term, :external}`). MG01 binary state format. EXSK serialization (sketch ID 14).
- XXHash3 NIF integration (`ExDataSketch.Hash.xxhash3_64/1,2`) for fast, cross-platform stable hashing via Rust NIF with phash2-based fallback.
- KLL `cdf/2` and `pmf/2` for cumulative distribution and probability mass functions.
- DDSketch `rank/2` for normalized rank queries.
- Rust NIF acceleration for all membership filters: Bloom, Cuckoo, Quotient, CQF, XorFilter, and IBLT. Batch operations (`put_many`, `merge`, `build`) automatically use compiled Rust NIFs when available, with dirty scheduler thresholds for large inputs.
- Parity tests verifying byte-identical serialization between Pure Elixir and Rust NIF backends for all sketch algorithms.
- Benchmark suites for REQ sketch, Misra-Gries, and XXHash3 NIF throughput.
- `Quantiles` facade for unified quantile sketch API across KLL and DDSketch.
## [0.5.0] - 2026-03-10
### Added
- Cuckoo filter (`ExDataSketch.Cuckoo`) with Pure Elixir backend. CKO1 binary state format. Partial-key cuckoo hashing with configurable fingerprint size, bucket size, and max kicks. Supports insertion, safe deletion, and membership testing. EXSK serialization (sketch ID 8).
- Quotient filter (`ExDataSketch.Quotient`) with Pure Elixir backend. QOT1 binary state format. Quotient/remainder fingerprint splitting with linear probing and metadata bits (is_occupied, is_continuation, is_shifted). Supports insertion, safe deletion, merge, and membership testing. EXSK serialization (sketch ID 9).
- Counting Quotient Filter (`ExDataSketch.CQF`) with Pure Elixir backend. CQF1 binary state format. Extends quotient filter with variable-length counter encoding for multiset membership and approximate counting via `estimate_count/2`. Supports insertion, deletion, merge. EXSK serialization (sketch ID 10).
- XorFilter (`ExDataSketch.XorFilter`) with Pure Elixir backend. XOR1 binary state format. Static build-once immutable filter constructed via `build/2` with 8-bit or 16-bit fingerprints. Supports membership testing only. EXSK serialization (sketch ID 11).
- IBLT (`ExDataSketch.IBLT`) with Pure Elixir backend. IBL1 binary state format. Invertible Bloom Lookup Table for set reconciliation via `subtract/2` and `list_entries/1`. Supports set mode and key-value mode, insertion, deletion, merge. EXSK serialization (sketch ID 12).
- FilterChain (`ExDataSketch.FilterChain`) for capability-aware membership filter composition. FCN1 binary state format. Lifecycle-tier patterns (hot/warm/cold) with stage position enforcement. Supports `add_stage/2`, `put/2`, `member?/2`, `delete/2`. Serializes all stages in order.
- Benchmark suites for Cuckoo, Quotient, CQF, XorFilter, IBLT, and FilterChain (`bench/*.exs`).
- `UnsupportedOperationError` for operations not supported by a structure (used by FilterChain).
- `InvalidChainCompositionError` for invalid FilterChain stage composition.
- `capabilities/0` function on Bloom, Cuckoo, Quotient, CQF, XorFilter, IBLT, and FilterChain modules.
- Cuckoo, Quotient, CQF, XorFilter, IBLT, and FilterChain backend callbacks on `ExDataSketch.Backend`.
## [0.4.0] - 2026-03-06
### Added
- Bloom filter (`ExDataSketch.Bloom`) with Pure Elixir backend.
- BLM1 binary state format (40-byte header + LSB-first packed bitset).
- Double hashing (Kirsch-Mitzenmacher) deriving k bit positions from a single 64-bit hash.
- Bloom backend callbacks: `bloom_new/1`, `bloom_put/3`, `bloom_put_many/3`, `bloom_member?/3`, `bloom_merge/3`, `bloom_count/2`.
- Automatic parameter derivation from capacity and false_positive_rate options.
- Bloom merge via bitwise OR with validation of matching bit_count, hash_count, and seed.
- Bloom popcount-based cardinality estimation.
- Bloom serialization via EXSK envelope (sketch ID 7).
- Bloom property tests (no false negatives, merge commutativity/associativity/identity, serialization round-trip).
- Bloom statistical validation tests (observed FPR within 2x of target).
- Bloom merge law properties in merge_laws_test.exs.
- Bloom parity test stubs for future Rust NIF backend.
- Bloom benchmark suite (`bench/bloom_bench.exs`).
- Bloom options section in usage guide.
## [0.3.0] - 2026-03-06
### Added
- FrequentItems sketch (`ExDataSketch.FrequentItems`) using the SpaceSaving algorithm with Pure Elixir and Rust NIF backends.
- FI1 binary state format (32-byte header + variable-length sorted entries).
- FrequentItems backend callbacks: `fi_new/1`, `fi_update/3`, `fi_update_many/3`, `fi_merge/3`, `fi_estimate/3`, `fi_top_k/3`, `fi_count/2`, `fi_entry_count/2`.
- Batch optimization via pre-aggregation (`Enum.frequencies/1`) with weighted updates.
- Deterministic tie-breaking on eviction (lexicographically smallest item_bytes).
- Key encoding policies: `:binary`, `:int` (signed 64-bit LE), `{:term, :external}`.
- Commutative merge via additive count combination and canonical replay.
- Rust NIF acceleration for `fi_update_many` and `fi_merge` with dirty scheduler support.
- FrequentItems support in `ExDataSketch.update_many/2` facade.
- FrequentItems merge law properties (commutativity, identity, count conservation).
- FrequentItems golden vector test fixtures.
- FrequentItems parity tests ensuring byte-identical output between Pure and Rust backends.
- FrequentItems benchmark suite (`bench/frequent_items_bench.exs`).
- EXSK codec sketch ID 6 for FrequentItems.
- FrequentItems usage documentation in usage guide with SpaceSaving algorithm overview.
- Mox test dependency for backend contract testing.
- Theta `compact/1` function for explicit compaction.
## [0.2.1] - 2026-03-05
### Added
- DDSketch quantiles sketch (`ExDataSketch.DDSketch`) with Pure Elixir and Rust NIF backends.
- DDSketch backend callbacks: `ddsketch_new/1`, `ddsketch_update/3`, `ddsketch_update_many/3`, `ddsketch_merge/3`, `ddsketch_quantile/3`, `ddsketch_count/2`, `ddsketch_min/2`, `ddsketch_max/2`.
- Rust NIF acceleration for `ddsketch_update_many` and `ddsketch_merge` with dirty scheduler support.
- DDSketch support in `ExDataSketch.Quantiles` facade (`type: :ddsketch`).
- DDSketch merge law properties (commutativity, identity, count additivity, min/max preservation).
- DDSketch golden vector test fixtures (empty, single, small_set, merge, zeros).
- DDSketch parity tests ensuring byte-identical output between Pure and Rust backends.
- DDSketch benchmark suite (`bench/ddsketch_bench.exs`).
- EXSK codec sketch ID 5 for DDSketch.
- DDSketch usage documentation in usage guide with KLL vs DDSketch comparison table.
## [0.2.0] - 2026-03-04
### Added
- KLL quantiles sketch (`ExDataSketch.KLL`) with Pure Elixir and Rust NIF backends.
- `ExDataSketch.Quantiles` facade module for type-dispatched quantile sketch access.
- KLL backend callbacks: `kll_new/1`, `kll_update/3`, `kll_update_many/3`, `kll_merge/3`, `kll_quantile/3`, `kll_rank/3`, `kll_count/2`, `kll_min/2`, `kll_max/2`.
- Rust NIF acceleration for `kll_update_many` and `kll_merge` with dirty scheduler support.
- KLL merge law properties (associativity, commutativity, identity, count additivity, min/max preservation).
- KLL golden vector test fixtures (empty, single, small_set, merge).
- KLL parity tests ensuring byte-identical output between Pure and Rust backends.
- KLL benchmark suite (`bench/kll_bench.exs`).
- EXSK codec sketch ID 4 for KLL.
## [0.1.1] - 2026-03-04
### Added
- Deterministic golden vector test fixtures for HLL, CMS, and Theta (JSON format with versioned schema).
- Pure vs Rust parity test suite ensuring byte-identical serialization and estimates.
- Merge-law property tests (associativity, commutativity, identity, chunking equivalence) for all sketch types.
- Compatibility and Stability section in README documenting serialization and parity guarantees.
- CI regression tracking for coverage and benchmark baselines.
### Changed
- Stabilized benchmark scripts with deterministic datasets and JSON output.
- Clarified HLL and CMS DataSketches interop stubs as intentionally unimplemented (not "future").
- Removed stale "Phase 2" language from module documentation.
## [0.1.0] - 2026-03-02
### Added
- Precompiled Rust NIF binaries for macOS (ARM64, x86_64) and Linux (x86_64 gnu/musl, aarch64 gnu/musl).
- Optional Rust NIF acceleration backend (`ExDataSketch.Backend.Rust`).
- Rust NIFs for HLL (update_many, merge, estimate), CMS (update_many, merge), and Theta (update_many, merge).
- Normal and dirty CPU scheduler NIF variants with configurable thresholds.
- Automatic fallback to Pure Elixir backend when Rust NIF is unavailable.
- Cross-backend parity tests ensuring byte-identical output between Pure and Rust.
- Side-by-side Pure vs Rust benchmark scenarios.
- CI jobs for Rust NIF compilation and testing (`test-rust`, `bench-rust`).
- Pure Elixir Theta sketch implementation (new, update, update_many, compact, merge, estimate).
- Apache DataSketches CompactSketch codec (serialize/deserialize) for Theta interop.
- MurmurHash3 seed hash computation for DataSketches compatibility.
- Deterministic test vectors for Theta sketch.
- Cross-language vector harness specification for Java interop testing.
- Theta Benchee benchmarks.
- Pure Elixir HLL implementation (new, update, update_many, merge, estimate).
- Pure Elixir CMS implementation (new, update, update_many, merge, estimate).
- Deterministic test vectors for HLL and CMS.
- Real Benchee benchmarks for HLL and CMS.
- Project skeleton with directory structure and dependencies.
- Public API stubs for HLL, CMS, and Theta sketch modules.
- ExDataSketch-native binary codec (EXSK format).
- Hash module with stable 64-bit hash interface.
- Backend behaviour with Pure Elixir stub implementation.
- Quick Start and Usage Guide documentation.
- GitHub Actions CI workflow.
- Integration convenience functions (`from_enumerable/2`, `merge_many/1`, `reducer/1`, `merger/1`) on all sketch modules.
- Integration guide with ecosystem examples (Flow, Broadway, Explorer, Nx, ex_arrow/ExZarr).
- Documented merge properties (associativity, commutativity) for HLL, CMS, and Theta.