Самый наивный подход к подсчёту частот — завести хеш-таблицу: ключ — элемент, значение — счётчик. Пришёл запрос — инкрементировали. В конце работы выгрузили топ. Это работает ровно до тех пор, пока множество уникальных ключей умещается в оперативной памяти.

Как только мы выходим за пределы сотен мегабайт или говорим о потоке, который идёт бесконечно, хеш-таблица перестаёт быть решением, ибо в ней надо хранить сами ключи. Каждый уникальный IP (4 байта) превращается в 50–100 байт из-за оверхеда структур данных и выравнивания. Если ключ — это URL длиной 100 байт, и таких URL миллионы, — память улетает в гигабайты.

В офлайне вы можете запустить MapReduce, распараллелить, подождать немного и получить точный результат. Но, увы, в реальном времени это не работает. Никто не будет ждать час, чтобы узнать, какие сейчас самые активные пользователи.

Предыдущие статьи этой серии решали похожие проблемы — для проверки наличия элемента и для подсчёта уникальности. HyperLogLog отвечает на вопрос «сколько уникальных элементов мы видели?» и не говорит ничего про частоты. Фильтр Блума говорит «есть / нет», но не умеет считать.

Сегодня мы добавим в этот набор ещё один инструмент, который делает ровно то, что нужно для потоковых частот: фиксированная память, константное время на операцию и строгая вероятностная гарантия — Count-Min Sketch.

❯ Предыстория и эволюция

Count-Min Sketch — это творение Грэма Кормода и С. Мутхакришнана, созданное в 2005 году. Работа называлась «An improved data stream summary: the count-min sketch and its applications» и вышла в Journal of Algorithms.

К тому времени уже существовали алгоритмы для работы с потоковыми данными, например Lossy Counting или алгоритм Флажоле-Мартина, но все они либо требовали слишком много памяти, либо не давали гарантий с заданной точностью. Кормод и Мутхакришнан предложили структуру, которая умеет одновременно три вещи: работает с фиксированным объёмом памяти, даёт контролируемую ошибку и выполняется за константное время на одну операцию.

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

Кроме того, CMS легко распараллеливается. Если у вас есть несколько потоков данных, вы можете держать отдельную структуру для каждого потока, а в конце просто поэлементно сложить массивы счётчиков (или взять минимум для каждого регистра, если архитектура позволяет). Это свойство — именно то, что требуется в распределённых системах мониторинга и в агрегаторах метрик вроде Prometheus или ClickHouse.

❯ Математика

И настало время математики, чтобы понять, как и почему алгоритм работает именно так. Почему, скажем, для ошибки в 1% нам нужно ровно 272 столбца, а не 200 и не 500? И почему глубина в 7 строк даёт вероятность ошибки меньше одного процента?

Сначала — как устроен сам массив. Это двумерная таблица из d строк и w столбцов. Все ячейки инициализируются нулями. Для каждого элемента мы считаем d разных хешей — по одному на каждую строку. Каждый хеш возвращает номер столбца от 0 до w-1. Мы берём и инкрементируем все эти d ячеек. Вот и вся вставка.

А теперь вопрос к вам: как вы думаете, почему мы берём минимум, а не максимум или среднее? Если вы подумали «потому что каждая ячейка завышает значение» — вы абсолютно правы.

Мы снова вычисляем те же d хешей, смотрим на значения в соответствующих ячейках и берём из них минимальное. Это не просто так — за этим стоит простая, но строгая логика.

Каждая отдельная ячейка хранит сумму всех вставок, которые попали в этот столбец через конкретную хеш-функцию. Она включает наш элемент плюс все остальные, которые дали коллизию по этой хеш-функции. Поэтому значение в ячейке всегда больше или равно реальной частоте нашего элемента. Мы не можем недооценить счётчик — только переоценить.

Теперь берём минимум по всем d строкам. Почему минимум? Потому что каждая строка даёт завышенную оценку, но с разными «шумами» из-за разных хеш-функций. Чем больше строк, тем выше шанс, что хотя бы одна из них не слишком сильно пострадала от коллизий. Минимум — это наиболее осторожная оценка сверху среди всех завышенных.

Дальше начинается чистая математика. Нам нужно выбрать w и d так, чтобы контролировать точность и надёжность.

Ширина таблицы w отвечает за точность. Чем больше столбцов, тем меньше элементов попадает в одну ячейку, и тем точнее оценка. Формула для w выводится из неравенства Маркова:

