HLL (HyperLogLog) Tutorial

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

Introduction

ExDataSketch.HLL estimates the number of distinct items in a stream -- "how many unique visitors," "how many distinct IPs" -- in a fixed, tiny amount of memory, regardless of how many events you feed it. A precision-14 HLL is about 16KB whether it has seen a thousand events or a billion.

The trade is accuracy: HLL gives you an estimate, typically within 1-2% of the true count at default precision, not an exact number. If you need exact counts, use a MapSet; if a few percent of error is fine in exchange for constant memory, HLL is the tool.

Sample data (cached locally)

Generating a few million semi-realistic events takes a moment, so this cell caches the result to a local file and only regenerates it if that file doesn't exist yet -- re-running this livebook later (or re-running just this cell) is instant after the first time.

cache_path = Path.join(System.tmp_dir!(), "ex_data_sketch_livebook_cache/hll_sample.bin")

events =
  if File.exists?(cache_path) do
    IO.puts("Loading cached sample data from #{cache_path}")
    cache_path |> File.read!() |> :erlang.binary_to_term()
  else
    IO.puts("Generating sample data (this takes a few seconds)...")

    # 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.
    events = for _ <- 1..2_000_000, do: "visitor_#{:rand.uniform(500_000)}"

    File.mkdir_p!(Path.dirname(cache_path))
    File.write!(cache_path, :erlang.term_to_binary(events))
    events
  end

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

`p`	Memory	Typical error
10	~1KB	~3.25%
12	~4KB	~1.6%
14	~16KB	~0.8% (recommended default)
16	~64KB	~0.4%