HLL (HyperLogLog) Tutorial

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

Introduction

Every event that arrives gets hashed. ExDataSketch.HLL looks at the pattern of that hash -- specifically, how long a run of leading zero bits it has -- and keeps only the longest run it has ever seen, per bucket. Long runs are exponentially rare, so if you've observed a very long one, you've probably hashed a lot of distinct items. That's the whole trick: no set, no list, no per-item bookkeeping, just 2^p single-byte counters updated in place, forever:

flowchart LR
    A[event] --> B["hash(event)"]
    B --> C["first p bits\n= register index"]
    B --> D["remaining bits\n= leading-zero run length"]
    C --> E["registers[index] =\nmax(current, run length)"]
    D --> E
    E --> F["harmonic mean\nacross 2^p registers"]
    F --> G["cardinality\nestimate"]

Use it for: "how many unique visitors," "how many distinct IPs hit this endpoint," "how many distinct users touched this feature this month" -- any question where the count of distinct items matters but you don't need to know which items they were, at a scale where holding every item in memory would be wasteful or impossible.

Don't use it for: exact counts (HLL is inherently probabilistic -- reach for a MapSet or a database COUNT(DISTINCT ...) when the number must be precise), membership testing ("was X one of the items I've seen?" -- HLL can't answer that at all; see ExDataSketch.Bloom or ExDataSketch.Cuckoo), or per-item frequency ("how many times did X occur?" -- see ExDataSketch.CMS).

What it buys you: a precision-14 HLL is a fixed 16 KB (4 + 2^p bytes, see the moduledoc's "Binary State Layout"), whether it has counted a thousand events or a billion -- with roughly 0.8% expected error at that precision (the formula is ~1.04/sqrt(2^p); see "Precision Range" below for the full table). An exact set holding a billion identifiers keeps growing without bound; the sketch does not:

If a fraction of a percent of error is an acceptable trade for constant, tiny memory, HLL is usually the right first reach for a distinct-count problem.

Sample data (cached locally)

2,000,000 page-view events from a pool of 500,000 distinct visitors -- so the true distinct count is 500,000, even though there are 4x as many events. This mismatch (events != distinct visitors) is exactly what HLL is for. ExDataSketch.SampleData generates and caches this (and every other tutorial's sample data) to a local file, so re-running this livebook later is instant after the first time.

events = ExDataSketch.SampleData.hll_events()
IO.puts("#{length(events)} events ready (true distinct count: 500,000)")

Basic usage

alias ExDataSketch.HLL

sketch = HLL.new(p: 14)
sketch = HLL.update(sketch, "visitor_1")
HLL.estimate(sketch)

update/2 is for one item at a time; update_many/2 (or from_enumerable/2 to build straight from a collection) is far more efficient for a batch like our sample data:

sketch = HLL.from_enumerable(events, p: 14)

estimate = HLL.estimate(sketch)
true_count = 500_000
error_pct = abs(estimate - true_count) / true_count * 100

IO.puts("Estimate: #{Float.round(estimate, 0)}")
IO.puts("True count: #{true_count}")
IO.puts("Error: #{Float.round(error_pct, 2)}%")
IO.puts("Sketch size: #{HLL.size_bytes(sketch)} bytes")

Precision trade-off

:p controls both memory (2^p registers) and accuracy. Higher p means more memory, less error:

for p <- [4, 10, 12, 14, 16, 20] do
  sketch = HLL.from_enumerable(events, p: p)
  estimate = HLL.estimate(sketch)
  error_pct = abs(estimate - 500_000) / 500_000 * 100

  IO.puts(
    "p=#{p}: #{HLL.size_bytes(sketch)} bytes, " <>
      "estimate=#{Float.round(estimate, 0)}, error=#{Float.round(error_pct, 2)}%"
  )
end

Why 4..26?

p >= 4 is a real algorithmic floor: the bias-correction constant alpha(m) (m = 2^p, the register count) is only defined via exact published values for m in {16, 32, 64} plus a general asymptotic formula valid for m >= 128 -- together these cover exactly p >= 4, with no case for p < 4.

p <= 26 is a practical ceiling, not an algorithmic one -- nothing in HLL's register encoding or estimator caps p below 26 (registers are plain bytes with tons of headroom, and alpha(m)'s formula works for any m >= 128). It's set to 26 specifically to match ExDataSketch.ULL's ceiling, which is a hard limit (see ull.livemd), so choosing between the two estimators is an apples-to-apples memory/precision tradeoff. At p = 26 a single sketch is 64 MiB -- most workloads should stay at p <= 18 or so, well below either ceiling.

Merging (distributed counting)

HLL merge is associative and commutative -- you can split your event stream across N workers, each builds its own sketch, and merging them gives the same answer as if one process had seen everything:

half = div(length(events), 2)
{first_half, second_half} = Enum.split(events, half)

worker_a = HLL.from_enumerable(first_half, p: 14)
worker_b = HLL.from_enumerable(second_half, p: 14)

merged = HLL.merge(worker_a, worker_b)
IO.puts("Merged estimate: #{Float.round(HLL.estimate(merged), 0)} (true: 500,000)")

Serialization

sketch = HLL.from_enumerable(Enum.take(events, 100_000), p: 14)
IO.puts("before serialize estimate: #{Float.round(HLL.estimate(sketch), 0)}")
binary = HLL.serialize(sketch)
{:ok, restored} = HLL.deserialize(binary)

IO.puts("Round-tripped estimate: #{Float.round(HLL.estimate(restored), 0)}")

Operational guidance

See also

• ExDataSketch.HLL module documentation -- full API reference.
• ExDataSketch.ULL -- an alternative cardinality estimator; see livebooks/sketches/ull.livemd for the comparison.
• guides/streaming_sketches.md, livebooks/streaming_cardinality.livemd -- Stream/Collectable integration instead of building from a plain list.
• guides/apache_interop.md -- reading/writing sketches built by the Apache DataSketches Java/C++/Python implementations.