HyperLogLog: Подсчёт уникальных за O(1) память

Цели урока

• Понять проблему cardinality estimation
• Освоить идею: ведущие нули как индикатор количества
• Реализовать HyperLogLog с бакетами
• Использовать Redis PFCOUNT

Предварительные знания

• Bloom Filter
• Хеш-функции

• Bloom Filter

Google обрабатывает миллиарды поисковых запросов в день. Как узнать сколько уникальных запросов было за месяц, не храня их все? HyperLogLog отвечает с точностью 99% используя всего 12 килобайт.

• Redis PFCOUNT - встроенный HyperLogLog
• Google BigQuery APPROX_COUNT_DISTINCT
• Apache Spark - approximate distinct count
• Аналитические системы - уникальные пользователи

Почти оптимальный оценщик Флажоле

HyperLogLog был опубликован в 2007 году Филиппом Флажоле, Эриком Фюзи, Оливье Гандуэ и Фредериком Мёнье в статье 'HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm'. Он стал последним в ряду оценщиков. Алгоритм Флажоле-Мартена 1985 года ввёл основной приём: использовать позицию младшего установленного бита в хеше для оценки кардинальности. Алгоритм LogLog Марианны Дюран и Филиппа Флажоле 2003 года добавил идею разбиения потока на множество бакетов и усреднения их оценок. HyperLogLog уточнил это, заменив геометрическое среднее на гармоническое, что резко снизило влияние бакетов-выбросов и довело стандартную ошибку примерно до 1.04 на корень из числа бакетов. В результате миллиарды уникальных элементов считаются примерно в 12 килобайтах. Сегодня он лежит в основе Redis PFCOUNT и APPROX_COUNT_DISTINCT в BigQuery, а также многих других систем.

Проблема: Подсчёт уникальных

**Задача:** сколько уникальных посетителей на сайте? Уникальных IP? Уникальных запросов?

**Redis PFCOUNT** использует HyperLogLog - 12 KB на любое количество элементов!

Идея: Вероятность редких событий

**Наблюдение:** если хешировать элементы в бинарное представление, редкие паттерны указывают на количество элементов.

**Интуиция:** чем больше уникальных элементов, тем выше шанс увидеть 'редкий' хеш с множеством нулей. Максимум нулей ≈ log₂(n).

Улучшение: Много бакетов

**Проблема:** один счётчик даёт большую дисперсию. Решение: много независимых оценок!

**Почему гармоническое среднее?** Арифметическое среднее искажается выбросами. Гармоническое устойчиво к редким большим значениям.

**Память:** 16384 бакета × 6 бит = 12 KB. Точность: σ ≈ 1.04/√m ≈ 0.81%

Реализация HyperLogLog

Применения HyperLogLog

• **Redis PFCOUNT** - подсчёт уникальных ключей/значений
• **Google BigQuery** - APPROX_COUNT_DISTINCT
• **PostgreSQL** - расширение для cardinality estimation
• **Аналитика** - уникальные посетители, сессии, события
• **Сетевой мониторинг** - уникальные IP, соединения

**Merge HLL** - можно объединять несколько HyperLogLog в один! Полезно для агрегации по времени (дни → недели → месяцы).

HyperLogLog

• Оценивает количество уникальных за O(1) память
• Идея: редкие хеши (много нулей) указывают на большое n
• Много бакетов → гармоническое среднее → точность ~1%
• Redis: 12 KB на любое количество элементов
• Можно merge несколько HLL в один

Вероятностные структуры

HyperLogLog - часть семейства sketch-алгоритмов. Другие: Count-Min Sketch (частоты), Bloom Filter (членство), MinHash (сходство множеств).

• Bloom Filter — Проверка членства

Связанные уроки

• ds-24-bloom-filter — Обе - вероятностные скетчи, использующие минимум памяти
• ds-06-hash-intro — Хеширование распределяет элементы для оценки шаблонов нулей
• prob-07-expectation — Оценка строится на математическом ожидании числа ведущих нулей
• db-19-redis — Redis предоставляет PFCOUNT на основе HyperLogLog
• stat-02-estimation — Оценка мощности множества - это статистическая точечная оценка
• crypto-19-hash-functions