Count-Min Sketch: частоты в потоке и heavy hitters без хранения ключей

Count-Min Sketch простыми словами: как оценить частоту элемента в потоке за фиксированную память, выбор ширины и глубины, conservative update, топ-k, сравнение с Misra-Gries. Код на Python.

13 мин чтенияструктуры данных · системный дизайн · python

Коротко

ПараметрЗначение
Отвечает на вопроссколько раз встретился элемент x
Устройствотаблица d×wd \times w счётчиков и dd хеш-функций
Добавление и запросO(d)O(d), обычно d=4d = 4–77
Памятьw=⌈e/ε⌉w = \lceil e / \varepsilon \rceil, d=⌈ln⁡(1/δ)⌉d = \lceil \ln(1/\delta) \rceil, не зависит от числа ключей
Ошибкатолько завышение, не больше εN\varepsilon N с вероятностью 1−δ1 - \delta
Слияниепоэлементная сумма таблиц
  • Каждый элемент увеличивает по одному счётчику в каждой из dd строк. Ответ на запрос — минимум из этих dd счётчиков.
  • Коллизии только добавляют, поэтому оценка никогда не меньше правды. Минимум — самая честная из dd завышенных оценок.
  • Ошибка аддитивная: εN\varepsilon N от длины всего потока. Популярные элементы считаются почти точно, редкие — бессмысленно. Поэтому главное применение — heavy hitters: топ самых частых.
  • В паре с кучей или словарём на kk кандидатов получается потоковый топ-k без хранения всех ключей.

Задача

Через систему идёт поток событий: поисковые запросы, URL, IP-адреса, хештеги. Нужно в любой момент ответить, сколько раз встретился конкретный ключ, и показать десять самых частых.

Точное решение — словарь ключ → счётчик, та же хеш-таблица, что и в задаче Top K Frequent. Оно работает, пока ключей немного. Но поток уникальных IP за сутки — сотни миллионов, поисковых запросов — миллиарды. Словарь растёт вместе с числом разных ключей, и большая часть памяти уходит на хвост, который встретился один-два раза и никому не интересен.

Хочется структуру фиксированного размера, которая хорошо считает частых и честно ошибается на редких. Это Count-Min Sketch, предложенный Грэмом Кормоудом и С. Мутукришнаном в 2003 году.

Если вам нужно не «сколько раз», а «сколько разных», это другая задача — её решает HyperLogLog. А «встречался ли вообще» — фильтр Блума.

Интуиция: одна строка счётчиков

Начнём с простого. Возьмём массив из ww счётчиков и одну хеш-функцию. Каждый элемент увеличивает счётчик h(x) % w. Частоту x оцениваем значением этого счётчика.

Пока ключей меньше, чем ячеек, и хеш не сталкивает их, всё точно. Когда ключей больше, в ячейку x попадают и чужие элементы. Ошибка всегда в плюс: чужие добавляют, но никто не вычитает.

Насколько большая ошибка? Остальные N−fxN - f_x событий разбросаны по ww ячейкам случайно, поэтому в нашу ячейку в среднем попадает не больше N/wN / w лишних. Но это в среднем: если в ячейку x случайно попал самый популярный ключ, оценка улетит.

Решение — несколько независимых строк. В каждой своя хеш-функция, и маловероятно, что x во всех строках делит ячейку с кем-то тяжёлым. Берём минимум по строкам: хотя бы в одной коллизии почти наверняка мелкие.

Устройство

Таблица d×wd \times w, на каждую строку своя хеш-функция hih_i.

  • add(x, c): для каждой строки ii делаем table[i][h_i(x)] += c.
  • estimate(x): возвращаем min⁡itable[i][hi(x)]\min_i \text{table}[i][h_i(x)].

Для каждой строки значение в ячейке x — это fxf_x плюс частоты всех, кто с ним столкнулся. Каждая строка — оценка сверху, минимум — самая точная из них.

Реализация

