HyperLogLog

Зачем нужно знать

Вопрос «сколько уникальных X?» (count distinct) — один из самых частых в analytics:

• Уникальные посетители страницы за день / месяц / квартал.
• Уникальные source IP в DDoS-атаке за последние 5 минут.
• Distinct search queries в поисковике, distinct user-агенты.
• Daily / monthly active users в product analytics.
• Уникальные клиенты, тронувшие фичу — для A/B-теста.

Наивное решение — HashSet. Точное, идемпотентное, легко merge-ить. И полностью неработоспособное в масштабе: 8 байт на хэш × 1 миллиард уникальных элементов = ~16 GB RAM на одну метрику. А метрика обычно не одна: per metric × per day × per dimension (страна, устройство, segment) — память взрывается на порядки.

HyperLogLog решает это радикально: constant memory ~12 KB для cardinality от нуля до 10^9+, ценой ~0.81% относительной ошибки. Это 1.3 миллиона раз меньше памяти. На этом построены APPROX_COUNT_DISTINCT в BigQuery, uniqHLL12 в ClickHouse, PFCOUNT в Redis, approx-distinct в Presto/Snowflake/Redshift — везде, где «приблизительно» дешевле «точно» на четыре порядка.

Mental model

«Хеш равномерно распределяет элементы по битовым строкам. Самая длинная серия лидирующих нулей, которую ты видел в хэшах, говорит, сколько уникальных элементов прошло мимо: P(k нулей подряд) = 1/2^k, значит чтобы такой хэш появился, нужно ~2^k уникальных samples. Один наблюдаемый run слишком шумный → разбиваем поток на m бакетов, в каждом запоминаем max leading zeros, потом берём harmonic mean. Память — m регистров по байту, ~12 KB на счётчик, независимо от того, сколько элементов прошло.»

Ключевая интуиция: HLL — это не «компрессия HashSet'а», это другой ответ на другую задачу. HashSet помнит, что он видел. HLL помнит только насколько разнообразный поток он видел. Большинство аналитических вопросов на самом деле второго типа.

Что показывает диаграмма

Канвас построен как side-by-side сравнение двух подходов к одной задаче — count distinct:

• Event stream (клиент слева) — общий источник: миллионы / миллиарды событий с user_id, ip, search-query.
• HashSet (exact) — наивный counter. Хранит каждый уникальный hash. Точный, но память линейна по cardinality.
• HLL register (12KB) — пробабилистический counter. Constant size. Содержит ADR с trade-off rationale.

Оба counter'а получают одинаковый поток событий (две одинаковые edges client → naive-counter и client → hll-counter). Дальше сценарии показывают, как ведёт себя память и ошибка при росте N от 100K до 1B.

Сценарии и что они учат

Наивный путь — HashSet. На 100K событий 5 MB, на 10M — 160 MB, на 1B — 16 GB RAM, и это на одну метрику. Сценарий заканчивается showError, потому что в реальном production это не «дорого», а буквально невозможно держать в памяти при per-day × per-dimension сегментации.

HLL на тех же данных. 100K → 12 KB. 10M → 12 KB. 1B → 12 KB. Constant size. Estimate возвращает cardinality с ошибкой 1.04 / √m: при m=16384 это 0.81% (на 1 миллиарде это ~8.1M ошибки — допустимо для дашборда, недопустимо для billing). Сценарий показывает, что выбор precision (m=4096 → 1.6%, m=16384 → 0.81%) — это явный трейд-офф память против точности, известный заранее.

Самое мощное свойство HLL — mergeable. Union двух HLL = element-wise max(A.registers, B.registers). Это даёт две большие возможности: (1) distributed compute — каждый шард считает локальный HLL, координатор берёт max'ы; (2) time-window rollups — 24 hourly HLL → daily HLL без переагрегации raw events. Network cost линеен от числа шардов: 12 KB × 100 shards = 1.2 MB на rollup, что на порядки дешевле, чем гонять сырые события.

Production check-in: PFADD/PFCOUNT/PFMERGE в Redis, APPROX_COUNT_DISTINCT в BigQuery (HLL++), uniqHLL12 в ClickHouse, approx_distinct в Presto, APPROXIMATE COUNT(DISTINCT) в Redshift, sketches first-class в Druid, DDoS source-IP estimation в Cloudflare DNS analytics. HLL — стандарт de facto, и встроен в любую современную analytical DB.

