Проверка на уникальность в больших данных с HyperLogLog
В современном мире разработки каждый проект собирает аналитику. На основе данных можно лучше понимать пользователей и их потребности. Одна из часто встречающихся задач в этой сфере — подсчет уникальных посещений веб-страниц.
Представим, что разрабатывается популярный медиаресурс. Посещаемость веб-сайта примерно равна 500 млн. уникальных посетителей в сутки. Перед нами стоит задача: кэшировать количество посещений каждой страницы с возможностью быстрой записи/чтения и получения общей статистики по нескольким страницам. Каждое уникальное посещение определяется IP адресом.
Redis Sets
Для начала можно использовать встроенную в Redis структуру данных Sets. Sets хранят набор уникальных значений, а также имеют функции для подсчета пересечений.
Кажется, что структура данных Sets хорошо подходит под задачу и полностью ее решает. Но это не совсем так. Redis Sets решает задачу подсчета уникальных посетителей на маленьких и средних сайтах. С учетом того, что в задаче указано 500 млн. посещений в сутки, ресурс нагруженный. Чтобы хранить все эти данные в Sets, потребуется много оперативной памяти. Также время чтения будет высоким, потому что при подсчете пересечений Redis придется перебирать сотни миллионов значений.
Redis HyperLogLog
В Redis есть структура данных HyperLogLog для хранения огромного количества уникальных событий, которая занимает постоянный объем памяти. HyperLogLog — это вероятностная структура, что означает, при большом наборе данных подсчет количества элементов может иметь ошибку до 0.81%. Например, подсчет 10 миллионов событий может иметь погрешность до 81 тыс. Допустимость такой ошибки зависит от проекта.
HyperLogLog подходит только для подсчета количества событий и их пересечений.
Запись
Для записи данных в HyperLogLog используется команда pfadd key [element [element ...]]
:
При успешной записи новых значений возвращается 1
. Если попытаться вставить существующее значение, то вернется 0
:
Чтение
Чтобы получить количество уникальных посетителей, используется команда pfcount key [key ...]
:
Рассчитать количество уникальных посетителей нескольких страниц можно командой pfmerge destkey sourcekey [sourcekey ...]
:
Команда pfmerge
сливает несколько HyperLogLog ключей в один. В примере выше результат сохранился в ключе articles
.
Резюме
Redis Sets подходит для подсчета уникальных событий, но не используется при большом количестве данных
Redis HyperLogLog — вероятностная структура данных, которая эффективно хранит и читает большое количество уникальных событий
для добавления данных в HyperLogLog используется команда
pfadd
подсчет событий в HyperLogLog осуществляется командой
pfcount
слить несколько HyperLogLog структур в одну можно с помощью команды
pfmerge
Дополнительные материалы
Вопросы для самопроверки
С помощью какого метода можно подсчитать количество уникальных значений в нескольких HyperLogLog ключах Redis?
выполнить
pfcount
, перечисляя все ключив Redis нет такой возможности
слить все ключи в один с помощью команды
pfmerge
и выполнитьpfcount
В ключе /users
хранится структура HyperLogLog. В структуру было добавлен 1 миллион уникальных значений. При выполнении команды pfcount
, возвращается значение 1 000 005. Выберите верный ответ, объясняющий, почему так происходит?
в структуру действительно было добавлено 1 000 005 уникальных значений
ошибка в Redis. Нужно перезагрузить сервер или обновиться до последней версии
HyperLogLog — вероятностная структура. Отклонение до 0.81% допустимо
Допишите команду добавления трех IP-адресов в ключ visitors:ip
, используя Redis HyperLogLog
___ visitors:ip 4.218.89.25 255.194.94.209 81.64.119.92
Допишите команду получения количества уникальных IP-адресов в ключе visitors:ip
, используя Redis HyperLogLog
___ visitors:ip