Здесь e — число Эйлера (примерно 2.718), а ε — допустимая относительная ошибка. Если мы хотим ошибку не более 1% (ε = 0.01), то получаем w ≈ 272. Если допускаем 5% — хватит 55 столбцов. Откуда берётся e? Это следствие из оптимизации границы для суммы индикаторов коллизий. Длинный вывод в оригинальной статье, но итог простой и красивый.

Глубина d отвечает за вероятность того, что ошибка превысит допустимый порог. Она логарифмическая:

Где δ — вероятность неудачи. Если мы хотим, чтобы ошибка превысила ε * N с вероятностью не более 5% (δ = 0.05), то d = 3. Для 1% (δ = 0.01) нужно d = 5. Для 0.1% — d = 7. Логарифм — это жёсткая зависимость: десять строк дают уже 0.0045%, дальше улучшение нивелируется ростом памяти.

Теперь главная теорема, которая соединяет эти две величины:

С вероятностью не менее 1 — δ, оценка частоты f_hat(x) для любого элемента x удовлетворяет неравенству:

Где N — общее число всех вставленных элементов. Но! Абсолютная ошибка растёт линейно с ростом N. Если через систему прошло миллиард событий, а ε = 0.01, то мы можем ошибиться на 10 миллионов. Звучит страшно, но это относительная ошибка в 1%. Для потоковых данных это приемлемо — нас обычно интересуют не абсолютные числа, а относительные сравнения. Кстати, я сам удивился поначалу, но это суть вероятностных алгоритмов — ценой точности мы получаем скорость.

На практике это означает, что при N = 10^9 и ε = 0.01 мы имеем массив размером 272×7 = 1904 ячейки. Если каждая ячейка — 4-байтовый счётчик (int32), это примерно 7.6 килобайт. Если же мы переживаем за переполнение счётчика (максимум 2 миллиарда для int32), то берём 8 байт — получаем 15 килобайт. Сравните с гигабайтами для хеш-таблицы.

Что ещё важно — формула с ε * N работает для любых элементов, независимо от распределения. Теорема не предполагает, что данные хорошо перемешаны или что хеш-функции идеальны — достаточно, чтобы они были попарно независимы. На практике MurmurHash3 и его собратья подходят отлично, хотя строгой статистической независимости не дают. Но для реальных данных этого хватает.

И последний нюанс. В формулах фигурирует N — общее количество вставок. Если поток бесконечен, N растёт, а с ним и абсолютная ошибка. В продакшене это решают либо сбрасыванием счётчиков (sliding window), либо использованием экспоненциального затухания. Но это уже совсем другая история и тема для другой статьи.

Вот теперь, когда у нас есть формулы, мы можем осмысленно выбирать параметры, с пониманием, во что нам обходится каждый лишний столбец и каждая дополнительная строка.

❯ Реализация на C

Перейдём, наконец, к коду! Полная реализация и весь код, включая бенчмарки, доступны по ссылке в моём репозитории.

Структура CMS умещается в четыре поля:

typedef struct {
    uint64_t width;
    uint64_t depth;
    uint64_t total_count;
    uint64_t *counters;
} CMS;

width и depth — те самые параметры из математики. total_count хранит общее число добавленных элементов (N из формулы ошибки). counters — одномерный массив размером depth * width, где ячейка с индексом d * width + w соответствует строке d и столбцу w.

Я выбрал одномерный массив вместо двумерного по двум причинам. Во-первых, это проще для аллокации: один вызов calloc вместо depth вызовов. Во-вторых, данные лежат непрерывно, что даёт лучшую локальность при последовательном обходе в cms_reset.

Счётчики — uint64_t, хотя теоретически 32 бита хватило бы для большинства задач (2 миллиарда вставок). Но переполнение 32-битного счётчика при интенсивном потоке — реальная угроза. 64 бита дают запас до 1.8e19, и плата за это — всего 8 байт на ячейку вместо 4. Для структуры размером 10–100 КБ разница не критична.

Хеш-функция

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

static uint64_t hash_murmur3_64(const uint8_t *key, size_t len, uint64_t seed);

В реализации используется 64-битный вариант с двумя независимыми регистрами (h1 и h2), которые обрабатывают входные данные блоками по 16 байт. В конце вызывается fmix64 — финальное перемешивание, которое убивает любые статистические артефакты. Полный код хеш-функции я вынес под спойлер — он стандартный, и вы можете найти его в любом репозитории с MurmurHash3.

