HLL (HyperLogLog) Tutorial

Mix.install([
  {:ex_data_sketch, "~> 0.10"}
])

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 <- [10, 12, 14, 16] 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

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%