Точный подсчёт требует хранить все уникальные id. HyperLogLog оценивает их число с ошибкой ~0,8%, используя 12 КБ на любое количество — от тысячи до миллиардов.
А ещё Пересечение считается хуже (через включение-исключение) — с большой ошибкой
Так подсказку видит пользователь sotto на живом собеседовании — за пару секунд, пока вы думаете вслух.
Почему не точно. Уникальные посетители за день — это множество id. Хранить множество из сотни миллионов id — гигабайты, и объединение множеств для недели и месяца тоже дорогое. Для отчётов и дашбордов часто достаточно точности в 1–2%.
Интуиция. Хешируем id в равномерное случайное число. Вероятность, что хеш начинается с r нулей, — 1/2^r. Если среди всех хешей самая длинная серия ведущих нулей равна 20, разных значений было порядка 2²⁰ ≈ миллион. Повторы одного id дают тот же хеш и ничего не меняют — считаются именно уникальные.
Как уменьшить шум. Одна такая оценка очень неточна. HyperLogLog берёт первые p бит хеша как номер корзины (в Redis 2¹⁴ = 16 384 корзины), а в остальных битах считает серию нулей; в каждой корзине хранится максимум (6 бит). Оценка — нормированное гармоническое среднее 2^max по корзинам с поправками для малых и больших значений. Стандартная ошибка ≈ 1,04 / √(число корзин) — для 16 384 корзин 0,81%. Память — 16 384 × 6 бит = 12 КБ.
Объединение. Скетч объединения двух множеств — поэлементный максимум корзин. Поэтому хранят HLL на каждый час или день и собирают любые периоды: уникальные за неделю — объединить 7 дневных скетчей, уникальные по стране и платформе — объединить соответствующие. Точными множествами так не сделать дёшево.
Где применяют: уникальные посетители и пользователи, число разных поисковых запросов, COUNT(DISTINCT) в аналитике (uniq в ClickHouse, APPROX_COUNT_DISTINCT в BigQuery и Snowflake, approx_count_distinct в Spark), мониторинг (сколько разных IP стучится).
Ограничения: только оценка числа, нельзя спросить «был ли этот id» (для этого — фильтр Блума); пересечения — через |A| + |B| − |A ∪ B|, и при малом пересечении относительная ошибка огромна; на очень малых множествах используется точный режим или поправка (в Redis — разреженное представление).
sottoPFADD visitors:2026-10-10 user:42 user:7 user:42 → 1
PFCOUNT visitors:2026-10-10 → 2
PFMERGE visitors:week visitors:2026-10-04 … visitors:2026-10-10
PFCOUNT visitors:week → 18 304 117 (± ~0,8%), ключ занимает ≤ 12 КБCOUNT(DISTINCT) по сырым событиям за месяц на лету.sotto слышит вопрос интервьюера и показывает короткий ответ и план, как в блоке «Коротко». Оставьте контакт — пришлём доступ и промокод.