static uint64_t hash_murmur3_64(const uint8_t *key, size_t len, uint64_t seed) {
    const uint8_t *data = key;
    size_t nblocks = len / 8;
    uint64_t h1 = seed ^ 0x6a09e667f3bcc908ULL;
    uint64_t h2 = seed ^ 0xbb67ae8584caa73bULL;
    const uint64_t c1 = 0x87c37b91114253d5ULL;
    const uint64_t c2 = 0x4cf5ad432745937fULL;
    const uint64_t *blocks = (const uint64_t *)data;

    for (size_t i = 0; i < nblocks; i++) {
        uint64_t k1 = blocks[i * 2];
        uint64_t k2 = blocks[i * 2 + 1];
        k1 *= c1;
        k1 = (k1 << 31) | (k1 >> 33);
        k1 *= c2;
        h1 ^= k1;
        h1 = (h1 << 27) | (h1 >> 37);
        h1 += h2;
        h1 = h1 * 5 + 0x52dce729;
        k2 *= c2;
        k2 = (k2 << 33) | (k2 >> 31);
        k2 *= c1;
        h2 ^= k2;
        h2 = (h2 << 31) | (h2 >> 33);
        h2 += h1;
        h2 = h2 * 5 + 0x38495ab5;
    }

    const uint8_t *tail = data + nblocks * 16;
    uint64_t k1 = 0, k2 = 0;
    switch (len & 15) {
        case 15: k2 ^= (uint64_t)tail[14] << 48;
        case 14: k2 ^= (uint64_t)tail[13] << 40;
        case 13: k2 ^= (uint64_t)tail[12] << 32;
        case 12: k2 ^= (uint64_t)tail[11] << 24;
        case 11: k2 ^= (uint64_t)tail[10] << 16;
        case 10: k2 ^= (uint64_t)tail[9] << 8;
        case 9:  k2 ^= (uint64_t)tail[8];
                 k2 *= c2;
                 k2 = (k2 << 33) | (k2 >> 31);
                 k2 *= c1;
                 h2 ^= k2;
        case 8:  k1 ^= (uint64_t)tail[7] << 56;
        case 7:  k1 ^= (uint64_t)tail[6] << 48;
        case 6:  k1 ^= (uint64_t)tail[5] << 40;
        case 5:  k1 ^= (uint64_t)tail[4] << 32;
        case 4:  k1 ^= (uint64_t)tail[3] << 24;
        case 3:  k1 ^= (uint64_t)tail[2] << 16;
        case 2:  k1 ^= (uint64_t)tail[1] << 8;
        case 1:  k1 ^= (uint64_t)tail[0];
                 k1 *= c1;
                 k1 = (k1 << 31) | (k1 >> 33);
                 k1 *= c2;
                 h1 ^= k1;
    }

    h1 ^= len;
    h2 ^= len;
    h1 += h2;
    h2 += h1;

    h1 ^= h1 >> 33;
    h1 *= 0xff51afd7ed558ccdULL;
    h1 ^= h1 >> 33;
    h1 *= 0xc4ceb9fe1a85ec53ULL;
    h1 ^= h1 >> 33;

    h2 ^= h2 >> 33;
    h2 *= 0xff51afd7ed558ccdULL;
    h2 ^= h2 >> 33;
    h2 *= 0xc4ceb9fe1a85ec53ULL;
    h2 ^= h2 >> 33;

    return h1 + h2;
}

Создание и удаление

cms_create выделяет память под структуру и массив счётчиков:

CMS* cms_create(uint64_t width, uint64_t depth) {
    if (width == 0 || depth == 0) return NULL;

    CMS *cms = malloc(sizeof(CMS));
    if (!cms) return NULL;

    cms->width = width;
    cms->depth = depth;
    cms->total_count = 0;

    cms->counters = calloc(depth * width, sizeof(uint64_t));
    if (!cms->counters) {
        free(cms);
        return NULL;
    }

    return cms;
}

Функция cms_create_with_epsilon_delta — удобная обёртка. Она принимает те самые ε и δ из математики и сама вычисляет размеры таблицы:

CMS* cms_create_with_epsilon_delta(double epsilon, double delta) {
    if (epsilon <= 0.0 || epsilon >= 1.0) return NULL;
    if (delta <= 0.0 || delta >= 1.0) return NULL;

    double e = 2.718281828459045;
    uint64_t width = (uint64_t)ceil(e / epsilon);
    uint64_t depth = (uint64_t)ceil(log(1.0 / delta));

    return cms_create(width, depth);
}

Для освобождения памяти — cms_destroy. Ничего необычного: освобождаем массив счётчиков, затем структуру.

Добавление элемента

Функция добавления тоже относительно простая, использует функцию хеширования:

