count-min-sketch.js·5 scenarios
Count-Min Sketch concept page: probabilistic frequency estimation via d×w counter matrix and d hash functions, point query as min over rows (NEVER underestimates), top-K via min-heap, overestimate from collisions, real production deployments (Redis CMS/TOPK, Cisco NetFlow, Cloudflare, Datadog, Twitter algebird, Yahoo DataSketches).
Когда поток событий измеряется миллиардами в сутки, точное хранение Map<Key, count> для каждого уникального ключа превращается в гигабайты RAM, которые никто не хочет платить ради ответа на вопрос «сколько раз?». Count-Min Sketch (CMS) — структура, которая отвечает на этот вопрос за десятки килобайт памяти и единицы наносекунд на event, ценой контролируемой ошибки в одну сторону (всегда переоценивает, никогда не недооценивает).
Реальные места, где CMS зарабатывает себе место в проде:
Если ты строишь real-time analytics, observability или security — рано или поздно встретишь CMS под капотом готовой системы (Redis CMS.*, Datadog sketches, Twitter algebird, Apache DataSketches). Понимание, что внутри, отделяет «использовал, потому что было в API» от «выбрал, потому что подходило по гарантиям».
CMS = матрица
d × wсчётчиков иdнезависимых hash-функций. На каждый event инкрементим ровноdячеек: по одной в каждой строке через свой hash. На запрос «сколько раз встречался X?» читаемdячеек и берём минимум — он отсекает большую часть коллизионного шума. Результат всегда>=истинной частоты, и с вероятностью>= 1 - δотстоит от неё не более чем наε · N, гдеN— суммарное количество всех events.
Два ключевых свойства, которые определяют всю физику CMS:
0 — ключа точно не было. Если ответ большой — может быть либо реальная частота, либо коллизия с heavy hitter.ε · N. Это значит: на потоке в 1B events с ε = 0.001 ошибка может быть ±1M на любой ключ. Для heavy hitters (которые сами по себе считаются в сотнях миллионов) это шум. Для редких ключей это катастрофа.Отсюда правило большого пальца: CMS — это структура для heavy hitters, а не для rare keys. Если тебе нужны точные frequencies для длинного хвоста — это не CMS.
На канвасе три осмысленных блока:
int32. Это «физическое» представление матрицы C[d][w].Шесть topology.connect() от client к каждой из пяти rows и к heap — это физические writes: на каждый event мы делаем d инкрементов плюс возможно одну операцию с heap. Анимация двигает «event» по этим рёбрам, чтобы показать, что update — это не одна запись, а d параллельных.
ADR-001 на пятой строке матрицы фиксирует выбор CMS как алгоритма; ADR-002 на heap-ноде — почему top-K делается отдельной структурой поверх CMS, а не самим CMS.
insert — multi-hash инкремент во всех d строкахСценарий разворачивает один логический «event» в пять физических writes: C[1][h_1(x)]++, C[2][h_2(x)]++, …, C[5][h_5(x)]++. Каждый шаг показывает свой hash-индекс. Это даёт интуицию «update стоит O(d), не O(1)» — но d маленькое (5-7), и каждая запись — это инкремент 4-байтового счётчика в L1-кеше, поэтому в абсолюте 5-10 ns на event на одном ядре.
Финальная строка сценария упоминает conservative update (Estan & Varghese, SIGCOMM 2003) — оптимизацию, в которой инкрементируются только те ячейки, что равны текущему минимуму. Это режет overestimate на heavy hitters в 2-5x при той же памяти. Стандарт в Cisco NetFlow и большинстве production-реализаций.
point-query — min из d ячеек гасит коллизииСценарий показывает запрос Estimate(x): читаем C[1][h_1(x)] … C[5][h_5(x)], видим разные значения (часть из них раздута коллизиями), берём минимум. Минимум — это строгая нижняя оценка истинной частоты среди ячеек этого ключа, и она же >= true count.
Здесь же объясняется sizing: w = ⌈e / ε⌉, d = ⌈ln(1 / δ)⌉. При ε = 0.001, δ = 0.01 это 5 × 2718 счётчиков по 4 байта — 54 KB на поток в 1B событий. При ε = 0.0001 уходим в ~750 KB. Это главный экономический аргумент CMS: linear improvement по ε стоит logarithmic по памяти.
top-k — CMS + min-heapТут видно, почему top-K — это отдельная структура поверх CMS, а не сам CMS. CMS отвечает только на point queries: «дай мне freq(x) по известному ключу». Он не итерируется и не возвращает список «топ-100 hashtags».
Pattern: на каждом event делаем CMS.update(x), потом count = CMS.estimate(x), потом if count > heap.min: heap.insert(x, count); heap.pop_min(). Heap-операция — O(log K), поэтому добавка к стоимости update небольшая, но накопительно даёт approximate top-K.
В конце сценария — альтернативы для skewed (Zipfian) распределений: Space-Saving (Metwally et al. 2005), HeavyKeeper (USENIX ATC 2018), Lossy Counting. Redis TOPK.* использует HeavyKeeper.
overestimate — rare key vs heavy hitterСценарий-антипример: query на rare key X с истинной частотой 5. Четыре из пяти его строк коллидируют с heavy hitter Y (счётчики 980K, 875K, 920K, 1.1M), и только пятая «чистая» (14). Min = 14. Истина — 5. Ошибка в 3x на ключе с истинной частотой 5 — это ε·N для маленькой ε, но катастрофа в относительных терминах.
Главный урок: CMS не годится для аналитики хвоста в skewed streams. Если у тебя few heavy hitters и long tail rare keys, и вопросы к rare keys — это не та структура.
Fix: больший w (снижает p(collision)), conservative updates (снижает накопленную накачку heavy hitters), либо вообще другой алгоритм (например, sampling-based).
production — где CMS реально работаетСценарий проходит по семи production-деплоям: Redis (CMS.INITBYDIM, TOPK.*), Cisco NetFlow, Cloudflare DNS analytics, Datadog top-K facets, Twitter algebird, Yahoo DataSketches FrequentItems, Apache Kafka Streams, BigQuery / Snowflake query optimizer, Cassandra row cache. Цель — показать, что это не «академическая структура для статьи», а инфраструктурный примитив, в который ты упрёшься, как только начнёшь смотреть в исходники любой serious streaming/analytics-системы.
Контекст. Нужно отвечать на вопросы вида «сколько раз встречался X?» в high-throughput streaming (DDoS, trending, hot keys, top URLs). Точный Map<Key, count> для миллиардов unique keys → гигабайты RAM. Когда таких метрик десятки (per-window × per-dimension × per-service), per-key bookkeeping не масштабируется.
Решение. Count-Min Sketch (Cormode & Muthukrishnan, 2005): матрица d × w счётчиков и d независимых hash-функций. Update — O(d) инкрементов; estimate — O(d) reads + min. Никогда не недооценивает; overestimate ограничен ε · N с вероятностью >= 1 - δ. Sizing w = ⌈e / ε⌉, d = ⌈ln(1 / δ)⌉ — параметры подбираются под конкретный SLA на относительную ошибку.
Альтернативы и почему не они. Count Sketch (Charikar et al. 2002) — даёт unbiased estimate (двусторонняя ошибка), но сложнее анализировать; CMS обычно достаточно. Exact Map — слишком дорого по памяти. Sampling — теряет heavy hitters. HyperLogLog — отвечает на другой вопрос (cardinality, не frequency).
Контекст. CMS не возвращает список ключей — только point query «freq(x)?». Для heavy-hitter detection (DDoS top-talkers, trending topics) нужна структура, которая помнит сами идентификаторы.
Решение. Поверх CMS поддерживается min-heap фиксированного размера K. На каждом event: CMS.update(x); count = CMS.estimate(x); if count > heap.min → heap.insert(x, count); heap.pop_min(). Память — O(K) на heap плюс O(d · w) на CMS. Стоимость event — O(d) + O(log K).
Альтернативы. Space-Saving (Metwally et al. 2005) — deterministic top-K с bounded memory, лучше теоретические гарантии. HeavyKeeper (USENIX ATC 2018) — современная вариация, точнее на Zipfian распределениях, используется в Redis TOPK.*. Lossy Counting (Manku & Motwani) — baseline для сравнения, на практике уступает HeavyKeeper.
Контекст. Vanilla CMS update инкрементит все d ячеек. Heavy hitters при этом «накачивают» все свои ячейки, и rare keys, коллидирующие с ними, страдают сильнее.
Решение. Conservative update (Estan & Varghese, SIGCOMM 2003): инкрементить только те ячейки, что равны текущему минимуму. Это сохраняет инвариант «min = lower bound истинной частоты», но не накачивает «лишние» ячейки сверх необходимого. Снижает overestimate на heavy hitters в 2-5x при той же памяти. Стандарт в network monitoring (Cisco NetFlow). Стоимость — нужно прочитать d ячеек перед записью (хотя в любом случае это нужно для query).
Trade-off. Чуть медленнее update (read-before-write), не mergeable в строгом смысле (после merge инвариант ломается). Если нужен distributed merge — vanilla CMS, если single-node — conservative.
CMS.INITBYDIM, CMS.INCRBY, CMS.QUERY. Отдельно TOPK.* поверх HeavyKeeper для heavy hitters.FrequentItems sketch (Space-Saving variant). Production-grade Java/C++.interactive-queries использует CMS-like для top-K.Когда видишь в архитектуре сервиса «approximate counts», «top-K dashboard», «heavy hitter detection» — это с большой вероятностью либо CMS, либо его потомок (Space-Saving, HeavyKeeper).
w. w = 64 «потому что красивая степень двойки» = коллизии на каждом шагу = бесполезные оценки. Считай w от целевой ε.N, ошибка ε · N растёт линейно. Через неделю любой ответ — мусор.C *= α каждые K events.d функциях. Если h_1, …, h_d не независимы (например, все используют один и тот же seed), min перестаёт давать гарантии. Используй double-hashing trick как в Bloom: h_i(x) = h_a(x) + i · h_b(x) mod w.negative counts из-за коллизий ответы превращаются в мусор. Используй только если controlled (например, decrement парных update'ов своих же).N < 10M и unique keys < 1M? Просто HashMap<Key, Long> — проще, точнее, дешевле памяти инженера.freq > threshold. CMS отвечает только на point queries. Для перечисления нужен либо top-K heap, либо Space-Saving / HeavyKeeper.x in S?). Bloom filter, не CMS.Концепты на этой платформе:
Кейсы, в которых CMS реально работает:
Источники (foundational):
Production docs: