HyperLogLog

Предпосылки: String, хеш-функция (детерминированность, равномерное распределение), SET.

← Stream | Bitmap и Bitfield →

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

Один счётчик уникальных элементов — тривиальная задача. SET с миллионом строк средней длины занимает порядка 50 МБ. На сервере с сотнями гигабайт RAM это ничего.

Масштаб всё меняет. Аналитическая система считает уникальных посетителей на каждую страницу в каждый день. При 100 000 страниц и 365 днях получается 36,5 миллионов отдельных счётчиков. Даже при средней кардинальности каждого SET’а суммарная память уходит в сотни гигабайт — и всё это только ради подсчёта уникальных. Сетевой мониторинг добавляет ещё одно измерение: уникальные IP на порт в минуту, тысячи портов × 1440 минут в сутках — миллионы счётчиков ежедневно.

Можно ли оценить количество уникальных элементов, не храня сами элементы?

Идея: статистика вместо хранения

Вместо того чтобы запоминать каждый элемент, можно наблюдать за статистическими паттернами в хеш-значениях этих элементов и по ним оценивать кардинальность.

Аналогия с монетой помогает уловить суть. Подбрасываем честную монету много раз подряд. Пять решек подряд — событие с вероятностью 1/32. Десять подряд — 1/1024. Если кто-то сообщает «я видел 10 решек подряд», можно оценить: подбрасываний было около тысячи. При этом не нужно знать результат каждого отдельного броска — достаточно знать длину самой длинной серии.

Биты хеш-значения работают так же. Хеш-функция с равномерным распределением даёт каждому биту вероятность 0 или 1 ровно 1/2 — те же «подбрасывания». Если среди хешей всех добавленных элементов самая длинная серия ведущих нулей имеет длину k, то количество уникальных элементов приблизительно равно 2^k. Добавили один элемент с хешем 0001… — максимум 3 ведущих нуля, оценка ≈ 8. Добавили тысячу элементов — среди них, скорее всего, встретится хеш с 10 ведущими нулями, оценка ≈ 1024.

Наивный подход — хранить один максимум ведущих нулей — даёт огромную дисперсию. Можно «угадать» длинную серию при малом количестве элементов или, наоборот, не встретить её при большом. Чтобы снизить шум, элементы разбивают на независимые группы, и каждая группа ведёт свой подсчёт.

От интуиции к алгоритму

Вместо одного счётчика алгоритм использует m независимых регистров. Часть битов хеша определяет, в какой регистр попадёт элемент, оставшиеся биты используются для подсчёта ведущих нулей. Каждый регистр хранит максимальную длину серии ведущих нулей, которую он наблюдал.

Мини-пример с 4 регистрами (2 бита на выбор регистра). Пусть хеш-функция даёт 8-битные значения:

Элемент  Хеш       Регистр (первые 2 бита)  Остаток   Ведущих нулей
  A      00|110100  → R0                     110100    0
  B      01|010110  → R1                     010110    1
  C      10|100011  → R2                     100011    0
  D      00|001101  → R0                     001101    2
  E      11|000010  → R3                     000010    4
  F      01|000001  → R1                     000001    5

После обработки шести элементов регистры хранят максимумы: R0=2, R1=5, R2=0, R3=4. Гармоническое среднее (величина, обратная среднему арифметическому обратных значений) подавляет выбросы лучше, чем арифметическое: один регистр с аномально большим значением не перекосит всю оценку. Формула HyperLogLog использует гармоническое среднее этих максимумов с поправочным коэффициентом, чтобы дать финальную оценку кардинальности.

Четыре регистра — слишком мало для практической точности. Чем больше регистров, тем больше независимых наблюдений, тем точнее среднее, тем ниже ошибка. Redis масштабирует эту идею до 16 384 регистров.

Реализация в Redis

Redis использует 16 384 регистра (2^14). Первые 14 бит хеша определяют номер регистра, оставшиеся 50 бит — для подсчёта ведущих нулей. Каждый регистр занимает 6 бит (значения 0–63), итого: 16 384 × 6 / 8 = 12 288 байт ≈ 12 КБ. Добавлено 100 элементов или 100 миллионов — память одна и та же: 12 КБ.

При малом количестве элементов большинство регистров пустые, и полная 12-килобайтная структура расточительна. Redis использует две кодировки: sparse и dense. В sparse-режиме регистры хранятся в сжатом виде (RLE — run-length encoding, кодирование длин серий: последовательности одинаковых значений записываются как «значение × количество»), что занимает значительно меньше 12 КБ. По мере добавления элементов Redis автоматически переключается на dense-представление. Порог управляется параметром hll-sparse-max-bytes (по умолчанию 3000 байт).

Стандартная ошибка составляет 0.81%. Для 1 000 000 уникальных элементов в 68% случаев результат попадёт в диапазон примерно 991 900–1 008 100 (±1 стандартное отклонение). Иногда отклонение будет больше, но выходы за ±2% редки.

Внутри Redis хранит HyperLogLog как обычный String — а значит, к нему применимы GET/SET, он реплицируется и персистируется как любой другой ключ. Префикс PF в командах — дань уважения Philippe Flajolet, автору алгоритма.

Команды

PFADD visitors "user:1" "user:2" "user:3"    -- добавить элементы
PFADD visitors "user:1"                       -- дубликат не меняет оценку
PFCOUNT visitors                              -- → 3 (приблизительно)
 
-- объединение нескольких HLL (например, за разные дни)
PFADD visitors:2025-01-15 "user:1" "user:4"
PFADD visitors:2025-01-16 "user:2" "user:5"
PFMERGE visitors:total visitors:2025-01-15 visitors:2025-01-16
PFCOUNT visitors:total                        -- уникальные за оба дня

PFADD возвращает 1, если внутреннее представление изменилось (вероятно, новый элемент), и 0, если нет. PFCOUNT для одного ключа — O(1), для нескольких ключей Redis сначала выполняет merge.

Когда HyperLogLog оправдан

Основная территория HyperLogLog — массовые счётчики уникальных, где точность до элемента не нужна. Типичный пример: веб-аналитика считает уникальных посетителей на страницу в день, а PFMERGE агрегирует дневные HLL в недельные и месячные без потери уникальности (объединение двух HLL — то же самое, что если бы все элементы добавлялись в один). Сетевой мониторинг с тысячами счётчиков уникальных IP в минуту — ещё один сценарий, где 12 КБ на счётчик вместо мегабайтов на SET делают задачу выполнимой.

HyperLogLog не подходит, если нужен ответ на вопрос «был ли конкретный элемент» — для этого есть Bitmap или SET. Если кардинальность невелика (до нескольких тысяч) и важен точный результат, SET проще и даёт точный ответ при сопоставимом расходе памяти.

См. также

• Уникальные посетители на HyperLogLog в Rails — PFADD, PFMERGE, дневные и недельные агрегаты

Sources

• Redis Documentation: HyperLogLog. https://redis.io/docs/data-types/hyperloglogs/
• Philippe Flajolet et al., «HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm», 2007
• Redis source: src/hyperloglog.c

---

← Stream | Bitmap и Bitfield →