import hashlib import math class CountMinSketch: def __init__(self, eps, delta): self.w = math.ceil(math.e / eps) # ширина: точность self.d = math.ceil(math.log(1 / delta)) # глубина: надёжность self.table = [[0] * self.w for _ in range(self.d)] self.total = 0 def _cells(self, item): # один хеш на 128 бит -> два числа -> d «независимых» хешей digest = hashlib.blake2b(str(item).encode(), digest_size=16).digest() h1 = int.from_bytes(digest[:8], "little") h2 = int.from_bytes(digest[8:], "little") | 1 for row in range(self.d): yield row, (h1 + row * h2) % self.w def add(self, item, count=1): self.total += count for row, col in self._cells(item): self.table[row][col] += count def estimate(self, item): return min(self.table[row][col] for row, col in self._cells(item))

Про хеши. Считать dd разных криптографических хешей дорого, поэтому используется приём двойного хеширования (Кирш и Митценмахер): один хеш делим на две половины h1,h2h_1, h_2, и ii-я функция — это h1+i⋅h2h_1 + i \cdot h_2. Для Count-Min и фильтра Блума этого достаточно. Встроенный hash() в Python для строк рандомизируется при каждом запуске, поэтому с ним результаты не воспроизводятся, а два процесса не смогут слить свои таблицы.

Проверка на потоке

Сделаем реалистичный поток: 200 000 обращений к 50 000 страниц с распределением Ципфа — первая страница в два раза популярнее второй, в три раза популярнее третьей и так далее. Так распределены запросы, слова, просмотры и почти всё в вебе.

import random from collections import Counter random.seed(1) keys = [f"/page/{i}" for i in range(50_000)] weights = [1 / (i + 1) for i in range(len(keys))] stream = random.choices(keys, weights, k=200_000) cms = CountMinSketch(eps=0.001, delta=0.01) for key in stream: cms.add(key) exact = Counter(stream) print(f"таблица {cms.d} x {cms.w} = {cms.d * cms.w} счётчиков, ключей {len(exact)}") bound = 0.001 * len(stream) over = [cms.estimate(k) - c for k, c in exact.items()] print("занижений:", sum(o < 0 for o in over)) print("превысили eps*N:", sum(o > bound for o in over), "из", len(over), "граница", bound) for key in ["/page/0", "/page/1", "/page/9", "/page/999", "/page/40000"]: print(f"{key:12} точно {exact[key]:6} оценка {cms.estimate(key):6}")
таблица 5 x 2719 = 13595 счётчиков, ключей 28857 занижений: 0 превысили eps*N: 0 из 28857 граница 200.0 /page/0 точно 17380 оценка 17396 /page/1 точно 8764 оценка 8794 /page/9 точно 1747 оценка 1761 /page/999 точно 10 оценка 53 /page/40000 точно 0 оценка 10

Что видно:

  • Ни одного занижения — так и должно быть.
  • Для лидеров ошибка — доли процента: 17 396 против 17 380.
  • Для страницы с 10 просмотрами оценка 53, в пять раз больше правды. Для страницы, которой в потоке нет вообще, оценка 10. Count-Min не умеет говорить «ноль».
  • 13 595 счётчиков вместо словаря на 28 857 ключей. Разница пока небольшая, но таблица не вырастет и при миллиарде ключей, а словарь вырастет.

Гарантия и выбор размеров

Пусть NN — сумма всех добавлений. Классическая оценка:

fx≤f^x≤fx+εNс вероятностью не меньше 1−δ,f_x \le \hat{f}_x \le f_x + \varepsilon N \quad \text{с вероятностью не меньше } 1 - \delta,

при w=⌈e/ε⌉w = \lceil e / \varepsilon \rceil и d=⌈ln⁡(1/δ)⌉d = \lceil \ln (1/\delta) \rceil.

Откуда это берётся. В одной строке ожидаемое число «чужих» событий в ячейке x не больше N/w=εN/eN / w = \varepsilon N / e. По неравенству Маркова вероятность, что их больше εN\varepsilon N, не больше 1/e1/e. Строки независимы, и минимум превышает εN\varepsilon N, только если превышают все dd строк: вероятность e−d≤δe^{-d} \le \delta.

Отсюда практическое правило:

  • ширина отвечает за величину ошибки: удвоили ww — ошибка упала вдвое;
  • глубина отвечает за то, как редко гарантия нарушается: каждая лишняя строка уменьшает вероятность провала в ee раз.
