Перейти к содержанию

Проверка на уникальность в больших данных с HyperLogLog

В современном мире разработки каждый проект собирает аналитику. На основе данных можно лучше понимать пользователей и их потребности. Одна из часто встречающихся задач в этой сфере — подсчет уникальных посещений веб-страниц.

Представим, что разрабатывается популярный медиаресурс. Посещаемость веб-сайта примерно равна 500 млн. уникальных посетителей в сутки. Перед нами стоит задача: кэшировать количество посещений каждой страницы с возможностью быстрой записи/чтения и получения общей статистики по нескольким страницам. Каждое уникальное посещение определяется IP адресом.

IP

Redis Sets

Для начала можно использовать встроенную в Redis структуру данных Sets. Sets хранят набор уникальных значений, а также имеют функции для подсчета пересечений.

127.0.0.1:6379> sadd article:1 220.6.122.77 35.64.194.82 38.175.235.3
(integer) 3
127.0.0.1:6379> sadd article:2 220.6.122.77 140.45.246.108
(integer) 2
127.0.0.1:6379> sinter article:1 article:2
1) "220.6.122.77"

Кажется, что структура данных Sets хорошо подходит под задачу и полностью ее решает. Но это не совсем так. Redis Sets решает задачу подсчета уникальных посетителей на маленьких и средних сайтах. С учетом того, что в задаче указано 500 млн. посещений в сутки, ресурс нагруженный. Чтобы хранить все эти данные в Sets, потребуется много оперативной памяти. Также время чтения будет высоким, потому что при подсчете пересечений Redis придется перебирать сотни миллионов значений.

Redis HyperLogLog

В Redis есть структура данных HyperLogLog для хранения огромного количества уникальных событий, которая занимает постоянный объем памяти. HyperLogLog — это вероятностная структура, что означает, при большом наборе данных подсчет количества элементов может иметь ошибку до 0.81%. Например, подсчет 10 миллионов событий может иметь погрешность до 81 тыс. Допустимость такой ошибки зависит от проекта.

HyperLogLog подходит только для подсчета количества событий и их пересечений.

Запись

Для записи данных в HyperLogLog используется команда pfadd key [element [element ...]]:

127.0.0.1:6379> pfadd article:1 4.218.89.25 255.194.94.209 81.64.119.92 226.110.217.208 68.199.143.222
(integer) 1
127.0.0.1:6379> pfadd article:2 14.193.144.176 132.231.108.228 81.64.119.92 226.110.217.208 68.199.143.222
(integer) 1
127.0.0.1:6379> pfadd article:3 4.218.89.25 255.194.94.209 81.64.119.92 225.109.160.131 85.83.185.103
(integer) 1

При успешной записи новых значений возвращается 1. Если попытаться вставить существующее значение, то вернется 0:

127.0.0.1:6379> pfadd article:1 4.218.89.25
(integer) 0

Чтение

Чтобы получить количество уникальных посетителей, используется команда pfcount key [key ...]:

127.0.0.1:6379> pfcount article:1
(integer) 5
127.0.0.1:6379> pfcount article:2
(integer) 5
127.0.0.1:6379> pfcount article:3
(integer) 5

Рассчитать количество уникальных посетителей нескольких страниц можно командой pfmerge destkey sourcekey [sourcekey ...]:

127.0.0.1:6379> pfmerge articles article:1 article:2 article:3
OK
127.0.0.1:6379> pfcount articles
(integer) 9

Команда 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