Trade-offs (развёрнутые ADR)

Память vs точность: выбор precision (p, m)

Параметр HLL — это p (количество бит на bucket index), m = 2^p регистров. Ошибка σ ≈ 1.04 / √m.

Правило: для дашбордов (DAU, MAU) хватает p=12..14. Для billing/compliance — HLL вообще не подходит, нужен exact. Для high-cardinality DDoS-source-IP в реальном времени p=14 — оптимум.

Constant memory vs «учится» на cardinality

В отличие от Count-Min Sketch (где растёт ошибка с N), у HLL constant relative error для всего диапазона m..2^32+. Это значит: на 10K и на 10B точность одинаковая в процентах. Абсолютная ошибка растёт, но это обычно ОК — на 10B уникальных user'ов разница в 8M никого не парит.

Sparse vs Dense representation

HLL++ (Google, 2013) ввёл sparse format: пока ненулевых регистров мало, хранить пары (bucket, rho) сильно дешевле, чем 16 KB. Redis тоже использует sparse format и конвертирует в dense только когда становится невыгодно. Следствие: для thin keys (мало уникальных значений) HLL почти бесплатен; это убирает «overhead на пустой счётчик» и делает массовое создание HLL-counter-ов реальным.

Mergeable vs Sketch composability

Union у HLL точен (мерж idempotent, ассоциативный). Но intersection через inclusion-exclusion (|A ∩ B| = |A| + |B| - |A ∪ B|) — катастрофически шумный для маленьких пересечений: вычитание двух чисел ~равной величины с ε каждый → ε вычитания взрывается. Если нужны intersections — используйте MinHash или Theta sketches (Apache DataSketches), они дают controlled error на intersect/difference.

Hash function quality — невидимый риск

Вся математика HLL держится на предположении, что хэш-функция даёт uniform random bits. Плохой хэш (MD5 на коротких строках, наивный hashCode на user_id-числах) даёт коррелированные buckets → ε взлетает на порядок. Правило: только MurmurHash3, xxHash, CityHash, SipHash. Не FNV, не Java hashCode. И — критично — один и тот же seed во всех шардах, иначе merge даёт мусор.

CP vs AP в распределённом сценарии

HLL встроен в большинство AP-систем (Cassandra, Redis Cluster, ClickHouse). Это работает естественно: counter eventually-consistent → final merge convergent. Для CP-систем (etcd, Spanner) HLL не нужен — у них и так строгая семантика и они не работают на cardinality уровня 10^9.

Реальные системы

• Redis — PFADD / PFCOUNT / PFMERGE с 2.8.9 (2014). Реализация Salvatore Sanfilippo (antirez), sparse → dense conversion. До 12 KB на ключ. PFADD ~1M ops/s на одно ядро. Это самый частый production HLL в мире.
• Google BigQuery — APPROX_COUNT_DISTINCT(), HLL_COUNT.INIT, HLL_COUNT.MERGE, HLL_COUNT.EXTRACT. Реализация HLL++ из их же paper (Heule, Nunkesser, Hall, 2013).
• ClickHouse — uniqHLL12() (m=4096, ε≈1.6%), uniqCombined() (адаптивный: hash table → HLL), uniqExact() (точный, для маленьких). Используется в production analytics rollups петабайтного масштаба.
• AWS Redshift — APPROXIMATE COUNT(DISTINCT ...) под капотом HLL.
• Snowflake — APPROX_COUNT_DISTINCT() через HLL.
• Facebook Presto / Trino — approx_distinct(). Daily active users tracking.
• Apache Druid — sketches как first-class column type, в т.ч. HLL и Theta.
• Apache DataSketches (Yahoo, теперь ASF) — production-grade library: HLL + Theta + Quantiles + KLL. Theta sketches покрывают intersection/difference, чего HLL не умеет.
• Twitter Algebird — Scala-библиотека скетчей, используется в Heron / production streaming.
• Cloudflare — оценка уникальных source-IP в DNS analytics, DDoS-источники.
• Reddit, Datadog, Honeycomb — internal analytics dashboards, unique entity counts.

