HyperLogLog: подсчёт уникальных приближённо

В прошлом уроке битовая карта считала посетителей за бит на человека, но требовала числовых id подряд. Теперь задача шире. Магазин хочет показать на странице книги «эту книгу смотрели 12 400 человек». Посетитель может быть без аккаунта, тогда вместо id у него случайная строка из cookie. Книг сто тысяч, и на каждую нужен свой счётчик уникальных посетителей. Множество из урока про множества посчитает точно, но съест гигабайты. Сегодня считаем почти точно за 12 КБ на счётчик.

Монетка и самая длинная серия

Представь, что друг подбрасывает монетку и рассказывает только одно: самую длинную серию орлов подряд, которая у него выпала. Если он говорит «два орла подряд», скорее всего, он бросил монетку несколько раз. Если «двадцать орлов подряд», он бросал очень долго: такая серия выпадает примерно раз на миллион попыток.

Ты не видел ни одного броска, но по одному числу примерно знаешь, сколько их было. Ошибиться можно: другу могло повезти. Поэтому попросим сотню друзей бросать каждого свою монетку и усредним их рассказы. Ошибка заметно уменьшится.

HyperLogLog работает так же. Каждый элемент превращается в хеш, похожий на серию случайных бросков монеты. Redis смотрит, сколько нулей идёт в хеше подряд, и запоминает самую длинную серию. «Друзей» у него 16 384: часть бит хеша выбирает, в какую ячейку записать результат. Каждая ячейка помнит только свою самую длинную серию, поэтому сами элементы нигде не хранятся.

Отсюда два свойства:

• Повтор ничего не меняет. Тот же элемент даёт тот же хеш и ту же серию. Посетитель, открывший страницу десять раз, посчитается один раз.
• Память постоянная. 16 384 ячейки по 6 бит это 12 КБ, сколько бы элементов ты ни добавил.

PFADD и PFCOUNT

Команды HyperLogLog начинаются с PF в честь Филиппа Флажоле, автора алгоритма. PFADD добавляет элементы. Ключ счётчика собираем из книги и дня:

127.0.0.1:6379> PFADD uv:book:1:2026-10-10 user:7 user:12 user:3
(integer) 1
127.0.0.1:6379> PFADD uv:book:1:2026-10-10 user:7
(integer) 0
127.0.0.1:6379> PFADD uv:book:1:2026-10-10 user:7 user:40
(integer) 1
127.0.0.1:6379> PFCOUNT uv:book:1:2026-10-10
(integer) 4

PFADD отвечает 1, если внутренние ячейки изменились, и 0, если нет. Повторный user:7 ничего не изменил. Это не «новый элемент или нет»: на больших объёмах новый элемент тоже может не сдвинуть ни одну ячейку, и PFADD ответит 0.

PFCOUNT возвращает оценку. На маленьких числах она точная: четыре разных пользователя, ответ 4.