Подсчитать 100 миллионов уникальных посетителей сайта можно, потратив всего 12 КБ памяти. Для сравнения, обычному счётчику, который сохраняет идентификаторы каждого пользователя, потребовались бы сотни мегабайт. Справиться с огромной разницей помогает алгоритм HyperLogLog, который оценивает количество людей с помощью вероятностей и редких комбинаций нулей и единиц. Причём разобраться в его работе можно с помощью обычной монетки.
Представим крупный новостной сайт, который ежедневно посещают миллионы человек. Один читатель открывает десять статей, другой возвращается несколько раз за день, третий обновляет страницу каждые пять минут. Система аналитики должна понять, сколько разных людей пришло на сайт, и не посчитать повторные визиты за новых посетителей. Самый очевидный способ требует хранить идентификаторы пользователей и проверять каждое новое посещение по огромному списку. Но чем больше аудитория, тем больше памяти приходится выделять.
Математики нашли неожиданное решение. Вместо хранения всех идентификаторов можно запоминать редкие события и по их частоте оценивать общее количество участников. В основе математического трюка лежит простая закономерность, которую легко проверить, подбрасывая монету.
Вероятность выбросить орла при одном броске составляет 50%. Получить двух орлов подряд сложнее, вероятность падает до 25%. Три орла подряд выпадают с вероятностью 12,5%, а десять в начале серии бросков встречаются в среднем лишь в одном случае из 1024. С каждой дополнительной монеткой, которая выпадает нужной стороной, комбинация становится вдвое реже.
Теперь представим человека, который много раз подбрасывает монету и записывает самую длинную серию орлов, выпавшую с самого начала очередной попытки. Если рекорд достиг десяти, можно предположить, что участник провёл около тысячи попыток. Конечно, необычная комбинация могла выпасть намного раньше или позже. Но длина рекордной серии уже позволяет приблизительно оценить количество бросков, даже если никто не вёл их точный подсчёт.
HyperLogLog применяет похожий принцип к цифровым данным. Только вместо монеты компьютер использует нули и единицы. Каждый пользовательский идентификатор программа пропускает через хеш-функцию, которая преобразует исходную информацию в последовательность битов фиксированной длины. Хорошая хеш-функция распределяет полученные значения достаточно равномерно, поэтому отдельные биты можно рассматривать как случайные.
Дальше программа ищет, сколько нулей подряд стоит в начале определённой части последовательности. Десять нулей встречаются примерно один раз на тысячу случайных значений, двадцать нулей ещё реже, приблизительно один раз на миллион. Чем длиннее обнаруженная серия, тем больше уникальных идентификаторов, вероятно, обработала система.
Есть и важная особенность. Если один посетитель открывает сайт двадцать раз, хеш-функция каждый раз выдаёт одинаковый результат для одного и того же идентификатора. Повторные обращения не увеличивают рекордную последовательность нулей. Поэтому счётчик может оценивать количество уникальных пользователей, не сохраняя полный список посещений.
Правда, опираться на единственный рекорд опасно. Двадцать нулей подряд могут случайно встретиться даже среди небольшого количества значений, и программа сильно завысит оценку. Чтобы уменьшить влияние удачи, HyperLogLog распределяет поступающие идентификаторы между множеством групп. В каждой группе алгоритм запоминает максимальную длину серии нулей, а затем объединяет результаты с помощью математической формулы. Расчёт учитывает показатели всех групп и ослабляет влияние слишком больших рекордов.
Экономия памяти получается впечатляющей. Например, реализация HyperLogLog в Redis использует 16 384 небольших регистра, которые занимают около 12 КБ. Даже если счётчик обработает миллиард уникальных значений, ему не придётся выделять память под миллиард записей. Согласно документации Redis, стандартная относительная ошибка составляет примерно 0,81%. Отдельный подсчёт может ошибиться сильнее, но для многих аналитических задач средней точности вполне достаточно.
Для сравнения, если хранить 100 миллионов идентификаторов размером по восемь байт, только сами значения займут 800 МБ. Дополнительная память потребуется для быстрого поиска и проверки повторений. HyperLogLog обходится несколькими килобайтами, поскольку запоминает лишь небольшую статистическую сводку.
Алгоритм пригодился и для объединения статистики. Допустим, крупный сайт обслуживают десятки серверов. Каждый сервер самостоятельно подсчитывает аудиторию, а затем система объединяет результаты, не собирая огромную общую базу идентификаторов. Аналогично можно вычислить приблизительное количество посетителей за неделю по отдельным дневным счётчикам, не суммируя одних и тех же людей несколько раз.
HyperLogLog уже давно работает в популярных сервисах. Google использует HyperLogLog++, улучшенную версию алгоритма, в Google Analytics 4 для оценки количества пользователей и сеансов. Поэтому некоторые показатели аудитории в аналитике Google могут немного отличаться от точных значений. Похожий подход подходит для подсчёта уникальных поисковых запросов, анализа огромных потоков сетевых событий и оценки количества разных адресов, которые обращаются к серверу.
Сам алгоритм представили в 2007 году. Математики Филипп Флажоле, Эрик Фюзи, Оливье Гандуе и Фредерик Менье показали, что можно оценивать количество элементов даже в наборах, превышающих миллиард записей, с типичной погрешностью около 2%, используя всего 1,5 КБ памяти. Позднее разработчики других систем улучшили точность и приспособили метод для обработки огромных потоков информации.
У HyperLogLog есть ограничения. Алгоритм не позволяет узнать, кто именно посещал сайт, восстановить список пользователей или гарантированно получить точное число. Кроме того, один человек может попасть в статистику несколько раз, если сайт выдаёт разные идентификаторы его устройствам или браузерам. Но когда нужно быстро оценить аудиторию в десятки миллионов человек, небольшая погрешность часто оказывается приемлемой платой за колоссальную экономию ресурсов. Вместо хранения огромной базы компьютер запоминает несколько тысяч чисел и по редким цепочкам нулей восстанавливает приблизительный масштаб потока.
