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

Дата публикации: 24-06-2026 16:05:58

Представим задачу: хайлоад-сервис гонит поток данных — логи, IP-адреса, ID пользователей, миллиарды записей в сутки. Ваша задача — посчитать количество уникальных посетителей за неделю.Первым решением может показаться завести HashSet и кидать туда ключи, а в конце посмотреть размер. Решение неплохое, но когда речь заходит о миллиардах записей — память будет слабым местом. Один IP-адрес (4 байта) как ключ в HashSet потянет за собой накладные расходы на ноды, указатели и хеши. На практике один элемент сжирает не меньше 50–100 байт. Поток в миллиард уникальных записей потребует под сотню гигабайт оперативной памяти. Это дорого, а если инстансов десять — то просто нереально.Но существует алгоритм, который способен решить эту задачу примерно в 1.5 килобайта памяти с погрешностью около 2%? Без хранения самих данных и гигантских кластеров. Достаточно одного прохода по потоку и пары битовых трюков — именно так и работает HyperLogLog, алгоритм родом из математической статистики, который перевернул подход к подсчёту уникальности в Big Data.HyperLogLog используют в Redis, BigQuery, ClickHouse, Presto. В этой статье мы разберем и реализуем этот алгоритм на C, а также узнаем его предысторию. Читать далее

Схожие новости

#	Наименование новости	Тональность	Информативность	Дата публикации
1	HyperLogLog: как найти уникальные значения в терабайте данных, не храня их	0	7	24-06-2026
2	[Перевод] Структуры данных на практике. Глава 16: Фильтры Блума и вероятностные структуры данных	0	8	28-06-2026
3	[Перевод] Вы можете победить бинарный поиск	5	7	15-06-2026
4	[Перевод] Структуры данных на практике. Глава 16: Фильтры Блума и вероятностные структуры данных	0	7	28-06-2026
5	OpenPGM: зачем Бирже мультикаст?	0	5	05-06-2026
6	Самый недооцененный механизм безопасности SSH или почему known_hosts — это не кэш	5	7	07-07-2026
7	pg_stl: анализ временных рядов прямо в PostgreSQL, без выгрузки данных	5	7	01-06-2026
8	Тап по тысяче точек за O(log n): QuadTree и сферическая геометрия в гео-соцсети	0	7	28-06-2026
9	In-memory база врёт: 5 расхождений с продовой БД	0	7	07-07-2026
10	Почему JSON на практике — быстрый формат для баз данных (если выкинуть лишние абстракции)	5	7	07-07-2026

Классификация: Пресс-релизы. Схожих патентов: 0. Схожих новостей: 10. Тональность: 0. Информативность: 7. Источник: habr.com.