void cms_add(CMS *cms, const uint8_t *key, size_t key_len, uint64_t delta) {
    if (!cms || !key || key_len == 0 || delta == 0) return;

    for (uint64_t d = 0; d < cms->depth; d++) {
        uint64_t seed = 0x6a09e667f3bcc908ULL + d * 0x9e3779b97f4a7c15ULL;
        uint64_t hash = hash_murmur3_64(key, key_len, seed);
        uint64_t idx = hash % cms->width;
        cms->counters[d * cms->width + idx] += delta;
    }

    cms->total_count += delta;
}

Для каждой строки мы вычисляем отдельный хеш, используя свою соль (seed). Соль вычисляется просто: берём константу и прибавляем номер строки, умноженный на золотое сечение. Это даёт достаточно независимые хеши на практике.

Обратите внимание: мы не проверяем переполнение счётчика. При uint64_t и реалистичных нагрузках это не проблема.

Запрос частоты

Вычисляем те же хеши, берём минимум:

uint64_t cms_query(CMS *cms, const uint8_t *key, size_t key_len) {
    if (!cms || !key || key_len == 0) return 0;

    uint64_t min_val = UINT64_MAX;

    for (uint64_t d = 0; d < cms->depth; d++) {
        uint64_t seed = 0x6a09e667f3bcc908ULL + d * 0x9e3779b97f4a7c15ULL;
        uint64_t hash = hash_murmur3_64(key, key_len, seed);
        uint64_t idx = hash % cms->width;
        uint64_t val = cms->counters[d * cms->width + idx];
        if (val < min_val) {
            min_val = val;
        }
    }

    return min_val;
}

Если элемент никогда не добавлялся, все ячейки будут нулевыми, функция вернёт 0. Если добавлялся — каждая ячейка хранит его частоту плюс «шум» от коллизий, поэтому минимум даёт наиболее точную оценку.

Дополнительные функции

Для удобства я добавил несколько вспомогательных функций:

void cms_reset(CMS *cms) {
    if (!cms) return;
    memset(cms->counters, 0, cms->depth * cms->width * sizeof(uint64_t));
    cms->total_count = 0;
}

uint64_t cms_total_count(CMS *cms) {
    return cms ? cms->total_count : 0;
}

double cms_epsilon(CMS *cms) {
    if (!cms || cms->width == 0) return 0.0;
    return 2.718281828459045 / (double)cms->width;
}

double cms_delta(CMS *cms) {
    if (!cms) return 0.0;
    return exp(-(double)cms->depth);
}

size_t cms_memory_usage(CMS *cms) {
    if (!cms) return 0;
    return sizeof(CMS) + cms->depth * cms->width * sizeof(uint64_t);
}

cms_reset обнуляет все счётчики, не освобождая память — удобно для переиспользования структуры. cms_epsilon и cms_delta возвращают теоретические параметры точности для текущей конфигурации. cms_memory_usage — сколько байт занимает структура вместе с данными.

❯ Бенчмарки и тестирование

Теория — это хорошо, но я хотел убедиться, что реализация действительно даёт ошибку в заявленных пределах, и заодно провести бенчмарки. Я написал бенчмарк, который генерирует N элементов, распределённых по U уникальным ключам, добавляет их в CMS, а затем сравнивает оценки с точными значениями.

Схема тестирования выглядит так:

1. Генерируем U уникальных ключей (длина key_len байт).

2. Создаём массив true_counts[U] для точного подсчёта.

3. В цикле N раз выбираем ключ (равномерно или по Zipf) и вызываем cms_add, инкрементируя true_counts.

4. После добавления всех элементов проходим по всем U ключам, для каждого вызываем cms_query и считаем ошибку относительно true_counts.

static void generate_key(uint8_t *key, size_t len, uint64_t seed, uint64_t idx) {
    uint64_t state = idx ^ seed;
    for (size_t i = 0; i < len; i += 8) {
        uint64_t val = hash_murmur3_64((uint8_t*)&state, sizeof(state),
                                       0x9e3779b97f4a7c15ULL + i);
        size_t copy = (len - i < 8) ? (len - i) : 8;
        memcpy(key + i, &val, copy);
    }
}

Кстати, о генерации ключей. В первой версии бенчмарка я использовал упрощённый подход:

static void generate_key(uint8_t *key, size_t len, uint64_t seed, uint64_t idx) {
    uint64_t h = seed ^ idx;
    h ^= h >> 33;
    h *= 0xff51afd7ed558ccdULL;
    h ^= h >> 33;
    h *= 0xc4ceb9fe1a85ec53ULL;
    h ^= h >> 33;
    for (size_t i = 0; i < len; i++) {
        key[i] = (uint8_t)((h >> (i * 8 % 64)) ^ (h >> ((i + 7) * 8 % 64)));
    }
}