ε\varepsilonδ\deltawwddСчётчиковПамять при 4 байтах
0,010,0127251 3605 КБ
0,0010,012 719513 59553 КБ
0,00010,00127 1837190 281743 КБ

Обратите внимание: ни в одной формуле нет числа разных ключей. Память зависит только от желаемой точности относительно NN.

Гарантия задана для одного запроса. Если спросить про сто тысяч ключей, около δ\delta из них могут выйти за границу. В нашем эксперименте не вышел ни один: на распределении Ципфа Count-Min работает заметно лучше худшего случая, потому что основная масса NN сосредоточена в немногих ключах.

Conservative update

Простое улучшение, которое почти бесплатно уменьшает завышение. При добавлении x с текущей оценкой mm (минимум по строкам) новая оценка будет m+cm + c. Счётчики, которые уже больше m+cm + c, увеличивать незачем: они и так завышены за счёт чужих, и на ответ про x всё равно не влияют. Поднимаем каждый счётчик только до m+cm + c.

class ConservativeCMS(CountMinSketch): def add(self, item, count=1): self.total += count cells = list(self._cells(item)) target = min(self.table[r][c] for r, c in cells) + count for r, c in cells: # поднимаем только те счётчики, что ниже новой оценки self.table[r][c] = max(self.table[r][c], target)

На том же потоке:

CountMinSketch среднее завышение 15.9, максимум 90 ConservativeCMS среднее завышение 7.9, максимум 58

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

Heavy hitters: топ-k в потоке

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

class TopK: def __init__(self, k, eps=0.001, delta=0.01): self.k = k self.cms = CountMinSketch(eps, delta) self.top = {} # кандидат -> оценка частоты def add(self, item): self.cms.add(item) est = self.cms.estimate(item) if item in self.top or len(self.top) < self.k: self.top[item] = est return weakest = min(self.top, key=self.top.get) if est > self.top[weakest]: del self.top[weakest] self.top[item] = est def result(self): return sorted(self.top.items(), key=lambda kv: -kv[1]) t = TopK(5) for key in stream: t.add(key) print(t.result()) print(exact.most_common(5))
[('/page/0', 17396), ('/page/1', 8784), ('/page/2', 6003), ('/page/3', 4409), ('/page/4', 3602)] [('/page/0', 17380), ('/page/1', 8764), ('/page/2', 5984), ('/page/3', 4390), ('/page/4', 3582)]

Состав и порядок совпали, частоты завышены на 16–20.

Поиск слабейшего здесь — min по словарю за O(k)O(k). Для kk в десятки это быстрее и проще всего. Для больших kk берут min-кучу: вершина — слабейший кандидат. Сложность в том, что оценка кандидата растёт, а в стандартной куче нельзя обновить элемент в середине. Обычно используют ленивое удаление: кладут новую запись, а устаревшие выбрасывают, когда они всплывают на вершину.

Одна тонкость: элемент, который был вытеснен, а потом вернулся, сразу получает правильную оценку из скетча, потому что скетч помнит всё. В этом преимущество над наивным «держим только k счётчиков».

Альтернативы

Misra-Gries: детерминированный топ

Если нужны только тяжёлые элементы, а не частоты произвольных ключей, есть алгоритм Мисры–Гриса (1982). Он держит не больше k−1k - 1 счётчиков. Новый элемент получает счётчик, если есть место; если места нет, все счётчики уменьшаются на единицу, и обнулившиеся удаляются.

def misra_gries(stream, k): """Не больше k-1 счётчиков; находит всех, у кого частота > N/k.""" counters = {} for x in stream: if x in counters: counters[x] += 1 elif len(counters) < k - 1: counters[x] = 1 else: for key in list(counters): counters[key] -= 1 if counters[key] == 0: del counters[key] return counters

Гарантия детерминированная: каждый элемент с частотой больше N/kN/k останется в словаре, а его счётчик занижен не больше чем на N/kN/k. На нашем потоке при k=100k = 100 лидер получил 15 731 вместо 17 380 — занижение 1 649, в пределах порога 2 000. Ошибка в другую сторону, чем у Count-Min.

