Вопрос с собеседования · Highload

Как посчитать число уникальных посетителей за день при миллиардах событий?

SeniorВероятностные структуры
Ещё спрашивают так:
  • Что такое HyperLogLog?
  • Как оценить количество различных элементов без хранения всех?
  • Как работает PFCOUNT в Redis?
Коротко

Точный подсчёт требует хранить все уникальные id. HyperLogLog оценивает их число с ошибкой ~0,8%, используя 12 КБ на любое количество — от тысячи до миллиардов.

  • Идея: в случайных хешах серия ведущих нулей длины r встречается примерно раз на 2^r разных значений
  • Хеш делится на корзины, в каждой хранится максимум серии нулей; оценка — гармоническое среднее
  • Скетчи объединяются (максимум по корзинам): уникальные за неделю = объединение дневных

А ещё Пересечение считается хуже (через включение-исключение) — с большой ошибкой

Подробно

Почему не точно. Уникальные посетители за день — это множество 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 — разреженное представление).

Пример

PFADD 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 КБ

Что хотят услышать

  • Почему точный подсчёт дорог и когда приближение допустимо.
  • Идея ведущих нулей в хеше и усреднение по корзинам.
  • Порядки: 12 КБ и ~0,8% ошибки.
  • Объединение скетчей и применение для окон времени.

Частые ошибки

  • Пытаться считать уникальные через COUNT(DISTINCT) по сырым событиям за месяц на лету.
  • Ожидать точного ответа или проверки принадлежности от HyperLogLog.

Проверьте себя

Один верный вариант. Подумайте, потом откройте ответ.

Показать варианты и ответ
  • ✗HyperLogLog хранит все уникальные id
  • ✗Память растёт линейно с числом уникальных
  • ✗Скетчи HyperLogLog нельзя объединять
  • ✓HyperLogLog: ошибка ~0,8% в 12 КБ при любом объёме

Связанные вопросы

Партнёр платформы

Разбор собеседования с sotto

После собеседования sotto разбирает разговор: оценка, каждый вопрос — хорошо, частично или слабо, чего не хватило в ответе и над чем поработать к следующему разу. Первые 30 минут бесплатно.

Разбор собеседования