Count-Min Sketch: как посчитать частоту миллиарда событий в 10 килобайт
Представьте: через ваш сервер проходит 10 миллионов запросов в минуту. Каждый запрос содержит метку (например, ID пользователя, IP-адрес или поисковый запрос). Руководство просит: «А давайте посмотрим, кто из пользователей самый активный?». Задача выглядит простой, пока вы не осознаете, что хранить HashMap из 10 миллионов ключей в оперативной памяти — это сотни мегабайт, а если ключи — длинные строки, то и гигабайты.Вероятностные структуры данных решают такие задачи без гигантских кластеров. В прошлых статьях мы разобрали, как с помощью HyperLogLog считать количество уникальных элементов, а с помощью Фильтра Блума — проверять наличие элемента. Сегодня мы закроем триаду и поговорим об алгоритме, который отвечает на вопрос «А сколько раз этот элемент встречался?» с фиксированной памятью в пару килобайт и строгой вероятностной гарантией.И это — Count-Min Sketch! Структура, которая лежит в основе анализа потоков в базах данных (от ClickHouse до BigQuery) и сетевых протоколов. Мы разберем её математику, реализуем на чистом C с использованием MurmurHash3 и проведем бенчмарки. Читать далее