HyperLogLog: Как считать уникальные значения в терабайтах данных без их хранения

Представьте себе сервис с высокой нагрузкой, который обрабатывает поток данных, таких как логи, IP-адреса и идентификаторы пользователей, генерируя миллиарды записей ежедневно. Задача заключается в том, чтобы определить количество уникальных посетителей за неделю. Первоначальный подход может заключаться в использовании HashSet для хранения этих ключей и проверки размера в конце. Хотя этот метод кажется разумным, он быстро становится непрактичным при миллиардах записей из-за ограничений памяти. Каждый IP-адрес, требующий 4 байта, влечет за собой значительные накладные расходы на узлы, указатели и хеши, что приводит к потреблению памяти не менее 50-100 байт на элемент. Таким образом, отслеживание миллиарда уникальных записей может потребовать почти ста гигабайт оперативной памяти, что дорого и неосуществимо при наличии нескольких инстансов. Однако существует алгоритм, который способен решить эту задачу, используя примерно 1,5 килобайта памяти с погрешностью около 2%, избегая необходимости хранить сами данные или поддерживать большие кластеры. Именно здесь на помощь приходит HyperLogLog, статистический алгоритм, который революционизирует подход к подсчету уникальных элементов в Big Data. HyperLogLog используется в таких платформах, как Redis, BigQuery, ClickHouse и Presto. В этой статье мы рассмотрим, как работает этот алгоритм, его реализацию на C и его исторический контекст.