Проблема заключалась в том, что при key_len = 32 байта реальная энтропия всего 64 бита, байты повторяются и коррелируют. Это давало аномально низкую ошибку — CMS казался идеальным, потому что коллизии хешей были реже, чем в реальных данных. Я сначала думал, повезло, моя реализация сверхточная и обогнала гипотетическую ошибку! Вроде бы маленькая ошибка — это же хорошо. А оказалось нет, это проблема тестовых данных.

После я поменял на хеш-алгоритм MurmurHash3 (вкупе с использованием настоящей хеш-функции в самом CMS), который решил главную проблему первых тестов — неестественное поведение ошибок на больших объёмах данных.

Зависимость ошибки от ε

Первый график проверяет главную формулу: ошибка должна быть не больше ε * N. Я зафиксировал N = 100000, δ = 0.01 (глубина 5) и менял ε от 0.1 до 0.001.

На графике видно, что средняя ошибка действительно не превышает ε * N. Для ε = 0.01 (ширина 272) ошибка ~900 элементов при N = 100000 — меньше теоретической границы в 1000. Для ε = 0.001 (ширина 2718) ошибка падает до ~80. Зависимость обратно пропорциональная, как и предсказывает формула. Время выполнения растёт линейно с шириной таблицы — больше столбцов = больше памяти и чуть больше кэш-промахов.

Зависимость ошибки от δ

Второй график показывает, как глубина влияет на вероятность превышения порога. Я зафиксировал ε = 0.01 (ширина 272) и менял δ от 0.5 до 0.001 (глубина от 1 до 7).

При depth = 1 ошибка превышает ε * N в ~32% случаев — это соответствует δ ≈ 0.37 (теория даёт e^(-1) ≈ 0.37). При depth = 3 доля превышений падает до ~5% (δ = 0.05). При depth = 5 — около 1%. При depth = 7 — менее 0.1%. Зависимость действительно экспоненциальная. Средняя ошибка при этом почти не меняется — глубина влияет не на величину ошибки, а на вероятность того, что она окажется слишком большой.

Зависимость ошибки от N

Третий график показывает, как растёт абсолютная ошибка с увеличением N. Это критичный момент: многие ожидают, что ошибка будет константной, но это не так.

Абсолютная ошибка растёт линейно с N. Для ε = 0.01 при N = 10^4 ошибка ~100, при N = 10^6 — ~10000. Относительная ошибка при этом остаётся в пределах 1%. Теоретическая граница ε * N выполняется с запасом. Важно: время выполнения не зависит от N — структура фиксированного размера обрабатывает миллион элементов за те же 0.02 секунды, что и тысячу.

Memory trade-off

Последний график — практический. Он показывает, как точность зависит от затраченной памяти.

При 1.3 КБ (ε = 0.05, δ = 0.05) ошибка ~5000 на 100000 элементов. При 10 КБ (ε = 0.01, δ = 0.01) — ~900. При 100 КБ (ε = 0.001, δ = 0.01) — ~80. Увеличение памяти в 10 раз даёт улучшение точности примерно в 10 раз — обратно пропорциональная зависимость. На практике я выбираю конфигурацию исходя из задачи: для обнаружения аномалий хватает 1%, для точного ранжирования лучше взять 0.1%.

Распределение ошибки

Для полноты картины я прогнал один тест 30 раз с одинаковыми параметрами (N = 100000, ε = 0.01, δ = 0.01) и построил распределение ошибок.

Ошибка распределена асимметрично — есть длинный правый хвост. Это весьма логично, так как CMS всегда завышает оценки, но редко — сильно. В 95% случаев ошибка укладывается в 2× от средней. В худшем случае из 30 запусков ошибка достигла ~1800 при среднем значении 900.

Все графики построены по данным из репозитория. Полный набор сырых данных доступен в директории benchmarks. Бенчмарк можно запустить самому:

make
python3 -m venv .venv
source .venv/bin/activate
pip3 install -r requirements.txt
python3 benchmark.py

❯ Заключение

CMS — это та редкая структура данных, где математика, реализация и практическая применимость сходятся в одной точке. Всего три параметра (ширина, глубина и общее число элементов), а дают такой результат.

И он отлично дополняет другие вероятностные структуры: фильтр Блума (отвечающий на вопрос «было ли это уже?»), HyperLogLog (подсчёт уникальных элементов), а Count-Min Sketch даёт частоты. Всё это — магия вероятностей, крайне интересная часть математики. Подсчитывать частоты или уникальные элементы в огромном потоке данных, и всё это за крохи памяти и невероятно быстро.

Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