При k=2k = 2 это ровно алгоритм Бойера–Мура для элемента большинства: один кандидат и счётчик. Хороший мостик на собеседовании: «Majority Element — частный случай потоковых heavy hitters».

Близкий родственник — Space-Saving (Метвалли и др., 2005): вместо уменьшения всех счётчиков новый элемент вытесняет минимальный и наследует его значение плюс один. Его используют, когда нужен точный список топа с оценками сверху.

Минус обоих: они не отвечают на вопрос про произвольный ключ, только про тех, кто в словаре. И их сложнее сливать между машинами, хотя для Misra-Gries способ есть.

Count Sketch: без систематического сдвига

Count Sketch (Чарикар, Чен, Фарах-Колтон, 2002) добавляет к каждому элементу случайный знак ±1\pm 1 в каждой строке. Чужие элементы теперь в среднем гасят друг друга, оценка строки несмещённая, а итог — медиана по строкам вместо минимума.

Count Sketch: средняя ошибка -0.1, средний модуль 7.3 Count-Min: средняя ошибка 15.9, средний модуль 15.9

Те же 5 × 2719 счётчиков: Count Sketch ошибается в обе стороны, но в среднем вдвое меньше. Для страницы с 10 просмотрами он дал 12, а Count-Min — 53. Его граница ошибки выражается через корень из суммы квадратов частот, а не через NN, и на тяжёлых хвостах она лучше. Цена — оценка может оказаться отрицательной или меньше правды, а это неудобно, если вы, например, решаете, банить ли IP.

Сводка

СтруктураОшибкаПроизвольный ключСлияниеУдаления
Словарьнетдадада
Count-Minтолько вверх, ≤εN\le \varepsilon Nдасумма таблицда, если частоты не уходят в минус
Count-Min + CUтолько вверх, меньшеданетнет
Count Sketchв обе стороны, несмещённаядасумма таблицда
Misra-Griesтолько вниз, ≤N/k\le N/kнет, только топесть алгоритмнет

Слияние и окна

Count-Min линеен: таблица потока A плюс таблица потока B — это таблица потока A+B. Важно только, чтобы размеры и хеш-функции совпадали.

half = len(stream) // 2 a, b = CountMinSketch(0.001, 0.01), CountMinSketch(0.001, 0.01) for key in stream[:half]: a.add(key) for key in stream[half:]: b.add(key) merged = CountMinSketch(0.001, 0.01) merged.table = [[x + y for x, y in zip(ra, rb)] for ra, rb in zip(a.table, b.table)] print("слияние совпадает:", merged.table == cms.table) # True

Отсюда две практические схемы:

  • Распределённый подсчёт. Каждый сервер ведёт свой скетч, раз в минуту отправляет 50 КБ агрегатору, тот складывает. Ни одного ключа по сети.
  • Скользящее окно. Держим скетч на каждую минуту и кольцевой буфер последних 60. Частота за час — сумма 60 таблиц, старая минута просто выбрасывается. Так строятся «тренды за последний час» и детекторы всплесков. Та же идея окон встречается в rate limiter.

Можно и вычитать: таблица часа минус таблица самой старой минуты. Это законно для обычного Count-Min, но не для conservative update.

Где применяется

  • Мониторинг сети. Какие IP шлют больше всего пакетов, кто устроил DDoS. Скетчи считают прямо на роутерах и в программируемых коммутаторах, где памяти мегабайты.
  • Тренды. Самые частые поисковые запросы, хештеги, товары за последний час.
  • Кэши. Политика допуска TinyLFU оценивает частоту обращений к ключу через Count-Min с 4-битными счётчиками и пускает в кэш только то, что популярнее вытесняемого. Она используется в Java-библиотеке Caffeine. Подробнее о вытеснении — в статье про стратегии кэширования.
  • Базы и движки обработки данных. В Redis есть команды CMS.INITBYPROB, CMS.INCRBY, CMS.QUERY, CMS.MERGE (раньше — модуль RedisBloom, в новых версиях входит в Redis), а также структура TOPK для heavy hitters. В Apache Spark — df.stat.countMinSketch(...).
  • NLP и машинное обучение. Частоты n-грамм в огромных корпусах, хеширование признаков.

Типичные ошибки