Общий паттерн: everyone uses HLL, и обычно не один — HLL для distinct count, Count-Min Sketch для frequency, Theta для set ops, t-digest для percentiles. Это стандартный sketch-toolkit modern analytics.

Anti-patterns

• HLL для billing, compliance, audit. Если за расхождение на 1 user'а будут судить — HLL нельзя. Точно. Никогда. Используйте exact count с поддержкой incremental dedup (HashSet → Bloom filter prefilter → exact storage).
• HLL для frequency (сколько раз X появился). HLL отвечает на «сколько уникальных», не «сколько раз». Для frequency — Count-Min Sketch.
• HLL для intersection через inclusion-exclusion. Ошибка вычитания двух noisy estimates взрывается. Для intersect — MinHash или Theta sketches.
• Разные hash seed на разных шардах. Merge даёт корректный по форме, но семантически мусорный результат. Закрепляйте seed в коде и в migration plan.
• Слабая hash-функция. FNV / Java hashCode / MD5 на коротких ключах → коррелированные buckets → ε × 5..10. Используйте Murmur3 / xxHash / CityHash / SipHash.
• Игнорировать sparse representation. На системе с миллионом ключей, у каждого по 10 уникальных значений, dense HLL = 12 GB; sparse HLL = десятки MB. В Redis это бесплатно (сам конвертирует), в самописных — нет.
• Merge HLL с разными precisions без careful downsampling. Можно — но теряете точность до меньшей precision и обязаны помнить об этом во всём pipeline.
• HLL «на всякий случай» для маленьких N (<1000). Overhead constant 12 KB не оправдан — exact HashSet дешевле и точен.

Когда НЕ использовать

• Точность критична (деньги, юридические записи, billing usage, инвентарь).
• Нужны частоты, а не уникальность — это домен Count-Min Sketch.
• Нужны intersections / differences с малым overlap — MinHash / Theta dominate здесь.
• Cardinality всегда маленькая (<1000) — exact HashSet проще, точен, и не имеет fixed-overhead.
• Нужны сами элементы, а не их количество (хочется итерировать по уникальным user_id) — HLL не хранит элементы, только sketches.
• Strong consistency требований на counter — HLL построен для eventual / merge-friendly мира, не для linearizable counters (для них — CRDT G-Counter или Spanner-style consensus).

Дальше читать

Фундаментальные papers:

• Flajolet, Fusy, Gandouet, Meunier — HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm (DMTCS 2007) — оригинал. https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
• Heule, Nunkesser, Hall — HyperLogLog in Practice (Google, EDBT 2013) — bias correction, sparse representation, production tricks. https://research.google/pubs/pub40671/
• Durand, Flajolet — LogLog Counting of Large Cardinalities (2003) — предшественник HLL.
• Whang et al. — A Linear-Time Probabilistic Counting Algorithm (1990) — predecessor для small-range mode.

Production docs:

• Redis HLL: https://redis.io/commands/?group=hyperloglog
• antirez blog post про HLL в Redis: http://antirez.com/news/75
• ClickHouse uniqHLL12: https://clickhouse.com/docs/en/sql-reference/aggregate-functions/reference/uniqhll12
• BigQuery HLL functions: https://cloud.google.com/bigquery/docs/reference/standard-sql/hll_functions
• Apache DataSketches Theta: https://datasketches.apache.org/docs/Theta/ThetaSketchFramework.html

Концепты рядом:

• ::concept{slug="probabilistic-data-structures"} — обзор всего sketch-семейства (HLL, Bloom, Count-Min, MinHash, t-digest).
• Bloom filter — membership («видел ли X?»), constant memory.
• Count-Min Sketch — frequency («сколько раз X?»).
• MinHash — Jaccard similarity между sets.
• Theta sketches — union + intersection + difference с известной ошибкой.

Применяется в кейсах:

• Любой analytics pipeline (см. кейсы про Twitter / Instagram timelines) — DAU/MAU считаются через HLL.
• Rate limiter с unique-source-IP tracking — HLL для «сколько уникальных IP стучатся в endpoint».
• DDoS detection — HLL по source-IP в скользящем окне.