Ждать точности на редких ключах. Ошибка εN\varepsilon N одинакова для всех. При NN = 10 млн и ε=0,001\varepsilon = 0{,}001 это 10 000 — для ключа с частотой 5 оценка бессмысленна. Count-Min — инструмент для тяжёлых элементов.

Путать роли ww и dd. Увеличивать глубину, чтобы уменьшить ошибку, — расточительно: ошибку определяет ширина. Глубина нужна для надёжности, 4–7 строк хватает почти всегда.

Зависимые хеши. Если все строки используют одну функцию или функции коррелируют, dd строк превращаются в одну. С двойным хешированием обязательно сделать h2h_2 ненулевым (в коде — | 1).

Разные хеши на разных машинах. Встроенный hash() в Python рандомизирован, в Java hashCode у разных версий классов может отличаться. Слить такие таблицы нельзя — и ошибку никто не заметит, оценки просто станут мусором.

Переполнение счётчиков. 32-битного счётчика хватит на 4 млрд событий. В долгоживущем скетче или при весах в байтах трафика берите 64 бита или периодически сбрасывайте.

Conservative update со слиянием или удалениями. Он ломает линейность. Если нужно складывать таблицы, используйте обычное обновление.

Count-Min вместо HyperLogLog. Сумма или число непустых ячеек не дают числа уникальных ключей. Для кардинальности — HyperLogLog.

Как это спрашивают на собеседовании

Системный дизайн. «Спроектируйте топ-10 самых популярных запросов за последний час», «трендовые хештеги», «самые просматриваемые видео в реальном времени», «найти IP, от которых идёт подозрительно много запросов». Хороший ответ строится так:

  1. Точное решение — словарь плюс куча. Оценить память: сотни миллионов ключей не помещаются на одну машину.
  2. Предложить Count-Min Sketch плюс топ-k кандидатов, назвать гарантию: только завышение, не больше εN\varepsilon N.
  3. Посчитать размер: ε=10−4\varepsilon = 10^{-4}, δ=10−3\delta = 10^{-3} — меньше мегабайта.
  4. Распределить: скетч на каждом сервере, агрегатор складывает таблицы. Окно — кольцо минутных скетчей.
  5. Сказать про ограничения: редкие ключи неточны; если нужен точный топ, второй проход по кандидатам с точным подсчётом.

Здесь пригодится навык прикидок на салфетке: интервьюер ждёт, что вы посчитаете память точного решения и скетча.

Алгоритмическая секция. Скетч не напишут как задачу, но к нему подводят follow-up вопросы:

  • Top K Frequent Elements — «а если данные не помещаются в память и идут потоком?»
  • Majority Element — «а если нужны все элементы с частотой больше n/kn/k?» Ответ — Misra-Gries.
  • «Как выбрать случайный элемент из потока?» — это уже reservoir sampling, ещё одна потоковая техника.

Вопросы вглубь:

  1. Почему минимум, а не среднее? (Каждая строка — оценка сверху; среднее тянет вверх самая неудачная строка.)
  2. Почему ошибка только в одну сторону? Можно ли сделать несмещённую? (Count Sketch.)
  3. Как поддержать удаление? (Вычитание работает, пока реальные частоты неотрицательны.)
  4. Чем Count-Min похож на фильтр Блума? (Те же dd хешей, только вместо битов счётчики; Блум — частный случай «частота больше нуля».)

Что запомнить

  • Count-Min Sketch — таблица d×wd \times w счётчиков: добавление увеличивает по счётчику в каждой строке, запрос берёт минимум.
  • Оценка никогда не занижает и завышает не больше чем на εN\varepsilon N с вероятностью 1−δ1 - \delta; w=e/εw = e/\varepsilon, d=ln⁡(1/δ)d = \ln(1/\delta).
  • Память не зависит от числа ключей. Хорошо считает тяжёлых, плохо — хвост.
  • Скетчи складываются: распределённый подсчёт и скользящие окна почти бесплатны.
  • Для топ-k нужен рядом словарь или куча на kk кандидатов. Если нужны только тяжёлые и детерминированно — Misra-Gries; если важна несмещённость — Count Sketch.

Потренироваться в спокойной обстановке

Все задачи